SDSL
3.0.0
Succinct Data Structure Library
|
A wavelet tree class for integer sequences. More...
#include <wt_int.hpp>
Classes | |
struct | node_type |
Represents a node in the wavelet tree. More... | |
Public Types | |
enum | { lex_ordered = 1 } |
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< wt_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 | |
wt_int ()=default | |
Default constructor. More... | |
template<typename t_it > | |
wt_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. More... | |
wt_int (const wt_int &wt) | |
Copy constructor. More... | |
wt_int (wt_int &&wt) | |
Move constructor. More... | |
wt_int & | operator= (const wt_int &wt) |
Assignment operator. More... | |
wt_int & | operator= (wt_int &&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] of the supported vector. More... | |
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. More... | |
size_type | select (size_type i, value_type c) const |
Calculates the i-th occurrence of the symbol c in the supported vector. More... | |
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). More... | |
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 |
How many symbols are lexicographic smaller/greater than c in [i..j-1]. More... | |
template<class t_ret_type = std::tuple<size_type, size_type>> | |
t_ret_type | lex_smaller_count (size_type i, value_type c) const |
How many symbols are lexicographic smaller than c in [0..i-1]. More... | |
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]. More... | |
void | _range_search_2d (size_type lb, size_type rb, value_type vlb, value_type vrb, size_type level, size_type ilb, size_type node_size, std::vector< size_type > &offsets, std::vector< size_type > &ones_before_os, size_type path, point_vec_type &point_vec, bool report, size_type &cnt_answers) const |
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 |
template<typename archive_t > | |
void | CEREAL_LOAD_FUNCTION_NAME (archive_t &ar) |
bool | operator== (wt_int const &other) const noexcept |
Equality operator. More... | |
bool | operator!= (wt_int const &other) const noexcept |
Inequality operator. More... | |
bool | is_leaf (const node_type &v) const |
Checks if the node is a leaf node. More... | |
value_type | sym (const node_type &v) const |
Returns the symbol of leaf node v. More... | |
auto | bit_vec (const node_type &v) const -> node_bv_container< t_bitvector > |
Random access container to bitvector of node v. More... | |
auto | seq (const node_type &v) const -> random_access_container< std::function< value_type(size_type)>> |
Random access container to sequence of node v. More... | |
bool | empty (const node_type &v) const |
Indicates if node v is empty. More... | |
auto | size (const node_type &v) const -> decltype(v.size) |
Return the size of node v. More... | |
node_type | root () const |
Return the root node. More... | |
std::array< node_type, 2 > | expand (const node_type &v) const |
Returns the two child nodes of an inner node. More... | |
std::array< node_type, 2 > | expand (node_type &&v) const |
Returns the two child nodes of an inner node. More... | |
std::array< range_vec_type, 2 > | expand (const node_type &v, const range_vec_type &ranges) const |
Returns for each range its left and right child ranges. More... | |
std::array< range_vec_type, 2 > | expand (const node_type &v, range_vec_type &&ranges) const |
Returns for each range its left and right child ranges. More... | |
std::array< range_type, 2 > | expand (const node_type &v, const range_type &r) const |
Returns for a range its left and right child ranges. More... | |
std::pair< uint64_t, uint64_t > | path (value_type c) const |
return the path to the leaf for a given symbol More... | |
Public Attributes | |
const size_type & | sigma = m_sigma |
Effective alphabet size of the wavelet tree. More... | |
const bit_vector_type & | tree = m_tree |
A concatenation of all bit vectors of the wavelet tree. More... | |
const uint32_t & | max_level = m_max_level |
Maximal level of the wavelet tree. More... | |
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 |
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 . |
Definition at line 48 of file wt_int.hpp.
typedef int_alphabet_tag sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::alphabet_category |
Definition at line 61 of file wt_int.hpp.
typedef t_bitvector sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::bit_vector_type |
Definition at line 56 of file wt_int.hpp.
typedef random_access_const_iterator<wt_int> sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::const_iterator |
Definition at line 54 of file wt_int.hpp.
typedef t_bitvector::difference_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::difference_type |
Definition at line 53 of file wt_int.hpp.
typedef wt_tag sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::index_category |
Definition at line 60 of file wt_int.hpp.
typedef const_iterator sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::iterator |
Definition at line 55 of file wt_int.hpp.
typedef std::pair<value_type, size_type> sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::point_type |
Definition at line 67 of file wt_int.hpp.
typedef std::vector<point_type> sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::point_vec_type |
Definition at line 68 of file wt_int.hpp.
typedef std::pair<size_type, point_vec_type> sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::r2d_res_type |
Definition at line 69 of file wt_int.hpp.
typedef t_rank sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::rank_1_type |
Definition at line 57 of file wt_int.hpp.
typedef t_select_zero sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::select_0_type |
Definition at line 59 of file wt_int.hpp.
typedef t_select sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::select_1_type |
Definition at line 58 of file wt_int.hpp.
typedef int_vector ::size_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::size_type |
Definition at line 51 of file wt_int.hpp.
typedef int_vector ::value_type sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::value_type |
Definition at line 52 of file wt_int.hpp.
anonymous enum |
Enumerator | |
---|---|
lex_ordered |
Definition at line 62 of file wt_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 156 of file wt_int.hpp.
|
inline |
Copy constructor.
Definition at line 244 of file wt_int.hpp.
|
inline |
Move constructor.
Definition at line 259 of file wt_int.hpp.
|
inline |
Definition at line 652 of file wt_int.hpp.
|
inline |
Returns a const_iterator to the first element.
Definition at line 749 of file wt_int.hpp.
|
inline |
Random access container to bitvector of node v.
Definition at line 865 of file wt_int.hpp.
|
inline |
Definition at line 795 of file wt_int.hpp.
|
inline |
Definition at line 783 of file wt_int.hpp.
|
inline |
Returns whether the wavelet tree contains no data.
Definition at line 307 of file wt_int.hpp.
|
inline |
Indicates if node v is empty.
Definition at line 890 of file wt_int.hpp.
|
inline |
Returns a const_iterator to the element after the last element.
Definition at line 752 of file wt_int.hpp.
|
inline |
Returns the two child nodes of an inner node.
v | An inner node of a wavelet tree. |
Definition at line 903 of file wt_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 989 of file wt_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 943 of file wt_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 959 of file wt_int.hpp.
|
inline |
Returns the two child nodes of an inner node.
v | An inner node of a wavelet tree. |
Definition at line 914 of file wt_int.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 ascending order. |
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 ![]() |
Definition at line 505 of file wt_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 393 of file wt_int.hpp.
|
inline |
Checks if the node is a leaf node.
Definition at line 859 of file wt_int.hpp.
|
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. |
Definition at line 542 of file wt_int.hpp.
|
inline |
How many symbols are lexicographic smaller than c in [0..i-1].
i | Exclusive right bound of the range. |
c | Symbol c. |
Definition at line 592 of file wt_int.hpp.
|
inline |
Loads the data structure from the given istream.
Definition at line 771 of file wt_int.hpp.
|
inlinenoexcept |
Inequality operator.
Definition at line 818 of file wt_int.hpp.
|
inline |
Assignment operator.
Definition at line 274 of file wt_int.hpp.
|
inline |
Assignment move operator.
Definition at line 285 of file wt_int.hpp.
|
inlinenoexcept |
Equality operator.
Definition at line 810 of file wt_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 315 of file wt_int.hpp.
|
inline |
return the path to the leaf for a given symbol
Definition at line 1003 of file wt_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 635 of file wt_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 354 of file wt_int.hpp.
|
inline |
Return the root node.
Definition at line 896 of file wt_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 431 of file wt_int.hpp.
|
inline |
Random access container to sequence of node v.
Definition at line 871 of file wt_int.hpp.
|
inline |
Serializes the data structure into the given ostream.
Definition at line 755 of file wt_int.hpp.
|
inline |
Returns the size of the original vector.
Definition at line 304 of file wt_int.hpp.
|
inline |
Return the size of node v.
Definition at line 893 of file wt_int.hpp.
|
inline |
Returns the symbol of leaf node v.
Definition at line 862 of file wt_int.hpp.
|
protected |
Definition at line 78 of file wt_int.hpp.
|
protected |
Definition at line 73 of file wt_int.hpp.
|
protected |
Definition at line 72 of file wt_int.hpp.
|
protected |
Definition at line 74 of file wt_int.hpp.
|
protected |
Definition at line 75 of file wt_int.hpp.
|
protected |
Definition at line 77 of file wt_int.hpp.
|
protected |
Definition at line 76 of file wt_int.hpp.
const uint32_t& sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::max_level = m_max_level |
Maximal level of the wavelet tree.
Definition at line 141 of file wt_int.hpp.
const size_type& sdsl::wt_int< t_bitvector, t_rank, t_select, t_select_zero >::sigma = m_sigma |
Effective alphabet size of the wavelet tree.
Definition at line 139 of file wt_int.hpp.
const bit_vector_type& sdsl::wt_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 140 of file wt_int.hpp.