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

A Wavelet Tree class for byte sequences. More...

#include <wt_rlmn.hpp>

Public Types

enum  { lex_ordered = false }
 
enum  { width = wt_rlmn_trait<alphabet_category>::width }
 
typedef t_wt wt_type
 
typedef int_vector ::size_type size_type
 
typedef t_wt::value_type value_type
 
typedef t_bitvector::difference_type difference_type
 
typedef random_access_const_iterator< wt_rlmnconst_iterator
 
typedef const_iterator iterator
 
typedef t_bitvector bit_vector_type
 
typedef t_rank rank_support_type
 
typedef t_select select_support_type
 
typedef wt_tag index_category
 
typedef t_wt::alphabet_category alphabet_category
 
typedef wt_rlmn_trait< alphabet_category >::C_type C_type
 
typedef wt_rlmn_trait< alphabet_category >::C_bf_rank_type C_bf_rank_type
 

Public Member Functions

 wt_rlmn ()=default
 
template<typename t_it>
 wt_rlmn (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_rlmn (wt_rlmn const &wt)
 Copy constructor.
 
 wt_rlmn (wt_rlmn &&wt)
 Move constructor.
 
wt_rlmnoperator= (wt_rlmn const &wt)
 Assignment operator.
 
wt_rlmnoperator= (wt_rlmn &&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].
 
std::pair< size_type, value_typeinverse_select (size_type i) const
 Calculates how many times symbol wt[i] occurs in the prefix [0..i-1].
 
size_type select (size_type i, value_type c) const
 Calculates the ith occurrence of the symbol c in the supported vector.
 
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== (wt_rlmn const &other) const noexcept
 Equality operator.
 
bool operator!= (wt_rlmn const &other) const noexcept
 Inequality operator.
 

Public Attributes

size_type const & sigma = m_wt.sigma
 

Detailed Description

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
class sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >

A Wavelet Tree class for byte sequences.

Space complexity
$ nH_0 + 2|\Sigma|\log n + 2n + o(n) $ bits, where $n$ is the size of the vector the wavelet tree was build for.
Template Parameters
t_bitvectorType of the bitvector which is used to represent bf and bl which mark the head of each run in the original sequence.
t_rankType of the rank support for bitvectors bf and bl.
t_selectType of the select support for bitvectors bf and lb.
t_wtType of the wavelet tree for the string consisting of the heads of the runs of the original sequence.
Reference:
Veli Mäkinen, Gonzalo Navarro: Succinct Suffix Arrays Based on Run-Length Encoding. CPM 2005: 45-56

Definition at line 114 of file wt_rlmn.hpp.

Member Typedef Documentation

◆ alphabet_category

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
typedef t_wt::alphabet_category sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::alphabet_category

Definition at line 127 of file wt_rlmn.hpp.

◆ bit_vector_type

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
typedef t_bitvector sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::bit_vector_type

Definition at line 123 of file wt_rlmn.hpp.

◆ C_bf_rank_type

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
typedef wt_rlmn_trait<alphabet_category>::C_bf_rank_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::C_bf_rank_type

Definition at line 137 of file wt_rlmn.hpp.

◆ C_type

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
typedef wt_rlmn_trait<alphabet_category>::C_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::C_type

Definition at line 136 of file wt_rlmn.hpp.

◆ const_iterator

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
typedef random_access_const_iterator<wt_rlmn> sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::const_iterator

Definition at line 121 of file wt_rlmn.hpp.

◆ difference_type

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
typedef t_bitvector::difference_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::difference_type

Definition at line 120 of file wt_rlmn.hpp.

◆ index_category

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
typedef wt_tag sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::index_category

Definition at line 126 of file wt_rlmn.hpp.

◆ iterator

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
typedef const_iterator sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::iterator

Definition at line 122 of file wt_rlmn.hpp.

◆ rank_support_type

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
typedef t_rank sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::rank_support_type

Definition at line 124 of file wt_rlmn.hpp.

◆ select_support_type

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
typedef t_select sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::select_support_type

Definition at line 125 of file wt_rlmn.hpp.

◆ size_type

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
typedef int_vector ::size_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::size_type

Definition at line 118 of file wt_rlmn.hpp.

◆ value_type

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
typedef t_wt::value_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::value_type

Definition at line 119 of file wt_rlmn.hpp.

◆ wt_type

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
typedef t_wt sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::wt_type

Definition at line 117 of file wt_rlmn.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
anonymous enum
Enumerator
lex_ordered 

Definition at line 128 of file wt_rlmn.hpp.

◆ anonymous enum

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
anonymous enum
Enumerator
width 

Definition at line 132 of file wt_rlmn.hpp.

Constructor & Destructor Documentation

◆ wt_rlmn() [1/4]

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::wt_rlmn ( )
default

◆ wt_rlmn() [2/4]

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
template<typename t_it>
sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::wt_rlmn ( 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.

Definition at line 172 of file wt_rlmn.hpp.

◆ wt_rlmn() [3/4]

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::wt_rlmn ( wt_rlmn< t_bitvector, t_rank, t_select, t_wt > const & wt)
inline

Copy constructor.

Definition at line 241 of file wt_rlmn.hpp.

◆ wt_rlmn() [4/4]

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::wt_rlmn ( wt_rlmn< t_bitvector, t_rank, t_select, t_wt > && wt)
inline

Move constructor.

Definition at line 260 of file wt_rlmn.hpp.

Member Function Documentation

◆ begin()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
const_iterator sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::begin ( ) const
inline

Returns a const_iterator to the first element.

Definition at line 415 of file wt_rlmn.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
template<typename archive_t>
void sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar)
inline

Load via cereal.

Definition at line 478 of file wt_rlmn.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
template<typename archive_t>
void sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar) const
inline

