SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 > Class Template Reference

A class for the Compressed Suffix Tree (CST) proposed by Sadakane. More...

#include <cst_sada.hpp>

Public Types

typedef cst_dfs_const_forward_iterator< cst_sadaconst_iterator
 
typedef cst_bottom_up_const_forward_iterator< cst_sadaconst_bottom_up_iterator
 
typedef t_csa::size_type size_type
 
typedef ptrdiff_t difference_type
 
typedef t_csa csa_type
 
typedef t_lcp::template type< cst_sadalcp_type
 
typedef t_csa::char_type char_type
 
typedef t_csa::string_type string_type
 
typedef size_type node_type
 Type for the nodes in the tree.
 
typedef t_bp_support bp_support_type
 
typedef t_rank_10 rank_10_type
 
typedef t_select_10 select_10_type
 
typedef t_csa::alphabet_type::comp_char_type comp_char_type
 
typedef t_csa::alphabet_type::sigma_type sigma_type
 
typedef t_csa::alphabet_category alphabet_category
 
typedef cst_tag index_category
 

Public Member Functions

 cst_sada ()=default
 Default constructor.
 
 cst_sada (cst_sada const &cst)
 Copy constructor.
 
 cst_sada (cst_sada &&cst)
 Move constructor.
 
 cst_sada (cache_config &config)
 Construct CST from file_map.
 
size_type size () const
 Number of leaves in the suffix tree.
 
bool empty () const
 Returns if the data strucutre is empty.
 
const_iterator begin () const
 Returns a const_iterator to the first element.
 
const_iterator begin (node_type const &v) const
 Returns a const_iterator to the first element of a depth first traversal of the subtree rooted at node v.
 
const_iterator end () const
 Returns a const_iterator to the element after the last element.
 
const_iterator end (node_type const &v) const
 Returns a const_iterator to the element past the end of a depth first traversal of the subtree rooted at node v.
 
const_bottom_up_iterator begin_bottom_up () const
 Returns an iterator to the first element of a bottom-up traversal of the tree.
 
const_bottom_up_iterator end_bottom_up () const
 Returns an iterator to the element after the last element of a bottom-up traversal of the tree.
 
cst_sadaoperator= (cst_sada const &cst)
 Assignment Operator.
 
cst_sadaoperator= (cst_sada &&cst)
 Move assignment Operator.
 
bool operator== (cst_sada const &other) const noexcept
 Equality operator.
 
bool operator!= (cst_sada 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)
 Load from a stream.
 
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)
 
node_type root () const
 Return the root of the suffix tree.
 
bool is_leaf (node_type v) const
 Decide if a node is a leaf in the suffix tree.
 
node_type select_leaf (size_type i) const
 Return the i-th leaf (1-based from left to right) of the suffix tree.
 
size_type depth (node_type v) const
 Returns the depth of node v.
 
size_type node_depth (node_type v) const
 Returns the node depth of node v.
 
size_type size (node_type v) const
 Calculate the number of leaves in the subtree rooted at node v.
 
node_type leftmost_leaf (const node_type v) const
 Calculates the leftmost leaf in the subtree rooted at node v.
 
node_type rightmost_leaf (const node_type v) const
 Calculates the rightmost leaf in the subtree rooted at node v.
 
size_type lb (const node_type v) const
 Calculates the index of the leftmost leaf in the corresponding suffix array.
 
size_type rb (const node_type v) const
 Calculates the index of the rightmost leaf in the corresponding suffix array.
 
node_type parent (node_type v) const
 Calculate the parent node of a node v.
 
cst_node_child_proxy< cst_sadachildren (node_type v) const
 Return a proxy object which allows iterating over the children of a node.
 
node_type sibling (node_type v) const
 Returns the next sibling of node v.
 
node_type child (node_type v, const char_type c, size_type &char_pos) const
 Get the child w of node v which edge label (v,w) starts with character c.
 
node_type child (node_type v, const char_type c) const
 Get the child w of node v which edge label (v,w) starts with character c.
 
node_type select_child (node_type v, size_type i) const
 Get the i-th child of a node v.
 
char_type edge (node_type v, size_type d) const
 Returns the d-th character (1-based indexing) of the edge-label pointing to v.
 
node_type lca (node_type v, node_type w) const
 Calculate the lowest common ancestor (lca) of two nodes v and w of the suffix tree.
 
node_type sl (node_type v) const
 Compute the suffix link of node v.
 
node_type sl (node_type v, size_type i) const
 Compute the suffix link of node v applied a number of times consecutively.
 
node_type wl (node_type v, const char_type c) const
 Compute the Weiner link of node v and character c.
 
