NCBI C++ ToolKit
rlebtv.h
Go to the documentation of this file.

Go to the SVN repository for this file.

1 /*
2 Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
3 
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 
16 For more information please visit: http://bitmagic.io
17 */
18 
19 #ifndef RLEBTV__H__INCLUDED__
20 #define RLEBTV__H__INCLUDED__
21 
22 /**
23  GAP vector is designed to be very small.
24  The size of buffer is fixed 128 short values.
25  First word is a start flag.
26  Used for debugging purposes.
27 
28  \internal
29 */
31 {
32 public:
34  {
35  m_buf[0] = 1 << 3; // initial length = 1;
36 
37  if (init)
38  {
39  m_buf[0] ^= 1;
40  }
41  m_buf[1] = gap_max_bits - 1;
42  }
43 
44  /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
45  int is_bit_true(unsigned pos) const;
46  int test(unsigned pos) const;
47 
48  /// Sets bit number pos to 1
49  /// returns true if operation sucessful, false if GAP threashold reached and
50  /// we need to convert block to true bitblock
51  bool set_bit(unsigned pos);
52 
53  /// Sets bit number pos to 0
54  bool clear_bit(unsigned pos);
55 
56  /// Counts number of bits ON
57  unsigned bit_count() const;
58 
59  unsigned count_range(unsigned left,
60  unsigned right,
61  unsigned* d=0) const;
62 
63  void control() const;
64 
65  void convert_to_bitset(unsigned* dest) const;
66 
67  int combine_and(const gap_word_t* other);
68 
69  const gap_word_t* get_buf() const { return m_buf; }
70 
71  void invert() { *m_buf = bm::gap_word_t(1 - *m_buf); }
72 
73  void temp_invert() const;
74 
75  void combine_or(const gap_vector& vect);
76  void combine_sub(const gap_vector& vect);
77  void combine_xor(const gap_vector& vect);
78 
79  gap_word_t* get_buf() { return m_buf; }
80 
81  int compare(const gap_vector& vect);
82 
83  bool get_last(unsigned* last) const;
84 
85 private:
87 };
88 
89 
90 inline void gap_vector::combine_or(const gap_vector& vect)
91 {
92 
93  gap_word_t tmp_buf[bm::gap_max_buff_len * 3] = {0,}; // temporary result
94  unsigned len, dsize;
95  gap_word_t* res = bm::gap_operation_or(m_buf, vect.get_buf(), tmp_buf, dsize);
96  len = bm::gap_length(res);
97 
98  if (res == tmp_buf)
99  {
100  assert(len);
101  ::memcpy(m_buf, tmp_buf, (len+1)*sizeof(gap_word_t));
102  }
103  else
104  {
105  assert(res == m_buf);
106  }
107 
108 }
109 
110 inline void gap_vector::combine_xor(const gap_vector& vect)
111 {
112 
113  gap_word_t tmp_buf[gap_max_buff_len * 3] = {0,}; // temporary result
114  unsigned len, dsize;
115  gap_word_t* res =
116  bm::gap_operation_xor(m_buf, vect.get_buf(), tmp_buf, dsize);
117  len = bm::gap_length(res);
118 
119  if (res == tmp_buf)
120  {
121  assert(len);
122  ::memcpy(m_buf, tmp_buf, (len+1)*sizeof(gap_word_t));
123  }
124  else
125  {
126  assert(res == m_buf);
127  }
128 
129 }
130 
131 
132 inline void gap_vector::combine_sub(const gap_vector& vect)
133 {
134  unsigned dsize;
135  gap_word_t tmp_buf[bm::gap_max_buff_len * 3] = {0,}; // temporary result
136  gap_word_t* res =
137  bm::gap_operation_sub(m_buf, vect.get_buf(), tmp_buf, dsize);
138  unsigned len = bm::gap_length(res);
139 
140  if (res == tmp_buf)
141  {
142  assert(len);
143  ::memcpy(m_buf, tmp_buf, (len+1) * sizeof(gap_word_t));
144  }
145  else
146  {
147  assert(res == m_buf);
148  }
149 
150 }
151 
152 
153 
154 inline void gap_vector::temp_invert() const
155 {
156  gap_word_t* buf = const_cast<gap_word_t*>(m_buf);
157  *buf ^= 1;
158 }
159 
160 inline void gap_vector::control() const
161 {
162  unsigned sum = bm::gap_control_sum(m_buf);
163  if(sum != bm::gap_max_bits-1)
164  {
165  assert(0);
166  cout << "GAP Control failed." << endl;
167  exit(1);
168  }
169  unsigned len = bm::gap_length(m_buf);
170  gap_word_t prev = m_buf[1];
171  for (unsigned i = 2; i < len; ++i)
172  {
173  if (i != len-1)
174  {
175  if (m_buf[i] <= prev)
176  {
177  assert(0);
178  cout << "GAP sequence control failed." << endl;
179  exit(1);
180  }
181  }
182  else
183  {
185  }
186  prev = m_buf[i];
187  }
188 }
189 
190 inline int gap_vector::is_bit_true(unsigned pos) const
191 {
192  auto r1 = bm::gap_test(m_buf, pos);
193  auto r2 = bm::gap_test_unr(m_buf, pos);
194  assert(r1 == r2);
195  return int(r2);
196 }
197 
198 inline bool gap_vector::get_last(unsigned* last) const
199 {
200  bool found = bm::gap_find_last(m_buf, last);
201  return found;
202 }
203 
204 
205 inline int gap_vector::test(unsigned pos) const
206 {
207  return is_bit_true(pos);
208 }
209 
210 
211 unsigned gap_vector::bit_count() const
212 {
213  return bm::gap_bit_count(m_buf);
214 }
215 
216 unsigned gap_vector::count_range(unsigned left,
217  unsigned right,
218  unsigned*) const
219 {
220  return bm::gap_bit_count_range(m_buf, (gap_word_t)left, (gap_word_t)right);
221 }
222 
223 
224 
225 // returns destination size
226 
227 
229 {
230 
231  gap_word_t tmp_buf[gap_max_buff_len * 3] = {0,}; // temporary result
232  unsigned dsize;
233 
234  gap_word_t* res = bm::gap_operation_and(m_buf, other, tmp_buf, dsize);
235  unsigned len = bm::gap_length(res);
236 
237  if (res == tmp_buf)
238  {
239  assert(len);
240  ::memcpy(m_buf, tmp_buf, (len+1) * sizeof(gap_word_t));
241  }
242  else
243  {
244  assert(res == m_buf);
245  }
246  return 0;
247 
248 }
249 
250 
251 inline bool gap_vector::set_bit(unsigned pos)
252 {
253  unsigned is_set;
254  bm::gap_set_value(1, m_buf, pos, &is_set);
255  return is_set!=0;
256 }
257 
258 inline bool gap_vector::clear_bit(unsigned pos)
259 {
260  unsigned is_set;
261  bm::gap_set_value(0, m_buf, pos, &is_set);
262  return is_set!=0;
263 }
264 
265 inline void gap_vector::convert_to_bitset(unsigned* dest) const
266 {
268 }
269 
270 inline int gap_vector::compare(const gap_vector& vect)
271 {
272  return bm::gapcmp(m_buf, vect.get_buf());
273 }
274 
275 
276 #endif
277 
278 
GAP vector is designed to be very small.
Definition: rlebtv.h:31
void combine_sub(const gap_vector &vect)
Definition: rlebtv.h:132
const gap_word_t * get_buf() const
Definition: rlebtv.h:69
int is_bit_true(unsigned pos) const
Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
Definition: rlebtv.h:190
bool set_bit(unsigned pos)
Sets bit number pos to 1 returns true if operation sucessful, false if GAP threashold reached and we ...
Definition: rlebtv.h:251
gap_word_t * get_buf()
Definition: rlebtv.h:79
void temp_invert() const
Definition: rlebtv.h:154
void combine_xor(const gap_vector &vect)
Definition: rlebtv.h:110
void invert()
Definition: rlebtv.h:71
int compare(const gap_vector &vect)
Definition: rlebtv.h:270
int combine_and(const gap_word_t *other)
Definition: rlebtv.h:228
void convert_to_bitset(unsigned *dest) const
Definition: rlebtv.h:265
bool clear_bit(unsigned pos)
Sets bit number pos to 0.
Definition: rlebtv.h:258
int test(unsigned pos) const
Definition: rlebtv.h:205
void combine_or(const gap_vector &vect)
Definition: rlebtv.h:90
void control() const
Definition: rlebtv.h:160
unsigned count_range(unsigned left, unsigned right, unsigned *d=0) const
Definition: rlebtv.h:216
gap_vector(gap_word_t init=0)
Definition: rlebtv.h:33
bool get_last(unsigned *last) const
Definition: rlebtv.h:198
gap_word_t m_buf[bm::gap_max_buff_len+3]
Definition: rlebtv.h:86
unsigned bit_count() const
Counts number of bits ON.
Definition: rlebtv.h:211
static void DLIST_NAME() init(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:40
static DLIST_TYPE *DLIST_NAME() last(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:51
static DLIST_TYPE *DLIST_NAME() prev(DLIST_LIST_TYPE *list, DLIST_TYPE *item)
Definition: dlist.tmpl.h:61
unsigned gap_bit_count_range(const T *const buf, unsigned left, unsigned right) noexcept
Counts 1 bits in GAP buffer in the closed [left, right] range.
Definition: bmfunc.h:2393
gap_word_t * gap_operation_xor(const gap_word_t *vect1, const gap_word_t *vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
GAP XOR operation.
Definition: bmfunc.h:6585
gap_word_t * gap_operation_or(const gap_word_t *vect1, const gap_word_t *vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
GAP OR operation.
Definition: bmfunc.h:6666
unsigned gap_test(const T *buf, unsigned pos) noexcept
Tests if bit = pos is true.
Definition: bmfunc.h:1790
unsigned gap_bit_count(const T *buf, unsigned dsize=0) noexcept
Calculates number of bits ON in GAP buffer.
Definition: bmfunc.h:2299
unsigned gap_control_sum(const T *buf) noexcept
Calculates sum of all words in GAP block. (For debugging purposes)
Definition: bmfunc.h:4521
unsigned gap_test_unr(const T *buf, const unsigned pos) noexcept
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
Definition: bmfunc.h:1833
void gap_convert_to_bitset(unsigned *dest, const T *buf, unsigned len=0) noexcept
GAP block to bitblock conversion.
Definition: bmfunc.h:4475
gap_word_t * gap_operation_sub(const gap_word_t *vect1, const gap_word_t *vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
GAP SUB (AND NOT) operation.
Definition: bmfunc.h:6712
gap_word_t * gap_operation_and(const gap_word_t *vect1, const gap_word_t *vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
GAP AND operation.
Definition: bmfunc.h:6518
unsigned gap_find_last(const T *buf, unsigned *last) noexcept
GAP block find the last set bit.
Definition: bmfunc.h:1667
unsigned gap_set_value(unsigned val, T *buf, unsigned pos, unsigned *is_set) noexcept
Sets or clears bit in the GAP buffer.
Definition: bmfunc.h:3254
int gapcmp(const T *buf1, const T *buf2) noexcept
Lexicographical comparison of GAP buffers.
Definition: bmfunc.h:2848
bm::gap_word_t gap_length(const bm::gap_word_t *buf) noexcept
Returs GAP block length.
Definition: bmfunc.h:1603
unsigned int
A callback function used to compare two keys in a database.
Definition: types.hpp:1210
exit(2)
char * buf
int i
int len
const unsigned gap_max_buff_len
Definition: bmconst.h:80
unsigned short gap_word_t
Definition: bmconst.h:78
const unsigned gap_max_bits
Definition: bmconst.h:81
#define assert(x)
Definition: srv_diag.hpp:58
Modified on Mon May 27 04:38:19 2024 by modify_doxy.py rev. 669887