BitMagicC++Library
Data Structures | Public Types | Public Member Functions | Friends
bm::bvector< Alloc > Class Template Reference

bitvector Bit-vector container with runtime compression of bits More...

#include <bm.h>

Inheritance diagram for bm::bvector< Alloc >:
Inheritance graph
[legend]

Data Structures

struct  allocation_policy
 memory allocation policy More...
 
struct  blocks_count
 structure for bit counts per block (prefix sum) Structure is used to accelerate bit range scans More...
 
class  counted_enumerator
 Constant iterator designed to enumerate "ON" bits counted_enumerator keeps bitcount, ie number of ON bits starting from the position 0 in the bit string up to the currently enumerated bit. More...
 
class  enumerator
 Constant iterator designed to enumerate "ON" bits. More...
 
class  insert_iterator
 Output iterator iterator designed to set "ON" bits based on input sequence of integers (bit indeces). More...
 
class  iterator_base
 Base class for all iterators. More...
 
class  reference
 Class reference implements an object for bit assignment. More...
 
struct  statistics
 Statistical information about bitset's memory allocation details. More...
 

Public Types

enum  optmode { opt_free_0 = 1, opt_free_01 = 2, opt_compress = 3 }
 Optimization mode Every next level means additional checks (better compression vs time) More...
 
typedef Alloc allocator_type
 
typedef blocks_manager< Alloc > blocks_manager_type
 
typedef bm::id_t size_type
 Type used to count bits in the bit vector. More...
 
typedef bool const_reference
 

Public Member Functions

 bvector (strategy strat=BM_BIT, const gap_word_t *glevel_len=bm::gap_len_table< true >::_len, size_type bv_size=bm::id_max, const Alloc &alloc=Alloc())
 Constructs bvector class. More...
 
 bvector (size_type bv_size, strategy strat=BM_BIT, const gap_word_t *glevel_len=bm::gap_len_table< true >::_len, const Alloc &alloc=Alloc())
 Constructs bvector class. More...
 
 bvector (const bvector< Alloc > &bvect)
 Copy constructor. More...
 
 ~bvector () BMNOEXEPT
 
void init ()
 Explicit post-construction initialization. More...
 
bvectoroperator= (const bvector< Alloc > &bvect)
 Copy assignment operator. More...
 
 bvector (bvector< Alloc > &&bvect) BMNOEXEPT
 Move constructor. More...
 
 bvector (std::initializer_list< bm::id_t > il)
 Brace constructor. More...
 
bvectoroperator= (bvector< Alloc > &&bvect) BMNOEXEPT
 Move assignment operator. More...
 
reference operator[] (bm::id_t n)
 
bool operator[] (bm::id_t n) const
 
void operator&= (const bvector< Alloc > &bv)
 
void operator^= (const bvector< Alloc > &bv)
 
void operator|= (const bvector< Alloc > &bv)
 
void operator-= (const bvector< Alloc > &bv)
 
bool operator< (const bvector< Alloc > &bv) const
 
bool operator<= (const bvector< Alloc > &bv) const
 
bool operator> (const bvector< Alloc > &bv) const
 
bool operator>= (const bvector< Alloc > &bv) const
 
bool operator== (const bvector< Alloc > &bv) const
 
bool operator!= (const bvector< Alloc > &bv) const
 
bvector< Alloc > operator~ () const
 
Alloc get_allocator () const
 
bool set_bit (bm::id_t n, bool val=true)
 Sets bit n. More...
 
bool set_bit_and (bm::id_t n, bool val=true)
 Sets bit n using bit AND with the provided value. More...
 
bool set_bit_conditional (bm::id_t n, bool val, bool condition)
 Sets bit n only if current value equals the condition. More...
 
bvector< Alloc > & set (bm::id_t n, bool val=true)
 Sets bit n if val is true, clears bit n if val is false. More...
 
bvector< Alloc > & set ()
 Sets every bit in this bitset to 1. More...
 
bvector< Alloc > & set_range (bm::id_t left, bm::id_t right, bool value=true)
 Sets all bits in the specified closed interval [left,right] Interval must be inside the bvector's size. This method DOES NOT resize vector. More...
 
insert_iterator inserter ()
 
bool clear_bit (bm::id_t n)
 Clears bit n. More...
 
void clear (bool free_mem=false)
 Clears every bit in the bitvector. More...
 
bvector< Alloc > & reset ()
 Clears every bit in the bitvector. More...
 
bm::id_t count () const
 Returns count of bits which are 1. More...
 
size_type capacity () const
 Returns bvector's capacity (number of bits it can store) More...
 
size_type size () const
 return current size of the vector (bits) More...
 
void resize (size_type new_size)
 Change size of the bvector. More...
 
