A wrapper class for the $\Psi$ and LF function for (compressed) suffix arrays that are based on a wavelet tree (like sdsl::csa_wt). More...

#include <csa_wt.hpp>

Public Types
typedef CsaWT::value_type	value_type
typedef CsaWT::size_type	size_type
typedef CsaWT::char_type	char_type
typedef CsaWT::difference_type	difference_type
typedef random_access_const_iterator < psi_of_csa_wt >	const_iterator
Public Member Functions
	psi_of_csa_wt (CsaWT *csa_wt=NULL)
	Constructor.
	psi_of_csa_wt (const psi_of_csa_wt &psi_of_csa)
	Copy constructor.
value_type	operator[] (size_type i) const
	Calculate the $\Psi$ value at position i.
value_type	psi_k (size_type i, size_type k) const
	Apply $\Psi$ k times to the value at position i.
value_type	operator() (size_type i) const
	Calculate the LF mapping at position i.
value_type	lf_k (size_type i, size_type k) const
	Apply LF k times to the value at position i.
psi_of_csa_wt &	operator= (const psi_of_csa_wt &psi_of_csa)
	Assignment operator.
bool	operator== (const psi_of_csa_wt &psi)
	Equality operator.
size_type	size () const
	Returns the size of the $\Psi$ function.
size_type	empty () const
	Returns if the $\Psi$ function is empty.
void	swap (psi_of_csa_wt &psi_of_csa)
	Swap operation require by the STL.
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.
uint32_t	get_sample_dens () const

Detailed Description

template<class CsaWT>
class sdsl::psi_of_csa_wt< CsaWT >

A wrapper class for the $\Psi$ and LF function for (compressed) suffix arrays that are based on a wavelet tree (like sdsl::csa_wt).

Member Function Documentation

template<class CsaWT>

const_iterator sdsl::psi_of_csa_wt< CsaWT >::begin ( ) const [inline]

Returns a const_iterator to the first element.

Required for the STL Container Concept.

See also:: end

template<class CsaWT>

const_iterator sdsl::psi_of_csa_wt< CsaWT >::end ( ) const [inline]

Returns a const_iterator to the element after the last element.

Required for the STL Container Concept.

See also:: begin.

template<class CsaWT>

value_type sdsl::psi_of_csa_wt< CsaWT >::lf_k	(	size_type	i,
		size_type	k
	)		const `[inline]`

Apply LF k times to the value at position i.

   \param i The index for which LF should be applied k times, \form#105.

Parameters:

k	Number of times LF should be applied

Time complexity: $\Order{\min\{k\cdot \log |\Sigma|, (s_{\SUF}+s_{\ISA})\log|\Sigma|\}}$

template<class CsaWT>

value_type sdsl::psi_of_csa_wt< CsaWT >::operator() ( size_type i ) const [inline]

Calculate the LF mapping at position i.

The LF mapping function is the inverse to the $\Psi$ function. That is $LF[\Psi(i)]=i$ .

Parameters:

i	The index for which the LF value should be calculated, $i\in [0..size()-1]$ .

Time complexity: $\Order{\log |\Sigma|}$

template<class CsaWT>

bool sdsl::psi_of_csa_wt< CsaWT >::operator== ( const psi_of_csa_wt< CsaWT > & psi ) [inline]

Equality operator.

return Always true, since all wrapper objects are equal only the reference to the supported csa differs.

template<class CsaWT>

value_type sdsl::psi_of_csa_wt< CsaWT >::operator[] ( size_type i ) const [inline]

Calculate the $\Psi$ value at position i.

   \param i The index for which the \form#6 value should be calculated, \form#105.
   \par Time complexity

$\Order{\log |\Sigma|}$

template<class CsaWT>

value_type sdsl::psi_of_csa_wt< CsaWT >::psi_k	(	size_type	i,
		size_type	k
	)		const `[inline]`

Apply $\Psi$ k times to the value at position i.

   \param i The index for which \form#6 should be applied k times, \form#105.

Parameters:

k	Number of times $\Psi$ should be applied

Time complexity: $\Order{\min\{k\cdot \log |\Sigma|, (s_{\SUF}+s_{\ISA})\log|\Sigma|\}}$

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

sdsl/include/sdsl/csa_wt.hpp

Public Types

Public Member Functions

Detailed Description

template<class CsaWT> class sdsl::psi_of_csa_wt< CsaWT >

Member Function Documentation

template<class CsaWT>
class sdsl::psi_of_csa_wt< CsaWT >