SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::csa_bitcompressed< t_alphabet_strat > Class Template Reference

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

#include <csa_bitcompressed.hpp>

Public Types

enum  { sa_sample_dens = 1 , isa_sample_dens = 1 }
 
typedef uint64_t value_type
 
typedef random_access_const_iterator< csa_bitcompressedconst_iterator
 
typedef const_iterator iterator
 
typedef const value_type const_reference
 
typedef const_reference reference
 
typedef const_referencepointer
 
typedef const pointer const_pointer
 
typedef int_vector ::size_type size_type
 
typedef size_type csa_size_type
 
typedef ptrdiff_t difference_type
 
typedef traverse_csa_saisa< csa_bitcompressed, true > psi_type
 
typedef traverse_csa_saisa< csa_bitcompressed, false > lf_type
 
typedef bwt_of_csa_psi< csa_bitcompressedbwt_type
 
typedef text_of_csa< csa_bitcompressedtext_type
 
typedef first_row_of_csa< csa_bitcompressedfirst_row_type
 
typedef _sa_order_sampling< csa_bitcompressed, 0 > sa_sample_type
 
typedef _isa_sampling< csa_bitcompressed, 0 > isa_sample_type
 
typedef isa_sample_type isa_type
 
typedef t_alphabet_strat alphabet_type
 
typedef alphabet_type::char_type char_type
 
typedef alphabet_type::comp_char_type comp_char_type
 
typedef alphabet_type::string_type string_type
 
typedef alphabet_type::alphabet_category alphabet_category
 
typedef csa_bitcompressed csa_type
 
typedef csa_tag index_category
 
typedef psi_tag extract_category
 

Public Member Functions

 csa_bitcompressed ()
 Default constructor.
 
 csa_bitcompressed (const csa_bitcompressed &csa)
 Copy constructor.
 
 csa_bitcompressed (csa_bitcompressed &&csa)
 Move constructor.
 
 csa_bitcompressed (cache_config &config)
 Constructor.
 
size_type size () const
 Number of elements in the instance.
 
bool empty () const
 Returns if the data structure is empty.
 
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_bitcompressedoperator= (const csa_bitcompressed &csa)
 Assignment Operator.
 
csa_bitcompressedoperator= (csa_bitcompressed &&csa)
 Assignment Move Operator.
 
bool operator== (csa_bitcompressed const &other) const noexcept
 Equality operator.
 
bool operator!= (csa_bitcompressed const &other) const noexcept
 Inequality operator.
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serialize to a stream.
 
void load (std::istream &in)
 
template<typename archive_t >
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 
size_type get_sample_dens () const
 

Static Public Member Functions

static size_type max_size ()
 Returns the largest size that csa_bitcompressed can ever have.
 

Public Attributes

const alphabet_type::char2comp_type & char2comp = m_alphabet.char2comp
 
const alphabet_type::comp2char_type & comp2char = m_alphabet.comp2char
 
const alphabet_type::C_type & C = m_alphabet.C
 
const alphabet_type::sigma_type & sigma = m_alphabet.sigma
 
const psi_type psi = psi_type(*this)
 
const lf_type lf = lf_type(*this)
 
const bwt_type bwt = bwt_type(*this)
 
const bwt_type L = bwt_type(*this)
 
const isa_typeisa = m_isa
 
const first_row_type F = first_row_type(*this)
 
const text_type text = text_type(*this)
 
const sa_sample_typesa_sample = m_sa
 
const isa_sample_typeisa_sample = m_isa
 

Friends

class bwt_of_csa_psi< csa_bitcompressed >
 

Detailed Description

template<class t_alphabet_strat = byte_alphabet>
class sdsl::csa_bitcompressed< t_alphabet_strat >

A class for the uncompressed 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, 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.

Template Parameters
t_alphabet_stratPolicy for alphabet representation.
Space complexity
$ 2n\cdot \log n$ bits, where $n$ equals the $size()$ of the suffix array.
See also
sdsl::csa_sada, sdsl::csa_wt

Definition at line 45 of file csa_bitcompressed.hpp.

Member Typedef Documentation

◆ alphabet_category

