SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t > Class Template Reference

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 &lt)
 
 louds_tree (louds_tree &&lt)
 
louds_treeoperator= (louds_tree const &lt)
 
louds_treeoperator= (louds_tree &&lt)
 
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
 

Detailed Description

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
class sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >

A tree class based on the level order unary degree sequence (LOUDS) representation.

Template Parameters
bit_vec_tThe bit vector representation used for LOUDS.
select_1_tA select_support on 1-bits required for the child(v,i) operation.
select_0_tA 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.

Member Typedef Documentation

◆ bit_vector_type

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
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.

◆ node_type

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
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.

◆ select_0_type

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
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.

◆ select_1_type

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
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.

◆ size_type

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
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.

Constructor & Destructor Documentation

◆ louds_tree() [1/3]

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
template<class Cst, class CstBfsIterator>
sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::louds_tree ( Cst const & cst,
const CstBfsIterator begin,
const CstBfsIterator end )
inline

Constructor for a cst and a root node for the traversal.

Definition at line 92 of file louds_tree.hpp.

◆ louds_tree() [2/3]

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::louds_tree ( louds_tree< bit_vec_t, select_1_t, select_0_t > const & lt)
inline

Definition at line 115 of file louds_tree.hpp.

◆ louds_tree() [3/3]

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::louds_tree ( louds_tree< bit_vec_t, select_1_t, select_0_t > && lt)
inline

Definition at line 125 of file louds_tree.hpp.

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
template<typename archive_t>
void sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar)
inline

Load via cereal.

Definition at line 251 of file louds_tree.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
template<typename archive_t>
void sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar) const
inline

Serialise (save) via cereal.

Definition at line 242 of file louds_tree.hpp.

◆ child()

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
node_type sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::child ( node_type const & v,
size_type i ) const
inline

Returns the i-child of a node.

Parameters
vThe parent node.
iIndex of the child. Indexing starts at 1.
Precondition
$ i \in [1..degree(v)] $

Definition at line 194 of file louds_tree.hpp.

◆ degree()

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
size_type sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::degree ( node_type const & v) const
inline

Returns the number of children of a node.

Parameters
vA node.

Definition at line 178 of file louds_tree.hpp.

◆ id()

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
size_type sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::id ( node_type const & v) const
inline

Returns an unique id for each node in [0..size()-1].

Definition at line 215 of file louds_tree.hpp.

◆ is_leaf()

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
bool sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::is_leaf ( node_type const & v) const
inline

Indicates if a node is a leaf.

Parameters
vA node.

Definition at line 168 of file louds_tree.hpp.

◆ load()

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
void sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::load ( std::istream & in)
inline

Definition at line 231 of file louds_tree.hpp.

◆ nodes()

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
size_type sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::nodes ( ) const
inline

Returns the number of nodes in the tree.

Definition at line 160 of file louds_tree.hpp.

◆ operator=() [1/2]

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
louds_tree & sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::operator= ( louds_tree< bit_vec_t, select_1_t, select_0_t > && lt)
inline

Definition at line 140 of file louds_tree.hpp.

◆ operator=() [2/2]

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
louds_tree & sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::operator= ( louds_tree< bit_vec_t, select_1_t, select_0_t > const & lt)
inline

Definition at line 130 of file louds_tree.hpp.

◆ parent()

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
node_type sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::parent ( node_type const & v) const
inline

Returns the parent of a node v or root() if v==root().

Definition at line 203 of file louds_tree.hpp.

◆ root()

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
node_type sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::root ( ) const
inline

Returns the root node.

Definition at line 154 of file louds_tree.hpp.

◆ serialize()

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
size_type sdsl::louds_tree< bit_vec_t, select_1_t, select_0_t >::serialize ( std::ostream & out,
structure_tree_node * v = nullptr,
std::string name = "" ) const
inline

Definition at line 220 of file louds_tree.hpp.

Member Data Documentation

◆ bv

template<class bit_vec_t = bit_vector, class select_1_t = typename bit_vec_t::select_1_type, class select_0_t = typename bit_vec_t::select_0_type>
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.


The documentation for this class was generated from the following file: