Collaboration diagram for bvector<> algorithms:

Modules
	Binary-distance metrics

Classes
struct	bm::agg_run_options< OBvects, OCounts, OSearchMasks >
	Aggregation options to control execution Default settings are to support only result bit-vector filters. More...

class	bm::aggregator< BV >
	Algorithms for fast aggregation of a group of bit-vectors. More...

class	bm::rank_compressor< BV >
	Algorithms for rank compression of bit-vector. More...

class	bm::random_subset< BV >

class	bm::sparse_vector_scanner< SV, S_FACTOR >
	algorithms for sparse_vector scan/search More...

class	bm::set2set_11_transform< SV >
	Integer set to set transformation (functional image in groups theory) https://en.wikipedia.org/wiki/Image_(mathematics) More...

Functions
template<class BV >
BV::size_type	bm::count_and (const BV &bv1, const BV &bv2) noexcept
	Computes bitcount of AND operation of two bitsets. More...

template<class BV >
BV::size_type	bm::any_and (const BV &bv1, const BV &bv2) noexcept
	Computes if there is any bit in AND operation of two bitsets. More...

template<class BV >
bm::distance_metric_descriptor::size_type	bm::count_xor (const BV &bv1, const BV &bv2) noexcept
	Computes bitcount of XOR operation of two bitsets. More...

template<class BV >
BV::size_type	bm::any_xor (const BV &bv1, const BV &bv2) noexcept
	Computes if there is any bit in XOR operation of two bitsets. More...

template<class BV >
BV::size_type	bm::count_sub (const BV &bv1, const BV &bv2) noexcept
	Computes bitcount of SUB operation of two bitsets. More...

template<class BV >
BV::size_type	bm::any_sub (const BV &bv1, const BV &bv2) noexcept
	Computes if there is any bit in SUB operation of two bitsets. More...

template<class BV >
BV::size_type	bm::count_or (const BV &bv1, const BV &bv2) noexcept
	Computes bitcount of OR operation of two bitsets. More...

template<class BV >
BV::size_type	bm::any_or (const BV &bv1, const BV &bv2) noexcept
	Computes if there is any bit in OR operation of two bitsets. More...

template<class BV , class Func >
int	bm::for_each_bit (const BV &bv, Func &bit_functor)
	bit-vector visitor scanner to traverse each 1 bit using C++ visitor More...

template<class BV , class Func >
int	bm::for_each_bit_range (const BV &bv, typename BV::size_type left, typename BV::size_type right, Func &bit_functor)
	bit-vector range visitor to traverse each 1 bit More...

template<class BV >
int	bm::visit_each_bit (const BV &bv, void *handle_ptr, bit_visitor_callback_type callback_ptr)
	bvector visitor scanner to traverse each 1 bit using C callback More...

template<class BV >
int	bm::visit_each_bit_range (const BV &bv, typename BV::size_type left, typename BV::size_type right, void *handle_ptr, bit_visitor_callback_type callback_ptr)
	bvector visitor scanner to traverse each bits in range (C callback) More...

template<typename BV , typename PairVect >
void	bm::rank_range_split (const BV &bv, typename BV::size_type rank, PairVect &target_v)
	Algorithm to identify bit-vector ranges (splits) for the rank. More...

template<class BV , class It >
void	bm::combine_or (BV &bv, It first, It last)
	OR Combine bitvector and the iterable sequence. More...

template<class BV , class It >
void	bm::combine_xor (BV &bv, It first, It last)
	XOR Combine bitvector and the iterable sequence. More...

template<class BV , class It >
void	bm::combine_sub (BV &bv, It first, It last)
	SUB Combine bitvector and the iterable sequence. More...

template<class BV , class It >
void	bm::combine_and_sorted (BV &bv, It first, It last)
	AND Combine bitvector and the iterable sequence. More...

template<class BV , class It >
void	bm::combine_and (BV &bv, It first, It last)
	AND Combine bitvector and the iterable sequence. More...

template<class BV >
BV::size_type	bm::count_intervals (const BV &bv)
	Compute number of bit intervals (GAPs) in the bitvector. More...

template<typename BV , class It >
void	bm::export_array (BV &bv, It first, It last)
	Export bitset from an array of binary data representing the bit vector. More...

Aggregator traits and control constants
typedef bm::agg_run_options< agg_disable_result_bvectors, agg_disable_counts >	bm::agg_opt_disable_bvects_and_counts
	Pre-defined aggregator options to disable both intermediate results and counts. More...

