SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
Public Types | Public Member Functions | List of all members
sdsl::bwt_of_csa_psi< t_csa > Class Template Reference

A wrapper for the bwt of a compressed suffix array that is based on the $\psi$ function. More...

#include <suffix_array_helper.hpp>

Public Types

typedef t_csa::char_type value_type
 
typedef t_csa::size_type size_type
 
typedef t_csa::char_type char_type
 
typedef t_csa::difference_type difference_type
 
typedef random_access_const_iterator< bwt_of_csa_psi > const_iterator
 
typedef csa_member_tag category
 
typedef t_csa::alphabet_category alphabet_category
 

Public Member Functions

 bwt_of_csa_psi (t_csa const &csa)
 Constructor.
 
value_type operator[] (size_type i) const
 Calculate the Burrows Wheeler Transform (BWT) at position i.
 
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 size () const
 Returns the size of the $\Psi$ function.
 
size_type empty () const
 Returns if the bwt is empty.
 
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.
 

Detailed Description

template<typename t_csa>
class sdsl::bwt_of_csa_psi< t_csa >

A wrapper for the bwt of a compressed suffix array that is based on the $\psi$ function.

Definition at line 243 of file suffix_array_helper.hpp.

Member Typedef Documentation

◆ alphabet_category

template<typename t_csa>
typedef t_csa::alphabet_category sdsl::bwt_of_csa_psi< t_csa >::alphabet_category

Definition at line 252 of file suffix_array_helper.hpp.

◆ category

template<typename t_csa>
typedef csa_member_tag sdsl::bwt_of_csa_psi< t_csa >::category

Definition at line 251 of file suffix_array_helper.hpp.

◆ char_type

template<typename t_csa>
typedef t_csa::char_type sdsl::bwt_of_csa_psi< t_csa >::char_type

Definition at line 248 of file suffix_array_helper.hpp.

◆ const_iterator

template<typename t_csa>
typedef random_access_const_iterator<bwt_of_csa_psi> sdsl::bwt_of_csa_psi< t_csa >::const_iterator

Definition at line 250 of file suffix_array_helper.hpp.

◆ difference_type

template<typename t_csa>
typedef t_csa::difference_type sdsl::bwt_of_csa_psi< t_csa >::difference_type

Definition at line 249 of file suffix_array_helper.hpp.

◆ size_type

template<typename t_csa>
typedef t_csa::size_type sdsl::bwt_of_csa_psi< t_csa >::size_type

Definition at line 247 of file suffix_array_helper.hpp.

◆ value_type

template<typename t_csa>
typedef t_csa::char_type sdsl::bwt_of_csa_psi< t_csa >::value_type

Definition at line 246 of file suffix_array_helper.hpp.

Constructor & Destructor Documentation

◆ bwt_of_csa_psi()

template<typename t_csa>
sdsl::bwt_of_csa_psi< t_csa >::bwt_of_csa_psi ( t_csa const & csa)
inline

Constructor.

Definition at line 259 of file suffix_array_helper.hpp.

Member Function Documentation

◆ begin()

template<typename t_csa>
const_iterator sdsl::bwt_of_csa_psi< t_csa >::begin ( ) const
inline

Returns a const_iterator to the first element.

Required for the STL Container Concept.

See also
end

Definition at line 316 of file suffix_array_helper.hpp.

◆ empty()

template<typename t_csa>
size_type sdsl::bwt_of_csa_psi< t_csa >::empty ( ) const
inline

Returns if the bwt is empty.

Definition at line 307 of file suffix_array_helper.hpp.

◆ end()

template<typename t_csa>
const_iterator sdsl::bwt_of_csa_psi< t_csa >::end ( ) const
inline

Returns a const_iterator to the element after the last element.

Required for the STL Container Concept.

See also
begin.

Definition at line 325 of file suffix_array_helper.hpp.

◆ operator[]()

template<typename t_csa>
value_type sdsl::bwt_of_csa_psi< t_csa >::operator[] ( size_type i) const
inline

Calculate the Burrows Wheeler Transform (BWT) at position i.

Parameters
iThe index for which the BWT value should be calculated, $i\in [0..size()-1]$.
Time complexity
$ \Order{\log |\Sigma|} $

Definition at line 267 of file suffix_array_helper.hpp.

◆ rank()

template<typename t_csa>
size_type sdsl::bwt_of_csa_psi< t_csa >::rank ( size_type i,
const char_type c ) const
inline

Calculates how many symbols c are in the prefix [0..i-1].

Parameters
iThe exclusive index of the prefix range [0..i-1], so $i\in [0..size()]$.
cThe symbol to count the occurrences in the prefix.
Returns
The number of occurrences of symbol c in the prefix [0..i-1].
Time complexity
$ \Order{\log n t_{\Psi}} $

Definition at line 282 of file suffix_array_helper.hpp.

◆ select()

template<typename t_csa>
size_type sdsl::bwt_of_csa_psi< t_csa >::select ( size_type i,
const char_type c ) const
inline

Calculates the position of the i-th c.

Parameters
iThe i-th occurrence. $i\in [1..rank(size(),c)]$.
cSymbol c.
Returns
The position of the i-th c or size() if c does occur less then i times.
Time complexity
$ \Order{t_{\Psi}} $

Definition at line 295 of file suffix_array_helper.hpp.

◆ size()

template<typename t_csa>
size_type sdsl::bwt_of_csa_psi< t_csa >::size ( ) const
inline

Returns the size of the $\Psi$ function.

Definition at line 301 of file suffix_array_helper.hpp.

The documentation for this class was generated from the following file: