Template Class BasicRankSelect

Defined in File RankSelect.h

Nested Relationships

Nested Types

Inheritance Relationships

Base Type

public ADS::RankSelectOptions (Struct RankSelectOptions)

Class Documentation

template<bool Lazy> class BasicRankSelect : public ADS::RankSelectOptions 

a static vector of bits with rank and select in O( 1 ) time, the inventories of select built in the constructor if not Lazy, and at the first select of each value if Lazy

Public Types

using value_type = bool

using size_type = std::size_t

using difference_type = std::ptrdiff_t

using reference = bool

using const_reference = bool

using const_iterator = SubscriptIterator<BasicRankSelect, bool>

using iterator = const_iterator 

Public Functions

BasicRankSelect(void)

explicit BasicRankSelect(BitVector b, Selects s = Selects::BOTH): the directory of the bits b, which it keeps, with the selects s

BasicRankSelect(std::span<const Word> w, std::size_t n, Selects s = Selects::BOTH)

the directory of the n bits of the words w, copied as they are counted, with the selects s

Pre:: w.size() >= ceil( n / 64 )

BasicRankSelect(const BasicRankSelect &o): a copy, with the inventories that o has built

BasicRankSelect(BasicRankSelect &&o) noexcept: a move, with the inventories that o has built

BasicRankSelect &operator=(const BasicRankSelect &o)

BasicRankSelect &operator=(BasicRankSelect &&o) noexcept

~BasicRankSelect(void) = default

const BitVector &bits(void) const: the bits

std::size_t size(void) const

bool operator[](std::size_t i) const

the bit i

Pre:: i < size()

std::size_t ones(void) const: the number of 1s

std::size_t zeros(void) const: the number of 0s

std::size_t rank1(std::size_t i) const

the number of 1s in the places [ 0 , i )

Pre:: i <= size()

std::size_t rank0(std::size_t i) const

the number of 0s in the places [ 0 , i )

Pre:: i <= size()

std::size_t select1(std::size_t k) const

the place of the k-th 1

Pre:: 1 <= k <= ones(), and the selects of the 1s were asked for
Post:: the bit there is 1 and rank1() of it is k - 1

std::size_t select0(std::size_t k) const

the place of the k-th 0

Pre:: 1 <= k <= zeros(), and the selects of the 0s were asked for
Post:: the bit there is 0 and rank0() of it is k - 1

std::size_t directoryBits(void) const: the bits of the directory, beyond those of the vector, with those of the inventories of the selects asked for, built or not

inline const_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const