bm::sparse_vector_scanner< SV, S_FACTOR > Class Template Reference
BitMagic Library » Sparse and compressed vectors » Sparse vector algorithms | BitMagic Library » bvector<> container » bvector<> algorithms

algorithms for sparse_vector scan/search More...

`#include <bmsparsevec_algo.h>`

## Data Structures

class | pipeline
| Pipeline to run multiple searches against a particular SV faster using cache optimizations. More...

## 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
typedef bm::aggregator< bvector_type > | aggregator_type
typedef bm::heap_vector< value_type, typename bvector_type::allocator_type, true > | remap_vector_type
typedef bm::heap_vector< bvector_type *, allocator_type, true > | bvect_vector_type
typedef aggregator_type::bv_count_vector_type | bv_count_vector_type
typedef aggregator_type::run_options | run_options
| Scanner options to control execution.

## 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
template<bool BOUND>
bool | bfind_eq_str_impl (const SV &sv, const typename SV::value_type *str, size_t in_len, bool remaped, typename SV::size_type &pos)
template<bool BOUND>
int | compare_str (const SV &sv, size_type idx, const value_type *BMRESTRICT str) const BMNOEXCEPT
Find in scalar vector
void | find_eq (const SV &sv, value_type value, bvector_type &bv_out)
| find all sparse vector elements EQ to search value
template<typename BII>
void | find_eq (const SV &sv, value_type value, BII bi)
| find all sparse vector elements EQ to search value
bool | find_eq (const SV &sv, value_type value, size_type &pos)
| find first sparse vector element
bool | bfind (const SV &sv, const value_type val, size_type &pos)
| binary search for position in the sorted sparse vector
void | find_gt (const SV &sv, value_type val, bvector_type &bv_out)
| find all elements sparse vector element greater (>) than value
void | find_ge (const SV &sv, value_type val, bvector_type &bv_out)
| find all elements sparse vector element greater or equal (>=) than value
void | find_lt (const SV &sv, value_type val, bvector_type &bv_out)
| find all elements sparse vector element less (<) than value
void | find_le (const SV &sv, value_type val, bvector_type &bv_out)
| find all elements sparse vector element less or equal (<=) than value
void | find_range (const SV &sv, value_type from, value_type to, bvector_type &bv_out)
| find all elements sparse vector element in closed range [left..right] interval

## Find in bit-transposed string vector

