SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat > Class Template Reference

An EPR-dictionary based wavelet. More...

#include <wt_epr.hpp>

Public Types

enum  { lex_ordered = true }
 
typedef t_tree_strat::template type< wt_eprtree_strat_type
 
typedef int_vector ::size_type size_type
 
typedef int_vector ::value_type value_type
 
typedef random_access_const_iterator< wt_eprconst_iterator
 
typedef const_iterator iterator
 
typedef int_vector ::difference_type difference_type
 
typedef wt_tag index_category
 
typedef byte_alphabet_tag alphabet_category
 

Public Member Functions

 wt_epr ()=default
 Default constructor.
 
template<typename t_it >
 wt_epr (t_it begin, t_it end)
 Construct the EPR-dictionary from a sequence defined by two interators.
 
template<typename t_it >
 wt_epr (t_it begin, t_it end, std::string)
 
 wt_epr (wt_epr const &wt)
 Copy constructor.
 
 wt_epr (wt_epr &&wt)
 
wt_eproperator= (wt_epr const &wt)
 Assignment operator.
 
wt_eproperator= (wt_epr &&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.
 
auto operator[] (size_type const 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].
 
template<class t_ret_type = std::tuple<size_type, size_type, size_type>>
t_ret_type lex_count (size_type i, size_type j, value_type c) const
 For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c).
 
template<class t_ret_type = std::tuple<size_type, size_type>>
t_ret_type lex_smaller_count (size_type i, value_type c) 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
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 

Public Attributes

size_type const & sigma = m_sigma
 
int_vector const & bv = m_bv
 

Friends

bool operator== (wt_epr const &lhs, wt_epr const &rhs) noexcept
 Equality operator.
 
bool operator!= (wt_epr const &lhs, wt_epr const &rhs) noexcept
 Inequality operator.
 

Detailed Description

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
class sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >

An EPR-dictionary based wavelet.

Template Parameters
alphabet_sizeSize of the alphabet.
t_rankRank support for pattern 1 on the bitvector.
t_tree_stratTree strategy determines alphabet and the tree class used to navigate the WT.

Definition at line 45 of file wt_epr.hpp.

Member Typedef Documentation

◆ alphabet_category

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
typedef byte_alphabet_tag sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::alphabet_category

Definition at line 55 of file wt_epr.hpp.

◆ const_iterator

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
typedef random_access_const_iterator<wt_epr> sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::const_iterator

Definition at line 51 of file wt_epr.hpp.

◆ difference_type

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
typedef int_vector ::difference_type sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::difference_type

Definition at line 53 of file wt_epr.hpp.

◆ index_category

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
typedef wt_tag sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::index_category

Definition at line 54 of file wt_epr.hpp.

◆ iterator

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
typedef const_iterator sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::iterator

Definition at line 52 of file wt_epr.hpp.

◆ size_type

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
typedef int_vector ::size_type sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::size_type

Definition at line 49 of file wt_epr.hpp.

◆ tree_strat_type

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
typedef t_tree_strat::template type<wt_epr> sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::tree_strat_type

Definition at line 48 of file wt_epr.hpp.

◆ value_type

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
typedef int_vector ::value_type sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::value_type

Definition at line 50 of file wt_epr.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
anonymous enum
Enumerator
lex_ordered 

Definition at line 56 of file wt_epr.hpp.

Constructor & Destructor Documentation

◆ wt_epr() [1/5]

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::wt_epr ( )
default

Default constructor.

◆ wt_epr() [2/5]

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
template<typename t_it >
sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::wt_epr ( t_it begin,
t_it end )
inline

Construct the EPR-dictionary from a sequence defined by two interators.

Parameters
beginIterator to the start of the input.
endIterator one past the end of the input.
Time complexity
$ \Order{n\log|\Sigma|}$, where $n=size$

Definition at line 116 of file wt_epr.hpp.

◆ wt_epr() [3/5]

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
template<typename t_it >
sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::wt_epr ( t_it begin,
t_it end,
std::string  )
inline

Definition at line 147 of file wt_epr.hpp.

◆ wt_epr() [4/5]

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::wt_epr ( wt_epr< alphabet_size, rank_type, t_tree_strat > const & wt)
inline

Copy constructor.

Definition at line 151 of file wt_epr.hpp.

◆ wt_epr() [5/5]

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::wt_epr ( wt_epr< alphabet_size, rank_type, t_tree_strat > && wt)
inline

Definition at line 156 of file wt_epr.hpp.

Member Function Documentation

◆ begin()

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
const_iterator sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::begin ( ) const
inline

Returns a const_iterator to the first element.

Definition at line 337 of file wt_epr.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
template<typename archive_t >
void sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar)
inline

