BitMagic-C++

algorithms for sparse_vector scan/search More...

#include <bmsparsevec_algo.h>

Public Types

typedef SV::bvector_type bvector_type
 
typedef const bvector_typebvector_type_const_ptr
 
typedef bvector_typebvector_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_typeheap_matrix_type
 
typedef bm::heap_matrix< typename SV::value_type, linear_cutoff2, SV::sv_octet_plains, allocator_typematrix_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
 

Detailed Description

template<typename SV>
class bm::sparse_vector_scanner< SV >

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.

Examples
strsvsample02.cpp, svsample06.cpp, svsample07.cpp, xsample03.cpp, and xsample05.cpp.

Definition at line 481 of file bmsparsevec_algo.h.

Member Typedef Documentation

◆ allocator_pool_type

template<typename SV >
allocator_type::allocator_pool_type bm::sparse_vector_scanner< SV >::allocator_pool_type

Definition at line 491 of file bmsparsevec_algo.h.

◆ allocator_type

template<typename SV >
bvector_type::allocator_type bm::sparse_vector_scanner< SV >::allocator_type

Definition at line 490 of file bmsparsevec_algo.h.

◆ bvector_type

template<typename SV >
SV::bvector_type bm::sparse_vector_scanner< SV >::bvector_type

Definition at line 484 of file bmsparsevec_algo.h.

◆ bvector_type_const_ptr

template<typename SV >
const bvector_type* bm::sparse_vector_scanner< SV >::bvector_type_const_ptr

Definition at line 485 of file bmsparsevec_algo.h.

◆ bvector_type_ptr

template<typename SV >
bvector_type* bm::sparse_vector_scanner< SV >::bvector_type_ptr

Definition at line 486 of file bmsparsevec_algo.h.

◆ heap_matrix_type

template<typename SV >
bm::dynamic_heap_matrix<value_type, allocator_type> bm::sparse_vector_scanner< SV >::heap_matrix_type
protected

Definition at line 732 of file bmsparsevec_algo.h.

◆ matrix_search_buf_type

template<typename SV >
bm::heap_matrix<typename SV::value_type, linear_cutoff2, SV::sv_octet_plains, allocator_type> bm::sparse_vector_scanner< SV >::matrix_search_buf_type
protected

Definition at line 736 of file bmsparsevec_algo.h.

◆ size_type

template<typename SV >
SV::size_type bm::sparse_vector_scanner< SV >::size_type

Definition at line 488 of file bmsparsevec_algo.h.

◆ value_type

template<typename SV >
SV::value_type bm::sparse_vector_scanner< SV >::value_type

Definition at line 487 of file bmsparsevec_algo.h.

Member Enumeration Documentation

◆ search_algo_params

template<typename SV >
enum bm::sparse_vector_scanner::search_algo_params
protected
Enumerator
linear_cutoff1 
linear_cutoff2 

Definition at line 726 of file bmsparsevec_algo.h.

◆ vector_capacity

template<typename SV >
enum bm::sparse_vector_scanner::vector_capacity
protected
Enumerator
max_columns 

Definition at line 721 of file bmsparsevec_algo.h.

Constructor & Destructor Documentation

◆ sparse_vector_scanner() [1/2]

template<typename SV >
bm::sparse_vector_scanner< SV >::sparse_vector_scanner ( )

Definition at line 1106 of file bmsparsevec_algo.h.

References bm::id_max.

◆ sparse_vector_scanner() [2/2]

template<typename SV >
bm::sparse_vector_scanner< SV >::sparse_vector_scanner ( const sparse_vector_scanner< SV > & )
protecteddelete

Member Function Documentation

◆ bfind_eq_str() [1/2]

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

Examples
xsample05.cpp.

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().

◆ bfind_eq_str() [2/2]

template<typename SV >
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

See also
bind

Definition at line 1711 of file bmsparsevec_algo.h.

References BM_ASSERT.

◆ bind()

template<typename SV >
void bm::sparse_vector_scanner< SV >::bind ( const SV & sv,
bool sorted )

bind sparse vector for all searches

Parameters
sv- input sparse vector to bind for searches
sorted- source index is sorted, build index for binary search
Examples
xsample05.cpp.

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().

◆ compare()

template<typename SV >
int bm::sparse_vector_scanner< SV >::compare ( const SV & sv,
size_type idx,
const value_type val )
protected

compare sv[idx] with input value

Definition at line 2022 of file bmsparsevec_algo.h.

◆ compare_str()

template<typename SV >
int bm::sparse_vector_scanner< SV >::compare_str ( const SV & sv,
size_type idx,
const value_type * str )
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.

◆ correct_nulls()

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

Parameters
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().

◆ decompress()

template<typename SV >
void bm::sparse_vector_scanner< SV >::decompress ( const SV & sv,
typename SV::bvector_type & bv_out )
protected

Rank-Select decompression for RSC vectors.

Definition at line 2099 of file bmsparsevec_algo.h.