enum | search_algo_params { linear_cutoff1 = 16 , linear_cutoff2 = 128 }
enum | code { sub_bfind_block_cnt = S_FACTOR , sub_block_l1_size = bm::gap_max_bits / S_FACTOR }
typedef bm::dynamic_heap_matrix< value_type, allocator_type > | heap_matrix_type
typedef bm::dynamic_heap_matrix< value_type, allocator_type > | matrix_search_buf_type
typedef bm::heap_vector< bm::id64_t, typename bvector_type::allocator_type, true > | mask_vector_type
bool | find_eq_str (const SV &sv, const value_type *str, bvector_type &bv_out)
| find sparse vector elements (string)
bool | find_eq_str (const value_type *str, bvector_type &bv_out)
| find sparse vector elementa (string) in the attached SV
bool | find_eq_str (const SV &sv, const value_type *str, size_type &pos)
| find first sparse vector element (string)
bool | find_eq_str (const value_type *str, size_type &pos)
| binary find first sparse vector element (string) Sparse vector must be attached (bind())
bool | find_eq_str_prefix (const SV &sv, const value_type *str, bvector_type &bv_out)
| find sparse vector elements with a given prefix (string)
template<class TPipe>
void | find_eq_str (TPipe &pipe)
| find sparse vector elements using search pipeline
bool | bfind_eq_str (const SV &sv, const value_type *str, size_type &pos)
| binary find first sparse vector element (string).
bool | lower_bound_str (const SV &sv, const value_type *str, size_type &pos)
| lower bound search for an array position
bool | bfind_eq_str (const value_type *str, size_type &pos)
| binary find first sparse vector element (string) Sparse vector must be sorted and attached (use method bind())
bool | bfind_eq_str (const value_type *str, size_t len, size_type &pos)
| binary find first sparse vector element (string) Sparse vector must be sorted and attached (use method bind())
void | find_zero (const SV &sv, bvector_type &bv_out, bool null_correct=true)
| find all sparse vector elements EQ to 0
void | find_nonzero (const SV &sv, bvector_type &bv_out)
| Find non-zero elements Output vector is computed as a logical OR (join) of all planes.
void | find_positive (const SV &sv, bvector_type &bv_out)
| Find positive (greter than zero elements) Output vector is computed as a logical OR (join) of all planes.
void | invert (const SV &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, bvector_type &bv_out)
| find all values A IN (C, D, E, F)
void | find_eq_with_nulls_horizontal (const SV &sv, value_type value, bvector_type &bv_out)
| For testing purposes only.
void | find_gt_horizontal (const SV &sv, value_type value, bvector_type &bv_out, bool null_correct=true)
| For testing purposes only.
void | correct_nulls (const SV &sv, bvector_type &bv_out)
| Exclude possible NULL values from the result vector.
allocator_pool_type & | get_bvector_alloc_pool () BMNOEXCEPT
| Return allocator pool for blocks (Can be used to improve performance of repeated searches with the same scanner).
template<bool BOUND>
bool | bfind_eq_str_impl (const SV &sv, const value_type *str, size_t in_len, bool remaped, size_type &pos)
void | set_search_range (size_type from, size_type to) BMNOEXCEPT
| set search boundaries (hint for the aggregator)
void | reset_search_range () BMNOEXCEPT
| reset (disable) search range
bool | find_eq_with_nulls (const SV &sv, value_type value, bvector_type &bv_out, size_type search_limit=0)
| find value (may include NULL indexes)
bool | find_first_eq (const SV &sv, value_type value, size_type &idx)
| find first value (may include NULL indexes)
bool | find_first_eq (const SV &sv, const value_type *str, size_t in_len, size_type &idx, bool remaped, unsigned prefix_len)
| find first string value (may include NULL indexes)
bool | find_eq_str_impl (const SV &sv, const value_type *str, bvector_type &bv_out, bool prefix_sub)
| find EQ str / prefix impl
bool | prepare_and_sub_aggregator (const SV &sv, value_type value)
| Prepare aggregator for AND-SUB (EQ) search.
bool | prepare_and_sub_aggregator (const SV &sv, const value_type *str, unsigned octet_start, bool prefix_sub)
| Prepare aggregator for AND-SUB (EQ) search (string).
void | decompress (const SV &sv, bvector_type &bv_out)
| Rank-Select decompression for RSC vectors.
template<bool BOUND>
int | compare_str (const SV &sv, size_type idx, const value_type *str) const BMNOEXCEPT
| 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
void | aggregate_OR_slices (bvector_type &bv_target, const SV &sv, unsigned from, unsigned total_planes)
void | resize_buffers ()
| sparse_vector_scanner (const sparse_vector_scanner &)=delete
void | operator= (const sparse_vector_scanner &)=delete
static bool | remap_tosv (remap_vector_type &remap_vect_target, const value_type *str, const SV &sv)
| Remap input value into SV char encodings.
static void | aggregate_AND_OR_slices (bvector_type &bv_target, const bvector_type &bv_mask, const SV &sv, unsigned from, unsigned total_planes)
static constexpr int | gt_slice_limit () noexcept
| Return the slice limit for signed/unsigned vector value types.
template<typename AGG>
static void | add_agg_char (AGG &agg, const SV &sv, int octet_idx, bm::id64_t planes_mask, unsigned value)
| Addd char to aggregator (AND-SUB).

## Detailed Description

template<typename SV, unsigned S_FACTOR>
class bm::sparse_vector_scanner< SV, S_FACTOR >

algorithms for sparse_vector scan/search

Scanner uses properties of bit-vector planes to answer questions like "find all sparse vector elements equivalent to XYZ".

Class uses fast algorithms based on properties of bit-planes. This is NOT a brute force, direct scan, scanner uses search space pruning and cache optimizations to run the search.

S_FACTOR - Sampling factor for search. Can be: [ 4, 8, 16, 32, 64 ]. Default: 16. Lower sampling facor (4, 8) lowers memory footprint for the scanner class instance Higher - improves search performance (at the expense for memory for sampled elements) Sampling factor is used for binary search in bound string sparse vector, so memory consumption depends on sampling and max string length.

Examples
  strsvsample02.cpp, strsvsample06.cpp, strsvsample07.cpp, strsvsample08.cpp, strsvsample09.cpp, svsample06.cpp, svsample07.cpp, svsample07a.cpp, svsample10.cpp, xsample03.cpp, xsample05.cpp, and xsample07.cpp.

Definition at line 581 of file bmsparsevec_algo.h.

## Member Typedef Documentation

## aggregator_type

template<typename SV, unsigned S_FACTOR>

