Class WaveletMatrix

• Defined in File WaveletMatrix.h

Class Documentation

class WaveletMatrix

a static sequence of integers of w bits with access, rank, select and the range quantiles in O( w ) time

Public Types

using value_type = std::uint64_t

using size_type = std::size_t

using difference_type = std::ptrdiff_t

using reference = std::uint64_t

using const_reference = std::uint64_t

using const_iterator = SubscriptIterator<WaveletMatrix, std::uint64_t>

using iterator = const_iterator

Public Functions

WaveletMatrix(void) = default

explicit WaveletMatrix(std::span<const std::uint64_t> x, int w = 0)

the sequence x, its items of w bits (0: the bits of the largest one)

Pre:

0 <= w <= 64 and the items are below 2^w

inline std::size_t size(void) const

inline bool empty(void) const

inline int width(void) const

the bits of an item

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

the item i

Pre:

i < size()

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

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

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

Pre:

i <= size()

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

the place of the k-th c

Pre:

1 <= k <= rank( c , size() )

std::uint64_t quantile(std::size_t i, std::size_t j, std::size_t k) const

the k-th smallest item of the places [ i , j ), from k = 0

Pre:

i <= j <= size() and k < j - i

std::size_t countLess(std::size_t i, std::size_t j, std::uint64_t c) const

the number of the items below c in the places [ i , j )

Pre:

i <= j <= size()

std::size_t sizeInBits(void) const

the bits of the levels and of their directories

inline const_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const