unsigned count_blocks (unsigned *arr) const
 Computes bitcount values for all bvector blocks. More...
 
bm::id_t count_range (bm::id_t left, bm::id_t right, const unsigned *block_count_arr=0) const
 Returns count of 1 bits in the given diapason. More...
 
void running_count_blocks (blocks_count *blocks_cnt) const
 compute running total of all blocks in bit vector More...
 
bm::id_t count_to (bm::id_t right, const blocks_count &blocks_cnt) const
 Returns count of 1 bits (population) in [0..right] range. More...
 
bm::id_t count_to_test (bm::id_t right, const blocks_count &blocks_cnt) const
 Returns count of 1 bits (population) in [0..right] range if test(right) == true. Faster than test() plus count_to() More...
 
bm::id_t recalc_count ()
 
void forget_count ()
 
bvector< Alloc > & invert ()
 Inverts all bits. More...
 
bool get_bit (bm::id_t n) const
 returns true if bit n is set and false is bit n is 0. More...
 
bool test (bm::id_t n) const
 returns true if bit n is set and false is bit n is 0. More...
 
bool any () const
 Returns true if any bits in this bitset are set, and otherwise returns false. More...
 
bool none () const
 Returns true if no bits are set, otherwise returns false. More...
 
bvector< Alloc > & flip (bm::id_t n)
 Flips bit n. More...
 
bvector< Alloc > & flip ()
 Flips all bits. More...
 
void swap (bvector< Alloc > &bvect) BMNOEXEPT
 Exchanges content of bv and this bvector. More...
 
bool find (bm::id_t from, bm::id_t &pos) const
 Finds index of 1 bit starting from position. More...
 
bm::id_t get_first () const
 find first 1 bit in vector. Function may return 0 and this requires an extra check if bit 0 is actually set or bit-vector is empty More...
 
bm::id_t get_next (bm::id_t prev) const
 Finds the number of the next bit ON. More...
 
bm::id_t extract_next (bm::id_t prev)
 Finds the number of the next bit ON and sets it to 0. More...
 
void calc_stat (struct bm::bvector< Alloc >::statistics *st) const
 Calculates bitvector statistics. More...
 
bm::bvector< Alloc > & bit_or (const bm::bvector< Alloc > &vect)
 Logical OR operation. More...
 
bm::bvector< Alloc > & bit_and (const bm::bvector< Alloc > &vect)
 Logical AND operation. More...
 
bm::bvector< Alloc > & bit_xor (const bm::bvector< Alloc > &vect)
 Logical XOR operation. More...
 
bm::bvector< Alloc > & bit_sub (const bm::bvector< Alloc > &vect)
 Logical SUB operation. More...
 
void set_new_blocks_strat (strategy strat)
 Sets new blocks allocation strategy. More...
 
strategy get_new_blocks_strat () const
 Returns blocks allocation strategy. More...
 
