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.
size_t	rank0 (size_t index) const
	Computes rank of zeros.
size_t	rank1 (size_t index) const
	Computes rank of ones.
virtual size_t	space_usage () const
	Estimate for the space usage.

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

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 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

bv	Vector 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

inlinenodiscard

Computes rank of zeros.

Parameters

index

Index 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

inlinenodiscard

Computes rank of ones.

Parameters

index

Index 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

inlinenodiscardvirtual

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:

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