A class for the compressed version of lcp information of an suffix array proposed by Stefan Kurtz in the paper "Reducing the Space Requirement of Suffix Trees". More...

#include <lcp_kurtz.hpp>

Classes
class	type
Public Types
enum	{ fast_access = 0, text_order = 0, sa_order = 1 }
typedef int_vector< width > ::value_type	value_type
typedef random_access_const_iterator < lcp_kurtz >	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 lcp_plain_tag	lcp_category
Public Member Functions
	lcp_kurtz ()
	Default Constructor.
	~lcp_kurtz ()
	Default Destructor.
	lcp_kurtz (const lcp_kurtz &lcp_c)
	Copy constructor.
template<class Text , class Sa >
	lcp_kurtz (const Text &text, const Sa &sa)
	Constructor for the compressed lcp from a compressed suffix array.
template<uint8_t int_width, class size_type_class >
	lcp_kurtz (int_vector_file_buffer< int_width, size_type_class > &lcp_buf)
	Construct the lcp array from an int_vector_file_buffer.
template<class Text , class Sa >
void	construct (const Text &text, const Sa &sa)
template<uint8_t int_width, class size_type_class >
void	construct (int_vector_file_buffer< int_width, size_type_class > &lcp_buf)
size_type	size () const
	Number of elements in the instance.
bool	empty () const
	Returns if the data strucutre is empty.
void	swap (lcp_kurtz &lcp_c)
	Swap method for lcp_kurtz.
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_kurtz &	operator= (const lcp_kurtz &lcp_c)
	Assignment Operator.
bool	operator== (const lcp_kurtz &lcp_c) const
	Equality Operator.
bool	operator!= (const lcp_kurtz &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)
	Load from a stream.
Static Public Member Functions
static size_type	max_size ()
	Returns the largest size that lcp_kurtz can ever have.

Detailed Description

template<uint8_t width = 0>
class sdsl::lcp_kurtz< width >

A class for the compressed version of lcp information of an suffix array proposed by Stefan Kurtz in the paper "Reducing the Space Requirement of Suffix Trees".

We use 8 bit for each lcp values + $ log n $ bits for each lcp value which is greater than 254.

Time complexity

$\Order{1}$ if the value is less than 255 and
$\Order{\log n}$ ( ) otherwise.

Member Function Documentation

template<uint8_t width>

lcp_kurtz< width >::const_iterator sdsl::lcp_kurtz< width >::begin ( ) const

Returns a const_iterator to the first element.

Required for the STL Container Concept.

See also:: end

template<uint8_t width = 0>

bool sdsl::lcp_kurtz< width >::empty ( ) const [inline]

Returns if the data strucutre is empty.

Required for the Container Concept of the STL.A

See also:: size

template<uint8_t width>

lcp_kurtz< width >::const_iterator sdsl::lcp_kurtz< width >::end ( ) const

Returns a const_iterator to the element after the last element.

Required for the STL Container Concept.

See also:: begin.

template<uint8_t width>

void sdsl::lcp_kurtz< width >::load ( std::istream & in )

Load from a stream.

Parameters:

in	Inputstream to load the data structure from.

template<uint8_t width = 0>

static size_type sdsl::lcp_kurtz< width >::max_size ( ) [inline, static]

Returns the largest size that lcp_kurtz can ever have.

Required for the Container Concept of the STL.

See also:: size

template<uint8_t width>

bool sdsl::lcp_kurtz< width >::operator!= ( const lcp_kurtz< width > & lcp_c ) const

Unequality Operator.

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

Required for the Equality Comparable Concept of the STL.

See also:: operator==

template<uint8_t width>

lcp_kurtz< width > & sdsl::lcp_kurtz< width >::operator= ( const lcp_kurtz< width > & lcp_c )

Assignment Operator.

Required for the Assignable Concept of the STL.

template<uint8_t width>

bool sdsl::lcp_kurtz< width >::operator== ( const lcp_kurtz< width > & lcp_c ) const

Equality Operator.

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

Required for the Equality Comparable Concept of the STL.

See also:: operator!=

template<uint8_t width>

lcp_kurtz< width >::value_type sdsl::lcp_kurtz< width >::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<uint8_t width>

lcp_kurtz< width >::size_type sdsl::lcp_kurtz< width >::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<uint8_t width = 0>

size_type sdsl::lcp_kurtz< width >::size ( ) const [inline]

Number of elements in the instance.

Required for the Container Concept of the STL.

See also:: max_size, empty

template<uint8_t width>

void sdsl::lcp_kurtz< width >::swap ( lcp_kurtz< width > & lcp_c )

Swap method for lcp_kurtz.

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_kurtz 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_kurtz.hpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

template<uint8_t width = 0> class sdsl::lcp_kurtz< width >

Member Function Documentation

template<uint8_t width = 0>
class sdsl::lcp_kurtz< width >