size_type sn (node_type v) const
 Compute the suffix number of a leaf node v.
 
size_type id (node_type v) const
 Computes a unique identification number for a node of the suffix tree in the range [0..nodes()-1].
 
size_type inv_id (size_type id)
 Computes the node for such that id(v)=id.
 
size_type nodes () const
 Get the number of nodes of the suffix tree.
 
node_type node (size_type lb, size_type rb) const
 Get the node in the suffix tree which corresponds to the lcp-interval [lb..rb].
 
size_type degree (node_type v) const
 Get the number of children of a node v.
 
size_type tlcp_idx (size_type i) const
 Maps an index i to the position in TLCP where LCP[i] can be found.
 

Static Public Member Functions

static size_type max_size ()
 Returns the maximal lenght of text for that a suffix tree can be build.
 

Public Attributes

t_csa const & csa = m_csa
 
lcp_type const & lcp = m_lcp
 
bit_vector const & bp = m_bp
 
bp_support_type const & bp_support = m_bp_support
 
rank_10_type const & bp_rank_10 = m_bp_rank10
 
select_10_type const & bp_select_10 = m_bp_select10
 

Detailed Description

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
class sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >

A class for the Compressed Suffix Tree (CST) proposed by Sadakane.

Template Parameters
t_csaType of a CSA (member of this type is accessible via member csa, default class is sdsl::csa_sada).
t_lcpType of a LCP structure (member is accessible via member lcp, default class is sdsl::lcp_support_sada),
t_bp_supportType of a BPS structure (member accessible via member bp_support, default class is sdsl::bp_support_sada),
t_rank_10Type of a rank structure for the 2-bit pattern 10 (accessible via member bp_rank_10, default class is sdsl::rank_support_v5)
t_select_10Type of a select structure for the 2-bit pattern 10 (accessible via member $bp\_select\_10$, default class is sdsl::select_support_mcl).

It also contains a sdsl::bit_vector which represents the balanced parentheses sequence of the suffix tree. This bit_vector can be accessed via member bp.

A node v of the csa_sada is represented by an integer i which corresponds to the position of the opening parenthesis of the parentheses pair $(i,\mu(i))$ that corresponds to v in bp.

Reference
Kunihiko Sadakane: Compressed Suffix Trees with Full Functionality. Theory Comput. Syst. 41(4): 589-607 (2007)

Definition at line 74 of file cst_sada.hpp.

Member Typedef Documentation

◆ alphabet_category

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef t_csa::alphabet_category sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::alphabet_category

Definition at line 96 of file cst_sada.hpp.

◆ bp_support_type

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef t_bp_support sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::bp_support_type

Definition at line 89 of file cst_sada.hpp.

◆ char_type

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef t_csa::char_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::char_type

Definition at line 86 of file cst_sada.hpp.

◆ comp_char_type

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef t_csa::alphabet_type::comp_char_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::comp_char_type

Definition at line 93 of file cst_sada.hpp.

◆ const_bottom_up_iterator

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef cst_bottom_up_const_forward_iterator<cst_sada> sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::const_bottom_up_iterator

Definition at line 81 of file cst_sada.hpp.

◆ const_iterator

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef cst_dfs_const_forward_iterator<cst_sada> sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::const_iterator

Definition at line 80 of file cst_sada.hpp.

◆ csa_type

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef t_csa sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::csa_type

Definition at line 84 of file cst_sada.hpp.

◆ difference_type

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef ptrdiff_t sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::difference_type

Definition at line 83 of file cst_sada.hpp.

◆ index_category

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef cst_tag sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::index_category

Definition at line 97 of file cst_sada.hpp.

◆ lcp_type

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef t_lcp::template type<cst_sada> sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::lcp_type

Definition at line 85 of file cst_sada.hpp.

◆ node_type

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::node_type

Type for the nodes in the tree.

Definition at line 88 of file cst_sada.hpp.

◆ rank_10_type

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef t_rank_10 sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::rank_10_type

Definition at line 90 of file cst_sada.hpp.

◆ select_10_type

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef t_select_10 sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::select_10_type

Definition at line 91 of file cst_sada.hpp.

◆ sigma_type

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef t_csa::alphabet_type::sigma_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::sigma_type

Definition at line 94 of file cst_sada.hpp.

◆ size_type

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef t_csa::size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::size_type

Definition at line 82 of file cst_sada.hpp.

◆ string_type

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
typedef t_csa::string_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::string_type

Definition at line 87 of file cst_sada.hpp.

Constructor & Destructor Documentation

◆ cst_sada() [1/4]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::cst_sada ( )
default

