SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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.
 
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.
 
 wt_gmr (wt_gmr const &wt)
 Copy constructor.
 
 wt_gmr (wt_gmr &&wt)
 Move constructor.
 
wt_gmroperator= (wt_gmr const &wt)
 Assignment operator.
 
wt_gmroperator= (wt_gmr &&wt)
 Move assignment 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 input[i] are in the prefix [0..i-1] of the original input.
 
size_type select (size_type i, value_type c) const
 Calculates the i-th occurrence of the symbol c in the supported vector.
 
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.
 
iterator begin ()
 
const_iterator end ()
 
iterator begin () const
 
const_iterator end () const
 
bool operator== (wt_gmr const &other) const noexcept
 Equality operator.
 
bool operator!= (wt_gmr const &other) const noexcept
 Inequality operator.
 

Public Attributes

size_type const & sigma = 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 825 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>
int_alphabet_tag sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::alphabet_category

Definition at line 834 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>
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 831 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>
t_bitvector::difference_type sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::difference_type

Definition at line 830 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>
wt_tag sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::index_category

Definition at line 833 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>
const_iterator sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::iterator

Definition at line 832 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>
t_rac::size_type sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::size_type

Definition at line 828 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>
t_rac::value_type sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::value_type

Definition at line 829 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 835 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 872 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 ( wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero > const & wt)
inline

Copy constructor.

Definition at line 976 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 999 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 1259 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 1267 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 1237 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 1218 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 1060 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 1263 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 1271 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 1138 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 1199 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 1287 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= ( wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero > && wt)
inline

Move assignment operator.

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

Assignment operator.

Definition at line 1022 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 1277 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 1073 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 1091 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 1162 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 1177 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 1054 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>
size_type const& sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::sigma = m_sigma

Definition at line 857 of file wt_gmr.hpp.


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