BitMagic-C++
Data Structures | Public Types | Friends
bm::bvector< Alloc > Class Template Reference

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

#include <bm.h>

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

Data Structures

struct  allocation_policy
 memory allocation policy More...
 
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_typeblocks_count
 
typedef rs_index< allocator_typers_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 () BMNOEXCEPT
 
void init ()
 Explicit post-construction initialization. More...
 
bvectoroperator= (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...
 
bvectoroperator= (bvector< Alloc > &&bvect) BMNOEXCEPT
 Move assignment operator. 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)
 
bool operator[] (size_type n) const BMNOEXCEPT
 
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 BMNOEXCEPT
 
bool operator!= (const bvector< Alloc > &bv) const BMNOEXCEPT
 
bvector< Alloc > operator~ () const
 
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_typeget_allocator_pool () BMNOEXCEPT
 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...
 
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=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 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 cout (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...
 
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
 
void forget_count () BMNOEXCEPT
 
Bit access (read-only)


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


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 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...
 
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_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


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, 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


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 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_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...
 
Comparison


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
 
template<class BV >
class aggregator
 
template<class BV >
class operation_deserializer
 

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_typeget_blocks_manager () const BMNOEXCEPT
 get access to memory manager (internal) Use only if you are BitMagic library More...
 
blocks_manager_typeget_blocks_manager () BMNOEXCEPT
 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)
 

Detailed Description

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

Bitvector Bit-vector container with runtime compression of bits.

Examples
bvsetalgebra.cpp, sample14.cpp, sample4.cpp, sample6.cpp, strsvsample05.cpp, xsample01.cpp, xsample07.cpp, and xsample07a.cpp.

Definition at line 107 of file bm.h.

Member Typedef Documentation

◆ allocator_pool_type

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

Definition at line 111 of file bm.h.

◆ allocator_type

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

Definition at line 110 of file bm.h.

◆ block_idx_type

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

Definition at line 113 of file bm.h.

◆ blocks_count

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

Definition at line 844 of file bm.h.

◆ blocks_manager_type

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

Definition at line 112 of file bm.h.

◆ const_reference

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

Definition at line 230 of file bm.h.

◆ rs_index_type

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

Definition at line 845 of file bm.h.

◆ size_type

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

Definition at line 117 of file bm.h.

Member Enumeration Documentation

◆ optmode

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

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

See also
optimize
Enumerator
opt_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)

Definition at line 129 of file bm.h.

Constructor & Destructor Documentation

◆ bvector() [1/6]

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

Constructs bvector class.

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

Definition at line 872 of file bm.h.

◆ bvector() [2/6]

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

Constructs bvector class.

Definition at line 884 of file bm.h.

◆ bvector() [3/6]

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

Copy constructor.

Definition at line 896 of file bm.h.

◆ bvector() [4/6]

template<class Alloc >
bm::bvector< Alloc >::bvector ( const bvector< Alloc > &  bvect,
size_type  left,
size_type  right 
)
inline

Copy constructor for range copy [left..right].

See also
copy_range

Definition at line 907 of file bm.h.

◆ ~bvector()

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

Definition at line 920 of file bm.h.

◆ bvector() [5/6]

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

Move constructor.

Definition at line 944 of file bm.h.

◆ bvector() [6/6]

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

Brace constructor.

Definition at line 954 of file bm.h.

Member Function Documentation

◆ any()

template<typename Alloc >
bool bm::bvector< Alloc >::any

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

Returns
true if any bit is set

Definition at line 2258 of file bm.h.

Referenced by DNA_FingerprintScanner::Find(), bm::bvector<>::none(), and resolve_duplicates().

◆ any_range()

template<typename Alloc >
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].

Parameters
left- index of first bit start checking
right- index of last bit
Returns
true if at least 1 bits is set
See also
is_all_one_range, count_range

Definition at line 2879 of file bm.h.

Referenced by add_object(), and main().