typedef bm::aggregator<bvector_type> bm::sparse_vector_scanner< SV, S_FACTOR >::aggregator_type

Definition at line 593 of file bmsparsevec_algo.h.

## allocator_pool_type

template<typename SV, unsigned S_FACTOR>

typedef allocator_type::allocator_pool_type bm::sparse_vector_scanner< SV, S_FACTOR >::allocator_pool_type

Definition at line 591 of file bmsparsevec_algo.h.

## allocator_type

template<typename SV, unsigned S_FACTOR>

typedef bvector_type::allocator_type bm::sparse_vector_scanner< SV, S_FACTOR >::allocator_type

Definition at line 590 of file bmsparsevec_algo.h.

## bv_count_vector_type

template<typename SV, unsigned S_FACTOR>

typedef aggregator_type::bv_count_vector_type bm::sparse_vector_scanner< SV, S_FACTOR >::bv_count_vector_type

Definition at line 600 of file bmsparsevec_algo.h.

## bvect_vector_type

template<typename SV, unsigned S_FACTOR>

typedef bm::heap_vector<bvector_type*, allocator_type, true> bm::sparse_vector_scanner< SV, S_FACTOR >::bvect_vector_type

Definition at line 598 of file bmsparsevec_algo.h.

## bvector_type

template<typename SV, unsigned S_FACTOR>

typedef SV::bvector_type bm::sparse_vector_scanner< SV, S_FACTOR >::bvector_type

Definition at line 584 of file bmsparsevec_algo.h.

## bvector_type_const_ptr

template<typename SV, unsigned S_FACTOR>

typedef const bvector_type* bm::sparse_vector_scanner< SV, S_FACTOR >::bvector_type_const_ptr

Definition at line 585 of file bmsparsevec_algo.h.

## bvector_type_ptr

template<typename SV, unsigned S_FACTOR>

typedef bvector_type* bm::sparse_vector_scanner< SV, S_FACTOR >::bvector_type_ptr

Definition at line 586 of file bmsparsevec_algo.h.

## heap_matrix_type

template<typename SV, unsigned S_FACTOR>

typedef bm::dynamic_heap_matrix<value_type, allocator_type> bm::sparse_vector_scanner< SV, S_FACTOR >::heap_matrix_type

protected

Definition at line 1150 of file bmsparsevec_algo.h.

## mask_vector_type

template<typename SV, unsigned S_FACTOR>

typedef bm::heap_vector<bm::id64_t, typename bvector_type::allocator_type, true> bm::sparse_vector_scanner< SV, S_FACTOR >::mask_vector_type

protected

Definition at line 1155 of file bmsparsevec_algo.h.

## matrix_search_buf_type

template<typename SV, unsigned S_FACTOR>

typedef bm::dynamic_heap_matrix<value_type, allocator_type> bm::sparse_vector_scanner< SV, S_FACTOR >::matrix_search_buf_type

protected

Definition at line 1151 of file bmsparsevec_algo.h.

## remap_vector_type

template<typename SV, unsigned S_FACTOR>

typedef bm::heap_vector<value_type, typename bvector_type::allocator_type, true> bm::sparse_vector_scanner< SV, S_FACTOR >::remap_vector_type

Definition at line 596 of file bmsparsevec_algo.h.

## run_options

template<typename SV, unsigned S_FACTOR>

typedef aggregator_type::run_options bm::sparse_vector_scanner< SV, S_FACTOR >::run_options

Scanner options to control execution.

Definition at line 606 of file bmsparsevec_algo.h.

## size_type

template<typename SV, unsigned S_FACTOR>

typedef SV::size_type bm::sparse_vector_scanner< SV, S_FACTOR >::size_type

Definition at line 588 of file bmsparsevec_algo.h.

## value_type

template<typename SV, unsigned S_FACTOR>

typedef SV::value_type bm::sparse_vector_scanner< SV, S_FACTOR >::value_type

Definition at line 587 of file bmsparsevec_algo.h.

## Member Enumeration Documentation

## code

template<typename SV, unsigned S_FACTOR>

enum bm::sparse_vector_scanner::code

protected

Enumerator
sub_bfind_block_cnt |
sub_block_l1_size |

Definition at line 1200 of file bmsparsevec_algo.h.

## search_algo_params

template<typename SV, unsigned S_FACTOR>

enum bm::sparse_vector_scanner::search_algo_params

protected

Enumerator
linear_cutoff1 |
linear_cutoff2 |

