SDSL  3.0.0
Succinct Data Structure Library
sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > Class Template Reference

A class for the Fully-Compressed Suffix Tree (FCST) proposed by Russo et al. More...

#include <cst_fully.hpp>

Public Types

typedef cst_dfs_const_forward_iterator< cst_fullyconst_iterator
 
typedef t_csa::size_type size_type
 
typedef t_csa csa_type
 
typedef lcp_fully< cst_fullylcp_type
 
typedef t_csa::char_type char_type
 
typedef std::pair< size_type, size_typenode_type
 
typedef size_type leaf_type
 
typedef size_type sampled_node_type
 
typedef t_s_support s_support_type
 
typedef t_b b_type
 
typedef t_b::select_0_type b_select_0_type
 
typedef t_b::select_1_type b_select_1_type
 
typedef t_depth depth_type
 
typedef t_csa::alphabet_category alphabet_category
 
typedef cst_tag index_category
 

Public Member Functions

 cst_fully ()=default
 Default constructor. More...
 
 cst_fully (const cst_fully &cst)
 Copy constructor. More...
 
 cst_fully (cst_fully &&cst)
 Move constructor. More...
 
 cst_fully (cache_config &config)
 Construct CST from file_map. More...
 
size_type size () const
 
bool empty () const
 
const_iterator begin () const
 
const_iterator end () const
 
cst_fullyoperator= (const cst_fully &cst)
 Copy Assignment Operator. More...
 
cst_fullyoperator= (cst_fully &&cst)
 Move Assignment Operator. More...
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serialize to a stream. More...
 
void load (std::istream &in)
 Load from a stream. More...
 
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)
 
bool operator== (cst_fully const &other) const noexcept
 Equality operator. More...
 
bool operator!= (cst_fully const &other) const noexcept
 Inequality operator. More...
 
node_type root () const
 Returns the root of the suffix tree. More...
 
sampled_node_type sampled_root () const
 Returns the root of the sampled tree. More...
 
bool is_leaf (node_type v) const
 Returns true iff node v is a leaf. More...
 
node_type select_leaf (size_type i) const
 Return the i-th leaf (1-based from left to right) of the suffix tree. More...
 
node_type node (size_type lb, size_type rb) const
 Get the node in the suffix tree which corresponds to the sa-interval [lb..rb]. More...
 
leaf_type lb (node_type v) const
 Returns the leftmost leaf (left boundary) of a node. More...
 
leaf_type rb (node_type v) const
 Returns the rightmost leaf (right boundary) of a node. More...
 
size_type size (const node_type &v) const
 Calculate the number of leaves in the subtree rooted at node v. More...
 
node_type leftmost_leaf (const node_type v) const
 Calculates the leftmost leaf in the subtree rooted at node v. More...
 
node_type rightmost_leaf (const node_type v) const
 Calculates the rightmost leaf in the subtree rooted at node v. More...
 
bool ancestor (node_type v, node_type w) const
 Returns true iff v is an ancestor of w. More...
 
sampled_node_type pred (leaf_type v) const
 Returns the index of the last bracket in S before the leaf with index l. More...
 
sampled_node_type lsa_leaf (leaf_type l) const
 Returns the LSA (lowest sampled ancestor) for a leaf with index l. More...
 
node_type sampled_node (sampled_node_type u) const
 Returns the node in the suffix tree corresponding to the node u in the sampled tree. More...
 
sampled_node_type sampled_lca (sampled_node_type u, sampled_node_type q) const
 Returns the LCA of two nodes in the sampled tree. More...
 
size_type depth (sampled_node_type u) const
 Returns the depth of a sampled node u. More...
 
size_type depth (node_type v) const
 Returns the depth of a node v. More...
 
node_type lca (node_type v, node_type w) const
 Calculate the LCA of two nodes v and w. More...
 
node_type lca (leaf_type l, leaf_type r) const
 Calculate the LCA of two leaves l and r. More...
 
size_type depth_lca (leaf_type l, leaf_type r, size_type &res_i, sampled_node_type &res_u, std::vector< char_type > &res_label) const
 Calculate the depth of the LCA of two leaves l and r. More...
 
size_type depth_lca (leaf_type l, leaf_type r, size_type &res_i, sampled_node_type &res_u) const
 This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...
 
node_type sl (node_type v) const
 Compute the suffix link of a node v. More...
 
node_type wl (node_type v, const char_type c) const
 Compute the Weiner link of node v and character c. More...
 
size_type sn (node_type v) const
 Compute the suffix number of a leaf node v. More...
 
node_type parent (node_type v) const
 Calculate the parent node of a node v. More...
 