◆ bit_and() [1/2]

template<class Alloc >
bm::bvector<Alloc>& bm::bvector< Alloc >::bit_and ( const bm::bvector< Alloc > &  bv,
optmode  opt_mode = opt_none 
)
inline

2 operand logical AND

Parameters
bv- argument vector
opt_mode- set an immediate optimization

Definition at line 1718 of file bm.h.

◆ bit_and() [2/2]

template<class Alloc >
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

Parameters
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()
See also
optimize, bit_and

Definition at line 5031 of file bm.h.

Referenced by bm::bvector<>::bit_and(), DemoAND(), bm::sparse_vector< unsigned, bm::bvector<> >::filter(), bm::bvector<>::keep(), bm::operator&(), bm::bvector<>::operator&=(), and resolve_duplicates().

◆ bit_or() [1/2]

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

2 operand logical OR

Parameters
bv- Argument vector.

Definition at line 1707 of file bm.h.

◆ bit_or() [2/2]

template<class Alloc >
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

Parameters
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()
See also
optimize, bit_or

Definition at line 4823 of file bm.h.

Referenced by bm::bvector<>::bit_and(), bm::bvector<>::bit_or(), bm::bvector<>::bit_sub(), DemoOR(), bm::dynamic_range_clip_high(), bm::dynamic_range_clip_low(), main(), bm::operator|(), bm::bvector<>::operator|=(), and bm::sparse_vector_find_mismatch().

◆ bit_sub() [1/2]

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

2 operand logical SUB(AND NOT). Also known as MINUS.

Parameters
bv- argument vector.

Definition at line 1739 of file bm.h.

◆ bit_sub() [2/2]

template<class Alloc >
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

Parameters
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()
See also
optimize, bit_sub

Definition at line 5125 of file bm.h.

Referenced by bm::bvector<>::bit_sub(), bm::bvector<>::clear(), DemoSUB(), main(), bm::operator-(), and bm::bvector<>::operator-=().

◆ bit_xor() [1/2]

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

2 operand logical XOR

Parameters
bv- argument vector.

Definition at line 1729 of file bm.h.

◆ bit_xor() [2/2]

template<class Alloc >
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

Parameters
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()
See also
optimize, bit_xor

Definition at line 4920 of file bm.h.

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

◆ build_rs_index()

template<typename Alloc >
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)

Parameters
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
See also
count_to, select, find_rank

Definition at line 2304 of file bm.h.

Referenced by bv_count_range_acc(), bv_count_to_acc(), and bv_count_to_range_acc().

◆ calc_stat()

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

Calculates bitvector statistics.

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

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

See also
statistics
Examples
xsample01.cpp.

Definition at line 3407 of file bm.h.

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

◆ clear() [1/2]

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

Clears every bit in the bitvector.

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

Definition at line 1233 of file bm.h.

◆ clear() [2/2]

template<class Alloc >
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.

Parameters
ids- pointer on array of indexes to set
ids_size- size of the input (ids)
so- sort order (use BM_SORTED for faster load)
See also
set, keep
Examples
xsample07a.cpp.

Definition at line 3560 of file bm.h.

Referenced by bm::bvector<>::build_rs_index(), bv_count_and(), bm::bvector<>::combine_operation_and(), compute_seq_group_union(), bm::bvector<>::copy_range(), DemoSUB(), CSeqClusters::elect_leaders(), bm::bvector<>::keep(), main(), bm::bvector<>::reset(), speed_test_bv_index(), speed_test_bvs_index(), speed_test_sv_index(), speed_test_vect_index(), and CSeqClusters::union_all_groups().

◆ clear_bit()

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

Clears bit n.

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

Definition at line 1219 of file bm.h.

◆ clear_bit_no_check()

template<class Alloc >
void bm::bvector< Alloc >::clear_bit_no_check ( size_type  n)
inline

Clears bit n without precondiion checks.

Parameters
n- bit's index to be cleaned.

Definition at line 1225 of file bm.h.

Referenced by bm::basic_bmatrix< bm::bvector<> >::set_octet(), and bm::sparse_vector< unsigned, bm::bvector<> >::set_value_no_null().

◆ clear_range()

template<class Alloc >
void bm::bvector< Alloc >::clear_range ( size_type  left,
size_type  right 
)
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.

Parameters
left- interval start
right- interval end (closed interval)
See also
set_range

Definition at line 1188 of file bm.h.

Referenced by main().

◆ combine_operation()

template<class Alloc >
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 5543 of file bm.h.

Referenced by DemoAND(), DemoOR(), DemoSUB(), and DemoXOR().

◆ combine_operation_and()

template<class Alloc >
void bm::bvector< Alloc >::combine_operation_and ( const bm::bvector< Alloc > &  bvect,
optmode  opt_mode 
)

perform a set-algebra operation AND

Definition at line 5391 of file bm.h.

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

◆ combine_operation_or()

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

perform a set-algebra operation OR

Definition at line 5220 of file bm.h.

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

◆ combine_operation_sub()

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

perform a set-algebra operation MINUS (AND NOT)

Definition at line 5479 of file bm.h.

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

◆ combine_operation_with_block()

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

◆ combine_operation_xor()

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

perform a set-algebra operation XOR

Definition at line 5292 of file bm.h.

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

◆ compare()

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

Lexicographical comparison with a bitvector.

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

Returns
0 if this == arg, -1 if this < arg, 1 if this > arg
See also
find_first_mismatch
Examples
xsample01.cpp.

Definition at line 3173 of file bm.h.

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

◆ copy_range()

template<class Alloc >
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].

Parameters
bvect- source bit-vector
left- interval start
right- interval end (closed interval)

Definition at line 6667 of file bm.h.

Referenced by main().

◆ count()

template<typename Alloc >
bvector< Alloc >::size_type bm::bvector< Alloc >::count

◆ count_blocks()

template<typename Alloc >
bvector< Alloc >::block_idx_type bm::bvector< Alloc >::count_blocks ( unsigned *  arr) const

Computes bitcount values for all bvector blocks.

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

Definition at line 2419 of file bm.h.

◆ count_range() [1/2]

template<typename Alloc >
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].

Parameters
left- index of first bit start counting from
right- index of last bit
Returns
population count in the diapason

Definition at line 2703 of file bm.h.

◆ count_range() [2/2]

template<typename Alloc >
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.

Parameters
left- index of first bit start counting from
right- index of last bit
rs_idx- block count structure to accelerate search
See also
build_rs_index
Returns
population count in the diapason

Definition at line 2973 of file bm.h.

Referenced by bv_count_range(), bv_count_range_acc(), and CSeqClusters::elect_leaders().

◆ count_to()

template<typename Alloc >
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.

Parameters
n- index of bit to rank
rs_idx- rank-select to accelerate search should be prepared using build_rs_index
Returns
population count in the range [0..n]
See also
build_rs_index
count_to_test, select, rank, rank_corrected

Definition at line 2547 of file bm.h.

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

◆ count_to_test()

template<typename Alloc >
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()

Parameters
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()
Returns
population count in the diapason or 0 if right bit test failed
See also
build_rs_index
count_to

Definition at line 2601 of file bm.h.

◆ end()

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

Returns enumerator pointing on the next bit after the last.

Definition at line 1790 of file bm.h.

Referenced by combine_or_test(), main(), speed_test_sv_index(), and speed_test_vect_index().

◆ equal()

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

Equal comparison with an agr bit-vector.

Returns
true if vectors are identical

Definition at line 1897 of file bm.h.

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

◆ erase()

template<class Alloc >
void bm::bvector< Alloc >::erase ( size_type  n)

Erase bit in the specified position All the vector content after erase position is shifted left.

Parameters
n- index of the bit to insert

Definition at line 4569 of file bm.h.

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

