StochHMM  v0.34
Flexible Hidden Markov Model C++ Library and Application
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Public Member Functions | Private Attributes | Friends
StochHMM::dynamic_bitset Class Reference

#include <dynamic_bitset.h>

List of all members.

Classes

class  bit_ref

Public Member Functions

 dynamic_bitset ()
 dynamic_bitset (size_t)
 dynamic_bitset (const dynamic_bitset &)
 dynamic_bitset (const std::string &)
 dynamic_bitset (const std::vector< bool > &)
void resize (size_t)
void reserve (size_t)
bool empty ()
void clear ()
bool operator[] (size_t pos) const
bit_ref operator[] (size_t pos)
dynamic_bitset operator& (const dynamic_bitset &rhs)
dynamic_bitset operator| (const dynamic_bitset &rhs)
dynamic_bitset operator^ (const dynamic_bitset &rhs)
dynamic_bitset operator~ () const
dynamic_bitset & operator= (const dynamic_bitset &rhs)
dynamic_bitset & operator&= (const dynamic_bitset &rhs)
 Bitwise AND all the bits with all the bits in the rhs.
dynamic_bitset & operator|= (const dynamic_bitset &rhs)
 Bitwise OR all the bits with all the bits in the rhs.
dynamic_bitset & operator^= (const dynamic_bitset &rhs)
 Bitwise XOR all the bits with all the bits in the rhs.
dynamic_bitset & operator-= (const dynamic_bitset &rhs)
dynamic_bitset & operator<<= (size_t n)
dynamic_bitset & operator>>= (size_t n)
dynamic_bitset operator<< (size_t n)
dynamic_bitset operator>> (size_t n)
void insert (size_t pos, size_t n)
void erase (size_t pos)
dynamic_bitset get_intersection (const dynamic_bitset &rhs)
dynamic_bitset get_union (const dynamic_bitset &rhs)
dynamic_bitset get_unique (const dynamic_bitset &rhs)
 Return only the bits that are uniqe to bitset.
bool operator== (const dynamic_bitset &rhs) const
bool operator!= (const dynamic_bitset &rhs) const
size_t size ()
bool at (size_t pos) const
bool test (size_t pos)
void set (size_t pos)
void set (size_t pos, bool value)
void unset (size_t pos)
void flip ()
void flip (size_t pos)
void reset ()
 Resets all the bits to zero.
void reset (size_t pos)
 Clears the bit as position.
bool any ()
bool none ()
void push_back (bool)
size_t count () const
size_t count_before (size_t) const
size_t find_first () const
size_t find_first (size_t pos) const
size_t find_last () const
size_t find_last (size_t pos) const
bool parity ()
std::string stringify () const
std::string stringify_all () const
 Returns string representation of bitset includes buffered bits.
bool intersects (const dynamic_bitset &) const

Private Attributes

size_t buffer
size_t current_size
size_t num_ints
std::vector< uint32_t > array

Friends

std::ostream & operator<< (std::ostream &, const dynamic_bitset &)

Detailed Description

A dynamic bitset class Allows the bitset to be set dynamically and manipulated in size dynamic_bitset uses 32 bit unsigned integers as the underlying datatype. Need to implement shifting to right and left Note: This dynamic_bitset is read from left to right This class can be greatly improved by using SSE optimization For portability and time issues: SSE optimization haven't been implemented yet.

Definition at line 30 of file dynamic_bitset.h.

Constructor & Destructor Documentation

StochHMM::dynamic_bitset::dynamic_bitset ( )
inline

Definition at line 32 of file dynamic_bitset.h.

:current_size(0),buffer(0),num_ints(0){}
StochHMM::dynamic_bitset::dynamic_bitset ( size_t  sz)

Definition at line 13 of file dynamic_bitset.cpp.

References array, buffer, and num_ints.

: current_size(sz){
num_ints = ((sz-1)/32)+1;
buffer = (num_ints*32) - sz;
array.resize(num_ints);
//array = new (std::nothrow) uint32_t[num_ints]{0};
return;
}
StochHMM::dynamic_bitset::dynamic_bitset ( const dynamic_bitset &  rhs)

Definition at line 21 of file dynamic_bitset.cpp.

References array, buffer, current_size, and num_ints.

{
num_ints = rhs.num_ints;
buffer = rhs.buffer;
current_size = rhs.current_size;
array = rhs.array;
return;
}
StochHMM::dynamic_bitset::dynamic_bitset ( const std::string &  str)

Definition at line 29 of file dynamic_bitset.cpp.

References array, buffer, current_size, and num_ints.