Definition at line 1144 of file bmsparsevec_algo.h.

## Constructor & Destructor Documentation

## sparse_vector_scanner() [1/2]

template<typename SV, unsigned S_FACTOR>

bm::sparse_vector_scanner< SV, S_FACTOR >::sparse_vector_scanner | ( |  | ) |

Definition at line 1582 of file bmsparsevec_algo.h.

References bm::id_max.

Referenced by operator=(), and sparse_vector_scanner().

## sparse_vector_scanner() [2/2]

template<typename SV, unsigned S_FACTOR>

bm::sparse_vector_scanner< SV, S_FACTOR >::sparse_vector_scanner | ( | const sparse_vector_scanner< SV, S_FACTOR > & |  | ) |

protected delete

References sparse_vector_scanner().

## Member Function Documentation

## add_agg_char()

template<typename SV, unsigned S_FACTOR>
template<typename AGG>

void bm::sparse_vector_scanner< SV, S_FACTOR >::add_agg_char | ( | AGG & | agg,
|  | const SV & | sv,
|  | int | octet_idx,
|  | bm::id64_t | planes_mask,
|  | unsigned | value )

inline static protected

Addd char to aggregator (AND-SUB).

Definition at line 1162 of file bmsparsevec_algo.h.

References bm::bitscan(), BM_ASSERT, and bm::word_bitcount().

Referenced by bm::sparse_vector_scanner< SV, S_FACTOR >::pipeline< Opt >::add(), and prepare_and_sub_aggregator().

## aggregate_AND_OR_slices()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::aggregate_AND_OR_slices | ( | bvector_type & | bv_target,
|  | const bvector_type & | bv_mask,
|  | const SV & | sv,
|  | unsigned | from,
|  | unsigned | total_planes )

static protected

Definition at line 2282 of file bmsparsevec_algo.h.

References BM_ASSERT.

Referenced by compare_str(), and find_gt_horizontal().

## aggregate_OR_slices()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::aggregate_OR_slices | ( | bvector_type & | bv_target,
|  | const SV & | sv,
|  | unsigned | from,
|  | unsigned | total_planes )

protected

Definition at line 2263 of file bmsparsevec_algo.h.

References BM_ASSERT.

Referenced by compare_str(), and find_gt_horizontal().

## bfind()

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::bfind | ( | const SV & | sv,
|  | const value_type | val,
|  | typename SV::size_type & | pos )

binary search for position in the sorted sparse vector

Method assumes the sparse array is sorted, if value is found pos returns its index, if not found, pos would contain index where it could be inserted to maintain the order

Parameters

  sv | - input sparse vector
  val | - value to search for
  pos | - output sparse vector element index (actual index if found or insertion point if not found)

Returns
  true if value found

Examples
  svsample07.cpp.

Definition at line 2730 of file bmsparsevec_algo.h.

References BM_ASSERT, compare(), linear_cutoff1, and linear_cutoff2.

Referenced by insertion_sort().

## bfind_eq_str() [1/3]

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::bfind_eq_str | ( | const SV & | sv,
|  | const value_type * | str,
|  | size_type & | pos )

binary find first sparse vector element (string).

Sparse vector must be sorted.

Parameters

  sv | - sparse vector of strings to search
  str | - string prefix to search for
  pos | - [out] first position found

Examples
  strsvsample08.cpp, and xsample05.cpp.

Definition at line 2638 of file bmsparsevec_algo.h.

References bfind_eq_str_impl(), and resize_buffers().

Referenced by bfind_eq_str(), find_eq_str(), main(), and run_benchmark().

## bfind_eq_str() [2/3]

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::bfind_eq_str | ( | const value_type * | str,
|  | size_t | len,
|  | size_type & | pos )

binary find first sparse vector element (string) Sparse vector must be sorted and attached (use method bind())

Parameters

  str | - string prefix to search for
  len | - string length
  pos | - [out] first position found

See also
  bind

Definition at line 2691 of file bmsparsevec_algo.h.

References bfind_eq_str_impl(), and BM_ASSERT.

## bfind_eq_str() [3/3]

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::bfind_eq_str | ( | const value_type * | str,
|  | size_type & | pos )

binary find first sparse vector element (string) Sparse vector must be sorted and attached (use method bind())

Parameters

  str | - string prefix to search for
  pos | - [out] first position found

See also
  bind

References bfind_eq_str(), find_nonzero(), find_positive(), find_zero(), and invert().

## bfind_eq_str_impl() [1/2]