◆ extract_next()

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

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

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

Definition at line 1564 of file bm.h.

Referenced by main().

◆ find() [1/2]

template<class Alloc >
bool bm::bvector< Alloc >::find ( size_type pos) const

Finds index of first 1 bit.

Parameters
pos- [out] index of the found 1 bit
Returns
true if search returned result
See also
get_first, get_next, extract_next, find_reverse, find_first_mismatch

Definition at line 4049 of file bm.h.

Referenced by bm::bvector<>::find(), bm::bvector<>::find_first_mismatch(), bm::bvector<>::find_range(), and main().

◆ find() [2/2]

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

Find index of 1 bit starting from position.

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

Definition at line 3977 of file bm.h.

◆ find_first_mismatch()

template<typename Alloc >
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.

Parameters
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)
Returns
true if didfference found, false - both vectors are equivalent
See also
compare

Definition at line 3291 of file bm.h.

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

◆ find_range()

template<class Alloc >
bool bm::bvector< Alloc >::find_range ( size_type first,
size_type last 
) const

Finds dynamic range of bit-vector [first, last].

Parameters
first- index of the first found 1 bit
last- index of the last found 1 bit
Returns
true if search returned result
See also
get_first, get_next, extract_next, find, find_reverse

Definition at line 4095 of file bm.h.

Referenced by main().

◆ find_rank() [1/2]

template<class Alloc >
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.

Parameters
rank- rank to find (bitcount)
from- start positioon for rank search
pos- position with speciefied rank (relative to from position)
Returns
true if requested rank was found

Definition at line 4115 of file bm.h.

◆ find_rank() [2/2]

template<class Alloc >
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.

Parameters
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)
See also
build_rs_index, select
Returns
true if requested rank was found

Definition at line 4168 of file bm.h.

◆ find_reverse()

template<class Alloc >
bool bm::bvector< Alloc >::find_reverse ( size_type pos) const

Finds last index of 1 bit.

Parameters
pos- index of the last found 1 bit
Returns
true if search returned result
See also
get_first, get_next, extract_next, find, find_first_mismatch

Definition at line 3992 of file bm.h.

Referenced by bm::bvector<>::build_rs_index(), bm::bvector<>::clear(), bm::bvector<>::find_range(), bm::bvector<>::keep(), main(), and bm::bvector<>::sync_size().

◆ first()

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

◆ flip() [1/2]

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

Flips all bits.

Returns
*this
See also
invert

Definition at line 1252 of file bm.h.

◆ flip() [2/2]

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

Flips bit n.

Returns
*this

Definition at line 1245 of file bm.h.

◆ forget_count()

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

Disables count cache. (deprecated).

Definition at line 1434 of file bm.h.

◆ get_allocator()

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

Definition at line 1030 of file bm.h.

◆ get_allocator_pool()

template<class Alloc >
allocator_pool_type* bm::bvector< Alloc >::get_allocator_pool ( )
inline

Get curent allocator pool (if set)

Returns
pointer to the current pool or NULL

Definition at line 1041 of file bm.h.

◆ get_bit()

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

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

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

Definition at line 3051 of file bm.h.

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

◆ get_blocks_manager() [1/2]

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

get access to memory manager (internal) Use only if you are BitMagic library

Definition at line 1946 of file bm.h.

◆ get_blocks_manager() [2/2]

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

get access to memory manager (internal) Use only if you are BitMagic library

Definition at line 1938 of file bm.h.

Referenced by bm::bvector<>::bit_and(), bm::bvector<>::bit_or(), bm::bvector<>::bit_sub(), bm::bvector<>::bit_xor(), and bm::basic_bmatrix< bm::bvector<> >::optimize_block().

◆ get_enumerator()

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

Returns enumerator pointing on specified or the next available bit.

Definition at line 1796 of file bm.h.

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

◆ get_first()

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

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

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

Definition at line 1545 of file bm.h.

