BitMagic-C++
Public Types | Public Member Functions | Protected Member Functions

algorithms for sparse_vector scan/seach 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_pool_type allocator_pool_type
 

Public Member Functions

 sparse_vector_scanner ()
 
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 More...
 
bool find_eq (const SV &sv, typename SV::value_type value, typename SV::size_type &pos)
 find first sparse vector element More...
 
void find_zero (const SV &sv, typename SV::bvector_type &bv_out)
 find all sparse vector elements EQ to 0 More...
 
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. More...
 
void invert (const SV &sv, typename SV::bvector_type &bv_out)
 invert search result ("EQ" to "not EQ") More...
 
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) More...
 
void find_eq_with_nulls_horizontal (const SV &sv, typename SV::value_type value, typename SV::bvector_type &bv_out)
 For testing purposes only. More...
 
void correct_nulls (const SV &sv, typename SV::bvector_type &bv_out)
 Exclude possible NULL values from the result vector. More...
 

Protected Member Functions

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) More...
 
bool find_first_eq (const SV &sv, typename SV::value_type value, bm::id_t &idx)
 find first value (may include NULL indexes) More...
 
bool prepare_and_sub_aggregator (const SV &sv, typename SV::value_type value)
 Prepare aggregator for AND-SUB (EQ) search. More...
 
void decompress (const SV &sv, typename SV::bvector_type &bv_out)
 Rank-Select decompression for RSC vectors. More...
 
 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/seach

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:
svsample06.cpp, and xsample03.cpp.

Definition at line 149 of file bmsparsevec_algo.h.

Member Typedef Documentation

◆ allocator_pool_type

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

Definition at line 157 of file bmsparsevec_algo.h.

◆ bvector_type

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

Definition at line 152 of file bmsparsevec_algo.h.

◆ bvector_type_const_ptr

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

Definition at line 153 of file bmsparsevec_algo.h.

◆ bvector_type_ptr

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

Definition at line 154 of file bmsparsevec_algo.h.

◆ size_type

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

Definition at line 156 of file bmsparsevec_algo.h.

◆ value_type

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

Definition at line 155 of file bmsparsevec_algo.h.

Constructor & Destructor Documentation

◆ sparse_vector_scanner() [1/2]

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

◆ 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

◆ 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 685 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 906 of file bmsparsevec_algo.h.

References BM_ASSERT.

Referenced by bm::sparse_vector_scanner< SV >::find_eq().

◆ find_eq() [1/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)

Definition at line 841 of file bmsparsevec_algo.h.

Referenced by main(), run_benchmark(), and bm::sparse_vector_scanner< SV >::sparse_vector_scanner().

◆ find_eq() [2/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 866 of file bmsparsevec_algo.h.

◆ find_eq() [3/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_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 696 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 787 of file bmsparsevec_algo.h.

References bm::bitscan(), and BM_ASSERT.

Referenced by bm::sparse_vector_scanner< SV >::find_eq().

◆ find_first_eq()

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

find first value (may include NULL indexes)

Definition at line 727 of file bmsparsevec_algo.h.

References BM_ASSERT.

Referenced by bm::sparse_vector_scanner< SV >::find_eq().

◆ 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 893 of file bmsparsevec_algo.h.

Referenced by bm::sparse_vector_scanner< SV >::sparse_vector_scanner().

◆ 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 641 of file bmsparsevec_algo.h.

References bm::id_max.

Referenced by bm::set2set_11_transform< SV >::attach_sv(), and bm::sparse_vector_scanner< SV >::sparse_vector_scanner().

◆ 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

Definition at line 667 of file bmsparsevec_algo.h.

References bm::id_max.

Referenced by main(), and bm::sparse_vector_scanner< SV >::sparse_vector_scanner().

◆ operator=()

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

◆ prepare_and_sub_aggregator()

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 750 of file bmsparsevec_algo.h.

References bm::bitscan(), and BM_ASSERT.

Referenced by bm::sparse_vector_scanner< SV >::find_eq().


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