SDSL 3.0.3
Succinct Data Structure Library
|
An EPR-dictionary based wavelet. More...
#include <wt_epr.hpp>
Public Types | |
enum | { lex_ordered = true } |
typedef t_tree_strat::template type< wt_epr > | tree_strat_type |
typedef int_vector ::size_type | size_type |
typedef int_vector ::value_type | value_type |
typedef random_access_const_iterator< wt_epr > | const_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_epr & | operator= (wt_epr const &wt) |
Assignment operator. | |
wt_epr & | operator= (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_type > | inverse_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. | |
An EPR-dictionary based wavelet.
alphabet_size | Size of the alphabet. |
t_rank | Rank support for pattern 1 on the bitvector. |
t_tree_strat | Tree strategy determines alphabet and the tree class used to navigate the WT. |
Definition at line 45 of file wt_epr.hpp.
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.
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.
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.
typedef wt_tag sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::index_category |
Definition at line 54 of file wt_epr.hpp.
typedef const_iterator sdsl::wt_epr< alphabet_size, rank_type, t_tree_strat >::iterator |
Definition at line 52 of file wt_epr.hpp.
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.
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.
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.
anonymous enum |
Enumerator | |
---|---|
lex_ordered |
Definition at line 56 of file wt_epr.hpp.
|
default |
Default constructor.
|
inline |
Construct the EPR-dictionary from a sequence defined by two interators.
begin | Iterator to the start of the input. |
end | Iterator one past the end of the input. |
Definition at line 116 of file wt_epr.hpp.
|
inline |
Definition at line 147 of file wt_epr.hpp.
|
inline |
Copy constructor.
Definition at line 151 of file wt_epr.hpp.
|
inline |
Definition at line 156 of file wt_epr.hpp.
|
inline |
Returns a const_iterator to the first element.
Definition at line 337 of file wt_epr.hpp.
|
inline |
Definition at line 393 of file wt_epr.hpp.
|
inline |
Definition at line 384 of file wt_epr.hpp.
|
inline |
Returns whether the wavelet tree contains no data.
Definition at line 197 of file wt_epr.hpp.
|
inline |
Returns a const_iterator to the element after the last element.
Definition at line 343 of file wt_epr.hpp.
|
inline |
Calculates how many times symbol wt[i] occurs in the prefix [0..i-1].
i | The index of the symbol. |
Definition at line 242 of file wt_epr.hpp.
|
inline |
For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c).
i | The start index (inclusive) of the interval. |
j | The end index (exclusive) of the interval. |
k | Reference for number of different symbols in [i..j-1]. |
cs | Reference 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_i | Reference to a vector which equals rank_c_i[p] = rank(i,cs[p]), for ![]() |
rank_c_j | Reference to a vector which equals rank_c_j[p] = rank(j,cs[p]), for ![]() |
How many symbols are lexicographic smaller/greater than c in [i..j-1].
i | Start index (inclusive) of the interval. |
j | End index (exclusive) of the interval. |
c | Symbol c. |
Definition at line 290 of file wt_epr.hpp.
|
inline |
Definition at line 326 of file wt_epr.hpp.
|
inline |
Loads the data structure from the given istream.
Definition at line 362 of file wt_epr.hpp.
|
inline |
Move assignment operator.
Definition at line 177 of file wt_epr.hpp.
|
inline |
Assignment operator.
Definition at line 166 of file wt_epr.hpp.
|
inline |
Recovers the i-th symbol of the original vector.
i | Index in the original vector. |
Definition at line 211 of file wt_epr.hpp.
|
inline |
Calculates how many symbols c are in the prefix [0..i-1].
i | Exclusive right bound of the range. |
c | Symbol c. |
Definition at line 227 of file wt_epr.hpp.
|
inline |
Serializes the data structure into the given ostream.
Definition at line 349 of file wt_epr.hpp.
|
inline |
Returns the size of the original vector.
Definition at line 191 of file wt_epr.hpp.
|
friend |
Inequality operator.
Definition at line 378 of file wt_epr.hpp.
|
friend |
Equality operator.
Definition at line 371 of file wt_epr.hpp.
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.
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.