pasta::bit_vector  v1.0.0
Compact and Fast Rank and Select Data Structure for Bit Vectors
pasta::FlatRankSelect< optimized_for, find_with, VectorType > Class Template Referencefinal

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 >:
pasta::FlatRank< OptimizedFor::DONT_CARE >

Public Member Functions

 FlatRankSelect ()=default
 Default constructor w/o parameter.
 
 FlatRankSelect (VectorType &bv)
 Constructor. Creates the auxiliary information for efficient rank and select queries. More...
 
 FlatRankSelect (FlatRankSelect &&)=default
 Default move constructor.
 
FlatRankSelectoperator= (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. 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::FlatRank< OptimizedFor::DONT_CARE >
 FlatRank ()=default
 Default constructor w/o parameter.
 
 FlatRank (BitVector &bv)
 Constructor. Creates the auxiliary information for efficient rank queries. More...
 
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

- Protected Attributes inherited from pasta::FlatRank< OptimizedFor::DONT_CARE >
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.
 
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_intrinsicSet 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.
OptimizedForCompile time option to optimize data structure for either 0, 1, or neither type of query. Default is neither.
use_intrinsicbool flag that specifies whether intrinsics should be used during select queries (currently using them is slower). Default is false.
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

◆ 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
bvVector 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
inline

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, FindL2FlatWith find_with = FindL2FlatWith::LINEAR_SEARCH, typename VectorType = BitVector>
size_t pasta::FlatRankSelect< optimized_for, find_with, VectorType >::select1 ( size_t  rank) const
inline

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, FindL2FlatWith find_with = FindL2FlatWith::LINEAR_SEARCH, typename VectorType = BitVector>
size_t pasta::FlatRankSelect< optimized_for, find_with, VectorType >::space_usage ( ) const
inlinefinalvirtual

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: