SDSL 3.0.3
Succinct Data Structure Library
|
A prefix code-shaped wavelet. More...
#include <wt_pc.hpp>
Public Types | |
enum | { lex_ordered = shape_type::lex_ordered } |
typedef t_tree_strat::template type< wt_pc > | tree_strat_type |
typedef int_vector ::size_type | size_type |
typedef tree_strat_type::value_type | value_type |
typedef t_bitvector::difference_type | difference_type |
typedef random_access_const_iterator< wt_pc > | const_iterator |
typedef const_iterator | iterator |
typedef t_bitvector | bit_vector_type |
typedef t_rank | rank_1_type |
typedef t_select | select_1_type |
typedef t_select_zero | select_0_type |
typedef wt_tag | index_category |
typedef tree_strat_type::alphabet_category | alphabet_category |
typedef t_shape::template type< wt_pc > | shape_type |
using | node_type = typename tree_strat_type::node_type |
Public Member Functions | |
wt_pc () | |
template<typename t_it> | |
wt_pc (t_it begin, t_it end) | |
Construct the wavelet tree from a sequence defined by two interators. | |
template<typename t_it> | |
wt_pc (t_it begin, t_it end, std::string) | |
wt_pc (wt_pc const &wt) | |
Copy constructor. | |
wt_pc (wt_pc &&wt) | |
wt_pc & | operator= (wt_pc const &wt) |
Assignment operator. | |
wt_pc & | operator= (wt_pc &&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. | |
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. | |
void | interval_symbols (size_type i, size_type j, size_type &k, std::vector< value_type > &cs, std::vector< size_type > &rank_c_i, std::vector< size_type > &rank_c_j) 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, size_type>> | |
std::enable_if< shape_type::lex_ordered, t_ret_type >::type | lex_count (size_type i, size_type j, value_type c) const |
How many symbols are lexicographic smaller/greater than c in [i..j-1]. | |
template<class t_ret_type = std::tuple<size_type, size_type>> | |
std::enable_if< shape_type::lex_ordered, t_ret_type >::type | lex_smaller_count (size_type i, value_type c) const |
How many symbols are lexicographic smaller than c in [0..i-1]. | |
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. | |
bool | operator== (wt_pc const &other) const noexcept |
Equality operator. | |
bool | operator!= (wt_pc const &other) const noexcept |
Inequality operator. | |
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) |
auto | bit_vec (node_type const &v) const -> node_bv_container< t_bitvector > |
Random access container to bitvector of node v. | |
auto | seq (node_type const &v) const -> random_access_container< std::function< value_type(size_type)> > |
Random access container to sequence of node v. | |
bool | is_leaf (node_type const &v) const |
Checks if the node is a leaf node. | |
value_type | sym (node_type const &v) const |
Symbol for a leaf. | |
bool | empty (node_type const &v) const |
Indicates if node v is empty. | |
auto | size (node_type const &v) const -> decltype(m_tree.size(v)) |
Return the size of node v. | |
node_type | root () const |
Returns the root node. | |
std::array< node_type, 2 > | expand (node_type const &v) const |
Returns the two child nodes of an inner node. | |
std::array< range_vec_type, 2 > | expand (node_type const &v, range_vec_type const &ranges) const |
Returns for each range its left and right child ranges. | |
std::array< range_vec_type, 2 > | expand (node_type const &v, range_vec_type &&ranges) const |
Returns for each range its left and right child ranges. | |
std::array< range_type, 2 > | expand (node_type const &v, range_type const &r) const |
Returns for a range its left and right child ranges. | |
std::pair< uint64_t, uint64_t > | path (value_type c) const |
return the path to the leaf for a given symbol | |
std::pair< bool, value_type > | symbol_gte (value_type c) const |
Returns for a symbol c the next larger or equal symbol in the WT. | |
std::pair< bool, value_type > | symbol_lte (value_type c) const |
Returns for a symbol c the previous smaller or equal symbol in the WT. | |
Public Attributes | |
size_type const & | sigma = m_sigma |
bit_vector_type const & | bv = m_bv |
A prefix code-shaped wavelet.
t_shape | Shape of the tree (). |
t_bitvector | Underlying bitvector structure. |
t_rank | Rank support for pattern 1 on the bitvector. |
t_select | Select support for pattern 1 on the bitvector. |
t_select_zero | Select support for pattern 0 on the bitvector. |
t_tree_strat | Tree strategy determines alphabet and the tree class used to navigate the WT. |
typedef tree_strat_type::alphabet_category sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::alphabet_category |
typedef t_bitvector sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::bit_vector_type |
typedef random_access_const_iterator<wt_pc> sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::const_iterator |
typedef t_bitvector::difference_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::difference_type |
typedef wt_tag sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::index_category |
typedef const_iterator sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::iterator |
using sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::node_type = typename tree_strat_type::node_type |
typedef t_rank sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::rank_1_type |
typedef t_select_zero sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::select_0_type |
typedef t_select sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::select_1_type |
typedef t_shape::template type<wt_pc> sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::shape_type |
typedef int_vector ::size_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::size_type |
typedef t_tree_strat::template type<wt_pc> sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::tree_strat_type |
typedef tree_strat_type::value_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::value_type |
anonymous enum |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Returns a const_iterator to the first element.
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Returns a const_iterator to the element after the last element.
|
inline |
|
inline |
Returns for a range its left and right child ranges.
v | An inner node of an wavelet tree. |
r | A ranges [s,e], such that [s,e] is contained in v=[v_s,v_e]. |
|
inline |
Returns for each range its left and right child ranges.
v | An inner node of an wavelet tree. |
ranges | A vector of ranges. Each range [s,e] has to be contained in v=[v_s,v_e]. |
|
inline |
Returns for each range its left and right child ranges.
v | An inner node of an wavelet tree. |
ranges | A vector of ranges. Each range [s,e] has to be contained in v=[v_s,v_e]. |
|
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 ![]() |
|
inline |
|
inline |
|
inline |
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. |
|
inline |
How many symbols are lexicographic smaller than c in [0..i-1].
i | Exclusive right bound of the range. |
c | Symbol c. |
|
inline |
|
inlinenoexcept |
|
inline |
|
inline |
|
inlinenoexcept |
|
inline |
|
inline |
|
inline |
Calculates how many symbols c are in the prefix [0..i-1].
i | Exclusive right bound of the range. |
c | Symbol c. |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Returns for a symbol c the next larger or equal symbol in the WT.
c | the symbol |
|
inline |
Returns for a symbol c the previous smaller or equal symbol in the WT.
c | the symbol |
bit_vector_type const& sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::bv = m_bv |
size_type const& sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::sigma = m_sigma |