SDSL 3.0.1
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. More...
 
template<typename t_it >
 wt_epr (t_it begin, t_it end)
 Construct the EPR-dictionary from a sequence defined by two interators. More...
 
template<typename t_it >
 wt_epr (t_it begin, t_it end, std::string)
 
 wt_epr (const wt_epr &wt)
 Copy constructor. More...
 
 wt_epr (wt_epr &&wt)
 
wt_eproperator= (const wt_epr &wt)
 Assignment operator. More...
 
wt_eproperator= (wt_epr &&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...
 
auto operator[] (size_type const 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]. More...
 
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]. More...
 
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). More...
 
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. More...
 
const_iterator end () const
 Returns a const_iterator to the element after the last element. 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
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 

Public Attributes

const size_typesigma = m_sigma
 
const int_vectorbv = m_bv
 

Friends

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

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 32 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 42 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 38 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 40 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 41 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 39 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 36 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 35 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 37 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 43 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 103 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 134 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 ( const wt_epr< alphabet_size, rank_type, t_tree_strat > &  wt)
inline

Copy constructor.

Definition at line 139 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 148 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 322 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 369 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 360 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 186 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 325 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 228 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 276 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 312 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 341 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= ( const wt_epr< alphabet_size, rank_type, t_tree_strat > &  wt)
inline

Assignment operator.

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

Move assignment operator.

Definition at line 169 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 197 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 213 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 328 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 183 of file wt_epr.hpp.

Friends And Related Function 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 357 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 350 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<>>
const int_vector& sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::bv = m_bv

Definition at line 91 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<>>
const size_type& sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::sigma = m_sigma

Definition at line 90 of file wt_epr.hpp.


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