8 #ifndef INCLUDED_SDSL_SUFFIX_ARRAY_HELPER
9 #define INCLUDED_SDSL_SUFFIX_ARRAY_HELPER
28 template <
typename t_csa>
31 assert(i < csa.size());
35 while (res < csa.sigma and csa.C[res] <= i) ++res;
36 return csa.comp2char[res - 1];
45 res = (upper_c + lower_c) / 2;
46 if (i < csa.C[res]) { upper_c = res; }
47 else if (i >= csa.C[res + 1])
51 }
while (i < csa.C[res] or i >= csa.C[res + 1]);
52 return csa.comp2char[res];
57 template <
typename t_csa,
bool t_direction>
66 template <
typename t_csa>
76 return csa.isa[(csa[i] + csa.size() - 1) % csa.size()];
80 template <
typename t_csa,
bool t_direction>
129 template <
typename t_csa,
bool t_direction>
137 return csa.isa[(csa[i] + 1) % csa.size()];
142 template <
typename t_csa>
152 return csa.isa[(csa[i] + csa.size() - 1) % csa.size()];
158 template <
typename t_csa,
bool t_direction>
214 template <
typename t_csa>
286 template <
typename t_csa,
bool t_direction>
295 return csa.wavelet_tree.select(i - csa.C[csa.char2comp[c]] + 1, c);
300 template <
typename t_csa>
308 typename t_csa::char_type c;
309 auto rc = csa.wavelet_tree.inverse_select(i);
312 return csa.C[csa.char2comp[c]] + j;
318 template <
typename t_csa,
bool t_direction>
345 assert(i < m_csa.size());
359 template <
typename t_csa>
387 return m_csa.wavelet_tree[i];
420 template <
typename t_csa>
446 auto sample = m_csa.isa_sample.sample_qeq(i);
448 if (std::get<1>(sample) < i) { i = std::get<1>(sample) + m_csa.size() - i; }
451 i = std::get<1>(sample) - i;
453 while (i--) { result = m_csa.lf[result]; }
467 template <
typename t_csa>
494 auto sample = m_csa.isa_sample.sample_leq(i);
496 i = i - std::get<1>(sample);
497 while (i--) { result = m_csa.psi[result]; }
510 template <
typename t_csa>
549 template <
typename t_csa>
A wrapper for the bwt of a compressed suffix array that is based on the function.
size_type size() const
Returns the size of the function.
value_type operator[](size_type i) const
Calculate the Burrows Wheeler Transform (BWT) at position i.
t_csa::char_type char_type
t_csa::char_type value_type
random_access_const_iterator< bwt_of_csa_psi > const_iterator
t_csa::size_type size_type
t_csa::alphabet_category alphabet_category
bwt_of_csa_psi(const t_csa &csa)
Constructor.
size_type rank(size_type i, const char_type c) const
Calculates how many symbols c are in the prefix [0..i-1].
size_type empty() const
Returns if the bwt is empty.
size_type select(size_type i, const char_type c) const
Calculates the position of the i-th c.
const_iterator end() const
Returns a const_iterator to the element after the last element.
const_iterator begin() const
Returns a const_iterator to the first element.
t_csa::difference_type difference_type
bwt_of_csa_wt(const t_csa &csa_wt)
Constructor.
size_type rank(size_type i, const char_type c) const
Calculates how many symbols c are in the prefix [0..i-1].
size_type select(size_type i, const char_type c) const
Calculates the position of the i-th c.
random_access_const_iterator< bwt_of_csa_wt > const_iterator
const t_csa::char_type value_type
size_type empty() const
Returns if the BWT function is empty.
size_type size() const
Returns the size of the BWT function.
const_iterator begin() const
Returns a const_iterator to the first element.
value_type operator[](size_type i) const
Calculate the Burrows Wheeler Transform (BWT) at position i.
t_csa::char_type char_type
t_csa::difference_type difference_type
t_csa::size_type size_type
t_csa::alphabet_category alphabet_category
const_iterator end() const
Returns a const_iterator to the element after the last element.
A class for the Compressed Suffix Array (CSA) based on a Wavelet Tree (WT) of the Burrow Wheeler Tran...
const_iterator end() const
Returns a const_iterator to the element after the last element.
random_access_const_iterator< first_row_of_csa > const_iterator
first_row_of_csa(const t_csa &csa)
Constructor.
const t_csa::char_type value_type
t_csa::size_type size_type
t_csa::alphabet_category alphabet_category
size_type empty() const
Returns if the F column is empty.
t_csa::difference_type difference_type
value_type operator[](size_type i) const
Calculate F[i].
const_iterator begin() const
Returns a const_iterator to the first element.
size_type size() const
Returns the size of the F column.
int_alphabet_tag alphabet_category
isa_of_csa_psi(const t_csa &csa_wt)
Constructor.
const_iterator begin() const
Returns a const_iterator to the first element.
size_type empty() const
Returns if the CSA is empty.
t_csa::size_type size_type
const_iterator end() const
Returns a const_iterator to the element after the last element.
size_type size() const
Returns the size of the CSA.
value_type operator[](size_type i) const
Access operator to ISA.
random_access_const_iterator< isa_of_csa_psi > const_iterator
t_csa::difference_type difference_type
t_csa::value_type value_type
size_type empty() const
Returns if the CSA is empty.
size_type size() const
Returns the size of the CSA.
t_csa::difference_type difference_type
const_iterator begin() const
Returns a const_iterator to the first element.
isa_of_csa_wt(const t_csa &csa_wt)
Constructor.
t_csa::size_type size_type
t_csa::value_type value_type
int_alphabet_tag alphabet_category
const_iterator end() const
Returns a const_iterator to the element after the last element.
value_type operator[](size_type i) const
Access operator to ISA.
random_access_const_iterator< isa_of_csa_wt > const_iterator
Generic iterator for a random access container.
value_type operator[](size_type i) const
Character at index of the original text.
size_type empty() const
Returns if text text has size 0.
t_csa::difference_type difference_type
t_csa::char_type value_type
t_csa::alphabet_category alphabet_category
text_of_csa(const t_csa &csa)
Constructor.
size_type size() const
Returns the size of the original text.
random_access_const_iterator< text_of_csa > const_iterator
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.
t_csa::size_type size_type
random_access_const_iterator< traverse_csa_psi > const_iterator
t_csa::difference_type difference_type
t_csa::size_type size_type
size_type size() const
Returns the size of the function.
const_iterator begin() const
const_iterator end() const
Returns a const_iterator to the element after the last element.
size_type empty() const
Returns if the function is empty.
value_type operator[](size_type i) const
Calculate the or value at position i.
traverse_csa_psi(const traverse_csa_psi &tcsa)
Copy constructor.
int_alphabet_tag alphabet_category
t_csa::value_type value_type
traverse_csa_psi(const t_csa &csa_psi)
Constructor.
A helper class for the function for (compressed) suffix arrays which provide also the inverse suffix...
const_iterator end() const
Returns a const_iterator to the element after the last element.
const_iterator begin() const
Returns a const_iterator to the first element.
traverse_csa_saisa(const traverse_csa_saisa &tcsa)
t_csa::size_type size_type
size_type empty() const
Returns if the function is empty.
traverse_csa_saisa(const t_csa &csa)
Constructor.
size_type size() const
Returns the size of the function.
t_csa::value_type value_type
int_alphabet_tag alphabet_category
value_type operator[](size_type i) const
Calculate the value at position i.
t_csa::difference_type difference_type
random_access_const_iterator< traverse_csa_saisa > const_iterator
A wrapper class for the and LF function for (compressed) suffix arrays that are based on a wavelet t...
value_type operator[](size_type i) const
Calculate the value at position i.
t_csa::char_type char_type
t_csa::difference_type difference_type
t_csa::size_type size_type
t_csa::value_type value_type
const_iterator end() const
Returns a const_iterator to the element after the last element.
const_iterator begin() const
Returns a const_iterator to the first element.
traverse_csa_wt(const t_csa &csa_wt)
Constructor.
size_type size() const
Returns the size of the function.
int_alphabet_tag alphabet_category
random_access_const_iterator< traverse_csa_wt > const_iterator
size_type empty() const
Returns if the function is empty.
iterators.hpp contains an generic iterator for random access containers.
int_vector ::size_type size_type
Namespace for the succinct data structure library.
t_csa::char_type first_row_symbol(const typename t_csa::size_type i, const t_csa &csa)
Get the symbol at position i in the first row of the sorted suffixes of CSA.
static value_type access(const t_csa &csa, size_type i)
t_csa::size_type size_type
t_csa::value_type value_type
t_csa::value_type value_type
t_csa::size_type size_type
static value_type access(const t_csa &csa, size_type i)
t_csa::value_type value_type
static value_type access(const t_csa &csa, size_type i)
t_csa::size_type size_type
static value_type access(const t_csa &csa, size_type i)
t_csa::value_type value_type
t_csa::size_type size_type
static value_type access(const t_csa &csa, size_type i)
t_csa::char_type char_type
t_csa::value_type value_type
t_csa::size_type size_type
t_csa::char_type char_type
t_csa::value_type value_type
t_csa::size_type size_type
static value_type access(const t_csa &csa, size_type i)