Default constructor.

◆ cst_sada() [2/4]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::cst_sada ( cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 > const & cst)
inline

Copy constructor.

Definition at line 127 of file cst_sada.hpp.

◆ cst_sada() [3/4]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::cst_sada ( cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 > && cst)
inline

Move constructor.

Definition at line 141 of file cst_sada.hpp.

◆ cst_sada() [4/4]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::cst_sada ( cache_config & config)
inline

Construct CST from file_map.

Definition at line 155 of file cst_sada.hpp.

Member Function Documentation

◆ begin() [1/2]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
const_iterator sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::begin ( ) const
inline

Returns a const_iterator to the first element.

Required for the STL Container Concept.

See also
end

Definition at line 295 of file cst_sada.hpp.

◆ begin() [2/2]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
const_iterator sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::begin ( node_type const & v) const
inline

Returns a const_iterator to the first element of a depth first traversal of the subtree rooted at node v.

Definition at line 303 of file cst_sada.hpp.

◆ begin_bottom_up()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
const_bottom_up_iterator sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::begin_bottom_up ( ) const
inline

Returns an iterator to the first element of a bottom-up traversal of the tree.

Definition at line 328 of file cst_sada.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
template<typename archive_t >
void sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar)
inline

Definition at line 433 of file cst_sada.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
template<typename archive_t >
void sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar) const
inline

Definition at line 422 of file cst_sada.hpp.

◆ child() [1/2]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::child ( node_type v,
const char_type c ) const
inline

Get the child w of node v which edge label (v,w) starts with character c.

Definition at line 676 of file cst_sada.hpp.

◆ child() [2/2]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::child ( node_type v,
const char_type c,
size_type & char_pos ) const
inline

Get the child w of node v which edge label (v,w) starts with character c.

Definition at line 642 of file cst_sada.hpp.

◆ children()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
cst_node_child_proxy< cst_sada > sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::children ( node_type v) const
inline

Return a proxy object which allows iterating over the children of a node.

Parameters
vA valid node of the suffix tree.
Returns
The proxy object of v containing all children
Time complexity
$ \Order{1}$

Definition at line 610 of file cst_sada.hpp.

◆ degree()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::degree ( node_type v) const
inline

Get the number of children of a node v.

Parameters
vA valid node v of a cst_sada.
Returns
The number of children of node v.
Time complexity
$ \Order{\sigma} $

Definition at line 958 of file cst_sada.hpp.

◆ depth()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::depth ( node_type v) const
inline

Returns the depth of node v.

Parameters
vA valid node of the suffix tree.
Returns
The depth of the node.
Time complexity
$ \Order{\lcpaccess \vee \saaccess} $

Definition at line 496 of file cst_sada.hpp.

◆ edge()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
char_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::edge ( node_type v,
size_type d ) const
inline

Returns the d-th character (1-based indexing) of the edge-label pointing to v.

Parameters
vThe node at which the edge path ends.
dThe position (1-based indexing) of the requested character on the edge path from the root to v. $ d >
0 \wedge d <= depth(v) $
Returns
The character at position d on the edge path from the root to v.
Time
complexity $ \Order{ \log\sigma + (\saaccess+\isaaccess) } $
Precondition
$ 1 \leq d \leq depth(v)  $

Definition at line 714 of file cst_sada.hpp.

◆ empty()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
bool sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::empty ( ) const
inline

Returns if the data strucutre is empty.

Required for the Container Concept of the STL.

See also
size

Definition at line 286 of file cst_sada.hpp.

◆ end() [1/2]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
const_iterator sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::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 314 of file cst_sada.hpp.

◆ end() [2/2]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
const_iterator sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::end ( node_type const & v) const
inline

Returns a const_iterator to the element past the end of a depth first traversal of the subtree rooted at node v.

Definition at line 320 of file cst_sada.hpp.

◆ end_bottom_up()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
const_bottom_up_iterator sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::end_bottom_up ( ) const
inline

Returns an iterator to the element after the last element of a bottom-up traversal of the tree.

Definition at line 336 of file cst_sada.hpp.

◆ id()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::id ( node_type v) const
inline

Computes a unique identification number for a node of the suffix tree in the range [0..nodes()-1].

Parameters
vA valid node of a cst_sada.
Returns
A unique identification number for the node v in the range [0..nodes()-1]
Time complexity
$ \Order{1} $
See also
inv_id(size_type id)

Definition at line 872 of file cst_sada.hpp.

◆ inv_id()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::inv_id ( size_type id)
inline

Computes the node for such that id(v)=id.

