SDSL 3.0.1
Succinct Data Structure Library
sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel > Class Template Reference

A class for the Compressed Suffix Tree (CST) proposed by Ohlebusch and Gog. More...

#include <cst_sct3.hpp>

Public Types

typedef cst_dfs_const_forward_iterator< cst_sct3const_iterator
 
typedef cst_bottom_up_const_forward_iterator< cst_sct3const_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_sct3lcp_type
 
typedef t_bp_support bp_support_type
 
typedef t_csa::char_type char_type
 
typedef t_csa::string_type string_type
 
typedef bp_interval< size_typenode_type
 Type for the nodes in the tree. More...
 
typedef t_bv bv_type
 
typedef t_rank rank_type
 
typedef t_sel sel_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_sct3 ()=default
 Default constructor. More...
 
 cst_sct3 (cache_config &cache, bool build_only_bps=false)
 Construct CST from cache config. More...
 
 cst_sct3 (const cst_sct3 &cst)
 Copy constructor. More...
 
 cst_sct3 (cst_sct3 &&cst)
 Move constructor. More...
 
size_type size () const
 Number of leaves of the suffix tree. More...
 
bool empty () const
 Returns if the data structure is empty. More...
 
const_iterator begin () const
 Returns a const_iterator to the first element of a depth first traversal of the tree. More...
 
const_iterator begin (const node_type &v) const
 Returns a const_iterator to the first element of a depth first traversal of the subtree rooted at node v. More...
 
const_iterator end () const
 Returns a const_iterator to the element after the last element of a depth first traversal of the tree. More...
 
const_iterator end (const node_type &v) const
 Returns a const_iterator to the element past the end of a depth first traversal of the subtree rooted at node v. More...
 
const_bottom_up_iterator begin_bottom_up () const
 Returns an iterator to the first element of a bottom-up traversal of the tree. More...
 
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. More...
 
cst_sct3operator= (const cst_sct3 &cst)
 Assignment Operator. More...
 
cst_sct3operator= (cst_sct3 &&cst)
 Assignment Move 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
 Serialise (save) via cereal. More...
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 Serialise (load) via cereal. More...
 
bool operator== (cst_sct3 const &other) const noexcept
 Equality operator. More...
 
bool operator!= (cst_sct3 const &other) const noexcept
 Inequality operator. More...
 
node_type root () const
 Return the root of the suffix tree. More...
 
bool is_leaf (const node_type &v) const
 Decide if a node is a leaf. More...
 
node_type select_leaf (size_type i) const
 Return the i-th leaf (1-based from left to right). 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...
 
size_type lb (const node_type &v) const
 Calculates the index of the leftmost leaf in the corresponding suffix array. More...
 
size_type rb (const node_type &v) const
 Calculates the index of the rightmost leaf in the corresponding suffix array. More...
 
node_type parent (const node_type &v) const
 Calculate the parent node of a node v. More...
 
cst_node_child_proxy< cst_sct3children (const node_type &v) const
 Return a proxy object which allows iterating over the children of a node. More...
 
node_type sibling (const node_type &v) const
 Returns the next sibling of node v. More...
 
node_type select_child (const node_type &v, size_type i) const
 Get the i-th child of a node v. More...
 
size_type degree (const node_type &v) const
 Get the number of children of a node v. More...
 
