SDSL
3.0.0
Succinct Data Structure Library
|
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_rlmn > | const_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. More... | |
wt_rlmn (const wt_rlmn &wt) | |
Copy constructor. More... | |
wt_rlmn (wt_rlmn &&wt) | |
Move constructor. More... | |
wt_rlmn & | operator= (const wt_rlmn &wt) |
Assignment operator. More... | |
wt_rlmn & | operator= (wt_rlmn &&wt) |
Assignment move 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... | |
value_type | operator[] (size_type 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_type > | inverse_select (size_type i) const |
Calculates how many times symbol wt[i] occurs in the prefix [0..i-1]. More... | |
size_type | select (size_type i, value_type c) const |
Calculates the ith occurrence of the symbol c in the supported vector. More... | |
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 |
Serialise (save) via cereal. More... | |
template<typename archive_t > | |
void | CEREAL_LOAD_FUNCTION_NAME (archive_t &ar) |
Load via cereal. More... | |
bool | operator== (wt_rlmn const &other) const noexcept |
Equality operator. More... | |
bool | operator!= (wt_rlmn const &other) const noexcept |
Inequality operator. More... | |
Public Attributes | |
const size_type & | sigma = m_wt.sigma |
A Wavelet Tree class for byte sequences.
t_bitvector | Type of the bitvector which is used to represent bf and bl which mark the head of each run in the original sequence. |
t_rank | Type of the rank support for bitvectors bf and bl. |
t_select | Type of the select support for bitvectors bf and lb. |
t_wt | Type of the wavelet tree for the string consisting of the heads of the runs of the original sequence. |
Definition at line 94 of file wt_rlmn.hpp.
typedef t_wt::alphabet_category sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::alphabet_category |
Definition at line 107 of file wt_rlmn.hpp.
typedef t_bitvector sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::bit_vector_type |
Definition at line 103 of file wt_rlmn.hpp.
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 117 of file wt_rlmn.hpp.
typedef wt_rlmn_trait<alphabet_category>::C_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::C_type |
Definition at line 116 of file wt_rlmn.hpp.
typedef random_access_const_iterator<wt_rlmn> sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::const_iterator |
Definition at line 101 of file wt_rlmn.hpp.
typedef t_bitvector::difference_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::difference_type |
Definition at line 100 of file wt_rlmn.hpp.
typedef wt_tag sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::index_category |
Definition at line 106 of file wt_rlmn.hpp.
typedef const_iterator sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::iterator |
Definition at line 102 of file wt_rlmn.hpp.
typedef t_rank sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::rank_support_type |
Definition at line 104 of file wt_rlmn.hpp.
typedef t_select sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::select_support_type |
Definition at line 105 of file wt_rlmn.hpp.
typedef int_vector ::size_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::size_type |
Definition at line 98 of file wt_rlmn.hpp.
typedef t_wt::value_type sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::value_type |
Definition at line 99 of file wt_rlmn.hpp.
typedef t_wt sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::wt_type |
Definition at line 97 of file wt_rlmn.hpp.
anonymous enum |
Enumerator | |
---|---|
lex_ordered |
Definition at line 108 of file wt_rlmn.hpp.
anonymous enum |
Enumerator | |
---|---|
width |
Definition at line 112 of file wt_rlmn.hpp.
|
default |
|
inline |
Construct the wavelet tree from a sequence defined by two interators.
begin | Iterator to the start of the input. |
end | Iterator one past the end of the input. |
tmp_dir | Temporary directory for intermediate results. |
Definition at line 152 of file wt_rlmn.hpp.
|
inline |
Copy constructor.
Definition at line 215 of file wt_rlmn.hpp.
|
inline |
Move constructor.
Definition at line 234 of file wt_rlmn.hpp.
|
inline |
Returns a const_iterator to the first element.
Definition at line 377 of file wt_rlmn.hpp.
|
inline |
Load via cereal.
Definition at line 434 of file wt_rlmn.hpp.
|
inline |
Serialise (save) via cereal.
Definition at line 418 of file wt_rlmn.hpp.
|
inline |
Returns whether the wavelet tree contains no data.
Definition at line 290 of file wt_rlmn.hpp.
|
inline |
Returns a const_iterator to the element after the last element.
Definition at line 380 of file wt_rlmn.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 339 of file wt_rlmn.hpp.
|
inline |
Loads the data structure from the given istream.
Definition at line 402 of file wt_rlmn.hpp.
|
inlinenoexcept |
Inequality operator.
Definition at line 461 of file wt_rlmn.hpp.
|
inline |
Assignment operator.
Definition at line 253 of file wt_rlmn.hpp.
|
inline |
Assignment move operator.
Definition at line 264 of file wt_rlmn.hpp.
|
inlinenoexcept |
Equality operator.
Definition at line 453 of file wt_rlmn.hpp.
|
inline |
Recovers the i-th symbol of the original vector.
i | Index in the original vector. ![]() |
Definition at line 299 of file wt_rlmn.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 314 of file wt_rlmn.hpp.
|
inline |
Calculates the ith occurrence of the symbol c in the supported vector.
i | The ith occurrence. ![]() |
c | The symbol c. |
Definition at line 367 of file wt_rlmn.hpp.
|
inline |
Serializes the data structure into the given ostream.
Definition at line 383 of file wt_rlmn.hpp.
|
inline |
Returns the size of the original vector.
Definition at line 287 of file wt_rlmn.hpp.
const size_type& sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::sigma = m_wt.sigma |
Definition at line 140 of file wt_rlmn.hpp.