template<class t_alphabet_strat = byte_alphabet>
typedef alphabet_type::alphabet_category sdsl::csa_bitcompressed< t_alphabet_strat >::alphabet_category

Definition at line 72 of file csa_bitcompressed.hpp.

◆ alphabet_type

template<class t_alphabet_strat = byte_alphabet>
typedef t_alphabet_strat sdsl::csa_bitcompressed< t_alphabet_strat >::alphabet_type

Definition at line 68 of file csa_bitcompressed.hpp.

◆ bwt_type

template<class t_alphabet_strat = byte_alphabet>
typedef bwt_of_csa_psi<csa_bitcompressed> sdsl::csa_bitcompressed< t_alphabet_strat >::bwt_type

Definition at line 62 of file csa_bitcompressed.hpp.

◆ char_type

template<class t_alphabet_strat = byte_alphabet>
typedef alphabet_type::char_type sdsl::csa_bitcompressed< t_alphabet_strat >::char_type

Definition at line 69 of file csa_bitcompressed.hpp.

◆ comp_char_type

template<class t_alphabet_strat = byte_alphabet>
typedef alphabet_type::comp_char_type sdsl::csa_bitcompressed< t_alphabet_strat >::comp_char_type

Definition at line 70 of file csa_bitcompressed.hpp.

◆ const_iterator

template<class t_alphabet_strat = byte_alphabet>
typedef random_access_const_iterator<csa_bitcompressed> sdsl::csa_bitcompressed< t_alphabet_strat >::const_iterator

Definition at line 51 of file csa_bitcompressed.hpp.

◆ const_pointer

template<class t_alphabet_strat = byte_alphabet>
typedef const pointer sdsl::csa_bitcompressed< t_alphabet_strat >::const_pointer

Definition at line 56 of file csa_bitcompressed.hpp.

◆ const_reference

template<class t_alphabet_strat = byte_alphabet>
typedef const value_type sdsl::csa_bitcompressed< t_alphabet_strat >::const_reference

Definition at line 53 of file csa_bitcompressed.hpp.

◆ csa_size_type

template<class t_alphabet_strat = byte_alphabet>
typedef size_type sdsl::csa_bitcompressed< t_alphabet_strat >::csa_size_type

Definition at line 58 of file csa_bitcompressed.hpp.

◆ csa_type

template<class t_alphabet_strat = byte_alphabet>
typedef csa_bitcompressed sdsl::csa_bitcompressed< t_alphabet_strat >::csa_type

Definition at line 73 of file csa_bitcompressed.hpp.

◆ difference_type

template<class t_alphabet_strat = byte_alphabet>
typedef ptrdiff_t sdsl::csa_bitcompressed< t_alphabet_strat >::difference_type

Definition at line 59 of file csa_bitcompressed.hpp.

◆ extract_category

template<class t_alphabet_strat = byte_alphabet>
typedef psi_tag sdsl::csa_bitcompressed< t_alphabet_strat >::extract_category

Definition at line 76 of file csa_bitcompressed.hpp.

◆ first_row_type

template<class t_alphabet_strat = byte_alphabet>
typedef first_row_of_csa<csa_bitcompressed> sdsl::csa_bitcompressed< t_alphabet_strat >::first_row_type

Definition at line 64 of file csa_bitcompressed.hpp.

◆ index_category

template<class t_alphabet_strat = byte_alphabet>
typedef csa_tag sdsl::csa_bitcompressed< t_alphabet_strat >::index_category

Definition at line 75 of file csa_bitcompressed.hpp.

◆ isa_sample_type

template<class t_alphabet_strat = byte_alphabet>
typedef _isa_sampling<csa_bitcompressed, 0> sdsl::csa_bitcompressed< t_alphabet_strat >::isa_sample_type

Definition at line 66 of file csa_bitcompressed.hpp.

◆ isa_type

template<class t_alphabet_strat = byte_alphabet>
typedef isa_sample_type sdsl::csa_bitcompressed< t_alphabet_strat >::isa_type

Definition at line 67 of file csa_bitcompressed.hpp.

◆ iterator