{
size_t str_size = str.size();
num_ints = ((str_size-1)/32)+1;
buffer = (num_ints*32) - str_size;
current_size=str_size;
array.resize(num_ints);
for(size_t i = 0; i < str_size; ++i){
if (str[(str_size-1) - i ] == '1'){
set(i);
continue;
}
else if (str[(str_size-1) - i ] == '0'){
continue;
}
else{
std::cerr << "Invalid argument: " << str[(str_size-1) - i ] << " Only 0's and 1's \
allowed in string to initialize dynamic_bitset" << std::endl;
exit(2);
}
}
return;
}
StochHMM::dynamic_bitset::dynamic_bitset ( const std::vector< bool > &  vec)

Definition at line 53 of file dynamic_bitset.cpp.

References array, buffer, current_size, and num_ints.

{
size_t vec_size = vec.size();
num_ints = ((vec_size-1)/32)+1;
buffer = (num_ints*32) - vec_size;
current_size = vec_size;
array.resize(num_ints);
for (size_t i = 0; i < vec_size; ++i){
if (vec[i]){
set(i);
}
}
return;
}

Member Function Documentation

bool StochHMM::dynamic_bitset::any ( )

Checks to see if any bits are set

Returns:
true if any bits are set
false no bits are set

Definition at line 697 of file dynamic_bitset.cpp.

References array, and num_ints.

{
for(size_t i = 0; i < num_ints; i++){
if (array[i]!=0){
return true;
}
}
return false;
}
bool StochHMM::dynamic_bitset::at ( size_t  pos) const

Returns state of bit at position *Performs range check first

Definition at line 589 of file dynamic_bitset.cpp.

References array, and current_size.

Referenced by stringify(), and test().

{
if (pos>=current_size){
std::cerr << "Error: Out of Range.\nFunction: " << __FUNCTION__ << std::endl;
exit(2);
}
size_t intIter = pos/32;
size_t bitIter = pos - (intIter*32);
return array[intIter] & (1 << bitIter);
}
void StochHMM::dynamic_bitset::clear ( )

Clears the complete bitset *Size is reduced to zero

Definition at line 148 of file dynamic_bitset.cpp.

References array, buffer, current_size, and num_ints.

{
buffer=0;
current_size=0;
num_ints=0;
array.clear();
return;
}
size_t StochHMM::dynamic_bitset::count ( ) const

Returns the number of 1's in the bitset bits.sephan-brumme countBits population

Returns:
size_t number of bits set in bitset

Definition at line 997 of file dynamic_bitset.cpp.

References array, and num_ints.

Referenced by StochHMM::sparseArray< double >::elements().

{
size_t population(0);
for (size_t i=0; i < num_ints; i++){
uint32_t x = array[i];
// count bits of each 2-bit chunk
x = x - ((x >> 1) & 0x55555555);
// count bits of each 4-bit chunk
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
// count bits of each 8-bit chunk
x = x + (x >> 4);
// mask out junk
x &= 0xF0F0F0F;
// add all four 8-bit chunks
population+= (x * 0x01010101) >> 24;
}
return population;
}
size_t StochHMM::dynamic_bitset::count_before ( size_t  pos) const

Returns the number of 1's in the bitset to the right of the current position bits.sephan-brumme countBits population

Returns:
size_t number of bits set in bitset

Definition at line 1019 of file dynamic_bitset.cpp.

References array.

