SDSL 3.0.1
Succinct Data Structure Library
sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero > Class Template Reference

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

#include <wt_gmr.hpp>

Public Types

enum  { lex_ordered = 0 }
 
typedef t_rac::size_type size_type
 
typedef t_rac::value_type value_type
 
typedef t_bitvector::difference_type difference_type
 
typedef random_access_const_iterator< wt_gmrconst_iterator
 
typedef const_iterator iterator
 
typedef wt_tag index_category
 
typedef int_alphabet_tag alphabet_category
 

Public Member Functions

 wt_gmr ()=default
 Default constructor. More...
 
template<typename t_it >
 wt_gmr (t_it begin, t_it end, std::string tmp_dir=ram_file_name(""))
 Construct the wavelet tree from a sequence defined by two interators. More...
 
 wt_gmr (const wt_gmr &wt)
 Copy constructor. More...
 
 wt_gmr (wt_gmr &&wt)
 Move constructor. More...
 
wt_gmroperator= (const wt_gmr &wt)
 Assignment operator. More...
 
wt_gmroperator= (wt_gmr &&wt)
 Move assignment operator. More...
 
size_type size () const
 Returns the size of the original vector. More...
 
bool empty () const
 Returns whether the wavelet tree contains no data. More...
 
value_type operator[] (size_type i) const
 Recovers the i-th symbol of the original vector. More...
 
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. More...
 
std::pair< size_type, value_typeinverse_select (size_type i) const
 Calculates how many occurrences of symbol input[i] are in the prefix [0..i-1] of the original input. More...
 
size_type select (size_type i, value_type c) const
 Calculates the i-th occurrence of the symbol c in the supported vector. More...
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serializes the data structure into the given ostream. More...
 
void load (std::istream &in)
 Loads the data structure from the given istream. More...
 
template<typename archive_t >
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 Serialise (save) via cereal. More...
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 Load via cereal. More...
 
iterator begin ()
 
const_iterator end ()
 
iterator begin () const
 
const_iterator end () const
 
bool operator== (wt_gmr const &other) const noexcept
 Equality operator. More...
 
bool operator!= (wt_gmr const &other) const noexcept
 Inequality operator. More...
 

Public Attributes

const size_typesigma = m_sigma
 

Detailed Description

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
class sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >

A wavelet tree class for integer sequences.

Template Parameters
t_racType of the random access container used for storing the permutation.
t_inv_supportType of the support structure for inverse permutation
t_bitvectorType of the bitvector used for storing B and X.
t_selectType of the support structure for select on pattern 1.
t_select_zeroType of the support structure for select on pattern 0.

This is an implementation of the second proposal in the SODA paper of Golynski et. al. which supports fast access, inverse select, rank, and select.

References
[1] A. Golynski, J. Munro and S. Rao: ,,Rank/select operations on large alphabets: a tool for text indexing'' Proceedings of SODA 2006.

Definition at line 746 of file wt_gmr.hpp.

Member Typedef Documentation

◆ alphabet_category

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
typedef int_alphabet_tag sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::alphabet_category

Definition at line 755 of file wt_gmr.hpp.

◆ const_iterator

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
typedef random_access_const_iterator<wt_gmr> sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::const_iterator

Definition at line 752 of file wt_gmr.hpp.

◆ difference_type

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
typedef t_bitvector::difference_type sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::difference_type

Definition at line 751 of file wt_gmr.hpp.

◆ index_category

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
typedef wt_tag sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::index_category

Definition at line 754 of file wt_gmr.hpp.

◆ iterator

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
typedef const_iterator sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::iterator

Definition at line 753 of file wt_gmr.hpp.

◆ size_type

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
typedef t_rac::size_type sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::size_type

Definition at line 749 of file wt_gmr.hpp.

◆ value_type

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
typedef t_rac::value_type sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::value_type

Definition at line 750 of file wt_gmr.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, 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 756 of file wt_gmr.hpp.

Constructor & Destructor Documentation

◆ wt_gmr() [1/4]

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::wt_gmr ( )
default

Default constructor.

◆ wt_gmr() [2/4]

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
template<typename t_it >
sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::wt_gmr ( 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 793 of file wt_gmr.hpp.

◆ wt_gmr() [3/4]

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::wt_gmr ( const wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero > &  wt)
inline

Copy constructor.

Definition at line 895 of file wt_gmr.hpp.

◆ wt_gmr() [4/4]

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::wt_gmr ( wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero > &&  wt)
inline

Move constructor.

Definition at line 918 of file wt_gmr.hpp.

Member Function Documentation

◆ begin() [1/2]

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
iterator sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::begin ( )
inline

Definition at line 1163 of file wt_gmr.hpp.

◆ begin() [2/2]

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
iterator sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::begin ( ) const
inline

Definition at line 1165 of file wt_gmr.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
template<typename archive_t >
void sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Load via cereal.

Definition at line 1141 of file wt_gmr.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
template<typename archive_t >
void sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Serialise (save) via cereal.

Definition at line 1122 of file wt_gmr.hpp.

◆ empty()

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
bool sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::empty ( ) const
inline

Returns whether the wavelet tree contains no data.

Definition at line 976 of file wt_gmr.hpp.

◆ end() [1/2]

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
const_iterator sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::end ( )
inline

Definition at line 1164 of file wt_gmr.hpp.

◆ end() [2/2]

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
const_iterator sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::end ( ) const
inline

Definition at line 1166 of file wt_gmr.hpp.

◆ inverse_select()

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
std::pair< size_type, value_type > sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::inverse_select ( size_type  i) const
inline

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

Parameters
iThe index of the symbol.
Returns
Pair (rank(input[i],i), input[i])
Time complexity
$ \Order{1} + One access to the inverse permutation $
Precondition
$ i < size() $

Definition at line 1042 of file wt_gmr.hpp.

◆ load()

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
void sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::load ( std::istream &  in)
inline

Loads the data structure from the given istream.

Definition at line 1103 of file wt_gmr.hpp.

◆ operator!=()

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
bool sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::operator!= ( wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero > const &  other) const
inlinenoexcept

Inequality operator.

Definition at line 1180 of file wt_gmr.hpp.

◆ operator=() [1/2]

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
wt_gmr & sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::operator= ( const wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero > &  wt)
inline

Assignment operator.

Definition at line 941 of file wt_gmr.hpp.

◆ operator=() [2/2]

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
wt_gmr & sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::operator= ( wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero > &&  wt)
inline

Move assignment operator.

Definition at line 949 of file wt_gmr.hpp.

◆ operator==()

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
bool sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::operator== ( wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero > const &  other) const
inlinenoexcept

Equality operator.

Definition at line 1169 of file wt_gmr.hpp.

◆ operator[]()

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
value_type sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, 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.
Time complexity
$ \Order{1} + 1 Access to the inverse permutation $
Precondition
$ i < size() $

Definition at line 986 of file wt_gmr.hpp.

◆ rank()

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
size_type sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, 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 1004 of file wt_gmr.hpp.

◆ select()

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
size_type sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, 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{1} $
Precondition
$ 1 \leq i \leq rank(size(), c) $

Definition at line 1066 of file wt_gmr.hpp.

◆ serialize()

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
size_type sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, 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 1081 of file wt_gmr.hpp.

◆ size()

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
size_type sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::size ( ) const
inline

Returns the size of the original vector.

Definition at line 973 of file wt_gmr.hpp.

Member Data Documentation

◆ sigma

template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
const size_type& sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::sigma = m_sigma

Definition at line 778 of file wt_gmr.hpp.


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