template<class t_alphabet_strat = byte_alphabet>
typedef const_iterator sdsl::csa_bitcompressed< t_alphabet_strat >::iterator

Definition at line 52 of file csa_bitcompressed.hpp.

◆ lf_type

template<class t_alphabet_strat = byte_alphabet>
typedef traverse_csa_saisa<csa_bitcompressed, false> sdsl::csa_bitcompressed< t_alphabet_strat >::lf_type

Definition at line 61 of file csa_bitcompressed.hpp.

◆ pointer

template<class t_alphabet_strat = byte_alphabet>
typedef const_reference* sdsl::csa_bitcompressed< t_alphabet_strat >::pointer

Definition at line 55 of file csa_bitcompressed.hpp.

◆ psi_type

template<class t_alphabet_strat = byte_alphabet>
typedef traverse_csa_saisa<csa_bitcompressed, true> sdsl::csa_bitcompressed< t_alphabet_strat >::psi_type

Definition at line 60 of file csa_bitcompressed.hpp.

◆ reference

template<class t_alphabet_strat = byte_alphabet>
typedef const_reference sdsl::csa_bitcompressed< t_alphabet_strat >::reference

Definition at line 54 of file csa_bitcompressed.hpp.

◆ sa_sample_type

template<class t_alphabet_strat = byte_alphabet>
typedef _sa_order_sampling<csa_bitcompressed, 0> sdsl::csa_bitcompressed< t_alphabet_strat >::sa_sample_type

Definition at line 65 of file csa_bitcompressed.hpp.

◆ size_type

template<class t_alphabet_strat = byte_alphabet>
typedef int_vector ::size_type sdsl::csa_bitcompressed< t_alphabet_strat >::size_type

Definition at line 57 of file csa_bitcompressed.hpp.

◆ string_type

template<class t_alphabet_strat = byte_alphabet>
typedef alphabet_type::string_type sdsl::csa_bitcompressed< t_alphabet_strat >::string_type

Definition at line 71 of file csa_bitcompressed.hpp.

◆ text_type

template<class t_alphabet_strat = byte_alphabet>
typedef text_of_csa<csa_bitcompressed> sdsl::csa_bitcompressed< t_alphabet_strat >::text_type

Definition at line 63 of file csa_bitcompressed.hpp.

◆ value_type

template<class t_alphabet_strat = byte_alphabet>
typedef uint64_t sdsl::csa_bitcompressed< t_alphabet_strat >::value_type

Definition at line 50 of file csa_bitcompressed.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<class t_alphabet_strat = byte_alphabet>
anonymous enum
Enumerator
sa_sample_dens 
isa_sample_dens 

Definition at line 78 of file csa_bitcompressed.hpp.

Constructor & Destructor Documentation

◆ csa_bitcompressed() [1/4]

template<class t_alphabet_strat = byte_alphabet>
sdsl::csa_bitcompressed< t_alphabet_strat >::csa_bitcompressed ( )
inline

Default constructor.

Definition at line 105 of file csa_bitcompressed.hpp.

◆ csa_bitcompressed() [2/4]

template<class t_alphabet_strat = byte_alphabet>
sdsl::csa_bitcompressed< t_alphabet_strat >::csa_bitcompressed ( const csa_bitcompressed< t_alphabet_strat > &  csa)
inline

Copy constructor.

Definition at line 107 of file csa_bitcompressed.hpp.

◆ csa_bitcompressed() [3/4]

template<class t_alphabet_strat = byte_alphabet>
sdsl::csa_bitcompressed< t_alphabet_strat >::csa_bitcompressed ( csa_bitcompressed< t_alphabet_strat > &&  csa)
inline

Move constructor.

Definition at line 114 of file csa_bitcompressed.hpp.

◆ csa_bitcompressed() [4/4]

template<class t_alphabet_strat = byte_alphabet>
sdsl::csa_bitcompressed< t_alphabet_strat >::csa_bitcompressed ( cache_config config)
inline

Constructor.

Definition at line 117 of file csa_bitcompressed.hpp.

Member Function Documentation

◆ begin()