typedef bm::agg_run_options< agg_disable_result_bvectors, agg_compute_counts >	bm::agg_opt_only_counts
	Pre-defined aggregator options for counts-only (results dropped) operation. More...

typedef bm::agg_run_options< agg_produce_result_bvectors, agg_compute_counts >	bm::agg_opt_bvect_and_counts
	Pre-defined aggregator options for results plus counts operation. More...

template<typename Agg , typename It >
void	bm::aggregator_pipeline_execute (It first, It last)
	Experimental method ro run multiple aggregators in sync. More...

const bool	bm::agg_produce_result_bvectors = true

const bool	bm::agg_disable_result_bvectors = false

const bool	bm::agg_compute_counts = true

const bool	bm::agg_disable_counts = false

const bool	bm::agg_disable_search_masks = false

Detailed Description

Set algebra algorithms using bit-vectors, arrays. Binary metrics and distances. Random sub-sets.

Typedef Documentation

◆ agg_opt_bvect_and_counts

typedef bm::agg_run_options<agg_produce_result_bvectors, agg_compute_counts> bm::agg_opt_bvect_and_counts

Pre-defined aggregator options for results plus counts operation.

Definition at line 103 of file bmaggregator.h.

◆ agg_opt_disable_bvects_and_counts

typedef bm::agg_run_options<agg_disable_result_bvectors, agg_disable_counts> bm::agg_opt_disable_bvects_and_counts

Pre-defined aggregator options to disable both intermediate results and counts.

Definition at line 86 of file bmaggregator.h.

◆ agg_opt_only_counts

typedef bm::agg_run_options<agg_disable_result_bvectors, agg_compute_counts> bm::agg_opt_only_counts

Pre-defined aggregator options for counts-only (results dropped) operation.

Definition at line 95 of file bmaggregator.h.

Function Documentation

◆ aggregator_pipeline_execute()

template<typename Agg , typename It >

void bm::aggregator_pipeline_execute	(	It	first,
		It	last
	)

Experimental method ro run multiple aggregators in sync.

Pipeleine algorithm walts the sequence of iterators (pointers on aggregators) and run them all via aggregator<>::run_step() method

Parameters

first	- iterator (pointer on aggregator)
last	- iterator (pointer on aggregator)

Definition at line 874 of file bmaggregator.h.

References first(), i, last(), and bm::set_sub_array_size.

◆ any_and()

template<class BV >

BV::size_type bm::any_and	(	const BV &	bv1,
		const BV &	bv2
	)

noexcept

Computes if there is any bit in AND operation of two bitsets.

Parameters

bv1	- Argument bit-vector.
bv2	- Argument bit-vector.

Returns: non zero value if there is any bit

Definition at line 62 of file bmalgo.h.

References bm::COUNT_AND, bm::distance_operation_any(), and bm::distance_metric_descriptor::result.

Referenced by AndOperationsTest(), and StressTest().

◆ any_or()

template<class BV >

BV::size_type bm::any_or	(	const BV &	bv1,
		const BV &	bv2
	)

noexcept

Computes if there is any bit in OR operation of two bitsets.

Parameters

bv1	- Argument bit-vector.
bv2	- Argument bit-vector.

Returns: non zero value if there is any bit

Definition at line 165 of file bmalgo.h.

References bm::COUNT_OR, bm::distance_operation_any(), and bm::distance_metric_descriptor::result.

Referenced by OrOperationsTest(), and StressTest().

◆ any_sub()

template<class BV >

BV::size_type bm::any_sub	(	const BV &	bv1,
		const BV &	bv2
	)

noexcept

Computes if there is any bit in SUB operation of two bitsets.

Parameters

bv1	- Argument bit-vector.
bv2	- Argument bit-vector.

Returns: non zero value if there is any bit

Definition at line 132 of file bmalgo.h.

References bm::COUNT_SUB_AB, bm::distance_operation_any(), and bm::distance_metric_descriptor::result.

Referenced by StressTest(), and SubOperationsTest().

◆ any_xor()

template<class BV >

BV::size_type bm::any_xor	(	const BV &	bv1,
		const BV &	bv2
	)

noexcept

Computes if there is any bit in XOR operation of two bitsets.

Parameters

bv1	- Argument bit-vector.
bv2	- Argument bit-vector.

Returns: non zero value if there is any bit

