A toolkit for working with phylogenetic data.
v0.18.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Bitvector Class Reference

#include <genesis/utils/math/bitvector.hpp>

Detailed Description

Definition at line 58 of file bitvector.hpp.

Public Member Functions

 Bitvector ()=default
 Default constructor. Creates an empty Bitvector of size 0. More...
 
 Bitvector (const size_t size, const bool init=false)
 Constructor that takes a size and an optional bool value to initialize the Bitvector, false by default. More...
 
 Bitvector (const size_t size, const std::initializer_list< int > list)
 Constructor that takes a size and a list of values (positions) to be set to true. More...
 
size_t count () const
 Counts the number of set bits in the Bitvector. More...
 
std::string dump () const
 
std::string dump_int (IntType x) const
 
void flip (size_t index)
 Flips (inverts) the value of a single bit, with boundary check. More...
 
bool get (size_t index) const
 Returns the value of a single bit, with boundary check. More...
 
size_t hash () const
 Returns an std::hash value for the Bitvector. More...
 
void invert ()
 Flip all bits. More...
 
void normalize ()
 Brings the Bitvector in a normalized form, where the first bit is always zero. More...
 
bool operator!= (const Bitvector &other) const
 
Bitvectoroperator&= (Bitvector const &rhs)
 
bool operator< (Bitvector const &rhs) const
 Strict subset. More...
 
bool operator<= (Bitvector const &rhs) const
 Subset or equal. More...
 
bool operator== (const Bitvector &other) const
 
bool operator> (Bitvector const &rhs) const
 Strict superset. More...
 
bool operator>= (Bitvector const &rhs) const
 Superset or equal. More...
 
bool operator[] (size_t index) const
 Returns the value of a single bit, without boundary check. More...
 
Bitvectoroperator^= (Bitvector const &rhs)
 
Bitvectoroperator|= (Bitvector const &rhs)
 
Bitvector operator~ () const
 
void reset (const bool value=false)
 Reset all the bits to false. If provided with parameter true, sets all bits to true. More...
 
void set (size_t index)
 Sets the value of a single bit to true, with boundary check. More...
 
void set (size_t index, bool value)
 Sets the value of a single bit to a given bool value, with boundary check. More...
 
size_t size () const
 Returns the size (number of total bits) of this Bitvector. More...
 
Bitvector symmetric_difference (Bitvector const &rhs) const
 
void unset (size_t index)
 Sets the value of a single bit to false, with boundary check. More...
 
IntType x_hash () const
 Returns a hash value of type IntType, that is quicker to calculate than hash(), and thus can be used where the std::hash is not needed. More...
 

Static Public Member Functions

static Bitvector symmetric_difference (Bitvector const &lhs, Bitvector const &rhs)
 

Public Types

typedef uint64_t IntType
 

Static Public Attributes

static const size_t IntSize = sizeof(IntType) * 8
 

Protected Member Functions

void unset_padding ()
 Internal function that sets all bits to zero that are not actively used. More...
 

Protected Attributes

std::vector< IntTypedata_
 
size_t size_ = 0
 

Static Protected Attributes

static const IntType all_0_ = 0ul
 
static const IntType all_1_ = (((1ul << 32) - 1) << 32) + ((1ul << 32) - 1)
 
static const IntType bit_mask_ [IntSize]
 Contains a single bit at each of the 64 positions. More...
 
static const IntType count_mask_ [4]
 Mask used for quickly counting the number of set bits, see count(). More...
 
static const IntType ones_mask_ [IntSize]
 Contains as many ones as the position in the array tells. More...
 

Friends

Bitvector operator& (Bitvector const &lhs, Bitvector const &rhs)
 
Bitvector operator- (Bitvector const &lhs, Bitvector const &rhs)
 Set-minus of two Bitvectors. More...
 
std::ostream & operator<< (std::ostream &out, Bitvector const &rhs)
 
Bitvector operator^ (Bitvector const &lhs, Bitvector const &rhs)
 
Bitvector operator| (Bitvector const &lhs, Bitvector const &rhs)
 

Constructor & Destructor Documentation

Bitvector ( )
default

Default constructor. Creates an empty Bitvector of size 0.

Bitvector ( const size_t  size,
const bool  init = false 
)
inline

Constructor that takes a size and an optional bool value to initialize the Bitvector, false by default.

Definition at line 85 of file bitvector.hpp.

Bitvector ( const size_t  size,
const std::initializer_list< int >  list 
)
inline

Constructor that takes a size and a list of values (positions) to be set to true.

Definition at line 95 of file bitvector.hpp.

Member Function Documentation

size_t count ( ) const

Counts the number of set bits in the Bitvector.

Definition at line 226 of file bitvector.cpp.

std::string dump ( ) const

Definition at line 362 of file bitvector.cpp.

std::string dump_int ( IntType  x) const

Definition at line 376 of file bitvector.cpp.

void flip ( size_t  index)
inline

Flips (inverts) the value of a single bit, with boundary check.

Definition at line 169 of file bitvector.hpp.

bool get ( size_t  index) const
inline

Returns the value of a single bit, with boundary check.

Definition at line 124 of file bitvector.hpp.

size_t hash ( ) const

Returns an std::hash value for the Bitvector.

Definition at line 258 of file bitvector.cpp.

void invert ( )

Flip all bits.

Definition at line 286 of file bitvector.cpp.

void normalize ( )

Brings the Bitvector in a normalized form, where the first bit is always zero.

If the first bit is zero, nothing happens. However, if is is one, the whole Bitvector is flipped using invert().

Definition at line 303 of file bitvector.cpp.

bool operator!= ( const Bitvector other) const
inline

Definition at line 187 of file bitvector.hpp.

Bitvector & operator&= ( Bitvector const &  rhs)

Definition at line 160 of file bitvector.cpp.

bool operator< ( Bitvector const &  rhs) const
inline

Strict subset.

Definition at line 195 of file bitvector.hpp.

bool operator<= ( Bitvector const &  rhs) const
inline

Subset or equal.

Definition at line 211 of file bitvector.hpp.

bool operator== ( const Bitvector other) const

Definition at line 196 of file bitvector.cpp.

bool operator> ( Bitvector const &  rhs) const
inline

Strict superset.

Definition at line 203 of file bitvector.hpp.

bool operator>= ( Bitvector const &  rhs) const
inline

Superset or equal.

Definition at line 219 of file bitvector.hpp.

bool operator[] ( size_t  index) const
inline

Returns the value of a single bit, without boundary check.

Definition at line 117 of file bitvector.hpp.

Bitvector & operator^= ( Bitvector const &  rhs)

Definition at line 179 of file bitvector.cpp.

Bitvector & operator|= ( Bitvector const &  rhs)

Definition at line 169 of file bitvector.cpp.

Bitvector operator~ ( ) const

Definition at line 189 of file bitvector.cpp.

void reset ( const bool  value = false)

Reset all the bits to false. If provided with parameter true, sets all bits to true.

Definition at line 313 of file bitvector.cpp.

void set ( size_t  index)
inline

Sets the value of a single bit to true, with boundary check.

Definition at line 135 of file bitvector.hpp.

void set ( size_t  index,
bool  value 
)
inline

Sets the value of a single bit to a given bool value, with boundary check.

Definition at line 157 of file bitvector.hpp.

size_t size ( ) const
inline

Returns the size (number of total bits) of this Bitvector.

Definition at line 105 of file bitvector.hpp.

Bitvector symmetric_difference ( Bitvector const &  rhs) const

Definition at line 213 of file bitvector.cpp.

Bitvector symmetric_difference ( Bitvector const &  lhs,
Bitvector const &  rhs 
)
static

Definition at line 218 of file bitvector.cpp.

void unset ( size_t  index)
inline

Sets the value of a single bit to false, with boundary check.

Definition at line 146 of file bitvector.hpp.

void unset_padding ( )
protected

Internal function that sets all bits to zero that are not actively used.

The data_ buffer always contains a multiple of IntSize many bits, thus there might be surplus bits at its end for padding. In case we do operations with Bitvectors of different size, these might be affected, so we need to reset them to zero sometimes.

Definition at line 334 of file bitvector.cpp.

Bitvector::IntType x_hash ( ) const

Returns a hash value of type IntType, that is quicker to calculate than hash(), and thus can be used where the std::hash is not needed.

Definition at line 274 of file bitvector.cpp.

Friends And Related Function Documentation

Bitvector operator& ( Bitvector const &  lhs,
Bitvector const &  rhs 
)
friend

Definition at line 105 of file bitvector.cpp.

Bitvector operator- ( Bitvector const &  lhs,
Bitvector const &  rhs 
)
friend

Set-minus of two Bitvectors.

Definition at line 151 of file bitvector.cpp.

std::ostream& operator<< ( std::ostream &  out,
Bitvector const &  rhs 
)
friend

Definition at line 354 of file bitvector.cpp.

Bitvector operator^ ( Bitvector const &  lhs,
Bitvector const &  rhs 
)
friend

Definition at line 135 of file bitvector.cpp.

Bitvector operator| ( Bitvector const &  lhs,
Bitvector const &  rhs 
)
friend

Definition at line 120 of file bitvector.cpp.

Member Typedef Documentation

typedef uint64_t IntType

Definition at line 66 of file bitvector.hpp.

Member Data Documentation

const Bitvector::IntType all_0_ = 0ul
staticprotected

Definition at line 250 of file bitvector.hpp.

const Bitvector::IntType all_1_ = (((1ul << 32) - 1) << 32) + ((1ul << 32) - 1)
staticprotected

Definition at line 251 of file bitvector.hpp.

const Bitvector::IntType bit_mask_
staticprotected
Initial value:
=
{
1ul << 0, 1ul << 1, 1ul << 2, 1ul << 3, 1ul << 4, 1ul << 5, 1ul << 6, 1ul << 7,
1ul << 8, 1ul << 9, 1ul << 10, 1ul << 11, 1ul << 12, 1ul << 13, 1ul << 14, 1ul << 15,
1ul << 16, 1ul << 17, 1ul << 18, 1ul << 19, 1ul << 20, 1ul << 21, 1ul << 22, 1ul << 23,
1ul << 24, 1ul << 25, 1ul << 26, 1ul << 27, 1ul << 28, 1ul << 29, 1ul << 30, 1ul << 31,
1ul << 32, 1ul << 33, 1ul << 34, 1ul << 35, 1ul << 36, 1ul << 37, 1ul << 38, 1ul << 39,
1ul << 40, 1ul << 41, 1ul << 42, 1ul << 43, 1ul << 44, 1ul << 45, 1ul << 46, 1ul << 47,
1ul << 48, 1ul << 49, 1ul << 50, 1ul << 51, 1ul << 52, 1ul << 53, 1ul << 54, 1ul << 55,
1ul << 56, 1ul << 57, 1ul << 58, 1ul << 59, 1ul << 60, 1ul << 61, 1ul << 62, 1ul << 63
}

Contains a single bit at each of the 64 positions.

Definition at line 253 of file bitvector.hpp.

const Bitvector::IntType count_mask_
staticprotected
Initial value:
=
{
0x5555555555555555,
0x3333333333333333,
0x0f0f0f0f0f0f0f0f,
0x0101010101010101
}

Mask used for quickly counting the number of set bits, see count().

Definition at line 256 of file bitvector.hpp.

std::vector<IntType> data_
protected

Definition at line 263 of file bitvector.hpp.

const size_t IntSize = sizeof(IntType) * 8
static

Definition at line 67 of file bitvector.hpp.

const Bitvector::IntType ones_mask_
staticprotected
Initial value:
=
{
Bitvector::all_0_, Bitvector::all_1_ >> 63, Bitvector::all_1_ >> 62, Bitvector::all_1_ >> 61,
Bitvector::all_1_ >> 60, Bitvector::all_1_ >> 59, Bitvector::all_1_ >> 58, Bitvector::all_1_ >> 57,
Bitvector::all_1_ >> 56, Bitvector::all_1_ >> 55, Bitvector::all_1_ >> 54, Bitvector::all_1_ >> 53,
Bitvector::all_1_ >> 52, Bitvector::all_1_ >> 51, Bitvector::all_1_ >> 50, Bitvector::all_1_ >> 49,
Bitvector::all_1_ >> 48, Bitvector::all_1_ >> 47, Bitvector::all_1_ >> 46, Bitvector::all_1_ >> 45,
Bitvector::all_1_ >> 44, Bitvector::all_1_ >> 43, Bitvector::all_1_ >> 42, Bitvector::all_1_ >> 41,
Bitvector::all_1_ >> 40, Bitvector::all_1_ >> 39, Bitvector::all_1_ >> 38, Bitvector::all_1_ >> 37,
Bitvector::all_1_ >> 36, Bitvector::all_1_ >> 35, Bitvector::all_1_ >> 34, Bitvector::all_1_ >> 33,
Bitvector::all_1_ >> 32, Bitvector::all_1_ >> 31, Bitvector::all_1_ >> 30, Bitvector::all_1_ >> 29,
Bitvector::all_1_ >> 28, Bitvector::all_1_ >> 27, Bitvector::all_1_ >> 26, Bitvector::all_1_ >> 25,
Bitvector::all_1_ >> 24, Bitvector::all_1_ >> 23, Bitvector::all_1_ >> 22, Bitvector::all_1_ >> 21,
Bitvector::all_1_ >> 20, Bitvector::all_1_ >> 19, Bitvector::all_1_ >> 18, Bitvector::all_1_ >> 17,
Bitvector::all_1_ >> 16, Bitvector::all_1_ >> 15, Bitvector::all_1_ >> 14, Bitvector::all_1_ >> 13,
Bitvector::all_1_ >> 12, Bitvector::all_1_ >> 11, Bitvector::all_1_ >> 10, Bitvector::all_1_ >> 9,
Bitvector::all_1_ >> 8, Bitvector::all_1_ >> 7, Bitvector::all_1_ >> 6, Bitvector::all_1_ >> 5,
Bitvector::all_1_ >> 4, Bitvector::all_1_ >> 3, Bitvector::all_1_ >> 2, Bitvector::all_1_ >> 1
}

Contains as many ones as the position in the array tells.

The element at position i contains i many ones, starting from the right:

ones_mask_[0] --> 0 ones: 0000...0000
ones_mask_[1] --> 1 one:  0000...0001
ones_mask_[2] --> 2 ones: 0000...0011
...

This mask is used for unsetting the padding bits in unset_padding().

Definition at line 254 of file bitvector.hpp.

size_t size_ = 0
protected

Definition at line 262 of file bitvector.hpp.


The documentation for this class was generated from the following files: