SDSL 3.0.3
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. | |
wt_rlmn (wt_rlmn const &wt) | |
Copy constructor. | |
wt_rlmn (wt_rlmn &&wt) | |
Move constructor. | |
wt_rlmn & | operator= (wt_rlmn const &wt) |
Assignment operator. | |
wt_rlmn & | operator= (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_type > | inverse_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 |
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 114 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 127 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 123 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 137 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 136 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 121 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 120 of file wt_rlmn.hpp.
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.
typedef const_iterator sdsl::wt_rlmn< t_bitvector, t_rank, t_select, t_wt >::iterator |
Definition at line 122 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 124 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 125 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 118 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 119 of file wt_rlmn.hpp.
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.
anonymous enum |
Enumerator | |
---|---|
lex_ordered |
Definition at line 128 of file wt_rlmn.hpp.
anonymous enum |
Enumerator | |
---|---|
width |
Definition at line 132 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 172 of file wt_rlmn.hpp.
|
inline |
Copy constructor.
Definition at line 241 of file wt_rlmn.hpp.
|
inline |
Move constructor.
Definition at line 260 of file wt_rlmn.hpp.
|
inline |
Returns a const_iterator to the first element.
Definition at line 415 of file wt_rlmn.hpp.
|
inline |
Load via cereal.
Definition at line 478 of file wt_rlmn.hpp.
|
inline |
Serialise (save) via cereal.
Definition at line 462 of file wt_rlmn.hpp.
|
inline |
Returns whether the wavelet tree contains no data.
Definition at line 319 of file wt_rlmn.hpp.
|
inline |
Returns a const_iterator to the element after the last element.
Definition at line 421 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 373 of file wt_rlmn.hpp.
|
inline |
Loads the data structure from the given istream.
Definition at line 446 of file wt_rlmn.hpp.
|
inlinenoexcept |
Inequality operator.
Definition at line 505 of file wt_rlmn.hpp.
|
inline |
Assignment move operator.
Definition at line 290 of file wt_rlmn.hpp.
|
inline |
Assignment operator.
Definition at line 279 of file wt_rlmn.hpp.
|
inlinenoexcept |
Equality operator.
Definition at line 497 of file wt_rlmn.hpp.
|
inline |
Recovers the i-th symbol of the original vector.
i | Index in the original vector. ![]() |
Definition at line 331 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 346 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 405 of file wt_rlmn.hpp.
|
inline |
Serializes the data structure into the given ostream.
Definition at line 427 of file wt_rlmn.hpp.
|
inline |
Returns the size of the original vector.
Definition at line 313 of file wt_rlmn.hpp.
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.