BitMagic-C++
|
Bitvector Bit-vector container with runtime compression of bits. More...
#include <bm.h>
Data Structures | |
struct | allocation_policy |
memory allocation policy More... | |
class | bulk_insert_iterator |
Output iterator iterator designed to set "ON" bits based on input sequence of integers. 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 | mem_pool_guard |
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_none = 0, 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 allocator_type::allocator_pool_type | allocator_pool_type |
typedef blocks_manager< Alloc > | blocks_manager_type |
typedef blocks_manager_type::block_idx_type | block_idx_type |
typedef bm::id_t | size_type |
typedef bool | const_reference |
typedef rs_index< allocator_type > | blocks_count |
typedef rs_index< allocator_type > | rs_index_type |
Public Member Functions | |
Construction, initialization, assignment | |
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 (const bvector< Alloc > &bvect, size_type left, size_type right) | |
Copy constructor for range copy [left..right]. More... | |
~bvector () BMNOEXEPT | |
void | init () |
Explicit post-construction initialization. More... | |
bvector & | operator= (const bvector< Alloc > &bvect) |
Copy assignment operator. More... | |
bvector (bvector< Alloc > &&bvect) BMNOEXEPT | |
Move constructor. More... | |
bvector (std::initializer_list< size_type > il) | |
Brace constructor. More... | |
bvector & | operator= (bvector< Alloc > &&bvect) BMNOEXEPT |
Move assignment operator. More... | |
void | move_from (bvector< Alloc > &bvect) BMNOEXEPT |
Move bvector content from another bvector. More... | |
void | swap (bvector< Alloc > &bvect) BMNOEXEPT |
Exchanges content of bv and this bvector. More... | |
void | merge (bm::bvector< Alloc > &bvect) |
Merge/move content from another vector. More... | |
reference | operator[] (size_type n) |
bool | operator[] (size_type 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 |
void | set_allocator_pool (allocator_pool_type *pool_ptr) |
Set allocator pool for local (non-threaded) memory cyclic(lots of alloc-free ops) opertations. More... | |
allocator_pool_type * | get_allocator_pool () |
Get curent allocator pool (if set) More... | |
Bit access/modification methods | |
| |
bool | set_bit (size_type n, bool val=true) |
Sets bit n. More... | |
bool | set_bit_and (size_type n, bool val=true) |
Sets bit n using bit AND with the provided value. More... | |
bool | inc (size_type n) |
Increment the specified element. More... | |
bool | set_bit_conditional (size_type n, bool val, bool condition) |
Sets bit n only if current value equals the condition. More... | |
bvector< Alloc > & | set (size_type 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... | |
void | set (const size_type *ids, size_type ids_size, bm::sort_order so=bm::BM_UNKNOWN) |
Set list of bits in this bitset to 1. More... | |
void | keep (const size_type *ids, size_type ids_size, bm::sort_order so=bm::BM_UNKNOWN) |
Keep list of bits in this bitset, others are cleared. More... | |
void | clear (const size_type *ids, size_type ids_size, bm::sort_order so=bm::BM_UNKNOWN) |
clear list of bits in this bitset More... | |
void | set_bit_no_check (size_type n) |
Set bit without checking preconditions (size, etc) More... | |
bvector< Alloc > & | set_range (size_type left, size_type 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... | |
void | copy_range (const bvector< Alloc > &bvect, size_type left, size_type right) |
Copy all bits in the specified closed interval [left,right]. More... | |
bool | clear_bit (size_type n) |
Clears bit n. More... | |
void | clear_bit_no_check (size_type n) |
Clears bit n without precondiion checks. More... | |
void | clear (bool free_mem=false) |
Clears every bit in the bitvector. More... | |
bvector< Alloc > & | reset () |
Clears every bit in the bitvector. More... | |
bvector< Alloc > & | flip (size_type n) |
Flips bit n. More... | |
bvector< Alloc > & | flip () |
Flips all bits. More... | |
insert_iterator | inserter () |
Size and capacity | |
By default bvector is dynamically sized, manual control methods available | |
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... | |
Population counting and ranking methods | |
size_type | count () const |
population cout (count of ON bits) More... | |
block_idx_type | count_blocks (unsigned *arr) const |
Computes bitcount values for all bvector blocks. More... | |
size_type | count_range (size_type left, size_type right, const rs_index_type &rs_idx) const |
Returns count of 1 bits in the given range [left..right] Uses rank-select index to accelerate the search. More... | |
size_type | count_range (size_type left, size_type right) const |
Returns count of 1 bits in the given range [left..right]. More... | |
void | build_rs_index (rs_index_type *rs_idx, bvector< Alloc > *bv_blocks=0) const |
compute running total of all blocks in bit vector (rank-select index) More... | |
size_type | count_to (size_type n, const rs_index_type &rs_idx) const |
Returns count of 1 bits (population) in [0..right] range. More... | |
size_type | rank (size_type n, const rs_index_type &rs_idx) const |
Returns rank of specified bit position. More... | |
size_type | count_to_test (size_type n, const rs_index_type &blocks_cnt) const |
popcount in [0..right] range if test(right) == true More... | |
size_type | recalc_count () |
void | forget_count () |
Bit access (read-only) | |
| |
bool | get_bit (size_type n) const |
returns true if bit n is set and false is bit n is 0. More... | |
bool | test (size_type n) const |
returns true if bit n is set and false is bit n is 0. More... | |
bit-shift and insert operations | |
| |
bool | shift_right () |
Shift right by 1 bit, fill with zero return carry out. More... | |
bool | shift_left () |
Shift left by 1 bit, fill with zero return carry out. More... | |
bool | insert (size_type n, bool value) |
Insert bit into specified position All the vector content after insert position is shifted right. More... | |
void | erase (size_type n) |
Erase bit in the specified position All the vector content after erase position is shifted left. More... | |
Check for empty-ness of container | |
| |
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... | |
Scan and find bits and indexes | |
bool | find (size_type &pos) const |
Finds index of first 1 bit. More... | |
bool | find (size_type from, size_type &pos) const |
Finds index of 1 bit starting from position. More... | |
size_type | 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... | |
size_type | get_next (size_type prev) const |
Finds the number of the next bit ON. More... | |
size_type | extract_next (size_type prev) |
Finds the number of the next bit ON and sets it to 0. More... | |
bool | find_reverse (size_type &pos) const |
Finds last index of 1 bit. More... | |
bool | find_range (size_type &first, size_type &last) const |
Finds dynamic range of bit-vector [first, last]. More... | |
bool | find_rank (size_type rank, size_type from, size_type &pos) const |
Find bit-vector position for the specified rank(bitcount) More... | |
bool | find_rank (size_type rank, size_type from, size_type &pos, const rs_index_type &rs_idx) const |
Find bit-vector position for the specified rank(bitcount) More... | |
bool | select (size_type rank, size_type &pos, const rs_index_type &rs_idx) const |
select bit-vector position for the specified rank(bitcount) More... | |
Algebra of Sets operations | |
| |
bm::bvector< Alloc > & | bit_or (const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode) |
3-operand OR : this := bv1 OR bv2 More... | |
bm::bvector< Alloc > & | bit_xor (const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode) |
3-operand XOR : this := bv1 XOR bv2 More... | |
bm::bvector< Alloc > & | bit_and (const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode) |
3-operand AND : this := bv1 AND bv2 More... | |
bm::bvector< Alloc > & | bit_sub (const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode) |
3-operand SUB : this := bv1 MINUS bv2 SUBtraction is also known as AND NOT More... | |
bm::bvector< Alloc > & | bit_or (const bm::bvector< Alloc > &bv) |
2 operand logical OR More... | |
bm::bvector< Alloc > & | bit_and (const bm::bvector< Alloc > &bv) |
2 operand logical AND More... | |
bm::bvector< Alloc > & | bit_xor (const bm::bvector< Alloc > &bv) |
2 operand logical XOR More... | |
bm::bvector< Alloc > & | bit_sub (const bm::bvector< Alloc > &bv) |
2 operand logical SUB(AND NOT). Also known as MINUS. More... | |
bvector< Alloc > & | invert () |
Invert/NEG all bits It should be noted, invert is affected by size() if size is set - it only inverts [0..size-1] bits. More... | |
void | combine_operation (const bm::bvector< Alloc > &bvect, bm::operation opcode) |
perform a set-algebra operation by operation code More... | |
void | combine_operation_or (const bm::bvector< Alloc > &bvect) |
perform a set-algebra operation OR More... | |
void | combine_operation_and (const bm::bvector< Alloc > &bvect) |
perform a set-algebra operation AND More... | |
void | combine_operation_sub (const bm::bvector< Alloc > &bvect) |
perform a set-algebra operation MINUS (AND NOT) More... | |
void | combine_operation_xor (const bm::bvector< Alloc > &bvect) |
perform a set-algebra operation XOR More... | |
Iterator-traversal methods | |
| |
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 (size_type pos) const |
Returns enumerator pointing on specified or the next available bit. More... | |
Memory management and compression | |
| |
void | calc_stat (struct bm::bvector< Alloc >::statistics *st) const |
Calculates bitvector statistics. 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... | |
Comparison | |
| |
int | compare (const bvector< Alloc > &bvect) const |
Lexicographical comparison with a bitvector. More... | |
Friends | |
class | iterator_base |
class | enumerator |
template<class BV > | |
class | aggregator |
Open internals | |
void | combine_operation_with_block (block_idx_type nb, const bm::word_t *arg_blk, bool arg_gap, bm::operation opcode) |
const blocks_manager_type & | get_blocks_manager () const |
get access to memory manager (internal) Use only if you are BitMagic library More... | |
blocks_manager_type & | get_blocks_manager () |
get access to memory manager (internal) Use only if you are BitMagic library More... | |
static void | throw_bad_alloc () |
void | sync_size () |
Syncronize size if it got extended due to bulk import. More... | |
void | import (const size_type *ids, size_type ids_size, bm::sort_order sorted_idx) |
Import integers (set bits). More... | |
void | import_block (const size_type *ids, block_idx_type nblock, size_type start, size_type stop) |
Bitvector Bit-vector container with runtime compression of bits.
typedef allocator_type::allocator_pool_type bm::bvector< Alloc >::allocator_pool_type |
typedef Alloc bm::bvector< Alloc >::allocator_type |
typedef blocks_manager_type::block_idx_type bm::bvector< Alloc >::block_idx_type |
typedef rs_index<allocator_type> bm::bvector< Alloc >::blocks_count |
typedef blocks_manager<Alloc> bm::bvector< Alloc >::blocks_manager_type |
typedef bool bm::bvector< Alloc >::const_reference |
typedef rs_index<allocator_type> bm::bvector< Alloc >::rs_index_type |
typedef bm::id_t bm::bvector< Alloc >::size_type |
enum bm::bvector::optmode |
Optimization mode Every next level means additional checks (better compression vs time)
Enumerator | |
---|---|
opt_none | no optimization |
opt_free_0 | Free unused 0 blocks. |
opt_free_01 | Free unused 0 and 1 blocks. |
opt_compress | compress blocks when possible (GAP/prefix sum) |
|
inline |
Constructs bvector class.
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 |
|
alloc | - alllocator for this instance |
|
inline |
|
inline |
|
inline |
Copy constructor for range copy [left..right].
|
inline |
|
inline |
|
inline |
bool bm::bvector< Alloc >::any |
Returns true if any bits in this bitset are set, and otherwise returns false.
Definition at line 2534 of file bm.h.
Referenced by DNA_FingerprintScanner::Find(), and bm::bvector<>::none().
|
inline |
bm::bvector< Alloc > & bm::bvector< Alloc >::bit_and | ( | const bm::bvector< Alloc > & | bv1, |
const bm::bvector< Alloc > & | bv2, | ||
typename bm::bvector< Alloc >::optmode | opt_mode | ||
) |
3-operand AND : this := bv1 AND bv2
bv1 | - Argument vector 1 |
bv2 | - Argument vector 2 |
opt_mode | - optimization compression (when it is performed on the fly it is faster than a separate call to optimize() |
Definition at line 4927 of file bm.h.
Referenced by DemoAND(), bm::sparse_vector< unsigned, bm::bvector<> >::filter(), bm::operator&(), and bm::bvector<>::operator&=().
|
inline |
bm::bvector< Alloc > & bm::bvector< Alloc >::bit_or | ( | const bm::bvector< Alloc > & | bv1, |
const bm::bvector< Alloc > & | bv2, | ||
typename bm::bvector< Alloc >::optmode | opt_mode | ||
) |
3-operand OR : this := bv1 OR bv2
bv1 | - Argument vector 1 |
bv2 | - Argument vector 2 |
opt_mode | - optimization compression (when it is performed on the fly it is faster than a separate call to optimize() |
Definition at line 4742 of file bm.h.
Referenced by DemoOR(), bm::dynamic_range_clip_high(), bm::dynamic_range_clip_low(), main(), bm::operator|(), and bm::bvector<>::operator|=().
|
inline |
bm::bvector< Alloc > & bm::bvector< Alloc >::bit_sub | ( | const bm::bvector< Alloc > & | bv1, |
const bm::bvector< Alloc > & | bv2, | ||
typename bm::bvector< Alloc >::optmode | opt_mode | ||
) |
3-operand SUB : this := bv1 MINUS bv2 SUBtraction is also known as AND NOT
bv1 | - Argument vector 1 |
bv2 | - Argument vector 2 |
opt_mode | - optimization compression (when it is performed on the fly it is faster than a separate call to optimize() |
Definition at line 5021 of file bm.h.
Referenced by DemoSUB(), bm::operator-(), and bm::bvector<>::operator-=().
|
inline |
bm::bvector< Alloc > & bm::bvector< Alloc >::bit_xor | ( | const bm::bvector< Alloc > & | bv1, |
const bm::bvector< Alloc > & | bv2, | ||
typename bm::bvector< Alloc >::optmode | opt_mode | ||
) |
3-operand XOR : this := bv1 XOR bv2
bv1 | - Argument vector 1 |
bv2 | - Argument vector 2 |
opt_mode | - optimization compression (when it is performed on the fly it is faster than a separate call to optimize() |
Definition at line 4829 of file bm.h.
Referenced by DemoXOR(), bm::operator^(), and bm::bvector<>::operator^=().
void bm::bvector< Alloc >::build_rs_index | ( | rs_index_type * | rs_idx, |
bvector< Alloc > * | bv_blocks = 0 |
||
) | const |
compute running total of all blocks in bit vector (rank-select index)
rs_idx | - [out] pointer to index / count structure |
bv_blocks | - [out] list of block ids in the vector (internal, optional) Function will fill full array of running totals |
Definition at line 2580 of file bm.h.
Referenced by bv_count_range_acc(), bv_count_to_acc(), and bv_count_to_range_acc().
void bm::bvector< Alloc >::calc_stat | ( | struct bm::bvector< Alloc >::statistics * | st | ) | const |
Calculates bitvector statistics.
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.
Definition at line 3354 of file bm.h.
Referenced by calc_memory_footprint(), convert_bv2bvs(), generate_bvector(), and print_statistics().
|
inline |
|
inline |
void bm::bvector< Alloc >::clear | ( | const size_type * | ids, |
size_type | ids_size, | ||
bm::sort_order | so = bm::BM_UNKNOWN |
||
) |
clear list of bits in this bitset
This is equivalent of AND NOT (Set Substract), argument set as an array.
ids | - pointer on array of indexes to set |
ids_size | - size of the input (ids) |
so | - sort order (use BM_SORTED for faster load) |
Definition at line 3504 of file bm.h.
Referenced by bm::bvector<>::build_rs_index(), bv_count_and(), DemoSUB(), main(), bm::bvector<>::reset(), speed_test_bv_index(), speed_test_bvs_index(), speed_test_sv_index(), and speed_test_vect_index().
|
inline |
|
inline |
Clears bit n without precondiion checks.
n | - bit's index to be cleaned. |
Definition at line 1606 of file bm.h.
Referenced by bm::basic_bmatrix< bm::bvector<> >::set_octet(), and bm::sparse_vector< unsigned, bm::bvector<> >::set_value_no_null().
void bm::bvector< Alloc >::combine_operation | ( | const bm::bvector< Alloc > & | bvect, |
bm::operation | opcode | ||
) |
void bm::bvector< Alloc >::combine_operation_and | ( | const bm::bvector< Alloc > & | bvect | ) |
perform a set-algebra operation AND
Definition at line 5283 of file bm.h.
Referenced by bm::bvector<>::bit_and().
void bm::bvector< Alloc >::combine_operation_or | ( | const bm::bvector< Alloc > & | bvect | ) |
perform a set-algebra operation OR
Definition at line 5116 of file bm.h.
Referenced by bm::bvector<>::bit_or().
void bm::bvector< Alloc >::combine_operation_sub | ( | const bm::bvector< Alloc > & | bvect | ) |
perform a set-algebra operation MINUS (AND NOT)
Definition at line 5370 of file bm.h.
Referenced by bm::bvector<>::bit_sub().
void bm::bvector< Alloc >::combine_operation_with_block | ( | block_idx_type | nb, |
const bm::word_t * | arg_blk, | ||
bool | arg_gap, | ||
bm::operation | opcode | ||
) |
void bm::bvector< Alloc >::combine_operation_xor | ( | const bm::bvector< Alloc > & | bvect | ) |
perform a set-algebra operation XOR
Definition at line 5188 of file bm.h.
Referenced by bm::bvector<>::bit_xor().
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.
Definition at line 3224 of file bm.h.
Referenced by convert_bv2bvs(), fingerprint_compare(), main(), bm::bvector<>::operator!=(), bm::bvector<>::operator<(), bm::bvector<>::operator<=(), bm::bvector<>::operator==(), bm::bvector<>::operator>(), bm::bvector<>::operator>=(), and run_benchmark().
void bm::bvector< Alloc >::copy_range | ( | const bvector< Alloc > & | bvect, |
size_type | left, | ||
size_type | right | ||
) |
Copy all bits in the specified closed interval [left,right].
bvect | - source bit-vector |
left | - interval start |
right | - interval end (closed interval) |
Definition at line 6560 of file bm.h.
Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::copy_range(), and bm::sparse_vector< unsigned, bm::bvector<> >::extract().
bvector< Alloc >::size_type bm::bvector< Alloc >::count |
population cout (count of ON bits)
Definition at line 2487 of file bm.h.
Referenced by bv_count_test(), convert_bv2vect(), main(), pre_heat(), print_bvector(), print_statistics(), bm::bvector<>::recalc_count(), run_benchmark(), and serialize_bvector().
bvector< Alloc >::block_idx_type bm::bvector< Alloc >::count_blocks | ( | unsigned * | arr | ) | const |
bvector< Alloc >::size_type bm::bvector< Alloc >::count_range | ( | size_type | left, |
size_type | right | ||
) | const |
bvector< Alloc >::size_type bm::bvector< Alloc >::count_range | ( | size_type | left, |
size_type | right, | ||
const rs_index_type & | rs_idx | ||
) | const |
Returns count of 1 bits in the given range [left..right] Uses rank-select index to accelerate the search.
left | - index of first bit start counting from |
right | - index of last bit |
rs_idx | - block count structure to accelerate search |
Definition at line 3029 of file bm.h.
Referenced by bv_count_range(), and bv_count_range_acc().
bvector< Alloc >::size_type bm::bvector< Alloc >::count_to | ( | size_type | n, |
const rs_index_type & | rs_idx | ||
) | const |
Returns count of 1 bits (population) in [0..right] range.
This operation is also known as rank of bit N.
n | - index of bit to rank |
rs_idx | - rank-select to accelerate search should be prepared using build_rs_index |
Definition at line 2826 of file bm.h.
Referenced by bv_count_to_acc(), bv_count_to_range_acc(), and bm::bvector<>::rank().
bvector< Alloc >::size_type bm::bvector< Alloc >::count_to_test | ( | size_type | n, |
const rs_index_type & | blocks_cnt | ||
) | const |
popcount in [0..right] range if test(right) == true
This is conditional rank operation, which is faster than test() plus count_to()
n | - index of bit to test and rank |
blocks_cnt | - block count structure to accelerate search should be prepared using running_count_blocks |
|
inline |
Returns enumerator pointing on the next bit after the last.
Definition at line 2128 of file bm.h.
Referenced by combine_or_test(), main(), speed_test_sv_index(), and speed_test_vect_index().
void bm::bvector< Alloc >::erase | ( | size_type | n | ) |
|
inline |
bool bm::bvector< Alloc >::find | ( | size_type & | pos | ) | const |
Finds index of first 1 bit.
pos | - index of the found 1 bit |
Definition at line 3969 of file bm.h.
Referenced by main().
bool bm::bvector< Alloc >::find | ( | size_type | from, |
size_type & | pos | ||
) | const |
Finds index of 1 bit starting from position.
from | - position to start search from |
pos | - index of the found 1 bit |
bool bm::bvector< Alloc >::find_range | ( | size_type & | first, |
size_type & | last | ||
) | const |
Finds dynamic range of bit-vector [first, last].
first | - index of the first found 1 bit |
last | - index of the last found 1 bit |
Definition at line 4015 of file bm.h.
Referenced by main().
bool bm::bvector< Alloc >::find_rank | ( | size_type | rank, |
size_type | from, | ||
size_type & | pos | ||
) | const |
Find bit-vector position for the specified rank(bitcount)
Rank based search, counts number of 1s from specified position until finds the ranked position relative to start from position. In other words: range population count between from and pos == rank.
rank | - rank to find (bitcount) |
from | - start positioon for rank search |
pos | - position with speciefied rank (relative to from position) |
bool bm::bvector< Alloc >::find_rank | ( | size_type | rank, |
size_type | from, | ||
size_type & | pos, | ||
const rs_index_type & | rs_idx | ||
) | const |
Find bit-vector position for the specified rank(bitcount)
Rank based search, counts number of 1s from specified position until finds the ranked position relative to start from position. In other words: range population count between from and pos == rank.
rank | - rank to find (bitcount) |
from | - start positioon for rank search |
pos | - position with speciefied rank (relative to from position) |
blocks_cnt | - block count structure to accelerate rank search should be prepared using build_rs_index |
bool bm::bvector< Alloc >::find_reverse | ( | size_type & | pos | ) | const |
Finds last index of 1 bit.
pos | - index of the last found 1 bit |
Definition at line 3914 of file bm.h.
Referenced by bm::bvector<>::clear(), bm::bvector<>::keep(), and main().
|
inline |
Returns enumerator pointing on the first non-zero bit.
Definition at line 2122 of file bm.h.
Referenced by bv2delta(), bv_counted_enumerator(), convert_bv2sv(), convert_bv2vect(), generate_random_subset(), main(), print_bvector(), print_sorted(), speed_test_bv_index(), speed_test_bvs_index(), speed_test_sv_index(), speed_test_vect_index(), and DNA_FingerprintScanner::TranslateResults().
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Get curent allocator pool (if set)
Definition at line 1453 of file bm.h.
Referenced by bm::bvector< Alloc >::mem_pool_guard::assign_if_not_set().
bool bm::bvector< Alloc >::get_bit | ( | size_type | n | ) | const |
returns true if bit n is set and false is bit n is 0.
n | - Index of the bit to check. |
Definition at line 3102 of file bm.h.
Referenced by bm::bvector<>::operator[](), and bm::bvector<>::test().
|
inline |
|
inline |
get access to memory manager (internal) Use only if you are BitMagic library
Definition at line 2239 of file bm.h.
Referenced by bm::bvector<>::bit_and(), bm::bvector<>::bit_or(), bm::bvector<>::bit_sub(), and bm::bvector<>::bit_xor().
|
inline |
Returns enumerator pointing on specified or the next available bit.
Definition at line 2134 of file bm.h.
Referenced by bm::bvector<>::first().
|
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
Definition at line 1888 of file bm.h.
Referenced by bm::bvector_mini< A >::compare(), and print_bvector().
|
inline |
Returns blocks allocation strategy.
|
inline |
Finds the number of the next bit ON.
prev | - Index of the previously found bit. |
Definition at line 1897 of file bm.h.
Referenced by bm::bvector_mini< A >::compare(), and print_bvector().
|
protected |
Import integers (set bits).
(Fast, no checks).
Definition at line 3592 of file bm.h.
Referenced by bm::bvector<>::clear(), bm::bvector< Alloc >::bulk_insert_iterator::flush(), bm::bvector<>::keep(), and bm::bvector< Alloc >::bulk_insert_iterator::operator=().
|
protected |
bool bm::bvector< Alloc >::inc | ( | size_type | n | ) |
Increment the specified element.
Bit increment rules: 0 + 1 = 1 (no carry over) 1 + 1 = 0 (with carry over returned)
n | - index of the bit to be set |
Definition at line 3736 of file bm.h.
Referenced by bm::bvector<>::flip(), and bm::sparse_vector< unsigned, bm::bvector<> >::inc().
void bm::bvector< Alloc >::init |
Explicit post-construction initialization.
Definition at line 2427 of file bm.h.
Referenced by bm::bvector<>::build_rs_index(), bm::bvector< Alloc >::bulk_insert_iterator::bulk_insert_iterator(), bv_set_bit_no_check_test(), bm::bvector<>::bvector(), bm::bvector< Alloc >::insert_iterator::insert_iterator(), bm::basic_bmatrix< bm::bvector<> >::insert_octet(), load_snp_report(), main(), run_benchmark(), bm::basic_bmatrix< bm::bvector<> >::set_octet(), and vector_search().
bool bm::bvector< Alloc >::insert | ( | size_type | n, |
bool | value | ||
) |
Insert bit into specified position All the vector content after insert position is shifted right.
n | - index of the bit to insert |
value | - insert value |
Definition at line 4311 of file bm.h.
Referenced by bm::basic_bmatrix< bm::bvector<> >::insert_octet(), and bm::sparse_vector< unsigned, bm::bvector<> >::insert_value_no_null().
|
inline |
bvector< Alloc > & bm::bvector< Alloc >::invert |
Invert/NEG all bits It should be noted, invert is affected by size() if size is set - it only inverts [0..size-1] bits.
Definition at line 3055 of file bm.h.
Referenced by DemoINV(), bm::bvector<>::flip(), and bm::bvector<>::operator~().
void bm::bvector< Alloc >::keep | ( | const size_type * | ids, |
size_type | ids_size, | ||
bm::sort_order | so = bm::BM_UNKNOWN |
||
) |
Keep list of bits in this bitset, others are cleared.
This is equivalent of AND (Set Intersect), argument set as an array.
ids | - pointer on array of indexes to set |
ids_size | - size of the input (ids) |
so | - sort order (use BM_SORTED for faster load) |
Definition at line 3476 of file bm.h.
Referenced by DemoAND().
void bm::bvector< Alloc >::merge | ( | bm::bvector< Alloc > & | bvect | ) |
Merge/move content from another vector.
Merge performs a logical OR operation, but the source vector is not immutable. Source content gets destroyed (memory moved) to create a union of two vectors. Merge operation can be more efficient than OR if argument is a temporary vector.
bvect | - [in, out] - source vector (NOT immutable) |
Definition at line 4657 of file bm.h.
Referenced by DemoOR(), and bm::sparse_vector< unsigned, bm::bvector<> >::merge().
void bm::bvector< Alloc >::move_from | ( | bvector< Alloc > & | bvect | ) |
Move bvector content from another bvector.
Definition at line 2436 of file bm.h.
Referenced by bm::bvector<>::operator=().
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
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
Definition at line 3136 of file bm.h.
Referenced by generate_bvector(), main(), make_BLOB(), bm::basic_bmatrix< bm::bvector<> >::optimize(), serialize_bvector(), speed_test_bv_index(), speed_test_bvs_index(), speed_test_sv_index(), and speed_test_vect_index().
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 3182 of file bm.h.
Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::optimize_gap_size().
|
inline |
Returns rank of specified bit position.
n | - index of bit to rank |
rs_idx | - rank-select index |
Definition at line 1749 of file bm.h.
Referenced by bm::bvector< Alloc >::enumerator::skip(), and bm::bvector< Alloc >::enumerator::skip_to_rank().
|
inline |
|
inline |
Clears every bit in the bitvector.
Definition at line 1623 of file bm.h.
Referenced by bv_set_bit_test(), and generate_test_set().
void bm::bvector< Alloc >::resize | ( | size_type | new_size | ) |
Change size of the bvector.
new_size | - new size in bits |
Definition at line 2546 of file bm.h.
Referenced by bm::bvector<>::clear(), convert_bv2sv(), DemoAND(), DemoINV(), DemoOR(), DemoSUB(), DemoXOR(), bm::bvector<>::keep(), bm::bvector< Alloc >::insert_iterator::operator=(), bm::bvector<>::operator=(), bm::bvector<>::operator[](), and pick_benchmark_set().
bool bm::bvector< Alloc >::select | ( | size_type | rank, |
size_type & | pos, | ||
const rs_index_type & | rs_idx | ||
) | const |
select bit-vector position for the specified rank(bitcount)
Rank based search, counts number of 1s from specified position until finds the ranked position relative to start from position. Uses In other words: range population count between from and pos == rank.
rank | - rank to find (bitcount) |
pos | - position with speciefied rank (relative to from position) [out] |
rs_idx | - block count structure to accelerate rank search |
Definition at line 4158 of file bm.h.
Referenced by main().
bvector< Alloc > & bm::bvector< Alloc >::set |
void bm::bvector< Alloc >::set | ( | const size_type * | ids, |
size_type | ids_size, | ||
bm::sort_order | so = bm::BM_UNKNOWN |
||
) |
Set list of bits in this bitset to 1.
Method implements optimized bulk setting of multiple bits at once. The best results are achieved when the imput comes sorted. This is equivalent of OR (Set Union), argument set as an array.
ids | - pointer on array of indexes to set |
ids_size | - size of the input (ids) |
so | - sort order (use BM_SORTED for faster load) |
bvector< Alloc > & bm::bvector< Alloc >::set | ( | size_type | n, |
bool | val = true |
||
) |
Sets bit n if val is true, clears bit n if val is false.
n | - index of the bit to be set |
val | - new bit value |
Definition at line 3539 of file bm.h.
Referenced by bm::bvector<>::build_rs_index(), bvector_bulk_set_test(), bm::sparse_vector< unsigned, bm::bvector<> >::clear(), DemoOR(), fill_bvector(), generate_bvector(), bm::sparse_vector< unsigned, bm::bvector<> >::import(), main(), pick_benchmark_set(), and run_benchmark().
|
inline |
Set allocator pool for local (non-threaded) memory cyclic(lots of alloc-free ops) opertations.
Definition at line 1448 of file bm.h.
Referenced by bm::bvector< Alloc >::mem_pool_guard::assign_if_not_set(), bm::sparse_vector< unsigned, bm::bvector<> >::extract(), and bm::bvector< Alloc >::mem_pool_guard::mem_pool_guard().
bool bm::bvector< Alloc >::set_bit | ( | size_type | n, |
bool | val = true |
||
) |
Sets bit n.
n | - index of the bit to be set. |
val | - new bit value |
Definition at line 3575 of file bm.h.
Referenced by bv_set_bit_test(), bm::bvector<>::clear_bit(), fill_bvector(), and generate_random_vector().
bool bm::bvector< Alloc >::set_bit_and | ( | size_type | n, |
bool | val = true |
||
) |
bool bm::bvector< Alloc >::set_bit_conditional | ( | size_type | n, |
bool | val, | ||
bool | condition | ||
) |
void bm::bvector< Alloc >::set_bit_no_check | ( | size_type | 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.
n | - bit number |
Definition at line 3425 of file bm.h.
Referenced by bv_set_bit_no_check_test(), bm::bvector<>::bvector(), bm::bvector<>::clear_bit_no_check(), bm::sparse_vector< unsigned, bm::bvector<> >::inc(), bm::basic_bmatrix< bm::bvector<> >::insert_octet(), load_snp_report(), main(), bm::bvector< Alloc >::insert_iterator::operator=(), run_benchmark(), bm::basic_bmatrix< bm::bvector<> >::set_octet(), bm::sparse_vector< unsigned, bm::bvector<> >::set_value(), bm::sparse_vector< unsigned, bm::bvector<> >::set_value_no_null(), and vector_search().
void bm::bvector< Alloc >::set_gap_levels | ( | const gap_word_t * | glevel_len | ) |
|
inline |
bvector< Alloc > & bm::bvector< Alloc >::set_range | ( | size_type | left, |
size_type | 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.
left | - interval start |
right | - interval end (closed interval) |
value | - value to set interval in |
Definition at line 2451 of file bm.h.
Referenced by bv_count_and(), generate_bvector(), bm::sparse_vector< unsigned, bm::bvector<> >::import(), bm::sparse_vector< unsigned, bm::bvector<> >::join(), and bm::sparse_vector< unsigned, bm::bvector<> >::merge().
bool bm::bvector< Alloc >::shift_left |
bool bm::bvector< Alloc >::shift_right |
Shift right by 1 bit, fill with zero return carry out.
Definition at line 4293 of file bm.h.
Referenced by DNA_FingerprintScanner::Find().
|
inline |
return current size of the vector (bits)
Definition at line 1660 of file bm.h.
Referenced by bm::bvector< Alloc >::insert_iterator::operator=(), bm::bvector<>::operator=(), print_bvector(), and run_benchmark().
void bm::bvector< Alloc >::swap | ( | bvector< Alloc > & | bvect | ) |
|
protected |
Syncronize size if it got extended due to bulk import.
Definition at line 2567 of file bm.h.
Referenced by bm::bvector< Alloc >::bulk_insert_iterator::flush().
|
inline |
returns true if bit n is set and false is bit n is 0.
n | - Index of the bit to check. |
Definition at line 1798 of file bm.h.
Referenced by load_snp_report(), main(), and pick_benchmark_set().
|
static |
|
friend |
Definition at line 1234 of file bm.h.
Referenced by bm::bvector<>::end(), and bm::bvector<>::get_enumerator().
|
friend |