SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero > Class Template Reference

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_intconst_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_typepoint_type
typedef std::vector< point_typepoint_vec_type
typedef std::pair< size_type, point_vec_typer2d_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_intoperator= (wm_int const &wt)
 Assignment operator.
wm_intoperator= (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_typeinverse_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_bitvectorType of the bitvector used for representing the wavelet tree.
t_rankType of the support structure for rank on pattern 1.
t_selectType of the support structure for select on pattern 1.
t_select_zeroType 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
beginIterator to the start of the input.
endIterator one past the end of the input.
tmp_dirTemporary directory for intermediate results.
Time complexity
$ \Order{n\log|\Sigma|}$, where $n=size$ 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
vAn 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
vAn 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
vAn inner node of an wavelet tree.
rA 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
vAn inner node of an wavelet tree.
rangesA 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
vAn inner node of an wavelet tree.
rangesA 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
iThe index of the symbol.
Returns
Pair (rank(wt[i],i),wt[i])
Precondition
$ i < size() $

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
iThe index of the symbol in the original vector.
Returns
The i-th symbol of the original vector.
Precondition
$ i < size() $

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
lbLeft bound of index interval (inclusive)
rbRight bound of index interval (inclusive)
vlbLeft bound of value interval (inclusive)
vrbRight bound of value interval (inclusive)
reportShould 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
iThe exclusive index of the prefix range [0..i-1], so $i\in[0..size()]$.
cThe 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
iThe i-th occurrence.
cThe 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