Template Class HuffmanWaveletTree

Nested Relationships

Nested Types

Class Documentation

template<class RS = RankSelect>
class HuffmanWaveletTree

a static sequence of symbols in about H0 + 1 bits each, with access, rank and select in time proportional to the length of a code; RS is the rank and select of its bits, RankSelect or CompactRankSelect

Public Functions

HuffmanWaveletTree(void) = default
explicit HuffmanWaveletTree(std::span<const std::uint32_t> x, bool withSelect = true)

the sequence x, of symbols below its largest one plus 1, with select if asked for (else the directory of RankSelect keeps no inventory)

Pre:

x.size() < 2^40

inline std::size_t size(void) const
inline bool empty(void) const
inline std::size_t sigma(void) const

the symbols are below sigma()

std::uint32_t access(std::size_t i) const

the item i

Pre:

i < size()

inline std::uint32_t operator[](std::size_t i) const
std::pair<std::uint32_t, std::size_t> accessRank(std::size_t i) const

the item i and its occurrences in [ 0 , i ), by one descent

Pre:

i < size()

std::size_t rank(std::uint32_t c, std::size_t i) const

the occurrences of c in [ 0 , i )

Pre:

i <= size()

std::pair<std::size_t, std::size_t> rank(std::uint32_t c, std::size_t i, std::size_t j) const

the occurrences of c in [ 0 , i ) and in [ 0 , j ), by one descent

Pre:

i <= j <= size()

std::size_t select(std::uint32_t c, std::size_t k) const

the place of the k-th occurrence of c

Pre:

1 <= k <= rank( c , size() ), and select was asked for

inline int codeLength(std::uint32_t c) const

the length of the code of c, 0 if c is not in the sequence

std::size_t sizeInBits(void) const

the bits of the tree: its vector with the directory, the nodes and the codes