Class CompactRankSelect

• Defined in File CompactRankSelect.h

Nested Relationships

Nested Types

• Struct CompactRankSelect::Entry

Class Documentation

class CompactRankSelect

a static vector of bits with rank and select in about 3.5% of its bits

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<CompactRankSelect, bool>

using iterator = const_iterator

Public Functions

inline CompactRankSelect(void)

explicit CompactRankSelect(BitVector b)

the directory of the bits b, which it keeps

CompactRankSelect(std::span<const Word> w, std::size_t n)

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

Pre:

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

inline const BitVector &bits(void) const

the bits

inline std::size_t size(void) const

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

the bit i

Pre:

i < size()

inline std::size_t ones(void) const

the number of 1s

inline 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()

inline 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()

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

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

inline const_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const