SDSL 3.0.3
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. | |
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_fully & | operator= (cst_fully const &cst) |
Copy Assignment Operator. | |
cst_fully & | operator= (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 |
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 v
in s
.
Definition at line 151 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 168 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 164 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 165 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 163 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 158 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 154 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 156 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 166 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 169 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 157 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 160 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 159 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 162 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 161 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 155 of file cst_fully.hpp.
|
default |
Default constructor.
|
inline |
Copy constructor.
Definition at line 198 of file cst_fully.hpp.
|
inline |
Move constructor.
Definition at line 215 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 1000 of file cst_fully.hpp.
|
inline |
Returns true iff v is an ancestor of w.
Definition at line 450 of file cst_fully.hpp.
|
inline |
Definition at line 238 of file cst_fully.hpp.
|
inline |
Definition at line 336 of file cst_fully.hpp.
|
inline |
Definition at line 322 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 803 of file cst_fully.hpp.
|
inline |
Definition at line 813 of file cst_fully.hpp.
|
inline |
Returns the depth of a node v.
v | The node v. |
Definition at line 556 of file cst_fully.hpp.
|
inline |
Returns the depth of a sampled node u.
u | A sampled node u. |
Definition at line 540 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 679 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 634 of file cst_fully.hpp.
|
inline |
Definition at line 233 of file cst_fully.hpp.
|
inline |
Definition at line 247 of file cst_fully.hpp.
|
inline |
Returns true iff node v is a leaf.
Definition at line 379 of file cst_fully.hpp.
|
inline |
Returns the leftmost leaf (left boundary) of a node.
Definition at line 405 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 601 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 578 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 433 of file cst_fully.hpp.
|
inline |
Load from a stream.
in | Inputstream to load the data structure from. |
Definition at line 308 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 472 of file cst_fully.hpp.
|
inlinestatic |
Definition at line 228 of file cst_fully.hpp.
|
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.
|
inlinenoexcept |
Inequality operator.
Definition at line 361 of file cst_fully.hpp.
|
inline |
Move Assignment Operator.
Definition at line 264 of file cst_fully.hpp.
|
inline |
Copy Assignment Operator.
Definition at line 253 of file cst_fully.hpp.
|
inlinenoexcept |
Equality operator.
Definition at line 353 of file cst_fully.hpp.
|
inline |
Calculate the parent node of a node v.
v | The node v. |
Definition at line 775 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 460 of file cst_fully.hpp.
|
inline |
Returns the rightmost leaf (right boundary) of a node.
Definition at line 411 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 444 of file cst_fully.hpp.
|
inline |
Returns the root of the suffix tree.
Definition at line 367 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 510 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 492 of file cst_fully.hpp.
|
inline |
Returns the root of the sampled tree.
Definition at line 373 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 392 of file cst_fully.hpp.
|
inline |
Serialize to a stream.
out | Outstream to write the data structure. |
Definition at line 288 of file cst_fully.hpp.
|
inline |
Definition at line 223 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 422 of file cst_fully.hpp.
|
inline |
Compute the suffix link of a node v.
v | The node v. |
Definition at line 725 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 762 of file cst_fully.hpp.
|
inline |
Compute the Weiner link of node v and character c.
Definition at line 748 of file cst_fully.hpp.
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_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_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_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.
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_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_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.
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_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.