template<typename SV, unsigned S_FACTOR>
template<bool BOUND>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::bfind_eq_str_impl | ( | const SV & | sv,
|  | const typename SV::value_type * | str,
|  | size_t | in_len,
|  | bool | remaped,
|  | typename SV::size_type & | pos )

Definition at line 2479 of file bmsparsevec_algo.h.

References BM_ASSERT, compare_str(), find_first_eq(), find_zero(), bm::gap_max_bits, reset_search_range(), bm::set_block_shift, set_search_range(), sub_bfind_block_cnt, and sub_block_l1_size.

## bfind_eq_str_impl() [2/2]

template<typename SV, unsigned S_FACTOR>
template<bool BOUND>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::bfind_eq_str_impl | ( | const SV & | sv,
|  | const value_type * | str,
|  | size_t | in_len,
|  | bool | remaped,
|  | size_type & | pos )

protected

References BMNOEXCEPT, decompress(), find_eq_str_impl(), find_eq_with_nulls(), find_first_eq(), and prepare_and_sub_aggregator().

Referenced by bfind_eq_str(), and bfind_eq_str().

## bind()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::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
  strsvsample08.cpp, svsample07a.cpp, and xsample05.cpp.

Definition at line 1594 of file bmsparsevec_algo.h.

References resize_buffers().

Referenced by main(), and run_benchmark().

## compare()

template<typename SV, unsigned S_FACTOR>

int bm::sparse_vector_scanner< SV, S_FACTOR >::compare | ( | const SV & | sv,
|  | size_type | idx,
|  | const value_type | val )

protected

compare sv[idx] with input value

Definition at line 3059 of file bmsparsevec_algo.h.

References BMNOEXCEPT.

Referenced by bfind(), and compare_str().

## compare_str() [1/2]

template<typename SV, unsigned S_FACTOR>
template<bool BOUND>

int bm::sparse_vector_scanner< SV, S_FACTOR >::compare_str | ( | const SV & | sv,
|  | size_type | idx,
|  | const value_type *BMRESTRICT | str ) const

Definition at line 2986 of file bmsparsevec_algo.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, bm::set_block_mask, and bm::set_block_shift.

## compare_str() [2/2]

template<typename SV, unsigned S_FACTOR>
template<bool BOUND>

int bm::sparse_vector_scanner< SV, S_FACTOR >::compare_str | ( | const SV & | sv,
|  | size_type | idx,
|  | const value_type * | str ) const

protected

compare sv[idx] with input str

References aggregate_AND_OR_slices(), aggregate_OR_slices(), BMNOEXCEPT, compare(), and compare_str().

Referenced by bfind_eq_str_impl(), compare_str(), and lower_bound_str().

## correct_nulls()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::correct_nulls | ( | const SV & | 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 1679 of file bmsparsevec_algo.h.

Referenced by find_eq(), find_eq(), find_ge(), find_gt_horizontal(), find_zero(), and invert().

## decompress()

template<typename SV, unsigned S_FACTOR>

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

protected

Rank-Select decompression for RSC vectors.

Definition at line 3191 of file bmsparsevec_algo.h.

References BM_ASSERT.

Referenced by bfind_eq_str_impl(), find_eq(), find_gt_horizontal(), and find_zero().

## find_eq() [1/4]

template<typename SV, unsigned S_FACTOR>
template<typename It>

