pasta::RankSelect< optimized_for, VectorType > Class Template Reference

Select support for BitVector. More...

#include <rank_select.hpp>

Inheritance diagram for pasta::RankSelect< optimized_for, VectorType >:

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

Additional Inherited Members
Public Attributes inherited from pasta::Rank< OptimizedFor::DONT_CARE, BitVector >
size_t	data_size_
	Size of the bit vector the rank support is constructed for.
VectorType::RawDataConstAccess	data_
	Pointer to the data of the bit vector.
size_t const	bit_size_
	Size of the bit vector in bits (only used for debug asserts)
tlx::SimpleVector< uint64_t, tlx::SimpleVectorMode::NoInitNoDestroy >	l0_
	Array containing the number of set bits in the L0-blocks.
tlx::SimpleVector< L12Type, tlx::SimpleVectorMode::NoInitNoDestroy >	l12_
	Array containing the information about the L1- and L2-blocks.

Detailed Description

template<OptimizedFor optimized_for = OptimizedFor::DONT_CARE, typename VectorType = BitVector>
class pasta::RankSelect< optimized_for, 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

RankSelect()

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

pasta::RankSelect< optimized_for, VectorType >::RankSelect ( VectorType &  bv )

inline

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

Parameters

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

Member Function Documentation

select0()

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

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

inline

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, typename VectorType = BitVector>

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

inline

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, typename VectorType = BitVector>

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

inlinefinalvirtual

Estimate for the space usage.

Returns

Number of bytes used by this data structure.

Reimplemented from pasta::Rank< OptimizedFor::DONT_CARE, BitVector >.

---

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

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