node_type child (const 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. More...
 
node_type child (const node_type &v, const char_type c) const
 Get the child w of node v which edge label (v,w) starts with character c. More...
 
char_type edge (const node_type &v, size_type d) const
 Returns the d-th character (1-based indexing) of the edge-label pointing to v. More...
 
node_type lca (node_type v, node_type w) const
 Calculate the LCA of two nodes v and w More...
 
size_type depth (const node_type &v) const
 Returns the string depth of node v. More...
 
size_type node_depth (node_type v) const
 Returns the node depth of node v. More...
 
node_type sl (const node_type &v) const
 Compute the suffix link of node v. More...
 
node_type wl (const node_type &v, const char_type c) const
 Compute the Weiner link of node v and character c. More...
 
size_type sn (const node_type &v) const
 Computes the suffix number of a leaf node v. More...
 
size_type id (const node_type &v) const
 Computes a unique identification number for a node of the suffx tree in the range [0..nodes()-1]. More...
 
node_type inv_id (size_type id)
 Computes the node for such that id(v)=id. More...
 
size_type nodes () const
 Get the number of nodes 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 lcp-interval [lb..rb]. More...
 
size_type tlcp_idx (size_type i) const
 Maps an index i to the position in TLCP where LCP[i] can be found. More...
 

Static Public Member Functions

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

Public Attributes

const csa_typecsa = m_csa
 
const lcp_typelcp = m_lcp
 
const bit_vectorbp = m_bp
 
const bp_support_typebp_support = m_bp_support
 
const bv_typefirst_child_bv = m_first_child
 
const rank_typefirst_child_rank = m_first_child_rank
 
const sel_typefirst_child_select = m_first_child_select
 

Detailed Description

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
class sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >

A class for the Compressed Suffix Tree (CST) proposed by Ohlebusch and Gog.

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_rankType of rank structure which supports the bitvector which indicates the leftmost child of the nodes.

It also contains a sdsl::bit_vector which represents the BP sequence of the Super-Cartesian tree of the LCP array. This bitvector can be accessed via the member bp. Another sdsl::bit_vector stores information, if a node is the leftmost child of another node. This bitvector can be access via the member first_child_bv and takes n bits.

A node $v$ of the csa_sct is represented by an sdsl::bp_interval. The size of the sdsl::cst_sct3 is smaller than the size of a sdsl::cst_sada since the tree topology needs only $2n+n=3n$ bits in contrast to the $4n$ bits in sdsl::cst_sada.

Reference
Enno Ohlebusch, Johannes Fischer, Simon Gog: CST++. SPIRE 2010: 322-333
Applications of the CST
The compressed suffix tree could be used for string matching and many other application in sequence analysis. 17 applications are in the book "Algorithms on Strings, Trees, and Sequences" of Dan Gusfield.

Definition at line 89 of file cst_sct3.hpp.

Member Typedef Documentation

◆ alphabet_category

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef t_csa::alphabet_category sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::alphabet_category

Definition at line 112 of file cst_sct3.hpp.

◆ bp_support_type

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef t_bp_support sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::bp_support_type

Definition at line 101 of file cst_sct3.hpp.

◆ bv_type

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef t_bv sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::bv_type

Definition at line 105 of file cst_sct3.hpp.

◆ char_type

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef t_csa::char_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::char_type

Definition at line 102 of file cst_sct3.hpp.

◆ comp_char_type

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef t_csa::alphabet_type::comp_char_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::comp_char_type

Definition at line 109 of file cst_sct3.hpp.

◆ const_bottom_up_iterator

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef cst_bottom_up_const_forward_iterator<cst_sct3> sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::const_bottom_up_iterator

Definition at line 96 of file cst_sct3.hpp.

◆ const_iterator

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef cst_dfs_const_forward_iterator<cst_sct3> sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::const_iterator

Definition at line 95 of file cst_sct3.hpp.

◆ csa_type

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef t_csa sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::csa_type

Definition at line 99 of file cst_sct3.hpp.

◆ difference_type

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef ptrdiff_t sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::difference_type

Definition at line 98 of file cst_sct3.hpp.

◆ index_category

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef cst_tag sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::index_category

Definition at line 113 of file cst_sct3.hpp.

◆ lcp_type

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef t_lcp::template type<cst_sct3> sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::lcp_type

Definition at line 100 of file cst_sct3.hpp.

◆ node_type

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef bp_interval<size_type> sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::node_type

Type for the nodes in the tree.

Definition at line 104 of file cst_sct3.hpp.

◆ rank_type

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef t_rank sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::rank_type

Definition at line 106 of file cst_sct3.hpp.

◆ sel_type

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef t_sel sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::sel_type

Definition at line 107 of file cst_sct3.hpp.

◆ sigma_type

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef t_csa::alphabet_type::sigma_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::sigma_type

Definition at line 110 of file cst_sct3.hpp.

◆ size_type

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef t_csa::size_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::size_type

Definition at line 97 of file cst_sct3.hpp.

◆ string_type

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
typedef t_csa::string_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::string_type

Definition at line 103 of file cst_sct3.hpp.

Constructor & Destructor Documentation

◆ cst_sct3() [1/4]

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::cst_sct3 ( )
default

Default constructor.

◆ cst_sct3() [2/4]

template<class t_csa , class t_lcp , class t_bp_support , class t_bv , class t_rank , class t_sel >
sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::cst_sct3 ( cache_config cache,
bool  build_only_bps = false 
)

Construct CST from cache config.

Definition at line 1188 of file cst_sct3.hpp.

◆ cst_sct3() [3/4]

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::cst_sct3 ( const cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel > &  cst)
inline

Copy constructor.

Parameters
cstThe cst_sct3 which should be copied.
Time complexity
$ \Order{n} $, where $n=$cst_sct3.size()

Definition at line 355 of file cst_sct3.hpp.

◆ cst_sct3() [4/4]

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::cst_sct3 ( cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel > &&  cst)
inline

Move constructor.

Parameters
cstThe cst_sct3 which should be moved.

Definition at line 374 of file cst_sct3.hpp.

Member Function Documentation

◆ begin() [1/2]

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
const_iterator sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::begin ( ) const
inline

Returns a const_iterator to the first element of a depth first traversal of the tree.

Required for the STL Container Concept.

See also
end

Definition at line 413 of file cst_sct3.hpp.

◆ begin() [2/2]

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
const_iterator sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::begin ( const node_type 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 421 of file cst_sct3.hpp.

◆ begin_bottom_up()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
const_bottom_up_iterator sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::begin_bottom_up ( ) const
inline

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

Definition at line 441 of file cst_sct3.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_csa , class t_lcp , class t_bp_support , class t_bv , class t_rank , class t_sel >
template<typename archive_t >
void sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)

Serialise (load) via cereal.

Definition at line 1268 of file cst_sct3.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_csa , class t_lcp , class t_bp_support , class t_bv , class t_rank , class t_sel >
template<typename archive_t >
void sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const

Serialise (save) via cereal.

Definition at line 1254 of file cst_sct3.hpp.

◆ child() [1/2]

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::child ( const 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 854 of file cst_sct3.hpp.

◆ child() [2/2]

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::child ( const 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.

Parameters
vA valid tree node of the cst.
cFirst character on the edge label.
char_posReference which will hold the position (0-based) of the matching char c in the sorted text/suffix array.
Returns
The child node w which edge label (v,w) starts with c or root() if it does not exist.
Time complexity
$ \Order{(\saaccess+\isaaccess) \cdot \log\sigma + \lcpaccess} $

Definition at line 787 of file cst_sct3.hpp.

◆ children()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
cst_node_child_proxy< cst_sct3 > sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::children ( const 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 638 of file cst_sct3.hpp.

◆ degree()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
size_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::degree ( const node_type v) const
inline

Get the number of children of a node v.

Parameters
vA valid node v.
Returns
The number of children of node v.
Time complexity
$ \Order{\frac{\sigma}{w}} $, where w=64 is the word size, can be implemented in $\Order{1}$ with rank and select.

Definition at line 732 of file cst_sct3.hpp.

◆ depth()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
size_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::depth ( const node_type v) const
inline

Returns the string depth of node v.

Parameters
vA valid node of a cst_sct3.
Returns
The string depth of node v.
Time complexity
$ \Order{1} $ for non-leaves and $\Order{t_{SA}}$ for leaves

Definition at line 929 of file cst_sct3.hpp.

◆ edge()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
char_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::edge ( const 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) 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 869 of file cst_sct3.hpp.

◆ empty()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
bool sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::empty ( ) const
inline

Returns if the data structure is empty.

Required for the Container Concept of the STL.

See also
size

Definition at line 407 of file cst_sct3.hpp.

◆ end() [1/2]

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
const_iterator sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::end ( ) const
inline

Returns a const_iterator to the element after the last element of a depth first traversal of the tree.

Required for the STL Container Concept.

See also
begin.

Definition at line 431 of file cst_sct3.hpp.

◆ end() [2/2]

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
const_iterator sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::end ( const node_type 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 434 of file cst_sct3.hpp.

◆ end_bottom_up()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
const_bottom_up_iterator sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::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 449 of file cst_sct3.hpp.

◆ id()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
size_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::id ( const node_type v) const
inline

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

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

Definition at line 1052 of file cst_sct3.hpp.

◆ inv_id()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::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 $ \Order{\log size()} $ for inner nodes
See also
id(node_type v)

Definition at line 1080 of file cst_sct3.hpp.

◆ is_leaf()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
bool sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::is_leaf ( const node_type v) const
inline

Decide if a node is a leaf.

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

Definition at line 536 of file cst_sct3.hpp.

◆ lb()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
size_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::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 592 of file cst_sct3.hpp.

◆ lca()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::lca ( node_type  v,
node_type  w 
) const
inline

Calculate the LCA of two nodes v and w

Parameters
vThe first node.
wThe second node.
Returns
The lowest common ancestor of v and w.
Time complexity
$ \Order{\rrenclose}\   $

Definition at line 896 of file cst_sct3.hpp.

◆ leftmost_leaf()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::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 574 of file cst_sct3.hpp.

◆ load()

template<class t_csa , class t_lcp , class t_bp_support , class t_bv , class t_rank , class t_sel >
void sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::load ( std::istream &  in)

Load from a stream.

Parameters
inInputstream to load the data structure from.

Definition at line 1240 of file cst_sct3.hpp.

◆ max_size()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
static size_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::max_size ( )
inlinestatic

Returns the largest size that cst_sct3 can ever have.

Required for the Container Concept of the STL.

See also
size

Definition at line 401 of file cst_sct3.hpp.

◆ node()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::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 1159 of file cst_sct3.hpp.

◆ node_depth()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
size_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::node_depth ( node_type  v) const
inline

Returns the node depth of node v.

Parameters
vA valid node of a cst_sct3.
Returns
The node depth of node v.
Time complexity
$ \Order{z} $, where $z$ is the resulting node depth.
Note
Can be implemented in O(1) with o(n) space. See Jansson, Sadakane, Sung: Ultra-succinct Representation of Ordered Trees SODA 2007

Definition at line 956 of file cst_sct3.hpp.

◆ nodes()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
size_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::nodes ( ) const
inline

Get the number of nodes of the suffix tree.

Definition at line 1150 of file cst_sct3.hpp.

◆ operator!=()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
bool sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::operator!= ( cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel > const &  other) const
inlinenoexcept

Inequality operator.

Definition at line 517 of file cst_sct3.hpp.

◆ operator=() [1/2]

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
cst_sct3 & sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::operator= ( const cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel > &  cst)
inline

Assignment Operator.

Required for the Assignable Concept of the STL.

Definition at line 455 of file cst_sct3.hpp.

◆ operator=() [2/2]

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
cst_sct3 & sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::operator= ( cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel > &&  cst)
inline

Assignment Move Operator.

Required for the Assignable Concept of the STL.

Definition at line 469 of file cst_sct3.hpp.

◆ operator==()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
bool sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::operator== ( cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel > const &  other) const
inlinenoexcept

Equality operator.

Definition at line 508 of file cst_sct3.hpp.

◆ parent()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::parent ( const 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 the root if v==root().
Time complexity
$ \Order{1}$

Definition at line 610 of file cst_sct3.hpp.

◆ rb()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
size_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::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 602 of file cst_sct3.hpp.

◆ rightmost_leaf()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::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 582 of file cst_sct3.hpp.

◆ root()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::root ( ) const
inline

Return the root of the suffix tree.

Time complexity O(1)
$ \Order{1} $

Definition at line 527 of file cst_sct3.hpp.

◆ select_child()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::select_child ( const 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.
Returns
The i-th child node of v or root() if v has no i-th child.
Time complexity
$ \Order{\frac{\sigma}{w}} $, where w=64 is the word size, can be implemented in $\Order{1}$ with rank and select.
Precondition
$ 1 \leq i \leq degree(v) $

Definition at line 701 of file cst_sct3.hpp.

◆ select_leaf()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::select_leaf ( size_type  i) const
inline

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

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

Definition at line 546 of file cst_sct3.hpp.

◆ serialize()

template<class t_csa , class t_lcp , class t_bp_support , class t_bv , class t_rank , class t_sel >
auto sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::serialize ( std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
) const

Serialize to a stream.

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

Definition at line 1221 of file cst_sct3.hpp.

◆ sibling()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::sibling ( const 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 650 of file cst_sct3.hpp.

◆ size() [1/2]

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
size_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::size ( ) const
inline

Number of leaves of the suffix tree.

Required for the Container Concept of the STL.

See also
max_size, empty

Definition at line 395 of file cst_sct3.hpp.

◆ size() [2/2]

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
size_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::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 566 of file cst_sct3.hpp.

◆ sl()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::sl ( const node_type v) const
inline

Compute the suffix link of node v.

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

Definition at line 974 of file cst_sct3.hpp.

◆ sn()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
size_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::sn ( const node_type v) const
inline

Computes the suffix number of a leaf node v.

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

Definition at line 1039 of file cst_sct3.hpp.

◆ tlcp_idx()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
size_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::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 1176 of file cst_sct3.hpp.

◆ wl()

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
node_type sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::wl ( const node_type v,
const char_type  c 
) const
inline

Compute the Weiner link of node v and character c.

Parameters
vA valid node of a cst_sct3.
cThe character which should be prepended to the string of the current node.
Returns
root() if the Weiner link of (v, c) does not exist, otherwise the Weiner link is returned.
Time complexity
$ \Order{ t_{rank\_bwt} } $

Definition at line 1012 of file cst_sct3.hpp.

Member Data Documentation

◆ bp

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
const bit_vector& sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::bp = m_bp

Definition at line 333 of file cst_sct3.hpp.

◆ bp_support

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
const bp_support_type& sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::bp_support = m_bp_support

Definition at line 334 of file cst_sct3.hpp.

◆ csa

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
const csa_type& sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::csa = m_csa

Definition at line 331 of file cst_sct3.hpp.

◆ first_child_bv

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
const bv_type& sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::first_child_bv = m_first_child

Definition at line 336 of file cst_sct3.hpp.

◆ first_child_rank

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
const rank_type& sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::first_child_rank = m_first_child_rank

Definition at line 337 of file cst_sct3.hpp.

◆ first_child_select

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
const sel_type& sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::first_child_select = m_first_child_select

Definition at line 338 of file cst_sct3.hpp.

◆ lcp

template<class t_csa = csa_wt<>, class t_lcp = lcp_dac<>, class t_bp_support = bp_support_sada<>, class t_bv = bit_vector, class t_rank = typename std::conditional<std::is_same<t_bv, bit_vector>::value, rank_support_v5<>, typename t_bv::rank_1_type>::type, class t_sel = typename std::conditional<std::is_same<t_bv, bit_vector>::value and std::is_same<typename t_csa::alphabet_category, byte_alphabet_tag>::value, select_support_scan<>, typename t_bv::select_1_type>::type>
const lcp_type& sdsl::cst_sct3< t_csa, t_lcp, t_bp_support, t_bv, t_rank, t_sel >::lcp = m_lcp

Definition at line 332 of file cst_sct3.hpp.


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