pasta::FlatRankSelect< optimized_for, find_with, VectorType > Class Template Reference

Select support for BitVector that can be used as an alternative to RankSelect for bit vectors up to length 2^40. More...

#include <flat_rank_select.hpp>

Inheritance diagram for pasta::FlatRankSelect< optimized_for, find_with, VectorType >:

Collaboration diagram for pasta::FlatRankSelect< optimized_for, find_with, VectorType >:

Public Member Functions
	FlatRankSelect ()=default
	Default constructor w/o parameter.
	FlatRankSelect (VectorType &bv)
	Constructor. Creates the auxiliary information for efficient rank and select queries.
	FlatRankSelect (FlatRankSelect &&)=default
	Default move constructor.
FlatRankSelect &	operator= (FlatRankSelect &&)=default
	Default move assignment.
	~FlatRankSelect ()=default
	Destructor. Deleting manually created arrays.
size_t	select0 (size_t rank) const
	Get position of specific zero, i.e., select.
size_t	select1 (size_t rank) const
	Get position of specific one, i.e., select.
size_t	space_usage () const final
	Estimate for the space usage.
Public Member Functions inherited from pasta::FlatRank< OptimizedFor::DONT_CARE >
	FlatRank ()=default
	Default constructor w/o parameter.
	FlatRank (BitVector &bv)
	Constructor. Creates the auxiliary information for efficient rank queries.
size_t	rank0 (size_t index) const
	Computes rank of zeros.
size_t	rank1 (size_t index) const
	Computes rank of ones.

Additional Inherited Members
Protected Attributes inherited from pasta::FlatRank< OptimizedFor::DONT_CARE >
size_t	data_size_
	Size of the bit vector the rank support is constructed for.
BitVector::RawDataConstAccess	data_
	Pointer to the data of the bit vector.
tlx::SimpleVector< BigL12Type, tlx::SimpleVectorMode::NoInitNoDestroy >	l12_
	Array containing the information about the L1- and L2-blocks.
size_t	l12_end_
	Number of actual existing BigL12-blocks (important for scanning)

Detailed Description

template<OptimizedFor optimized_for = OptimizedFor::DONT_CARE, FindL2FlatWith find_with = FindL2FlatWith::LINEAR_SEARCH, typename VectorType = BitVector>
class pasta::FlatRankSelect< optimized_for, find_with, VectorType >

Select support for BitVector that can be used as an alternative to RankSelect for bit vectors up to length 2^40.

The select support is an extended and engineered version of the popcount select support by Zhou et al. [2]. Similar to the FlatRank support, the highest utility array (L0) is removed. For more details see FlatRank and BigL12Type.

Template Parameters

use_intrinsic	Set true if intrinsic functions should be used to find L2-block where the select query has to search the last 512 bits. Currently slower than simple loop.
OptimizedFor	Compile time option to optimize data structure for either 0, 1, or neither type of query. Default is neither.
use_intrinsic	bool flag that specifies whether intrinsics should be used during select queries (currently using them is slower). Default is false.
VectorType	Type of the vector the rank and select data structure is constructed for, e.g., plain BitVector or a compressed bit vector.

Constructor & Destructor Documentation

FlatRankSelect()

template<OptimizedFor optimized_for = OptimizedFor::DONT_CARE, FindL2FlatWith find_with = FindL2FlatWith::LINEAR_SEARCH, typename VectorType = BitVector>

pasta::FlatRankSelect< optimized_for, find_with, VectorType >::FlatRankSelect ( VectorType & bv )

inline

Constructor. Creates the auxiliary information for efficient rank and select queries.

Parameters

bv	Vector of type VectorType the rank and select structure is created for.

Member Function Documentation

select0()

template<OptimizedFor optimized_for = OptimizedFor::DONT_CARE, FindL2FlatWith find_with = FindL2FlatWith::LINEAR_SEARCH, typename VectorType = BitVector>

size_t pasta::FlatRankSelect< optimized_for, find_with, VectorType >::select0 ( size_t rank ) const

inlinenodiscard

Get position of specific zero, i.e., select.

Parameters

rank	Rank of zero the position is searched for.

Returns

Position of the rank-th zero.

select1()

template<OptimizedFor optimized_for = OptimizedFor::DONT_CARE, FindL2FlatWith find_with = FindL2FlatWith::LINEAR_SEARCH, typename VectorType = BitVector>

size_t pasta::FlatRankSelect< optimized_for, find_with, VectorType >::select1 ( size_t rank ) const

inlinenodiscard

Get position of specific one, i.e., select.

Parameters

rank	Rank of one the position is searched for.

Returns

Position of the rank-th one.

space_usage()

template<OptimizedFor optimized_for = OptimizedFor::DONT_CARE, FindL2FlatWith find_with = FindL2FlatWith::LINEAR_SEARCH, typename VectorType = BitVector>

size_t pasta::FlatRankSelect< optimized_for, find_with, VectorType >::space_usage ( ) const

inlinenodiscardfinalvirtual

Estimate for the space usage.

Returns

Number of bytes used by this data structure.

Reimplemented from pasta::FlatRank< OptimizedFor::DONT_CARE >.

---

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

• include/pasta/bit_vector/support/flat_rank_select.hpp