SDSL 3.0.1
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 (const Cst &cst, const CstBfsIterator begin, const CstBfsIterator end) | |
Constructor for a cst and a root node for the traversal. | |
louds_tree (const louds_tree <) | |
louds_tree (louds_tree &<) | |
louds_tree & | operator= (const louds_tree <) |
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 (const node_type &v) const |
Indicates if a node is a leaf. | |
size_type | degree (const node_type &v) const |
Returns the number of children of a node. | |
node_type | child (const node_type &v, size_type i) const |
Returns the i-child of a node. | |
node_type | parent (const node_type &v) const |
Returns the parent of a node v or root() if v==root(). | |
size_type | id (const node_type &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 | |
const bit_vector_type & | 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 66 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 71 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 70 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 73 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 72 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 69 of file louds_tree.hpp.
|
inline |
Constructor for a cst and a root node for the traversal.
Definition at line 84 of file louds_tree.hpp.
|
inline |
Definition at line 107 of file louds_tree.hpp.
|
inline |
Definition at line 117 of file louds_tree.hpp.
|
inline |
Load via cereal.
Definition at line 232 of file louds_tree.hpp.
|
inline |
Serialise (save) via cereal.
Definition at line 223 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 181 of file louds_tree.hpp.
|
inline |
Returns the number of children of a node.
v | A node. |
Definition at line 165 of file louds_tree.hpp.
|
inline |
Returns an unique id for each node in [0..size()-1].
Definition at line 199 of file louds_tree.hpp.
|
inline |
|
inline |
Definition at line 212 of file louds_tree.hpp.
|
inline |
Returns the number of nodes in the tree.
Definition at line 150 of file louds_tree.hpp.
|
inline |
Definition at line 123 of file louds_tree.hpp.
|
inline |
Definition at line 133 of file louds_tree.hpp.
|
inline |
Returns the parent of a node v or root() if v==root().
Definition at line 190 of file louds_tree.hpp.
|
inline |
Returns the root node.
Definition at line 147 of file louds_tree.hpp.
|
inline |
Definition at line 201 of file louds_tree.hpp.
const bit_vector_type& sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::bv |
Definition at line 80 of file louds_tree.hpp.