bv::query_support< dtype, leaf_type, block_size > Class Template Reference

Support structure for bv::bit_vector to enable fast queries. More...

#include <query_support.hpp>

Public Member Functions
void	append (leaf_type *leaf)
	Add leaf reference to the support structure. More...
void	finalize ()
	Prepare the structure for querying. More...
dtype	size () const
	Number of bits stored in the bit vector. More...
dtype	p_sum () const
	Number of 1-bits stored in the bit vector. More...
bool	at (dtype i) const
	Return value of bit at index \(i\) in the underlying bit vector. More...
dtype	rank (dtype i) const
	Number of 1-bits up to position \(i\) in the underlying bit vector. More...
dtype	select (dtype i) const
	Index of the \(i\)th 1-bit in the data structure. More...
uint64_t	bit_size () const
	Number of bits allocated for the support structure. More...
void	print (bool internal_only) const
	Outputs json representation of the support structure. More...

Protected Member Functions
dtype	s_select (dtype i) const
	Locate the block containing the \(i\)th 1-bit. More...
dtype	dumb_select (dtype i) const
	Index of the \(i\)th 1-bit in the data structure. More...

Protected Attributes
dtype	size_ = 0
dtype	sum_ = 0
std::vector< r_elem< dtype, leaf_type > >	elems_

Detailed Description

template<class dtype, class leaf_type, dtype block_size>
class bv::query_support< dtype, leaf_type, block_size >

Support structure for bv::bit_vector to enable fast queries.

Precalculates results for rank, select and access queries along with leaf pointers to enable faster queries while the bit vector remains unmodified.

Leaves should be appended in natural order. After all leaves have been added, the structure should be finalized to ensure properly precalculated select blocks.

If the underlying structure changes, querying the support structure may lead to undefined behaviour. The support structure should be discarded (delete(q)) as it becomes outdated.

Template Parameters

dtype	Integer type to use for indexing (uint32_t or uint64_t).
leaf_type	Leaf type used by the relevant bv::bit_vector.

Member Function Documentation

append()

template<class dtype , class leaf_type , dtype block_size>

void bv::query_support< dtype, leaf_type, block_size >::append ( leaf_type *  leaf )

inline

Add leaf reference to the support structure.

Block results are calculated and stored for \(\approx \frac{\mathrm{leaf->size()}}{\mathrm{block\_size}}\) positions for the leaf.

Parameters

leaf	Pointer to the leaf to add.

at()

template<class dtype , class leaf_type , dtype block_size>

bool bv::query_support< dtype, leaf_type, block_size >::at ( dtype  i ) const

inline

Return value of bit at index \(i\) in the underlying bit vector.

Uses precalculated partial block sums to locate the leaf containing the \(i\)^th bit in constant time.

Parameters

i	Index to query.

Returns

Value of bit at index \(i\).

bit_size()

template<class dtype , class leaf_type , dtype block_size>

uint64_t bv::query_support< dtype, leaf_type, block_size >::bit_size ( ) const

inline

Number of bits allocated for the support structure.

The space allocated for the leaves is not included in the total as those are accounted for by the bv.bit_size().

Returns

Number of bits allocated for the support structure.

dumb_select()

template<class dtype , class leaf_type , dtype block_size>

dtype bv::query_support< dtype, leaf_type, block_size >::dumb_select ( dtype  i ) const

inlineprotected

Index of the \(i\)^th 1-bit in the data structure.

Used for sparse or non-uniformly distributed bit vectors where direct indexing fails to calculate the correct target block in constant time.

Parameters

i	Selection target.

Returns

\(\underset{j \in [0..n)}{\mathrm{arg min}}\left(\sum_{k = 0}^j \mathrm{bv}[k]\right) = i\).

finalize()

template<class dtype , class leaf_type , dtype block_size>

void bv::query_support< dtype, leaf_type, block_size >::finalize ( )

inline

Prepare the structure for querying.

Precalculates and stores results for some select queries to speed up subsequent select queries.

For sparse bit vectors where p_sum < size / block_size, locations for all 1-bits are precalculated, to allow constant time select queries.

p_sum()

template<class dtype , class leaf_type , dtype block_size>

dtype bv::query_support< dtype, leaf_type, block_size >::p_sum ( ) const

inline

Number of 1-bits stored in the bit vector.

Returns

Number of 1-bits stored in the bit vector.

print()

template<class dtype , class leaf_type , dtype block_size>

void bv::query_support< dtype, leaf_type, block_size >::print ( bool  internal_only ) const

inline

Outputs json representation of the support structure.

Parameters

internal_only

Should raw leaf data be omitted from the output.

rank()

template<class dtype , class leaf_type , dtype block_size>

dtype bv::query_support< dtype, leaf_type, block_size >::rank ( dtype  i ) const

inline

Number of 1-bits up to position \(i\) in the underlying bit vector.

Precalculated results are used to locate the the leaf containing the \(i\)^th bit in constant time. at most \(\mathrm{block\_size}\) are read from the leaf, to calculate the result for the rank query based on precalculated block results.

Parameters

i	Number of elements to include in the "summation".

Returns

\(\sum_{i = 0}^{i - 1} \mathrm{bv}[i]\).

s_select()

template<class dtype , class leaf_type , dtype block_size>

dtype bv::query_support< dtype, leaf_type, block_size >::s_select ( dtype  i ) const

inlineprotected

Locate the block containing the \(i\)^th 1-bit.

Used for building the select support index for dense bit vectors.

Parameters

i	Selection target.

Returns

The index of the block containing the \(i\)^th 1-bit.

select()

template<class dtype , class leaf_type , dtype block_size>

dtype bv::query_support< dtype, leaf_type, block_size >::select ( dtype  i ) const

inline

Index of the \(i\)^th 1-bit in the data structure.

For fairly dense approximately uniformly distributed bit vectors, the block containing the \(i\)^th 1-bit can be located in constant time. For less dense or non-uniformly distributed bit vectors the block containing the \(i\)^th 1-bit can be located either in constant time or logarithmic time depending on the local bit distribution in the vicinity of the \(i\)^th bit.

After the correct block is located, at most block_size bits are scanned for a single leaf.

For sparse bit vectors where p_sum < size / block_size, locations for all 1-bits have been precalculated, allowing constant time select queries.

Parameters

i	Selection target.

Returns

\(\underset{j \in [0..n)}{\mathrm{arg min}}\left(\sum_{k = 0}^j \mathrm{bv}[k]\right) = i\).

size()

template<class dtype , class leaf_type , dtype block_size>

dtype bv::query_support< dtype, leaf_type, block_size >::size ( ) const

inline

Number of bits stored in the bit vector.

Returns

Number of bits stored in the bit vector.

Member Data Documentation

elems_

template<class dtype , class leaf_type , dtype block_size>

std::vector<r_elem<dtype, leaf_type> > bv::query_support< dtype, leaf_type, block_size >::elems_

protected

Initial value:

=
        std::vector<r_elem<dtype, leaf_type>>()

---

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

• bit_vector/internal/query_support.hpp