Definition at line 97 of file bmalgo.h.

References bm::COUNT_XOR, bm::distance_operation_any(), and bm::distance_metric_descriptor::result.

Referenced by StressTest(), and XorOperationsTest().

◆ combine_and()

template<class BV , class It >

void bm::combine_and	(	BV &	bv,
		It	first,
		It	last
	)

AND Combine bitvector and the iterable sequence.

Algorithm combines bvector with sequence of integers (represents another set). When the agrument set is sorted this method can give serious increase in performance.

Parameters

bv	- destination bitvector
first	- first element of the iterated sequence
last	- last element of the iterated sequence

See also: combine_and_sorted

Definition at line 1365 of file bmalgo_impl.h.

References bm::combine_or(), first(), and last().

Referenced by bm::aggregator< BV >::combine_and().

◆ combine_and_sorted()

template<class BV , class It >

void bm::combine_and_sorted	(	BV &	bv,
		It	first,
		It	last
	)

AND Combine bitvector and the iterable sequence.

Algorithm combines bvector with sorted sequence of integers (represents another set).

Parameters

bv	- destination bitvector
first	- first element of the iterated sequence
last	- last element of the iterated sequence

Definition at line 1333 of file bmalgo_impl.h.

References BM_ASSERT, first(), last(), and prev().

Referenced by AndOperationsTest().

◆ combine_or()

template<class BV , class It >

void bm::combine_or	(	BV &	bv,
		It	first,
		It	last
	)

OR Combine bitvector and the iterable sequence.

Algorithm combines bvector with sequence of integers (represents another set). When the agrument set is sorted this method can give serious increase in performance.

Parameters

bv	- destination bitvector
first	- first element of the iterated sequence
last	- last element of the iterated sequence

Definition at line 1080 of file bmalgo_impl.h.

References bm::block_range_scan(), BM_ASSERT, BMGAP_PTR, first(), bm::gap_limit(), bm::gap_set_value(), bm::id_max, last(), bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.

Referenced by BvectorBitForEachTest(), BvectorBulkSetTest(), bm::combine_and(), bm::aggregator< BV >::combine_or(), bm::iterator_deserializer< BV, SerialIterator >::load_id_list(), OrOperationsTest(), RangeForEachTest(), and ResizeTest().

◆ combine_sub()

template<class BV , class It >

void bm::combine_sub	(	BV &	bv,
		It	first,
		It	last
	)

SUB Combine bitvector and the iterable sequence.

Algorithm combines bvector with sequence of integers (represents another set). When the agrument set is sorted this method can give serious increase in performance.

Parameters

bv	- destination bitvector
first	- first element of the iterated sequence
last	- last element of the iterated sequence

Definition at line 1248 of file bmalgo_impl.h.

References bm::block_range_scan(), BM_ASSERT, BMGAP_PTR, first(), bm::gap_limit(), bm::gap_set_value(), bm::gap_test_unr(), bm::id_max, last(), bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::iterator_deserializer< BV, SerialIterator >::load_id_list().

◆ combine_xor()

template<class BV , class It >

void bm::combine_xor	(	BV &	bv,
		It	first,
		It	last
	)

XOR Combine bitvector and the iterable sequence.

Algorithm combines bvector with sequence of integers (represents another set). When the agrument set is sorted this method can give serious increase in performance.

Parameters

bv	- destination bitvector
first	- first element of the iterated sequence
last	- last element of the iterated sequence

Definition at line 1161 of file bmalgo_impl.h.

References bm::block_range_scan(), BM_ASSERT, BMGAP_PTR, first(), bm::gap_limit(), bm::gap_set_value(), bm::gap_test_unr(), bm::id_max, last(), bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, and bm::set_word_shift.

Referenced by XorOperationsTest().

◆ count_and()

template<class BV >

BV::size_type bm::count_and	(	const BV &	bv1,
		const BV &	bv2
	)

noexcept

Computes bitcount of AND operation of two bitsets.

Parameters

bv1	- Argument bit-vector.
bv2	- Argument bit-vector.

Returns: bitcount of the result

Definition at line 49 of file bmalgo.h.

References bm::distance_and_operation().

Referenced by AndOperationsTest(), bm::operation_deserializer< BV >::deserialize_xor(), GroupByTest(), bm::process_operation(), StressTest(), and TestCompressSparseVector().

◆ count_intervals()

template<class BV >

BV::size_type bm::count_intervals ( const BV & bv )