void bm::sparse_vector_scanner< SV, S_FACTOR >::find_eq | ( | const SV & | sv,
|  | It | start,
|  | It | end,
|  | 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 990 of file bmsparsevec_algo.h.

References BM_ASSERT, correct_nulls(), find_eq(), and find_eq_with_nulls().

## find_eq() [2/4]

template<typename SV, unsigned S_FACTOR>
template<typename BII>

void bm::sparse_vector_scanner< SV, S_FACTOR >::find_eq | ( | const SV & | sv,
|  | value_type | value,
|  | BII | bi )

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
  bi | - back insert iterator for the search results

Definition at line 3096 of file bmsparsevec_algo.h.

References find_zero(), and prepare_and_sub_aggregator().

## find_eq() [3/4]

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::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 | - search result bit-vector (search result is a vector of 1s when sv[i] == value)

Examples
  svsample06.cpp, svsample07a.cpp, xsample03.cpp, and xsample07.cpp.

Definition at line 3071 of file bmsparsevec_algo.h.

References correct_nulls(), decompress(), find_eq_with_nulls(), and find_zero().

Referenced by compute_frequent_kmers(), find_eq(), find_eq(), find_ge(), find_gt_horizontal(), main(), and run_benchmark().

## find_eq() [4/4]

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::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 3130 of file bmsparsevec_algo.h.

References find_eq(), find_first_eq(), and bm::conditional< b >::test().

## find_eq_str() [1/5]

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::find_eq_str | ( | const SV & | sv,
|  | const value_type * | str,
|  | bvector_type & | bv_out )

find sparse vector elements (string)

Parameters

  sv | - sparse vector of strings to search
  str | - string to search for
  bv_out | - search result bit-vector (search result masks 1 elements)

Examples
  strsvsample06.cpp, strsvsample07.cpp, and xsample05.cpp.

References find_eq_str().

Referenced by find_eq_str(), find_eq_str(), find_eq_str(), find_eq_str(), main(), main(), and run_benchmark().

## find_eq_str() [2/5]

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::find_eq_str | ( | const SV & | sv,
|  | const value_type * | str,
|  | size_type & | pos )

find first sparse vector element (string)

Parameters

  sv | - sparse vector of strings to search
  str | - string to search for
  pos | - [out] index of the first found

References find_eq_str().

## find_eq_str() [3/5]

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::find_eq_str | ( | const value_type * | str,
|  | bvector_type & | bv_out )

find sparse vector elementa (string) in the attached SV

Parameters

  str | - string to search for
  bv_out | - search result bit-vector (search result masks 1 elements)

References find_eq_str().

## find_eq_str() [4/5]

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::find_eq_str | ( | const value_type * | str,
|  | size_type & | pos )

binary find first sparse vector element (string) Sparse vector must be attached (bind())

Parameters

  str | - string to search for
  pos | - [out] index of the first found

See also
  bind

References bfind_eq_str(), find_eq_str(), find_eq_str_prefix(), and lower_bound_str().

## find_eq_str() [5/5]

template<typename SV, unsigned S_FACTOR>
template<class TPipe>

void bm::sparse_vector_scanner< SV, S_FACTOR >::find_eq_str | ( | TPipe & | pipe | ) |

find sparse vector elements using search pipeline

Parameters

  pipe | - pipeline to run

Definition at line 2461 of file bmsparsevec_algo.h.

## find_eq_str_impl()

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::find_eq_str_impl | ( | const SV & | sv,
|  | const value_type * | str,
|  | bvector_type & | bv_out,
|  | bool | prefix_sub )

protected

find EQ str / prefix impl

aggregator search

Definition at line 2409 of file bmsparsevec_algo.h.

References BM_ASSERT, find_zero(), prepare_and_sub_aggregator(), and remap_tosv().

Referenced by bfind_eq_str_impl(), and find_eq_str_prefix().

## find_eq_str_prefix()

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::find_eq_str_prefix | ( | const SV & | sv,
|  | const value_type * | str,
|  | bvector_type & | bv_out )

find sparse vector elements with a given prefix (string)

Parameters

  sv | - sparse vector of strings to search
  str | - string prefix to search for "123" is a prefix for "1234567"
  bv_out | - search result bit-vector (search result masks 1 elements)

Examples
  strsvsample06.cpp.

Definition at line 2300 of file bmsparsevec_algo.h.

References find_eq_str_impl().

Referenced by find_eq_str(), and main().

## find_eq_with_nulls()

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::find_eq_with_nulls | ( | const SV & | sv,
|  | value_type | value,
|  | bvector_type & | bv_out,
|  | size_type | search_limit = 0 )

protected

find value (may include NULL indexes)

Definition at line 1690 of file bmsparsevec_algo.h.

References find_zero(), and prepare_and_sub_aggregator().

Referenced by bfind_eq_str_impl(), find_eq(), and find_eq().

## find_eq_with_nulls_horizontal()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::find_eq_with_nulls_horizontal | ( | const SV & | sv,
|  | value_type | value,
|  | bvector_type & | bv_out )

For testing purposes only.

Definition at line 1933 of file bmsparsevec_algo.h.

References bm::bitscan(), BM_ASSERT, and find_zero().

## find_first_eq() [1/2]

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::find_first_eq | ( | const SV & | sv,
|  | const value_type * | str,
|  | size_t | in_len,
|  | size_type & | idx,
|  | bool | remaped,
|  | unsigned | prefix_len )

protected

find first string value (may include NULL indexes)

Definition at line 1745 of file bmsparsevec_algo.h.

References BM_ASSERT, and prepare_and_sub_aggregator().

