SDSL 3.0.1
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 (const wm_int &wt)
 Copy constructor.
 
 wm_int (wm_int &&wt)
 Move copy constructor.
 
wm_intoperator= (const wm_int &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 (const node_type &v) const
 Checks if the node is a leaf node.
 
value_type sym (const node_type &v) const
 Symbol of leaf node v.
 
auto bit_vec (const node_type &v) const -> node_bv_container< t_bitvector >
 Random access container to bitvector of node v.
 
auto seq (const node_type &v) const -> random_access_container< std::function< value_type(size_type)> >
 Random access container to sequence of node v.
 
bool empty (const node_type &v) const
 Indicates if node v is empty.
 
auto size (const node_type &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 (const node_type &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 (const node_type &v, const range_vec_type &ranges) const
 Returns for each range its left and right child ranges.
 
std::array< range_vec_type, 2 > expand (const node_type &v, range_vec_type &&ranges) const
 Returns for each range its left and right child ranges.
 
std::array< range_type, 2 > expand (const node_type &v, const range_type &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

const size_typesigma = m_sigma
 Effective alphabet size of the wavelet tree.
 
const bit_vector_typetree = m_tree
 A concatenation of all bit vectors of the wavelet tree.
 
const uint32_t & 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 51 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 64 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 59 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 57 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 56 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 63 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 58 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 70 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 71 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 72 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 60 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 62 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 61 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 54 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 55 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 65 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 105 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 ( const wm_int< t_bitvector, t_rank, t_select, t_select_zero > &  wt)
inline

Copy constructor.

Definition at line 184 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 201 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 449 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 525 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 ( const node_type v) const -> node_bv_container<t_bitvector>
inline

Random access container to bitvector of node v.

Definition at line 652 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 579 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 564 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 263 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 ( const node_type v) const
inline

Indicates if node v is empty.

Definition at line 677 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 528 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 ( const 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 690 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< range_type, 2 > sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::expand ( const node_type v,
const range_type 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 777 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_vec_type, 2 > sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::expand ( const node_type v,
const 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 731 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 ( const node_type 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 747 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< 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 701 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 339 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 ( const node_type v) const
inline

Checks if the node is a leaf node.

Definition at line 646 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 549 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 605 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= ( const wm_int< t_bitvector, t_rank, t_select, t_select_zero > &  wt)
inline

Assignment operator.

Definition at line 218 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 > &&  wt)
inline

Assignment move operator.

Definition at line 239 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 596 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 271 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 791 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 429 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 303 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 683 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 374 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 ( const node_type v) const -> random_access_container<std::function<value_type(size_type)>>
inline

Random access container to sequence of node v.

Definition at line 658 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 531 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 260 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 ( const node_type v) const -> decltype(v.size)
inline

Return the size of node v.

Definition at line 680 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 ( const node_type v) const
inline

Symbol of leaf node v.

Definition at line 649 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 83 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 85 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 78 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 77 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 79 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 80 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 82 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 81 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 84 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>
const uint32_t& 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 90 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>
const size_type& 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 88 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>
const bit_vector_type& 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 89 of file wm_int.hpp.


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