node_type child (node_type v, char_type c) const
 Get the child w of node v which edge label (v,w) starts with character c. More...
 
node_type child (node_type v, char_type c, size_type d) const
 

Static Public Member Functions

static size_type max_size ()
 

Public Attributes

const size_typedelta = m_delta
 
const csa_typecsa = m_csa
 
const bit_vectors = m_s
 
const s_support_types_support = m_s_support
 
const b_typeb = m_b
 
const b_select_0_typeb_select_0 = m_b_select0
 
const b_select_1_typeb_select_1 = m_b_select1
 
const depth_typedepth_sampling = m_depth
 
const lcp_typelcp = m_lcp
 

Detailed Description

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
class sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >

A class for the Fully-Compressed Suffix Tree (FCST) proposed by Russo et al.

Template Parameters
t_csaType of a CSA (member of this type is accessible via member csa, default class is sdsl::wt).
t_deltaValue of the sampling parameter. Larger values result in lower space consumption while requiring more time. For t_delta = 0, delta = log n log log n is used.
t_s_supportType of a BPS structure (member accessible via member s_support, default class is sdsl::bp_support_sada),
t_bType of a bit vector for the leaf mapping (member accessible via member b, default class is sdsl::sd_vector),
t_depthType of an integer vector for the depth of the sampled nodes (member accessible via member depth_sampling, default class is sdsl::dac_vector),
t_sample_leavesBoolean value indicating whether leaves are to be sampled. This is helpful for debugging purposes.

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

A node v of the cst_fully 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 s.

