A dynamic wavelet matrix supporting insertion, deletion, and 2D range reporting on rank coordinates. More...

#include <dynamic_wavelet_matrix_for_range_search.hpp>

Classes
class	XRankIterator
	Random-access iterator traversing elements in x-rank order. More...

class	YRankIterator
	Random-access iterator traversing elements in y-rank order. More...

Public Member Functions
	DynamicWaveletMatrixForRangeSearch ()
	Default constructor. Initializes an empty structure.

Converters
std::vector< bool >	get_bit_sequence (uint64_t h, uint64_t node_id) const
	Return the bit sequence stored in a node as a vector.

std::vector< uint64_t >	to_local_rank_elements_in_y_order (uint64_t h, uint64_t node_id) const
	Extract rank elements in y-order for the subtree rooted at (h, node_id).

std::vector< uint64_t >	to_rank_elements_in_y_order () const
	Extract all rank elements in y-order for the entire structure.

std::vector< uint64_t >	to_rank_elements_in_x_order () const
	Extract all y-ranks in x-order for the entire structure.

std::string	to_string () const

Print and verification functions
bool	verify () const
	Verify structural consistency of the wavelet tree.

void	print_tree () const
	Print a textual representation of the wavelet tree to standard output (for debugging).

Iterators
XRankIterator	x_rank_begin () const
	Return an iterator to the first element in x-rank order.

XRankIterator	x_rank_end () const
	Return an iterator past the last element in x-rank order.

YRankIterator	y_rank_begin () const
	Return an iterator to the first element in y-rank order.

YRankIterator	y_rank_end () const
	Return an iterator past the last element in y-rank order.

Lightweight Queries
int64_t	height () const
	Return the height of the wavelet tree.

uint64_t	size () const
	Return the number of stored elements.

Main Queries
template<typename APPENDABLE_VECTOR >
uint64_t	range_report (uint64_t x_min, uint64_t x_max, uint64_t y_min, uint64_t y_max, APPENDABLE_VECTOR &out) const
	Report all x-ranks of elements whose coordinates lie in the given rectangle.

uint64_t	access_x_rank (uint64_t y_rank) const
	Return the x-rank of the element at global y-rank `y_rank`.

uint64_t	find_leaf_index (uint64_t x_rank) const
	Return the leaf node identifier for global x-rank `x_rank`.

uint64_t	access_y_rank (uint64_t x_rank) const
	Return the y-rank of the element at global x-rank `x_rank`.

Update Operations
void	swap (DynamicWaveletMatrixForRangeSearch &item)
	Swap the contents of this structure with `item`.

void	clear ()
	Clear all bit sequences, length sequences, and reset the structure to empty.

void	rebuild (const std::vector< uint64_t > &rank_elements, int message_paragraph=stool::Message::NO_MESSAGE)

void	insert (uint64_t x_rank, uint64_t y_rank)
	Insert an element at global coordinates (x_rank, y_rank).

void	erase_y_rank (uint64_t y_rank)
	Remove the element at global y-rank `y_rank`.

Load, save, and builder functions
uint64_t	size_in_bytes (bool only_extra_bytes=false) const
	Return the serialized size of this structure in bytes.

