8#ifndef INCLUDED_SDSL_SUFFIX_ARRAY_HELPER
9#define INCLUDED_SDSL_SUFFIX_ARRAY_HELPER
27template <
typename t_csa>
28typename t_csa::char_type
first_row_symbol(
const typename t_csa::size_type i, t_csa
const & csa)
30 assert(i < csa.size());
33 typename t_csa::size_type res = 1;
34 while (res < csa.sigma and csa.C[res] <= i)
36 return csa.comp2char[res - 1];
41 typename t_csa::size_type upper_c = csa.sigma,
43 typename t_csa::size_type res = 0;
46 res = (upper_c + lower_c) / 2;
51 else if (i >= csa.C[res + 1])
56 while (i < csa.C[res] or i >= csa.C[res + 1]);
57 return csa.comp2char[res];
62template <
typename t_csa,
bool t_direction>
74template <
typename t_csa>
84 return csa.isa[(csa[i] + csa.size() - 1) % csa.size()];
88template <
typename t_csa,
bool t_direction>
128 return m_csa.empty();
147template <
typename t_csa,
bool t_direction>
155 return csa.isa[(csa[i] + 1) % csa.size()];
160template <
typename t_csa>
170 return csa.isa[(csa[i] + csa.size() - 1) % csa.size()];
176template <
typename t_csa,
bool t_direction>
219 return m_csa,
empty();
242template <
typename t_csa>
284 return m_csa.rank_bwt(i, c);
297 return m_csa.select_bwt(i, c);
309 return m_csa.empty();
332template <
typename t_csa,
bool t_direction>
341 return csa.wavelet_tree.select(i - csa.C[csa.char2comp[c]] + 1, c);
346template <
typename t_csa>
354 typename t_csa::char_type c;
355 auto rc = csa.wavelet_tree.inverse_select(i);
358 return csa.C[csa.char2comp[c]] + j;
364template <
typename t_csa,
bool t_direction>
391 assert(i < m_csa.size());
403 return m_csa.empty();
417template <
typename t_csa>
445 return m_csa.wavelet_tree[i];
463 return m_csa.rank_bwt(i, c);
476 return m_csa.select(i, c);
482 return m_csa.empty();
496template <
typename t_csa>
522 auto sample = m_csa.isa_sample.sample_qeq(i);
524 if (std::get<1>(sample) < i)
526 i = std::get<1>(sample) + m_csa.size() - i;
530 i = std::get<1>(sample) - i;
534 result = m_csa.lf[result];
547 return m_csa.empty();
561template <
typename t_csa>
588 auto sample = m_csa.isa_sample.sample_leq(i);
590 i = i - std::get<1>(sample);
593 result = m_csa.psi[result];
605 return m_csa.empty();
619template <
typename t_csa>
655 return m_csa.empty();
669template <
typename t_csa>
710 return m_csa.empty();
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.
t_csa::alphabet_category alphabet_category
value_type operator[](size_type i) const
Calculate the Burrows Wheeler Transform (BWT) at position i.
bwt_of_csa_psi(t_csa const &csa)
Constructor.
t_csa::char_type value_type
random_access_const_iterator< bwt_of_csa_psi > const_iterator
t_csa::size_type size_type
t_csa::char_type char_type
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
t_csa::alphabet_category alphabet_category
t_csa::difference_type difference_type
bwt_of_csa_wt(t_csa const &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.
size_type empty() const
Returns if the BWT function is empty.
t_csa::size_type size_type
size_type size() const
Returns the size of the BWT function.
const_iterator begin() const
Returns a const_iterator to the first element.
random_access_const_iterator< bwt_of_csa_wt > const_iterator
const t_csa::char_type value_type
t_csa::char_type char_type
value_type operator[](size_type i) const
Calculate the Burrows Wheeler Transform (BWT) at position i.
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
const t_csa::char_type value_type
t_csa::alphabet_category alphabet_category
size_type empty() const
Returns if the F column is empty.
value_type operator[](size_type i) const
Calculate F[i].
first_row_of_csa(t_csa const &csa)
Constructor.
t_csa::size_type size_type
t_csa::difference_type difference_type
const_iterator begin() const
Returns a const_iterator to the first element.
size_type size() const
Returns the size of the F column.
random_access_const_iterator< isa_of_csa_psi > const_iterator
const_iterator begin() const
Returns a const_iterator to the first element.
int_alphabet_tag alphabet_category
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.
t_csa::difference_type difference_type
size_type size() const
Returns the size of the CSA.
isa_of_csa_psi(t_csa const &csa_wt)
Constructor.
value_type operator[](size_type i) const
Access operator to ISA.
t_csa::value_type value_type
size_type empty() const
Returns if the CSA is empty.
isa_of_csa_wt(t_csa const &csa_wt)
Constructor.
size_type size() const
Returns the size of the CSA.
random_access_const_iterator< isa_of_csa_wt > const_iterator
t_csa::value_type value_type
t_csa::difference_type difference_type
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.
value_type operator[](size_type i) const
Access operator to ISA.
t_csa::size_type size_type
int_alphabet_tag alphabet_category
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::char_type value_type
t_csa::size_type size_type
random_access_const_iterator< text_of_csa > const_iterator
size_type size() const
Returns the size of the original text.
t_csa::difference_type difference_type
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.
text_of_csa(t_csa const &csa)
Constructor.
t_csa::alphabet_category alphabet_category
t_csa::value_type value_type
random_access_const_iterator< traverse_csa_psi > const_iterator
traverse_csa_psi(t_csa const &csa_psi)
Constructor.
t_csa::difference_type difference_type
size_type size() const
Returns the size of the function.
const_iterator begin() const
t_csa::size_type size_type
int_alphabet_tag alphabet_category
traverse_csa_psi(traverse_csa_psi const &tcsa)
Copy constructor.
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.
A helper class for the function for (compressed) suffix arrays which provide also the inverse suffix...
t_csa::size_type size_type
const_iterator end() const
Returns a const_iterator to the element after the last element.
t_csa::difference_type difference_type
const_iterator begin() const
Returns a const_iterator to the first element.
size_type empty() const
Returns if the function is empty.
size_type size() const
Returns the size of the function.
traverse_csa_saisa(t_csa const &csa)
Constructor.
traverse_csa_saisa(traverse_csa_saisa const &tcsa)
random_access_const_iterator< traverse_csa_saisa > const_iterator
int_alphabet_tag alphabet_category
value_type operator[](size_type i) const
Calculate the value at position i.
t_csa::value_type value_type
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::size_type size_type
int_alphabet_tag alphabet_category
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.
size_type size() const
Returns the size of the function.
traverse_csa_wt(t_csa const &csa_wt)
Constructor.
t_csa::difference_type difference_type
t_csa::char_type char_type
random_access_const_iterator< traverse_csa_wt > const_iterator
size_type empty() const
Returns if the function is empty.
t_csa::value_type value_type
iterators.hpp contains an generic iterator for random access containers.
Namespace for the succinct data structure library.
t_csa::char_type first_row_symbol(const typename t_csa::size_type i, t_csa const &csa)
Get the symbol at position i in the first row of the sorted suffixes of CSA.
Contains declarations and definitions of data structure concepts.
static value_type access(t_csa const &csa, size_type i)
t_csa::size_type size_type
t_csa::value_type value_type
t_csa::size_type size_type
t_csa::value_type value_type
static value_type access(t_csa const &csa, size_type i)
t_csa::size_type size_type
t_csa::value_type value_type
static value_type access(t_csa const &csa, size_type i)
t_csa::size_type size_type
static value_type access(t_csa const &csa, size_type i)
t_csa::value_type value_type
t_csa::char_type char_type
t_csa::value_type value_type
t_csa::size_type size_type
static value_type access(t_csa const &csa, size_type i)
t_csa::char_type char_type
t_csa::value_type value_type
static value_type access(t_csa const &csa, size_type i)
t_csa::size_type size_type