SDSL 3.0.3
Succinct Data Structure Library
|
A tree class based on the level order unary degree sequence (LOUDS) representation. More...
#include <louds_tree.hpp>
Public Types | |
typedef bit_vector::size_type | size_type |
typedef louds_node | node_type |
typedef bit_vec_t | bit_vector_type |
typedef select_1_t | select_1_type |
typedef select_0_t | select_0_type |
Public Member Functions | |
template<class Cst, class CstBfsIterator> | |
louds_tree (Cst const &cst, const CstBfsIterator begin, const CstBfsIterator end) | |
Constructor for a cst and a root node for the traversal. | |
louds_tree (louds_tree const <) | |
louds_tree (louds_tree &<) | |
louds_tree & | operator= (louds_tree const <) |
louds_tree & | operator= (louds_tree &<) |
node_type | root () const |
Returns the root node. | |
size_type | nodes () const |
Returns the number of nodes in the tree. | |
bool | is_leaf (node_type const &v) const |
Indicates if a node is a leaf. | |
size_type | degree (node_type const &v) const |
Returns the number of children of a node. | |
node_type | child (node_type const &v, size_type i) const |
Returns the i-child of a node. | |
node_type | parent (node_type const &v) const |
Returns the parent of a node v or root() if v==root(). | |
size_type | id (node_type const &v) const |
Returns an unique id for each node in [0..size()-1]. | |
size_type | serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const |
void | load (std::istream &in) |
template<typename archive_t> | |
void | CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const |
Serialise (save) via cereal. | |
template<typename archive_t> | |
void | CEREAL_LOAD_FUNCTION_NAME (archive_t &ar) |
Load via cereal. |
Public Attributes | |
bit_vector_type const & | bv |
A tree class based on the level order unary degree sequence (LOUDS) representation.
bit_vec_t | The bit vector representation used for LOUDS. |
select_1_t | A select_support on 1-bits required for the child(v,i) operation. |
select_0_t | A select_support on 0-bits required for the parent operation. |
Example of the structure: A tree with balanced parentheses representation (()()(()())) is translated into 10001110011. Traverse the tree in breadth-first order an write for each node a 1-bit followed by as many 0-bits as the node has children.
Disadvantages of louds: No efficient support for subtree size.
Definition at line 73 of file louds_tree.hpp.
typedef bit_vec_t sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::bit_vector_type |
Definition at line 78 of file louds_tree.hpp.
typedef louds_node sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::node_type |
Definition at line 77 of file louds_tree.hpp.
typedef select_0_t sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::select_0_type |
Definition at line 80 of file louds_tree.hpp.
typedef select_1_t sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::select_1_type |
Definition at line 79 of file louds_tree.hpp.
typedef bit_vector::size_type sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::size_type |
Definition at line 76 of file louds_tree.hpp.
|
inline |
Constructor for a cst and a root node for the traversal.
Definition at line 92 of file louds_tree.hpp.
|
inline |
Definition at line 115 of file louds_tree.hpp.
|
inline |
Definition at line 125 of file louds_tree.hpp.
|
inline |
Load via cereal.
Definition at line 251 of file louds_tree.hpp.
|
inline |
Serialise (save) via cereal.
Definition at line 242 of file louds_tree.hpp.
|
inline |
Returns the i-child of a node.
v | The parent node. |
i | Index of the child. Indexing starts at 1. |
Definition at line 194 of file louds_tree.hpp.
|
inline |
Returns the number of children of a node.
v | A node. |
Definition at line 178 of file louds_tree.hpp.
|
inline |
Returns an unique id for each node in [0..size()-1].
Definition at line 215 of file louds_tree.hpp.
|
inline |
|
inline |
Definition at line 231 of file louds_tree.hpp.
|
inline |
Returns the number of nodes in the tree.
Definition at line 160 of file louds_tree.hpp.
|
inline |
Definition at line 140 of file louds_tree.hpp.
|
inline |
Definition at line 130 of file louds_tree.hpp.
|
inline |
Returns the parent of a node v or root() if v==root().
Definition at line 203 of file louds_tree.hpp.
|
inline |
Returns the root node.
Definition at line 154 of file louds_tree.hpp.
|
inline |
Definition at line 220 of file louds_tree.hpp.
bit_vector_type const& sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::bv |
Definition at line 88 of file louds_tree.hpp.