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

Select support for BitVector. More...

#include <wide_rank_select.hpp>

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

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

Public Member Functions
	WideRankSelect ()=default
	Default constructor w/o parameter.
	WideRankSelect (VectorType &bv)
	Constructor. Creates the auxiliary information for efficient rank and select queries.
	WideRankSelect (WideRankSelect &&other)=default
	Default move constructor.
WideRankSelect &	operator= (WideRankSelect &&other)=default
	Default move assignment.
	~WideRankSelect ()=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 override
	Estimate for the space usage.
Public Member Functions inherited from pasta::WideRank< OptimizedFor::DONT_CARE >
	WideRank ()=default
	Default constructor w/o parameter.
	WideRank (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.

Detailed Description

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

Select support for BitVector.

The rank and select support is based on popcount and described in detail by Zhou et al. [2]. The data structure consists of three levels (L0, L1, and L2) that contain different information regarding the popcount of the current block or all previous blocks.

Since the rank data structures used by rank are a strict subset of the data structures required by select, we provide a (ever so slightly) more space-efficient rank only data structure in BitVectorRank.

Template Parameters

OptimizedFor	Compile time option to optimize data structure for either 0, 1, or no specific type of query.
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

WideRankSelect()

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

pasta::WideRankSelect< optimized_for, find_with, VectorType >::WideRankSelect ( 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, FindL2WideWith find_with = FindL2WideWith::LINEAR_SEARCH, typename VectorType = BitVector>

size_t pasta::WideRankSelect< 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, FindL2WideWith find_with = FindL2WideWith::LINEAR_SEARCH, typename VectorType = BitVector>

size_t pasta::WideRankSelect< 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, FindL2WideWith find_with = FindL2WideWith::LINEAR_SEARCH, typename VectorType = BitVector>

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

inlinenodiscardoverridevirtual

Estimate for the space usage.

Returns

Number of bytes used by this data structure.

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

---

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

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