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

Rank support for BitVector. More...

#include <rank.hpp>

Public Member Functions
	Rank ()=default
	Default constructor w/o parameter.
	Rank (VectorType &bv)
	Constructor. Creates the auxiliary information for efficient rank queries.
	Rank (Rank &&other)=default
	Default move constructor.
Rank &	operator= (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.
virtual size_t	space_usage () const
	Estimate for the space usage.

Public 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.
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::Rank< optimized_for, VectorType >

Rank support for BitVector.

The rank 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.

Note that rank support is also provided in addition to select support by RankSelect, which uses this rank support implementation internally.

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

Rank() [1/2]

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

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

inline

Constructor. Creates the auxiliary information for efficient rank queries.

Parameters

bv	Vector of type VectorType the rank structure is created for.

Rank() [2/2]

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

pasta::Rank< optimized_for, VectorType >::Rank ( Rank< optimized_for, VectorType > && other )

default

Default move constructor.

Parameters

other

Other rank data structure.

Member Function Documentation

operator=()

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

Rank & pasta::Rank< optimized_for, VectorType >::operator= ( Rank< optimized_for, VectorType > && other )

default

Default move assignment.

Parameters

other

Other rank data structure.

rank0()

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

size_t pasta::Rank< 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::Rank< optimized_for, VectorType >::rank1 ( size_t index ) const

inlinenodiscard

Computes rank of ones.

Parameters

index

Index the rank of ones is computed for.

Returns

Numbers of ones (rank) before position index.

space_usage()

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

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

inlinenodiscardvirtual

Estimate for the space usage.

Returns

Number of bytes used by this data structure.

Reimplemented in pasta::RankSelect< optimized_for, VectorType >.

---

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

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