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

louds_tree &	operator= (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_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.

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

v	The parent node.
i	Index 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

v A 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

v A 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:

/builddir/build/BUILD/sdsl-lite-3.0.3-build/sdsl-lite-3.0.3/include/sdsl/louds_tree.hpp

Public Types

Public Member Functions

Public Attributes

Detailed Description

Member Typedef Documentation

◆ bit_vector_type

◆ node_type

◆ select_0_type

◆ select_1_type

◆ size_type

Constructor & Destructor Documentation

◆ louds_tree() [1/3]

◆ louds_tree() [2/3]

◆ louds_tree() [3/3]

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

◆ CEREAL_SAVE_FUNCTION_NAME()

◆ child()

◆ degree()

◆ id()

◆ is_leaf()

◆ load()

◆ nodes()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ parent()

◆ root()

◆ serialize()

Member Data Documentation

◆ bv