SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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.
 cst_fully (cst_fully const &cst)
 Copy constructor.
 cst_fully (cst_fully &&cst)
 Move constructor.
 cst_fully (cache_config &config)
 Construct CST from file_map.
size_type size () const
bool empty () const
const_iterator begin () const
const_iterator end () const
cst_fullyoperator= (cst_fully const &cst)
 Copy Assignment Operator.
cst_fullyoperator= (cst_fully &&cst)
 Move Assignment 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)
bool operator== (cst_fully const &other) const noexcept
 Equality operator.
bool operator!= (cst_fully const &other) const noexcept
 Inequality operator.
node_type root () const
 Returns the root of the suffix tree.
sampled_node_type sampled_root () const
 Returns the root of the sampled tree.
bool is_leaf (node_type v) const
 Returns true iff node v is a leaf.
node_type select_leaf (size_type i) const
 Return the i-th leaf (1-based from left to right) 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 sa-interval [lb..rb].
leaf_type lb (node_type v) const
 Returns the leftmost leaf (left boundary) of a node.
leaf_type rb (node_type v) const
 Returns the rightmost leaf (right boundary) of a node.
size_type size (node_type const &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.
bool ancestor (node_type v, node_type w) const
 Returns true iff v is an ancestor of w.
sampled_node_type pred (leaf_type v) const
 Returns the index of the last bracket in S before the leaf with index l.
sampled_node_type lsa_leaf (leaf_type l) const
 Returns the LSA (lowest sampled ancestor) for a leaf with index l.
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.
sampled_node_type sampled_lca (sampled_node_type u, sampled_node_type q) const
 Returns the LCA of two nodes in the sampled tree.
size_type depth (sampled_node_type u) const
 Returns the depth of a sampled node u.
size_type depth (node_type v) const
 Returns the depth of a node v.
node_type lca (node_type v, node_type w) const
 Calculate the LCA of two nodes v and w.
node_type lca (leaf_type l, leaf_type r) const
 Calculate the LCA of two leaves l and r.
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.
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.
node_type sl (node_type v) const
 Compute the suffix link of a node v.
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.
node_type parent (node_type v) const
 Calculate the parent node of a node v.
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.
node_type child (node_type v, char_type c, size_type d) const

Static Public Member Functions

static size_type max_size ()

Public Attributes

size_type const & delta = m_delta
csa_type const & csa = m_csa
bit_vector const & s = m_s
s_support_type const & s_support = m_s_support
b_type const & b = m_b
b_select_0_type const & b_select_0 = m_b_select0
b_select_1_type const & b_select_1 = m_b_select1
depth_type const & depth_sampling = m_depth
lcp_type const & lcp = 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 151 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 168 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 164 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 165 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 163 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 158 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 154 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 156 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 166 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 169 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 157 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 160 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 159 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 162 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 161 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 155 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 ( cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > const & cst)
inline

Copy constructor.

Definition at line 198 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 215 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 1000 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 450 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 238 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 336 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 322 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 803 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 813 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 556 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 540 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 679 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 634 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 233 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 247 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 379 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 405 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 601 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 578 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 433 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 308 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 472 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>
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 228 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 399 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 361 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= ( cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves > && cst)
inline

Move Assignment Operator.

Definition at line 264 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 > const & cst)
inline

Copy Assignment Operator.

Definition at line 253 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 353 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 775 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 460 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 411 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 444 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 367 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 510 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 492 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 373 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 392 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 288 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 223 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 ( node_type const & 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 422 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 725 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 762 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 748 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>
b_type const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b = m_b

Definition at line 188 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>
b_select_0_type const& 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 189 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>
b_select_1_type const& 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 190 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>
csa_type const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::csa = m_csa

Definition at line 185 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>
size_type const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::delta = m_delta

Definition at line 184 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>
depth_type const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth_sampling = m_depth

Definition at line 191 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>
lcp_type const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lcp = m_lcp

Definition at line 192 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>
bit_vector const& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::s = m_s

Definition at line 186 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>
s_support_type const& 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 187 of file cst_fully.hpp.


The documentation for this class was generated from the following file:
  • /builddir/build/BUILD/sdsl-lite-3.0.3-build/sdsl-lite-3.0.3/include/sdsl/cst_fully.hpp