Referenced by bm::bvector_mini< A >::compare(), print_bvector(), and CSeqClusters::take_group().

◆ get_new_blocks_strat()

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

Returns blocks allocation strategy.

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

Definition at line 1832 of file bm.h.

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

◆ get_next()

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

Finds the number of the next bit ON.

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

Definition at line 1554 of file bm.h.

Referenced by bm::bvector_mini< A >::compare(), and print_bvector().

◆ import()

template<class Alloc >
void bm::bvector< Alloc >::import ( const size_type ids,
size_type  ids_size,
bm::sort_order  sorted_idx 
)
protected

◆ import_block()

template<class Alloc >
void bm::bvector< Alloc >::import_block ( const size_type ids,
block_idx_type  nblock,
size_type  start,
size_type  stop 
)
protected

Definition at line 3699 of file bm.h.

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

◆ inc()

template<class Alloc >
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)

Parameters
n- index of the bit to be set
Returns
TRUE if carry over created (1+1)

Definition at line 3814 of file bm.h.

Referenced by bm::bvector<>::flip(), and bm::sparse_vector< unsigned, bm::bvector<> >::inc_no_null().

◆ init()

template<typename Alloc >
void bm::bvector< Alloc >::init

◆ insert()

template<class Alloc >
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.

Parameters
n- index of the bit to insert
value- insert value
Returns
Carry over bit value (1 or 0)

Definition at line 4392 of file bm.h.

Referenced by bm::basic_bmatrix< bm::bvector<> >::insert_octet(), bm::sparse_vector< unsigned, bm::bvector<> >::insert_value_no_null(), and bm::bvector<>::shift_right().

◆ inserter()

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

Function erturns insert iterator for this bitvector

Definition at line 1259 of file bm.h.

Referenced by main().

◆ invert()

template<typename Alloc >
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 3001 of file bm.h.

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

◆ is_all_one_range()

template<typename Alloc >
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].

Parameters
left- index of first bit start checking
right- index of last bit
Returns
true if all bits are 1, false otherwise
See also
any_range, count_range

Definition at line 2795 of file bm.h.

Referenced by main().

◆ is_init()

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

Return true if bvector is initialized at all.

Definition at line 1872 of file bm.h.

◆ keep()

template<class Alloc >
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.

Parameters
ids- pointer on array of indexes to set
ids_size- size of the input (ids)
so- sort order (use BM_SORTED for faster load)
See also
set, clear

Definition at line 3532 of file bm.h.

Referenced by DemoAND().

◆ keep_range()

template<class Alloc >
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.

Parameters
left- interval start
right- interval end (closed interval)
See also
set_range

Definition at line 2159 of file bm.h.

Referenced by main().

◆ merge()

template<class Alloc >
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.

Parameters
bvect- [in, out] - source vector (NOT immutable)

Definition at line 4738 of file bm.h.

Referenced by CKMerAcc::add(), DemoOR(), and bm::sparse_vector< unsigned, bm::bvector<> >::merge().

◆ move_from()

template<typename Alloc >
void bm::bvector< Alloc >::move_from ( bvector< Alloc > &  bvect)

Move bvector content from another bvector.

Definition at line 2146 of file bm.h.

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

◆ none()

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

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

Definition at line 1508 of file bm.h.

◆ operator!=()

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

Definition at line 1026 of file bm.h.

◆ operator&=()

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

Definition at line 1016 of file bm.h.

◆ operator-=()

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

Definition at line 1019 of file bm.h.

◆ operator<()

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

Definition at line 1021 of file bm.h.

◆ operator<=()

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

Definition at line 1022 of file bm.h.

◆ operator=() [1/2]

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

Move assignment operator.

Definition at line 971 of file bm.h.

◆ operator=() [2/2]

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

Copy assignment operator.

Definition at line 929 of file bm.h.

◆ operator==()

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

Definition at line 1025 of file bm.h.

◆ operator>()

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

Definition at line 1023 of file bm.h.

