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

#include <wm_int.hpp>

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

Public Types
enum	{ lex_ordered = 0 }

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< wm_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
	wm_int ()=default
	Default constructor.

template<typename t_it>
	wm_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.

	wm_int (wm_int const &wt)
	Copy constructor.

	wm_int (wm_int &&wt)
	Move copy constructor.

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

wm_int &	operator= (wm_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.

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 (node_type v, range_type r, value_type vlb, value_type vrb, size_type ilb, std::vector< size_type > &is, std::vector< size_type > &rank_off, 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
	Serialise (save) via cereal.

template<typename archive_t>
void	CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
	Load via cereal.

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

bool	operator!= (wm_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
	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

int_vector< 64 >	m_zero_cnt

int_vector< 64 >	m_rank_level

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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >

A wavelet tree class for integer sequences.

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`.

This wavelet tree variant does not store the two children of a node v aligned with v; it is also known as wavelet matrix.

References: [1] F. Claude, G. Navarro: ,,The Wavelet Matrix'', Proceedings of SPIRE 2012.

Definition at line 63 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::alphabet_category

Definition at line 76 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::bit_vector_type

Definition at line 71 of file wm_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<wm_int> sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::const_iterator

Definition at line 69 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::difference_type

Definition at line 68 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::index_category

Definition at line 75 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::iterator

Definition at line 70 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::point_type

Definition at line 82 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::point_vec_type

Definition at line 83 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::r2d_res_type

Definition at line 84 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::rank_1_type

Definition at line 72 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::select_0_type

Definition at line 74 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::select_1_type

Definition at line 73 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::size_type

Definition at line 66 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::value_type

Definition at line 67 of file wm_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 77 of file wm_int.hpp.

Constructor & Destructor Documentation

◆ wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::wm_int ( )

default

Default constructor.

◆ wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::wm_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 117 of file wm_int.hpp.

◆ wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::wm_int ( wm_int< t_bitvector, t_rank, t_select, t_select_zero > const & wt )

inline

Copy constructor.

Definition at line 203 of file wm_int.hpp.

◆ wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::wm_int ( wm_int< t_bitvector, t_rank, t_select, t_select_zero > && wt )

inline

Move copy constructor.

Definition at line 220 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::_range_search_2d	(	node_type	v,
		range_type	r,
		value_type	vlb,
		value_type	vrb,
		size_type	ilb,
		std::vector< size_type > &	is,
		std::vector< size_type > &	rank_off,
		point_vec_type &	point_vec,
		bool	report,
		size_type &	cnt_answers ) const

inline

Definition at line 473 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::begin ( ) const

inline

Returns a const_iterator to the first element.

Definition at line 553 of file wm_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::wm_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 704 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar )

inline

Load via cereal.

Definition at line 613 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar ) const

inline

Serialise (save) via cereal.

Definition at line 598 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::empty ( ) const

inline

Returns whether the wavelet tree contains no data.

Definition at line 285 of file wm_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::wm_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 730 of file wm_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::wm_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 559 of file wm_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::wm_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 a pair of nodes (left child, right child).

Precondition: !is_leaf(v)

Definition at line 763 of file wm_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::wm_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 a pair of nodes (left child, right child).

Precondition: !is_leaf(v)

Definition at line 752 of file wm_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::wm_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 839 of file wm_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::wm_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 809 of file wm_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::wm_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 793 of file wm_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::wm_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 364 of file wm_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::wm_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 692 of file wm_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::wm_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 583 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::operator!= ( wm_int< t_bitvector, t_rank, t_select, t_select_zero > const & other ) const

inlinenoexcept

Inequality operator.

Definition at line 639 of file wm_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>

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

inline

Assignment move operator.

Definition at line 258 of file wm_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>

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

inline

Assignment operator.

Definition at line 237 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::operator== ( wm_int< t_bitvector, t_rank, t_select, t_select_zero > const & other ) const

inlinenoexcept

Equality operator.

Definition at line 630 of file wm_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::wm_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 296 of file wm_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::wm_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 853 of file wm_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::wm_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 455 of file wm_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::wm_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 328 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::root ( ) const

inline

Return the root node.

Definition at line 742 of file wm_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::wm_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 399 of file wm_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::wm_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 710 of file wm_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::wm_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 565 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::size ( ) const

inline

Returns the size of the original vector.

Definition at line 279 of file wm_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::wm_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 736 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::sym ( node_type const & v ) const

inline

Symbol of leaf node v.

Definition at line 698 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::m_max_level = 0

protected

Definition at line 95 of file wm_int.hpp.

◆ m_rank_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>

int_vector<64> sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::m_rank_level

protected

Definition at line 97 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::m_sigma = 0

protected

Definition at line 90 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::m_size = 0

protected

Definition at line 89 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::m_tree

protected

Definition at line 91 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::m_tree_rank

protected

Definition at line 92 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::m_tree_select0

protected

Definition at line 94 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::m_tree_select1

protected

Definition at line 93 of file wm_int.hpp.

◆ m_zero_cnt

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>

int_vector<64> sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::m_zero_cnt

protected

Definition at line 96 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::max_level = m_max_level

Maximal level of the wavelet tree.

Definition at line 102 of file wm_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::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::sigma = m_sigma

Effective alphabet size of the wavelet tree.

Definition at line 100 of file wm_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::wm_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 101 of file wm_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/wm_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

◆ wm_int() [1/4]

◆ wm_int() [2/4]

◆ wm_int() [3/4]

◆ wm_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]

◆ inverse_select()

◆ is_leaf()

◆ 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_rank_level

◆ m_sigma

◆ m_size

◆ m_tree

◆ m_tree_rank

◆ m_tree_select0

◆ m_tree_select1

◆ m_zero_cnt

◆ max_level

◆ sigma

◆ tree