template<class t_alphabet_strat = byte_alphabet>
const_iterator sdsl::csa_bitcompressed< t_alphabet_strat >::begin ( ) const
inline

Returns a const_iterator to the first element.

Required for the STL Container Concept.

See also
end

Definition at line 151 of file csa_bitcompressed.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_alphabet_strat = byte_alphabet>
template<typename archive_t >
void sdsl::csa_bitcompressed< t_alphabet_strat >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Definition at line 235 of file csa_bitcompressed.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_alphabet_strat = byte_alphabet>
template<typename archive_t >
void sdsl::csa_bitcompressed< t_alphabet_strat >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Definition at line 227 of file csa_bitcompressed.hpp.

◆ empty()

template<class t_alphabet_strat = byte_alphabet>
bool sdsl::csa_bitcompressed< t_alphabet_strat >::empty ( ) const
inline

Returns if the data structure is empty.

Required for the Container Concept of the STL.

See also
size

Definition at line 145 of file csa_bitcompressed.hpp.

◆ end()

template<class t_alphabet_strat = byte_alphabet>
const_iterator sdsl::csa_bitcompressed< t_alphabet_strat >::end ( ) const
inline

Returns a const_iterator to the element after the last element.

Required for the STL Container Concept.

See also
begin.

Definition at line 157 of file csa_bitcompressed.hpp.

◆ get_sample_dens()

template<class t_alphabet_strat = byte_alphabet>
size_type sdsl::csa_bitcompressed< t_alphabet_strat >::get_sample_dens ( ) const
inline

Definition at line 242 of file csa_bitcompressed.hpp.

◆ load()

template<class t_alphabet_strat = byte_alphabet>
void sdsl::csa_bitcompressed< t_alphabet_strat >::load ( std::istream &  in)
inline

Definition at line 219 of file csa_bitcompressed.hpp.

◆ max_size()

template<class t_alphabet_strat = byte_alphabet>
static size_type sdsl::csa_bitcompressed< t_alphabet_strat >::max_size ( )
inlinestatic

Returns the largest size that csa_bitcompressed can ever have.

Required for the Container Concept of the STL.

See also
size

Definition at line 139 of file csa_bitcompressed.hpp.

◆ operator!=()

template<class t_alphabet_strat = byte_alphabet>
bool sdsl::csa_bitcompressed< t_alphabet_strat >::operator!= ( csa_bitcompressed< t_alphabet_strat > const &  other) const
inlinenoexcept

Inequality operator.

Definition at line 202 of file csa_bitcompressed.hpp.

◆ operator=() [1/2]

template<class t_alphabet_strat = byte_alphabet>
csa_bitcompressed & sdsl::csa_bitcompressed< t_alphabet_strat >::operator= ( const csa_bitcompressed< t_alphabet_strat > &  csa)
inline

Assignment Operator.

Required for the Assignable Concept of the STL.

Definition at line 170 of file csa_bitcompressed.hpp.

◆ operator=() [2/2]

template<class t_alphabet_strat = byte_alphabet>
csa_bitcompressed & sdsl::csa_bitcompressed< t_alphabet_strat >::operator= ( csa_bitcompressed< t_alphabet_strat > &&  csa)
inline

Assignment Move Operator.

Required for the Assignable Concept of the STL.

Definition at line 184 of file csa_bitcompressed.hpp.

◆ operator==()

template<class t_alphabet_strat = byte_alphabet>
bool sdsl::csa_bitcompressed< t_alphabet_strat >::operator== ( csa_bitcompressed< t_alphabet_strat > const &  other) const
inlinenoexcept

Equality operator.

Definition at line 196 of file csa_bitcompressed.hpp.

◆ operator[]()

template<class t_alphabet_strat = byte_alphabet>
value_type sdsl::csa_bitcompressed< t_alphabet_strat >::operator[] ( size_type  i) const
inline

[]-operator

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

Required for the STL Random Access Container Concept.

Definition at line 164 of file csa_bitcompressed.hpp.

◆ serialize()

template<class t_alphabet_strat = byte_alphabet>
size_type sdsl::csa_bitcompressed< t_alphabet_strat >::serialize ( std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
) const
inline