std::vector< std::string >	get_memory_usage_info (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Return human-readable memory usage statistics for this structure.

static DynamicWaveletMatrixForRangeSearch	build (const std::vector< uint64_t > &rank_elements, int message_paragraph=stool::Message::NO_MESSAGE)
	Build the entire structure from rank elements ordered by y-rank.

static void	store_to_file (DynamicWaveletMatrixForRangeSearch &item, std::ofstream &os)
	Serialize the structure to a binary output stream.

static void	store_to_bytes (DynamicWaveletMatrixForRangeSearch &item, std::vector< uint8_t > &output, uint64_t &pos)
	Serialize the structure to a byte buffer.

static DynamicWaveletMatrixForRangeSearch	load_from_file (std::ifstream &ifs)
	Deserialize a structure from a binary input stream.

static DynamicWaveletMatrixForRangeSearch	load_from_bytes (const std::vector< uint8_t > &data, uint64_t &pos)
	Deserialize a structure from a byte buffer.

Detailed Description

A dynamic wavelet matrix supporting insertion, deletion, and 2D range reporting on rank coordinates.

The structure stores n elements as pairs of x-rank and y-rank coordinates. Elements are ordered primarily by y-rank; x-rank is the associated value at each y-rank position.

Member Function Documentation

◆ access_x_rank()

uint64_t stool::bptree::DynamicWaveletMatrixForRangeSearch::access_x_rank ( uint64_t y_rank ) const

inline

Return the x-rank of the element at global y-rank y_rank.

Parameters

y_rank Global y-rank position (0-based).

Returns: The corresponding x-rank.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ access_y_rank()

uint64_t stool::bptree::DynamicWaveletMatrixForRangeSearch::access_y_rank ( uint64_t x_rank ) const

inline

Return the y-rank of the element at global x-rank x_rank.

Parameters

x_rank Global x-rank position (0-based).

Returns: The corresponding y-rank.

Warning: O(H log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ build()

static DynamicWaveletMatrixForRangeSearch stool::bptree::DynamicWaveletMatrixForRangeSearch::build	(	const std::vector< uint64_t > &	rank_elements,
		int	message_paragraph = `stool::Message::NO_MESSAGE`
	)

inlinestatic

Build the entire structure from rank elements ordered by y-rank.

Parameters

rank_elements	Vector of x-ranks in y-rank order.
message_paragraph	Indentation level for progress messages (use stool::Message::NO_MESSAGE to suppress).

Warning: O(n log^2 n) time

Here is the call graph for this function:

◆ erase_y_rank()

void stool::bptree::DynamicWaveletMatrixForRangeSearch::erase_y_rank ( uint64_t y_rank )

inline

Remove the element at global y-rank y_rank.

After removal, the structure may be rebuilt if the size falls below half of the root node's upper capacity threshold.

Parameters

y_rank The y-rank of the element to remove.

Exceptions

std::runtime_error if the structure is empty.

Warning: amortized O(H log n) time

Here is the call graph for this function:

◆ find_leaf_index()

uint64_t stool::bptree::DynamicWaveletMatrixForRangeSearch::find_leaf_index ( uint64_t x_rank ) const

inline

Return the leaf node identifier for global x-rank x_rank.

Parameters

x_rank Global x-rank position (0-based).

Returns: Node identifier at the leaf level.

Exceptions

std::runtime_error if x_rank is out of range.

Warning: O(H log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_bit_sequence()

std::vector< bool > stool::bptree::DynamicWaveletMatrixForRangeSearch::get_bit_sequence	(	uint64_t	h,
		uint64_t	node_id
	)		const

inline

Return the bit sequence stored in a node as a vector.

Parameters

h	Level in the wavelet tree.
node_id	Node identifier at level `h`.

Returns: Copy of the node's bits in y-rank order.

Here is the caller graph for this function:

◆ get_memory_usage_info()

std::vector< std::string > stool::bptree::DynamicWaveletMatrixForRangeSearch::get_memory_usage_info ( int message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Return human-readable memory usage statistics for this structure.

Parameters

message_paragraph Indentation level for output lines (default: stool::Message::SHOW_MESSAGE).

Returns: Vector of formatted strings describing total and per-level memory usage.

Here is the call graph for this function:

◆ height()

int64_t stool::bptree::DynamicWaveletMatrixForRangeSearch::height ( ) const

inline

Return the height of the wavelet tree.

Returns: Number of levels in bits_seq (0 if empty).

Warning: O(1) time

Here is the caller graph for this function:

◆ insert()

void stool::bptree::DynamicWaveletMatrixForRangeSearch::insert	(	uint64_t	x_rank,
		uint64_t	y_rank
	)

inline

Insert an element at global coordinates (x_rank, y_rank).

After insertion, the structure may be partially or fully rebuilt if capacity or balance thresholds are exceeded.

Parameters

x_rank	The x-rank of the element to insert.
y_rank	The y-rank position at which to insert.

Warning: amortized O(H log n) time

Here is the call graph for this function:

◆ load_from_bytes()

static DynamicWaveletMatrixForRangeSearch stool::bptree::DynamicWaveletMatrixForRangeSearch::load_from_bytes	(	const std::vector< uint8_t > &	data,
		uint64_t &	pos
	)

inlinestatic

Deserialize a structure from a byte buffer.

Parameters

data	Byte buffer containing serialized data.
pos	Read position in `data`; advanced on return.

Returns: Reconstructed DynamicWaveletMatrixForRangeSearch instance.

Here is the call graph for this function:

◆ load_from_file()

static DynamicWaveletMatrixForRangeSearch stool::bptree::DynamicWaveletMatrixForRangeSearch::load_from_file ( std::ifstream & ifs )

inlinestatic

Deserialize a structure from a binary input stream.

Parameters

ifs	Input file stream positioned at the serialized data.

Returns: Reconstructed DynamicWaveletMatrixForRangeSearch instance.

Here is the call graph for this function:

◆ range_report()

template<typename APPENDABLE_VECTOR >

uint64_t stool::bptree::DynamicWaveletMatrixForRangeSearch::range_report	(	uint64_t	x_min,
		uint64_t	x_max,
		uint64_t	y_min,
		uint64_t	y_max,
		APPENDABLE_VECTOR &	out
	)		const

inline

Report all x-ranks of elements whose coordinates lie in the given rectangle.

Template Parameters

APPENDABLE_VECTOR Vector type supporting push_back (e.g. std::vector).

Parameters

x_min	Minimum x-rank (inclusive).
x_max	Maximum x-rank (inclusive).
y_min	Minimum y-rank (inclusive).
y_max	Maximum y-rank (inclusive).
out	Output vector to which matching x-ranks are appended.

Returns: Number of m elements reported.

Warning: O((m + 1) log^2 n) time

Here is the call graph for this function:

◆ size()

uint64_t stool::bptree::DynamicWaveletMatrixForRangeSearch::size ( ) const

inline

Return the number of stored elements.

Returns: Size of the root-level bit sequence, or 0 if empty.

Warning: O(1) time

Here is the call graph for this function:

Here is the caller graph for this function:

◆ size_in_bytes()

uint64_t stool::bptree::DynamicWaveletMatrixForRangeSearch::size_in_bytes ( bool only_extra_bytes = false ) const

inline

Return the serialized size of this structure in bytes.

Parameters

only_extra_bytes If true, count only dynamically allocated extra bytes in sub-structures.

Returns: Total byte size when serialized.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ store_to_bytes()

static void stool::bptree::DynamicWaveletMatrixForRangeSearch::store_to_bytes	(	DynamicWaveletMatrixForRangeSearch &	item,
		std::vector< uint8_t > &	output,
		uint64_t &	pos
	)

inlinestatic

Serialize the structure to a byte buffer.

Parameters

item	Structure to serialize.
output	Byte buffer; resized if necessary.
pos	Read/write position in `output`; advanced on return.

Here is the call graph for this function:

◆ store_to_file()

static void stool::bptree::DynamicWaveletMatrixForRangeSearch::store_to_file	(	DynamicWaveletMatrixForRangeSearch &	item,
		std::ofstream &	os
	)

inlinestatic

Serialize the structure to a binary output stream.

Parameters

item	Structure to serialize.
os	Output file stream.

Here is the call graph for this function:

◆ swap()

void stool::bptree::DynamicWaveletMatrixForRangeSearch::swap ( DynamicWaveletMatrixForRangeSearch & item )

inline

Swap the contents of this structure with item.

Parameters

item	Another DynamicWaveletMatrixForRangeSearch instance.

◆ to_local_rank_elements_in_y_order()

std::vector< uint64_t > stool::bptree::DynamicWaveletMatrixForRangeSearch::to_local_rank_elements_in_y_order	(	uint64_t	h,
		uint64_t	node_id
	)		const

inline

Extract rank elements in y-order for the subtree rooted at (h, node_id).

Parameters

h	Level of the subtree root.
node_id	Node identifier at level `h`.

Returns: Vector of x-ranks in y-rank order within the subtree.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ to_rank_elements_in_x_order()

std::vector< uint64_t > stool::bptree::DynamicWaveletMatrixForRangeSearch::to_rank_elements_in_x_order ( ) const

inline

Extract all y-ranks in x-order for the entire structure.

Returns: Vector where r[i] is the y-rank of the element with x-rank i.

Here is the call graph for this function:

◆ to_rank_elements_in_y_order()

std::vector< uint64_t > stool::bptree::DynamicWaveletMatrixForRangeSearch::to_rank_elements_in_y_order ( ) const

inline

Extract all rank elements in y-order for the entire structure.

Returns: Vector of x-ranks in global y-rank order, or an empty vector if empty.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ verify()

bool stool::bptree::DynamicWaveletMatrixForRangeSearch::verify ( ) const

inline

Verify structural consistency of the wavelet tree.

Checks that zero/one counts in each internal node match the sizes of its left and right children, and that leaf nodes contain at most one bit.

Returns: True if the structure is valid.

Exceptions

std::runtime_error if an inconsistency is detected.

Here is the call graph for this function:

Here is the caller graph for this function:

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

include/range_search/dynamic_wavelet_matrix_for_range_search.hpp

Classes

Public Member Functions

Lightweight Queries

Main Queries

Update Operations

Load, save, and builder functions

Detailed Description

Member Function Documentation

◆ access_x_rank()

◆ access_y_rank()

◆ build()

◆ erase_y_rank()

◆ find_leaf_index()

◆ get_bit_sequence()

◆ get_memory_usage_info()

◆ height()

◆ insert()

◆ load_from_bytes()

◆ load_from_file()

◆ range_report()

◆ size()

◆ size_in_bytes()

◆ store_to_bytes()

◆ store_to_file()

◆ swap()

◆ to_local_rank_elements_in_y_order()

◆ to_rank_elements_in_x_order()

◆ to_rank_elements_in_y_order()

◆ verify()