Storage-backed wavelet tree over an unsigned symbol type. More...

#include <index.h>

Inheritance diagram for pixie::WaveletTreeIndex< Symbol, Storage >:

Public Types
using	symbol_type = Symbol

Public Member Functions
	WaveletTreeIndex (std::size_t alphabet_size, std::span< const Symbol > data, const WaveletTreeBuildType build_type=WaveletTreeBuildType::Standard)
	Construct from a contiguous sequence of typed symbols.

template<class ForEachSymbol> requires (std::same_as<Storage, AlignedStorage>)
	WaveletTreeIndex (std::size_t alphabet_size, std::span< const std::size_t > symbol_counts, ForEachSymbol &&for_each_symbol, const WaveletTreeBuildType build_type=WaveletTreeBuildType::Standard)
	Construct from counts and one streamed pass over the symbols.

size_t	rank_impl (Symbol symbol, size_t pos) const
	Rank of specified symbol up to position pos (exclusive)

size_t	select_impl (Symbol symbol, size_t rank) const
	Select the position of the rank-th specified symbol (1-indexed)

std::vector< Symbol >	get_segment_impl (size_t begin, size_t end) const
	Accumulates the original data segment.

size_t	size_impl () const

void	serialize_impl (BinaryWriter &writer) const
	Write a versioned canonical little-endian wavelet-tree artifact.

Public Member Functions inherited from pixie::WaveletTreeBase< WaveletTreeIndex< Symbol, AlignedStorage >, Symbol >
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)`.

Public Member Functions inherited from pixie::SerializationBase< WaveletTreeIndex< Symbol, AlignedStorage > >
void	serialize (BinaryWriter &writer) const
	Serialize this value through its concrete implementation.

Static Public Member Functions
static WaveletTreeIndex	deserialize_impl (BinaryReader &reader, DeserializationValidation validation=DeserializationValidation::kQuick)
	Restore one checked wavelet-tree artifact.

Static Public Member Functions inherited from pixie::SerializationBase< WaveletTreeIndex< Symbol, AlignedStorage > >
static WaveletTreeIndex< Symbol, AlignedStorage >	deserialize (BinaryReader &reader, Context &&... context)
	Restore exactly `Derived` and advance `reader` on success.

static WaveletTreeIndex< Symbol, AlignedStorage >	deserialize (std::span< const std::byte > &data, Context &&... context)
	Restore exactly `Derived` and advance a mutable byte span.

Detailed Description

template<WaveletTreeSymbol Symbol, StorageImplementation Storage = AlignedStorage>
class pixie::WaveletTreeIndex< Symbol, Storage >

Storage-backed wavelet tree over an unsigned symbol type.

Template Parameters

Symbol	Unsigned symbol type. Its value range must cover the dense alphabet `[0, alphabet_size)`.
Storage	Owning aligned storage or a non-owning read-only view.

Constructor & Destructor Documentation

◆ WaveletTreeIndex() [1/2]

template<WaveletTreeSymbol Symbol, StorageImplementation Storage = AlignedStorage>

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

inline

Construct from a contiguous sequence of typed symbols.

Parameters

alphabet_size	Dense alphabet size; every symbol must be smaller.
data	Input symbols retained only for the duration of construction.
build_type	Standard or Huffman-shaped construction.

Exceptions

std::invalid_argument if the alphabet or a symbol is invalid.

◆ WaveletTreeIndex() [2/2]

template<WaveletTreeSymbol Symbol, StorageImplementation Storage = AlignedStorage>

template<class ForEachSymbol>
requires (std::same_as<Storage, AlignedStorage>)

pixie::WaveletTreeIndex< Symbol, Storage >::WaveletTreeIndex	(	std::size_t	alphabet_size,
		std::span< const std::size_t >	symbol_counts,
		ForEachSymbol &&	for_each_symbol,
		const WaveletTreeBuildType	build_type = WaveletTreeBuildType::Standard )

inline

Construct from counts and one streamed pass over the symbols.

for_each_symbol is invoked exactly once with a consumer that accepts one Symbol. Emitted symbols must exactly match symbol_counts; this permits callers to scan a replayable source once for counts and once for construction without materializing the sequence.

Parameters

alphabet_size	Dense alphabet size.
symbol_counts	Count for every symbol in alphabet order.
for_each_symbol	Callable accepting the construction consumer.
build_type	Standard or Huffman-shaped construction.

Exceptions

std::invalid_argument for invalid or inconsistent input.

Member Function Documentation

◆ deserialize_impl()

template<WaveletTreeSymbol Symbol, StorageImplementation Storage = AlignedStorage>

static WaveletTreeIndex pixie::WaveletTreeIndex< Symbol, Storage >::deserialize_impl	(	BinaryReader &	reader,
		DeserializationValidation	validation = DeserializationValidation::kQuick )

inlinestatic

Restore one checked wavelet-tree artifact.

The aligned-storage specialization copies all restored metadata. The read-only specialization retains views into the reader's backing bytes, which must remain alive, immutable, and aligned for 64-bit access. On success reader advances past exactly one framed artifact; on failure it is unchanged. validation selects quick structural checks or exact bitvector-derived metadata validation.

Parameters

reader	Input cursor, advanced only after successful validation.
validation	Quick structural or full bitvector-derived validation.

Exceptions

std::invalid_argument	for malformed, truncated, incompatible, or structurally inconsistent metadata.
std::length_error	when an encoded count is not representable.

◆ get_segment_impl()

template<WaveletTreeSymbol Symbol, StorageImplementation Storage = AlignedStorage>

std::vector< Symbol > pixie::WaveletTreeIndex< Symbol, 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

Queries packed bit vectors and rank/select metadata directly through the node storage. A deserialized view does not consult or retain its BinaryReader. The current implementation materializes the requested output and an equally sized temporary buffer, for peak auxiliary and result storage of two Symbol values per returned symbol.

◆ rank_impl()

template<WaveletTreeSymbol Symbol, StorageImplementation Storage = AlignedStorage>

size_t pixie::WaveletTreeIndex< Symbol, Storage >::rank_impl	(	Symbol	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<WaveletTreeSymbol Symbol, StorageImplementation Storage = AlignedStorage>

size_t pixie::WaveletTreeIndex< Symbol, Storage >::select_impl	(	Symbol	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

◆ serialize_impl()

template<WaveletTreeSymbol Symbol, StorageImplementation Storage = AlignedStorage>

void pixie::WaveletTreeIndex< Symbol, Storage >::serialize_impl ( BinaryWriter & writer ) const

inline

Write a versioned canonical little-endian wavelet-tree artifact.

Exceptions

std::invalid_argument if the artifact would not begin at an eight-byte-aligned writer offset required by zero-copy deserialization.

◆ size_impl()

template<WaveletTreeSymbol Symbol, StorageImplementation Storage = AlignedStorage>

size_t pixie::WaveletTreeIndex< Symbol, 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

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ WaveletTreeIndex() [1/2]

◆ WaveletTreeIndex() [2/2]

Member Function Documentation

◆ deserialize_impl()

◆ get_segment_impl()

◆ rank_impl()

◆ select_impl()

◆ serialize_impl()

◆ size_impl()