void optimize (bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
 Optimize memory bitvector's memory allocation. More...
 
void optimize_gap_size ()
 Optimize sizes of GAP blocks. More...
 
void set_gap_levels (const gap_word_t *glevel_len)
 Sets new GAP lengths table. All GAP blocks will be reallocated to match the new scheme. More...
 
int compare (const bvector< Alloc > &bvect) const
 Lexicographical comparison with a bitvector. More...
 
bm::word_tallocate_tempblock () const
 Allocates temporary block of memory. More...
 
void free_tempblock (bm::word_t *block) const
 Frees temporary block of memory. More...
 
enumerator first () const
 Returns enumerator pointing on the first non-zero bit. More...
 
enumerator end () const
 Returns enumerator pointing on the next bit after the last. More...
 
enumerator get_enumerator (bm::id_t pos) const
 Returns enumerator pointing on specified or the next available bit. More...
 
void combine_operation (const bm::bvector< Alloc > &bvect, bm::operation opcode)
 
const bm::word_tget_block (unsigned nb) const
 get access to internal block by number More...
 
void set_bit_no_check (bm::id_t n)
 Set bit without checking preconditions (size, etc) More...
 
void combine_operation_with_block (unsigned nb, const bm::word_t *arg_blk, bool arg_gap, bm::operation opcode)
 
const blocks_manager_typeget_blocks_manager () const
 
blocks_manager_typeget_blocks_manager ()
 

Friends

class iterator_base
 
class enumerator
 

Detailed Description

template<class Alloc>
class bm::bvector< Alloc >

bitvector Bit-vector container with runtime compression of bits

Examples:
sample14.cpp, sample4.cpp, and sample6.cpp.

Definition at line 108 of file bm.h.

Member Typedef Documentation

◆ allocator_type

template<class Alloc>
typedef Alloc bm::bvector< Alloc >::allocator_type

Definition at line 112 of file bm.h.

◆ blocks_manager_type

template<class Alloc>
typedef blocks_manager<Alloc> bm::bvector< Alloc >::blocks_manager_type

Definition at line 113 of file bm.h.

◆ const_reference

template<class Alloc>
typedef bool bm::bvector< Alloc >::const_reference

Definition at line 213 of file bm.h.

◆ size_type

template<class Alloc>
typedef bm::id_t bm::bvector< Alloc >::size_type

Type used to count bits in the bit vector.

Definition at line 115 of file bm.h.

Member Enumeration Documentation

◆ optmode

template<class Alloc>
enum bm::bvector::optmode

Optimization mode Every next level means additional checks (better compression vs time)

See also
optimize
Enumerator
opt_free_0 

Free unused 0 blocks.

opt_free_01 

Free unused 0 and 1 blocks.

opt_compress 

compress blocks when possible

Definition at line 1663 of file bm.h.

Constructor & Destructor Documentation

◆ bvector() [1/5]

template<class Alloc>
bm::bvector< Alloc >::bvector ( strategy  strat = BM_BIT,
const gap_word_t glevel_len = bm::gap_len_table<true>::_len,
size_type  bv_size = bm::id_max,
const Alloc &  alloc = Alloc() 
)
inline

Constructs bvector class.

Parameters
strat- operation mode strategy, BM_BIT - default strategy, bvector use plain bitset blocks, (performance oriented strategy). BM_GAP - memory effitent strategy, bvector allocates blocks as array of intervals(gaps) and convert blocks into plain bitsets only when enthropy grows.
glevel_len
bv_size
  • bvector size (number of bits addressable by bvector), bm::id_max means "no limits" (recommended). bit vector allocates this space dynamically on demand.
alloc- alllocator for this instance
See also
bm::gap_len_table bm::gap_len_table_min set_new_blocks_strat

Definition at line 1011 of file bm.h.

Referenced by bm::bvector< Alloc >::blocks_count::copy_from().

◆ bvector() [2/5]

template<class Alloc>
bm::bvector< Alloc >::bvector ( size_type  bv_size,
strategy  strat = BM_BIT,
const gap_word_t glevel_len = bm::gap_len_table<true>::_len,
const Alloc &  alloc = Alloc() 
)
inline

Constructs bvector class.

Definition at line 1023 of file bm.h.

◆ bvector() [3/5]

template<class Alloc>
bm::bvector< Alloc >::bvector ( const bvector< Alloc > &  bvect)
inline

Copy constructor.

Definition at line 1035 of file bm.h.

◆ ~bvector()

template<class Alloc>
bm::bvector< Alloc >::~bvector ( )
inline

Definition at line 1041 of file bm.h.

◆ bvector() [4/5]

template<class Alloc>
bm::bvector< Alloc >::bvector ( bvector< Alloc > &&  bvect)
inline

Move constructor.

Definition at line 1073 of file bm.h.

◆ bvector() [5/5]

template<class Alloc>
bm::bvector< Alloc >::bvector ( std::initializer_list< bm::id_t il)
inline

Brace constructor.

Definition at line 1089 of file bm.h.

Member Function Documentation

◆ allocate_tempblock()

template<class Alloc>
bm::word_t* bm::bvector< Alloc >::allocate_tempblock ( ) const
inline

Allocates temporary block of memory.

Temp block can be passed to bvector functions requiring some temp memory for their operation. (like serialize)

Note
method is marked const, but it's not quite true, since it can in some cases modify the state of the block allocator (if it has a state). (Can be important in MT programs).
See also
free_tempblock

Definition at line 1724 of file bm.h.

◆ any()

template<class Alloc>
bool bm::bvector< Alloc >::any ( ) const
inline

Returns true if any bits in this bitset are set, and otherwise returns false.

Returns
true if any bit is set

Definition at line 1473 of file bm.h.

Referenced by bm::bvector<>::none().

◆ bit_and()

template<class Alloc>
bm::bvector<Alloc>& bm::bvector< Alloc >::bit_and ( const bm::bvector< Alloc > &  vect)
inline

Logical AND operation.

Parameters
vect- Argument vector.

Definition at line 1606 of file bm.h.

Referenced by bm::operator &(), and bm::bvector<>::operator &=().

◆ bit_or()

template<class Alloc>
bm::bvector<Alloc>& bm::bvector< Alloc >::bit_or ( const bm::bvector< Alloc > &  vect)
inline

Logical OR operation.

Parameters
vect- Argument vector.

Definition at line 1595 of file bm.h.

Referenced by bm::bvector<>::operator=(), bm::operator|(), and bm::bvector<>::operator|=().

◆ bit_sub()

template<class Alloc>
bm::bvector<Alloc>& bm::bvector< Alloc >::bit_sub ( const bm::bvector< Alloc > &  vect)
inline

Logical SUB operation.

Parameters
vect- Argument vector.

Definition at line 1628 of file bm.h.

Referenced by bm::operator-(), and bm::bvector<>::operator-=().

◆ bit_xor()

template<class Alloc>
bm::bvector<Alloc>& bm::bvector< Alloc >::bit_xor ( const bm::bvector< Alloc > &  vect)
inline

Logical XOR operation.

Parameters
vect- Argument vector.

Definition at line 1617 of file bm.h.

Referenced by bm::operator^(), and bm::bvector<>::operator^=().

◆ calc_stat()

template<typename Alloc>
void bm::bvector< Alloc >::calc_stat ( struct bm::bvector< Alloc >::statistics st) const

Calculates bitvector statistics.

Parameters
st- pointer on statistics structure to be filled in.

Function fills statistics structure containing information about how this vector uses memory and estimation of max. amount of memory bvector needs to serialize itself.

See also
statistics
Examples:
xsample01.cpp.

Definition at line 2533 of file bm.h.

Referenced by calc_memory_footprint(), convert_bv2bvs(), bm::bvector<>::extract_next(), generate_bvector(), bm::bvector<>::optimize(), bm::bvector<>::optimize_gap_size(), and print_statistics().

◆ capacity()

template<class Alloc>
size_type bm::bvector< Alloc >::capacity ( ) const
inline

Returns bvector's capacity (number of bits it can store)

Definition at line 1343 of file bm.h.

◆ clear()

template<class Alloc>
void bm::bvector< Alloc >::clear ( bool  free_mem = false)
inline

Clears every bit in the bitvector.

Parameters
free_memif "true" (default) bvector frees the memory, otherwise sets blocks to 0.
Examples:
xsample01.cpp.

Definition at line 1317 of file bm.h.

Referenced by bv_count_and(), main(), bm::bvector<>::operator=(), bm::bvector<>::reset(), speed_test_bv_index(), speed_test_bvs_index(), speed_test_sv_index(), and speed_test_vect_index().

◆ clear_bit()

template<class Alloc>
bool bm::bvector< Alloc >::clear_bit ( bm::id_t  n)
inline

Clears bit n.

Parameters
n- bit's index to be cleaned.
Returns
true if bit was cleared

Definition at line 1305 of file bm.h.

◆ combine_operation()

template<class Alloc>
void bm::bvector< Alloc >::combine_operation ( const bm::bvector< Alloc > &  bvect,
bm::operation  opcode 
)

◆ combine_operation_with_block()

template<class Alloc>
void bm::bvector< Alloc >::combine_operation_with_block ( unsigned  nb,
const bm::word_t arg_blk,
bool  arg_gap,
bm::operation  opcode 
)
inline

Definition at line 1838 of file bm.h.

◆ compare()

template<typename Alloc>
int bm::bvector< Alloc >::compare ( const bvector< Alloc > &  bvect) const

Lexicographical comparison with a bitvector.

Function compares current bitvector with the provided argument bit by bit and returns -1 if our bitvector less than the argument, 1 - greater, 0 - equal.

Examples:
xsample01.cpp.

Definition at line 2400 of file bm.h.

Referenced by convert_bv2bvs(), main(), bm::bvector<>::operator!=(), bm::bvector<>::operator<(), bm::bvector<>::operator<=(), bm::bvector<>::operator==(), bm::bvector<>::operator>(), and bm::bvector<>::operator>=().

◆ count()

template<typename Alloc >
bm::id_t bm::bvector< Alloc >::count ( ) const

Returns count of bits which are 1.

Returns
Total number of bits ON.
Examples:
xsample01.cpp.

Definition at line 2004 of file bm.h.

Referenced by bv_count_test(), convert_bv2vect(), main(), pre_heat(), print_statistics(), bm::bvector<>::recalc_count(), bm::bvector<>::reset(), and serialize_bvector().

◆ count_blocks()

template<class Alloc>
unsigned bm::bvector< Alloc >::count_blocks ( unsigned *  arr) const
inline

Computes bitcount values for all bvector blocks.

Parameters
arr- pointer on array of block bit counts
Returns
Index of the last block counted. This number +1 gives you number of arr elements initialized during the function call.

Definition at line 1368 of file bm.h.

Referenced by bv_count_range_acc(), and bm::bvector<>::running_count_blocks().

◆ count_range()

template<typename Alloc >
bm::id_t bm::bvector< Alloc >::count_range ( bm::id_t  left,
bm::id_t  right,
const unsigned *  block_count_arr = 0 
) const

Returns count of 1 bits in the given diapason.

Parameters
left- index of first bit start counting from
right- index of last bit
block_count_arr- optional parameter (bitcount by bvector blocks) calculated by count_blocks method. Used to improve performance of wide range searches
Returns
population count in the diapason

Definition at line 2153 of file bm.h.

Referenced by bv_count_range(), bv_count_range_acc(), and bm::bvector<>::count_blocks().

◆ count_to()

template<typename Alloc >
bm::id_t bm::bvector< Alloc >::count_to ( bm::id_t  right,
const blocks_count blocks_cnt 
) const

Returns count of 1 bits (population) in [0..right] range.

Parameters
right- index of last bit
blocks_cnt- block count structure to accelerate search should be prepared using running_count_blocks
Returns
population count in the diapason
See also
running_count_blocks
count_to_test

Definition at line 2066 of file bm.h.

Referenced by bv_count_to_acc(), bv_count_to_range_acc(), and bm::bvector<>::count_blocks().

◆ count_to_test()

template<typename Alloc >
bm::id_t bm::bvector< Alloc >::count_to_test ( bm::id_t  right,
const blocks_count blocks_cnt 
) const

Returns count of 1 bits (population) in [0..right] range if test(right) == true. Faster than test() plus count_to()

Parameters
right- index of last bit
blocks_cnt- block count structure to accelerate search should be prepared using running_count_blocks
Returns
population count in the diapason or 0 if right bit test failed
See also
running_count_blocks
count_to

Definition at line 2102 of file bm.h.

Referenced by bm::bvector<>::count_blocks().

◆ end()

template<class Alloc>
bvector::enumerator bm::bvector< Alloc >::end ( ) const
inline

Returns enumerator pointing on the next bit after the last.

Examples:
xsample01.cpp.

Definition at line 1758 of file bm.h.

Referenced by bm::bvector<>::bvector(), combine_or_test(), main(), speed_test_sv_index(), and speed_test_vect_index().

◆ extract_next()

template<class Alloc>
bm::id_t bm::bvector< Alloc >::extract_next ( bm::id_t  prev)
inline

Finds the number of the next bit ON and sets it to 0.

Parameters
prev- Index of the previously found bit.
Returns
Index of the next bit which is ON or 0 if not found.
See also
get_first, get_next,

Definition at line 1572 of file bm.h.

◆ find()

template<class Alloc >
bool bm::bvector< Alloc >::find ( bm::id_t  from,
bm::id_t pos 
) const

Finds index of 1 bit starting from position.

Parameters
from- position to start search from
pos- index of the found 1 bit
Returns
true if search returned result
See also
get_first, get_next, extract_next

Definition at line 2868 of file bm.h.

Referenced by bm::bvector<>::swap().

◆ first()

template<class Alloc>
enumerator bm::bvector< Alloc >::first ( ) const
inline

Returns enumerator pointing on the first non-zero bit.

Examples:
xsample01.cpp.

Definition at line 1749 of file bm.h.

Referenced by bv2delta(), bv_counted_enumerator(), convert_bv2sv(), convert_bv2vect(), bm::bvector< Alloc >::enumerator::go_to(), main(), speed_test_bv_index(), and speed_test_bvs_index().

◆ flip() [1/2]

template<class Alloc>
bvector<Alloc>& bm::bvector< Alloc >::flip ( bm::id_t  n)
inline

Flips bit n.

Returns
*this

Definition at line 1501 of file bm.h.

◆ flip() [2/2]

template<class Alloc>
bvector<Alloc>& bm::bvector< Alloc >::flip ( )
inline

Flips all bits.

Returns
*this

Definition at line 1511 of file bm.h.

◆ forget_count()

template<class Alloc>
void bm::bvector< Alloc >::forget_count ( )
inline

Disables count cache. Next call to count() or recalc_count() restores count caching.

Note
Works only if BMCOUNTOPT enabled(defined). Othewise does nothing.

Definition at line 1441 of file bm.h.

◆ free_tempblock()

template<class Alloc>
void bm::bvector< Alloc >::free_tempblock ( bm::word_t block) const
inline

Frees temporary block of memory.

Note
method is marked const, but it's not quite true, since it can in some cases modify the state of the block allocator (if it has a state). (Can be important in MT programs).
See also
allocate_tempblock

Definition at line 1739 of file bm.h.

◆ get_allocator()

template<class Alloc>
Alloc bm::bvector< Alloc >::get_allocator ( ) const
inline

Definition at line 1196 of file bm.h.

◆ get_bit()

template<typename Alloc >
bool bm::bvector< Alloc >::get_bit ( bm::id_t  n) const

returns true if bit n is set and false is bit n is 0.

Parameters
n- Index of the bit to check.
Returns
Bit value (1 or 0)

Definition at line 2280 of file bm.h.

Referenced by bm::bvector<>::flip(), bm::bvector<>::forget_count(), bm::bvector<>::operator[](), and bm::bvector<>::test().

◆ get_block()

template<class Alloc>
const bm::word_t* bm::bvector< Alloc >::get_block ( unsigned  nb) const
inline

get access to internal block by number

This is an internal method, declared public to add low level optimized algorithms outside of the main bvector<> class. Use it AT YOUR OWN RISK!

Parameters
nb- block number

Definition at line 1787 of file bm.h.

Referenced by bm::bvector<>::combine_operation_with_block(), and bm::bvector< Alloc >::enumerator::go_to().

◆ get_blocks_manager() [1/2]

template<class Alloc>
const blocks_manager_type& bm::bvector< Alloc >::get_blocks_manager ( ) const
inline

Definition at line 1879 of file bm.h.

◆ get_blocks_manager() [2/2]

template<class Alloc>
blocks_manager_type& bm::bvector< Alloc >::get_blocks_manager ( )
inline

Definition at line 1884 of file bm.h.

◆ get_enumerator()

template<class Alloc>
enumerator bm::bvector< Alloc >::get_enumerator ( bm::id_t  pos) const
inline

Returns enumerator pointing on specified or the next available bit.

Definition at line 1767 of file bm.h.

Referenced by bm::bvector<>::first().

◆ get_first()

template<class Alloc>
bm::id_t bm::bvector< Alloc >::get_first ( ) const
inline

find first 1 bit in vector. Function may return 0 and this requires an extra check if bit 0 is actually set or bit-vector is empty

Returns
Index of the first 1 bit, may return 0
See also
get_next, find, extract_next

Definition at line 1551 of file bm.h.

Referenced by print_bvector().

◆ get_new_blocks_strat()

template<class Alloc>
strategy bm::bvector< Alloc >::get_new_blocks_strat ( ) const
inline

Returns blocks allocation strategy.

Returns
- Strategy code 0 - bitblocks allocation only. 1 - Blocks mutation mode (adaptive algorithm)
See also
set_new_blocks_strat

Definition at line 1652 of file bm.h.

Referenced by bm::bvector<>::combine_operation(), and bm::bvector<>::set_bit_no_check().

◆ get_next()

template<class Alloc>
bm::id_t bm::bvector< Alloc >::get_next ( bm::id_t  prev) const
inline

Finds the number of the next bit ON.

Parameters
prev- Index of the previously found bit.
Returns
Index of the next bit which is ON or 0 if not found.
See also
get_first, find, extract_next

Definition at line 1560 of file bm.h.

Referenced by print_bvector().

◆ init()

template<class Alloc>
void bm::bvector< Alloc >::init ( )
inline

Explicit post-construction initialization.

Definition at line 1049 of file bm.h.

Referenced by bv_set_bit_no_check_test(), bm::bvector<>::bvector(), and main().

◆ inserter()

template<class Alloc>
insert_iterator bm::bvector< Alloc >::inserter ( )
inline

Function erturns insert iterator for this bitvector

Definition at line 1294 of file bm.h.

Referenced by main().

◆ invert()

template<typename Alloc >
bvector< Alloc > & bm::bvector< Alloc >::invert ( )

Inverts all bits.

Definition at line 2254 of file bm.h.

Referenced by bm::bvector<>::flip(), bm::bvector<>::forget_count(), and bm::bvector<>::operator~().

◆ none()

template<class Alloc>
bool bm::bvector< Alloc >::none ( ) const
inline

Returns true if no bits are set, otherwise returns false.

Definition at line 1492 of file bm.h.

◆ operator!=()

template<class Alloc>
bool bm::bvector< Alloc >::operator!= ( const bvector< Alloc > &  bv) const
inline

Definition at line 1186 of file bm.h.

◆ operator&=()

template<class Alloc>
void bm::bvector< Alloc >::operator &= ( const bvector< Alloc > &  bv)
inline

Definition at line 1141 of file bm.h.

◆ operator-=()

template<class Alloc>
void bm::bvector< Alloc >::operator-= ( const bvector< Alloc > &  bv)
inline

Definition at line 1156 of file bm.h.

◆ operator<()

template<class Alloc>
bool bm::bvector< Alloc >::operator< ( const bvector< Alloc > &  bv) const
inline

Definition at line 1161 of file bm.h.

◆ operator<=()

template<class Alloc>
bool bm::bvector< Alloc >::operator<= ( const bvector< Alloc > &  bv) const
inline

Definition at line 1166 of file bm.h.

◆ operator=() [1/2]

template<class Alloc>
bvector& bm::bvector< Alloc >::operator= ( const bvector< Alloc > &  bvect)
inline

Copy assignment operator.

Definition at line 1058 of file bm.h.

◆ operator=() [2/2]

template<class Alloc>
bvector& bm::bvector< Alloc >::operator= ( bvector< Alloc > &&  bvect)
inline

Move assignment operator.

Definition at line 1111 of file bm.h.

◆ operator==()

template<class Alloc>
bool bm::bvector< Alloc >::operator== ( const bvector< Alloc > &  bv) const
inline

Definition at line 1181 of file bm.h.

Referenced by bm::bvector< Alloc >::iterator_base::operator!=().

◆ operator>()

template<class Alloc>
bool bm::bvector< Alloc >::operator> ( const bvector< Alloc > &  bv) const
inline

Definition at line 1171 of file bm.h.

◆ operator>=()

template<class Alloc>
bool bm::bvector< Alloc >::operator>= ( const bvector< Alloc > &  bv) const
inline

Definition at line 1176 of file bm.h.

◆ operator[]() [1/2]

template<class Alloc>
reference bm::bvector< Alloc >::operator[] ( bm::id_t  n)
inline

Definition at line 1128 of file bm.h.

◆ operator[]() [2/2]

template<class Alloc>
bool bm::bvector< Alloc >::operator[] ( bm::id_t  n) const
inline

Definition at line 1135 of file bm.h.

◆ operator^=()

template<class Alloc>
void bm::bvector< Alloc >::operator^= ( const bvector< Alloc > &  bv)
inline

Definition at line 1146 of file bm.h.

◆ operator|=()

template<class Alloc>
void bm::bvector< Alloc >::operator|= ( const bvector< Alloc > &  bv)
inline

Definition at line 1151 of file bm.h.

◆ operator~()

template<class Alloc>
bvector<Alloc> bm::bvector< Alloc >::operator~ ( ) const
inline

Definition at line 1191 of file bm.h.

◆ optimize()

template<typename Alloc >
void bm::bvector< Alloc >::optimize ( bm::word_t temp_block = 0,
optmode  opt_mode = opt_compress,
statistics stat = 0 
)

Optimize memory bitvector's memory allocation.

Function analyze all blocks in the bitvector, compresses blocks with a regular structure, frees some memory. This function is recommended after a bulk modification of the bitvector using set_bit, clear_bit or logical operations.

Optionally function can calculate vector post optimization statistics

See also
optmode, optimize_gap_size
Examples:
xsample01.cpp.

Definition at line 2311 of file bm.h.

Referenced by generate_bvector(), main(), serialize_bvector(), speed_test_bv_index(), speed_test_bvs_index(), speed_test_sv_index(), and speed_test_vect_index().

◆ optimize_gap_size()

template<typename Alloc >
void bm::bvector< Alloc >::optimize_gap_size ( )

Optimize sizes of GAP blocks.

This method runs an analysis to find optimal GAP levels for the specific vector. Current GAP compression algorithm uses several fixed GAP sizes. By default bvector uses some reasonable preset.

Definition at line 2360 of file bm.h.

◆ recalc_count()

template<class Alloc>
bm::id_t bm::bvector< Alloc >::recalc_count ( )
inline

Recalculate bitcount this function only make sense when BMCOUNTOPT is defined and bvector<> keeps its bitcount. Otherwise, equivalent of cout().

Definition at line 1428 of file bm.h.

◆ reset()

template<class Alloc>
bvector<Alloc>& bm::bvector< Alloc >::reset ( )
inline

Clears every bit in the bitvector.

Returns
*this;

Definition at line 1327 of file bm.h.

Referenced by bv_set_bit_test().

◆ resize()

template<typename Alloc >
void bm::bvector< Alloc >::resize ( size_type  new_size)

Change size of the bvector.

Parameters
new_size- new size in bits

Definition at line 2029 of file bm.h.

Referenced by convert_bv2sv(), bm::bvector<>::operator=(), and bm::bvector<>::size().

◆ running_count_blocks()

template<typename Alloc >
void bm::bvector< Alloc >::running_count_blocks ( blocks_count blocks_cnt) const

compute running total of all blocks in bit vector

Parameters
blocks_cnt- out pointer to counting structure, holding the array Function will fill full array of running totals
See also
count_to

Definition at line 2050 of file bm.h.

Referenced by bv_count_to_acc(), bv_count_to_range_acc(), and bm::bvector<>::count_blocks().

◆ set() [1/2]

template<class Alloc>
bvector<Alloc>& bm::bvector< Alloc >::set ( bm::id_t  n,
bool  val = true 
)
inline

Sets bit n if val is true, clears bit n if val is false.

Parameters
n- index of the bit to be set
val- new bit value
Returns
*this

Definition at line 1259 of file bm.h.

Referenced by fill_bvector(), generate_bvector(), and main().

◆ set() [2/2]

template<class Alloc>
bvector<Alloc>& bm::bvector< Alloc >::set ( )
inline

Sets every bit in this bitset to 1.

Returns
*this

Definition at line 1269 of file bm.h.

◆ set_bit()

template<class Alloc>
bool bm::bvector< Alloc >::set_bit ( bm::id_t  n,
bool  val = true 
)
inline

Sets bit n.

Parameters
n- index of the bit to be set.
val- new bit value
Returns
TRUE if bit was changed
Examples:
xsample01.cpp.

Definition at line 1208 of file bm.h.

Referenced by bv_set_bit_test(), bm::bvector<>::clear_bit(), fill_bvector(), generate_random_vector(), and bm::bvector<>::set().

◆ set_bit_and()

template<class Alloc>
bool bm::bvector< Alloc >::set_bit_and ( bm::id_t  n,
bool  val = true 
)
inline

Sets bit n using bit AND with the provided value.

Parameters
n- index of the bit to be set.
val- new bit value
Returns
TRUE if bit was changed

Definition at line 1224 of file bm.h.

◆ set_bit_conditional()

template<class Alloc>
bool bm::bvector< Alloc >::set_bit_conditional ( bm::id_t  n,
bool  val,
bool  condition 
)
inline

Sets bit n only if current value equals the condition.

Parameters
n- index of the bit to be set.
val- new bit value
condition- expected current value
Returns
TRUE if bit was changed

Definition at line 1241 of file bm.h.

◆ set_bit_no_check()

template<class Alloc >
void bm::bvector< Alloc >::set_bit_no_check ( bm::id_t  n)

Set bit without checking preconditions (size, etc)

Fast set bit method, without safety net. Make sure you call bvector<>::init() before setting bits with this function.

Side effect: invalidates bit-count optimization (BMCOUNTOPT)

Parameters
n- bit number

Definition at line 2619 of file bm.h.

Referenced by bv_set_bit_no_check_test(), bm::bvector<>::bvector(), bm::bvector<>::get_block(), bm::bvector<>::invert(), bm::bvector<>::set_bit(), and bm::bvector<>::set_bit_no_check().

◆ set_gap_levels()

template<typename Alloc >
void bm::bvector< Alloc >::set_gap_levels ( const gap_word_t glevel_len)

Sets new GAP lengths table. All GAP blocks will be reallocated to match the new scheme.

Parameters
glevel_len- pointer on C-style array keeping GAP block sizes.

Definition at line 2384 of file bm.h.

Referenced by bm::bvector<>::optimize_gap_size().

◆ set_new_blocks_strat()

template<class Alloc>
void bm::bvector< Alloc >::set_new_blocks_strat ( strategy  strat)
inline

Sets new blocks allocation strategy.

Parameters
strat- Strategy code 0 - bitblocks allocation only. 1 - Blocks mutation mode (adaptive algorithm)

Definition at line 1641 of file bm.h.

Referenced by main().

◆ set_range()

template<typename Alloc >
bvector< Alloc > & bm::bvector< Alloc >::set_range ( bm::id_t  left,
bm::id_t  right,
bool  value = true 
)

Sets all bits in the specified closed interval [left,right] Interval must be inside the bvector's size. This method DOES NOT resize vector.

Parameters
left- interval start
right- interval end (closed interval)
value- value to set interval in
Returns
*this

Definition at line 1974 of file bm.h.

Referenced by bv_count_and(), bm::bvector<>::combine_operation(), generate_bvector(), bm::bvector<>::resize(), bm::bvector<>::set(), and bm::bvector<>::set_range().

◆ size()

template<class Alloc>
size_type bm::bvector< Alloc >::size ( ) const
inline

return current size of the vector (bits)

Definition at line 1351 of file bm.h.

Referenced by bm::bvector<>::operator=().

◆ swap()

template<class Alloc>
void bm::bvector< Alloc >::swap ( bvector< Alloc > &  bvect)
inline

Exchanges content of bv and this bvector.

Definition at line 1518 of file bm.h.

Referenced by main().

◆ test()

template<class Alloc>
bool bm::bvector< Alloc >::test ( bm::id_t  n) const
inline

returns true if bit n is set and false is bit n is 0.

Parameters
n- Index of the bit to check.
Returns
Bit value (1 or 0)

Definition at line 1464 of file bm.h.

Referenced by bm::bvector<>::find().

Friends And Related Function Documentation

◆ enumerator

template<class Alloc>
friend class enumerator
friend

Definition at line 918 of file bm.h.

◆ iterator_base

template<class Alloc>
friend class iterator_base
friend

Definition at line 917 of file bm.h.


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