Serialise (save) via cereal.

Definition at line 462 of file wt_rlmn.hpp.

◆ empty()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
bool sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::empty ( ) const
inline

Returns whether the wavelet tree contains no data.

Definition at line 319 of file wt_rlmn.hpp.

◆ end()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
const_iterator sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::end ( ) const
inline

Returns a const_iterator to the element after the last element.

Definition at line 421 of file wt_rlmn.hpp.

◆ inverse_select()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
std::pair< size_type, value_type > sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::inverse_select ( size_type i) const
inline

Calculates how many times symbol wt[i] occurs in the prefix [0..i-1].

Parameters
iThe index of the symbol.
Returns
Pair (rank(wt[i],i),wt[i])
Time complexity
$ \Order{H_0} $

Definition at line 373 of file wt_rlmn.hpp.

◆ load()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
void sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::load ( std::istream & in)
inline

Loads the data structure from the given istream.

Definition at line 446 of file wt_rlmn.hpp.

◆ operator!=()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
bool sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::operator!= ( wt_rlmn< t_bitvector, t_rank, t_select, t_wt > const & other) const
inlinenoexcept

Inequality operator.

Definition at line 505 of file wt_rlmn.hpp.

◆ operator=() [1/2]

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
wt_rlmn & sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::operator= ( wt_rlmn< t_bitvector, t_rank, t_select, t_wt > && wt)
inline

Assignment move operator.

Definition at line 290 of file wt_rlmn.hpp.

◆ operator=() [2/2]

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
wt_rlmn & sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::operator= ( wt_rlmn< t_bitvector, t_rank, t_select, t_wt > const & wt)
inline

Assignment operator.

Definition at line 279 of file wt_rlmn.hpp.

◆ operator==()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
bool sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::operator== ( wt_rlmn< t_bitvector, t_rank, t_select, t_wt > const & other) const
inlinenoexcept

Equality operator.

Definition at line 497 of file wt_rlmn.hpp.

◆ operator[]()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
value_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::operator[] ( size_type i) const
inline

Recovers the i-th symbol of the original vector.

Parameters
iIndex in the original vector. $i \in [0..size()-1]$.
Returns
The i-th symbol of the original vector.
Time complexity
$ \Order{H_0} $ on average, where $ H_0 $ is the zero order entropy of the sequence

Definition at line 331 of file wt_rlmn.hpp.

◆ rank()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
size_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::rank ( size_type i,
value_type c ) const
inline

Calculates how many symbols c are in the prefix [0..i-1].

Parameters
iExclusive right bound of the range ( $i\in[0..size()]$).
cSymbol c.
Returns
Number of occurrences of symbol c in the prefix [0..i-1].
Time complexity
$ \Order{H_0} $ on average, where $ H_0 $ is the zero order entropy of the sequence

Definition at line 346 of file wt_rlmn.hpp.

◆ select()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
size_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::select ( size_type i,
value_type c ) const
inline

Calculates the ith occurrence of the symbol c in the supported vector.

Parameters
iThe ith occurrence. $i\in [1..rank(size(),c)]$.
cThe symbol c.
Time complexity
$ \Order{H_0} $ on average, where $ H_0 $ is the zero order entropy of the sequence

Definition at line 405 of file wt_rlmn.hpp.

◆ serialize()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
size_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::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 427 of file wt_rlmn.hpp.

◆ size()

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
size_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::size ( ) const
inline

Returns the size of the original vector.

Definition at line 313 of file wt_rlmn.hpp.

Member Data Documentation

◆ sigma

template<class t_bitvector = sd_vector<>, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_wt = wt_huff<>>
size_type const& sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::sigma = m_wt.sigma

Definition at line 160 of file wt_rlmn.hpp.


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