SDSL
3.0.0
Succinct Data Structure Library
|
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_fully > | const_iterator |
typedef t_csa::size_type | size_type |
typedef t_csa | csa_type |
typedef lcp_fully< cst_fully > | lcp_type |
typedef t_csa::char_type | char_type |
typedef std::pair< size_type, size_type > | node_type |
typedef size_type | leaf_type |
typedef size_type | sampled_node_type |
typedef t_s_support | s_support_type |
typedef t_b | b_type |
typedef t_b::select_0_type | b_select_0_type |
typedef t_b::select_1_type | b_select_1_type |
typedef t_depth | depth_type |
typedef t_csa::alphabet_category | alphabet_category |
typedef cst_tag | index_category |
Public Member Functions | |
cst_fully ()=default | |
Default constructor. More... | |
cst_fully (const cst_fully &cst) | |
Copy constructor. More... | |
cst_fully (cst_fully &&cst) | |
Move constructor. More... | |
cst_fully (cache_config &config) | |
Construct CST from file_map. More... | |
size_type | size () const |
bool | empty () const |
const_iterator | begin () const |
const_iterator | end () const |
cst_fully & | operator= (const cst_fully &cst) |
Copy Assignment Operator. More... | |
cst_fully & | operator= (cst_fully &&cst) |
Move Assignment Operator. More... | |
size_type | serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const |
Serialize to a stream. More... | |
void | load (std::istream &in) |
Load from a stream. More... | |
template<typename archive_t > | |
void | CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const |
template<typename archive_t > | |
void | CEREAL_LOAD_FUNCTION_NAME (archive_t &ar) |
bool | operator== (cst_fully const &other) const noexcept |
Equality operator. More... | |
bool | operator!= (cst_fully const &other) const noexcept |
Inequality operator. More... | |
node_type | root () const |
Returns the root of the suffix tree. More... | |
sampled_node_type | sampled_root () const |
Returns the root of the sampled tree. More... | |
bool | is_leaf (node_type v) const |
Returns true iff node v is a leaf. More... | |
node_type | select_leaf (size_type i) const |
Return the i-th leaf (1-based from left to right) of the suffix tree. More... | |
node_type | node (size_type lb, size_type rb) const |
Get the node in the suffix tree which corresponds to the sa-interval [lb..rb]. More... | |
leaf_type | lb (node_type v) const |
Returns the leftmost leaf (left boundary) of a node. More... | |
leaf_type | rb (node_type v) const |
Returns the rightmost leaf (right boundary) of a node. More... | |
size_type | size (const node_type &v) const |
Calculate the number of leaves in the subtree rooted at node v. More... | |
node_type | leftmost_leaf (const node_type v) const |
Calculates the leftmost leaf in the subtree rooted at node v. More... | |
node_type | rightmost_leaf (const node_type v) const |
Calculates the rightmost leaf in the subtree rooted at node v. More... | |
bool | ancestor (node_type v, node_type w) const |
Returns true iff v is an ancestor of w. More... | |
sampled_node_type | pred (leaf_type v) const |
Returns the index of the last bracket in S before the leaf with index l. More... | |
sampled_node_type | lsa_leaf (leaf_type l) const |
Returns the LSA (lowest sampled ancestor) for a leaf with index l. More... | |
node_type | sampled_node (sampled_node_type u) const |
Returns the node in the suffix tree corresponding to the node u in the sampled tree. More... | |
sampled_node_type | sampled_lca (sampled_node_type u, sampled_node_type q) const |
Returns the LCA of two nodes in the sampled tree. More... | |
size_type | depth (sampled_node_type u) const |
Returns the depth of a sampled node u. More... | |
size_type | depth (node_type v) const |
Returns the depth of a node v. More... | |
node_type | lca (node_type v, node_type w) const |
Calculate the LCA of two nodes v and w. More... | |
node_type | lca (leaf_type l, leaf_type r) const |
Calculate the LCA of two leaves l and r. More... | |
size_type | depth_lca (leaf_type l, leaf_type r, size_type &res_i, sampled_node_type &res_u, std::vector< char_type > &res_label) const |
Calculate the depth of the LCA of two leaves l and r. More... | |
size_type | depth_lca (leaf_type l, leaf_type r, size_type &res_i, sampled_node_type &res_u) const |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More... | |
node_type | sl (node_type v) const |
Compute the suffix link of a node v. More... | |
node_type | wl (node_type v, const char_type c) const |
Compute the Weiner link of node v and character c. More... | |
size_type | sn (node_type v) const |
Compute the suffix number of a leaf node v. More... | |
node_type | parent (node_type v) const |
Calculate the parent node of a node v. More... | |
node_type | child (node_type v, char_type c) const |
Get the child w of node v which edge label (v,w) starts with character c. More... | |
node_type | child (node_type v, char_type c, size_type d) const |
Static Public Member Functions | |
static size_type | max_size () |
Public Attributes | |
const size_type & | delta = m_delta |
const csa_type & | csa = m_csa |
const bit_vector & | s = m_s |
const s_support_type & | s_support = m_s_support |
const b_type & | b = m_b |
const b_select_0_type & | b_select_0 = m_b_select0 |
const b_select_1_type & | b_select_1 = m_b_select1 |
const depth_type & | depth_sampling = m_depth |
const lcp_type & | lcp = m_lcp |
A class for the Fully-Compressed Suffix Tree (FCST) proposed by Russo et al.
t_csa | Type of a CSA (member of this type is accessible via member csa , default class is sdsl::wt). |
t_delta | Value 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_support | Type of a BPS structure (member accessible via member s_support , default class is sdsl::bp_support_sada), |
t_b | Type of a bit vector for the leaf mapping (member accessible via member b , default class is sdsl::sd_vector), |
t_depth | Type 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_leaves | Boolean 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 that corresponds to
v
in s
.
Definition at line 122 of file cst_fully.hpp.
typedef t_csa::alphabet_category sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::alphabet_category |
Definition at line 139 of file cst_fully.hpp.
typedef t_b::select_0_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_select_0_type |
Definition at line 135 of file cst_fully.hpp.
typedef t_b::select_1_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_select_1_type |
Definition at line 136 of file cst_fully.hpp.
typedef t_b sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_type |
Definition at line 134 of file cst_fully.hpp.
typedef t_csa::char_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::char_type |
Definition at line 129 of file cst_fully.hpp.
typedef cst_dfs_const_forward_iterator<cst_fully> sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::const_iterator |
Definition at line 125 of file cst_fully.hpp.
typedef t_csa sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::csa_type |
Definition at line 127 of file cst_fully.hpp.
typedef t_depth sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth_type |
Definition at line 137 of file cst_fully.hpp.
typedef cst_tag sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::index_category |
Definition at line 140 of file cst_fully.hpp.
typedef lcp_fully<cst_fully> sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lcp_type |
Definition at line 128 of file cst_fully.hpp.
typedef size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::leaf_type |
Definition at line 131 of file cst_fully.hpp.
typedef std::pair<size_type, size_type> sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::node_type |
Definition at line 130 of file cst_fully.hpp.
typedef t_s_support sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::s_support_type |
Definition at line 133 of file cst_fully.hpp.
typedef size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::sampled_node_type |
Definition at line 132 of file cst_fully.hpp.
typedef t_csa::size_type sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::size_type |
Definition at line 126 of file cst_fully.hpp.
|
default |
Default constructor.
|
inline |
Copy constructor.
Definition at line 169 of file cst_fully.hpp.
|
inline |
Move constructor.
Definition at line 186 of file cst_fully.hpp.
sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::cst_fully | ( | cache_config & | config | ) |
Construct CST from file_map.
Definition at line 854 of file cst_fully.hpp.
|
inline |
Returns true iff v is an ancestor of w.
Definition at line 373 of file cst_fully.hpp.
|
inline |
Definition at line 197 of file cst_fully.hpp.
|
inline |
Definition at line 289 of file cst_fully.hpp.
|
inline |
Definition at line 275 of file cst_fully.hpp.
|
inline |
Get the child w of node v which edge label (v,w) starts with character c.
v | A node v. |
c | First character of the edge label from v to the desired child. |
Definition at line 687 of file cst_fully.hpp.
|
inline |
Definition at line 694 of file cst_fully.hpp.
|
inline |
Returns the depth of a node v.
v | The node v. |
Definition at line 461 of file cst_fully.hpp.
|
inline |
Returns the depth of a sampled node u.
u | A sampled node u. |
Definition at line 445 of file cst_fully.hpp.
|
inline |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
Definition at line 575 of file cst_fully.hpp.
|
inline |
Calculate the depth of the LCA of two leaves l and r.
l | The index of leaf l. |
r | The index of leaf r. ![]() |
res_i | The index i for the ancestor used to determine the depth (return value). |
res_u | The ancestor used to determine the depth (return value). |
res_label | The label from the found sampled node to the actual LCA. |
Definition at line 533 of file cst_fully.hpp.
|
inline |
Definition at line 195 of file cst_fully.hpp.
|
inline |
Definition at line 203 of file cst_fully.hpp.
|
inline |
Returns true iff node v is a leaf.
Definition at line 323 of file cst_fully.hpp.
|
inline |
Returns the leftmost leaf (left boundary) of a node.
Definition at line 343 of file cst_fully.hpp.
|
inline |
Calculate the LCA of two leaves l and r.
l | The index of leaf l. |
r | The index of leaf r. ![]() |
Definition at line 503 of file cst_fully.hpp.
|
inline |
Calculate the LCA of two nodes v and w.
v | The node v. |
w | The node w. |
Definition at line 483 of file cst_fully.hpp.
|
inline |
Calculates the leftmost leaf in the subtree rooted at node v.
v | A valid node of the suffix tree. |
Definition at line 362 of file cst_fully.hpp.
|
inline |
Load from a stream.
in | Inputstream to load the data structure from. |
Definition at line 261 of file cst_fully.hpp.
|
inline |
Returns the LSA (lowest sampled ancestor) for a leaf with index l.
v | The index of leaf l. |
Definition at line 389 of file cst_fully.hpp.
|
inlinestatic |
Definition at line 193 of file cst_fully.hpp.
|
inline |
Get the node in the suffix tree which corresponds to the sa-interval [lb..rb].
Definition at line 340 of file cst_fully.hpp.
|
inlinenoexcept |
Inequality operator.
Definition at line 314 of file cst_fully.hpp.
|
inline |
Copy Assignment Operator.
Definition at line 206 of file cst_fully.hpp.
|
inline |
Move Assignment Operator.
Definition at line 217 of file cst_fully.hpp.
|
inlinenoexcept |
Equality operator.
Definition at line 306 of file cst_fully.hpp.
|
inline |
Calculate the parent node of a node v.
v | The node v. |
Definition at line 665 of file cst_fully.hpp.
|
inline |
Returns the index of the last bracket in S before the leaf with index l.
v | The index of leaf l. |
Definition at line 380 of file cst_fully.hpp.
|
inline |
Returns the rightmost leaf (right boundary) of a node.
Definition at line 346 of file cst_fully.hpp.
|
inline |
Calculates the rightmost leaf in the subtree rooted at node v.
v | A valid node of the suffix tree. |
Definition at line 370 of file cst_fully.hpp.
|
inline |
Returns the root of the suffix tree.
Definition at line 317 of file cst_fully.hpp.
|
inline |
Returns the LCA of two nodes in the sampled tree.
u | The sampled node u. |
q | The sampled node q. |
Definition at line 424 of file cst_fully.hpp.
|
inline |
Returns the node in the suffix tree corresponding to the node u in the sampled tree.
v | The node u in the sampled tree. |
Definition at line 406 of file cst_fully.hpp.
|
inline |
Returns the root of the sampled tree.
Definition at line 320 of file cst_fully.hpp.
|
inline |
Return the i-th leaf (1-based from left to right) of the suffix tree.
i | 1-based position of the leaf. ![]() |
Definition at line 333 of file cst_fully.hpp.
|
inline |
Serialize to a stream.
out | Outstream to write the data structure. |
Definition at line 241 of file cst_fully.hpp.
|
inline |
Definition at line 191 of file cst_fully.hpp.
|
inline |
Calculate the number of leaves in the subtree rooted at node v.
v | A valid node of the suffix tree. |
Definition at line 354 of file cst_fully.hpp.
|
inline |
Compute the suffix link of a node v.
v | The node v. |
Definition at line 618 of file cst_fully.hpp.
|
inline |
Compute the suffix number of a leaf node v.
v | A valid leaf node of a cst_sada. |
Definition at line 652 of file cst_fully.hpp.
|
inline |
Compute the Weiner link of node v and character c.
Definition at line 638 of file cst_fully.hpp.
const b_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b = m_b |
Definition at line 159 of file cst_fully.hpp.
const b_select_0_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_select_0 = m_b_select0 |
Definition at line 160 of file cst_fully.hpp.
const b_select_1_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::b_select_1 = m_b_select1 |
Definition at line 161 of file cst_fully.hpp.
const csa_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::csa = m_csa |
Definition at line 156 of file cst_fully.hpp.
const size_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::delta = m_delta |
Definition at line 155 of file cst_fully.hpp.
const depth_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::depth_sampling = m_depth |
Definition at line 162 of file cst_fully.hpp.
const lcp_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::lcp = m_lcp |
Definition at line 163 of file cst_fully.hpp.
const bit_vector& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::s = m_s |
Definition at line 157 of file cst_fully.hpp.
const s_support_type& sdsl::cst_fully< t_csa, t_delta, t_s_support, t_b, t_depth, t_sample_leaves >::s_support = m_s_support |
Definition at line 158 of file cst_fully.hpp.