pixie::WaveletTreeIndex< Storage > Class Template Reference

Inheritance diagram for pixie::WaveletTreeIndex< Storage >:

Public Member Functions
	WaveletTreeIndex (size_t alphabet_size, std::span< const uint64_t > data, const WaveletTreeBuildType build_type=WaveletTreeBuildType::Standard)
size_t	rank_impl (uint64_t symbol, size_t pos) const
	Rank of specified symbol up to position pos (exclusive)
size_t	select_impl (uint64_t symbol, size_t rank) const
	Select the position of the rank-th specified symbol (1-indexed)
std::vector< uint64_t >	get_segment_impl (size_t begin, size_t end) const
	Accumulates the original data segment.
size_t	size_impl () const
void	serialize (pixie::OutputBitStream &bs) const
	Writes a wavelet tree serialization to the bit stream.
Public Member Functions inherited from pixie::WaveletTreeBase< WaveletTreeIndex< AlignedStorage > >
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).

Static Public Member Functions
static WaveletTreeIndex< ReadOnlyStorageView >	deserialize (std::span< const std::byte > &data)

Constructor & Destructor Documentation

WaveletTreeIndex()

template<StorageImplementation Storage = AlignedStorage>

pixie::WaveletTreeIndex< Storage >::WaveletTreeIndex ( size_t alphabet_size, std::span< const uint64_t > data, const WaveletTreeBuildType build_type = WaveletTreeBuildType::Standard )

inline

Parameters

alphabet_size	Size of the alphabet
data	Original text. Its characters are from the range [0, alphabet_size)
build_type	Either Standard or Huffman. This effects on how the wavelet tree builds: like segment tree on trivially sorted characters or like in Huffman algorithm

Standard: Just calls build_node Huffman: Reorders characters with respect to Huffman algorithm and then calls build_node with specific get_middle function

Member Function Documentation

get_segment_impl()

template<StorageImplementation Storage = AlignedStorage>

std::vector< uint64_t > pixie::WaveletTreeIndex< Storage >::get_segment_impl ( size_t begin, size_t end ) const

inline

Accumulates the original data segment.

Parameters

begin	Begin of the segment
end	End of the segment

Returns

Queried segment of data

rank_impl()

template<StorageImplementation Storage = AlignedStorage>

size_t pixie::WaveletTreeIndex< Storage >::rank_impl ( uint64_t symbol, size_t pos ) const

inline

Rank of specified symbol up to position pos (exclusive)

Parameters

symbol	The character that the query is about
pos	Character index in [0, size()]

Returns

Number of specified symbols in [0, pos)

select_impl()

template<StorageImplementation Storage = AlignedStorage>

size_t pixie::WaveletTreeIndex< Storage >::select_impl ( uint64_t symbol, size_t rank ) const

inline

Select the position of the rank-th specified symbol (1-indexed)

Parameters

symbol	The character that the query is about
rank	1-indexed rank of specified symbol to select

Returns

Symbol index, or size() if rank is out of range

size_impl()

template<StorageImplementation Storage = AlignedStorage>

size_t pixie::WaveletTreeIndex< Storage >::size_impl ( ) const

inline

Returns

Returns the number of characters in data

---

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

• include/pixie/wavelet_tree/index.h