/* BaitFisher (version 1.2.7) a program for designing DNA target enrichment baits
* Copyright 2013-2016 by Christoph Mayer
*
* This source file is part of the BaitFisher-package.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with BaitFisher. If not, see .
*
*
* For any enquiries send an Email to Christoph Mayer
* c.mayer.zfmk@uni-bonn.de
*
* When publishing work that is based on the results please cite:
* Mayer et al. 2016: BaitFisher: A software package for multi-species target DNA enrichment probe design
*
*/
#ifndef FAST_DYNAMIC_BITSET_H
#define FAST_DYNAMIC_BITSET_H
// 23.7.2014: Since unsigned long has 64 bits on some computers unsinged long cannot be used as
// the word data type without having to change large parts of the code.
#include
#include
#include
#include
//#define __num_bits_in_word (( unsigned long)8*sizeof(unsigned long))
//#define __get_word_index(i) (( unsigned long)i/(__num_bits_in_word))
//#define __get_num_words(size) (((unsigned long)size+__num_bits_in_word-1ul)/(__num_bits_in_word))
//#define __get_empty_mask(size,numWords) ( 0xFFFFFFFF >> numWords*__num_bits_in_word - size )
//#define __get_num_byte(words) ( words*sizeof(unsigned long))
#define __num_bits_in_word 32
#define __get_word_index(i) (i >> 5)
#define __get_word_offset(i) (i & 31)
#define __get_num_words(size) ((size + 31) >> 5)
#define __get_num_byte(words) ( words*4 )
// Must be a 32 bit integer type:
//typedef unsigned bitset_word_type;
typedef unsigned my_uint_32;
const unsigned char __num_bits_table[256] =
{
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,
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,
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,
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,
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,
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,
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,
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
};
const my_uint_32 __mask_table[32] =
{
0x00000001, 0x00000002, 0x00000004, 0x00000008,
0x00000010, 0x00000020, 0x00000040, 0x00000080,
0x00000100, 0x00000200, 0x00000400, 0x00000800,
0x00001000, 0x00002000, 0x00004000, 0x00008000,
0x00010000, 0x00020000, 0x00040000, 0x00080000,
0x00100000, 0x00200000, 0x00400000, 0x00800000,
0x01000000, 0x02000000, 0x04000000, 0x08000000,
0x10000000, 0x20000000, 0x40000000, 0x80000000
};
const my_uint_32 __empty_mask_table[32] =
{
0xFFFFFFFF, 0x7FFFFFFF, 0x3FFFFFFF, 0x1FFFFFFF,
0x0FFFFFFF, 0x07FFFFFF, 0x03FFFFFF, 0x01FFFFFF,
0x00FFFFFF, 0x007FFFFF, 0x003FFFFF, 0x001FFFFF,
0x000FFFFF, 0x0007FFFF, 0x0003FFFF, 0x0001FFFF,
0x0000FFFF, 0x00007FFF, 0x00003FFF, 0x00001FFF,
0x00000FFF, 0x000007FF, 0x000003FF, 0x000001FF,
0x000000FF, 0x0000007F, 0x0000003F, 0x0000001F,
0x0000000F, 0x00000007, 0x00000003, 0x00000001
};
class fast_dynamic_bitset
{
public:
class exception {};
class outOfRange : public exception {};
class zeroSizeBitset : public exception {};
class UnequalSizedBitsets : public exception {};
private:
my_uint_32 *__data;
my_uint_32 __size;
my_uint_32 __numWords;
// my_uint_32 __empty_mask;
public:
fast_dynamic_bitset(my_uint_32 size=0):__size(size),__numWords(__get_num_words(size))
{
// if (size == 0)
// throw zeroSizeBitset();
// __size = size;
__data = new my_uint_32 [__numWords];
// __empty_mask = __empty_mask_table[__numWords * __num_bits_in_word - size];
// 0xFFFFFFFF >> (__numWords * __num_bits_in_word - size);
}
fast_dynamic_bitset(const fast_dynamic_bitset &a)
{
memcpy((void*)this, (void*) &a, sizeof(fast_dynamic_bitset) );
__data = new my_uint_32 [__numWords];
memcpy((void*)__data,(void*)a.__data, __get_num_byte(__numWords) );
}
~fast_dynamic_bitset() {
delete [] __data;
// std::cout << "Dest" << std::endl;
}
my_uint_32 size()
{
return __size;
}
fast_dynamic_bitset& operator=(const fast_dynamic_bitset &a)
{
if ( __size != a.__size )
{
delete [] __data;
memcpy((void*)this, (void*) &a, sizeof(fast_dynamic_bitset) );
__data = new my_uint_32 [__numWords];
memcpy((void*)__data,(void*)a.__data, __get_num_byte(__numWords) );
}
else
{
memcpy((void*)__data,(void*)a.__data, __get_num_byte(__numWords) );
}
return *this;
}
void reset()
{
memset((void*)__data, 0, __get_num_byte(__numWords));
}
void clear()
{
reset();
}
void set()
{
for(my_uint_32 index=0; index < __numWords-1; ++index)
__data[index] = ~static_cast(0);
__data[__numWords-1] = __empty_mask_table[__numWords * __num_bits_in_word - __size];
}
void flip()
{
for(my_uint_32 index=0; index < __numWords; ++index)
__data[index] = ~__data[index];
__data[__numWords-1] &= __empty_mask_table[__numWords * __num_bits_in_word - __size];
}
void unchecked_set(my_uint_32 i)
{
__data[__get_word_index(i)] |= __mask_table[__get_word_offset(i)];
}
void set(my_uint_32 i)
{
if (i >= __size)
throw outOfRange();
__data[__get_word_index(i)] |= __mask_table[__get_word_offset(i)];
}
void unchecked_reset(my_uint_32 i)
{
__data[__get_word_index(i)] ^= __mask_table[__get_word_offset(i)];
}
void reset(my_uint_32 i)
{
if (i >= __size)
throw outOfRange();
__data[__get_word_index(i)] ^= __mask_table[__get_word_offset(i)];
}
void unchecked_set(my_uint_32 i, my_uint_32 x)
{
if (x==0)
unchecked_reset(i);
else
unchecked_set(i);
}
void set(my_uint_32 i, my_uint_32 x)
{
if (x==0)
reset(i);
else
set(i);
}
bool unchecked_test(my_uint_32 i) const
{
return (__data[__get_word_index(i)] & __mask_table[__get_word_offset(i)]);
}
bool test(my_uint_32 i) const
{
// if (i >= __size)
// throw outOfRange();
return (__data[__get_word_index(i)] & __mask_table[__get_word_offset(i)]);
}
void unchecked_flip(my_uint_32 i)
{
__data[__get_word_index(i)] ^= __mask_table[__get_word_offset(i)];
}
void flip(my_uint_32 i)
{
// if (i >= __size)
// throw outOfRange();
__data[__get_word_index(i)] ^= __mask_table[__get_word_offset(i)];
}
void operator&=(const fast_dynamic_bitset &a)
{
// if ( a.__numWords != __numWords )
// throw UnequalSizedBitsets();
for(my_uint_32 index=0; index < __numWords; ++index)
__data[index] &= a.__data[index];
}
void operator|=(const fast_dynamic_bitset &a)
{
// if ( a.__numWords != __numWords )
// throw UnequalSizedBitsets();
for(my_uint_32 index=0; index < __numWords; ++index)
__data[index] |= a.__data[index];
}
void operator^=(const fast_dynamic_bitset &a)
{
// if ( a.__numWords != __numWords )
// throw UnequalSizedBitsets();
for(my_uint_32 index=0; index < __numWords; ++index)
__data[index] ^= a.__data[index];
}
fast_dynamic_bitset operator~()
{
fast_dynamic_bitset a=*this;
a.flip();
return a;
}
std::string as_string_highBitsFirst() const
{
std::string str;
/* // Print overhead-empty bit in bitset: */
/* //------------------------------------- */
/* my_uint_32 k = __numWords * __num_bits_in_word; */
/* while (k != __size) */
/* { */
/* --k; */
/* if (unchecked_test(k)) */
/* str.push_back('1'); */
/* else */
/* str.push_back('0'); */
/* } */
/* // os << "|"; */
// Print bitset with high bits first
//-----------------------------------
my_uint_32 i = __size;
while (i != 0)
{
--i;
if (unchecked_test(i))
str.push_back('1');
else
str.push_back('0');
}
return str;
}
std::string as_string_lowBitsFirst() const
{
std::string str;
// Print bitset with low bits first
//----------------------------------
my_uint_32 i = 0;
while (i < __size )
{
if (unchecked_test(i))
str.push_back('1');
else
str.push_back('0');
++i;
}
return str;
}
std::ostream& print_lowBitsFirst(std::ostream& os) const
{
// Print bitset with low bits first
//----------------------------------
my_uint_32 i = 0;
while (i < __size )
{
if (unchecked_test(i))
os << "1";
else
os << "0";
++i;
}
/* // Print overhead-empty bit in bitset: */
/* //------------------------------------- */
/* os << "|"; */
/* while ( i < __numWords * __num_bits_in_word) */
/* { */
/* if (unchecked_test(i)) */
/* os << "1"; */
/* else */
/* os << "0"; */
/* ++i; */
/* } */
return os;
}
void binary_out(std::ostream& os)
{
os.write((char*)__data,__numWords*sizeof(my_uint_32));
}
void binary_in(std::istream& is)
{
is.read((char*) __data,__numWords*sizeof(my_uint_32));
}
my_uint_32 count() const
{
my_uint_32 sum = 0;
unsigned char *ptr = (unsigned char*) __data;
unsigned char *ptr_end = ptr + __get_num_byte(__numWords);
while ( ptr != ptr_end )
{
sum += __num_bits_table[*ptr];
++ptr;
}
return sum;
}
bool any() const
{
for(my_uint_32 i=0; i < __numWords; ++i)
{
if (__data[i])
return true;
}
return false;
}
bool none() const
{
return !any();
}
void operator++()
{
my_uint_32 i=0;
while ( i < __numWords )
{
++__data[i];
if (__data[i]) // if __data[i] == 0 we have to carry a bit otherwise we are done.
break;
++i;
}
}
friend bool operator!=(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
{
// if ( a.__numWords != b.__numWords )
// throw UnequalSizedBitsets();
for (my_uint_32 i = 0; i < a.__numWords; --i)
{
if ( a.__data[i] != b.__data[i] )
return true;
}
return false;
}
friend bool operator==(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
{
return !(a != b);
}
friend bool operator<(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
{
// if ( a.__numWords != b.__numWords )
// throw UnequalSizedBitsets();
for (my_uint_32 i=a.__numWords-1; i > 0; --i)
{
if ( a.__data[i] < b.__data[i] )
return true;
else if (a.__data[i] > b.__data[i])
return false;
}
if ( a.__data[0] < b.__data[0] )
return true;
else
return false;
}
friend bool operator>(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
{
// if ( a.__numWords != b.__numWords )
// throw UnequalSizedBitsets();
for (my_uint_32 i=a.__numWords-1; i > 0; --i)
{
if ( a.__data[i] != b.__data[i] )
return a.__data[i] > b.__data[i];
}
return a.__data[0] > b.__data[0];
}
friend bool operator<=(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
{
return !(a>b);
}
friend bool operator>=(const fast_dynamic_bitset &a, const fast_dynamic_bitset &b)
{
return !(a