Compute number of bit intervals (GAPs) in the bitvector.

Algorithm traverses bit vector and count number of uninterrupted intervals of 1s and 0s.

For example: 
  empty vector   - 1 interval
  00001111100000 - gives us 3 intervals
  10001111100000 - 4 intervals
  00000000000000 - 1 interval
  11111111111111 - 1 interval

Returns: Number of intervals

Definition at line 1389 of file bmalgo_impl.h.

References bm::for_each_block(), bm::id_max, and st().

Referenced by BitCountChangeTest(), CheckIntervals(), and IntervalsCheck().

◆ count_or()

template<class BV >

BV::size_type bm::count_or	(	const BV &	bv1,
		const BV &	bv2
	)

noexcept

Computes bitcount of OR operation of two bitsets.

Parameters

bv1	- Argument bit-vector.
bv2	- Argument bit-vector.

Returns: bitcount of the result

Definition at line 149 of file bmalgo.h.

References bm::COUNT_OR, bm::distance_operation(), and bm::distance_metric_descriptor::result.

Referenced by bm::operation_deserializer< BV >::deserialize_xor(), OrOperationsTest(), bm::iterator_deserializer< BV, SerialIterator >::process_id_list(), bm::process_operation(), and StressTest().

◆ count_sub()

template<class BV >

BV::size_type bm::count_sub	(	const BV &	bv1,
		const BV &	bv2
	)

noexcept

Computes bitcount of SUB operation of two bitsets.

Parameters

bv1	- Argument bit-vector.
bv2	- Argument bit-vector.

Returns: bitcount of the result

Definition at line 115 of file bmalgo.h.

References bm::COUNT_SUB_AB, bm::distance_operation(), and bm::distance_metric_descriptor::result.

Referenced by bm::operation_deserializer< BV >::deserialize_xor(), bm::iterator_deserializer< BV, SerialIterator >::process_id_list(), bm::process_operation(), StressTest(), and SubOperationsTest().

◆ count_xor()

template<class BV >

bm::distance_metric_descriptor::size_type bm::count_xor	(	const BV &	bv1,
		const BV &	bv2
	)

noexcept

Computes bitcount of XOR operation of two bitsets.

Parameters

bv1	- Argument bit-vector.
bv2	- Argument bit-vector.

Returns: bitcount of the result

Definition at line 81 of file bmalgo.h.

References bm::COUNT_XOR, bm::distance_operation(), and bm::distance_metric_descriptor::result.

Referenced by bm::operation_deserializer< BV >::deserialize_xor(), bm::iterator_deserializer< BV, SerialIterator >::process_id_list(), bm::process_operation(), StressTest(), and XorOperationsTest().

◆ export_array()

template<typename BV , class It >

void bm::export_array	(	BV &	bv,
		It	first,
		It	last
	)

Export bitset from an array of binary data representing the bit vector.

Input array can be array of ints, chars or other native C types. Method works with iterators, which makes it compatible with STL containers and C arrays

Parameters

bv	- destination bitvector
first	- first element of the iterated sequence
last	- last element of the iterated sequence

Definition at line 1423 of file bmalgo_impl.h.

References BM_ASSERT, bm::BM_BIT, first(), i, last(), bm::set_block_size, bm::set_total_blocks, and tmp.

Referenced by ExportTest().

◆ for_each_bit()

template<class BV , class Func >

int bm::for_each_bit	(	const BV &	bv,
		Func &	bit_functor
	)

bit-vector visitor scanner to traverse each 1 bit using C++ visitor

Parameters

bv	- bit vector to scan
bit_functor	- visitor: should support add_bits(), add_range()

Returns: return code from functor (< 0 indicates to interrupt iteration and exit)

See also: for_each_bit_range visit_each_bit

Definition at line 202 of file bmalgo.h.

References bm::avx2_test_all_zero_wave(), BM_SCANNER_OP, FULL_BLOCK_FAKE_ADDR, FULL_SUB_BLOCK_REAL_ADDR, i, r(), bm::set_sub_array_size, and bm::sse42_test_all_zero_wave().

Referenced by bm::rank_compressor< BV >::compress_by_source(), and bm::visit_each_bit().

◆ for_each_bit_range()

template<class BV , class Func >

int bm::for_each_bit_range	(	const BV &	bv,
		typename BV::size_type	left,
		typename BV::size_type	right,
		Func &	bit_functor
	)