{
size_t current_int = pos/32;
size_t current_pos = pos%32;
uint32_t x(array[current_int]);
//Mask all the bits to right (including pos);
uint32_t mask = (1 << current_pos) - 1;
x &= mask;
//Count bits
x = x - ((x >> 1) & 0x55555555); // reuse input as temporary
x = (x & 0x33333333) + ((x >> 2) & 0x33333333); // temp
size_t population(((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24); // count
//Count the bit of integers to left
for (size_t i=0; i < current_int; i++){
x = array[i];
// count bits of each 2-bit chunk
x = x - ((x >> 1) & 0x55555555);
// count bits of each 4-bit chunk
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
// count bits of each 8-bit chunk
x = x + (x >> 4);
// mask out junk
x &= 0xF0F0F0F;
// add all four 8-bit chunks
population+= (x * 0x01010101) >> 24;
}
return population;
}
bool StochHMM::dynamic_bitset::empty ( )
inline

Definition at line 48 of file dynamic_bitset.h.

References current_size.

{return (current_size ==0) ? true : false;}
void StochHMM::dynamic_bitset::erase ( size_t  pos)

Erase the bit at the position from the set. *Causes the bits to shift right by one

Definition at line 478 of file dynamic_bitset.cpp.

References array, buffer, current_size, StochHMM::maskLeft(), StochHMM::maskRight(), num_ints, StochHMM::rso(), and SIZE_MAX.

{
//if the remove position is beyond the end the don't do anything.
if (pos>=current_size){
return;
}
//If size is equal to one then just assign zero and return
if (current_size == 1){
current_size =0;
buffer = 32;
array[0] = 0;
return;
}
size_t new_buffer = 32-(current_size-1)%32;
size_t new_num_ints = ((current_size-2))/32+1;
size_t first_affected = pos/32;
size_t relative_pos = pos%32;
//Get the value shifted off the last int
uint32_t shifted(0);
//If not last
if (first_affected != num_ints-1){
shifted = rso(array[num_ints-1], 1);
//Shift the rest of the integers up to first affected
for (size_t i = num_ints-2; i != first_affected && i != SIZE_MAX; --i){
uint32_t temp(array[i]);
array[i] = (array[i]>>1) | shifted;
shifted = temp << 31;
}
}
//Get the left most part of the first affected
uint32_t temp_mask = maskLeft(array[first_affected], relative_pos+1);
//std::cout << intToBinString(temp_mask) << std::endl;
//Get the right most part of the first affected and return it
if ((relative_pos - 1) == SIZE_MAX){
array[first_affected] = 0;
}
else{
array[first_affected] = maskRight(array[first_affected], relative_pos-1);
}
//Shift the left part
temp_mask >>=1;
//std::cout << intToBinString(temp_mask) << std::endl;
//Add the shifted bit from the previous
temp_mask |= shifted;
//std::cout << intToBinString(temp_mask) << std::endl;
//Add pack to the first affected
array[first_affected] |= temp_mask;
//Resize the int if necessary
if (new_num_ints != num_ints){
array.resize(new_num_ints);
}
//Set new values of buffer and size;
buffer = new_buffer;
current_size--;
return;
}
size_t StochHMM::dynamic_bitset::find_first ( ) const

Find first set bit within bitset and return the position *Searches from beginning to end. (Left to Right)

Returns:
size_t position of first bit set http://bits.stephan-brumme.com/lowestBitSet.html

Definition at line 758 of file dynamic_bitset.cpp.

References array, num_ints, and SIZE_MAX.

{
for(size_t i = 0; i < num_ints ; ++i){
if (array[i] == 0){
continue;
}
else{
uint32_t val = array[i];
static const size_t MultiplyDeBruijnBitPosition[32] =
{
// precomputed lookup table
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
// leave only lowest bit
val &= -int(val);
// DeBruijn constant
val *= 0x077CB531;
// get upper 5 bits
val >>= 27;
// convert to actual position
return i*32 + MultiplyDeBruijnBitPosition[val];
}
}
return SIZE_MAX;
}
size_t StochHMM::dynamic_bitset::find_first ( size_t  pos) const

Find the first bit within the bitset starting at position pos *Searches from beginning to end. (Left to Right)

Parameters:
posPosition to start the search
Returns:
Returns the position within the bitset with first set bit

Definition at line 792 of file dynamic_bitset.cpp.

References array, current_size, num_ints, and SIZE_MAX.

{
static const size_t MultiplyDeBruijnBitPosition[32] =
{
// precomputed lookup table
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
if (pos > current_size){
return SIZE_MAX;
}
//Deal with partial integer upto next integer boundary
//Find Current interger
size_t iter = pos/32;
//Position within the integer to start
size_t int_pos = pos%32;
int32_t val = array[iter];
//Mask bits before the position
val = val & ~((1 << int_pos) - 1);
if (val !=0){
// leave only lowest bit
val &= -int(val);
// DeBruijn constant
val *= 0x077CB531;
// get upper 5 bits
val >>= 27;
// convert to actual position
return iter * 32 + MultiplyDeBruijnBitPosition[val];
}
//Deal with everything from integer boundary onward
//http://bits.stephan-brumme.com/lowestBitSet.html
for(size_t i = iter+1; i < num_ints ; ++i){
if (array[i] == 0){
continue;
}
else{
uint32_t val = array[i];
// leave only lowest bit
val &= -int(val);
// DeBruijn constant
val *= 0x077CB531;
// get upper 5 bits
val >>= 27;
// convert to actual position
return i * 32 + MultiplyDeBruijnBitPosition[val];
}
}
return SIZE_MAX;
}
size_t StochHMM::dynamic_bitset::find_last ( ) const

Searches in reverse to find first set bit within bitset and return the position *Searches from end to beginning. (Right to Left)

Returns:
size_t position of first bit set

Definition at line 856 of file dynamic_bitset.cpp.

References array, num_ints, and SIZE_MAX.

{
for(size_t i = num_ints-1; i != SIZE_MAX ; --i){
if (array[i] == 0){
continue;
}
else{
//Adapted from http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i
//Using binary search algorithm to search
uint32_t val = array[i];
const uint32_t mask[] = {
0x00000FFFF,
0x0000000FF,
0x00000000F,
0x000000003,
0x000000001
};
uint32_t hi = 32;
uint32_t lo = 0;
if (val == 0)
return 0;
for (uint32_t j = 0; j < 5; j++) {
int mi = lo + (hi - lo) / 2;
if ((val >> mi) != 0)
lo = mi;
else if ((val & (mask[j] << lo)) != 0)
hi = mi;
}
return lo + 32 * i;
}
}
return SIZE_MAX;
}
size_t StochHMM::dynamic_bitset::find_last ( size_t  pos) const

Definition at line 893 of file dynamic_bitset.cpp.

References array, current_size, and SIZE_MAX.

{
if (pos > current_size){
return SIZE_MAX;
}
//Deal with partial integer upto next integer boundary
//Find Current interger
size_t iter = pos/32;
//Position within the integer to start
size_t int_pos = pos%32;
int32_t val = array[iter];
//std::cout << intToBinString(val) << std::endl;
//Mask bits before the position
val = val & ((1 << int_pos+1) - 1);
//std::cout << intToBinString(val) << std::endl;
//If value isn't zero then we'll need to find which position is set within it
if (val !=0) {
//Adapted from http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i
//Using binary search algorithm to search
const uint32_t mask[] = {
0x00000FFFF,
0x0000000FF,
0x00000000F,
0x000000003,
0x000000001
};
uint32_t hi = 32;
uint32_t lo = 0;
if (val == 0)
return 0;
for (uint32_t j = 0; j < 5; j++) {
int mi = lo + (hi - lo) / 2;
if ((val >> mi) != 0)
lo = mi;
else if ((val & (mask[j] << lo)) != 0)
hi = mi;
}
return lo + 32 * iter;
}
for(size_t i = iter-1; i != SIZE_MAX ; --i){
if (array[i] == 0){
continue;
}
else{
//Adapted from http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i
//Using binary search algorithm to search
uint32_t val = array[i];
const uint32_t mask[] = {
0x00000FFFF,
0x0000000FF,
0x00000000F,
0x000000003,
0x000000001
};
uint32_t hi = 32;
uint32_t lo = 0;
if (val == 0)
return 0;
for (uint32_t j = 0; j < 5; j++) {
int mi = lo + (hi - lo) / 2;
if ((val >> mi) != 0)
lo = mi;
else if ((val & (mask[j] << lo)) != 0)
hi = mi;
}
return lo + 32 * i;
}
}
return SIZE_MAX;
}
void StochHMM::dynamic_bitset::flip ( )

Flips the whole bitset *Complete bitset gets assigned the complement bitset

Definition at line 665 of file dynamic_bitset.cpp.

{
*this = ~*this;
return;
}
void StochHMM::dynamic_bitset::flip ( size_t  pos)

Flip the bit at position If bit is set 1, then it gets unset 0

Definition at line 672 of file dynamic_bitset.cpp.

References test(), and unset().

{
if (test(pos)){
unset(pos);
}
else{
set(pos);
}
return;
}
dynamic_bitset StochHMM::dynamic_bitset::get_intersection ( const dynamic_bitset &  rhs)

Return the intersection bitset with rhs bitset Same as bitwise AND

Parameters:
dynamic_bitset&
Returns:
dynamic_bitset that is intersection of both

Definition at line 553 of file dynamic_bitset.cpp.

{
return *this & rhs;
}
dynamic_bitset StochHMM::dynamic_bitset::get_union ( const dynamic_bitset &  rhs)

Returns the union bitset Same as bitwise OR

Definition at line 559 of file dynamic_bitset.cpp.

{
return *this | rhs;
}
dynamic_bitset StochHMM::dynamic_bitset::get_unique ( const dynamic_bitset &  rhs)

Return only the bits that are uniqe to bitset.

Definition at line 564 of file dynamic_bitset.cpp.

{
return *this & ~rhs ;
}
void StochHMM::dynamic_bitset::insert ( size_t  pos,
size_t  n 
)

Insert n bits (set to zero) at the position. Bitsets at this position and *greater will be shifted to the left. This will increase the size of the bitset

Definition at line 384 of file dynamic_bitset.cpp.

References array, buffer, current_size, StochHMM::lso(), StochHMM::maskLeft(), StochHMM::maskRight(), and num_ints.

{
if (pos > current_size){
std::cerr << "dynamic_bitset::"<<__FUNCTION__ << " Error: Position for insert is beyond the range current size\n";
exit(2);
}
size_t new_buffer = 32-(current_size + n)%32;
size_t remainder = 32 - (pos%32);
size_t new_num_ints = ((current_size-1)+n)/32+1;
size_t first_affected = pos/32;
//size_t last_affected = num_ints;
size_t next_affected = (pos+n)/32;
int64_t next_shift_size = ((pos+n)%32) - (pos%32);
int64_t intervening_ints = int64_t (n-remainder) / 32;
size_t relative_pos = pos%32;
if (new_num_ints!= num_ints){
if (intervening_ints != 0 && intervening_ints >= 0){
array.insert(array.begin()+first_affected+1,intervening_ints,0);
num_ints+= intervening_ints;
}
//Add additional on end if necessary
if (new_num_ints != num_ints){
array.resize(new_num_ints);
num_ints= new_num_ints;
}
}
uint32_t temp_mask = maskLeft(array[first_affected], relative_pos);
array[first_affected] = maskRight(array[first_affected], relative_pos-1);
//If shift is by factor of 32 then we just need to reassign values
if (next_shift_size == 0){
size_t ints_shifted = n/32;
for (size_t i = num_ints-1; i > first_affected + intervening_ints + 1; --i){
array[i] = array[i-(ints_shifted-intervening_ints)];
}
array[first_affected+ints_shifted] = temp_mask;
}
else if (next_shift_size < 0){ //Right shift after intervening sequence
//Shift temp sequence right by necessary amount
uint8_t left_shift = 32 - abs( (uint8_t) next_shift_size);
temp_mask >>= abs( (uint8_t) next_shift_size);
for(size_t i = next_affected; i < num_ints ; ++i){
uint32_t tmp = array[i];
array[i] <<= left_shift;
array[i] |= temp_mask;
temp_mask = tmp >> (32-left_shift);
//temp_mask = lsoso(array[i], temp_mask, left_shift);
}
}
else{//left_shift after intervening sequence
//Move the values to new cells before shifting old values
if (n>32){
size_t ints_shifted = n/32;
for (size_t i = num_ints-1; i > first_affected + intervening_ints + 1; --i){
array[i] = array[i-(ints_shifted-intervening_ints)];
array[i-(ints_shifted-intervening_ints)]=0;
}
}
//Shift temp value
uint32_t shifted = lso(temp_mask,next_shift_size);
array[next_affected] |= temp_mask;
//Shift the rest of the values
for(size_t i = next_affected+1; i < num_ints ; ++i){
uint32_t tmp = array[i];
array[i] <<= next_shift_size;
array[i] |= shifted;
shifted = tmp >> (32-next_shift_size);
}
}
buffer = new_buffer;
current_size +=n;
return;
}
bool StochHMM::dynamic_bitset::intersects ( const dynamic_bitset &  ) const
bool StochHMM::dynamic_bitset::none ( )

Checks to see if no bits are set

Returns:
false if any bits are set
true if no bits are set

Definition at line 709 of file dynamic_bitset.cpp.

References array, and num_ints.

{
for(size_t i = 0; i < num_ints; i++){
if (array[i]!=0){
return false;
}
}
return true;
}
bool StochHMM::dynamic_bitset::operator!= ( const dynamic_bitset &  rhs) const

Checks to see if bitset is not equal to *this

Parameters:
Bitsetto compare with *this
Returns:
true if the bitsets are not equal to each other
false if the bitsets are equal

Definition at line 293 of file dynamic_bitset.cpp.

References array, and num_ints.

{
for(size_t i = 0; i < num_ints ;++i){
if (array[i]!=rhs.array[i]){
return true;
}
}
return false;
}
dynamic_bitset StochHMM::dynamic_bitset::operator& ( const dynamic_bitset &  rhs)

Bitwise - AND operator

Returns:
a dynamic_bitset that is *this AND rhs

Definition at line 159 of file dynamic_bitset.cpp.

{
dynamic_bitset output(*this);
output&=rhs;
return output;
}
dynamic_bitset & StochHMM::dynamic_bitset::operator&= ( const dynamic_bitset &  rhs)

Bitwise AND all the bits with all the bits in the rhs.

Definition at line 208 of file dynamic_bitset.cpp.

References array, buffer, current_size, and num_ints.

{
if (rhs.current_size != this->current_size){
std::cerr << __FUNCTION__ << " called on dynamic_bitsets of different sizes." <<std::endl;
exit(2);
}
for(size_t i = 0; i < num_ints; ++i){
array[i] &= rhs.array[i];
}
//Clear those bits that are outside of the current scope
uint32_t mask = (1 << 32-buffer) - 1;
array[num_ints-1] &= mask;
return *this;
}
dynamic_bitset& StochHMM::dynamic_bitset::operator-= ( const dynamic_bitset &  rhs)
dynamic_bitset StochHMM::dynamic_bitset::operator<< ( size_t  n)

Definition at line 333 of file dynamic_bitset.cpp.

{
dynamic_bitset output(*this);
output<<=n;
return output;
}
dynamic_bitset & StochHMM::dynamic_bitset::operator<<= ( size_t  n)

Shift the bitset to the left n positions *Size of the bitset will not change. If values are shifted off bitset then *they will be lost.

Parameters:
nNumber of positions to shift the bits

Definition at line 306 of file dynamic_bitset.cpp.

References array, buffer, StochHMM::lso(), StochHMM::lsoso(), and num_ints.

{
//If shifting more than 32 then need to insert integer before
size_t start(0);
if (n>=32){
size_t ints_to_add = n/32;
n %=32;
array.insert(array.begin(), ints_to_add, 0);
array.resize(num_ints);
if (n==0){
return *this;
}
}
if (n!=0){
uint32_t shifted(lso(array[start],n));
for(size_t i = start+1; i < num_ints ; ++i){
shifted = lsoso(array[i], shifted, n);
}
//Clear those bits that are outside of the current scope (bits in buffer region)
uint32_t mask = (1 << 32-buffer) - 1;
array[num_ints-1] &= mask;
}
return *this;
}
dynamic_bitset & StochHMM::dynamic_bitset::operator= ( const dynamic_bitset &  rhs)

Overloaded assignment operator makes *this a copy of rhs

Parameters:
rhsdynamic_bitset to copy
Returns:
*this;

Definition at line 199 of file dynamic_bitset.cpp.

References array, buffer, current_size, and num_ints.

{
num_ints = rhs.num_ints;
buffer = rhs.buffer;
current_size = rhs.current_size;
array = rhs.array;
return *this;
}
bool StochHMM::dynamic_bitset::operator== ( const dynamic_bitset &  rhs) const

Checks to see if bitset is equal to *this

Parameters:
Bitsetto compare with *this
Returns:
false if the bitsets are not equal to each other
true if the bitsets are equal

Definition at line 280 of file dynamic_bitset.cpp.

References array, and num_ints.

{
for(size_t i = 0; i < num_ints ;++i){
if (array[i]!=rhs.array[i]){
return false;
}
}
return true;
}
dynamic_bitset StochHMM::dynamic_bitset::operator>> ( size_t  n)

Definition at line 374 of file dynamic_bitset.cpp.

{
dynamic_bitset output(*this);
output>>=n;
return output;
}
dynamic_bitset & StochHMM::dynamic_bitset::operator>>= ( size_t  n)

Shift the bitset to the right n positions *Size of the bitset will not change. If values are shifted off bitset then *they will be lost.

Parameters:
nNumber of positions to shift the bits

Definition at line 344 of file dynamic_bitset.cpp.

References array, num_ints, StochHMM::rso(), StochHMM::rsoso(), and SIZE_MAX.

{
//If shifting more than 32 then need to insert integer before
size_t start(num_ints-1);
if (n>=32){
size_t ints_to_delete = n/32;
n %= 32;
array.erase(array.begin(), array.begin()+ints_to_delete);
start -= ints_to_delete;
if (n == 0){
array.resize(num_ints);
return *this;
}
}
if (n != 0){
//Shift first integers and get value to shift to next
uint32_t shifted(rso(array[start],n));
//For all the integers before shift the value
for(size_t i = start-1; i != SIZE_MAX ; --i){
shifted = rsoso(array[i], shifted, n);
}
//Resesize the array
array.resize(num_ints);
}
return *this;
}
bool StochHMM::dynamic_bitset::operator[] ( size_t  pos) const

Get state of bit at position *No initial range check

Returns:
true if set 1
false if not set 0

Definition at line 575 of file dynamic_bitset.cpp.

References array.

{
size_t intIter = pos/32;
size_t bitIter = pos - (intIter*32);
return array[intIter] & (1 << bitIter);
}
dynamic_bitset::bit_ref StochHMM::dynamic_bitset::operator[] ( size_t  pos)

Definition at line 581 of file dynamic_bitset.cpp.

References array.

{
size_t intIter = pos/32;
size_t bitIter = pos - (intIter*32);
return bit_ref(array[intIter],bitIter);
}
dynamic_bitset StochHMM::dynamic_bitset::operator^ ( const dynamic_bitset &  rhs)

Bitwise - XOR operator

Returns:
a dynamic_bitset that is *this XOR rhs

Definition at line 175 of file dynamic_bitset.cpp.

{
dynamic_bitset output(*this);
output^=rhs;
return output;
}
dynamic_bitset & StochHMM::dynamic_bitset::operator^= ( const dynamic_bitset &  rhs)

Bitwise XOR all the bits with all the bits in the rhs.

Definition at line 248 of file dynamic_bitset.cpp.

References array, buffer, current_size, and num_ints.

{
if (rhs.current_size != this->current_size){
std::cerr << __FUNCTION__ << " called on dynamic_bitsets of different sizes." <<std::endl;
exit(2);
}
for(size_t i = 0; i < num_ints; ++i){
array[i] ^= rhs.array[i];
}
//Clear those bits that are outside of the current scope
uint32_t mask = (1 << 32-buffer) - 1;
array[num_ints-1] &= mask;
return *this;
}
dynamic_bitset StochHMM::dynamic_bitset::operator| ( const dynamic_bitset &  rhs)

Bitwise - OR operator

Returns:
a dynamic_bitset that is *this OR rhs

Definition at line 167 of file dynamic_bitset.cpp.

{
dynamic_bitset output(*this);
output|=rhs;
return output;
}
dynamic_bitset & StochHMM::dynamic_bitset::operator|= ( const dynamic_bitset &  rhs)

Bitwise OR all the bits with all the bits in the rhs.

Definition at line 227 of file dynamic_bitset.cpp.

References array, buffer, current_size, and num_ints.

{
if (rhs.current_size != this->current_size){
std::cerr << __FUNCTION__ << " called on dynamic_bitsets of different sizes." <<std::endl;
exit(2);
}
for(size_t i = 0; i < num_ints; ++i){
array[i] |= rhs.array[i];
}
//Clear those bits that are outside of the current scope
uint32_t mask = (1 << 32-buffer) - 1;
array[num_ints-1] &= mask;
return *this;
}
dynamic_bitset StochHMM::dynamic_bitset::operator~ ( ) const

Bitwise ~ Complement

Returns:
dynamic_bitset that is complement of *this

Definition at line 183 of file dynamic_bitset.cpp.

References array, buffer, and num_ints.

{
dynamic_bitset output(*this);
for(size_t i = 0; i < num_ints; ++i){
output.array[i] = ~output.array[i];
}
//Clear those bits that are outside of the current scope
uint32_t mask = (1 << 32-output.buffer) - 1;
output.array[num_ints-1] &= mask;
return output;
}
bool StochHMM::dynamic_bitset::parity ( )

Returns whether there are an odd number of bits set

Returns:
true if number of 1's is odd
false if number of 1' is even

Definition at line 981 of file dynamic_bitset.cpp.

References array, and num_ints.

{
bool val(false);
for(size_t i = 0; i < num_ints; ++i){
uint32_t temp = array[i];
temp ^= temp >> 1;
temp ^= temp >> 2;
temp &= 0x011111111;
temp *= 0x011111111;
val ^= ((temp >> 28) & 1) != 0;
}
return val;
}
void StochHMM::dynamic_bitset::push_back ( bool  val)

Pushes a bit onto the bitset *Increases the bitset size by 1

Parameters:
boolValue to set in bitset

Definition at line 721 of file dynamic_bitset.cpp.

References array, buffer, current_size, num_ints, reserve(), and unset().

{
if (buffer==0){
//Reserve more memory. Push uint32(0) onto array
if (current_size != 0){
reserve(current_size*2);
array.push_back(0);
buffer = 32;
num_ints++;
}
else{
reserve(32);
array.push_back(0);
buffer = 32;
num_ints++;
}
}
//Increases the size and decrease buffer;
current_size++;
buffer--;
//Set value of position
if (val){
set(current_size-1);
}
else{
unset(current_size-1);
}
return;
}
void StochHMM::dynamic_bitset::reserve ( size_t  sz)

Reserves the set amount of memory *Doesn't change any of the bitset size. Only reserve a set amount of memory.

Definition at line 134 of file dynamic_bitset.cpp.

References array, buffer, and current_size.

Referenced by push_back().

{
if (sz <= current_size + buffer){
return;
}
else{
size_t new_num_ints = ((sz-1)/32)+1;
array.reserve(new_num_ints);
}
return;
}
void StochHMM::dynamic_bitset::reset ( )

Resets all the bits to zero.

Definition at line 684 of file dynamic_bitset.cpp.

References array, and num_ints.

{
array.assign(num_ints, 0);
}
void StochHMM::dynamic_bitset::reset ( size_t  pos)

Clears the bit as position.

Definition at line 689 of file dynamic_bitset.cpp.

References unset().

{
unset(pos);
return;
}
void StochHMM::dynamic_bitset::resize ( size_t  sz)

Resize the bitset. If size is smaller than bitset, those values will get deleted If size is larger than bitset, it will get extended.

Definition at line 109 of file dynamic_bitset.cpp.

References array, buffer, current_size, and num_ints.

{
size_t new_num_ints = ((sz-1)/32)+1;
if (num_ints == new_num_ints){
current_size = sz;
}
else{
array.resize(new_num_ints);
current_size = sz;
num_ints = new_num_ints;
}
//Set new buffer size
buffer = (num_ints*32)-sz;
//Clear bit in buffer
//Clear those bits that are outside of the current scope
uint32_t mask = (1 << 32 - buffer) - 1;
array[num_ints-1] &= mask;
return;
}
void StochHMM::dynamic_bitset::set ( size_t  pos)

Sets the bit at position with value *Checks size before assignment

Parameters:
positionwithin bitset

Definition at line 617 of file dynamic_bitset.cpp.

References array, and current_size.

{
if (pos>=current_size){
std::cerr << "Error: Out of Range.\nFunction: " << __FUNCTION__ << std::endl;
exit(2);
}
size_t intIter = pos/32;
size_t bitIter = pos - (intIter*32);
array[intIter] |= (1 << bitIter);
return;
}
void StochHMM::dynamic_bitset::set ( size_t  pos,
bool  val 
)

Sets the bit at position with value *Checks size before assignment

Parameters:
positionwithin bitset
valValue to set bit

Definition at line 634 of file dynamic_bitset.cpp.

References current_size, and unset().

{
if (pos>=current_size){
std::cerr << "Error: Out of Range.\nFunction: " << __FUNCTION__ << std::endl;
exit(2);
}
if (val){
set(pos);
}
else{
unset(pos);
}
}
size_t StochHMM::dynamic_bitset::size ( )
inline

Definition at line 100 of file dynamic_bitset.h.

References current_size.

Referenced by StochHMM::sparseArray< double >::size().

{return current_size;}
std::string StochHMM::dynamic_bitset::stringify ( ) const

Returns string representation of bitset

Returns:
std::string representation of bitset

Definition at line 1054 of file dynamic_bitset.cpp.

References at(), current_size, SIZE_MAX, and test().

Referenced by StochHMM::operator<<().

{
std::string output("");
for (size_t i=current_size-1;i != SIZE_MAX; --i){
bool test = at(i);
if (test){
output+="1";
}
else{
output+="0";
}
// if (i!= 0 && i%32 == 0){
// output+=",";
// }
}
return output;
}
std::string StochHMM::dynamic_bitset::stringify_all ( ) const

Returns string representation of bitset includes buffered bits.

Definition at line 1077 of file dynamic_bitset.cpp.

References array, StochHMM::intToBinString(), num_ints, and SIZE_MAX.

{
std::string output("");
for (size_t i=num_ints-1 ; i != SIZE_MAX; --i){
output+= intToBinString(array[i]);
// if (i!=0){
// output+=",";
// }
}
return output;
}
bool StochHMM::dynamic_bitset::test ( size_t  pos)

Returns whether bit is set at the position *Performs range check first

Parameters:
posPosition within bitset
Returns:
true if bit is set
false if bit is unset

Definition at line 605 of file dynamic_bitset.cpp.

References at(), and current_size.

Referenced by flip(), and stringify().

{
if (pos>=current_size){
std::cerr << "Error: Out of Range.\nFunction: " << __FUNCTION__ << std::endl;
exit(2);
}
return at(pos);
}
void StochHMM::dynamic_bitset::unset ( size_t  pos)

Unsets the bit at position *Checks size before assignment

Definition at line 650 of file dynamic_bitset.cpp.

References array, and current_size.

Referenced by flip(), push_back(), reset(), and set().

{
if (pos>=current_size){
std::cerr << "Error: Out of Range.\nFunction: " << __FUNCTION__ << std::endl;
exit(2);
}
size_t intIter = pos/32;
size_t bitIter = pos - (intIter*32);
array[intIter] &= ~(1 << bitIter);
return;
}

Friends And Related Function Documentation

std::ostream& operator<< ( std::ostream &  output,
const dynamic_bitset &  bs 
)
friend

Overloaded ostream for using dynamic_bitsets in ostream *Usage: std::cout << bs << ....;

Definition at line 270 of file dynamic_bitset.cpp.

{
output << bs.stringify();
return output;
}

Member Data Documentation

std::vector<uint32_t> StochHMM::dynamic_bitset::array
private

Definition at line 141 of file dynamic_bitset.h.

Referenced by any(), at(), clear(), count(), count_before(), dynamic_bitset(), erase(), find_first(), find_last(), insert(), none(), operator!=(), operator&=(), operator<<=(), operator=(), operator==(), operator>>=(), operator[](), operator^=(), operator|=(), operator~(), parity(), push_back(), reserve(), reset(), resize(), set(), stringify_all(), and unset().

size_t StochHMM::dynamic_bitset::buffer
private

Definition at line 137 of file dynamic_bitset.h.

Referenced by clear(), dynamic_bitset(), erase(), insert(), operator&=(), operator<<=(), operator=(), operator^=(), operator|=(), operator~(), push_back(), reserve(), and resize().

size_t StochHMM::dynamic_bitset::current_size
private

Definition at line 138 of file dynamic_bitset.h.

Referenced by at(), clear(), dynamic_bitset(), empty(), erase(), find_first(), find_last(), insert(), operator&=(), operator=(), operator^=(), operator|=(), push_back(), reserve(), resize(), set(), size(), stringify(), test(), and unset().

size_t StochHMM::dynamic_bitset::num_ints
private

Definition at line 139 of file dynamic_bitset.h.

Referenced by any(), clear(), count(), dynamic_bitset(), erase(), find_first(), find_last(), insert(), none(), operator!=(), operator&=(), operator<<=(), operator=(), operator==(), operator>>=(), operator^=(), operator|=(), operator~(), parity(), push_back(), reset(), resize(), and stringify_all().

The documentation for this class was generated from the following files:
Generated on Tue Jul 30 2013 13:23:13 for StochHMM by   doxygen 1.8.1