References BM_ASSERT.

◆ find_eq() [1/3]

template<typename SV >
template<typename It >
void bm::sparse_vector_scanner< SV >::find_eq ( const SV & sv,
It start,
It end,
typename SV::bvector_type & bv_out )
inline

find all values A IN (C, D, E, F)

Parameters
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().

◆ find_eq() [2/3]

template<typename SV >
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

Parameters
sv- input sparse vector
value- value to search for
bv_out- output bit-vector (search result masks 1 elements)
Examples
svsample06.cpp, and xsample03.cpp.

Definition at line 2033 of file bmsparsevec_algo.h.

Referenced by main(), and run_benchmark().

◆ find_eq() [3/3]

template<typename SV >
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

Parameters
sv- input sparse vector
value- value to search for
pos- output found sparse vector element index
Returns
true if found

Definition at line 2057 of file bmsparsevec_algo.h.

◆ find_eq_str() [1/2]

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

Examples
xsample05.cpp.

Definition at line 1515 of file bmsparsevec_algo.h.

Referenced by run_benchmark().

◆ find_eq_str() [2/2]

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

See also
bind

Definition at line 1505 of file bmsparsevec_algo.h.

References BM_ASSERT.

◆ find_eq_with_nulls()

template<typename SV >
bool bm::sparse_vector_scanner< SV >::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 )
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().

◆ find_eq_with_nulls_horizontal()

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

◆ find_first_eq() [1/2]

template<typename SV >
bool bm::sparse_vector_scanner< SV >::find_first_eq ( const SV & sv,
const typename SV::value_type * str,
size_type & idx,
bool remaped )
protected

find first string value (may include NULL indexes)

Definition at line 1283 of file bmsparsevec_algo.h.

References BM_ASSERT.

◆ find_first_eq() [2/2]

template<typename SV >
bool bm::sparse_vector_scanner< SV >::find_first_eq ( const SV & sv,
typename SV::value_type value,
size_type & idx )
protected

find first value (may include NULL indexes)

Definition at line 1259 of file bmsparsevec_algo.h.

References BM_ASSERT.

◆ find_nonzero()

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

Parameters
sv- input sparse vector
bv_out- output bit-bector of non-zero elements

Definition at line 2086 of file bmsparsevec_algo.h.

◆ find_zero()

template<typename SV >
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

Parameters
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().

◆ invert()

template<typename SV >
void bm::sparse_vector_scanner< SV >::invert ( const SV & sv,
typename SV::bvector_type & bv_out )

invert search result ("EQ" to "not EQ")

Parameters
sv- input sparse vector
bv_out- output bit-bector of non-zero elements
Examples
svsample06.cpp.

Definition at line 1195 of file bmsparsevec_algo.h.

References bm::id_max.

Referenced by main().

◆ lower_bound()

template<typename SV >
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

Parameters
sv- input sparse vector
val- value to search for
pos- output sparse vector element index
Returns
true if value found
Examples
svsample07.cpp.

Definition at line 1721 of file bmsparsevec_algo.h.

References BM_ASSERT.

Referenced by insertion_sort().

◆ lower_bound_str()

template<typename SV >
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

Parameters
sv- input sparse vector
str- value to search for
pos- output sparse vector element index
Returns
true if value found
Examples
strsvsample02.cpp.

Definition at line 1841 of file bmsparsevec_algo.h.

References BM_ASSERT.

Referenced by insertion_sort().

◆ operator=()

template<typename SV >
void bm::sparse_vector_scanner< SV >::operator= ( const sparse_vector_scanner< SV > & )
protecteddelete

◆ prepare_and_sub_aggregator() [1/2]

template<typename SV >
bool bm::sparse_vector_scanner< SV >::prepare_and_sub_aggregator ( const SV & sv,
const typename SV::value_type * str,
unsigned octet_start )
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().

◆ prepare_and_sub_aggregator() [2/2]

template<typename SV >
bool bm::sparse_vector_scanner< SV >::prepare_and_sub_aggregator ( const SV & sv,
typename SV::value_type value )
protected

Prepare aggregator for AND-SUB (EQ) search.

Definition at line 1415 of file bmsparsevec_algo.h.

References bm::bitscan(), and BM_ASSERT.

◆ reset_binding()

template<typename SV >
void bm::sparse_vector_scanner< SV >::reset_binding ( )

reset sparse vector binding

Definition at line 1161 of file bmsparsevec_algo.h.

◆ reset_search_range()

template<typename SV >
void bm::sparse_vector_scanner< SV >::reset_search_range ( )
protected

reset (disable) search range

Definition at line 2126 of file bmsparsevec_algo.h.

References bm::id_max.

◆ set_search_range()

template<typename SV >
void bm::sparse_vector_scanner< SV >::set_search_range ( size_type from,
size_type to )
protected

set search boundaries (hint for the aggregator)

Definition at line 2115 of file bmsparsevec_algo.h.

References BM_ASSERT.


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