## find_first_eq() [2/2]

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::find_first_eq | ( | const SV & | sv,
|  | value_type | value,
|  | size_type & | idx )

protected

find first value (may include NULL indexes)

Definition at line 1721 of file bmsparsevec_algo.h.

References BM_ASSERT, and prepare_and_sub_aggregator().

Referenced by bfind_eq_str_impl(), bfind_eq_str_impl(), and find_eq().

## find_ge()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::find_ge | ( | const SV & | sv,
|  | value_type | val,
|  | bvector_type & | bv_out )

find all elements sparse vector element greater or equal (>=) than value

Parameters

  sv | - input sparse vector
  value | - value to search for
  bv_out | - search result bit-vector (search result is a vector of 1s when sv[i] >= value)

Examples
  svsample10.cpp.

Definition at line 1997 of file bmsparsevec_algo.h.

References correct_nulls(), find_eq(), and find_gt_horizontal().

Referenced by find_lt(), find_range(), and main().

## find_gt()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::find_gt | ( | const SV & | sv,
|  | value_type | val,
|  | bvector_type & | bv_out )

find all elements sparse vector element greater (>) than value

Parameters

  sv | - input sparse vector
  value | - value to search for
  bv_out | - search result bit-vector (search result is a vector of 1s when sv[i] > value)

Examples
  svsample10.cpp.

Definition at line 1985 of file bmsparsevec_algo.h.

References find_gt_horizontal().

Referenced by find_le(), find_range(), and main().

## find_gt_horizontal()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::find_gt_horizontal | ( | const SV & | sv,
|  | value_type | value,
|  | bvector_type & | bv_out,
|  | bool | null_correct = true )

For testing purposes only.

Definition at line 2077 of file bmsparsevec_algo.h.

References aggregate_AND_OR_slices(), aggregate_OR_slices(), bm::bitscan(), BM_ASSERT, correct_nulls(), decompress(), find_eq(), find_positive(), find_zero(), and gt_slice_limit().

Referenced by find_ge(), and find_gt().

## find_le()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::find_le | ( | const SV & | sv,
|  | value_type | val,
|  | bvector_type & | bv_out )

find all elements sparse vector element less or equal (<=) than value

Parameters

  sv | - input sparse vector
  value | - value to search for
  bv_out | - search result bit-vector (search result is a vector of 1s when sv[i] <= value)

Examples
  svsample10.cpp.

Definition at line 2048 of file bmsparsevec_algo.h.

References find_gt(), and invert().

Referenced by main().

## find_lt()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::find_lt | ( | const SV & | sv,
|  | value_type | val,
|  | bvector_type & | bv_out )

find all elements sparse vector element less (<) than value

Parameters

  sv | - input sparse vector
  value | - value to search for
  bv_out | - search result bit-vector (search result is a vector of 1s when sv[i] < value)

Examples
  svsample10.cpp.

Definition at line 2036 of file bmsparsevec_algo.h.

References find_ge(), and invert().

Referenced by main().

## find_nonzero()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::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 planes.

Parameters

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

Definition at line 3160 of file bmsparsevec_algo.h.

Referenced by bfind_eq_str(), and find_zero().

## find_positive()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::find_positive | ( | const SV & | sv,
|  | typename SV::bvector_type & | bv_out )

Find positive (greter than zero elements) Output vector is computed as a logical OR (join) of all planes.

Parameters

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

Definition at line 3175 of file bmsparsevec_algo.h.

References BM_ASSERT.

Referenced by bfind_eq_str(), and find_gt_horizontal().

## find_range()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::find_range | ( | const SV & | sv,
|  | value_type | from,
|  | value_type | to,
|  | bvector_type & | bv_out )

find all elements sparse vector element in closed range [left..right] interval

Parameters

  sv | - input sparse vector
  from | - range from
  to | - range to
  bv_out | - search result bit-vector (search result is a vector of 1s when sv[i] <= value)

Examples
  svsample10.cpp.

Definition at line 2059 of file bmsparsevec_algo.h.

References find_ge(), find_gt(), and bm::xor_swap().

Referenced by main().

## find_zero()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::find_zero | ( | const SV & | sv,
|  | bvector_type & | bv_out,
|  | bool | null_correct = true )

find all sparse vector elements EQ to 0

Parameters

  sv | - input sparse vector
  bv_out | - output bit-vector (search result masks 1 elements)
  null_correct | - flag to perform NULL correction

Definition at line 1634 of file bmsparsevec_algo.h.

References correct_nulls(), decompress(), find_nonzero(), bm::id_max, and invert().