Definition at line 393 of file wt_epr.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
template<typename archive_t >
void sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar) const
inline

Definition at line 384 of file wt_epr.hpp.

◆ empty()

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
bool sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::empty ( ) const
inline

Returns whether the wavelet tree contains no data.

Definition at line 197 of file wt_epr.hpp.

◆ end()

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
const_iterator sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::end ( ) const
inline

Returns a const_iterator to the element after the last element.

Definition at line 343 of file wt_epr.hpp.

◆ inverse_select()

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
std::pair< size_type, value_type > sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::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{1} $
Precondition
$ i < size() $

Definition at line 242 of file wt_epr.hpp.

◆ lex_count()

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
template<class t_ret_type = std::tuple<size_type, size_type, size_type>>
t_ret_type sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::lex_count ( size_type i,
size_type j,
value_type c ) const
inline

For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c).

Parameters
iThe start index (inclusive) of the interval.
jThe end index (exclusive) of the interval.
kReference for number of different symbols in [i..j-1].
csReference to a vector that will contain in cs[0..k-1] all symbols that occur in [i..j-1] in arbitrary order (if lex_ordered = false) and ascending order (if lex_ordered = true).
rank_c_iReference to a vector which equals rank_c_i[p] = rank(i,cs[p]), for $ 0 \leq p < k $.
rank_c_jReference to a vector which equals rank_c_j[p] = rank(j,cs[p]), for $ 0 \leq p < k $.
Precondition
$ i \leq j \leq size() $ $ cs.size() \geq \sigma $ $ rank_{c_i}.size() \geq \sigma $ $ rank_{c_j}.size() \geq \sigma $

How many symbols are lexicographic smaller/greater than c in [i..j-1].

Parameters
iStart index (inclusive) of the interval.
jEnd index (exclusive) of the interval.
cSymbol c.
Returns
A triple containing:
  • rank(i,c)
  • #symbols smaller than c in [i..j-1]
  • #symbols greater than c in [i..j-1]
Precondition
$ i \leq j \leq size() $

Definition at line 290 of file wt_epr.hpp.

◆ lex_smaller_count()

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
template<class t_ret_type = std::tuple<size_type, size_type>>
t_ret_type sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::lex_smaller_count ( size_type i,
value_type c ) const
inline

Definition at line 326 of file wt_epr.hpp.

◆ load()

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
void sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::load ( std::istream & in)
inline

Loads the data structure from the given istream.

Definition at line 362 of file wt_epr.hpp.

◆ operator=() [1/2]

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
wt_epr & sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::operator= ( wt_epr< alphabet_size, rank_type, t_tree_strat > && wt)
inline

Move assignment operator.

Definition at line 177 of file wt_epr.hpp.

◆ operator=() [2/2]

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
wt_epr & sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::operator= ( wt_epr< alphabet_size, rank_type, t_tree_strat > const & wt)
inline

Assignment operator.

Definition at line 166 of file wt_epr.hpp.

◆ operator[]()

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
auto sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::operator[] ( size_type const i) const
inline

Recovers the i-th symbol of the original vector.

Parameters
iIndex in the original vector.
Returns
The i-th symbol of the original vector.
Time complexity
$ \Order{1} $
Precondition
$ i < size() $

Definition at line 211 of file wt_epr.hpp.

◆ rank()

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
size_type sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::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.
cSymbol c.
Returns
Number of occurrences of symbol c in the prefix [0..i-1].
Time complexity
$ \Order{1} $
Precondition
$ i \leq size() $

Definition at line 227 of file wt_epr.hpp.

◆ serialize()

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
size_type sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::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 349 of file wt_epr.hpp.

◆ size()

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
size_type sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::size ( ) const
inline

Returns the size of the original vector.

Definition at line 191 of file wt_epr.hpp.

Friends And Related Symbol Documentation

◆ operator!=

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
bool operator!= ( wt_epr< alphabet_size, rank_type, t_tree_strat > const & lhs,
wt_epr< alphabet_size, rank_type, t_tree_strat > const & rhs )
friend

Inequality operator.

Definition at line 378 of file wt_epr.hpp.

◆ operator==

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
bool operator== ( wt_epr< alphabet_size, rank_type, t_tree_strat > const & lhs,
wt_epr< alphabet_size, rank_type, t_tree_strat > const & rhs )
friend

Equality operator.

Definition at line 371 of file wt_epr.hpp.

Member Data Documentation

◆ bv

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
int_vector const& sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::bv = m_bv

Definition at line 104 of file wt_epr.hpp.

◆ sigma

template<uint8_t alphabet_size, class rank_type = rank_support_int_v<alphabet_size>, class t_tree_strat = byte_tree<>>
size_type const& sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::sigma = m_sigma

Definition at line 103 of file wt_epr.hpp.


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