Serialize to a stream.

Parameters
outOutput stream to write the data structure.
Returns
The number of written bytes.

Definition at line 208 of file csa_bitcompressed.hpp.

◆ size()

template<class t_alphabet_strat = byte_alphabet>
size_type sdsl::csa_bitcompressed< t_alphabet_strat >::size ( ) const
inline

Number of elements in the instance.

Required for the Container Concept of the STL.

See also
max_size, empty

Definition at line 133 of file csa_bitcompressed.hpp.

Friends And Related Function Documentation

◆ bwt_of_csa_psi< csa_bitcompressed >

template<class t_alphabet_strat = byte_alphabet>
friend class bwt_of_csa_psi< csa_bitcompressed >
friend

Definition at line 1 of file csa_bitcompressed.hpp.

Member Data Documentation

◆ bwt

template<class t_alphabet_strat = byte_alphabet>
const bwt_type sdsl::csa_bitcompressed< t_alphabet_strat >::bwt = bwt_type(*this)

Definition at line 96 of file csa_bitcompressed.hpp.

◆ C

template<class t_alphabet_strat = byte_alphabet>
const alphabet_type::C_type& sdsl::csa_bitcompressed< t_alphabet_strat >::C = m_alphabet.C

Definition at line 92 of file csa_bitcompressed.hpp.

◆ char2comp

template<class t_alphabet_strat = byte_alphabet>
const alphabet_type::char2comp_type& sdsl::csa_bitcompressed< t_alphabet_strat >::char2comp = m_alphabet.char2comp

Definition at line 90 of file csa_bitcompressed.hpp.

◆ comp2char

template<class t_alphabet_strat = byte_alphabet>
const alphabet_type::comp2char_type& sdsl::csa_bitcompressed< t_alphabet_strat >::comp2char = m_alphabet.comp2char

Definition at line 91 of file csa_bitcompressed.hpp.

◆ F

template<class t_alphabet_strat = byte_alphabet>
const first_row_type sdsl::csa_bitcompressed< t_alphabet_strat >::F = first_row_type(*this)

Definition at line 99 of file csa_bitcompressed.hpp.

◆ isa

template<class t_alphabet_strat = byte_alphabet>
const isa_type& sdsl::csa_bitcompressed< t_alphabet_strat >::isa = m_isa

Definition at line 98 of file csa_bitcompressed.hpp.

◆ isa_sample

template<class t_alphabet_strat = byte_alphabet>
const isa_sample_type& sdsl::csa_bitcompressed< t_alphabet_strat >::isa_sample = m_isa

Definition at line 102 of file csa_bitcompressed.hpp.

◆ L

template<class t_alphabet_strat = byte_alphabet>
const bwt_type sdsl::csa_bitcompressed< t_alphabet_strat >::L = bwt_type(*this)

Definition at line 97 of file csa_bitcompressed.hpp.

◆ lf

template<class t_alphabet_strat = byte_alphabet>
const lf_type sdsl::csa_bitcompressed< t_alphabet_strat >::lf = lf_type(*this)

Definition at line 95 of file csa_bitcompressed.hpp.

◆ psi

template<class t_alphabet_strat = byte_alphabet>
const psi_type sdsl::csa_bitcompressed< t_alphabet_strat >::psi = psi_type(*this)

Definition at line 94 of file csa_bitcompressed.hpp.

◆ sa_sample

template<class t_alphabet_strat = byte_alphabet>
const sa_sample_type& sdsl::csa_bitcompressed< t_alphabet_strat >::sa_sample = m_sa

Definition at line 101 of file csa_bitcompressed.hpp.

◆ sigma

template<class t_alphabet_strat = byte_alphabet>
const alphabet_type::sigma_type& sdsl::csa_bitcompressed< t_alphabet_strat >::sigma = m_alphabet.sigma

Definition at line 93 of file csa_bitcompressed.hpp.

◆ text

template<class t_alphabet_strat = byte_alphabet>
const text_type sdsl::csa_bitcompressed< t_alphabet_strat >::text = text_type(*this)

Definition at line 100 of file csa_bitcompressed.hpp.


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