SDSL 3.0.2
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::wt_gmr_rs< t_rac, 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 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< wt_gmr_rsconst_iterator
 
typedef const_iterator iterator
 
typedef wt_tag index_category
 
typedef int_alphabet_tag alphabet_category
 

Public Member Functions

 wt_gmr_rs ()=default
 Default constructor.
 
template<typename t_it >
 wt_gmr_rs (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_rs (wt_gmr_rs const &wt)
 Copy constructor.
 
 wt_gmr_rs (wt_gmr_rs &&wt)
 Move copy constructor.
 
wt_gmr_rsoperator= (wt_gmr_rs const &wt)
 Assignment operator.
 
wt_gmr_rsoperator= (wt_gmr_rs &&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 symbols c are in the prefix [0..i-1] of the supported vector.
 
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_rs const &other) const noexcept
 Equality operator.
 
bool operator!= (wt_gmr_rs const &other) const noexcept
 Inequality operator.
 

Public Attributes

size_type const & sigma = m_sigma
 

Detailed Description

template<class t_rac = int_vector<>, 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_rs< t_rac, 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 E.
t_bitvectorType of the bitvector used for storing B.
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 first proposal in the SODA paper of Golynski et. al. which support fast rank and select, but not fast access.

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 360 of file wt_gmr.hpp.

Member Typedef Documentation

◆ alphabet_category

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::alphabet_category

Definition at line 369 of file wt_gmr.hpp.

◆ const_iterator

template<class t_rac = int_vector<>, 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_rs> sdsl::wt_gmr_rs< t_rac, t_bitvector, t_select, t_select_zero >::const_iterator

Definition at line 366 of file wt_gmr.hpp.

◆ difference_type

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::difference_type

Definition at line 365 of file wt_gmr.hpp.

◆ index_category

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::index_category

Definition at line 368 of file wt_gmr.hpp.

◆ iterator

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::iterator

Definition at line 367 of file wt_gmr.hpp.

◆ size_type

template<class t_rac = int_vector<>, 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_vector ::size_type sdsl::wt_gmr_rs< t_rac, t_bitvector, t_select, t_select_zero >::size_type

Definition at line 363 of file wt_gmr.hpp.

◆ value_type

template<class t_rac = int_vector<>, 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_vector ::value_type sdsl::wt_gmr_rs< t_rac, t_bitvector, t_select, t_select_zero >::value_type

Definition at line 364 of file wt_gmr.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<class t_rac = int_vector<>, 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 370 of file wt_gmr.hpp.

Constructor & Destructor Documentation

◆ wt_gmr_rs() [1/4]

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::wt_gmr_rs ( )
default

Default constructor.

◆ wt_gmr_rs() [2/4]

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::wt_gmr_rs ( 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 401 of file wt_gmr.hpp.

◆ wt_gmr_rs() [3/4]

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::wt_gmr_rs ( wt_gmr_rs< t_rac, t_bitvector, t_select, t_select_zero > const &  wt)
inline

Copy constructor.

Definition at line 490 of file wt_gmr.hpp.

◆ wt_gmr_rs() [4/4]

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::wt_gmr_rs ( wt_gmr_rs< t_rac, t_bitvector, t_select, t_select_zero > &&  wt)
inline

Move copy constructor.

Definition at line 505 of file wt_gmr.hpp.

Member Function Documentation

◆ begin() [1/2]

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::begin ( )
inline

Definition at line 770 of file wt_gmr.hpp.

◆ begin() [2/2]

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::begin ( ) const
inline

Definition at line 778 of file wt_gmr.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Load via cereal.

Definition at line 756 of file wt_gmr.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Serialise (save) via cereal.

Definition at line 742 of file wt_gmr.hpp.

◆ empty()

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::empty ( ) const
inline

Returns whether the wavelet tree contains no data.

Definition at line 550 of file wt_gmr.hpp.

◆ end() [1/2]

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::end ( )
inline

Definition at line 774 of file wt_gmr.hpp.

◆ end() [2/2]

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::end ( ) const
inline

Definition at line 782 of file wt_gmr.hpp.

◆ inverse_select()

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::inverse_select ( size_type  i) 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{|\Sigma|} $
Precondition
$ i \leq size() $

Definition at line 650 of file wt_gmr.hpp.

◆ load()

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::load ( std::istream &  in)
inline

Loads the data structure from the given istream.

Definition at line 728 of file wt_gmr.hpp.

◆ operator!=()

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::operator!= ( wt_gmr_rs< t_rac, t_bitvector, t_select, t_select_zero > const &  other) const
inlinenoexcept

Inequality operator.

Definition at line 796 of file wt_gmr.hpp.

◆ operator=() [1/2]

template<class t_rac = int_vector<>, 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_rs & sdsl::wt_gmr_rs< t_rac, t_bitvector, t_select, t_select_zero >::operator= ( wt_gmr_rs< t_rac, t_bitvector, t_select, t_select_zero > &&  wt)
inline

Move assignment operator.

Definition at line 528 of file wt_gmr.hpp.

◆ operator=() [2/2]

template<class t_rac = int_vector<>, 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_rs & sdsl::wt_gmr_rs< t_rac, t_bitvector, t_select, t_select_zero >::operator= ( wt_gmr_rs< t_rac, t_bitvector, t_select, t_select_zero > const &  wt)
inline

Assignment operator.

Definition at line 520 of file wt_gmr.hpp.

◆ operator==()

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::operator== ( wt_gmr_rs< t_rac, t_bitvector, t_select, t_select_zero > const &  other) const
inlinenoexcept

Equality operator.

Definition at line 788 of file wt_gmr.hpp.

◆ operator[]()

template<class t_rac = int_vector<>, 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_rs< t_rac, 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{|\Sigma|} $
Precondition
$ i < size() $

Definition at line 563 of file wt_gmr.hpp.

◆ rank()

template<class t_rac = int_vector<>, 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_rs< t_rac, 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 607 of file wt_gmr.hpp.

◆ select()

template<class t_rac = int_vector<>, 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_rs< t_rac, 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 704 of file wt_gmr.hpp.

◆ serialize()

template<class t_rac = int_vector<>, 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_rs< t_rac, 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 711 of file wt_gmr.hpp.

◆ size()

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::size ( ) const
inline

Returns the size of the original vector.

Definition at line 544 of file wt_gmr.hpp.

Member Data Documentation

◆ sigma

template<class t_rac = int_vector<>, 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_rs< t_rac, t_bitvector, t_select, t_select_zero >::sigma = m_sigma

Definition at line 386 of file wt_gmr.hpp.


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