A wavelet tree class for integer sequences. More...

#include <wt_int.hpp>

Classes
struct	node_type
	Represents a node in the wavelet tree. More...

Public Types
enum	{ lex_ordered = 1 }

typedef int_vector ::size_type	size_type

typedef int_vector ::value_type	value_type

typedef t_bitvector::difference_type	difference_type

typedef random_access_const_iterator< wt_int >	const_iterator

typedef const_iterator	iterator

typedef t_bitvector	bit_vector_type

typedef t_rank	rank_1_type

typedef t_select	select_1_type

typedef t_select_zero	select_0_type

typedef wt_tag	index_category

typedef int_alphabet_tag	alphabet_category

typedef std::pair< value_type, size_type >	point_type

typedef std::vector< point_type >	point_vec_type

typedef std::pair< size_type, point_vec_type >	r2d_res_type

Public Member Functions
	wt_int ()=default
	Default constructor.

template<typename t_it>
	wt_int (t_it begin, t_it end, std::string tmp_dir=ram_file_name(""))
	Construct the wavelet tree from a sequence defined by two interators.

	wt_int (wt_int const &wt)
	Copy constructor.

	wt_int (wt_int &&wt)
	Move constructor.

wt_int &	operator= (wt_int const &wt)
	Assignment operator.

wt_int &	operator= (wt_int &&wt)
	Assignment move operator.

size_type	size () const
	Returns the size of the original vector.

bool	empty () const
	Returns whether the wavelet tree contains no data.

value_type	operator[] (size_type i) const
	Recovers the i-th symbol of the original vector.

size_type	rank (size_type i, value_type c) const
	Calculates how many symbols c are in the prefix [0..i-1] of the supported vector.

std::pair< size_type, value_type >	inverse_select (size_type i) const
	Calculates how many occurrences of symbol wt[i] are in the prefix [0..i-1] of the original sequence.

size_type	select (size_type i, value_type c) const
	Calculates the i-th occurrence of the symbol c in the supported vector.

void	interval_symbols (size_type i, size_type j, size_type &k, std::vector< value_type > &cs, std::vector< size_type > &rank_c_i, std::vector< size_type > &rank_c_j) const
	For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c).

template<class t_ret_type = std::tuple<size_type, size_type, size_type>>
t_ret_type	lex_count (size_type i, size_type j, value_type c) const
	How many symbols are lexicographic smaller/greater than c in [i..j-1].

template<class t_ret_type = std::tuple<size_type, size_type>>
t_ret_type	lex_smaller_count (size_type i, value_type c) const
	How many symbols are lexicographic smaller than c in [0..i-1].

std::pair< size_type, std::vector< std::pair< value_type, size_type > > >	range_search_2d (size_type lb, size_type rb, value_type vlb, value_type vrb, bool report=true) const
	range_search_2d searches points in the index interval [lb..rb] and value interval [vlb..vrb].

void	_range_search_2d (size_type lb, size_type rb, value_type vlb, value_type vrb, size_type level, size_type ilb, size_type node_size, std::vector< size_type > &offsets, std::vector< size_type > &ones_before_os, size_type path, point_vec_type &point_vec, bool report, size_type &cnt_answers) const

const_iterator	begin () const
	Returns a const_iterator to the first element.

const_iterator	end () const
	Returns a const_iterator to the element after the last element.

size_type	serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
	Serializes the data structure into the given ostream.

void	load (std::istream &in)
	Loads the data structure from the given istream.

template<typename archive_t>
void	CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const

template<typename archive_t>
void	CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)

bool	operator== (wt_int const &other) const noexcept
	Equality operator.

bool	operator!= (wt_int const &other) const noexcept
	Inequality operator.

bool	is_leaf (node_type const &v) const
	Checks if the node is a leaf node.

value_type	sym (node_type const &v) const
	Returns the symbol of leaf node v.

auto	bit_vec (node_type const &v) const -> node_bv_container< t_bitvector >
	Random access container to bitvector of node v.

auto	seq (node_type const &v) const -> random_access_container< std::function< value_type(size_type)> >
	Random access container to sequence of node v.

bool	empty (node_type const &v) const
	Indicates if node v is empty.

auto	size (node_type const &v) const -> decltype(v.size)
	Return the size of node v.

node_type	root () const
	Return the root node.

std::array< node_type, 2 >	expand (node_type const &v) const
	Returns the two child nodes of an inner node.

std::array< node_type, 2 >	expand (node_type &&v) const
	Returns the two child nodes of an inner node.

std::array< range_vec_type, 2 >	expand (node_type const &v, range_vec_type const &ranges) const
	Returns for each range its left and right child ranges.

