A class for the compressed version of lcp information of an suffix array of class Csa proposed by Sadakane in the paper "Succinct Representation of lcp Information and Improvements in the Compressed Suffix Arrays". More...

#include <lcp_support_sada.hpp>

Classes
class	type
Public Types
enum	{ fast_access = 0, text_order = 1, sa_order = 0 }
typedef Csa::value_type	value_type
typedef random_access_const_iterator < _lcp_support_sada >	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 ptrdiff_t	difference_type
typedef BitVector	bit_vector_type
typedef Csa	csa_type
typedef lcp_permuted_tag	lcp_category
Public Member Functions
	_lcp_support_sada ()
	Default Constructor.
	~_lcp_support_sada ()
	Default Destructor.
	_lcp_support_sada (const _lcp_support_sada &lcp_c)
	Copy constructor.
template<class Text , class Sa >
	_lcp_support_sada (const Text &text, const Sa &sa, const Csa *csa)
	Constructor for the compressed lcp from a suffix array and a text.
template<uint8_t int_width, class size_type_class , uint8_t int_width_1, class size_type_class_1 >
	_lcp_support_sada (int_vector_file_buffer< int_width, size_type_class > &lcp_buf, int_vector_file_buffer< int_width_1, size_type_class_1 > &isa_buf, const Csa *f_csa)
	Construct the lcp array from an lcp array and an int_vector_file_buffer of the inverse suffix array.
template<class Text , class Sa >
void	construct (const Text &text, const Sa &sa, const Csa *csa)
template<uint8_t int_width, class size_type_class , uint8_t int_width_1, class size_type_class_1 >
void	construct (int_vector_file_buffer< int_width, size_type_class > &lcp_buf, int_vector_file_buffer< int_width_1, size_type_class_1 > &isa_buf, const Csa *f_csa)
void	set_csa (const Csa *f_csa)
size_type	size () const
	Number of elements in the instance.
bool	empty () const
	Returns if the data strucutre is empty.
void	swap (_lcp_support_sada &lcp_c)
	Swap method for _lcp_support_sada.
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
_lcp_support_sada &	operator= (const _lcp_support_sada &lcp_c)
	Assignment Operator.
bool	operator== (const _lcp_support_sada &lcp_c) const
	Equality Operator.
bool	operator!= (const _lcp_support_sada &lcp_c) const
	Unequality Operator.
size_type	serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="") const
	Serialize to a stream.
void	load (std::istream &in, const Csa *csa)
	Load from a stream.
Static Public Member Functions
static size_type	max_size ()
	Returns the largest size that _lcp_support_sada can ever have.
Public Attributes
const Csa *&	csa

Detailed Description

template<class Csa = csa_sada<>, class BitVector = bit_vector, class SelectSupport = typename BitVector::select_1_type>
class sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >

A class for the compressed version of lcp information of an suffix array of class Csa proposed by Sadakane in the paper "Succinct Representation of lcp Information and Improvements in the Compressed Suffix Arrays".

The class has two template parameters:

Csa is the (compressed) suffix array for which the lcp information should by provided.
SelectSupport is the SelectSupport class which is used in the data structure to calculate the select queries.

Space complexity
bits, where 2n is the maximal size of the bitvector for the differences of the PLCP array and o(n) for the select support data structure.

The representation of the lcp information corresponds to the concept of an immutable random access container of the STL.

Member Function Documentation

template<class Csa , class BitVector , class SelectSupport >

_lcp_support_sada< Csa, BitVector, SelectSupport >::const_iterator sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >::begin ( ) const

Returns a const_iterator to the first element.

Required for the STL Container Concept.

See also:: end

template<class Csa = csa_sada<>, class BitVector = bit_vector, class SelectSupport = typename BitVector::select_1_type>

bool sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >::empty ( ) const [inline]

Returns if the data strucutre is empty.

Required for the Container Concept of the STL.A

See also:: size

template<class Csa , class BitVector , class SelectSupport >

_lcp_support_sada< Csa, BitVector, SelectSupport >::const_iterator sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >::end ( ) const

Returns a const_iterator to the element after the last element.

Required for the STL Container Concept.

See also:: begin.

template<class Csa, class BitVector , class SelectSupport >

void sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >::load	(	std::istream &	in,
		const Csa *	csa
	)

Load from a stream.

Parameters:

in	Inputstream to load the data structure from.
csa	Compressed Suffix Array that is supported.

template<class Csa = csa_sada<>, class BitVector = bit_vector, class SelectSupport = typename BitVector::select_1_type>

static size_type sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >::max_size ( ) [inline, static]

Returns the largest size that _lcp_support_sada can ever have.

Required for the Container Concept of the STL.

See also:: size

template<class Csa , class BitVector , class SelectSupport >

bool sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >::operator!= ( const _lcp_support_sada< Csa, BitVector, SelectSupport > & lcp_c ) const

Unequality Operator.

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

Required for the Equality Comparable Concept of the STL.

See also:: operator==

template<class Csa , class BitVector , class SelectSupport >

_lcp_support_sada< Csa, BitVector, SelectSupport > & sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >::operator= ( const _lcp_support_sada< Csa, BitVector, SelectSupport > & lcp_c )

Assignment Operator.

Required for the Assignable Concept of the STL.

template<class Csa , class BitVector , class SelectSupport >

bool sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >::operator== ( const _lcp_support_sada< Csa, BitVector, SelectSupport > & lcp_c ) const

Equality Operator.

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

Required for the Equality Comparable Concept of the STL.

See also:: operator!=

template<class Csa , class BitVector , class SelectSupport >

_lcp_support_sada< Csa, BitVector, SelectSupport >::value_type sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >::operator[] ( size_type i ) const [inline]

[]-operator

Parameters:

i	Index of the value. $i \in [0..size()-1]$ . Time complexity: O(suffix array access) Required for the STL Random Access Container Concept.

template<class Csa , class BitVector , class SelectSupport >

_lcp_support_sada< Csa, BitVector, SelectSupport >::size_type sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >::serialize	(	std::ostream &	out,
		structure_tree_node *	v = `NULL`,
		std::string	name = `""`
	)		const

Serialize to a stream.

Parameters:

out	Outstream to write the data structure.

Returns:: The number of written bytes.

template<class Csa = csa_sada<>, class BitVector = bit_vector, class SelectSupport = typename BitVector::select_1_type>

size_type sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >::size ( ) const [inline]

Number of elements in the instance.

Required for the Container Concept of the STL.

See also:: max_size, empty

template<class Csa , class BitVector , class SelectSupport >

void sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >::swap ( _lcp_support_sada< Csa, BitVector, SelectSupport > & lcp_c )

Swap method for _lcp_support_sada.

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:

lcp_c _lcp_support_sada to swap.

Required for the Assignable Conecpt of the STL.

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

sdsl/include/sdsl/lcp_support_sada.hpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Detailed Description

template<class Csa = csa_sada<>, class BitVector = bit_vector, class SelectSupport = typename BitVector::select_1_type> class sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >

Member Function Documentation

template<class Csa = csa_sada<>, class BitVector = bit_vector, class SelectSupport = typename BitVector::select_1_type>
class sdsl::_lcp_support_sada< Csa, BitVector, SelectSupport >