BitMagic-C++
|
Topics | |
Binary-distance metrics | |
Data Structures | |
class | bm::rank_compressor< BV > |
Algorithms for rank compression of bit-vector. More... | |
class | bm::aggregator< BV > |
Algorithms for fast aggregation of a group of bit-vectors. More... | |
class | bm::random_subset< BV > |
class | bm::sparse_vector_scanner< SV > |
algorithms for sparse_vector scan/search More... | |
class | bm::set2set_11_transform< SV > |
Integer set to set transformation (functional image in groups theory) https://en.wikipedia.org/wiki/Image_(mathematics) More... | |
Functions | |
template<class BV > | |
BV::size_type | bm::count_and (const BV &bv1, const BV &bv2) BMNOEXCEPT |
Computes bitcount of AND operation of two bitsets. | |
template<class BV > | |
BV::size_type | bm::any_and (const BV &bv1, const BV &bv2) BMNOEXCEPT |
Computes if there is any bit in AND operation of two bitsets. | |
template<class BV > | |
bm::distance_metric_descriptor::size_type | bm::count_xor (const BV &bv1, const BV &bv2) BMNOEXCEPT |
Computes bitcount of XOR operation of two bitsets. | |
template<class BV > | |
BV::size_type | bm::any_xor (const BV &bv1, const BV &bv2) BMNOEXCEPT |
Computes if there is any bit in XOR operation of two bitsets. | |
template<class BV > | |
BV::size_type | bm::count_sub (const BV &bv1, const BV &bv2) BMNOEXCEPT |
Computes bitcount of SUB operation of two bitsets. | |
template<class BV > | |
BV::size_type | bm::any_sub (const BV &bv1, const BV &bv2) BMNOEXCEPT |
Computes if there is any bit in SUB operation of two bitsets. | |
template<class BV > | |
BV::size_type | bm::count_or (const BV &bv1, const BV &bv2) BMNOEXCEPT |
Computes bitcount of OR operation of two bitsets. | |
template<class BV > | |
BV::size_type | bm::any_or (const BV &bv1, const BV &bv2) BMNOEXCEPT |
Computes if there is any bit in OR operation of two bitsets. | |
template<class BV , class Func > | |
void | bm::for_each_bit (const BV &bv, Func &bit_functor) |
bit-vector visitor scanner to traverse each 1 bit using C++ visitor | |
template<class BV , class Func > | |
void | bm::for_each_bit_range (const BV &bv, typename BV::size_type left, typename BV::size_type right, Func &bit_functor) |
bit-vector range visitor to traverse each 1 bit | |
template<class BV > | |
void | bm::visit_each_bit (const BV &bv, void *handle_ptr, bit_visitor_callback_type callback_ptr) |
bvector visitor scanner to traverse each 1 bit using C callback | |
template<class BV > | |
void | bm::visit_each_bit_range (const BV &bv, typename BV::size_type left, typename BV::size_type right, void *handle_ptr, bit_visitor_callback_type callback_ptr) |
bvector visitor scanner to traverse each bits in range (C callback) | |
template<class BV , class It > | |
void | bm::combine_or (BV &bv, It first, It last) |
OR Combine bitvector and the iterable sequence. | |
template<class BV , class It > | |
void | bm::combine_xor (BV &bv, It first, It last) |
XOR Combine bitvector and the iterable sequence. | |
template<class BV , class It > | |
void | bm::combine_sub (BV &bv, It first, It last) |
SUB Combine bitvector and the iterable sequence. | |
template<class BV , class It > | |
void | bm::combine_and_sorted (BV &bv, It first, It last) |
AND Combine bitvector and the iterable sequence. | |
template<class BV , class It > | |
void | bm::combine_and (BV &bv, It first, It last) |
AND Combine bitvector and the iterable sequence. | |
template<class BV > | |
BV::size_type | bm::count_intervals (const BV &bv) |
Compute number of bit intervals (GAPs) in the bitvector. | |
template<typename BV , class It > | |
void | bm::export_array (BV &bv, It first, It last) |
Export bitset from an array of binary data representing the bit vector. | |
template<typename Agg , typename It > | |
void | bm::aggregator_pipeline_execute (It first, It last) |
Experimental method ro run multiple aggregators in sync. | |
Set algebra algorithms using bit-vectors, arrays. Binary metrics and distances. Random sub-sets.
void bm::aggregator_pipeline_execute | ( | It | first, |
It | last ) |
Experimental method ro run multiple aggregators in sync.
Pipeleine algorithm walts the sequence of iterators (pointers on aggregators) and run them all via aggregator<>::run_step() method
first | - iterator (pointer on aggregator) |
last | - iterator (pointer on aggregator) |
Definition at line 481 of file bmaggregator.h.
References bm::set_sub_array_size.
Referenced by DNA_FingerprintScanner::FindCollection().
BV::size_type bm::any_and | ( | const BV & | bv1, |
const BV & | bv2 ) |
Computes if there is any bit in AND operation of two bitsets.
bv1 | - Argument bit-vector. |
bv2 | - Argument bit-vector. |
Definition at line 62 of file bmalgo.h.
References bm::COUNT_AND, bm::distance_operation_any(), and bm::distance_metric_descriptor::result.
BV::size_type bm::any_or | ( | const BV & | bv1, |
const BV & | bv2 ) |
Computes if there is any bit in OR operation of two bitsets.
bv1 | - Argument bit-vector. |
bv2 | - Argument bit-vector. |
Definition at line 165 of file bmalgo.h.
References bm::COUNT_OR, bm::distance_operation_any(), and bm::distance_metric_descriptor::result.
BV::size_type bm::any_sub | ( | const BV & | bv1, |
const BV & | bv2 ) |
Computes if there is any bit in SUB operation of two bitsets.
bv1 | - Argument bit-vector. |
bv2 | - Argument bit-vector. |
Definition at line 132 of file bmalgo.h.
References bm::COUNT_SUB_AB, bm::distance_operation_any(), and bm::distance_metric_descriptor::result.
BV::size_type bm::any_xor | ( | const BV & | bv1, |
const BV & | bv2 ) |
Computes if there is any bit in XOR operation of two bitsets.
bv1 | - Argument bit-vector. |
bv2 | - Argument bit-vector. |
Definition at line 97 of file bmalgo.h.
References bm::COUNT_XOR, bm::distance_operation_any(), and bm::distance_metric_descriptor::result.
void bm::combine_and | ( | BV & | bv, |
It | first, | ||
It | last ) |
AND Combine bitvector and the iterable sequence.
Algorithm combines bvector with sequence of integers (represents another set). When the agrument set is sorted this method can give serious increase in performance.
bv | - destination bitvector |
first | - first element of the iterated sequence |
last | - last element of the iterated sequence |
Definition at line 1301 of file bmalgo_impl.h.
References bm::combine_or().
Referenced by bm::aggregator< BV >::combine_and(), bm::aggregator< BV >::combine_and(), DemoAND(), and main().
void bm::combine_and_sorted | ( | BV & | bv, |
It | first, | ||
It | last ) |
AND Combine bitvector and the iterable sequence.
Algorithm combines bvector with sorted sequence of integers (represents another set).
bv | - destination bitvector |
first | - first element of the iterated sequence |
last | - last element of the iterated sequence |
Definition at line 1269 of file bmalgo_impl.h.
References BM_ASSERT.
Referenced by main().
void bm::combine_or | ( | BV & | bv, |
It | first, | ||
It | last ) |
OR Combine bitvector and the iterable sequence.
Algorithm combines bvector with sequence of integers (represents another set). When the agrument set is sorted this method can give serious increase in performance.
bv | - destination bitvector |
first | - first element of the iterated sequence |
last | - last element of the iterated sequence |
Definition at line 1016 of file bmalgo_impl.h.
References bm::block_range_scan(), BM_ASSERT, BMGAP_PTR, bm::gap_limit(), bm::gap_set_value(), bm::id_max, bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::combine_and(), bm::aggregator< BV >::combine_or(), bm::aggregator< BV >::combine_or(), combine_or_test(), DemoOR(), main(), speed_test_sv_index(), and speed_test_vect_index().
void bm::combine_sub | ( | BV & | bv, |
It | first, | ||
It | last ) |
SUB Combine bitvector and the iterable sequence.
Algorithm combines bvector with sequence of integers (represents another set). When the agrument set is sorted this method can give serious increase in performance.
bv | - destination bitvector |
first | - first element of the iterated sequence |
last | - last element of the iterated sequence |
Definition at line 1184 of file bmalgo_impl.h.
References bm::block_range_scan(), BM_ASSERT, BMGAP_PTR, bm::gap_limit(), bm::gap_set_value(), bm::gap_test_unr(), bm::id_max, bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.
void bm::combine_xor | ( | BV & | bv, |
It | first, | ||
It | last ) |
XOR Combine bitvector and the iterable sequence.
Algorithm combines bvector with sequence of integers (represents another set). When the agrument set is sorted this method can give serious increase in performance.
bv | - destination bitvector |
first | - first element of the iterated sequence |
last | - last element of the iterated sequence |
Definition at line 1097 of file bmalgo_impl.h.
References bm::block_range_scan(), BM_ASSERT, BMGAP_PTR, bm::gap_limit(), bm::gap_set_value(), bm::gap_test_unr(), bm::id_max, bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.
Referenced by DemoXOR().
BV::size_type bm::count_and | ( | const BV & | bv1, |
const BV & | bv2 ) |
Computes bitcount of AND operation of two bitsets.
bv1 | - Argument bit-vector. |
bv2 | - Argument bit-vector. |
Definition at line 49 of file bmalgo.h.
References bm::distance_and_operation().
Referenced by bv_count_and(), and main().
BV::size_type bm::count_intervals | ( | const BV & | bv | ) |
Compute number of bit intervals (GAPs) in the bitvector.
Algorithm traverses bit vector and count number of uninterrupted intervals of 1s and 0s.
For example: empty vector - 1 interval 00001111100000 - gives us 3 intervals 10001111100000 - 4 intervals 00000000000000 - 1 interval 11111111111111 - 1 interval
Definition at line 1325 of file bmalgo_impl.h.
References bm::for_each_block(), and bm::id_max.
BV::size_type bm::count_or | ( | const BV & | bv1, |
const BV & | bv2 ) |
Computes bitcount of OR operation of two bitsets.
bv1 | - Argument bit-vector. |
bv2 | - Argument bit-vector. |
Definition at line 149 of file bmalgo.h.
References bm::COUNT_OR, bm::distance_operation(), and bm::distance_metric_descriptor::result.
BV::size_type bm::count_sub | ( | const BV & | bv1, |
const BV & | bv2 ) |
Computes bitcount of SUB operation of two bitsets.
bv1 | - Argument bit-vector. |
bv2 | - Argument bit-vector. |
Definition at line 115 of file bmalgo.h.
References bm::COUNT_SUB_AB, bm::distance_operation(), and bm::distance_metric_descriptor::result.
bm::distance_metric_descriptor::size_type bm::count_xor | ( | const BV & | bv1, |
const BV & | bv2 ) |
Computes bitcount of XOR operation of two bitsets.
bv1 | - Argument bit-vector. |
bv2 | - Argument bit-vector. |
Definition at line 81 of file bmalgo.h.
References bm::COUNT_XOR, bm::distance_operation(), and bm::distance_metric_descriptor::result.
Referenced by main().
void bm::export_array | ( | BV & | bv, |
It | first, | ||
It | last ) |
Export bitset from an array of binary data representing the bit vector.
Input array can be array of ints, chars or other native C types. Method works with iterators, which makes it compatible with STL containers and C arrays
bv | - destination bitvector |
first | - first element of the iterated sequence |
last | - last element of the iterated sequence |
Definition at line 1359 of file bmalgo_impl.h.
References BM_ASSERT, bm::BM_BIT, bm::set_block_size, and bm::set_total_blocks.
void bm::for_each_bit | ( | const BV & | bv, |
Func & | bit_functor ) |
bit-vector visitor scanner to traverse each 1 bit using C++ visitor
bv | - bit vector to scan |
bit_functor | - visitor: should support add_bits(), add_range() |
Definition at line 200 of file bmalgo.h.
References BM_SCANNER_OP, FULL_BLOCK_FAKE_ADDR, FULL_SUB_BLOCK_REAL_ADDR, bm::set_sub_array_size, and bm::sse42_test_all_zero_wave().
Referenced by bm::rank_compressor< BV >::compress_by_source(), and bm::visit_each_bit().
void bm::for_each_bit_range | ( | const BV & | bv, |
typename BV::size_type | left, | ||
typename BV::size_type | right, | ||
Func & | bit_functor ) |
bit-vector range visitor to traverse each 1 bit
bv | - bit vector to scan |
right | - start of closed interval [from..to] |
left | - end of close interval [from..to] |
bit_functor | - visitor: should support add_bits(), add_range() |
Definition at line 264 of file bmalgo.h.
References BM_ASSERT, bm::for_each_bit_range_no_check(), bm::id_max, and bm::xor_swap().
Referenced by bm::visit_each_bit_range().
void bm::visit_each_bit | ( | const BV & | bv, |
void * | handle_ptr, | ||
bit_visitor_callback_type | callback_ptr ) |
bvector visitor scanner to traverse each 1 bit using C callback
bv | - bit vector to scan |
handle_ptr | - handle to private memory used by callback |
callback_ptr | - callback function |
Definition at line 356 of file bmalgo.h.
References bm::for_each_bit().
void bm::visit_each_bit_range | ( | const BV & | bv, |
typename BV::size_type | left, | ||
typename BV::size_type | right, | ||
void * | handle_ptr, | ||
bit_visitor_callback_type | callback_ptr ) |
bvector visitor scanner to traverse each bits in range (C callback)
bv | - bit vector to scan |
left | - from [left..right] |
right | - to [left..right] |
handle_ptr | - handle to private memory used by callback |
callback_ptr | - callback function |
Definition at line 380 of file bmalgo.h.
References bm::for_each_bit_range().