A class for the Compressed Suffix Array (CSA) proposed by Sadakane. csa_sada_theo is the one to one implementation of Sadakane's theoretical description with our data structures. More...

#include <csa_sada_theo.hpp>

Public Types
typedef uint64_t	value_type
typedef random_access_const_iterator < csa_sada_theo >	const_iterator
typedef const_iterator	iterator
typedef const value_type	const_reference
typedef const_reference	reference
typedef const_reference *	pointer
typedef const pointer	const_pointer
typedef int_vector::size_type	size_type
typedef size_type	csa_size_type
typedef ptrdiff_t	difference_type
typedef const unsigned char *	pattern_type
Public Member Functions
	csa_sada_theo ()
	Default Constructor.
	csa_sada_theo (const csa_sada_theo< EncVector, RankSupport > &csa)
	Copy constructor.
template<typename RandomAccessContainer >
	csa_sada_theo (const RandomAccessContainer &sa, const unsigned char *str)
	Constructor for the CSA taking an already calculated suffix array sa.
	csa_sada_theo (const unsigned char *str)
	Constructor for the CSA taking a string for that the CSA should be calculated.
	~csa_sada_theo ()
	Default destructor.
size_type	size () const
	Number of elements in the instance.
bool	empty () const
	Returns if the CSA is empty.
void	swap (csa_sada_theo< EncVector, RankSupport > &csa)
	Swap method for csa_sada_theo.
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
	[]-operator
csa_sada_theo &	operator= (const csa_sada_theo &csa)
	Assignment Operator.
bool	operator== (const csa_sada_theo &csa) const
	Equality Operator.
bool	operator!= (const csa_sada_theo &csa) const
	Unequality Operator.
size_type	serialize (std::ostream &out) const
	Serialize the SDSCompressedSuffixArray to a stream.
void	load (std::istream &in)
	Load SDSCompressedSuffixArray from a stream.
Static Public Member Functions
static size_type	max_size ()
	Returns the largest size that csa_sada_theo can ever have.
Public Attributes
const uint16_t *	char2comp
const unsigned char *	comp2char
const size_type *	C

Detailed Description

template<class EncVector = enc_vector<>, class RankSupport = rank_support_v<>>
class sdsl::csa_sada_theo< EncVector, RankSupport >

A class for the Compressed Suffix Array (CSA) proposed by Sadakane. csa_sada_theo is the one to one implementation of Sadakane's theoretical description with our data structures.

The CSA is parameterized with an enc_vector and a rank_support. The enc_vector holds the $\Psi$ -functions and rank_support helps navigating at the different levels of the data structure. Sadakane proposed to use $O(\log\log n)$ levels to achive the desired space complexity of the data structure.

See also:: csa_sada

Constructor & Destructor Documentation

template<class EncVector , class RankSupport >

template<typename RandomAccessContainer >

sdsl::csa_sada_theo< EncVector, RankSupport >::csa_sada_theo	(	const RandomAccessContainer &	sa,
		const unsigned char *	str
	)

Constructor for the CSA taking an already calculated suffix array sa.

Parameters:

sa	A Container containing an already calculated suffix array.
str	String for which sa is a suffix array.

Member Function Documentation

template<class EncVector , class RankSupport >

csa_sada_theo< EncVector, RankSupport >::const_iterator sdsl::csa_sada_theo< EncVector, RankSupport >::begin ( ) const

Returns a const_iterator to the first element.

Required for the STL Container Concept.

See also:: end

template<class EncVector = enc_vector<>, class RankSupport = rank_support_v<>>

bool sdsl::csa_sada_theo< EncVector, RankSupport >::empty ( ) const [inline]

Returns if the CSA is empty.

Required for the Container Concept of the STL.

template<class EncVector , class RankSupport >

csa_sada_theo< EncVector, RankSupport >::const_iterator sdsl::csa_sada_theo< EncVector, RankSupport >::end ( ) const

Returns a const_iterator to the element after the last element.

Required for the STL Container Concept.

See also:: begin.

template<class EncVector = enc_vector<>, class RankSupport = rank_support_v<>>

static size_type sdsl::csa_sada_theo< EncVector, RankSupport >::max_size ( ) [inline, static]

Returns the largest size that csa_sada_theo can ever have.

Required for the Container Concept of the STL.

See also:: size

template<class EncVector , class RankSupport >

bool sdsl::csa_sada_theo< EncVector, RankSupport >::operator!= ( const csa_sada_theo< EncVector, RankSupport > & csa ) const

Unequality Operator.

Two Instances of csa_sada_theo are equal if not all their members are equal.

Required for the Equality Comparable Concept of the STL.

See also:: operator==

template<class EncVector , class RankSupport >

csa_sada_theo< EncVector, RankSupport > & sdsl::csa_sada_theo< EncVector, RankSupport >::operator= ( const csa_sada_theo< EncVector, RankSupport > & csa )

Assignment Operator.

Required for the Assignable Concept of the STL.

template<class EncVector , class RankSupport >

bool sdsl::csa_sada_theo< EncVector, RankSupport >::operator== ( const csa_sada_theo< EncVector, RankSupport > & csa ) const

Equality Operator.

Two Instances of csa_sada_theo are equal if all their members are equal.

Required for the Equality Comparable Concept of the STL.

See also:: operator!=

template<class EncVector , class RankSupport >

csa_sada_theo< EncVector, RankSupport >::value_type sdsl::csa_sada_theo< EncVector, RankSupport >::operator[] ( size_type i ) const [inline]

[]-operator

Parameters:

i	Index of the value. $i \in [0..size()-1]$ .

Required for the STL Random Access Container Concept.

template<class EncVector , class RankSupport >

csa_sada_theo< EncVector, RankSupport >::size_type sdsl::csa_sada_theo< EncVector, RankSupport >::serialize ( std::ostream & out ) const

Serialize the SDSCompressedSuffixArray to a stream.

Parameters:

out	Outstream to write the data structure.

Returns:: The number of written bytes.

template<class EncVector = enc_vector<>, class RankSupport = rank_support_v<>>

size_type sdsl::csa_sada_theo< EncVector, RankSupport >::size ( ) const [inline]

Number of elements in the instance.

Required for the Container Concept of the STL.

See also:: max_size

template<class EncVector, class RankSupport>

void sdsl::csa_sada_theo< EncVector, RankSupport >::swap ( csa_sada_theo< EncVector, RankSupport > & csa )

Swap method for csa_sada_theo.

The swap method can be defined in terms of assignment. This requires three assignments, each of which, for a container type, is linear in the container's size. In a sense, then, a.swap(b) is redundant. This implementation guaranties a run-time complexity that is constant rather than linear.

Parameters:

csa	csa_sada_theo to swap.

Required for the Assignable Conecpt of the STL.

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

sdsl/include/sdsl/csa_sada_theo.hpp

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Detailed Description

template<class EncVector = enc_vector<>, class RankSupport = rank_support_v<>> class sdsl::csa_sada_theo< EncVector, RankSupport >

Constructor & Destructor Documentation

Member Function Documentation

template<class EncVector = enc_vector<>, class RankSupport = rank_support_v<>>
class sdsl::csa_sada_theo< EncVector, RankSupport >