template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
class sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >
A wavelet tree class for integer sequences.
- Template Parameters
-
t_rac | Type of the random access container used for storing the permutation. |
t_inv_support | Type of the support structure for inverse permutation |
t_bitvector | Type of the bitvector used for storing B and X. |
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 is an implementation of the second proposal in the SODA paper of Golynski et. al. which supports fast access, inverse select, rank, and select.
- References
- [1] A. Golynski, J. Munro and S. Rao: ,,Rank/select operations on large alphabets: a tool for text indexing'' Proceedings of SODA 2006.
Definition at line 746 of file wt_gmr.hpp.
template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
template<typename t_it >
sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::wt_gmr |
( |
t_it |
begin, |
|
|
t_it |
end, |
|
|
std::string |
tmp_dir = ram_file_name("") |
|
) |
| |
|
inline |
Construct the wavelet tree from a sequence defined by two interators.
- Parameters
-
begin | Iterator to the start of the input. |
end | Iterator one past the end of the input. |
tmp_dir | Temporary directory for intermediate results. |
- Time complexity
, where
I.e. we need \Order{n\log n} if rac is a permutation of 0..n-1.
Definition at line 793 of file wt_gmr.hpp.
template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
template<typename archive_t >
void sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::CEREAL_LOAD_FUNCTION_NAME |
( |
archive_t & |
ar | ) |
|
|
inline |
template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
template<typename archive_t >
void sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::CEREAL_SAVE_FUNCTION_NAME |
( |
archive_t & |
ar | ) |
const |
|
inline |
Serialise (save) via cereal.
Definition at line 1122 of file wt_gmr.hpp.
template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
bool sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::empty |
( |
| ) |
const |
|
inline |
Returns whether the wavelet tree contains no data.
Definition at line 976 of file wt_gmr.hpp.
template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
Calculates how many occurrences of symbol input[i] are in the prefix [0..i-1] of the original input.
- Parameters
-
i | The index of the symbol. |
- Returns
- Pair (rank(input[i],i), input[i])
- Time complexity
- Precondition
Definition at line 1042 of file wt_gmr.hpp.
template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
void sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::load |
( |
std::istream & |
in | ) |
|
|
inline |
Loads the data structure from the given istream.
Definition at line 1103 of file wt_gmr.hpp.
template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
wt_gmr & sdsl::wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero >::operator= |
( |
wt_gmr< t_rac, t_inverse_support, t_bitvector, t_select, t_select_zero > && |
wt | ) |
|
|
inline |
Move assignment operator.
Definition at line 949 of file wt_gmr.hpp.
template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
Recovers the i-th symbol of the original vector.
- Parameters
-
i | The index of the symbol in the original vector. |
- Returns
- The i-th symbol of the original vector.
- Time complexity
- Precondition
Definition at line 986 of file wt_gmr.hpp.
template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
Calculates how many symbols c are in the prefix [0..i-1] of the supported vector.
- Parameters
-
i | The exclusive index of the prefix range [0..i-1], so . |
c | The symbol to count the occurrences in the prefix. |
- Returns
- The number of occurrences of symbol c in the prefix [0..i-1] of the supported vector.
- Time complexity
- Precondition
Definition at line 1004 of file wt_gmr.hpp.
template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
Calculates the i-th occurrence of the symbol c in the supported vector.
- Parameters
-
i | The i-th occurrence. |
c | The symbol c. |
- Time complexity
- Precondition
Definition at line 1066 of file wt_gmr.hpp.
template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
Serializes the data structure into the given ostream.
Definition at line 1081 of file wt_gmr.hpp.
template<class t_rac = int_vector<>, class t_inverse_support = inv_multi_perm_support<32, t_rac>, class t_bitvector = bit_vector, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
Returns the size of the original vector.
Definition at line 973 of file wt_gmr.hpp.