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

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

#include <flat_rank.hpp>

Public Member Functions

 FlatRank ()=default
 Default constructor w/o parameter.
 
 FlatRank (VectorType &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...
 

Protected Attributes

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_ = 0
 Number of actual existing BigL12-blocks (important for scanning)
 

Friends

template<OptimizedFor o, FindL2FlatWith f, typename v >
class FlatRankSelect
 Friend class, using internal information l12_.
 

Detailed Description

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

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

The rank support is an extended and engineered version of the popcount rank support by Zhou et al. [2]. This flat rank support hoverer removes the highest utility array (L0) and also groups twice as many L2-blocks in a single L1-block. This allows us to store more information—most importantly the number of ones w.r.t. the beginning of the L1-block—in the L2-blocks. For the L1/2-block layout see BigL12Type.

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 data structure is constructed for, e.g., plain BitVector or a compressed bit vector.

Constructor & Destructor Documentation

◆ FlatRank()

template<OptimizedFor optimized_for = OptimizedFor::DONT_CARE, typename VectorType = BitVector>
pasta::FlatRank< optimized_for, VectorType >::FlatRank ( VectorType &  bv)
inline

Constructor. Creates the auxiliary information for efficient rank queries.

Parameters
bvVector of VectorType the rank structure is created for.

Member Function Documentation

◆ rank0()

template<OptimizedFor optimized_for = OptimizedFor::DONT_CARE, typename VectorType = BitVector>
size_t pasta::FlatRank< optimized_for, VectorType >::rank0 ( size_t  index) const
inline

Computes rank of zeros.

Parameters
indexIndex the rank of zeros is computed for.
Returns
Number of zeros (rank) before position index.

◆ rank1()

template<OptimizedFor optimized_for = OptimizedFor::DONT_CARE, typename VectorType = BitVector>
size_t pasta::FlatRank< optimized_for, VectorType >::rank1 ( size_t  index) const
inline

Computes rank of ones.

Parameters
indexIndex the rank of ones is computed for.
Returns
Number of ones (rank) before position index.

◆ space_usage()

template<OptimizedFor optimized_for = OptimizedFor::DONT_CARE, typename VectorType = BitVector>
virtual size_t pasta::FlatRank< optimized_for, VectorType >::space_usage ( ) const
inlinevirtual

Estimate for the space usage.

Returns
Number of bytes used by this data structure.

Reimplemented in pasta::FlatRankSelect< optimized_for, find_with, VectorType >.


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