Debian Codegraph @

fast-dynamic-bitset/fast-dynamic-bitset.h

raw
1 /* BaitFisher (version 1.2.7) a program for designing DNA target enrichment baits
2 * Copyright 2013-2016 by Christoph Mayer
3 *
4 * This source file is part of the BaitFisher-package.
5 *
6 * This program is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with BaitFisher. If not, see <http://www.gnu.org/licenses/>.
18 *
19 *
20 * For any enquiries send an Email to Christoph Mayer
21 * [email protected]
22 *
23 * When publishing work that is based on the results please cite:
24 * Mayer et al. 2016: BaitFisher: A software package for multi-species target DNA enrichment probe design
25 *
26 */
27 #ifndef FAST_DYNAMIC_BITSET_H
28 #define FAST_DYNAMIC_BITSET_H
29
30 // 23.7.2014: Since unsigned long has 64 bits on some computers unsinged long cannot be used as
31 // the word data type without having to change large parts of the code.
32
33 #include <iostream>
34 #include <fstream>
35 #include <cstring>
36 #include <string>
37
38 //#define __num_bits_in_word (( unsigned long)8*sizeof(unsigned long))
39 //#define __get_word_index(i) (( unsigned long)i/(__num_bits_in_word))
40 //#define __get_num_words(size) (((unsigned long)size+__num_bits_in_word-1ul)/(__num_bits_in_word))
41 //#define __get_empty_mask(size,numWords) ( 0xFFFFFFFF >> numWords*__num_bits_in_word - size )
42 //#define __get_num_byte(words) ( words*sizeof(unsigned long))
43
44 #define __num_bits_in_word 32
45 #define __get_word_index(i) (i >> 5)
46 #define __get_word_offset(i) (i & 31)
47 #define __get_num_words(size) ((size + 31) >> 5)
48 #define __get_num_byte(words) ( words*4 )
49
50 // Must be a 32 bit integer type:
51 //typedef unsigned bitset_word_type;
52 typedef unsigned my_uint_32;
53
54 const unsigned char __num_bits_table[256] =
55 {
56 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
57 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
58 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
59 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
60 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
61 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
62 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
63 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
64 };
65
66 const my_uint_32 __mask_table[32] =
67 {
68 0x00000001, 0x00000002, 0x00000004, 0x00000008,
69 0x00000010, 0x00000020, 0x00000040, 0x00000080,
70 0x00000100, 0x00000200, 0x00000400, 0x00000800,
71 0x00001000, 0x00002000, 0x00004000, 0x00008000,
72
73 0x00010000, 0x00020000, 0x00040000, 0x00080000,
74 0x00100000, 0x00200000, 0x00400000, 0x00800000,
75 0x01000000, 0x02000000, 0x04000000, 0x08000000,
76 0x10000000, 0x20000000, 0x40000000, 0x80000000
77 };
78
79
80 const my_uint_32 __empty_mask_table[32] =
81 {
82 0xFFFFFFFF, 0x7FFFFFFF, 0x3FFFFFFF, 0x1FFFFFFF,
83 0x0FFFFFFF, 0x07FFFFFF, 0x03FFFFFF, 0x01FFFFFF,
84 0x00FFFFFF, 0x007FFFFF, 0x003FFFFF, 0x001FFFFF,
85 0x000FFFFF, 0x0007FFFF, 0x0003FFFF, 0x0001FFFF,
86
87 0x0000FFFF, 0x00007FFF, 0x00003FFF, 0x00001FFF,
88 0x00000FFF, 0x000007FF, 0x000003FF, 0x000001FF,
89 0x000000FF, 0x0000007F, 0x0000003F, 0x0000001F,
90 0x0000000F, 0x00000007, 0x00000003, 0x00000001
91 };
92
93
94 class fast_dynamic_bitset
95 {
96 public:
97 class exception {};
98 class outOfRange : public exception {};
99 class zeroSizeBitset : public exception {};
100 class UnequalSizedBitsets : public exception {};
101
102 private:
103 my_uint_32 *__data;
104 my_uint_32 __size;
105 my_uint_32 __numWords;
106 // my_uint_32 __empty_mask;
107
108 public:
109 fast_dynamic_bitset(my_uint_32 size=0):__size(size),__numWords(__get_num_words(size))
110 {
111 // if (size == 0)
112 // throw zeroSizeBitset();
113
114 // __size = size;
115 __data = new my_uint_32 [__numWords];
116 // __empty_mask = __empty_mask_table[__numWords * __num_bits_in_word - size];
117 // 0xFFFFFFFF >> (__numWords * __num_bits_in_word - size);
118 }
119
120 fast_dynamic_bitset(const fast_dynamic_bitset &a)
121 {
122 memcpy((void*)this, (void*) &a, sizeof(fast_dynamic_bitset) );
123 __data = new my_uint_32 [__numWords];
124 memcpy((void*)__data,(void*)a.__data, __get_num_byte(__numWords) );
125 }
126
127 ~fast_dynamic_bitset() {
128 delete [] __data;
129 // std::cout << "Dest" << std::endl;
130 }
131
132 my_uint_32 size()
133 {
134 return __size;
135 }
136
137 fast_dynamic_bitset& operator=(const fast_dynamic_bitset &a)
138 {
139 if ( __size != a.__size )
140 {
141 delete [] __data;
142 memcpy((void*)this, (void*) &a, sizeof(fast_dynamic_bitset) );
143 __data = new my_uint_32 [__numWords];
144 memcpy((void*)__data,(void*)a.__data, __get_num_byte(__numWords) );
145 }
146 else
147 {
148 memcpy((void*)__data,(void*)a.__data, __get_num_byte(__numWords) );
149 }
150 return *this;
151 }
152
153
154 void reset()
155 {
156 memset((void*)__data, 0, __get_num_byte(__numWords));
157 }
158
159 void clear()
160 {
161 reset();
162 }
163
164 void set()
165 {
166 for(my_uint_32 index=0; index < __numWords-1; ++index)
167 __data[index] = ~static_cast<my_uint_32>(0);
168 __data[__numWords-1] = __empty_mask_table[__numWords * __num_bits_in_word - __size];
169 }
170
171 void flip()
172 {
173 for(my_uint_32 index=0; index < __numWords; ++index)
174 __data[index] = ~__data[index];
175 __data[__numWords-1] &= __empty_mask_table[__numWords * __num_bits_in_word - __size];
176 }
177
178
179 void unchecked_set(my_uint_32 i)
180 {
181 __data[__get_word_index(i)] |= __mask_table[__get_word_offset(i)];
182 }
183
184 void set(my_uint_32 i)
185 {
186 if (i >= __size)
187 throw outOfRange();
188
189 __data[__get_word_index(i)] |= __mask_table[__get_word_offset(i)];
190 }
191
192 void unchecked_reset(my_uint_32 i)
193 {
194 __data[__get_word_index(i)] ^= __mask_table[__get_word_offset(i)];
195 }
196
197 void reset(my_uint_32 i)
198 {
199 if (i >= __size)
200 throw outOfRange();
201
202 __data[__get_word_index(i)] ^= __mask_table[__get_word_offset(i)];
203 }
204
205 void unchecked_set(my_uint_32 i, my_uint_32 x)
206 {
207 if (x==0)
208 unchecked_reset(i);
209 else
210 unchecked_set(i);
211 }
212
213 void set(my_uint_32 i, my_uint_32 x)
214 {
215 if (x==0)
216 reset(i);
217 else
218 set(i);
219 }
220
221 bool unchecked_test(my_uint_32 i) const
222 {
223 return (__data[__get_word_index(i)] & __mask_table[__get_word_offset(i)]);
224 }
225
226 bool test(my_uint_32 i) const
227 {
228 // if (i >= __size)
229 // throw outOfRange();
230
231 return (__data[__get_word_index(i)] & __mask_table[__get_word_offset(i)]);
232 }
233
234 void unchecked_flip(my_uint_32 i)
235 {
236 __data[__get_word_index(i)] ^= __mask_table[__get_word_offset(i)];
237 }
238
239 void flip(my_uint_32 i)
240 {
241 // if (i >= __size)
242 // throw outOfRange();
243
244 __data[__get_word_index(i)] ^= __mask_table[__get_word_offset(i)];
245 }
246
247 void operator&=(const fast_dynamic_bitset &a)
248 {
249 // if ( a.__numWords != __numWords )
250 // throw UnequalSizedBitsets();
251
252 for(my_uint_32 index=0; index < __numWords; ++index)
253 __data[index] &= a.__data[index];
254 }
255
256 void operator|=(const fast_dynamic_bitset &a)
257 {
258 // if ( a.__numWords != __numWords )
259 // throw UnequalSizedBitsets();
260
261 for(my_uint_32 index=0; index < __numWords; ++index)
262 __data[index] |= a.__data[index];
263 }
264
265 void operator^=(const fast_dynamic_bitset &a)
266 {
267 // if ( a.__numWords != __numWords )
268 // throw UnequalSizedBitsets();
269
270 for(my_uint_32 index=0; index < __numWords; ++index)
271 __data[index] ^= a.__data[index];
272 }
273
274 fast_dynamic_bitset operator~()
275 {
276 fast_dynamic_bitset a=*this;
277 a.flip();
278 return a;
279 }
280
281 std::string as_string_highBitsFirst() const
282 {
283 std::string str;
284
285 /* // Print overhead-empty bit in bitset: */
286 /* //------------------------------------- */
287 /* my_uint_32 k = __numWords * __num_bits_in_word; */
288 /* while (k != __size) */
289 /* { */
290 /* --k; */
291 /* if (unchecked_test(k)) */
292 /* str.push_back('1'); */
293 /* else */
294 /* str.push_back('0'); */
295 /* } */
296 /* // os << "|"; */
297
298 // Print bitset with high bits first
299 //-----------------------------------
300 my_uint_32 i = __size;
301
302 while (i != 0)
303 {
304 --i;
305 if (unchecked_test(i))
306 str.push_back('1');
307 else
308 str.push_back('0');
309 }
310 return str;
311 }
312
313 std::string as_string_lowBitsFirst() const
314 {
315 std::string str;
316
317 // Print bitset with low bits first
318 //----------------------------------
319 my_uint_32 i = 0;
320
321 while (i < __size )
322 {
323 if (unchecked_test(i))
324 str.push_back('1');
325 else
326 str.push_back('0');
327 ++i;
328 }
329 return str;
330 }
331
332
333 std::ostream& print_lowBitsFirst(std::ostream& os) const
334 {
335 // Print bitset with low bits first
336 //----------------------------------
337 my_uint_32 i = 0;
338
339 while (i < __size )
340 {
341 if (unchecked_test(i))
342 os << "1";
343 else
344 os << "0";
345 ++i;
346 }
347
348 /* // Print overhead-empty bit in bitset: */
349 /* //------------------------------------- */
350 /* os << "|"; */
351 /* while ( i < __numWords * __num_bits_in_word) */
352 /* { */
353 /* if (unchecked_test(i)) */
354 /* os << "1"; */
355 /* else */
356 /* os << "0"; */
357 /* ++i; */
358 /* } */
359 return os;
360 }
361
362 void binary_out(std::ostream& os)
363 {
364 os.write((char*)__data,__numWords*sizeof(my_uint_32));
365 }
366
367 void binary_in(std::istream& is)
368 {
369 is.read((char*) __data,__numWords*sizeof(my_uint_32));
370 }
371
372
373 my_uint_32 count() const
374 {
375 my_uint_32 sum = 0;
376 unsigned char *ptr = (unsigned char*) __data;
377 unsigned char *ptr_end = ptr + __get_num_byte(__numWords);
378
379 while ( ptr != ptr_end )
380 {
381 sum += __num_bits_table[*ptr];
382 ++ptr;
383 }
384 return sum;
385 }
386
387 bool any() const
388 {
389 for(my_uint_32 i=0; i < __numWords; ++i)
390 {
391 if (__data[i])
392 return true;
393 }
394 return false;
395 }
396
397 bool none() const
398 {
399 return !any();
400 }
401
402 void operator++()
403 {
404 my_uint_32 i=0;
405
406 while ( i < __numWords )
407 {
408 ++__data[i];
409 if (__data[i]) // if __data[i] == 0 we have to carry a bit otherwise we are done.
410 break;
411 ++i;
412 }
413 }
414
415 friend bool operator!=(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
416 {
417 // if ( a.__numWords != b.__numWords )
418 // throw UnequalSizedBitsets();
419
420 for (my_uint_32 i = 0; i < a.__numWords; --i)
421 {
422 if ( a.__data[i] != b.__data[i] )
423 return true;
424 }
425 return false;
426 }
427
428 friend bool operator==(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
429 {
430 return !(a != b);
431 }
432
433 friend bool operator<(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
434 {
435 // if ( a.__numWords != b.__numWords )
436 // throw UnequalSizedBitsets();
437
438 for (my_uint_32 i=a.__numWords-1; i > 0; --i)
439 {
440 if ( a.__data[i] < b.__data[i] )
441 return true;
442 else if (a.__data[i] > b.__data[i])
443 return false;
444 }
445 if ( a.__data[0] < b.__data[0] )
446 return true;
447 else
448 return false;
449 }
450
451 friend bool operator>(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
452 {
453 // if ( a.__numWords != b.__numWords )
454 // throw UnequalSizedBitsets();
455
456 for (my_uint_32 i=a.__numWords-1; i > 0; --i)
457 {
458 if ( a.__data[i] != b.__data[i] )
459 return a.__data[i] > b.__data[i];
460 }
461 return a.__data[0] > b.__data[0];
462 }
463
464 friend bool operator<=(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
465 {
466 return !(a>b);
467 }
468
469 friend bool operator>=(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
470 {
471 return !(a<b);
472 }
473
474
475 };
476
477
478
479 // Global functions for fast_dynamic_bitsets
480
481 inline fast_dynamic_bitset operator&(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
482 {
483 fast_dynamic_bitset c(a);
484 c &= b;
485 return c;
486 }
487
488 inline fast_dynamic_bitset operator|(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
489 {
490 fast_dynamic_bitset c(a);
491 c |= b;
492 return c;
493 }
494
495 inline fast_dynamic_bitset operator^(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
496 {
497 fast_dynamic_bitset c(a);
498 c ^= b;
499 return c;
500 }
501
502 inline std::ostream& operator<<(std::ostream& os, const fast_dynamic_bitset& b)
503 {
504 b.print_lowBitsFirst(os);
505 return os;
506 }
507
508
509
510
511
512
513 // To do:
514 // shift left
515 // shift right
516 // readFromString
517
518 #endif