std::array< range_vec_type, 2 >	expand (node_type const &v, range_vec_type &&ranges) const
	Returns for each range its left and right child ranges.

std::array< range_type, 2 >	expand (node_type const &v, range_type const &r) const
	Returns for a range its left and right child ranges.

std::pair< uint64_t, uint64_t >	path (value_type c) const
	return the path to the leaf for a given symbol

Public Attributes
size_type const &	sigma = m_sigma
	Effective alphabet size of the wavelet tree.

bit_vector_type const &	tree = m_tree
	A concatenation of all bit vectors of the wavelet tree.

uint32_t const &	max_level = m_max_level
	Maximal level of the wavelet tree.

Protected Attributes
size_type	m_size = 0

size_type	m_sigma = 0

bit_vector_type	m_tree

rank_1_type	m_tree_rank

select_1_type	m_tree_select1

select_0_type	m_tree_select0

uint32_t	m_max_level = 0

Detailed Description

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
class sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >

A wavelet tree class for integer sequences.

Space complexity: $\Order{n\log|\Sigma|}$ bits, where is the size of the vector the wavelet tree was build for.

Template Parameters

t_bitvector	Type of the bitvector used for representing the wavelet tree.
t_rank	Type of the support structure for rank on pattern `1`.
t_select	Type of the support structure for select on pattern `1`.
t_select_zero	Type of the support structure for select on pattern `0`.

Definition at line 61 of file wt_int.hpp.

Member Typedef Documentation

◆ alphabet_category

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef int_alphabet_tag sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::alphabet_category

Definition at line 74 of file wt_int.hpp.

◆ bit_vector_type

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef t_bitvector sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::bit_vector_type

Definition at line 69 of file wt_int.hpp.

◆ const_iterator

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef random_access_const_iterator<wt_int> sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::const_iterator

Definition at line 67 of file wt_int.hpp.

◆ difference_type

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef t_bitvector::difference_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::difference_type

Definition at line 66 of file wt_int.hpp.

◆ index_category

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef wt_tag sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::index_category

Definition at line 73 of file wt_int.hpp.

◆ iterator

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef const_iterator sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::iterator

Definition at line 68 of file wt_int.hpp.

◆ point_type

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef std::pair<value_type, size_type> sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::point_type

Definition at line 80 of file wt_int.hpp.

◆ point_vec_type

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef std::vector<point_type> sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::point_vec_type

Definition at line 81 of file wt_int.hpp.

◆ r2d_res_type

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef std::pair<size_type, point_vec_type> sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::r2d_res_type

Definition at line 82 of file wt_int.hpp.

◆ rank_1_type

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef t_rank sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::rank_1_type

Definition at line 70 of file wt_int.hpp.

◆ select_0_type

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef t_select_zero sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::select_0_type

Definition at line 72 of file wt_int.hpp.

◆ select_1_type

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef t_select sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::select_1_type

Definition at line 71 of file wt_int.hpp.

◆ size_type

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef int_vector ::size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::size_type

Definition at line 64 of file wt_int.hpp.

◆ value_type

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

typedef int_vector ::value_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::value_type

Definition at line 65 of file wt_int.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

anonymous enum

Enumerator
lex_ordered

Definition at line 75 of file wt_int.hpp.

Constructor & Destructor Documentation

◆ wt_int() [1/4]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::wt_int ( )

default

Default constructor.

◆ wt_int() [2/4]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

template<typename t_it>

sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::wt_int	(	t_it	begin,
		t_it	end,
		std::string	tmp_dir = ram_file_name("") )

inline

Construct the wavelet tree from a sequence defined by two interators.

Parameters

begin	Iterator to the start of the input.
end	Iterator one past the end of the input.
tmp_dir	Temporary directory for intermediate results.

Time complexity: $\Order{n\log|\Sigma|}$ , where I.e. we need \Order{n\log n} if rac is a permutation of 0..n-1.

Definition at line 169 of file wt_int.hpp.

◆ wt_int() [3/4]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::wt_int ( wt_int< t_bitvector, t_rank, t_select, t_select_zero > const & wt )

inline

Copy constructor.

Definition at line 263 of file wt_int.hpp.

◆ wt_int() [4/4]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::wt_int ( wt_int< t_bitvector, t_rank, t_select, t_select_zero > && wt )

inline

Move constructor.

Definition at line 278 of file wt_int.hpp.

Member Function Documentation

◆ _range_search_2d()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

void sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::_range_search_2d	(	size_type	lb,
		size_type	rb,
		value_type	vlb,
		value_type	vrb,
		size_type	level,
		size_type	ilb,
		size_type	node_size,
		std::vector< size_type > &	offsets,
		std::vector< size_type > &	ones_before_os,
		size_type	path,
		point_vec_type &	point_vec,
		bool	report,
		size_type &	cnt_answers ) const

inline

Definition at line 679 of file wt_int.hpp.

◆ begin()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

const_iterator sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::begin ( ) const

inline

Returns a const_iterator to the first element.

Definition at line 780 of file wt_int.hpp.

◆ bit_vec()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

auto sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::bit_vec ( node_type const & v ) const -> node_bv_container<t_bitvector>

inline

Random access container to bitvector of node v.

Definition at line 920 of file wt_int.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

template<typename archive_t>

void sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar )

inline

Definition at line 832 of file wt_int.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

template<typename archive_t>

void sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar ) const

inline

Definition at line 820 of file wt_int.hpp.

◆ empty() [1/2]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

bool sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::empty ( ) const

inline

Returns whether the wavelet tree contains no data.

Definition at line 329 of file wt_int.hpp.

◆ empty() [2/2]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

bool sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::empty ( node_type const & v ) const

inline

Indicates if node v is empty.

Definition at line 946 of file wt_int.hpp.

◆ end()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

const_iterator sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::end ( ) const

inline

Returns a const_iterator to the element after the last element.

Definition at line 786 of file wt_int.hpp.

◆ expand() [1/5]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

std::array< node_type, 2 > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::expand ( node_type && v ) const

inline

Returns the two child nodes of an inner node.

Parameters

v	An inner node of a wavelet tree.

Returns: Return an array of nodes (left child, right child).

Precondition: !is_leaf(v)

Definition at line 979 of file wt_int.hpp.

◆ expand() [2/5]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

std::array< node_type, 2 > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::expand ( node_type const & v ) const

inline

Returns the two child nodes of an inner node.

Parameters

v	An inner node of a wavelet tree.

Returns: Return an array of nodes (left child, right child).

Precondition: !is_leaf(v)

Definition at line 968 of file wt_int.hpp.

◆ expand() [3/5]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

std::array< range_type, 2 > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::expand	(	node_type const &	v,
		range_type const &	r ) const

inline

Returns for a range its left and right child ranges.

Parameters

v	An inner node of an wavelet tree.
r	A ranges [s,e], such that [s,e] is contained in v=[v_s,v_e].

Returns: A range pair. The first element of the range pair correspond to the original range mapped to the left child of v; the second element to the range mapped to the right child of v.

Precondition: !is_leaf(v) and s>=v_s and e<=v_e

Definition at line 1054 of file wt_int.hpp.

◆ expand() [4/5]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

std::array< range_vec_type, 2 > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::expand	(	node_type const &	v,
		range_vec_type &&	ranges ) const

inline

Returns for each range its left and right child ranges.

Parameters

v	An inner node of an wavelet tree.
ranges	A vector of ranges. Each range [s,e] has to be contained in v=[v_s,v_e].

Returns: A vector a range pairs. The first element of each range pair correspond to the original range mapped to the left child of v; the second element to the range mapped to the right child of v.

Precondition: !is_leaf(v) and s>=v_s and e<=v_e

Definition at line 1024 of file wt_int.hpp.

◆ expand() [5/5]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

std::array< range_vec_type, 2 > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::expand	(	node_type const &	v,
		range_vec_type const &	ranges ) const

inline

Returns for each range its left and right child ranges.

Parameters

v	An inner node of an wavelet tree.
ranges	A vector of ranges. Each range [s,e] has to be contained in v=[v_s,v_e].

Returns: A vector a range pairs. The first element of each range pair correspond to the original range mapped to the left child of v; the second element to the range mapped to the right child of v.

Precondition: !is_leaf(v) and s>=v_s and e<=v_e

Definition at line 1008 of file wt_int.hpp.

◆ interval_symbols()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

void sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::interval_symbols	(	size_type	i,
		size_type	j,
		size_type &	k,
		std::vector< value_type > &	cs,
		std::vector< size_type > &	rank_c_i,
		std::vector< size_type > &	rank_c_j ) const

inline

For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c).

Parameters

i	The start index (inclusive) of the interval.
j	The end index (exclusive) of the interval.
k	Reference for number of different symbols in [i..j-1].
cs	Reference to a vector that will contain in cs[0..k-1] all symbols that occur in [i..j-1] in ascending order.
rank_c_i	Reference to a vector which equals rank_c_i[p] = rank(i,cs[p]), for $0 \leq p < k$ .
rank_c_j	Reference to a vector which equals rank_c_j[p] = rank(j,cs[p]), for $0 \leq p < k$ .

