SDSL 3.0.2
Succinct Data Structure Library
|
A class for the Compressed Suffix Tree (CST) proposed by Sadakane. More...
#include <cst_sada.hpp>
Public Types | |
typedef cst_dfs_const_forward_iterator< cst_sada > | const_iterator |
typedef cst_bottom_up_const_forward_iterator< cst_sada > | const_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_sada > | lcp_type |
typedef t_csa::char_type | char_type |
typedef t_csa::string_type | string_type |
typedef size_type | node_type |
Type for the nodes in the tree. | |
typedef t_bp_support | bp_support_type |
typedef t_rank_10 | rank_10_type |
typedef t_select_10 | select_10_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_sada ()=default | |
Default constructor. | |
cst_sada (cst_sada const &cst) | |
Copy constructor. | |
cst_sada (cst_sada &&cst) | |
Move constructor. | |
cst_sada (cache_config &config) | |
Construct CST from file_map. | |
size_type | size () const |
Number of leaves in the suffix tree. | |
bool | empty () const |
Returns if the data strucutre is empty. | |
const_iterator | begin () const |
Returns a const_iterator to the first element. | |
const_iterator | begin (node_type const &v) const |
Returns a const_iterator to the first element of a depth first traversal of the subtree rooted at node v. | |
const_iterator | end () const |
Returns a const_iterator to the element after the last element. | |
const_iterator | end (node_type const &v) const |
Returns a const_iterator to the element past the end of a depth first traversal of the subtree rooted at node v. | |
const_bottom_up_iterator | begin_bottom_up () const |
Returns an iterator to the first element of a bottom-up traversal of the tree. | |
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. | |
cst_sada & | operator= (cst_sada const &cst) |
Assignment Operator. | |
cst_sada & | operator= (cst_sada &&cst) |
Move assignment Operator. | |
bool | operator== (cst_sada const &other) const noexcept |
Equality operator. | |
bool | operator!= (cst_sada const &other) const noexcept |
Inequality 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) |
node_type | root () const |
Return the root of the suffix tree. | |
bool | is_leaf (node_type v) const |
Decide if a node is a leaf in the suffix tree. | |
node_type | select_leaf (size_type i) const |
Return the i-th leaf (1-based from left to right) of the suffix tree. | |
size_type | depth (node_type v) const |
Returns the depth of node v. | |
size_type | node_depth (node_type v) const |
Returns the node depth of node v. | |
size_type | size (node_type 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. | |
size_type | lb (const node_type v) const |
Calculates the index of the leftmost leaf in the corresponding suffix array. | |
size_type | rb (const node_type v) const |
Calculates the index of the rightmost leaf in the corresponding suffix array. | |
node_type | parent (node_type v) const |
Calculate the parent node of a node v. | |
cst_node_child_proxy< cst_sada > | children (node_type v) const |
Return a proxy object which allows iterating over the children of a node. | |
node_type | sibling (node_type v) const |
Returns the next sibling of node v. | |
node_type | child (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. | |
node_type | child (node_type v, const char_type c) const |
Get the child w of node v which edge label (v,w) starts with character c. | |
node_type | select_child (node_type v, size_type i) const |
Get the i-th child of a node v. | |
char_type | edge (node_type v, size_type d) const |
Returns the d-th character (1-based indexing) of the edge-label pointing to v. | |
node_type | lca (node_type v, node_type w) const |
Calculate the lowest common ancestor (lca) of two nodes v and w of the suffix tree. | |
node_type | sl (node_type v) const |
Compute the suffix link of node v. | |
node_type | sl (node_type v, size_type i) const |
Compute the suffix link of node v applied a number of times consecutively. | |
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. | |
size_type | id (node_type v) const |
Computes a unique identification number for a node of the suffix tree in the range [0..nodes()-1]. | |
size_type | inv_id (size_type id) |
Computes the node for such that id(v)=id. | |
size_type | nodes () const |
Get the number of nodes 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 lcp-interval [lb..rb]. | |
size_type | degree (node_type v) const |
Get the number of children of a node v. | |
size_type | tlcp_idx (size_type i) const |
Maps an index i to the position in TLCP where LCP[i] can be found. | |
Static Public Member Functions | |
static size_type | max_size () |
Returns the maximal lenght of text for that a suffix tree can be build. | |
Public Attributes | |
t_csa const & | csa = m_csa |
lcp_type const & | lcp = m_lcp |
bit_vector const & | bp = m_bp |
bp_support_type const & | bp_support = m_bp_support |
rank_10_type const & | bp_rank_10 = m_bp_rank10 |
select_10_type const & | bp_select_10 = m_bp_select10 |
A class for the Compressed Suffix Tree (CST) proposed by Sadakane.
t_csa | Type of a CSA (member of this type is accessible via member csa , default class is sdsl::csa_sada). |
t_lcp | Type of a LCP structure (member is accessible via member lcp , default class is sdsl::lcp_support_sada), |
t_bp_support | Type of a BPS structure (member accessible via member bp_support , default class is sdsl::bp_support_sada), |
t_rank_10 | Type of a rank structure for the 2-bit pattern 10 (accessible via member bp_rank_10 , default class is sdsl::rank_support_v5) |
t_select_10 | Type of a select structure for the 2-bit pattern 10 (accessible via member ![]() |
It also contains a sdsl::bit_vector which represents the balanced parentheses sequence of the suffix tree. This bit_vector can be accessed via member bp
.
A node v
of the csa_sada
is represented by an integer i
which corresponds to the position of the opening parenthesis of the parentheses pair v
in bp
.
Definition at line 74 of file cst_sada.hpp.
typedef t_csa::alphabet_category sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::alphabet_category |
Definition at line 96 of file cst_sada.hpp.
typedef t_bp_support sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::bp_support_type |
Definition at line 89 of file cst_sada.hpp.
typedef t_csa::char_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::char_type |
Definition at line 86 of file cst_sada.hpp.
typedef t_csa::alphabet_type::comp_char_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::comp_char_type |
Definition at line 93 of file cst_sada.hpp.
typedef cst_bottom_up_const_forward_iterator<cst_sada> sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::const_bottom_up_iterator |
Definition at line 81 of file cst_sada.hpp.
typedef cst_dfs_const_forward_iterator<cst_sada> sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::const_iterator |
Definition at line 80 of file cst_sada.hpp.
typedef t_csa sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::csa_type |
Definition at line 84 of file cst_sada.hpp.
typedef ptrdiff_t sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::difference_type |
Definition at line 83 of file cst_sada.hpp.
typedef cst_tag sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::index_category |
Definition at line 97 of file cst_sada.hpp.
typedef t_lcp::template type<cst_sada> sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::lcp_type |
Definition at line 85 of file cst_sada.hpp.
typedef size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::node_type |
Type for the nodes in the tree.
Definition at line 88 of file cst_sada.hpp.
typedef t_rank_10 sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::rank_10_type |
Definition at line 90 of file cst_sada.hpp.
typedef t_select_10 sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::select_10_type |
Definition at line 91 of file cst_sada.hpp.
typedef t_csa::alphabet_type::sigma_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::sigma_type |
Definition at line 94 of file cst_sada.hpp.
typedef t_csa::size_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::size_type |
Definition at line 82 of file cst_sada.hpp.
typedef t_csa::string_type sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::string_type |
Definition at line 87 of file cst_sada.hpp.
|
default |
Default constructor.
|
inline |
Copy constructor.
Definition at line 127 of file cst_sada.hpp.
|
inline |
Move constructor.
Definition at line 141 of file cst_sada.hpp.
|
inline |
Construct CST from file_map.
Definition at line 155 of file cst_sada.hpp.
|
inline |
Returns a const_iterator to the first element.
Required for the STL Container Concept.
Definition at line 295 of file cst_sada.hpp.
|
inline |
Returns a const_iterator to the first element of a depth first traversal of the subtree rooted at node v.
Definition at line 303 of file cst_sada.hpp.
|
inline |
Returns an iterator to the first element of a bottom-up traversal of the tree.
Definition at line 328 of file cst_sada.hpp.
|
inline |
Definition at line 433 of file cst_sada.hpp.
|
inline |
Definition at line 422 of file cst_sada.hpp.
|
inline |
Get the child w of node v which edge label (v,w) starts with character c.
Definition at line 676 of file cst_sada.hpp.
|
inline |
Get the child w of node v which edge label (v,w) starts with character c.
Definition at line 642 of file cst_sada.hpp.
|
inline |
Return a proxy object which allows iterating over the children of a node.
v | A valid node of the suffix tree. |
Definition at line 610 of file cst_sada.hpp.
|
inline |
Get the number of children of a node v.
v | A valid node v of a cst_sada. |
Definition at line 958 of file cst_sada.hpp.
|
inline |
Returns the depth of node v.
v | A valid node of the suffix tree. |
Definition at line 496 of file cst_sada.hpp.
|
inline |
Returns the d-th character (1-based indexing) of the edge-label pointing to v.
v | The node at which the edge path ends. |
d | The position (1-based indexing) of the requested character on the edge path from the root to v. ![]() |
Definition at line 714 of file cst_sada.hpp.
|
inline |
Returns if the data strucutre is empty.
Required for the Container Concept of the STL.
Definition at line 286 of file cst_sada.hpp.
|
inline |
Returns a const_iterator to the element after the last element.
Required for the STL Container Concept.
Definition at line 314 of file cst_sada.hpp.
|
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 320 of file cst_sada.hpp.
|
inline |
Returns an iterator to the element after the last element of a bottom-up traversal of the tree.
Definition at line 336 of file cst_sada.hpp.
|
inline |
Computes a unique identification number for a node of the suffix tree in the range [0..nodes()-1].
v | A valid node of a cst_sada. |
Definition at line 872 of file cst_sada.hpp.
|
inline |
Computes the node for such that id(v)=id.
id | An id in the range [0..nodes()-1]. |
Definition at line 893 of file cst_sada.hpp.
|
inline |
Decide if a node is a leaf in the suffix tree.
v | A valid node of a cst_sada. |
Definition at line 467 of file cst_sada.hpp.
|
inline |
Calculates the index of the leftmost leaf in the corresponding suffix array.
v | A valid node of the suffix tree. |
Definition at line 568 of file cst_sada.hpp.
|
inline |
Calculate the lowest common ancestor (lca) of two nodes v and w of the suffix tree.
v | The first node for which the lca with the second node should be computed. |
w | The second node for which the lca with the first node should be computed. |
Definition at line 752 of file cst_sada.hpp.
|
inline |
Calculates the leftmost leaf in the subtree rooted at node v.
v | A valid node of the suffix tree. |
Definition at line 543 of file cst_sada.hpp.
|
inline |
Load from a stream.
in | Inputstream to load the data structure from. |
Definition at line 411 of file cst_sada.hpp.
|
inlinestatic |
Returns the maximal lenght of text for that a suffix tree can be build.
Required for the Container Concept of the STL.
Definition at line 277 of file cst_sada.hpp.
|
inline |
Get the node in the suffix tree which corresponds to the lcp-interval [lb..rb].
Definition at line 946 of file cst_sada.hpp.
|
inline |
Returns the node depth of node v.
v | A valid node of a cst_sada. |
Definition at line 517 of file cst_sada.hpp.
|
inline |
Get the number of nodes of the suffix tree.
Definition at line 936 of file cst_sada.hpp.
|
inlinenoexcept |
Inequality operator.
Definition at line 385 of file cst_sada.hpp.
|
inline |
Move assignment Operator.
Required for the Assignable Concept of the STL.
Definition at line 359 of file cst_sada.hpp.
|
inline |
Assignment Operator.
Required for the Assignable Concept of the STL.
Definition at line 345 of file cst_sada.hpp.
|
inlinenoexcept |
Equality operator.
Definition at line 377 of file cst_sada.hpp.
|
inline |
Calculate the parent node of a node v.
v | A valid node of the suffix tree. |
Definition at line 593 of file cst_sada.hpp.
|
inline |
Calculates the index of the rightmost leaf in the corresponding suffix array.
v | A valid node of the suffix tree. |
Definition at line 581 of file cst_sada.hpp.
|
inline |
Calculates the rightmost leaf in the subtree rooted at node v.
v | A valid node of the suffix tree. |
Definition at line 554 of file cst_sada.hpp.
|
inline |
|
inline |
Get the i-th child of a node v.
v | A valid tree node of the cst. |
i | 1-based Index of the child which should be returned. ![]() |
Definition at line 691 of file cst_sada.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 482 of file cst_sada.hpp.
|
inline |
Serialize to a stream.
out | Outstream to write the data structure. |
Definition at line 394 of file cst_sada.hpp.
|
inline |
Returns the next sibling of node v.
v | A valid node v of the suffix tree. |
Definition at line 622 of file cst_sada.hpp.
|
inline |
Number of leaves in the suffix tree.
Required for the Container Concept of the STL.
Definition at line 268 of file cst_sada.hpp.
|
inline |
Calculate the number of leaves in the subtree rooted at node v.
v | A valid node of the suffix tree. |
This method is used e.g. in the count method.
Definition at line 531 of file cst_sada.hpp.
|
inline |
Compute the suffix link of node v.
v | A valid node of a cst_sada. |
Definition at line 775 of file cst_sada.hpp.
|
inline |
Compute the suffix link of node v applied a number of times consecutively.
v | A valid node of a cst_sada |
Definition at line 800 of file cst_sada.hpp.
|
inline |
Compute the suffix number of a leaf node v.
v | A valid leaf node of a cst_sada. |
Definition at line 857 of file cst_sada.hpp.
|
inline |
Maps an index i to the position in TLCP where LCP[i] can be found.
i | The index in the LCP array |
Definition at line 975 of file cst_sada.hpp.
|
inline |
Compute the Weiner link of node v and character c.
Definition at line 826 of file cst_sada.hpp.
bit_vector const& sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::bp = m_bp |
Definition at line 118 of file cst_sada.hpp.
rank_10_type const& sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::bp_rank_10 = m_bp_rank10 |
Definition at line 120 of file cst_sada.hpp.
select_10_type const& sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::bp_select_10 = m_bp_select10 |
Definition at line 121 of file cst_sada.hpp.
bp_support_type const& sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::bp_support = m_bp_support |
Definition at line 119 of file cst_sada.hpp.
t_csa const& sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::csa = m_csa |
Definition at line 116 of file cst_sada.hpp.
lcp_type const& sdsl::cst_sada< t_csa, t_lcp, t_bp_support, t_rank_10, t_select_10 >::lcp = m_lcp |
Definition at line 117 of file cst_sada.hpp.