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 > & )

protecteddelete

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 )

inlinestaticprotected

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 )

staticprotected

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

inlinestaticconstexprprotectednoexcept

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 > & )

protecteddelete

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 )

staticprotected

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

inlineprotected

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

Data Structures

Public Types

Public Member Functions

Find in bit-transposed string vector

Detailed Description

Member Typedef Documentation

◆ aggregator_type

◆ allocator_pool_type

◆ allocator_type

◆ bv_count_vector_type

◆ bvect_vector_type

◆ bvector_type

◆ bvector_type_const_ptr

◆ bvector_type_ptr

◆ heap_matrix_type

◆ mask_vector_type

◆ matrix_search_buf_type

◆ remap_vector_type

◆ run_options

◆ size_type

◆ value_type

Member Enumeration Documentation

◆ code

◆ search_algo_params

Constructor & Destructor Documentation

◆ sparse_vector_scanner() [1/2]

◆ sparse_vector_scanner() [2/2]

Member Function Documentation

◆ add_agg_char()

◆ aggregate_AND_OR_slices()

◆ aggregate_OR_slices()

◆ bfind()

◆ bfind_eq_str() [1/3]

◆ bfind_eq_str() [2/3]

◆ bfind_eq_str() [3/3]

◆ bfind_eq_str_impl() [1/2]

◆ bfind_eq_str_impl() [2/2]

◆ bind()

◆ compare()

◆ compare_str() [1/2]

◆ compare_str() [2/2]

◆ correct_nulls()

◆ decompress()

◆ find_eq() [1/4]

◆ find_eq() [2/4]

◆ find_eq() [3/4]

◆ find_eq() [4/4]

◆ find_eq_str() [1/5]

◆ find_eq_str() [2/5]

◆ find_eq_str() [3/5]

◆ find_eq_str() [4/5]

◆ find_eq_str() [5/5]

◆ find_eq_str_impl()

◆ find_eq_str_prefix()

◆ find_eq_with_nulls()

◆ find_eq_with_nulls_horizontal()

◆ find_first_eq() [1/2]

◆ find_first_eq() [2/2]

◆ find_ge()

◆ find_gt()

◆ find_gt_horizontal()

◆ find_le()

◆ find_lt()

◆ find_nonzero()

◆ find_positive()

◆ find_range()

◆ find_zero()

◆ get_bvector_alloc_pool()

◆ gt_slice_limit()

◆ invert()

◆ lower_bound_str()

◆ operator=()

◆ prepare_and_sub_aggregator() [1/2]

◆ prepare_and_sub_aggregator() [2/2]

◆ remap_tosv()

◆ reset_binding()

◆ reset_search_range()

◆ resize_buffers()

◆ set_search_range()