pasta_bit_vector  1.0.1
Bit Vector with Compact and Fast Rank and Select Support
Loading...
Searching...
No Matches
pasta::RankSelect< optimized_for, VectorType > Class Template Referencefinal

Select support for BitVector. More...

#include <rank_select.hpp>

Inheritance diagram for pasta::RankSelect< optimized_for, VectorType >:
Collaboration 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.
 
 RankSelect (RankSelect &&other)=default
 Default move constructor.
 
RankSelectoperator= (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.
 
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::Rank< OptimizedFor::DONT_CARE, BitVector >
 Rank ()=default
 Default constructor w/o parameter.
 
 Rank (BitVector &bv)
 Constructor. Creates the auxiliary information for efficient rank queries.
 
 Rank (Rank &&other)=default
 Default move constructor.
 
Rankoperator= (Rank &&other)=default
 Default move assignment.
 
 ~Rank ()=default
 Destructor. Deleting manually created arrays.
 
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

- 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.
 
BitVector::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
OptimizedForCompile time option to optimize data structure for either 0, 1, or no specific type of query.
VectorTypeType 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
bvVector 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
inlinenodiscard

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

Parameters
rankRank 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
inlinenodiscard

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

Parameters
rankRank 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
inlinenodiscardfinalvirtual

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: