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 825 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 872 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 1218 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 1060 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 1138 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 1199 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 |
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 1073 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 1091 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 1162 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 1177 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 1054 of file wt_gmr.hpp.