◆ operator>=()

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

Definition at line 1024 of file bm.h.

◆ operator[]() [1/2]

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

Definition at line 1000 of file bm.h.

◆ operator[]() [2/2]

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

Definition at line 1010 of file bm.h.

◆ operator^=()

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

Definition at line 1017 of file bm.h.

◆ operator|=()

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

Definition at line 1018 of file bm.h.

◆ operator~()

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

Definition at line 1028 of file bm.h.

◆ optimize()

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

Optimize memory bitvector's memory allocation.

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

Optionally function can calculate vector post optimization statistics

See also
optmode, optimize_gap_size
Examples
xsample01.cpp.

Definition at line 3085 of file bm.h.

Referenced by compute_seq_group_union(), generate_bvector(), generate_k_mers(), 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().

◆ optimize_gap_size()

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

Optimize sizes of GAP blocks.

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

Definition at line 3131 of file bm.h.

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::optimize_gap_size().

◆ rank()

template<class Alloc >
size_type bm::bvector< Alloc >::rank ( size_type  n,
const rs_index_type rs_idx 
) const
inline

Returns rank of specified bit position (same as count_to())

Parameters
n- index of bit to rank
rs_idx- rank-select index
Returns
population count in the range [0..n]
See also
build_rs_index
count_to_test, select, rank, rank_corrected

Definition at line 1385 of file bm.h.

Referenced by bm::bvector< Alloc >::enumerator::skip(), and bm::bvector< Alloc >::enumerator::skip_to_rank().

◆ rank_corrected()

template<typename Alloc >
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().

Parameters
n- index of bit to rank
rs_idx- rank-select index
Returns
population count in the range [0..n] corrected as -1 by the value of n
See also
build_rs_index
count_to_test, select, rank

Definition at line 2658 of file bm.h.

◆ recalc_count()

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

Recalculate bitcount (deprecated)

Definition at line 1429 of file bm.h.

◆ reset()

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

Clears every bit in the bitvector.

Returns
*this;

Definition at line 1239 of file bm.h.

Referenced by bv_set_bit_test(), and generate_test_set().

◆ resize()

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

◆ select()

template<class Alloc >
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.

Parameters
rank- rank to find (bitcount)
pos- position with speciefied rank (relative to from position) [out]
rs_idx- block count structure to accelerate rank search
See also
running_count_blocks, find_rank
Returns
true if requested rank was found

Definition at line 4239 of file bm.h.

Referenced by main().

◆ set() [1/3]

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

Sets every bit in this bitset to 1.

Returns
*this

Definition at line 3586 of file bm.h.

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

◆ set() [2/3]

template<class Alloc >
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.

Parameters
ids- pointer on array of indexes to set
ids_size- size of the input (ids)
so- sort order (use BM_SORTED for faster load)
See also
keep, clear

Definition at line 3517 of file bm.h.

◆ set() [3/3]

template<class Alloc >
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.

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

Definition at line 3595 of file bm.h.

Referenced by CKMerAcc::add(), bm::bvector<>::build_rs_index(), bvector_bulk_set_test(), bm::sparse_vector< unsigned, bm::bvector<> >::clear(), DemoOR(), CSeqClusters::elect_leaders(), fill_bvector(), generate_bvector(), bm::sparse_vector< unsigned, bm::bvector<> >::import(), main(), pick_benchmark_set(), and run_benchmark().

◆ set_allocator_pool()

template<class Alloc >
void bm::bvector< Alloc >::set_allocator_pool ( allocator_pool_type pool_ptr)
inline

Set allocator pool for local (non-th readed) memory cyclic(lots of alloc-free ops) opertations.

Definition at line 1036 of file bm.h.

Referenced by assign_to_best_cluster(), and assign_to_best_cluster_union().

◆ set_bit()

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

Sets bit n.

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

Definition at line 3631 of file bm.h.

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

◆ set_bit_and()

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

Sets bit n using bit AND with the provided value.

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

Definition at line 3618 of file bm.h.

◆ set_bit_conditional()

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

Sets bit n only if current value equals the condition.

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

Definition at line 3604 of file bm.h.

◆ set_bit_no_check() [1/2]

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

◆ set_bit_no_check() [2/2]

template<class Alloc >
bool bm::bvector< Alloc >::set_bit_no_check ( size_type  n,
bool  val 
)

Set specified bit without checking preconditions (size, etc)

Definition at line 3730 of file bm.h.

◆ set_gap_levels()

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

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

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

Definition at line 3157 of file bm.h.

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

◆ set_new_blocks_strat()

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

Sets new blocks allocation strategy.

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

Definition at line 1824 of file bm.h.

Referenced by main().

◆ set_range()

template<typename Alloc >
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.

Parameters
left- interval start
right- interval end (closed interval)
value- value to set interval in
Returns
*this
See also
clear_range
Examples
strsvsample05.cpp.

Definition at line 2172 of file bm.h.

Referenced by add_object(), bv_count_and(), bm::bvector<>::clear_range(), bm::bvector<>::combine_operation(), compute_jaccard_clusters(), generate_bvector(), bm::sparse_vector< unsigned, bm::bvector<> >::import(), bm::sparse_vector< unsigned, bm::bvector<> >::join(), main(), bm::sparse_vector< unsigned, bm::bvector<> >::merge(), bm::bvector<>::resize(), bm::bvector<>::set(), and bm::bvector<>::set_range().

◆ shift_left()

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

Shift left by 1 bit, fill with zero return carry out.

Returns
Carry over bit value (1 or 0)

Definition at line 4382 of file bm.h.

◆ shift_right()

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

Shift right by 1 bit, fill with zero return carry out.

Returns
Carry over bit value (1 or 0)

Definition at line 4374 of file bm.h.

Referenced by DNA_FingerprintScanner::Find().

◆ size()

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

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

return current size of the vector (bits)

Definition at line 1272 of file bm.h.

Referenced by generate_k_mers(), bm::bvector< Alloc >::insert_iterator::operator=(), bm::bvector<>::operator=(), print_bvector(), run_benchmark(), and bm::sparse_vector_find_mismatch().

◆ swap()

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

Exchanges content of bv and this bvector.

Examples
xsample07a.cpp.

Definition at line 3395 of file bm.h.

Referenced by main(), and CSeqClusters::take_group().

◆ sync_size()

template<typename Alloc >
void bm::bvector< Alloc >::sync_size
protected

Syncronize size if it got extended due to bulk import.

Definition at line 2291 of file bm.h.

Referenced by bm::bvector< Alloc >::bulk_insert_iterator::flush(), and bm::bvector<>::set().

◆ test()

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

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

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

Definition at line 1454 of file bm.h.

Referenced by bm::bvector<>::any_range(), compute_group(), bm::bvector<>::count_range(), CSeqClusters::elect_leaders(), bm::bvector<>::erase(), bm::bvector<>::is_all_one_range(), load_snp_report(), main(), pick_benchmark_set(), and bm::bvector<>::shift_left().

◆ throw_bad_alloc()

template<class Alloc >
void bm::bvector< Alloc >::throw_bad_alloc
static

Definition at line 6744 of file bm.h.

Friends And Related Function Documentation

◆ aggregator

template<class Alloc >
template<class BV >
friend class aggregator
friend

Definition at line 824 of file bm.h.

◆ enumerator

template<class Alloc >
friend class enumerator
friend

Definition at line 823 of file bm.h.

Referenced by bm::bvector<>::end(), and bm::bvector<>::get_enumerator().

◆ iterator_base

template<class Alloc >
friend class iterator_base
friend

Definition at line 822 of file bm.h.

◆ operation_deserializer

template<class Alloc >
template<class BV >
friend class operation_deserializer
friend

Definition at line 825 of file bm.h.


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