SDSL 3.0.3
Succinct Data Structure Library
|
A wavelet tree class for integer sequences. More...
#include <wm_int.hpp>
Classes | |
struct | node_type |
Represents a node in the wavelet tree. More... | |
Public Types | |
enum | { lex_ordered = 0 } |
typedef int_vector ::size_type | size_type |
typedef int_vector ::value_type | value_type |
typedef t_bitvector::difference_type | difference_type |
typedef random_access_const_iterator< wm_int > | 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 int_alphabet_tag | alphabet_category |
typedef std::pair< value_type, size_type > | point_type |
typedef std::vector< point_type > | point_vec_type |
typedef std::pair< size_type, point_vec_type > | r2d_res_type |
Public Member Functions | |
wm_int ()=default | |
Default constructor. | |
template<typename t_it> | |
wm_int (t_it begin, t_it end, std::string tmp_dir=ram_file_name("")) | |
Construct the wavelet tree from a sequence defined by two interators. | |
wm_int (wm_int const &wt) | |
Copy constructor. | |
wm_int (wm_int &&wt) | |
Move copy constructor. | |
wm_int & | operator= (wm_int const &wt) |
Assignment operator. | |
wm_int & | operator= (wm_int &&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] of the supported vector. | |
std::pair< size_type, value_type > | inverse_select (size_type i) const |
Calculates how many occurrences of symbol wt[i] are in the prefix [0..i-1] of the original sequence. | |
size_type | select (size_type i, value_type c) const |
Calculates the i-th occurrence of the symbol c in the supported vector. | |
std::pair< size_type, std::vector< std::pair< value_type, size_type > > > | range_search_2d (size_type lb, size_type rb, value_type vlb, value_type vrb, bool report=true) const |
range_search_2d searches points in the index interval [lb..rb] and value interval [vlb..vrb]. | |
void | _range_search_2d (node_type v, range_type r, value_type vlb, value_type vrb, size_type ilb, std::vector< size_type > &is, std::vector< size_type > &rank_off, point_vec_type &point_vec, bool report, size_type &cnt_answers) 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 |
Serialise (save) via cereal. | |
template<typename archive_t> | |
void | CEREAL_LOAD_FUNCTION_NAME (archive_t &ar) |
Load via cereal. | |
bool | operator== (wm_int const &other) const noexcept |
Equality operator. | |
bool | operator!= (wm_int const &other) const noexcept |
Inequality operator. | |
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 of leaf node v. | |
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 | empty (node_type const &v) const |
Indicates if node v is empty. | |
auto | size (node_type const &v) const -> decltype(v.size) |
Return the size of node v. | |
node_type | root () const |
Return 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< node_type, 2 > | expand (node_type &&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 | |
Public Attributes | |
size_type const & | sigma = m_sigma |
Effective alphabet size of the wavelet tree. | |
bit_vector_type const & | tree = m_tree |
A concatenation of all bit vectors of the wavelet tree. | |
uint32_t const & | max_level = m_max_level |
Maximal level of the wavelet tree. | |
Protected Attributes | |
size_type | m_size = 0 |
size_type | m_sigma = 0 |
bit_vector_type | m_tree |
rank_1_type | m_tree_rank |
select_1_type | m_tree_select1 |
select_0_type | m_tree_select0 |
uint32_t | m_max_level = 0 |
int_vector< 64 > | m_zero_cnt |
int_vector< 64 > | m_rank_level |
A wavelet tree class for integer sequences.
t_bitvector | Type of the bitvector used for representing the wavelet tree. |
t_rank | Type of the support structure for rank on pattern 1 . |
t_select | Type of the support structure for select on pattern 1 . |
t_select_zero | Type of the support structure for select on pattern 0 . |
This wavelet tree variant does not store the two children of a node v aligned with v; it is also known as wavelet matrix.
Definition at line 63 of file wm_int.hpp.
typedef int_alphabet_tag sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::alphabet_category |
Definition at line 76 of file wm_int.hpp.
typedef t_bitvector sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::bit_vector_type |
Definition at line 71 of file wm_int.hpp.
typedef random_access_const_iterator<wm_int> sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::const_iterator |
Definition at line 69 of file wm_int.hpp.
typedef t_bitvector::difference_type sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::difference_type |
Definition at line 68 of file wm_int.hpp.
typedef wt_tag sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::index_category |
Definition at line 75 of file wm_int.hpp.
typedef const_iterator sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::iterator |
Definition at line 70 of file wm_int.hpp.
typedef std::pair<value_type, size_type> sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::point_type |
Definition at line 82 of file wm_int.hpp.
typedef std::vector<point_type> sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::point_vec_type |
Definition at line 83 of file wm_int.hpp.
typedef std::pair<size_type, point_vec_type> sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::r2d_res_type |
Definition at line 84 of file wm_int.hpp.
typedef t_rank sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::rank_1_type |
Definition at line 72 of file wm_int.hpp.
typedef t_select_zero sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::select_0_type |
Definition at line 74 of file wm_int.hpp.
typedef t_select sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::select_1_type |
Definition at line 73 of file wm_int.hpp.
typedef int_vector ::size_type sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::size_type |
Definition at line 66 of file wm_int.hpp.
typedef int_vector ::value_type sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::value_type |
Definition at line 67 of file wm_int.hpp.
anonymous enum |
Enumerator | |
---|---|
lex_ordered |
Definition at line 77 of file wm_int.hpp.
|
default |
Default constructor.
|
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 117 of file wm_int.hpp.
|
inline |
Copy constructor.
Definition at line 203 of file wm_int.hpp.
|
inline |
Move copy constructor.
Definition at line 220 of file wm_int.hpp.
|
inline |
Definition at line 473 of file wm_int.hpp.
|
inline |
Returns a const_iterator to the first element.
Definition at line 553 of file wm_int.hpp.
|
inline |
Random access container to bitvector of node v.
Definition at line 704 of file wm_int.hpp.
|
inline |
Load via cereal.
Definition at line 613 of file wm_int.hpp.
|
inline |
Serialise (save) via cereal.
Definition at line 598 of file wm_int.hpp.
|
inline |
Returns whether the wavelet tree contains no data.
Definition at line 285 of file wm_int.hpp.
|
inline |
Indicates if node v is empty.
Definition at line 730 of file wm_int.hpp.
|
inline |
Returns a const_iterator to the element after the last element.
Definition at line 559 of file wm_int.hpp.
|
inline |
Returns the two child nodes of an inner node.
v | An inner node of a wavelet tree. |
Definition at line 763 of file wm_int.hpp.
|
inline |
Returns the two child nodes of an inner node.
v | An inner node of a wavelet tree. |
Definition at line 752 of file wm_int.hpp.
|
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]. |
Definition at line 839 of file wm_int.hpp.
|
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]. |
Definition at line 809 of file wm_int.hpp.
|
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]. |
Definition at line 793 of file wm_int.hpp.
|
inline |
Calculates how many occurrences of symbol wt[i] are in the prefix [0..i-1] of the original sequence.
i | The index of the symbol. |
Definition at line 364 of file wm_int.hpp.
|
inline |
Checks if the node is a leaf node.
Definition at line 692 of file wm_int.hpp.
|
inline |
Loads the data structure from the given istream.
Definition at line 583 of file wm_int.hpp.
|
inlinenoexcept |
Inequality operator.
Definition at line 639 of file wm_int.hpp.
|
inline |
Assignment move operator.
Definition at line 258 of file wm_int.hpp.
|
inline |
Assignment operator.
Definition at line 237 of file wm_int.hpp.
|
inlinenoexcept |
Equality operator.
Definition at line 630 of file wm_int.hpp.
|
inline |
Recovers the i-th symbol of the original vector.
i | The index of the symbol in the original vector. |
Definition at line 296 of file wm_int.hpp.
|
inline |
return the path to the leaf for a given symbol
Definition at line 853 of file wm_int.hpp.
|
inline |
range_search_2d searches points in the index interval [lb..rb] and value interval [vlb..vrb].
lb | Left bound of index interval (inclusive) |
rb | Right bound of index interval (inclusive) |
vlb | Left bound of value interval (inclusive) |
vrb | Right bound of value interval (inclusive) |
report | Should the matching points be returned? |
Definition at line 455 of file wm_int.hpp.
|
inline |
Calculates how many symbols c are in the prefix [0..i-1] of the supported vector.
i | The exclusive index of the prefix range [0..i-1], so ![]() |
c | The symbol to count the occurrences in the prefix. |
Definition at line 328 of file wm_int.hpp.
|
inline |
Return the root node.
Definition at line 742 of file wm_int.hpp.
|
inline |
Calculates the i-th occurrence of the symbol c in the supported vector.
i | The i-th occurrence. |
c | The symbol c. |
Definition at line 399 of file wm_int.hpp.
|
inline |
Random access container to sequence of node v.
Definition at line 710 of file wm_int.hpp.
|
inline |
Serializes the data structure into the given ostream.
Definition at line 565 of file wm_int.hpp.
|
inline |
Returns the size of the original vector.
Definition at line 279 of file wm_int.hpp.
|
inline |
Return the size of node v.
Definition at line 736 of file wm_int.hpp.
|
inline |
Symbol of leaf node v.
Definition at line 698 of file wm_int.hpp.
|
protected |
Definition at line 95 of file wm_int.hpp.
|
protected |
Definition at line 97 of file wm_int.hpp.
|
protected |
Definition at line 90 of file wm_int.hpp.
|
protected |
Definition at line 89 of file wm_int.hpp.
|
protected |
Definition at line 91 of file wm_int.hpp.
|
protected |
Definition at line 92 of file wm_int.hpp.
|
protected |
Definition at line 94 of file wm_int.hpp.
|
protected |
Definition at line 93 of file wm_int.hpp.
|
protected |
Definition at line 96 of file wm_int.hpp.
uint32_t const& sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::max_level = m_max_level |
Maximal level of the wavelet tree.
Definition at line 102 of file wm_int.hpp.
size_type const& sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::sigma = m_sigma |
Effective alphabet size of the wavelet tree.
Definition at line 100 of file wm_int.hpp.
bit_vector_type const& sdsl::wm_int< t_bitvector, t_rank, t_select, t_select_zero >::tree = m_tree |
A concatenation of all bit vectors of the wavelet tree.
Definition at line 101 of file wm_int.hpp.