BitMagic-C++
|
algorithms for sparse_vector scan/search More...
#include <bmsparsevec_algo.h>
Public Types | |
typedef SV::bvector_type | bvector_type |
typedef const bvector_type * | bvector_type_const_ptr |
typedef bvector_type * | bvector_type_ptr |
typedef SV::value_type | value_type |
typedef SV::size_type | size_type |
typedef bvector_type::allocator_type | allocator_type |
typedef allocator_type::allocator_pool_type | allocator_pool_type |
Public Member Functions | |
sparse_vector_scanner () | |
void | bind (const SV &sv, bool sorted) |
bind sparse vector for all searches | |
void | reset_binding () BMNOEXCEPT |
reset sparse vector binding | |
void | find_eq (const SV &sv, typename SV::value_type value, typename SV::bvector_type &bv_out) |
find all sparse vector elements EQ to search value | |
bool | find_eq (const SV &sv, typename SV::value_type value, typename SV::size_type &pos) |
find first sparse vector element | |
bool | find_eq_str (const SV &sv, const typename SV::value_type *str, typename SV::size_type &pos) |
find first sparse vector element (string) | |
bool | find_eq_str (const typename SV::value_type *str, typename SV::size_type &pos) |
binary find first sparse vector element (string) Sparse vector must be attached (bind()) | |
bool | bfind_eq_str (const SV &sv, const typename SV::value_type *str, typename SV::size_type &pos) |
binary find first sparse vector element (string) Sparse vector must be sorted. | |
bool | lower_bound (const SV &sv, const typename SV::value_type val, typename SV::size_type &pos) |
lower bound search for an array position | |
bool | lower_bound_str (const SV &sv, const typename SV::value_type *str, typename SV::size_type &pos) |
lower bound search for an array position | |
bool | bfind_eq_str (const typename SV::value_type *str, typename SV::size_type &pos) |
binary find first sparse vector element (string) Sparse vector must be sorted and attached | |
void | find_zero (const SV &sv, typename SV::bvector_type &bv_out) |
find all sparse vector elements EQ to 0 | |
void | find_nonzero (const SV &sv, typename SV::bvector_type &bv_out) |
Find non-zero elements Output vector is computed as a logical OR (join) of all plains. | |
void | invert (const SV &sv, typename SV::bvector_type &bv_out) |
invert search result ("EQ" to "not EQ") | |
template<typename It > | |
void | find_eq (const SV &sv, It start, It end, typename SV::bvector_type &bv_out) |
find all values A IN (C, D, E, F) | |
void | find_eq_with_nulls_horizontal (const SV &sv, typename SV::value_type value, typename SV::bvector_type &bv_out) |
For testing purposes only. | |
void | correct_nulls (const SV &sv, typename SV::bvector_type &bv_out) |
Exclude possible NULL values from the result vector. | |
Protected Types | |
enum | vector_capacity { max_columns = SV::max_vector_size } |
enum | search_algo_params { linear_cutoff1 = 16 , linear_cutoff2 = 128 } |
typedef bm::dynamic_heap_matrix< value_type, allocator_type > | heap_matrix_type |
typedef bm::heap_matrix< typename SV::value_type, linear_cutoff2, SV::sv_octet_plains, allocator_type > | matrix_search_buf_type |
Protected Member Functions | |
void | set_search_range (size_type from, size_type to) |
set search boundaries (hint for the aggregator) | |
void | reset_search_range () |
reset (disable) search range | |
bool | find_eq_with_nulls (const SV &sv, typename SV::value_type value, typename SV::bvector_type &bv_out, typename SV::size_type search_limit=0) |
find value (may include NULL indexes) | |
bool | find_first_eq (const SV &sv, typename SV::value_type value, size_type &idx) |
find first value (may include NULL indexes) | |
bool | find_first_eq (const SV &sv, const typename SV::value_type *str, size_type &idx, bool remaped) |
find first string value (may include NULL indexes) | |
bool | prepare_and_sub_aggregator (const SV &sv, typename SV::value_type value) |
Prepare aggregator for AND-SUB (EQ) search. | |
bool | prepare_and_sub_aggregator (const SV &sv, const typename SV::value_type *str, unsigned octet_start) |
Prepare aggregator for AND-SUB (EQ) search (string) | |
void | decompress (const SV &sv, typename SV::bvector_type &bv_out) |
Rank-Select decompression for RSC vectors. | |
int | compare_str (const SV &sv, size_type idx, const value_type *str) |
compare sv[idx] with input str | |
int | compare (const SV &sv, size_type idx, const value_type val) BMNOEXCEPT |
compare sv[idx] with input value | |
sparse_vector_scanner (const sparse_vector_scanner &)=delete | |
void | operator= (const sparse_vector_scanner &)=delete |
algorithms for sparse_vector scan/search
Scanner uses properties of bit-vector plains to answer questions like "find all sparse vector elements equivalent to XYZ".
Class uses fast algorithms based on properties of bit-plains. This is NOT a brute force, direct scan.
Definition at line 481 of file bmsparsevec_algo.h.
typedef allocator_type::allocator_pool_type bm::sparse_vector_scanner< SV >::allocator_pool_type |
Definition at line 491 of file bmsparsevec_algo.h.
typedef bvector_type::allocator_type bm::sparse_vector_scanner< SV >::allocator_type |
Definition at line 490 of file bmsparsevec_algo.h.
typedef SV::bvector_type bm::sparse_vector_scanner< SV >::bvector_type |
Definition at line 484 of file bmsparsevec_algo.h.
typedef const bvector_type* bm::sparse_vector_scanner< SV >::bvector_type_const_ptr |
Definition at line 485 of file bmsparsevec_algo.h.
typedef bvector_type* bm::sparse_vector_scanner< SV >::bvector_type_ptr |
Definition at line 486 of file bmsparsevec_algo.h.
|
protected |
Definition at line 732 of file bmsparsevec_algo.h.
|
protected |
Definition at line 736 of file bmsparsevec_algo.h.
typedef SV::size_type bm::sparse_vector_scanner< SV >::size_type |
Definition at line 488 of file bmsparsevec_algo.h.
typedef SV::value_type bm::sparse_vector_scanner< SV >::value_type |
Definition at line 487 of file bmsparsevec_algo.h.
|
protected |
Enumerator | |
---|---|
linear_cutoff1 | |
linear_cutoff2 |
Definition at line 726 of file bmsparsevec_algo.h.
|
protected |
Enumerator | |
---|---|
max_columns |
Definition at line 721 of file bmsparsevec_algo.h.
bm::sparse_vector_scanner< SV >::sparse_vector_scanner | ( | ) |
Definition at line 1106 of file bmsparsevec_algo.h.
References bm::id_max.
|
protecteddelete |
bool bm::sparse_vector_scanner< SV >::bfind_eq_str | ( | const SV & | sv, |
const typename SV::value_type * | str, | ||
typename SV::size_type & | pos | ||
) |
binary find first sparse vector element (string)
Sparse vector must be sorted.
Definition at line 1561 of file bmsparsevec_algo.h.
References BM_ASSERT, bm::gap_max_bits, bm::set_block_shift, and bm::sub_block3_size.
Referenced by run_benchmark().
bool bm::sparse_vector_scanner< SV >::bfind_eq_str | ( | const typename SV::value_type * | str, |
typename SV::size_type & | pos | ||
) |
binary find first sparse vector element (string) Sparse vector must be sorted and attached
Definition at line 1711 of file bmsparsevec_algo.h.
References BM_ASSERT.
void bm::sparse_vector_scanner< SV >::bind | ( | const SV & | sv, |
bool | sorted | ||
) |
bind sparse vector for all searches
sv | - input sparse vector to bind for searches |
sorted | - source index is sorted, build index for binary search |
Definition at line 1118 of file bmsparsevec_algo.h.
References BM_ASSERT, bm::gap_max_bits, bm::set_block_shift, and bm::sub_block3_size.
Referenced by run_benchmark().
|
protected |
compare sv[idx] with input value
Definition at line 2022 of file bmsparsevec_algo.h.
|
protected |
compare sv[idx] with input str
Definition at line 1971 of file bmsparsevec_algo.h.
References BM_ASSERT, bm::set_block_mask, bm::set_block_shift, and bm::sub_block3_size.
void bm::sparse_vector_scanner< SV >::correct_nulls | ( | const SV & | sv, |
typename SV::bvector_type & | bv_out | ||
) |
Exclude possible NULL values from the result vector.
sv | - input sparse vector |
bv_out | - output bit-bector of non-zero elements |
Definition at line 1217 of file bmsparsevec_algo.h.
Referenced by bm::sparse_vector_scanner< SV >::find_eq().
|
protected |
Rank-Select decompression for RSC vectors.
Definition at line 2099 of file bmsparsevec_algo.h.
References BM_ASSERT.
|
inline |
find all values A IN (C, D, E, F)
sv | - input sparse vector |
start | - start iterator (set to search) |
end | - end iterator (set to search) |
bv_out | - output bit-bector of non-zero elements |
Definition at line 631 of file bmsparsevec_algo.h.
References bm::bvector< Alloc >::mem_pool_guard::assign_if_not_set(), BM_ASSERT, bm::sparse_vector_scanner< SV >::correct_nulls(), and bm::sparse_vector_scanner< SV >::find_eq_with_nulls().
void bm::sparse_vector_scanner< SV >::find_eq | ( | const SV & | sv, |
typename SV::value_type | value, | ||
typename SV::bvector_type & | bv_out | ||
) |
find all sparse vector elements EQ to search value
Find all sparse vector elements equivalent to specified value
sv | - input sparse vector |
value | - value to search for |
bv_out | - output bit-vector (search result masks 1 elements) |
Definition at line 2033 of file bmsparsevec_algo.h.
Referenced by main(), and run_benchmark().
bool bm::sparse_vector_scanner< SV >::find_eq | ( | const SV & | sv, |
typename SV::value_type | value, | ||
typename SV::size_type & | pos | ||
) |
find first sparse vector element
Find all sparse vector elements equivalent to specified value. Works well if sperse vector represents unordered set
sv | - input sparse vector |
value | - value to search for |
pos | - output found sparse vector element index |
Definition at line 2057 of file bmsparsevec_algo.h.
bool bm::sparse_vector_scanner< SV >::find_eq_str | ( | const SV & | sv, |
const typename SV::value_type * | str, | ||
typename SV::size_type & | pos | ||
) |
find first sparse vector element (string)
Definition at line 1515 of file bmsparsevec_algo.h.
Referenced by run_benchmark().
bool bm::sparse_vector_scanner< SV >::find_eq_str | ( | const typename SV::value_type * | str, |
typename SV::size_type & | pos | ||
) |
binary find first sparse vector element (string) Sparse vector must be attached (bind())
Definition at line 1505 of file bmsparsevec_algo.h.
References BM_ASSERT.
|
protected |
find value (may include NULL indexes)
Definition at line 1228 of file bmsparsevec_algo.h.
Referenced by bm::sparse_vector_scanner< SV >::find_eq().
void bm::sparse_vector_scanner< SV >::find_eq_with_nulls_horizontal | ( | const SV & | sv, |
typename SV::value_type | value, | ||
typename SV::bvector_type & | bv_out | ||
) |
For testing purposes only.
Definition at line 1452 of file bmsparsevec_algo.h.
References bm::bitscan(), and BM_ASSERT.
|
protected |
find first string value (may include NULL indexes)
Definition at line 1283 of file bmsparsevec_algo.h.
References BM_ASSERT.
|
protected |
find first value (may include NULL indexes)
Definition at line 1259 of file bmsparsevec_algo.h.
References BM_ASSERT.
void bm::sparse_vector_scanner< SV >::find_nonzero | ( | const SV & | sv, |
typename SV::bvector_type & | bv_out | ||
) |
Find non-zero elements Output vector is computed as a logical OR (join) of all plains.
sv | - input sparse vector |
bv_out | - output bit-bector of non-zero elements |
Definition at line 2086 of file bmsparsevec_algo.h.
void bm::sparse_vector_scanner< SV >::find_zero | ( | const SV & | sv, |
typename SV::bvector_type & | bv_out | ||
) |
find all sparse vector elements EQ to 0
sv | - input sparse vector |
bv_out | - output bit-vector (search result masks 1 elements) |
Definition at line 1170 of file bmsparsevec_algo.h.
References bm::id_max.
Referenced by bm::set2set_11_transform< SV >::attach_sv().
void bm::sparse_vector_scanner< SV >::invert | ( | const SV & | sv, |
typename SV::bvector_type & | bv_out | ||
) |
invert search result ("EQ" to "not EQ")
sv | - input sparse vector |
bv_out | - output bit-bector of non-zero elements |
Definition at line 1195 of file bmsparsevec_algo.h.
References bm::id_max.
Referenced by main().
bool bm::sparse_vector_scanner< SV >::lower_bound | ( | const SV & | sv, |
const typename SV::value_type | val, | ||
typename SV::size_type & | pos | ||
) |
lower bound search for an array position
Method assumes the sparse array is sorted
sv | - input sparse vector |
val | - value to search for |
pos | - output sparse vector element index |
Definition at line 1721 of file bmsparsevec_algo.h.
References BM_ASSERT.
Referenced by insertion_sort().
bool bm::sparse_vector_scanner< SV >::lower_bound_str | ( | const SV & | sv, |
const typename SV::value_type * | str, | ||
typename SV::size_type & | pos | ||
) |
lower bound search for an array position
Method assumes the sparse array is sorted
sv | - input sparse vector |
str | - value to search for |
pos | - output sparse vector element index |
Definition at line 1841 of file bmsparsevec_algo.h.
References BM_ASSERT.
Referenced by insertion_sort().
|
protecteddelete |
|
protected |
Prepare aggregator for AND-SUB (EQ) search (string)
Definition at line 1331 of file bmsparsevec_algo.h.
References bm::bitscan(), BM_ASSERT, and bm::word_bitcount().
|
protected |
Prepare aggregator for AND-SUB (EQ) search.
Definition at line 1415 of file bmsparsevec_algo.h.
References bm::bitscan(), and BM_ASSERT.
void bm::sparse_vector_scanner< SV >::reset_binding | ( | ) |
reset sparse vector binding
Definition at line 1161 of file bmsparsevec_algo.h.
|
protected |
reset (disable) search range
Definition at line 2126 of file bmsparsevec_algo.h.
References bm::id_max.
|
protected |
set search boundaries (hint for the aggregator)
Definition at line 2115 of file bmsparsevec_algo.h.
References BM_ASSERT.