Parameters
idAn id in the range [0..nodes()-1].
Returns
A node v of the CST such that id(v)=id.
Time complexity
$ \Order{1} $ for leaves and $ \log n $ for inner nodes
See also
id(node_type v)

Definition at line 893 of file cst_sada.hpp.

◆ is_leaf()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
bool sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::is_leaf ( node_type v) const
inline

Decide if a node is a leaf in the suffix tree.

Parameters
vA valid node of a cst_sada.
Returns
A boolean value indicating if v is a leaf.
Time complexity
$ \Order{1} $

Definition at line 467 of file cst_sada.hpp.

◆ lb()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::lb ( const node_type v) const
inline

Calculates the index of the leftmost leaf in the corresponding suffix array.

Parameters
vA valid node of the suffix tree.
Returns
The index of the leftmost leaf in the corresponding suffix array.
Time complexity
$ \Order{1} $
Note
lb is an abbreviation for ,,left bound''

Definition at line 568 of file cst_sada.hpp.

◆ lca()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::lca ( node_type v,
node_type w ) const
inline

Calculate the lowest common ancestor (lca) of two nodes v and w of the suffix tree.

Parameters
vThe first node for which the lca with the second node should be computed.
wThe second node for which the lca with the first node should be computed.
Returns
A node that is the lowest common ancestor of v and w in the suffix tree.
Time complexity
$ \Order{\rrenclose}\   $

Definition at line 752 of file cst_sada.hpp.

◆ leftmost_leaf()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::leftmost_leaf ( const node_type v) const
inline

Calculates the leftmost leaf in the subtree rooted at node v.

Parameters
vA valid node of the suffix tree.
Returns
The leftmost leaf in the subtree rooted at node v.
Time complexity
$ \Order{1} $

Definition at line 543 of file cst_sada.hpp.

◆ load()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
void sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::load ( std::istream & in)
inline

Load from a stream.

Parameters
inInputstream to load the data structure from.

Definition at line 411 of file cst_sada.hpp.

◆ max_size()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
static size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::max_size ( )
inlinestatic

Returns the maximal lenght of text for that a suffix tree can be build.

Required for the Container Concept of the STL.

See also
size

Definition at line 277 of file cst_sada.hpp.

◆ node()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::node ( size_type lb,
size_type rb ) const
inline

Get the node in the suffix tree which corresponds to the lcp-interval [lb..rb].

Definition at line 946 of file cst_sada.hpp.

◆ node_depth()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::node_depth ( node_type v) const
inline

Returns the node depth of node v.

Parameters
vA valid node of a cst_sada.
Returns
The node depth of node v.
Time complexity
$ \Order{1} $

Definition at line 517 of file cst_sada.hpp.

◆ nodes()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::nodes ( ) const
inline

Get the number of nodes of the suffix tree.

Definition at line 936 of file cst_sada.hpp.

◆ operator!=()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
bool sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::operator!= ( cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 > const & other) const
inlinenoexcept

Inequality operator.

Definition at line 385 of file cst_sada.hpp.

◆ operator=() [1/2]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
cst_sada & sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::operator= ( cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 > && cst)
inline

Move assignment Operator.

Required for the Assignable Concept of the STL.

Definition at line 359 of file cst_sada.hpp.

◆ operator=() [2/2]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
cst_sada & sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::operator= ( cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 > const & cst)
inline

Assignment Operator.

Required for the Assignable Concept of the STL.

Definition at line 345 of file cst_sada.hpp.

◆ operator==()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
bool sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::operator== ( cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 > const & other) const
inlinenoexcept

Equality operator.

Definition at line 377 of file cst_sada.hpp.

◆ parent()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::parent ( node_type v) const
inline

Calculate the parent node of a node v.

Parameters
vA valid node of the suffix tree.
Returns
The parent node of v or root() if v equals root().
Time complexity
$ \Order{1} $

Definition at line 593 of file cst_sada.hpp.

◆ rb()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::rb ( const node_type v) const
inline

Calculates the index of the rightmost leaf in the corresponding suffix array.

Parameters
vA valid node of the suffix tree.
Returns
The index of the rightmost leaf in the corresponding suffix array.
Time complexity
$ \Order{1} $
Note
rb is an abbreviation for ,,right bound''

Definition at line 581 of file cst_sada.hpp.

◆ rightmost_leaf()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::rightmost_leaf ( const node_type v) const
inline

Calculates the rightmost leaf in the subtree rooted at node v.

Parameters
vA valid node of the suffix tree.
Returns
The rightmost leaf in the subtree rooted at node v.
Time complexity
$ \Order{1} $

Definition at line 554 of file cst_sada.hpp.

