|
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 | 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 bvector_size_type | size_type |
| typedef bool | const_reference |
| typedef bm::alloc_pool_guard< allocator_pool_type, bvector< Alloc > > | mem_pool_guard |
| More... | |
| 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 (const bvector< Alloc > &bvect, bm::finalization is_final) | |
| Copy-constructor for mutable/immutable initialization. More... | |
| ~bvector () BMNOEXCEPT | |
| void | init () |
| Explicit post-construction initialization. Must be caled to make sure safe use of *_no_check() methods. More... | |
| bvector & | operator= (const bvector< Alloc > &bvect) |
| Copy assignment operator. More... | |
| bvector (bvector< Alloc > &&bvect) BMNOEXCEPT | |
| Move constructor. More... | |
| bvector (std::initializer_list< size_type > il) | |
| Brace constructor. More... | |
| bvector & | operator= (bvector< Alloc > &&bvect) BMNOEXCEPT |
| Move assignment operator. More... | |
| void | copy (const bvector< Alloc > &bvect, bm::finalization is_final) |
| Copy bvector from the argument bvector. More... | |
| void | move_from (bvector< Alloc > &bvect) BMNOEXCEPT |
| Move bvector content from another bvector. More... | |
| void | swap (bvector< Alloc > &bvect) BMNOEXCEPT |
| 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) |
| More... | |
| bool | operator[] (size_type n) const BMNOEXCEPT |
| More... | |
| void | operator&= (const bvector< Alloc > &bv) |
| More... | |
| void | operator^= (const bvector< Alloc > &bv) |
| More... | |
| void | operator|= (const bvector< Alloc > &bv) |
| More... | |
| void | operator-= (const bvector< Alloc > &bv) |
| More... | |
| bool | operator< (const bvector< Alloc > &bv) const |
| More... | |
| bool | operator<= (const bvector< Alloc > &bv) const |
| More... | |
| bool | operator> (const bvector< Alloc > &bv) const |
| More... | |
| bool | operator>= (const bvector< Alloc > &bv) const |
| More... | |
| bool | operator== (const bvector< Alloc > &bv) const BMNOEXCEPT |
| More... | |
| bool | operator!= (const bvector< Alloc > &bv) const BMNOEXCEPT |
| More... | |
| bvector< Alloc > | operator~ () const |
| More... | |
| Alloc | get_allocator () const |
| void | set_allocator_pool (allocator_pool_type *pool_ptr) BMNOEXCEPT |
| Set allocator pool for local (non-th readed) memory cyclic(lots of alloc-free ops) opertations. More... | |
| allocator_pool_type * | get_allocator_pool () BMNOEXCEPT |
| Get curent allocator pool (if set) More... | |
Read-only / immutable vector methods <br> | |
| void | freeze () |
| Turn current vector to read-only (immutable vector). More... | |
| bool | is_ro () const BMNOEXCEPT |
| Returns true if vector is read-only. More... | |
Bit access/modification methods <br> | |
| 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... | |
| bool | set_bit_no_check (size_type n, bool val) |
| Set specified 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 | clear_range (size_type left, size_type right) |
| Sets all bits to zero in the specified closed interval [left,right] Interval must be inside the bvector's size. This method DOES NOT resize vector. More... | |
| void | keep_range (size_type left, size_type right) |
| Sets all bits to zero outside of the closed interval [left,right] Expected result: 00000...0[left, right]0....0000. 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=true) BMNOEXCEPT |
| Clears every bit in the bitvector. More... | |
| bvector< Alloc > & | reset () BMNOEXCEPT |
| 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 () |
| More... | |
Size and capacity | |
By default bvector is dynamically sized, manual control methods available | |
| size_type | size () const BMNOEXCEPT |
| Returns bvector's capacity (number of bits it can store) More... | |
| void | resize (size_type new_size) |
| Change size of the bvector. More... | |
Population counting, ranks, ranges and intervals | |
| size_type | count () const BMNOEXCEPT |
| population count (count of ON bits) More... | |
| block_idx_type | count_blocks (unsigned *arr) const BMNOEXCEPT |
| 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 BMNOEXCEPT |
| 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 BMNOEXCEPT |
| Returns count of 1 bits in the given range [left..right]. More... | |
| size_type | count_range_no_check (size_type left, size_type right) const BMNOEXCEPT |
| More... | |
| size_type | count_range_no_check (size_type left, size_type right, const rs_index_type &rs_idx) const BMNOEXCEPT |
| More... | |
| bool | is_all_one_range (size_type left, size_type right) const BMNOEXCEPT |
| Returns true if all bits in the range are 1s (saturated interval) Function uses closed interval [left, right]. More... | |
| bool | any_range (size_type left, size_type right) const BMNOEXCEPT |
| Returns true if any bits in the range are 1s (non-empty interval) Function uses closed interval [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 BMNOEXCEPT |
| Returns count of 1 bits (population) in [0..right] range. More... | |
| size_type | rank (size_type n, const rs_index_type &rs_idx) const BMNOEXCEPT |
| Returns rank of specified bit position (same as count_to()) More... | |
| size_type | rank_corrected (size_type n, const rs_index_type &rs_idx) const BMNOEXCEPT |
| Returns rank corrceted by the requested border value (as -1) More... | |
| size_type | count_to_test (size_type n, const rs_index_type &rs_idx) const BMNOEXCEPT |
| popcount in [0..right] range if test(right) == true More... | |
| size_type | recalc_count () BMNOEXCEPT |
| More... | |
| void | forget_count () BMNOEXCEPT |
| More... | |
Bit access (read-only) <br> | |
| bool | get_bit (size_type n) const BMNOEXCEPT |
| returns true if bit n is set and false is bit n is 0. More... | |
| bool | test (size_type n) const BMNOEXCEPT |
| returns true if bit n is set and false is bit n is 0. More... | |
bit-shift and insert operations <br> | |
| 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 <br> | |
| bool | any () const BMNOEXCEPT |
| Returns true if any bits in this bitset are set, and otherwise returns false. More... | |
| bool | none () const BMNOEXCEPT |
| Returns true if no bits are set, otherwise returns false. More... | |
| bool | empty () const BMNOEXCEPT |
| Returns true if the set is empty (no bits are set, otherwise returns false) Please note that this is NOT a size check, it is an empty SET check (absense of 1s) More... | |
Scan and find bits and indexes | |
| bool | find (size_type &pos) const BMNOEXCEPT |
| Finds index of first 1 bit. More... | |
| bool | find (size_type from, size_type &pos) const BMNOEXCEPT |
| Find index of 1 bit starting from position. More... | |
| size_type | get_first () const BMNOEXCEPT |
| 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 BMNOEXCEPT |
| 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 BMNOEXCEPT |
| Finds last index of 1 bit. More... | |
| bool | find_reverse (size_type from, size_type &pos) const BMNOEXCEPT |
| Reverse finds next(prev) index of 1 bit. More... | |
| bool | find_range (size_type &first, size_type &last) const BMNOEXCEPT |
| Finds dynamic range of bit-vector [first, last]. More... | |
| bool | find_rank (size_type rank, size_type from, size_type &pos) const BMNOEXCEPT |
| 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 BMNOEXCEPT |
| 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 BMNOEXCEPT |
| select bit-vector position for the specified rank(bitcount) More... | |
Algebra of Sets operations <br> | |
| bm::bvector< Alloc > & | bit_or (const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode=opt_none) |
| 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=opt_none) |
| 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=opt_none) |
| 3-operand AND : this := bv1 AND bv2 More... | |
| bm::bvector< Alloc > & | bit_or_and (const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode=opt_none) |
| 3-operand AND where result is ORed into the terget vector : this |= bv1 AND bv2 TARGET := TARGET OR (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=opt_none) |
| 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, optmode opt_mode=opt_none) |
| 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, optmode opt_mode) |
| 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 <br> | |
| 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 <br> | |
| void | calc_stat (struct bm::bvector< Alloc >::statistics *st) const BMNOEXCEPT |
| Calculates bitvector statistics. More... | |
| void | set_new_blocks_strat (strategy strat) |
| Sets new blocks allocation strategy. More... | |
| strategy | get_new_blocks_strat () const BMNOEXCEPT |
| 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_range (size_type left, size_type right, bm::word_t *temp_block, optmode opt_mode=opt_compress) |
| 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... | |
| bool | is_init () const BMNOEXCEPT |
| Return true if bvector is initialized at all. More... | |
| void | fill_alloc_digest (bvector< Alloc > &bv_blocks) const |
| Calculate blocks digest vector (for diagnostics purposes) 1 is added if NB is a real, allocated block. More... | |
Comparison <br> | |
| int | compare (const bvector< Alloc > &bvect) const BMNOEXCEPT |
| Lexicographical comparison with a bitvector. More... | |
| bool | equal (const bvector< Alloc > &bvect) const BMNOEXCEPT |
| Equal comparison with an agr bit-vector. More... | |
| bool | find_first_mismatch (const bvector< Alloc > &bvect, size_type &pos, size_type search_to=bm::id_max) const BMNOEXCEPT |
| Find index of first bit different between this and the agr vector. More... | |
Friends | |
| class | iterator_base |
| class | enumerator |
| More... | |
| template<class BV > | |
| class | aggregator |
| template<class BV > | |
| class | operation_deserializer |
| template<class BV , class DEC > | |
| class | deserializer |
Open internals <br> | |
| void | combine_operation_with_block (block_idx_type nb, const bm::word_t *arg_blk, bool arg_gap, bm::operation opcode) |
| More... | |
| const blocks_manager_type & | get_blocks_manager () const BMNOEXCEPT |
| get access to memory manager (internal) Use only if you are BitMagic library More... | |
| blocks_manager_type & | get_blocks_manager () BMNOEXCEPT |
| get access to memory manager (internal) Use only if you are BitMagic library More... | |
| void | import (const size_type *ids, size_type ids_size, bm::sort_order sorted_idx) |
| Import integers (set bits). More... | |
| void | import_sorted (const size_type *ids, const size_type ids_size, bool opt_flag) |
| Import sorted integers (set bits). More... | |
| void | set_range_no_check (size_type left, size_type right) |
| Set range without validity/bounds checking. More... | |
| void | clear_range_no_check (size_type left, size_type right) |
| Clear range without validity/bounds checking. More... | |
| static void | throw_bad_alloc () |
| void | sync_size () |
| Syncronize size if it got extended due to bulk import. More... | |
| void | import_block (const size_type *ids, block_idx_type nblock, size_type start, size_type stop) |
| More... | |
| size_type | check_or_next (size_type prev) const BMNOEXCEPT |
| More... | |
| bool | gap_block_set (bm::gap_word_t *gap_blk, bool val, block_idx_type nblock, unsigned nbit) |
| set bit in GAP block with GAP block length control More... | |
| void | gap_block_set_no_ret (bm::gap_word_t *gap_blk, bool val, block_idx_type nblock, unsigned nbit) |
| set bit in GAP block with GAP block length control More... | |
| size_type | check_or_next_extract (size_type prev) |
| check if specified bit is 1, and set it to 0 if specified bit is 0, scan for the next 1 and returns it if no 1 found returns 0 More... | |
| bool | and_bit_no_check (size_type n, bool val) |
| AND specified bit without checking preconditions (size, etc) More... | |
| bool | set_bit_conditional_impl (size_type n, bool val, bool condition) |
| More... | |
| void | combine_operation_with_block (block_idx_type nb, bool gap, bm::word_t *blk, const bm::word_t *arg_blk, bool arg_gap, bm::operation opcode) |
| More... | |
| bool | combine_operation_block_or (unsigned i, unsigned j, const bm::word_t *arg_blk1, const bm::word_t *arg_blk2) |
| More... | |
| bool | combine_operation_block_xor (unsigned i, unsigned j, const bm::word_t *arg_blk1, const bm::word_t *arg_blk2) |
| More... | |
| bool | combine_operation_block_and (unsigned i, unsigned j, const bm::word_t *arg_blk1, const bm::word_t *arg_blk2) |
| More... | |
| bool | combine_operation_block_and_or (unsigned i, unsigned j, const bm::word_t *arg_blk1, const bm::word_t *arg_blk2) |
| More... | |
| bool | combine_operation_block_sub (unsigned i, unsigned j, const bm::word_t *arg_blk1, const bm::word_t *arg_blk2) |
| More... | |
| void | combine_operation_block_or (unsigned i, unsigned j, bm::word_t *blk, const bm::word_t *arg_blk) |
| More... | |
| void | combine_operation_block_xor (unsigned i, unsigned j, bm::word_t *blk, const bm::word_t *arg_blk) |
| More... | |
| void | combine_operation_block_and (unsigned i, unsigned j, bm::word_t *blk, const bm::word_t *arg_blk) |
| More... | |
| void | combine_operation_block_sub (unsigned i, unsigned j, bm::word_t *blk, const bm::word_t *arg_blk) |
| More... | |
| void | copy_range_no_check (const bvector< Alloc > &bvect, size_type left, size_type right) |
| More... | |
Bitvector Bit-vector container with runtime compression of bits.
| 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].
Definition at line 877 of file bm.h.
References bm::bvector< Alloc >::copy_range_no_check(), and bm::xor_swap().
|
inline |
Copy-constructor for mutable/immutable initialization.
Definition at line 892 of file bm.h.
References bm::READONLY.
|
inline |
|
inline |
Brace constructor.
Definition at line 936 of file bm.h.
References bm::bvector< Alloc >::init(), and bm::bvector< Alloc >::set_bit_no_check().
|
protected |
AND specified bit without checking preconditions (size, etc)
Definition at line 4598 of file bm.h.
References BM_ASSERT, BMGAP_PTR, bm::bvector< Alloc >::gap_block_set(), bm::gap_test_unr(), bm::bvector< Alloc >::get_new_blocks_strat(), bm::bvector< Alloc >::is_ro(), IS_VALID_ADDR, bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::bvector< Alloc >::set_bit_and().
| bool bm::bvector< Alloc >::any |
Returns true if any bits in this bitset are set, and otherwise returns false.
Definition at line 2416 of file bm.h.
References bm::for_each_nzblock_if().
Referenced by bm::bvector< Alloc >::empty(), DNA_FingerprintScanner::Find(), main(), bm::bvector< Alloc >::none(), and resolve_duplicates().
| bool bm::bvector< Alloc >::any_range | ( | size_type | left, |
| size_type | right | ||
| ) | const |
Returns true if any bits in the range are 1s (non-empty interval) Function uses closed interval [left, right].
| left | - index of first bit start checking |
| right | - index of last bit |
Definition at line 3387 of file bm.h.
References bm::block_any(), bm::block_any_range(), BM_ASSERT, FULL_BLOCK_FAKE_ADDR, bm::gap_max_bits, bm::get_block_coord(), bm::id_max, bm::set_block_mask, bm::set_block_shift, bm::set_sub_array_size, bm::bvector< Alloc >::test(), and bm::xor_swap().
Referenced by add_object(), and main().
|
inline |
2 operand logical AND
| bv | - argument vector |
| opt_mode | - set an immediate optimization |
Definition at line 1780 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::combine_operation_and(), and bm::bvector< Alloc >::is_ro().
| 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 = opt_none |
||
| ) |
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 5880 of file bm.h.
References bm::bvector< Alloc >::bit_and(), BM_ASSERT, bm::bvector< Alloc >::combine_operation_block_and(), FULL_BLOCK_FAKE_ADDR, FULL_SUB_BLOCK_REAL_ADDR, bm::bvector< Alloc >::get_blocks_manager(), bm::bvector< Alloc >::is_ro(), bm::bvector< Alloc >::opt_compress, bm::bvector< Alloc >::opt_none, and bm::set_sub_array_size.
Referenced by bm::bvector< Alloc >::bit_and(), bm::bvector< Alloc >::bit_or_and(), DemoAND(), bm::bvector< Alloc >::keep(), main(), bm::operator&(), bm::bvector< Alloc >::operator&=(), and resolve_duplicates().
|
inline |
2 operand logical OR
| bv | - Argument vector. |
Definition at line 1768 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::combine_operation_or(), and bm::bvector< Alloc >::is_ro().
| 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 = opt_none |
||
| ) |
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 5668 of file bm.h.
References bm::bvector< Alloc >::bit_or(), BM_ASSERT, bm::bvector< Alloc >::combine_operation_block_or(), FULL_BLOCK_FAKE_ADDR, bm::bvector< Alloc >::get_blocks_manager(), bm::bvector< Alloc >::is_ro(), bm::bvector< Alloc >::opt_compress, bm::bvector< Alloc >::opt_none, and bm::set_sub_array_size.
Referenced by bm::bvector< Alloc >::bit_or(), bm::bvector< Alloc >::bit_or_and(), bm::bvector< Alloc >::bit_sub(), DemoOR(), bm::dynamic_range_clip_high(), bm::dynamic_range_clip_low(), main(), bm::bvector< Alloc >::merge(), bm::operator|(), bm::bvector< Alloc >::operator|=(), and bm::sparse_vector_find_mismatch().
| bm::bvector< Alloc > & bm::bvector< Alloc >::bit_or_and | ( | const bm::bvector< Alloc > & | bv1, |
| const bm::bvector< Alloc > & | bv2, | ||
| typename bm::bvector< Alloc >::optmode | opt_mode = opt_none |
||
| ) |
3-operand AND where result is ORed into the terget vector : this |= bv1 AND bv2 TARGET := TARGET OR (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 5975 of file bm.h.
References bm::bvector< Alloc >::bit_and(), bm::bvector< Alloc >::bit_or(), BM_ASSERT, bm::bvector< Alloc >::combine_operation_block_and(), bm::bvector< Alloc >::combine_operation_block_and_or(), FULL_BLOCK_FAKE_ADDR, FULL_SUB_BLOCK_REAL_ADDR, bm::bvector< Alloc >::get_blocks_manager(), bm::bvector< Alloc >::is_ro(), bm::bvector< Alloc >::opt_compress, bm::bvector< Alloc >::opt_none, and bm::set_sub_array_size.
Referenced by DemoAND_OR().
|
inline |
2 operand logical SUB(AND NOT). Also known as MINUS.
| bv | - argument vector. |
Definition at line 1803 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::combine_operation_sub(), and bm::bvector< Alloc >::is_ro().
| 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 = opt_none |
||
| ) |
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 6092 of file bm.h.
References bm::bvector< Alloc >::bit_or(), bm::bvector< Alloc >::bit_sub(), BM_ASSERT, bm::bvector< Alloc >::combine_operation_block_sub(), FULL_BLOCK_FAKE_ADDR, FULL_SUB_BLOCK_REAL_ADDR, bm::bvector< Alloc >::get_blocks_manager(), bm::bvector< Alloc >::is_ro(), bm::bvector< Alloc >::opt_compress, bm::bvector< Alloc >::opt_none, and bm::set_sub_array_size.
Referenced by bm::bvector< Alloc >::bit_sub(), bm::bvector< Alloc >::clear(), DemoSUB(), main(), bm::operator-(), and bm::bvector< Alloc >::operator-=().
|
inline |
2 operand logical XOR
| bv | - argument vector. |
Definition at line 1792 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::combine_operation_xor(), and bm::bvector< Alloc >::is_ro().
| 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 = opt_none |
||
| ) |
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 5767 of file bm.h.
References bm::bvector< Alloc >::bit_xor(), BM_ASSERT, bm::bvector< Alloc >::combine_operation_block_xor(), FULL_BLOCK_FAKE_ADDR, FULL_SUB_BLOCK_REAL_ADDR, bm::bvector< Alloc >::get_blocks_manager(), bm::bvector< Alloc >::is_ro(), bm::bvector< Alloc >::opt_compress, bm::bvector< Alloc >::opt_none, and bm::set_sub_array_size.
Referenced by bm::bvector< Alloc >::bit_xor(), DemoXOR(), bm::operator^(), bm::bvector< Alloc >::operator^=(), and bm::sparse_vector_find_mismatch().
| 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 2466 of file bm.h.
References bm::bit_block_calc_count_range(), bm::bit_block_calc_count_to(), BLOCK_ADDR_SAN, BM_ASSERT, BM_IS_GAP, BMGAP_PTR, bm::bvector< Alloc >::clear(), bm::bvector< Alloc >::find_reverse(), FULL_BLOCK_FAKE_ADDR, bm::gap_bfind(), bm::gap_bit_count_range(), bm::gap_bit_count_to(), bm::gap_max_bits, bm::get_block_coord(), bm::bvector< Alloc >::init(), bm::rs3_border0, bm::rs3_border0_1, bm::rs3_border1, bm::rs3_border1_1, bm::bvector< Alloc >::set_bit_no_check(), bm::set_block_shift, bm::bvector< Alloc >::set_range_no_check(), and bm::set_sub_array_size.
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 3943 of file bm.h.
References BM_ASSERT, BM_IS_GAP, BMGAP_PTR, bm::find_not_null_ptr(), FULL_BLOCK_FAKE_ADDR, bm::gap_capacity(), bm::gap_length(), bm::gap_level(), bm::gap_levels, bm::bvector< Alloc >::is_ro(), IS_VALID_ADDR, bm::set_block_size, and bm::set_sub_array_size.
Referenced by calc_memory_footprint(), convert_bv2bvs(), generate_bvector(), bm::bvector< Alloc >::optimize(), bm::bvector< Alloc >::optimize_gap_size(), and print_statistics().
|
protected |
Definition at line 5086 of file bm.h.
References bm::bit_block_find(), bm::bit_find_first(), bm::bits_in_array, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, FULL_SUB_BLOCK_REAL_ADDR, bm::gap_block_find(), bm::gap_find_first(), bm::gap_max_bits, bm::get_block_coord(), bm::set_block_mask, bm::set_block_shift, and bm::set_sub_array_size.
Referenced by bm::bvector< Alloc >::check_or_next_extract(), bm::bvector< Alloc >::find(), bm::bvector< Alloc >::get_first(), and bm::bvector< Alloc >::get_next().
|
protected |
check if specified bit is 1, and set it to 0 if specified bit is 0, scan for the next 1 and returns it if no 1 found returns 0
Definition at line 5170 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::check_or_next(), bm::bvector< Alloc >::clear_bit_no_check(), and bm::bvector< Alloc >::is_ro().
Referenced by bm::bvector< Alloc >::extract_next().
| void bm::bvector< Alloc >::clear | ( | bool | free_mem = true | ) |
Clears every bit in the bitvector.
| free_mem | if "true" (default) bvector frees the memory, otherwise sets blocks to 0. |
Definition at line 4100 of file bm.h.
References BM_ASSERT, and bm::bvector< Alloc >::is_ro().
| 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 4114 of file bm.h.
References bm::bvector< Alloc >::bit_sub(), BM_ASSERT, bm::bvector< Alloc >::find_reverse(), bm::bvector< Alloc >::import(), bm::bvector< Alloc >::is_ro(), and bm::bvector< Alloc >::resize().
Referenced by bm::bvector< Alloc >::build_rs_index(), bv_count_and(), bm::bvector< Alloc >::combine_operation_and(), compute_seq_group_union(), bm::bvector< Alloc >::copy_range(), DemoSUB(), CSeqClusters::elect_leaders(), bm::bvector< Alloc >::keep(), main(), bm::bvector< Alloc >::reset(), speed_test_bv_index(), speed_test_bvs_index(), speed_test_sv_index(), speed_test_vect_index(), and CSeqClusters::union_all_groups().
|
inline |
Clears bit n.
| n | - bit's index to be cleaned. |
Definition at line 1225 of file bm.h.
References bm::bvector< Alloc >::set_bit().
| void bm::bvector< Alloc >::clear_bit_no_check | ( | size_type | n | ) |
Clears bit n without precondiion checks.
| n | - bit's index to be cleaned. |
Definition at line 4439 of file bm.h.
References BM_ASSERT, BM_ASSERT_THROW, BMGAP_PTR, bm::bvector< Alloc >::gap_block_set_no_ret(), bm::bvector< Alloc >::get_new_blocks_strat(), bm::id_max, bm::bvector< Alloc >::is_ro(), bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::bvector< Alloc >::check_or_next_extract().
|
inline |
Sets all bits to zero 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) |
Definition at line 1194 of file bm.h.
References bm::bvector< Alloc >::set_range().
Referenced by main().
| void bm::bvector< Alloc >::clear_range_no_check | ( | size_type | left, |
| size_type | right | ||
| ) |
Clear range without validity/bounds checking.
Definition at line 7666 of file bm.h.
References bm::bits_in_block, bm::BM_AND, BM_ASSERT, BM_IS_GAP, bm::bvector< Alloc >::combine_operation_with_block(), bm::get_block_coord(), bm::set_block_mask, and bm::set_block_shift.
Referenced by bm::bvector< Alloc >::copy_range_no_check(), bm::bvector< Alloc >::invert(), and bm::bvector< Alloc >::set_range().
| void bm::bvector< Alloc >::combine_operation | ( | const bm::bvector< Alloc > & | bvect, |
| bm::operation | opcode | ||
| ) |
perform a set-algebra operation by operation code
Definition at line 6512 of file bm.h.
References bm::BM_AND, BM_IS_GAP, bm::BM_SUB, bm::bvector< Alloc >::combine_operation_with_block(), bm::bvector< Alloc >::set_range(), and bm::set_sub_array_size.
Referenced by DemoAND(), DemoOR(), DemoSUB(), and DemoXOR().
| void bm::bvector< Alloc >::combine_operation_and | ( | const bm::bvector< Alloc > & | bvect, |
| optmode | opt_mode | ||
| ) |
perform a set-algebra operation AND
Definition at line 6360 of file bm.h.
References bm::avx2_test_all_zero_wave(), BM_AND_OP, bm::bvector< Alloc >::clear(), FULL_BLOCK_FAKE_ADDR, bm::set_sub_array_size, and bm::sse42_test_all_zero_wave().
Referenced by bm::bvector< Alloc >::bit_and().
|
protected |
Definition at line 7231 of file bm.h.
References bm::bit_block_and(), bm::bit_block_copy(), bm::bit_is_all_zero(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, BMSET_PTRGAP, bm::calc_block_digest0(), bm::bvector< Alloc >::empty(), bm::gap_and_to_bitset(), bm::gap_equiv_len, bm::gap_is_all_zero(), bm::gap_operation_and(), IS_FULL_BLOCK, bm::update_block_digest0(), and bm::word_bitcount64().
|
protected |
Definition at line 6789 of file bm.h.
References bm::bit_block_and_2way(), bm::bit_is_all_zero(), BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::gap_and_to_bitset(), bm::gap_equiv_len, and bm::gap_operation_and().
Referenced by bm::bvector< Alloc >::bit_and(), and bm::bvector< Alloc >::bit_or_and().
|
protected |
Definition at line 6874 of file bm.h.
References bm::bit_block_and_or_2way(), bm::bit_block_copy(), bm::bit_block_or(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, bm::bvector< Alloc >::combine_operation_block_or(), FULL_BLOCK_FAKE_ADDR, bm::gap_add_to_bitset(), bm::gap_and_to_bitset(), bm::gap_equiv_len, bm::gap_operation_and(), and bm::is_bits_one().
Referenced by bm::bvector< Alloc >::bit_or_and().
|
protected |
Definition at line 7048 of file bm.h.
References bm::bit_block_copy(), bm::bit_block_or(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::gap_add_to_bitset(), bm::gap_equiv_len, bm::gap_operation_or(), bm::is_bits_one(), and IS_FULL_BLOCK.
|
protected |
Definition at line 6634 of file bm.h.
References bm::bit_block_or_2way(), BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::gap_add_to_bitset(), bm::gap_equiv_len, and bm::gap_operation_or().
Referenced by bm::bvector< Alloc >::bit_or(), bm::bvector< Alloc >::combine_operation_block_and_or(), and bm::bvector< Alloc >::merge().
|
protected |
Definition at line 7335 of file bm.h.
References bm::bit_andnot_arr_ffmask(), bm::bit_is_all_zero(), bm::bit_operation_sub(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, bm::bvector< Alloc >::empty(), bm::gap_convert_to_bitset_smart(), bm::gap_equiv_len, bm::gap_max_bits, bm::gap_operation_sub(), bm::gap_sub_to_bitset(), IS_FULL_BLOCK, and IS_VALID_ADDR.
|
protected |
Definition at line 6974 of file bm.h.
References bm::bit_block_sub(), bm::bit_block_sub_2way(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_convert_to_bitset(), bm::gap_equiv_len, bm::gap_operation_sub(), and bm::gap_sub_to_bitset().
Referenced by bm::bvector< Alloc >::bit_sub().
|
protected |
Definition at line 7127 of file bm.h.
References bm::bit_block_copy(), bm::bit_block_set(), bm::bit_block_xor(), bm::bit_invert(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::gap_equiv_len, bm::gap_invert(), bm::gap_operation_xor(), bm::gap_xor_to_bitset(), and IS_FULL_BLOCK.
|
protected |
Definition at line 6707 of file bm.h.
References bm::bit_block_xor_2way(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::gap_equiv_len, bm::gap_operation_xor(), bm::gap_xor_to_bitset(), and IS_FULL_BLOCK.
Referenced by bm::bvector< Alloc >::bit_xor().
| void bm::bvector< Alloc >::combine_operation_or | ( | const bm::bvector< Alloc > & | bvect | ) |
perform a set-algebra operation OR
Definition at line 6189 of file bm.h.
References bm::avx2_test_all_eq_wave2(), BM_OR_OP, FULL_BLOCK_FAKE_ADDR, bm::set_sub_array_size, and bm::sse42_test_all_eq_wave2().
Referenced by bm::bvector< Alloc >::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 6448 of file bm.h.
References bm::avx2_test_all_zero_wave(), BM_SUB_OP, FULL_BLOCK_FAKE_ADDR, bm::set_sub_array_size, and bm::sse42_test_all_zero_wave().
Referenced by bm::bvector< Alloc >::bit_sub().
|
protected |
Definition at line 7416 of file bm.h.
References bm::all_bits_mask, bm::bit_andnot_arr_ffmask(), bm::bit_block_copy(), bm::bit_operation_and(), bm::bit_operation_or(), bm::bit_operation_sub(), bm::bit_operation_xor(), bm::BM_AND, BM_ASSERT, bm::BM_OR, bm::BM_SUB, bm::BM_XOR, BMGAP_PTR, bm::gap_convert_to_bitset_smart(), bm::gap_equiv_len, bm::gap_is_all_zero(), bm::gap_max_bits, bm::operation_functions< T >::gap_op_to_bit(), bm::operation_functions< T >::gap_operation(), IS_FULL_BLOCK, IS_VALID_ADDR, bm::set_block_size, and VECT_XOR_ARR_2_MASK.
| void bm::bvector< Alloc >::combine_operation_with_block | ( | block_idx_type | nb, |
| const bm::word_t * | arg_blk, | ||
| bool | arg_gap, | ||
| bm::operation | opcode | ||
| ) |
Definition at line 5651 of file bm.h.
References BM_IS_GAP, bm::bvector< Alloc >::combine_operation_with_block(), and bm::get_block_coord().
Referenced by bm::bvector< Alloc >::clear_range_no_check(), bm::bvector< Alloc >::combine_operation(), bm::bvector< Alloc >::combine_operation_with_block(), and bm::bvector< Alloc >::set_range_no_check().
| void bm::bvector< Alloc >::combine_operation_xor | ( | const bm::bvector< Alloc > & | bvect | ) |
perform a set-algebra operation XOR
Definition at line 6261 of file bm.h.
References bm::avx2_test_all_zero_wave2(), BM_XOR_OP, FULL_BLOCK_FAKE_ADDR, FULL_SUB_BLOCK_REAL_ADDR, bm::set_sub_array_size, and bm::sse42_test_all_zero_wave2().
Referenced by bm::bvector< Alloc >::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 this bitvector less than the argument, 1 - greater, 0 - equal
Definition at line 3709 of file bm.h.
References bm::bit_is_all_zero(), bm::bitcmp(), BM_DECLARE_TEMP_BLOCK, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_convert_to_bitset(), bm::gap_is_all_zero(), bm::gapcmp(), bm::set_block_size_op, and bm::set_sub_array_size.
Referenced by convert_bv2bvs(), fingerprint_compare(), main(), bm::bvector< Alloc >::operator<(), bm::bvector< Alloc >::operator<=(), bm::bvector< Alloc >::operator>(), bm::bvector< Alloc >::operator>=(), and run_benchmark().
| void bm::bvector< Alloc >::copy | ( | const bvector< Alloc > & | bvect, |
| bm::finalization | is_final | ||
| ) |
Copy bvector from the argument bvector.
| bvect | - bit-vector to copy from |
| is_final | - BM_READONLY - copies as immutable, BM_READWRITE - copies as mutable even if the argument bvect is read-only vector, BM_UNDEFINED - follow the argument type as is |
Definition at line 2268 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::is_ro(), bm::READONLY, bm::READWRITE, bm::bvector< Alloc >::resize(), bm::bvector< Alloc >::size(), and bm::UNDEFINED.
Referenced by bm::bvector< Alloc >::operator=().
| 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 7743 of file bm.h.
References bm::bvector< Alloc >::clear(), bm::bvector< Alloc >::copy_range_no_check(), and bm::xor_swap().
Referenced by main().
|
protected |
Definition at line 7788 of file bm.h.
References BM_ASSERT, BM_ASSERT_THROW, bm::bvector< Alloc >::clear_range_no_check(), bm::bvector< Alloc >::find_reverse(), bm::gap_max_bits, bm::id_max, and bm::set_block_shift.
Referenced by bm::bvector< Alloc >::bvector(), and bm::bvector< Alloc >::copy_range().
| bvector< Alloc >::size_type bm::bvector< Alloc >::count |
population count (count of ON bits)
Definition at line 2366 of file bm.h.
References BM_ASSERT, bm::find_not_null_ptr(), FULL_BLOCK_FAKE_ADDR, bm::gap_max_bits, and bm::set_sub_array_size.
Referenced by bv_count_test(), CSeqClusters::clear_empty_groups(), compute_and_sim_row(), CSeqClusters::compute_avg_count(), compute_group(), compute_jaccard_clusters(), convert_bv2vect(), CSeqClusters::elect_leaders(), main(), pre_heat(), print_bvector(), print_statistics(), CSeqClusters::print_summary(), bm::bvector< Alloc >::recalc_count(), run_benchmark(), and serialize_bvector().
| bvector< Alloc >::block_idx_type bm::bvector< Alloc >::count_blocks | ( | unsigned * | arr | ) | const |
Computes bitcount values for all bvector blocks.
| arr | - pointer on array of block bit counts |
Definition at line 2602 of file bm.h.
References bm::for_each_nzblock().
| bvector< Alloc >::size_type bm::bvector< Alloc >::count_range | ( | size_type | left, |
| size_type | right | ||
| ) | const |
Returns count of 1 bits in the given range [left..right].
| left | - index of first bit start counting from |
| right | - index of last bit |
Definition at line 3207 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::count_range_no_check(), bm::id_max, and bm::xor_swap().
| 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 3481 of file bm.h.
References BM_ASSERT_THROW, bm::bvector< Alloc >::count_range_no_check(), bm::id_max, and bm::xor_swap().
Referenced by bv_count_range(), bv_count_range_acc(), and CSeqClusters::elect_leaders().
| bvector< Alloc >::size_type bm::bvector< Alloc >::count_range_no_check | ( | size_type | left, |
| size_type | right | ||
| ) | const |
Returns count of 1 bits in the given range [left..right] Function expects that caller guarantees that left < right
Definition at line 3223 of file bm.h.
References bm::bit_block_calc_count_range(), bm::bits_in_block, BM_IS_GAP, BMGAP_PTR, bm::for_each_nzblock_range(), bm::gap_bit_count_range(), bm::gap_bit_count_to(), bm::get_block_coord(), bm::set_block_mask, and bm::set_block_shift.
Referenced by bm::bvector< Alloc >::count_range().
| bvector< Alloc >::size_type bm::bvector< Alloc >::count_range_no_check | ( | size_type | left, |
| size_type | right, | ||
| const rs_index_type & | rs_idx | ||
| ) | const |
Returns count of 1 bits in the given range [left..right] Function expects that caller guarantees that left < right
Definition at line 3495 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::count_to(), and bm::bvector< Alloc >::test().
| 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 3053 of file bm.h.
References BM_ASSERT, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::get_block_coord(), bm::id_max, bm::set_block_mask, and bm::set_block_shift.
Referenced by bv_count_to_acc(), bv_count_to_range_acc(), bm::bvector< Alloc >::count_range_no_check(), and bm::bvector< Alloc >::rank().
| bvector< Alloc >::size_type bm::bvector< Alloc >::count_to_test | ( | size_type | n, |
| const rs_index_type & | rs_idx | ||
| ) | 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 |
| rs_idx | - rank-select index (block count structure to accelerate search) should be prepared using build_rs_index() |
Definition at line 3106 of file bm.h.
References bm::bit_block_calc_count_to(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::gap_bit_count_to(), bm::get_block_coord(), bm::id_max, bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.
|
inline |
Returns true if the set is empty (no bits are set, otherwise returns false) Please note that this is NOT a size check, it is an empty SET check (absense of 1s)
Definition at line 1540 of file bm.h.
References bm::bvector< Alloc >::any().
Referenced by bm::bvector< Alloc >::combine_operation_block_and(), and bm::bvector< Alloc >::combine_operation_block_sub().
|
inline |
Returns enumerator pointing on the next bit after the last.
Definition at line 1855 of file bm.h.
References bm::bvector< Alloc >::enumerator.
Referenced by combine_or_test(), main(), speed_test_sv_index(), and speed_test_vect_index().
|
inline |
Equal comparison with an agr bit-vector.
Definition at line 1995 of file bm.h.
References bm::bvector< Alloc >::find_first_mismatch().
Referenced by main(), bm::bvector< Alloc >::operator!=(), bm::bvector< Alloc >::operator==(), Set3VL_AndDemo(), and Set3VL_ORDemo().
| void bm::bvector< Alloc >::erase | ( | size_type | n | ) |
Erase bit in the specified position All the vector content after erase position is shifted left.
| n | - index of the bit to insert |
Definition at line 5408 of file bm.h.
References bm::bit_block_erase(), bm::bit_block_shift_l1_unr(), BM_ASSERT, BM_ASSERT_THROW, bm::BM_BIT, BM_IS_GAP, BMGAP_PTR, bm::find_not_null_ptr(), FULL_BLOCK_FAKE_ADDR, bm::gap_is_all_zero(), bm::gap_limit(), bm::gap_max_bits, bm::gap_shift_l1(), bm::get_block_coord(), bm::id_max, IS_FULL_BLOCK, bm::bvector< Alloc >::is_ro(), IS_VALID_ADDR, bm::bvector< Alloc >::set_bit_no_check(), bm::set_block_mask, bm::set_block_shift, bm::set_block_size, bm::set_sub_array_size, bm::set_top_array_size, and bm::bvector< Alloc >::test().
Referenced by bm::bvector< Alloc >::shift_left().
|
inline |
Finds the number of the next bit ON and sets it to 0.
| prev | - Index of the previously found bit. |
Definition at line 1597 of file bm.h.
References bm::bvector< Alloc >::check_or_next_extract(), and bm::id_max.
Referenced by main().
| void bm::bvector< Alloc >::fill_alloc_digest | ( | bvector< Alloc > & | bv_blocks | ) | const |
Calculate blocks digest vector (for diagnostics purposes) 1 is added if NB is a real, allocated block.
| bv_blocks | - [out] bvector of blocks statistics |
Definition at line 4023 of file bm.h.
References FULL_BLOCK_FAKE_ADDR, bm::bvector< Alloc >::init(), IS_VALID_ADDR, bm::bvector< Alloc >::set_bit_no_check(), and bm::set_sub_array_size.
| bool bm::bvector< Alloc >::find | ( | size_type & | pos | ) | const |
Finds index of first 1 bit.
| pos | - [out] index of the found 1 bit |
Definition at line 4855 of file bm.h.
References bm::bit_find_first(), bm::bits_in_array, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, FULL_SUB_BLOCK_REAL_ADDR, bm::gap_find_first(), bm::gap_max_bits, and bm::set_sub_array_size.
Referenced by access_bench3(), bm::bvector< Alloc >::find(), bm::bvector< Alloc >::find_first_mismatch(), bm::bvector< Alloc >::find_range(), and main().
| bool bm::bvector< Alloc >::find | ( | size_type | from, |
| size_type & | pos | ||
| ) | const |
Find index of 1 bit starting from position.
| from | - position to start search from, please note that if bit at from position is set then it will be found, function uses closed interval [from... |
| pos | - [out] index of the found 1 bit |
Definition at line 4658 of file bm.h.
References bm::bvector< Alloc >::check_or_next(), bm::bvector< Alloc >::find(), and bm::id_max.
| bool bm::bvector< Alloc >::find_first_mismatch | ( | const bvector< Alloc > & | bvect, |
| size_type & | pos, | ||
| size_type | search_to = bm::id_max |
||
| ) | const |
Find index of first bit different between this and the agr vector.
| bvect | - argumnet vector to compare with |
| pos | - [out] position of the first difference |
| search_to | - search limiter [0..to] to avoid overscan (default: unlimited to the vectors end) |
Definition at line 3827 of file bm.h.
References BLOCK_ADDR_SAN, bm::block_find_first_diff(), bm::bvector< Alloc >::find(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_max_bits, bm::get_block_coord(), bm::set_block_shift, and bm::set_sub_array_size.
Referenced by bm::bvector< Alloc >::equal(), and main().
| 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 4901 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::find(), and bm::bvector< Alloc >::find_reverse().
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) |
Definition at line 4921 of file bm.h.
References bm::block_find_rank(), BM_ASSERT, BM_ASSERT_THROW, bm::gap_max_bits, bm::id_max, bm::set_block_mask, bm::set_block_shift, bm::set_block_size, and bm::set_total_blocks.
| 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) |
| rs_idx | - rank-select index to accelarate search (should be prepared using build_rs_index) |
Definition at line 4974 of file bm.h.
References bm::block_find_rank(), BM_ASSERT, BM_ASSERT_THROW, bm::id_max, bm::set_block_mask, bm::set_block_shift, and bm::set_block_size.
| bool bm::bvector< Alloc >::find_reverse | ( | size_type & | pos | ) | const |
Finds last index of 1 bit.
| pos | - [out] index of the last found 1 bit |
Definition at line 4673 of file bm.h.
References bm::bit_find_last(), BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, FULL_SUB_BLOCK_REAL_ADDR, bm::gap_find_last(), bm::gap_max_bits, and bm::set_sub_array_size.
Referenced by access_bench2(), access_bench3(), bm::bvector< Alloc >::build_rs_index(), bm::bvector< Alloc >::clear(), bm::bvector< Alloc >::copy_range_no_check(), bm::bvector< Alloc >::find_range(), bm::bvector< Alloc >::keep(), main(), and bm::bvector< Alloc >::sync_size().
| bool bm::bvector< Alloc >::find_reverse | ( | size_type | from, |
| size_type & | pos | ||
| ) | const |
Reverse finds next(prev) index of 1 bit.
| from | - index to search from |
| pos | - [out] found position index (undefined if method returns false) |
Definition at line 4730 of file bm.h.
References bm::bit_find_last(), bm::block_find_reverse(), BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, FULL_SUB_BLOCK_REAL_ADDR, bm::gap_find_last(), bm::gap_max_bits, bm::get_block_coord(), bm::set_block_mask, bm::set_block_shift, bm::set_sub_array_size, and bm::bvector< Alloc >::test().
|
inline |
Returns enumerator pointing on the first non-zero bit.
Definition at line 1849 of file bm.h.
References bm::bvector< Alloc >::get_enumerator().
Referenced by bv2delta(), bv_counted_enumerator(), compute_random_clusters(), convert_bv2sv(), convert_bv2vect(), CSequenceColl::deserialize_k_mers(), CSeqClusters::elect_leaders(), generate_random_subset(), main(), print_bvector(), print_sorted(), PrintKleeneVector(), speed_test_bv_index(), speed_test_bvs_index(), speed_test_sv_index(), speed_test_vect_index(), and DNA_FingerprintScanner::TranslateResults().
|
inline |
Flips all bits.
Definition at line 1258 of file bm.h.
References bm::bvector< Alloc >::invert().
|
inline |
Flips bit n.
Definition at line 1251 of file bm.h.
References bm::bvector< Alloc >::inc().
|
inline |
| void bm::bvector< Alloc >::freeze |
Turn current vector to read-only (immutable vector).
After calling this method any modification (non-const methods) will cause undefined behavior (likely crash or assert)
Definition at line 7820 of file bm.h.
References bm::bvector< Alloc >::is_ro(), bm::READONLY, and bm::bvector< Alloc >::swap().
Referenced by main().
|
protected |
set bit in GAP block with GAP block length control
Definition at line 4473 of file bm.h.
References bm::gap_length(), bm::gap_limit(), and bm::gap_set_value().
Referenced by bm::bvector< Alloc >::and_bit_no_check(), bm::bvector< Alloc >::inc(), bm::bvector< Alloc >::set_bit_conditional_impl(), and bm::bvector< Alloc >::set_bit_no_check().
|
protected |
set bit in GAP block with GAP block length control
Definition at line 4492 of file bm.h.
References bm::gap_length(), bm::gap_limit(), and bm::gap_set_value().
Referenced by bm::bvector< Alloc >::clear_bit_no_check(), bm::bvector< Alloc >::import_block(), and bm::bvector< Alloc >::set_bit_no_check().
|
inline |
| 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 3567 of file bm.h.
References BM_ASSERT, BM_ASSERT_THROW, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::gap_test_unr(), bm::get_block_coord(), bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::bvector< Alloc >::operator[](), and bm::bvector< Alloc >::test().
|
inline |
|
inline |
get access to memory manager (internal) Use only if you are BitMagic library
Definition at line 2036 of file bm.h.
Referenced by bm::bvector< Alloc >::bit_and(), bm::bvector< Alloc >::bit_or(), bm::bvector< Alloc >::bit_or_and(), bm::bvector< Alloc >::bit_sub(), and bm::bvector< Alloc >::bit_xor().
|
inline |
Returns enumerator pointing on specified or the next available bit.
Definition at line 1861 of file bm.h.
References bm::bvector< Alloc >::enumerator.
Referenced by bm::bvector< Alloc >::first(), and main().
|
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 1578 of file bm.h.
References bm::bvector< Alloc >::check_or_next().
Referenced by bm::bvector_mini< A >::compare(), print_bvector(), and CSeqClusters::take_group().
|
inline |
Returns blocks allocation strategy.
Definition at line 1898 of file bm.h.
Referenced by bm::bvector< Alloc >::and_bit_no_check(), bm::bvector< Alloc >::clear_bit_no_check(), bm::bvector< Alloc >::inc(), bm::bvector< Alloc >::insert(), bm::bvector< Alloc >::set_bit_conditional_impl(), and bm::bvector< Alloc >::set_bit_no_check().
|
inline |
Finds the number of the next bit ON.
| prev | - Index of the previously found bit. |
Definition at line 1587 of file bm.h.
References bm::bvector< Alloc >::check_or_next(), and bm::id_max.
Referenced by bm::bvector_mini< A >::compare(), and print_bvector().
| void bm::bvector< Alloc >::import | ( | const size_type * | ids, |
| size_type | ids_size, | ||
| bm::sort_order | sorted_idx | ||
| ) |
Import integers (set bits).
(Fast, no checks).
Definition at line 4210 of file bm.h.
References BM_ASSERT, bm::BM_SORTED, bm::idx_arr_block_lookup_u32(), bm::idx_arr_block_lookup_u64(), bm::bvector< Alloc >::import_block(), bm::bvector< Alloc >::is_ro(), and bm::set_block_shift.
Referenced by bm::bvector< Alloc >::clear(), bm::bvector< Alloc >::bulk_insert_iterator::flush(), bm::bvector< Alloc >::keep(), and bm::bvector< Alloc >::bulk_insert_iterator::operator=().
|
protected |
Definition at line 4321 of file bm.h.
References BM_ASSERT, BM_IS_GAP, BMGAP_PTR, bm::bvector< Alloc >::gap_block_set_no_ret(), IS_FULL_BLOCK, bm::set_block_bits_u32(), bm::set_block_bits_u64(), bm::set_block_mask, bm::set_block_size, and bm::set_total_blocks.
Referenced by bm::bvector< Alloc >::import(), and bm::bvector< Alloc >::import_sorted().
| void bm::bvector< Alloc >::import_sorted | ( | const size_type * | ids, |
| const size_type | ids_size, | ||
| bool | opt_flag | ||
| ) |
Import sorted integers (set bits).
(Fast, no checks).
Definition at line 4255 of file bm.h.
References BM_ASSERT, bm::get_block_coord(), bm::id_max, bm::idx_arr_block_lookup_u32(), bm::idx_arr_block_lookup_u64(), bm::bvector< Alloc >::import_block(), bm::bvector< Alloc >::opt_compress, bm::set_block_mask, and bm::set_block_shift.
| 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 4510 of file bm.h.
References BM_ASSERT, BM_IS_GAP, BMGAP_PTR, bm::bvector< Alloc >::gap_block_set(), bm::gap_test_unr(), bm::bvector< Alloc >::get_new_blocks_strat(), bm::bvector< Alloc >::is_ro(), IS_VALID_ADDR, bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::bvector< Alloc >::flip().
| void bm::bvector< Alloc >::init |
Explicit post-construction initialization. Must be caled to make sure safe use of *_no_check() methods.
Definition at line 2258 of file bm.h.
References BM_ASSERT, and bm::bvector< Alloc >::is_ro().
Referenced by bm::bvector< Alloc >::build_rs_index(), bm::bvector< Alloc >::bulk_insert_iterator::bulk_insert_iterator(), bv_set_bit_no_check_test(), bm::bvector< Alloc >::bvector(), bm::basic_bmatrix< BV >::construct_bvector(), bm::bvector< Alloc >::fill_alloc_digest(), bm::bvector< Alloc >::insert_iterator::insert_iterator(), load_snp_report(), main(), run_benchmark(), 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 5205 of file bm.h.
References bm::bit_block_insert(), bm::bit_block_shift_r1_unr(), BM_ASSERT, BM_ASSERT_THROW, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::gap_insert(), bm::gap_limit(), bm::gap_max_bits, bm::gap_shift_r1(), bm::get_block_coord(), bm::bvector< Alloc >::get_new_blocks_strat(), bm::id_max, IS_FULL_BLOCK, bm::bvector< Alloc >::is_ro(), IS_VALID_ADDR, bm::bvector< Alloc >::set(), bm::bvector< Alloc >::set_bit_no_check(), bm::set_block_mask, bm::set_block_shift, bm::set_block_size, bm::set_sub_array_size, bm::set_top_array_size, bm::set_total_blocks, and bm::bvector< Alloc >::enumerator::value().
Referenced by bm::bvector< Alloc >::shift_right().
|
inline |
Function erturns insert iterator for this bitvector
Definition at line 1265 of file bm.h.
Referenced by DNA_FingerprintScanner::Build(), main(), and Set3VL_ValueDemo2().
| 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 3515 of file bm.h.
References bm::bit_invert(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, bm::bvector< Alloc >::clear_range_no_check(), FULL_BLOCK_FAKE_ADDR, bm::gap_invert(), bm::id_max, IS_FULL_BLOCK, bm::bvector< Alloc >::is_ro(), bm::bvector< Alloc >::set_bit_no_check(), bm::set_sub_array_size, and bm::set_top_array_size.
Referenced by DemoINV(), bm::bvector< Alloc >::flip(), main(), bm::bvector< Alloc >::operator~(), and bm::sparse_vector_find_mismatch().
| bool bm::bvector< Alloc >::is_all_one_range | ( | size_type | left, |
| size_type | right | ||
| ) | const |
Returns true if all bits in the range are 1s (saturated interval) Function uses closed interval [left, right].
| left | - index of first bit start checking |
| right | - index of last bit |
Definition at line 3303 of file bm.h.
References bm::block_is_all_one_range(), BM_ASSERT, bm::check_block_one(), FULL_BLOCK_FAKE_ADDR, bm::gap_max_bits, bm::get_block_coord(), bm::id_max, bm::set_block_mask, bm::set_block_shift, bm::set_sub_array_size, bm::bvector< Alloc >::test(), and bm::xor_swap().
Referenced by main().
|
inline |
|
inline |
Returns true if vector is read-only.
Definition at line 1046 of file bm.h.
Referenced by bm::bvector< Alloc >::and_bit_no_check(), bm::bvector< Alloc >::bit_and(), bm::bvector< Alloc >::bit_or(), bm::bvector< Alloc >::bit_or_and(), bm::bvector< Alloc >::bit_sub(), bm::bvector< Alloc >::bit_xor(), bm::bvector< Alloc >::calc_stat(), bm::bvector< Alloc >::check_or_next_extract(), bm::bvector< Alloc >::clear(), bm::bvector< Alloc >::clear_bit_no_check(), bm::bvector< Alloc >::copy(), bm::bvector< Alloc >::erase(), bm::bvector< Alloc >::freeze(), bm::bvector< Alloc >::import(), bm::bvector< Alloc >::inc(), bm::bvector< Alloc >::init(), bm::bvector< Alloc >::insert(), bm::bvector< Alloc >::invert(), bm::bvector< Alloc >::keep(), bm::bvector< Alloc >::keep_range(), main(), bm::bvector< Alloc >::merge(), bm::bvector< Alloc >::optimize(), bm::bvector< Alloc >::optimize_range(), bm::bvector< Alloc >::resize(), bm::bvector< Alloc >::set(), bm::bvector< Alloc >::set_bit(), bm::bvector< Alloc >::set_bit_and(), bm::bvector< Alloc >::set_bit_no_check(), bm::bvector< Alloc >::set_gap_levels(), bm::bvector< Alloc >::set_range(), bm::bvector< Alloc >::shift_left(), bm::bvector< Alloc >::shift_right(), and bm::bvector< Alloc >::sync_size().
| 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 4070 of file bm.h.
References bm::bvector< Alloc >::bit_and(), BM_ASSERT, bm::bvector< Alloc >::clear(), bm::bvector< Alloc >::find_reverse(), bm::bvector< Alloc >::import(), bm::bvector< Alloc >::is_ro(), and bm::bvector< Alloc >::resize().
Referenced by DemoAND().
| void bm::bvector< Alloc >::keep_range | ( | size_type | left, |
| size_type | right | ||
| ) |
Sets all bits to zero outside of the closed interval [left,right] Expected result: 00000...0[left, right]0....0000.
| left | - interval start |
| right | - interval end (closed interval) |
Definition at line 2318 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::is_ro(), and bm::xor_swap().
Referenced by main().
| 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 5578 of file bm.h.
References bm::bvector< Alloc >::bit_or(), BM_ASSERT, bm::bvector< Alloc >::combine_operation_block_or(), FULL_BLOCK_FAKE_ADDR, bm::bvector< Alloc >::is_ro(), and bm::set_sub_array_size.
Referenced by CKMerAcc::add(), DemoOR(), CSeqGroup::merge_member_sync(), and DNA_FingerprintScanner::MergeVector().
| void bm::bvector< Alloc >::move_from | ( | bvector< Alloc > & | bvect | ) |
Move bvector content from another bvector.
Definition at line 2305 of file bm.h.
Referenced by bm::bvector< Alloc >::operator=().
|
inline |
Returns true if no bits are set, otherwise returns false.
Definition at line 1534 of file bm.h.
References bm::bvector< Alloc >::any().
|
inline |
Definition at line 1016 of file bm.h.
References bm::bvector< Alloc >::equal().
|
inline |
Definition at line 1006 of file bm.h.
References bm::bvector< Alloc >::bit_and().
|
inline |
Definition at line 1009 of file bm.h.
References bm::bvector< Alloc >::bit_sub().
|
inline |
Definition at line 1011 of file bm.h.
References bm::bvector< Alloc >::compare().
|
inline |
Definition at line 1012 of file bm.h.
References bm::bvector< Alloc >::compare().
|
inline |
Move assignment operator.
Definition at line 951 of file bm.h.
References bm::bvector< Alloc >::move_from().
|
inline |
Copy assignment operator.
Definition at line 916 of file bm.h.
References bm::bvector< Alloc >::copy(), and bm::UNDEFINED.
|
inline |
Definition at line 1015 of file bm.h.
References bm::bvector< Alloc >::equal().
|
inline |
Definition at line 1013 of file bm.h.
References bm::bvector< Alloc >::compare().
|
inline |
Definition at line 1014 of file bm.h.
References bm::bvector< Alloc >::compare().
|
inline |
Definition at line 990 of file bm.h.
References bm::id_max, and bm::bvector< Alloc >::resize().
|
inline |
Definition at line 1000 of file bm.h.
References BM_ASSERT, and bm::bvector< Alloc >::get_bit().
|
inline |
Definition at line 1007 of file bm.h.
References bm::bvector< Alloc >::bit_xor().
|
inline |
Definition at line 1008 of file bm.h.
References bm::bvector< Alloc >::bit_or().
|
inline |
Definition at line 1018 of file bm.h.
References bm::bvector< Alloc >::invert().
| 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
| temp_block | - externally allocated temp buffer for optimization BM_DECLARE_TEMP_BLOCK(tb) if NULL - it will allocated (and de-allocated upon exit) |
| opt_mode | - optimization level |
| stat | - statistics of memory consumption and serialization stat can also be computed by calc_stat() but it would require an extra pass |
Definition at line 3600 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::calc_stat(), bm::gap_levels, bm::bv_statistics::gap_levels, bm::bvector< Alloc >::is_ro(), bm::bv_statistics::max_serialize_mem, bm::bv_statistics::memory_used, and bm::bv_statistics::reset().
Referenced by compute_seq_group_union(), generate_bvector(), generate_k_mers(), GenerateDemoVector(), main(), make_BLOB(), serialize_bvector(), Set3VL_ValueDemo(), Set3VL_ValueDemo2(), speed_test_bv_index(), speed_test_bvs_index(), speed_test_sv_index(), speed_test_vect_index(), and write_as_bvector().
| 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 3665 of file bm.h.
References bm::bvector< Alloc >::calc_stat(), bm::gap_levels, bm::improve_gap_levels(), and bm::bvector< Alloc >::set_gap_levels().
| void bm::bvector< Alloc >::optimize_range | ( | size_type | left, |
| size_type | right, | ||
| bm::word_t * | temp_block, | ||
| optmode | opt_mode = opt_compress |
||
| ) |
Run partial vector optimization for the area [left..right] (specified in bit coordinates)
| left | - bit index to optimize from (approximate, rounded up to a nearest block) |
| right | - bit index to optimize to Please note that left and right define range in bit coordinates but later rounded to blocks |
| temp_block | - external scratch memory (MUST be pre-allocated) |
| opt_mode | - optimization level |
Definition at line 3636 of file bm.h.
References BM_ASSERT, bm::get_block_coord(), bm::bvector< Alloc >::is_ro(), and bm::set_block_shift.
|
inline |
Returns rank of specified bit position (same as count_to())
| n | - index of bit to rank |
| rs_idx | - rank-select index |
Definition at line 1411 of file bm.h.
References bm::bvector< Alloc >::count_to().
Referenced by bm::bvector< Alloc >::enumerator::skip(), and bm::bvector< Alloc >::enumerator::skip_to_rank().
| bvector< Alloc >::size_type bm::bvector< Alloc >::rank_corrected | ( | size_type | n, |
| const rs_index_type & | rs_idx | ||
| ) | const |
Returns rank corrceted by the requested border value (as -1)
This is rank function (bit-count) minus value of bit 'n' if bit-n is true function returns rank()-1 if false returns rank() faster than rank() + test().
| n | - index of bit to rank |
| rs_idx | - rank-select index |
Definition at line 3162 of file bm.h.
References BM_ASSERT, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, bm::get_block_coord(), bm::id_max, bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.
|
inline |
Recalculate bitcount (deprecated)
Definition at line 1455 of file bm.h.
References bm::bvector< Alloc >::count().
|
inline |
Clears every bit in the bitvector.
Definition at line 1245 of file bm.h.
References bm::bvector< Alloc >::clear().
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 2428 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::is_ro(), and bm::bvector< Alloc >::set_range().
Referenced by bm::bvector< Alloc >::clear(), convert_bv2sv(), bm::bvector< Alloc >::copy(), DemoAND(), DemoAND_OR(), DemoINV(), DemoOR(), DemoSUB(), DemoXOR(), bm::bvector< Alloc >::keep(), main(), bm::bvector< Alloc >::insert_iterator::operator=(), bm::bvector< Alloc >::operator[](), pick_benchmark_set(), bm::bvector< Alloc >::set_bit(), bm::bvector< Alloc >::set_bit_conditional(), bm::bvector< Alloc >::set_range(), bm::sparse_vector_find_first_mismatch(), bm::sparse_vector_find_mismatch(), and bm::bvector< Alloc >::sync_size().
| 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 5045 of file bm.h.
References bm::block_find_rank(), BM_ASSERT, FULL_BLOCK_FAKE_ADDR, bm::gap_max_bits, bm::get_block_coord(), and bm::set_block_size.
Referenced by main().
| bvector< Alloc > & bm::bvector< Alloc >::set |
Sets every bit in this bitset to 1.
Definition at line 4142 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::is_ro(), and bm::bvector< Alloc >::set_range().
Referenced by bm::bvector< Alloc >::insert().
| 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) |
Definition at line 4053 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::is_ro(), and bm::bvector< Alloc >::sync_size().
| 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 4153 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::is_ro(), and bm::bvector< Alloc >::set_bit().
Referenced by CKMerAcc::add(), bvector_bulk_set_test(), CSeqGroup::clear_member(), CSeqGroup::CSeqGroup(), DemoOR(), CSeqClusters::elect_leaders(), fill_bvector(), generate_bvector(), main(), pick_benchmark_set(), run_benchmark(), and write_as_bvector().
|
inline |
Set allocator pool for local (non-th readed) memory cyclic(lots of alloc-free ops) opertations.
Definition at line 1026 of file bm.h.
Referenced by assign_to_best_cluster(), and assign_to_best_cluster_union().
| 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 4192 of file bm.h.
References BM_ASSERT, BM_ASSERT_THROW, bm::id_max, bm::bvector< Alloc >::is_ro(), bm::bvector< Alloc >::resize(), and bm::bvector< Alloc >::set_bit_no_check().
Referenced by bv_set_bit_test(), bm::bvector< Alloc >::clear_bit(), fill_bvector(), generate_random_vector(), and bm::bvector< Alloc >::set().
| bool bm::bvector< Alloc >::set_bit_and | ( | size_type | n, |
| bool | val = true |
||
| ) |
Sets bit n using bit AND with the provided value.
| n | - index of the bit to be set. |
| val | - new bit value |
Definition at line 4178 of file bm.h.
References bm::bvector< Alloc >::and_bit_no_check(), BM_ASSERT, BM_ASSERT_THROW, and bm::bvector< Alloc >::is_ro().
| bool bm::bvector< Alloc >::set_bit_conditional | ( | size_type | n, |
| bool | val, | ||
| bool | condition | ||
| ) |
Sets bit n only if current value equals the condition.
| n | - index of the bit to be set. |
| val | - new bit value |
| condition | - expected current value |
Definition at line 4164 of file bm.h.
References bm::id_max, bm::bvector< Alloc >::resize(), and bm::bvector< Alloc >::set_bit_conditional_impl().
|
protected |
Definition at line 4546 of file bm.h.
References BMGAP_PTR, bm::bvector< Alloc >::gap_block_set(), bm::bvector< Alloc >::get_new_blocks_strat(), IS_VALID_ADDR, bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::bvector< Alloc >::set_bit_conditional().
| 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 4405 of file bm.h.
References BM_ASSERT, BM_ASSERT_THROW, BMGAP_PTR, bm::bvector< Alloc >::gap_block_set_no_ret(), bm::bvector< Alloc >::get_new_blocks_strat(), bm::id_max, bm::bvector< Alloc >::is_ro(), IS_VALID_ADDR, bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.
Referenced by CSeqGroup::add_member(), CSeqGroup::add_member_sync(), bm::bvector< Alloc >::build_rs_index(), bv_set_bit_no_check_test(), bm::bvector< Alloc >::bvector(), bm::bvector< Alloc >::erase(), bm::bvector< Alloc >::fill_alloc_digest(), bm::bvector< Alloc >::insert(), bm::bvector< Alloc >::invert(), load_snp_report(), main(), bm::bvector< Alloc >::insert_iterator::operator=(), run_benchmark(), bm::bvector< Alloc >::set_bit(), and vector_search().
| bool bm::bvector< Alloc >::set_bit_no_check | ( | size_type | n, |
| bool | val | ||
| ) |
Set specified bit without checking preconditions (size, etc)
Definition at line 4356 of file bm.h.
References BM_ASSERT, BM_ASSERT_THROW, BMGAP_PTR, bm::bvector< Alloc >::gap_block_set(), bm::bvector< Alloc >::get_new_blocks_strat(), bm::id_max, bm::bvector< Alloc >::is_ro(), IS_VALID_ADDR, bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.
| 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.
| glevel_len | - pointer on C-style array keeping GAP block sizes. |
Definition at line 3691 of file bm.h.
References BM_ASSERT, bm::for_each_nzblock(), and bm::bvector< Alloc >::is_ro().
Referenced by bm::bvector< Alloc >::optimize_gap_size().
|
inline |
Sets new blocks allocation strategy.
| strat | - Strategy code 0 - bitblocks allocation only. 1 - Blocks mutation mode (adaptive algorithm) |
Definition at line 1890 of file bm.h.
Referenced by main().
| 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 2333 of file bm.h.
References BM_ASSERT, BM_ASSERT_THROW, bm::bvector< Alloc >::clear_range_no_check(), bm::id_max, bm::bvector< Alloc >::is_ro(), bm::bvector< Alloc >::resize(), bm::bvector< Alloc >::set_range(), bm::bvector< Alloc >::set_range_no_check(), and bm::bvector< Alloc >::enumerator::value().
Referenced by add_object(), bv_count_and(), bm::bvector< Alloc >::clear_range(), bm::bvector< Alloc >::combine_operation(), compute_jaccard_clusters(), generate_bvector(), main(), bm::bvector< Alloc >::resize(), bm::bvector< Alloc >::set(), and bm::bvector< Alloc >::set_range().
| void bm::bvector< Alloc >::set_range_no_check | ( | size_type | left, |
| size_type | right | ||
| ) |
Set range without validity/bounds checking.
Definition at line 7592 of file bm.h.
References bm::bits_in_block, BM_ASSERT, BM_IS_GAP, bm::BM_OR, bm::bvector< Alloc >::combine_operation_with_block(), bm::get_block_coord(), bm::set_block_mask, and bm::set_block_shift.
Referenced by bm::bvector< Alloc >::build_rs_index(), and bm::bvector< Alloc >::set_range().
| bool bm::bvector< Alloc >::shift_left |
Shift left by 1 bit, fill with zero return carry out.
Definition at line 5194 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::erase(), bm::bvector< Alloc >::is_ro(), and bm::bvector< Alloc >::test().
| bool bm::bvector< Alloc >::shift_right |
Shift right by 1 bit, fill with zero return carry out.
Definition at line 5185 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::insert(), and bm::bvector< Alloc >::is_ro().
Referenced by DNA_FingerprintScanner::Find().
|
inline |
Returns bvector's capacity (number of bits it can store)
return current size of the vector (bits)
Definition at line 1278 of file bm.h.
Referenced by bm::bvector< Alloc >::copy(), generate_k_mers(), bm::bvector< Alloc >::insert_iterator::operator=(), print_bvector(), run_benchmark(), and bm::sparse_vector_find_mismatch().
| void bm::bvector< Alloc >::swap | ( | bvector< Alloc > & | bvect | ) |
Exchanges content of bv and this bvector.
Definition at line 3931 of file bm.h.
References bm::xor_swap().
Referenced by bm::bvector< Alloc >::freeze(), main(), and CSeqClusters::take_group().
|
protected |
Syncronize size if it got extended due to bulk import.
Definition at line 2451 of file bm.h.
References BM_ASSERT, bm::bvector< Alloc >::find_reverse(), bm::id_max, bm::bvector< Alloc >::is_ro(), and bm::bvector< Alloc >::resize().
Referenced by bm::bvector< Alloc >::bulk_insert_iterator::flush(), and bm::bvector< Alloc >::set().
|
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 1480 of file bm.h.
References bm::bvector< Alloc >::get_bit().
Referenced by bm::bvector< Alloc >::any_range(), compute_group(), bm::bvector< Alloc >::count_range_no_check(), CSeqClusters::elect_leaders(), bm::bvector< Alloc >::erase(), bm::bvector< Alloc >::find_reverse(), bm::bvector< Alloc >::is_all_one_range(), load_snp_report(), main(), pick_benchmark_set(), PrintKleeneVector(), and bm::bvector< Alloc >::shift_left().
1.9.2