Time complexity: $\Order{\min{\sigma, k \log \sigma}}$

Precondition: $i \leq j \leq size()$ $cs.size() \geq \sigma$ $rank_{c_i}.size() \geq \sigma$ $rank_{c_j}.size() \geq \sigma$

Definition at line 530 of file wt_int.hpp.

◆ inverse_select()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

std::pair< size_type, value_type > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::inverse_select ( size_type i ) const

inline

Calculates how many occurrences of symbol wt[i] are in the prefix [0..i-1] of the original sequence.

Parameters

i	The index of the symbol.

Returns: Pair (rank(wt[i],i),wt[i])

Precondition

Definition at line 418 of file wt_int.hpp.

◆ is_leaf()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

bool sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::is_leaf ( node_type const & v ) const

inline

Checks if the node is a leaf node.

Definition at line 908 of file wt_int.hpp.

◆ lex_count()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

template<class t_ret_type = std::tuple<size_type, size_type, size_type>>

t_ret_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::lex_count	(	size_type	i,
		size_type	j,
		value_type	c ) const

inline

How many symbols are lexicographic smaller/greater than c in [i..j-1].

Parameters

i	Start index (inclusive) of the interval.
j	End index (exclusive) of the interval.
c	Symbol c.

Returns

A triple containing:

rank(i,c)
#symbols smaller than c in [i..j-1]
#symbols greater than c in [i..j-1]

Precondition: $i \leq j \leq size()$

Definition at line 570 of file wt_int.hpp.

◆ lex_smaller_count()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

template<class t_ret_type = std::tuple<size_type, size_type>>

t_ret_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::lex_smaller_count	(	size_type	i,
		value_type	c ) const

inline

How many symbols are lexicographic smaller than c in [0..i-1].

Parameters

i	Exclusive right bound of the range.
c	Symbol c.

Returns

A tuple containing:

rank(i,c)
#symbols smaller than c in [0..i-1]

Precondition: $i \leq size()$

Definition at line 620 of file wt_int.hpp.

◆ load()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

void sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::load ( std::istream & in )

inline

Loads the data structure from the given istream.

Definition at line 808 of file wt_int.hpp.

◆ operator!=()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

bool sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::operator!= ( wt_int< t_bitvector, t_rank, t_select, t_select_zero > const & other ) const

inlinenoexcept

Inequality operator.

Definition at line 855 of file wt_int.hpp.

◆ operator=() [1/2]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

wt_int & sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::operator= ( wt_int< t_bitvector, t_rank, t_select, t_select_zero > && wt )

inline

Assignment move operator.

Definition at line 304 of file wt_int.hpp.

◆ operator=() [2/2]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

wt_int & sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::operator= ( wt_int< t_bitvector, t_rank, t_select, t_select_zero > const & wt )

inline

Assignment operator.

Definition at line 293 of file wt_int.hpp.

◆ operator==()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

bool sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::operator== ( wt_int< t_bitvector, t_rank, t_select, t_select_zero > const & other ) const

inlinenoexcept

Equality operator.

Definition at line 847 of file wt_int.hpp.

◆ operator[]()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

value_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::operator[] ( size_type i ) const

inline

Recovers the i-th symbol of the original vector.

Parameters

i	The index of the symbol in the original vector.

Returns: The i-th symbol of the original vector.

Precondition

Definition at line 340 of file wt_int.hpp.

◆ path()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

std::pair< uint64_t, uint64_t > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::path ( value_type c ) const

inline

return the path to the leaf for a given symbol

Definition at line 1068 of file wt_int.hpp.

◆ range_search_2d()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

std::pair< size_type, std::vector< std::pair< value_type, size_type > > > sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::range_search_2d	(	size_type	lb,
		size_type	rb,
		value_type	vlb,
		value_type	vrb,
		bool	report = true ) const

inline

range_search_2d searches points in the index interval [lb..rb] and value interval [vlb..vrb].

Parameters

lb	Left bound of index interval (inclusive)
rb	Right bound of index interval (inclusive)
vlb	Left bound of value interval (inclusive)
vrb	Right bound of value interval (inclusive)
report	Should the matching points be returned?

