A class for the uncmpressed suffix array (SA). More...

#include <csa_uncompressed.hpp>

Public Types
enum	{ sa_sample_dens = 1, isa_sample_dens = 1 }
typedef uint64_t	value_type
typedef random_access_const_iterator < csa_uncompressed >	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 psi_of_sa_and_isa < csa_uncompressed >	psi_type
typedef bwt_of_csa_psi < csa_uncompressed >	bwt_type
typedef const unsigned char *	pattern_type
typedef unsigned char	char_type
typedef int_vector	sa_sample_type
typedef int_vector	isa_sample_type
typedef csa_tag	index_category
Public Member Functions
	csa_uncompressed ()
	Default Constructor.
	~csa_uncompressed ()
	Default Destructor.
	csa_uncompressed (const csa_uncompressed &csa)
	Copy constructor.
template<typename RandomAccessContainer >
	csa_uncompressed (const RandomAccessContainer &sa, const unsigned char *str)
	Construct csa_uncompressed from another compressed or uncompressed suffix array.
	csa_uncompressed (const unsigned char *str)
	Constructor for the CSA taking a string for that the CSA should be calculated.
template<uint8_t int_width, class size_type_class , class size_type_class_1 >
	csa_uncompressed (int_vector_file_buffer< 8, size_type_class > &text_buf, int_vector_file_buffer< int_width, size_type_class_1 > &sa_buf)
	Construct the csa_uncompressed form a int_vector_file_buffer for the text and the SA.
	csa_uncompressed (tMSS &file_map, const std::string &dir, const std::string &id)
void	construct (tMSS &file_map, const std::string &dir, const std::string &id)
size_type	size () const
	Number of elements in the instance.
bool	empty () const
	Returns if the data strucutre is empty.
void	swap (csa_uncompressed &csa)
	Swap method for csa_uncompressed.
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
value_type	operator() (size_type i) const
	()-operator return inverse suffix array values
csa_uncompressed &	operator= (const csa_uncompressed &csa)
	Assignment Operator.
bool	operator== (const csa_uncompressed &csa) const
	Equality Operator.
bool	operator!= (const csa_uncompressed &csa) const
	Unequality Operator.
size_type	serialize (std::ostream &out) const
	Serialize to a stream.
void	load (std::istream &in)
	Load from a stream.
size_type	get_sample_dens () const
size_type	rank_bwt (size_type i, const unsigned char c) const
	Calculates how many symbols c are in the prefix [0..i-1] of the BWT of the original text.
size_type	select_bwt (size_type i, const unsigned char c) const
	Calculates the ith occurence of symbol c in the BWT of the original text.
Static Public Member Functions
static size_type	max_size ()
	Returns the largest size that csa_uncompressed can ever have.
Public Attributes
const int_vector< 8 > &	char2comp
const int_vector< 8 > &	comp2char
const int_vector< 64 > &	C
const uint16_t &	sigma
const psi_type &	psi
const bwt_type &	bwt
const sa_sample_type &	sa_sample
const isa_sample_type &	isa_sample
Friends
class	psi_of_sa_and_isa< csa_uncompressed >
class	bwt_of_csa_psi< csa_uncompressed >

Detailed Description

A class for the uncmpressed suffix array (SA).

This class stores the information of the suffix array and the inverse suffix array in uncompressed form. In contrast to this class, classes like sdsl::csa_sada_theo, sdsl::csa_sada, and sdsl::csa_wt store the suffix array and inverse suffix array data in compressed form.

The interface of this class is exactly the same as for the compressed indexes. This is the reason why it is in the group of compressed suffix arrays.

Space complexity: $2n\cdot \log n$ bits, where equals the of the suffix array.

Member Function Documentation

const_iterator sdsl::csa_uncompressed::begin ( ) const

Returns a const_iterator to the first element.

Required for the STL Container Concept.

See also:: end

bool sdsl::csa_uncompressed::empty ( ) const [inline]

Returns if the data strucutre is empty.

Required for the Container Concept of the STL.A

See also:: size

const_iterator sdsl::csa_uncompressed::end ( ) const

Returns a const_iterator to the element after the last element.

Required for the STL Container Concept.

See also:: begin.

void sdsl::csa_uncompressed::load ( std::istream & in )

Load from a stream.

Parameters:

in	Inputstream to load the data structure from.

static size_type sdsl::csa_uncompressed::max_size ( ) [inline, static]

Returns the largest size that csa_uncompressed can ever have.

Required for the Container Concept of the STL.

See also:: size

bool sdsl::csa_uncompressed::operator!= ( const csa_uncompressed & csa ) const

Unequality Operator.

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

Required for the Equality Comparable Concept of the STL.

See also:: operator==

value_type sdsl::csa_uncompressed::operator() ( size_type i ) const [inline]

()-operator return inverse suffix array values

Parameters:

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

csa_uncompressed& sdsl::csa_uncompressed::operator= ( const csa_uncompressed & csa )

Assignment Operator.

Required for the Assignable Concept of the STL.

bool sdsl::csa_uncompressed::operator== ( const csa_uncompressed & csa ) const

Equality Operator.

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

Required for the Equality Comparable Concept of the STL.

See also:: operator!=

value_type sdsl::csa_uncompressed::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.

size_type sdsl::csa_uncompressed::rank_bwt	(	size_type	i,
		const unsigned char	c
	)		const

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

Parameters:

i	The exclusive index of the prefix range [0..i-1], so $i\in [0..size()]$ .
c	The symbol to count the occurences in the prefix.

Returns:: The number of occurences of symbol c in the prefix [0..i-1] of the BWT.

Time complexity: $\Order{\log n}$

size_type sdsl::csa_uncompressed::select_bwt	(	size_type	i,
		const unsigned char	c
	)		const

Calculates the ith occurence of symbol c in the BWT of the original text.

Parameters:

i	The ith occurence. $i\in [1..rank(size(),c)]$ .
c	The symbol c.

Returns:: The ith occurence symbol c in the the BWT or size() if no ith occurence of the symbol exists in the BWT.

Time complexity: $\Order{t_{\Psi}}$

size_type sdsl::csa_uncompressed::serialize ( std::ostream & out ) const

Serialize to a stream.

Parameters:

out	Outstream to write the data structure.

Returns:: The number of written bytes.

size_type sdsl::csa_uncompressed::size ( ) const [inline]

Number of elements in the instance.

Required for the Container Concept of the STL.

See also:: max_size, empty

void sdsl::csa_uncompressed::swap ( csa_uncompressed & csa )

Swap method for csa_uncompressed.

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

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Friends

Detailed Description

Member Function Documentation