BitMagic-C++
|
Set algebra algorithms using bit-vectors, arrays. Binary metrics and distances. Random sub-sets. More...
Modules | |
Binary-distance metrics | |
Distance metrics and algorithms to compute binary distances. | |
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/seach 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 , 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 More... | |
template<class BV > | |
void | bm::visit_each_bit (const BV &bv, void *handle_ptr, bit_visitor_callback_type callback_ptr) |
bit-vector visitor scanner to traverse each 1 bit using C callback More... | |
template<class BV , class It > | |
void | bm::combine_or (BV &bv, It first, It last) |
OR Combine bitvector and the iterable sequence. More... | |
template<class BV , class It > | |
void | bm::combine_xor (BV &bv, It first, It last) |
XOR Combine bitvector and the iterable sequence. More... | |
template<class BV , class It > | |
void | bm::combine_sub (BV &bv, It first, It last) |
SUB Combine bitvector and the iterable sequence. More... | |
template<class BV , class It > | |
void | bm::combine_and_sorted (BV &bv, It first, It last) |
AND Combine bitvector and the iterable sequence. More... | |
template<class BV , class It > | |
void | bm::combine_and (BV &bv, It first, It last) |
AND Combine bitvector and the iterable sequence. More... | |
template<class BV > | |
BV::size_type | bm::count_intervals (const BV &bv) |
Compute number of bit intervals (GAPs) in the bitvector. More... | |
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. More... | |
template<typename Agg , typename It > | |
void | bm::aggregator_pipeline_execute (It first, It last) |
Experimental method ro run multiple aggregators in sync. More... | |
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 475 of file bmaggregator.h.
References bm::set_sub_array_size.
Referenced by DNA_FingerprintScanner::FindCollection().
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 1433 of file bmalgo_impl.h.
References bm::combine_or().
Referenced by bm::aggregator< bvector_type >::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 1401 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 1148 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< bvector_type >::combine_or(), combine_or_test(), bm::rank_compressor< bvector_type >::compress(), bm::rank_compressor< bvector_type >::decompress(), 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 1316 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 1229 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_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 1457 of file bmalgo_impl.h.
References bm::for_each_block().
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 1487 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 | (should support add_bits() and add_range() methods |
Definition at line 65 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< bvector_type >::compress_by_source(), bm::sparse_vector< unsigned, bm::bvector<> >::extract(), and bm::visit_each_bit().
void bm::visit_each_bit | ( | const BV & | bv, |
void * | handle_ptr, | ||
bit_visitor_callback_type | callback_ptr | ||
) |
bit-vector 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 131 of file bmalgo.h.
References bm::for_each_bit().