|
| 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.
|
|
RankSelect & | operator= (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.
|
|
| 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.
|
|
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.
|
|
|
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.
|
|
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
-
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 and select data structure is constructed for, e.g., plain BitVector or a compressed bit vector. |