Referenced by bm::set2set_11_transform< SV >::attach_sv(), bfind_eq_str(), bfind_eq_str_impl(), find_eq(), find_eq(), find_eq_str_impl(), find_eq_with_nulls(), find_eq_with_nulls_horizontal(), and find_gt_horizontal().

## get_bvector_alloc_pool()

template<typename SV, unsigned S_FACTOR>

allocator_pool_type & bm::sparse_vector_scanner< SV, S_FACTOR >::get_bvector_alloc_pool | ( |  | ) |

inline

Return allocator pool for blocks (Can be used to improve performance of repeated searches with the same scanner).

Examples
  svsample07a.cpp.

Definition at line 1042 of file bmsparsevec_algo.h.

References BMNOEXCEPT.

Referenced by main().

## gt_slice_limit()

template<typename SV, unsigned S_FACTOR>

constexpr int bm::sparse_vector_scanner< SV, S_FACTOR >::gt_slice_limit | ( |  | ) |

inline static constexpr protected noexcept

Return the slice limit for signed/unsigned vector value types.

Definition at line 1123 of file bmsparsevec_algo.h.

References gt_slice_limit().

Referenced by find_gt_horizontal(), and gt_slice_limit().

## invert()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::invert | ( | const SV & | 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 1661 of file bmsparsevec_algo.h.

References correct_nulls().

Referenced by bfind_eq_str(), find_le(), find_lt(), find_zero(), and main().

## lower_bound_str()

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::lower_bound_str | ( | const SV & | sv,
|  | const value_type * | str,
|  | 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, and strsvsample09.cpp.

Definition at line 2851 of file bmsparsevec_algo.h.

References BM_ASSERT, compare_str(), linear_cutoff1, and linear_cutoff2.

Referenced by find_eq_str(), insertion_sort(), and insertion_sort().

## operator=()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::operator= | ( | const sparse_vector_scanner< SV, S_FACTOR > & |  | ) |

protected delete

References sparse_vector_scanner().

## prepare_and_sub_aggregator() [1/2]

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::prepare_and_sub_aggregator | ( | const SV & | sv,
|  | const value_type * | str,
|  | unsigned | octet_start,
|  | bool | prefix_sub )

protected

Prepare aggregator for AND-SUB (EQ) search (string).

Definition at line 1845 of file bmsparsevec_algo.h.

References add_agg_char(), and BM_ASSERT.

## prepare_and_sub_aggregator() [2/2]

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::prepare_and_sub_aggregator | ( | const SV & | sv,
|  | value_type | value )

protected

Prepare aggregator for AND-SUB (EQ) search.

Definition at line 1892 of file bmsparsevec_algo.h.

References bm::bitscan(), and BM_ASSERT.

Referenced by bfind_eq_str_impl(), find_eq(), find_eq_str_impl(), find_eq_with_nulls(), find_first_eq(), and find_first_eq().

## remap_tosv()

template<typename SV, unsigned S_FACTOR>

bool bm::sparse_vector_scanner< SV, S_FACTOR >::remap_tosv | ( | remap_vector_type & | remap_vect_target,
|  | const value_type * | str,
|  | const SV & | sv )

static protected

Remap input value into SV char encodings.

Definition at line 2395 of file bmsparsevec_algo.h.

Referenced by bm::sparse_vector_scanner< SV, S_FACTOR >::pipeline< Opt >::add(), and find_eq_str_impl().

## reset_binding()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::reset_binding | ( |  | ) |

reset sparse vector binding

Definition at line 1625 of file bmsparsevec_algo.h.

References BMNOEXCEPT.

## reset_search_range()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::reset_search_range | ( |  | ) |

protected

reset (disable) search range

Definition at line 3223 of file bmsparsevec_algo.h.

References BMNOEXCEPT.

Referenced by bfind_eq_str_impl().

## resize_buffers()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::resize_buffers | ( |  | ) |

inline protected

Definition at line 1131 of file bmsparsevec_algo.h.

Referenced by bfind_eq_str(), and bind().

## set_search_range()

template<typename SV, unsigned S_FACTOR>

void bm::sparse_vector_scanner< SV, S_FACTOR >::set_search_range | ( | size_type | from,
|  | size_type | to )

protected

set search boundaries (hint for the aggregator)

Definition at line 3213 of file bmsparsevec_algo.h.

References BM_ASSERT, and BMNOEXCEPT.

Referenced by bfind_eq_str_impl().

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

- bmsparsevec_algo.h