◆ root()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::root ( ) const
inline

Return the root of the suffix tree.

Time complexity
$ \Order{1} $

Definition at line 455 of file cst_sada.hpp.

◆ select_child()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::select_child ( node_type v,
size_type i ) const
inline

Get the i-th child of a node v.

Parameters
vA valid tree node of the cst.
i1-based Index of the child which should be returned. $i \geq 1$.
Returns
The i-th child node of v or root() if v has no i-th child.
Time complexity
$ \Order{i} $ for $  i \leq \sigma $
Precondition
$ 1 \leq i \leq degree(v) $

Definition at line 691 of file cst_sada.hpp.

◆ select_leaf()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::select_leaf ( size_type i) const
inline

Return the i-th leaf (1-based from left to right) of the suffix tree.

Parameters
i1-based position of the leaf. $1\leq i\leq csa.size()$.
Returns
The i-th leave.
Time complexity
$ \Order{1} $
Precondition
$ 1 \leq i \leq csa.size() $

Definition at line 482 of file cst_sada.hpp.

◆ serialize()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::serialize ( std::ostream & out,
structure_tree_node * v = nullptr,
std::string name = "" ) const
inline

Serialize to a stream.

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

Definition at line 394 of file cst_sada.hpp.

◆ sibling()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::sibling ( node_type v) const
inline

Returns the next sibling of node v.

Parameters
vA valid node v of the suffix tree.
Returns
The next (right) sibling of node v or root() if v has no next (right) sibling.
Time complexity
$ \Order{1} $

Definition at line 622 of file cst_sada.hpp.

◆ size() [1/2]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::size ( ) const
inline

Number of leaves in the suffix tree.

Required for the Container Concept of the STL.

See also
max_size, empty

Definition at line 268 of file cst_sada.hpp.

◆ size() [2/2]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::size ( node_type v) const
inline

Calculate the number of leaves in the subtree rooted at node v.

Parameters
vA valid node of the suffix tree.
Returns
The number of leaves in the subtree rooted at node v.
Time complexity
$ \Order{1} $

This method is used e.g. in the count method.

Definition at line 531 of file cst_sada.hpp.

◆ sl() [1/2]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::sl ( node_type v) const
inline

Compute the suffix link of node v.

Parameters
vA valid node of a cst_sada.
Returns
The suffix link of node v.
Time complexity
$ \Order{ 1 } $

Definition at line 775 of file cst_sada.hpp.

◆ sl() [2/2]

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::sl ( node_type v,
size_type i ) const
inline

Compute the suffix link of node v applied a number of times consecutively.

Parameters
vA valid node of a cst_sada
Returns
The suffix link ^ i of node v.
Time complexity
$ \Order{ i } $

Definition at line 800 of file cst_sada.hpp.

◆ sn()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::sn ( node_type v) const
inline

Compute the suffix number of a leaf node v.

Parameters
vA valid leaf node of a cst_sada.
Returns
The suffix array value corresponding to the leaf node v.
Time complexity
$ \Order{ \saaccess } $

Definition at line 857 of file cst_sada.hpp.

◆ tlcp_idx()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::tlcp_idx ( size_type i) const
inline

Maps an index i to the position in TLCP where LCP[i] can be found.

Parameters
iThe index in the LCP array
Returns
The corresponding position in the TLCP array

Definition at line 975 of file cst_sada.hpp.

◆ wl()

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
node_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::wl ( node_type v,
const char_type c ) const
inline

Compute the Weiner link of node v and character c.

Definition at line 826 of file cst_sada.hpp.

Member Data Documentation

◆ bp

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
bit_vector const& sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::bp = m_bp

Definition at line 118 of file cst_sada.hpp.

◆ bp_rank_10

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
rank_10_type const& sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::bp_rank_10 = m_bp_rank10

Definition at line 120 of file cst_sada.hpp.

◆ bp_select_10

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
select_10_type const& sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::bp_select_10 = m_bp_select10

Definition at line 121 of file cst_sada.hpp.

◆ bp_support

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
bp_support_type const& sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::bp_support = m_bp_support

Definition at line 119 of file cst_sada.hpp.

◆ csa

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
t_csa const& sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::csa = m_csa

Definition at line 116 of file cst_sada.hpp.

◆ lcp

template<class t_csa = csa_sada<>, class t_lcp = lcp_support_sada<>, class t_bp_support = bp_support_sada<>, class t_rank_10 = rank_support_v5<10, 2>, class t_select_10 = select_support_mcl<10, 2>>
lcp_type const& sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::lcp = m_lcp

Definition at line 117 of file cst_sada.hpp.


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