Returns: Pair (#of found points, vector of points), the vector is empty when report = false.

Definition at line 664 of file wt_int.hpp.

◆ rank()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::rank	(	size_type	i,
		value_type	c ) const

inline

Calculates how many symbols c are in the prefix [0..i-1] of the supported vector.

Parameters

i	The exclusive index of the prefix range [0..i-1], so $i\in[0..size()]$ .
c	The symbol to count the occurrences in the prefix.

Returns: The number of occurrences of symbol c in the prefix [0..i-1] of the supported vector.

Time complexity: $\Order{\log |\Sigma|}$

Precondition: $i \leq size()$

Definition at line 379 of file wt_int.hpp.

◆ root()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

node_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::root ( ) const

inline

Return the root node.

Definition at line 958 of file wt_int.hpp.

◆ select()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::select	(	size_type	i,
		value_type	c ) const

inline

Calculates the i-th occurrence of the symbol c in the supported vector.

Parameters

i	The i-th occurrence.
c	The symbol c.

Time complexity: $\Order{\log |\Sigma|}$

Precondition: $1 \leq i \leq rank(size(), c)$

Definition at line 456 of file wt_int.hpp.

◆ seq()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

auto sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::seq ( node_type const & v ) const -> random_access_container<std::function<value_type(size_type)>>

inline

Random access container to sequence of node v.

Definition at line 926 of file wt_int.hpp.

◆ serialize()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::serialize	(	std::ostream &	out,
		structure_tree_node *	v = nullptr,
		std::string	name = "" ) const

inline

Serializes the data structure into the given ostream.

Definition at line 792 of file wt_int.hpp.

◆ size() [1/2]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::size ( ) const

inline

Returns the size of the original vector.

Definition at line 323 of file wt_int.hpp.

◆ size() [2/2]

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

auto sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::size ( node_type const & v ) const -> decltype(v.size)

inline

Return the size of node v.

Definition at line 952 of file wt_int.hpp.

◆ sym()

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

value_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::sym ( node_type const & v ) const

inline

Returns the symbol of leaf node v.

Definition at line 914 of file wt_int.hpp.

Member Data Documentation

◆ m_max_level

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

uint32_t sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_max_level = 0

protected

Definition at line 91 of file wt_int.hpp.

◆ m_sigma

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_sigma = 0

protected

Definition at line 86 of file wt_int.hpp.

◆ m_size

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_size = 0

protected

Definition at line 85 of file wt_int.hpp.

◆ m_tree

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

bit_vector_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_tree

protected

Definition at line 87 of file wt_int.hpp.

◆ m_tree_rank

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

rank_1_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_tree_rank

protected

Definition at line 88 of file wt_int.hpp.

◆ m_tree_select0

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

select_0_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_tree_select0

protected

Definition at line 90 of file wt_int.hpp.

◆ m_tree_select1

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

select_1_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::m_tree_select1

protected

Definition at line 89 of file wt_int.hpp.

◆ max_level

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

uint32_t const& sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::max_level = m_max_level

Maximal level of the wavelet tree.

Definition at line 154 of file wt_int.hpp.

◆ sigma

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

size_type const& sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::sigma = m_sigma

Effective alphabet size of the wavelet tree.

Definition at line 152 of file wt_int.hpp.

◆ tree

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>

bit_vector_type const& sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::tree = m_tree

A concatenation of all bit vectors of the wavelet tree.

Definition at line 153 of file wt_int.hpp.

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

/builddir/build/BUILD/sdsl-lite-3.0.3-build/sdsl-lite-3.0.3/include/sdsl/wt_int.hpp

Classes

Public Types

Public Member Functions

Public Attributes

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ alphabet_category

◆ bit_vector_type

◆ const_iterator

◆ difference_type

◆ index_category

◆ iterator

◆ point_type

◆ point_vec_type

◆ r2d_res_type

◆ rank_1_type

◆ select_0_type

◆ select_1_type

◆ size_type

◆ value_type

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ wt_int() [1/4]

◆ wt_int() [2/4]

◆ wt_int() [3/4]

◆ wt_int() [4/4]

Member Function Documentation

◆ _range_search_2d()

◆ begin()

◆ bit_vec()

◆ CEREAL_LOAD_FUNCTION_NAME()

◆ CEREAL_SAVE_FUNCTION_NAME()

◆ empty() [1/2]

◆ empty() [2/2]

◆ end()

◆ expand() [1/5]

◆ expand() [2/5]

◆ expand() [3/5]

◆ expand() [4/5]

◆ expand() [5/5]

◆ interval_symbols()

◆ inverse_select()

◆ is_leaf()

◆ lex_count()

◆ lex_smaller_count()

◆ load()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]()

◆ path()

◆ range_search_2d()

◆ rank()

◆ root()

◆ select()

◆ seq()

◆ serialize()

◆ size() [1/2]

◆ size() [2/2]

◆ sym()

Member Data Documentation

◆ m_max_level

◆ m_sigma

◆ m_size

◆ m_tree

◆ m_tree_rank

◆ m_tree_select0

◆ m_tree_select1

◆ max_level

◆ sigma

◆ tree