stool::bptree::DynamicWaveletTree Class Reference

A dynamic data structure supporting rank and select queries on a string T[0..n-1] over alphabet U[0..σ-1]. More...

#include <dynamic_wavelet_tree.hpp>

Public Member Functions
Constructors and Destructor
	DynamicWaveletTree ()
	Default constructor with |T| = 0 and |U| = 0.
	DynamicWaveletTree (const std::vector< uint8_t > &_alphabet)
	Default constructor with |T| = 0 and U = _alphabet.
	~DynamicWaveletTree ()
	Destroy the Dynamic Wavelet Tree object.
	DynamicWaveletTree (DynamicWaveletTree &&) noexcept=default
	Default move constructor.
Operators
DynamicWaveletTree &	operator= (const DynamicWaveletTree &)=delete
	Deleted copy assignment operator.
DynamicWaveletTree &	operator= (DynamicWaveletTree &&) noexcept=default
	Default move assignment operator.
uint8_t	operator[] (uint64_t i) const
	The alias for at query.
Lightweight functions for accessing to properties of this class
uint64_t	size () const
	Return |T|.
uint64_t	get_alphabet_size () const
	Return alphabet size |U|.
bool	has_empty_alphabet () const
	Check if the alphabet U is empty.
uint64_t	get_smallest_character_in_alphabet () const
	Return the smallest character in the alphabet U.
int64_t	get_lexicographic_order (uint8_t c) const
	Return the lexicographic order of a given character c in the alphabet U if it exists, otherwise returns -1.
uint64_t	height () const
	Return the height of the wavelet tree.
uint64_t	size_in_bytes (bool only_dynamic_memory=false) const
	Returns the total memory usage in bytes.
Main queries
uint64_t	at (uint64_t i) const
	Return T[i].
int64_t	one_based_rank (uint64_t i, uint64_t c) const
	Counts the number of occurrences of a character c in T[0..i-1].
int64_t	select (uint64_t i, uint64_t c) const
	Returns the position p of the (i+1)-th 1 in B if such a position exists, otherwise returns -1.
uint64_t	get_lexicographic_order_by_position (uint64_t i) const
	Return the lexicographic order of T[i] in the alphabet U.
uint64_t	count_c (uint8_t c) const
	Return the number of occurrences of the character c in T.
Conversion functions
std::string	to_string () const
	Return T as a string.
std::vector< uint8_t >	to_u8_vector () const
	Return T as a vector of uint8_t.
std::vector< uint8_t >	to_alphabet_vector () const
	Return the alphabet U.
Update operations
void	swap (DynamicWaveletTree &item)
	Swap operation.
void	set_alphabet (const std::vector< uint8_t > &_alphabet)
	Initialize this instance with |T| = 0 and U = _alphabet.
void	clear ()
	Clear the elements in T.
void	push_back (uint8_t c)
	Adds a character c to the end of T.
void	push_many (const std::vector< uint8_t > &str)
	Add a given sequence Q[0..k-1] to the end of T[0..n-1] (i.e., T = T[0..n-1]Q[0..k-1])
void	insert (uint64_t i, uint8_t c)
	Insert a character c into T as T[i].
void	remove (uint64_t i)
	Remove the character at the position i from T.
Print and verification functions
std::vector< std::string >	get_memory_usage_info (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Return the memory usage information of this data structure as a vector of strings.
void	print_statistics (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Print the statistics of this data structure.
void	print_memory_usage (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Print the memory usage information of this data structure.
void	print_content (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Print the string T.
void	print_info () const
	Print the statistics of this data structure.

Load, save, and builder functions
static DynamicWaveletTree	build (const std::vector< uint8_t > &_text, const std::vector< uint8_t > &_alphabet)
	Build a new DynamicWaveletTree from a given sequence _text and alphabet _alphabet.
static DynamicWaveletTree	load_from_file (std::ifstream &ifs)
	Returns the DynamicWaveletTree instance loaded from a file stream ifs.
static void	store_to_file (DynamicWaveletTree &item, std::ofstream &os)
	Save the given instance item to a file stream os.

Detailed Description

A dynamic data structure supporting rank and select queries on a string T[0..n-1] over alphabet U[0..σ-1].

Member Function Documentation

at()

uint64_t stool::bptree::DynamicWaveletTree::at ( uint64_t  i ) const

inline

Return T[i].

Note

O(log σ log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

count_c()

uint64_t stool::bptree::DynamicWaveletTree::count_c ( uint8_t  c ) const

inline

Return the number of occurrences of the character c in T.

Note

O(1) time

Here is the call graph for this function:

get_lexicographic_order_by_position()

uint64_t stool::bptree::DynamicWaveletTree::get_lexicographic_order_by_position ( uint64_t  i ) const

inline

Return the lexicographic order of T[i] in the alphabet U.

Note

O(log σ log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

get_memory_usage_info()

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

inline

Return the memory usage information of this data structure as a vector of strings.

Parameters

message_paragraph

The paragraph depth of message logs (-1 for no output)

Here is the call graph for this function:

Here is the caller graph for this function:

insert()

void stool::bptree::DynamicWaveletTree::insert ( uint64_t  i, uint8_t  c  )

inline

Insert a character c into T as T[i].

Note

O(log σ log n) time

Here is the call graph for this function:

one_based_rank()

int64_t stool::bptree::DynamicWaveletTree::one_based_rank ( uint64_t  i, uint64_t  c  ) const

inline

Counts the number of occurrences of a character c in T[0..i-1].

Note

O(log σ log n) time

Here is the call graph for this function:

print_content()

void stool::bptree::DynamicWaveletTree::print_content ( int  message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Print the string T.

Parameters

message_paragraph

The paragraph depth of message logs

Here is the call graph for this function:

print_memory_usage()

void stool::bptree::DynamicWaveletTree::print_memory_usage ( int  message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Print the memory usage information of this data structure.

Parameters

message_paragraph

The paragraph depth of message logs

Here is the call graph for this function:

print_statistics()

void stool::bptree::DynamicWaveletTree::print_statistics ( int  message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Print the statistics of this data structure.

Parameters

message_paragraph

The paragraph depth of message logs

Here is the call graph for this function:

push_back()

void stool::bptree::DynamicWaveletTree::push_back ( uint8_t  c )

inline

Adds a character c to the end of T.

Note

O(log σ log n) time

Here is the call graph for this function:

Here is the caller graph for this function:

push_many()

void stool::bptree::DynamicWaveletTree::push_many ( const std::vector< uint8_t > &  str )

inline

Add a given sequence Q[0..k-1] to the end of T[0..n-1] (i.e., T = T[0..n-1]Q[0..k-1])

Note

O(|Q| log σ log n) time

Here is the call graph for this function:

remove()

void stool::bptree::DynamicWaveletTree::remove ( uint64_t  i )

inline

Remove the character at the position i from T.

Note

O(log σ log n) time

Here is the call graph for this function:

select()

int64_t stool::bptree::DynamicWaveletTree::select ( uint64_t  i, uint64_t  c  ) const

inline

Returns the position p of the (i+1)-th 1 in B if such a position exists, otherwise returns -1.

Note

O(log σ log n) time

Here is the call graph for this function:

size_in_bytes()

uint64_t stool::bptree::DynamicWaveletTree::size_in_bytes ( bool  only_dynamic_memory = false ) const

inline

Returns the total memory usage in bytes.

Parameters

only_dynamic_memory

If true, only the size of the dynamic memory is returned

Here is the caller graph for this function:

---

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

• include/dynamic_wavelet_tree.hpp