Reference
Russo, Lu{\'\i}s and Navarro, Gonzalo and Oliveira, Arlindo L: Fully Compressed Suffix Trees. ACM Transactions on Algorithms (TALG), vol. 7, no. 4, p. 53, 2011

Definition at line 122 of file cst_fully.hpp.

Member Typedef Documentation

◆ alphabet_category

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef t_csa::alphabet_category sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::alphabet_category

Definition at line 139 of file cst_fully.hpp.

◆ b_select_0_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef t_b::select_0_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_select_0_type

Definition at line 135 of file cst_fully.hpp.

◆ b_select_1_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef t_b::select_1_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_select_1_type

Definition at line 136 of file cst_fully.hpp.

◆ b_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef t_b sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_type

Definition at line 134 of file cst_fully.hpp.

◆ char_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef t_csa::char_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::char_type

Definition at line 129 of file cst_fully.hpp.

◆ const_iterator

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef cst_dfs_const_forward_iterator<cst_fully> sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::const_iterator

Definition at line 125 of file cst_fully.hpp.

◆ csa_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef t_csa sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::csa_type

Definition at line 127 of file cst_fully.hpp.

◆ depth_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef t_depth sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth_type

Definition at line 137 of file cst_fully.hpp.

◆ index_category

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef cst_tag sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::index_category

Definition at line 140 of file cst_fully.hpp.

◆ lcp_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef lcp_fully<cst_fully> sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lcp_type

Definition at line 128 of file cst_fully.hpp.

◆ leaf_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::leaf_type

Definition at line 131 of file cst_fully.hpp.

◆ node_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef std::pair<size_type, size_type> sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::node_type

Definition at line 130 of file cst_fully.hpp.

◆ s_support_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef t_s_support sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::s_support_type

Definition at line 133 of file cst_fully.hpp.

◆ sampled_node_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::sampled_node_type

Definition at line 132 of file cst_fully.hpp.

◆ size_type

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
typedef t_csa::size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::size_type

Definition at line 126 of file cst_fully.hpp.

Constructor & Destructor Documentation

◆ cst_fully() [1/4]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::cst_fully ( )
default

Default constructor.

◆ cst_fully() [2/4]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::cst_fully ( const cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > &  cst)
inline

Copy constructor.

Definition at line 169 of file cst_fully.hpp.

◆ cst_fully() [3/4]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::cst_fully ( cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > &&  cst)
inline

Move constructor.

Definition at line 186 of file cst_fully.hpp.

◆ cst_fully() [4/4]

template<class t_csa , uint32_t t_delta, class t_s_support , class t_b , class t_depth , bool t_sample_leaves>
sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::cst_fully ( cache_config config)

Construct CST from file_map.

Definition at line 854 of file cst_fully.hpp.

Member Function Documentation

◆ ancestor()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
bool sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::ancestor ( node_type  v,
node_type  w 
) const
inline

Returns true iff v is an ancestor of w.

Definition at line 373 of file cst_fully.hpp.

◆ begin()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
const_iterator sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::begin ( ) const
inline

Definition at line 197 of file cst_fully.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
template<typename archive_t >
void sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Definition at line 289 of file cst_fully.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
template<typename archive_t >
void sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Definition at line 275 of file cst_fully.hpp.

◆ child() [1/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::child ( node_type  v,
char_type  c 
) const
inline

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

Parameters
vA node v.
cFirst character of the edge label from v to the desired child.
Returns
The child node w which edge label (v,w) starts with c or root() if it does not exist.
Time complexity
$ \Order{ \log m \cdot (\saaccess+\isaaccess) } $ where $ m $ is the number of leaves in the subtree rooted at node v.

Definition at line 687 of file cst_fully.hpp.

◆ child() [2/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::child ( node_type  v,
char_type  c,
size_type  d 
) const
inline

Definition at line 694 of file cst_fully.hpp.

◆ depth() [1/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth ( node_type  v) const
inline

Returns the depth of a node v.

Parameters
vThe node v.
Returns
The depth of node v.
Time complexity
$ \Order( \delta ) $ for inner nodes, $ \Order( \saaccess ) $ for leaves.

Definition at line 461 of file cst_fully.hpp.

◆ depth() [2/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth ( sampled_node_type  u) const
inline

Returns the depth of a sampled node u.

Parameters
uA sampled node u.
Returns
The depth of sampled node u.
Time complexity
$ \Order{1} $

Definition at line 445 of file cst_fully.hpp.

◆ depth_lca() [1/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth_lca ( leaf_type  l,
leaf_type  r,
size_type res_i,
sampled_node_type res_u 
) const
inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 575 of file cst_fully.hpp.

◆ depth_lca() [2/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth_lca ( leaf_type  l,
leaf_type  r,
size_type res_i,
sampled_node_type res_u,
std::vector< char_type > &  res_label 
) const
inline

Calculate the depth of the LCA of two leaves l and r.

Parameters
lThe index of leaf l.
rThe index of leaf r. $ r > l $
res_iThe index i for the ancestor used to determine the depth (return value).
res_uThe ancestor used to determine the depth (return value).
res_labelThe label from the found sampled node to the actual LCA.
Returns
The depth of the LCA of l and r.
Time complexity
$ \Order( \delta ) $

Definition at line 533 of file cst_fully.hpp.

◆ empty()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
bool sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::empty ( ) const
inline

Definition at line 195 of file cst_fully.hpp.

◆ end()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
const_iterator sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::end ( ) const
inline

Definition at line 203 of file cst_fully.hpp.

◆ is_leaf()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
bool sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::is_leaf ( node_type  v) const
inline

Returns true iff node v is a leaf.

Definition at line 323 of file cst_fully.hpp.

◆ lb()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
leaf_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lb ( node_type  v) const
inline

Returns the leftmost leaf (left boundary) of a node.

Definition at line 343 of file cst_fully.hpp.

◆ lca() [1/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lca ( leaf_type  l,
leaf_type  r 
) const
inline

Calculate the LCA of two leaves l and r.

Parameters
lThe index of leaf l.
rThe index of leaf r. $ r > l $
Returns
The LCA of l and r.
Time complexity
$ \Order( \delta \cdot ( 1 + t_{rank\_bwt} ) ) $

Definition at line 503 of file cst_fully.hpp.

◆ lca() [2/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lca ( node_type  v,
node_type  w 
) const
inline

Calculate the LCA of two nodes v and w.

Parameters
vThe node v.
wThe node w.
Returns
The LCA of v and w.
Time complexity
$ \Order( \delta \cdot ( 1 + t_{rank\_bwt} ) ) $

Definition at line 483 of file cst_fully.hpp.

◆ leftmost_leaf()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::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 362 of file cst_fully.hpp.

◆ load()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
void sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::load ( std::istream &  in)
inline

Load from a stream.

Parameters
inInputstream to load the data structure from.

Definition at line 261 of file cst_fully.hpp.

◆ lsa_leaf()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
sampled_node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lsa_leaf ( leaf_type  l) const
inline

Returns the LSA (lowest sampled ancestor) for a leaf with index l.

Parameters
vThe index of leaf l.
Returns
The LSA for the leaf with index l.
Time complexity
$ \Order{1} $

Definition at line 389 of file cst_fully.hpp.

◆ max_size()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
static size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::max_size ( )
inlinestatic

Definition at line 193 of file cst_fully.hpp.

◆ node()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::node ( size_type  lb,
size_type  rb 
) const
inline

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

Definition at line 340 of file cst_fully.hpp.

◆ operator!=()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
bool sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::operator!= ( cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > const &  other) const
inlinenoexcept

Inequality operator.

Definition at line 314 of file cst_fully.hpp.

◆ operator=() [1/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
cst_fully& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::operator= ( const cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > &  cst)
inline

Copy Assignment Operator.

Definition at line 206 of file cst_fully.hpp.

◆ operator=() [2/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
cst_fully& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::operator= ( cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > &&  cst)
inline

Move Assignment Operator.

Definition at line 217 of file cst_fully.hpp.

◆ operator==()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
bool sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::operator== ( cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > const &  other) const
inlinenoexcept

Equality operator.

Definition at line 306 of file cst_fully.hpp.

◆ parent()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::parent ( node_type  v) const
inline

Calculate the parent node of a node v.

Parameters
vThe node v.
Returns
The parent node of v or root() if v equals root().
Time complexity
$ \Order( \delta \cdot ( 1 + t_{rank\_bwt} ) ) $

Definition at line 665 of file cst_fully.hpp.

◆ pred()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
sampled_node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::pred ( leaf_type  v) const
inline

Returns the index of the last bracket in S before the leaf with index l.

Parameters
vThe index of leaf l.
Returns
The index of the last bracket in S before the leaf with index l.

Definition at line 380 of file cst_fully.hpp.

◆ rb()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
leaf_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::rb ( node_type  v) const
inline

Returns the rightmost leaf (right boundary) of a node.

Definition at line 346 of file cst_fully.hpp.

◆ rightmost_leaf()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::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 370 of file cst_fully.hpp.

◆ root()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::root ( ) const
inline

Returns the root of the suffix tree.

Definition at line 317 of file cst_fully.hpp.

◆ sampled_lca()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
sampled_node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::sampled_lca ( sampled_node_type  u,
sampled_node_type  q 
) const
inline

Returns the LCA of two nodes in the sampled tree.

Parameters
uThe sampled node u.
qThe sampled node q.
Returns
The lowest common ancestor of u and q in the sampled tree.
Time complexity
$ \Order{\rrenclose} $

Definition at line 424 of file cst_fully.hpp.

◆ sampled_node()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::sampled_node ( sampled_node_type  u) const
inline

Returns the node in the suffix tree corresponding to the node u in the sampled tree.

Parameters
vThe node u in the sampled tree.
Returns
The node in the suffix tree corresponding to the node u in the sampled tree.
Time complexity
$ \Order{1} $

Definition at line 406 of file cst_fully.hpp.

◆ sampled_root()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
sampled_node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::sampled_root ( ) const
inline

Returns the root of the sampled tree.

Definition at line 320 of file cst_fully.hpp.

◆ select_leaf()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::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 333 of file cst_fully.hpp.

◆ serialize()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::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 241 of file cst_fully.hpp.

◆ size() [1/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::size ( ) const
inline

Definition at line 191 of file cst_fully.hpp.

◆ size() [2/2]

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::size ( const 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} $

Definition at line 354 of file cst_fully.hpp.

◆ sl()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::sl ( node_type  v) const
inline

Compute the suffix link of a node v.

Parameters
vThe node v.
Returns
The suffix link of node v or root() if v equals root().
Time complexity
$ \Order( \delta \cdot ( 1 + t_{rank\_bwt} ) ) $

Definition at line 618 of file cst_fully.hpp.

◆ sn()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::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 652 of file cst_fully.hpp.

◆ wl()

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
node_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::wl ( node_type  v,
const char_type  c 
) const
inline

Compute the Weiner link of node v and character c.

Definition at line 638 of file cst_fully.hpp.

Member Data Documentation

◆ b

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
const b_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b = m_b

Definition at line 159 of file cst_fully.hpp.

◆ b_select_0

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
const b_select_0_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_select_0 = m_b_select0

Definition at line 160 of file cst_fully.hpp.

◆ b_select_1

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
const b_select_1_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_select_1 = m_b_select1

Definition at line 161 of file cst_fully.hpp.

◆ csa

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
const csa_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::csa = m_csa

Definition at line 156 of file cst_fully.hpp.

◆ delta

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
const size_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::delta = m_delta

Definition at line 155 of file cst_fully.hpp.

◆ depth_sampling

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
const depth_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth_sampling = m_depth

Definition at line 162 of file cst_fully.hpp.

◆ lcp

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
const lcp_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lcp = m_lcp

Definition at line 163 of file cst_fully.hpp.

◆ s

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
const bit_vector& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::s = m_s

Definition at line 157 of file cst_fully.hpp.

◆ s_support

template<class t_csa = csa_wt<>, uint32_t t_delta = 0, class t_s_support = bp_support_sada<>, class t_b = sd_vector<>, class t_depth = dac_vector<>, bool t_sample_leaves = false>
const s_support_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::s_support = m_s_support

Definition at line 158 of file cst_fully.hpp.


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