pixie::WaveletTreeBase< Impl, Symbol > Class Template Reference

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

#include <wavelet_tree.h>

Inheritance diagram for pixie::WaveletTreeBase< Impl, Symbol >:

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 (Symbol symbol, std::size_t end_position) const
	Count occurrences of symbol in [0, end_position).
std::size_t	select (Symbol symbol, std::size_t rank) const
	Return the position of the rank-th occurrence of symbol.
std::vector< Symbol >	get_segment (std::size_t begin, std::size_t end) const
	Reconstruct the sequence range [@p begin, @p end).

Detailed Description

template<class Impl, WaveletTreeSymbol Symbol>
class pixie::WaveletTreeBase< Impl, Symbol >

CRTP facade for wavelet-tree queries.

See also

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

Template Parameters

Impl	Concrete implementation exposing the documented *_impl() extension points.
Symbol	Unsigned symbol type returned by access operations and accepted by rank/select operations.

Member Function Documentation

empty()

template<class Impl, WaveletTreeSymbol Symbol>

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

inline

Check whether the indexed sequence is empty.

Returns

true when size() == 0.

get_segment()

template<class Impl, WaveletTreeSymbol Symbol>

std::vector< Symbol > pixie::WaveletTreeBase< Impl, Symbol >::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, WaveletTreeSymbol Symbol>

std::size_t pixie::WaveletTreeBase< Impl, Symbol >::rank ( Symbol 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, WaveletTreeSymbol Symbol>

std::size_t pixie::WaveletTreeBase< Impl, Symbol >::select ( Symbol 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, WaveletTreeSymbol Symbol>

std::size_t pixie::WaveletTreeBase< Impl, Symbol >::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