pixie::WaveletTreeBase< Impl > Class Template Reference

CRTP facade for wavelet-tree queries. More...

#include <wavelet_tree.h>

Inheritance diagram for pixie::WaveletTreeBase< Impl >:

Public Member Functions
std::size_t	size () const
	Return the number of symbols in the indexed sequence.
bool	empty () const
	Check whether the indexed sequence is empty.
std::size_t	rank (std::uint64_t symbol, std::size_t end_position) const
	Count occurrences of symbol in [0, end_position).
std::size_t	select (std::uint64_t symbol, std::size_t rank) const
	Return the position of the rank-th occurrence of symbol.
std::vector< std::uint64_t >	get_segment (std::size_t begin, std::size_t end) const
	Reconstruct the sequence range [@p begin, @p end).

Detailed Description

template<class Impl>
class pixie::WaveletTreeBase< Impl >

CRTP facade for wavelet-tree queries.

See also

<pixie/wavelet_tree/implementations.h> for the available concrete implementations.

Member Function Documentation

empty()

template<class Impl>

bool pixie::WaveletTreeBase< Impl >::empty ( ) const

inline

Check whether the indexed sequence is empty.

Returns

true when size() == 0.

get_segment()

template<class Impl>

std::vector< std::uint64_t > pixie::WaveletTreeBase< Impl >::get_segment ( std::size_t begin, std::size_t end ) const

inline

Reconstruct the sequence range [@p begin, @p end).

Parameters

begin	First zero-based sequence position.
end	One past the last sequence position; must not exceed size().

Returns

Symbols in the requested half-open range.

rank()

template<class Impl>

std::size_t pixie::WaveletTreeBase< Impl >::rank ( std::uint64_t symbol, std::size_t end_position ) const

inline

Count occurrences of symbol in [0, end_position).

Parameters

symbol	Symbol in the indexed alphabet.
end_position	Prefix boundary in [0, size()].

Returns

Number of occurrences, or zero for a symbol outside the alphabet.

select()

template<class Impl>

std::size_t pixie::WaveletTreeBase< Impl >::select ( std::uint64_t symbol, std::size_t rank ) const

inline

Return the position of the rank-th occurrence of symbol.

Parameters

symbol	Symbol in the indexed alphabet.
rank	One-based occurrence rank.

Returns

Zero-based sequence position, or size() when absent.

size()

template<class Impl>

std::size_t pixie::WaveletTreeBase< Impl >::size ( ) const

inline

Return the number of symbols in the indexed sequence.

Returns

Logical sequence length.

---

The documentation for this class was generated from the following file:

• include/pixie/wavelet_tree.h