bit-vector range visitor to traverse each 1 bit

Parameters

bv	- bit vector to scan
right	- start of closed interval [from..to]
left	- end of close interval [from..to]
bit_functor	- visitor: should support add_bits(), add_range()

See also: for_each_bit

Definition at line 266 of file bmalgo.h.

References BM_ASSERT, bm::for_each_bit_range_no_check(), bm::id_max, and bm::xor_swap().

Referenced by BvectorBitForEachTest(), bm::visit_each_bit_range(), and VisitorAllRangeTest().

◆ rank_range_split()

template<typename BV , typename PairVect >

void bm::rank_range_split	(	const BV &	bv,
		typename BV::size_type	rank,
		PairVect &	target_v
	)

Algorithm to identify bit-vector ranges (splits) for the rank.

Rank range split algorithm walks the bit-vector to create list of non-overlapping ranges [s1..e1],[s2..e2]...[sN...eN] with requested (rank) number of 1 bits. All ranges should be the same popcount weight, except the last one, which may have less. Scan is progressing from left to right so result ranges will be naturally sorted.

Parameters

bv	- bit vector to perform the range split scan
rank	- requested number of bits in each range if 0 it will create single range [first..last] to cover the whole bv
target_v	- [out] STL(or STL-like) vector of pairs to keep pairs results

Definition at line 394 of file bmalgo.h.

References first(), and last().

Referenced by RankRangeSplitTest().

◆ visit_each_bit()

template<class BV >

int bm::visit_each_bit	(	const BV &	bv,
		void *	handle_ptr,
		bit_visitor_callback_type	callback_ptr
	)

bvector visitor scanner to traverse each 1 bit using C callback

Parameters

bv	- bit vector to scan
handle_ptr	- handle to private memory used by callback
callback_ptr	- callback function

Returns: exit code form call back function

See also: bit_visitor_callback_type

Definition at line 336 of file bmalgo.h.

References bm::for_each_bit().

Referenced by BvectorBitForEachTest(), and RangeForEachTest().

◆ visit_each_bit_range()

template<class BV >

int bm::visit_each_bit_range	(	const BV &	bv,
		typename BV::size_type	left,
		typename BV::size_type	right,
		void *	handle_ptr,
		bit_visitor_callback_type	callback_ptr
	)

bvector visitor scanner to traverse each bits in range (C callback)

Parameters

bv	- bit vector to scan
left	- from [left..right]
right	- to [left..right]
handle_ptr	- handle to private memory used by callback
callback_ptr	- callback function

Returns: exit code form call back function

See also: bit_visitor_callback_type for_each_bit

Definition at line 362 of file bmalgo.h.

References bm::for_each_bit_range().

Referenced by BvectorBitForEachTest().

Variable Documentation

◆ agg_compute_counts

const bool bm::agg_compute_counts = true

Definition at line 53 of file bmaggregator.h.

◆ agg_disable_counts

const bool bm::agg_disable_counts = false

Definition at line 54 of file bmaggregator.h.

◆ agg_disable_result_bvectors

const bool bm::agg_disable_result_bvectors = false

Definition at line 52 of file bmaggregator.h.

◆ agg_disable_search_masks

const bool bm::agg_disable_search_masks = false

Definition at line 55 of file bmaggregator.h.

◆ agg_produce_result_bvectors

const bool bm::agg_produce_result_bvectors = true

Definition at line 51 of file bmaggregator.h.

Modules

Classes

Functions

Aggregator traits and control constants

Detailed Description

Typedef Documentation

◆ agg_opt_bvect_and_counts

◆ agg_opt_disable_bvects_and_counts

◆ agg_opt_only_counts

Function Documentation

◆ aggregator_pipeline_execute()

◆ any_and()

◆ any_or()

◆ any_sub()

◆ any_xor()

◆ combine_and()

◆ combine_and_sorted()

◆ combine_or()

◆ combine_sub()

◆ combine_xor()

◆ count_and()

◆ count_intervals()

◆ count_or()

◆ count_sub()

◆ count_xor()

◆ export_array()

◆ for_each_bit()

◆ for_each_bit_range()

◆ rank_range_split()

◆ visit_each_bit()

◆ visit_each_bit_range()

Variable Documentation

◆ agg_compute_counts

◆ agg_disable_counts

◆ agg_disable_result_bvectors

◆ agg_disable_search_masks

◆ agg_produce_result_bvectors