open-cpp-utils 0.0.1
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Static Public Attributes | List of all members
open_cpp_utils::directed_tree< T > Class Template Reference

Class for creating a directed tree. More...

#include <directed_tree.h>

Classes

class  breadth_first
 Breadth first traversal. More...
 
class  in_order
 In-order traversal. More...
 
class  post_order
 Post-order traversal. More...
 
class  pre_order
 Pre-order traversal. More...
 
class  traverser
 Visitor pattern for traversing the tree. More...
 

Public Types

using data_type = T
 
using node = uint32_t
 
using node_queue = std::deque<node>
 

Public Member Functions

 directed_tree ()
 Default constructor, creates tree with empty root.
 
node parent (node id) const
 Get the parent of a node. O(1)
 
node first_child (node id) const
 Get the first child of a node. O(1)
 
node prev_sibling (node id) const
 Get the previous sibling of a node. O(1)
 
node next_sibling (node id) const
 Get the next sibling of a node. O(1)
 
node left_most (node id) const
 Get the left most child of a node. O(log(n))
 
uint32_t depth (node id) const
 Get the depth of a node.
 
node insert (const data_type &data, node p_id)
 Insert a node into the tree as a child of the provided node.
 
void erase (node id)
 Erase a node in the tree.
 
data_type & operator[] (node id)
 Getter for data associated with a node.
 
const data_type & operator[] (node id) const
 Constant getter for data associated with a node.
 
template<typename O = pre_order, typename V >
void traverse (V &visitor)
 Traverser-Visitor pattern for accessing the tree.
 

Static Public Attributes

static constexpr constant_value< node, node(0)> root {}
 

Detailed Description

template<typename T>
class open_cpp_utils::directed_tree< T >

Class for creating a directed tree.

Template Parameters
TType of the data associated with each node

The tree is a series of child nodes in forward linked lists.

Member Function Documentation

◆ depth()

template<typename T >
uint32_t open_cpp_utils::directed_tree< T >::depth ( node id) const
inline

Get the depth of a node.

Parameters
id
Returns

◆ erase()

template<typename T >
void open_cpp_utils::directed_tree< T >::erase ( node id)
inline

Erase a node in the tree.

Parameters
idId of the node to erase

◆ first_child()

template<typename T >
node open_cpp_utils::directed_tree< T >::first_child ( node id) const
inline

Get the first child of a node. O(1)

Parameters
idNode id to reference
Returns
Node id of the first child

◆ insert()

template<typename T >
node open_cpp_utils::directed_tree< T >::insert ( const data_type & data,
node p_id )
inline

Insert a node into the tree as a child of the provided node.

Parameters
dataValue to insert
p_idId of the parent node
Returns
Id of the inserted node

◆ left_most()

template<typename T >
node open_cpp_utils::directed_tree< T >::left_most ( node id) const
inline

Get the left most child of a node. O(log(n))

Parameters
idNode id to reference
Returns
Node id of the left most child

◆ next_sibling()

template<typename T >
node open_cpp_utils::directed_tree< T >::next_sibling ( node id) const
inline

Get the next sibling of a node. O(1)

Parameters
idNode id to reference
Returns
Node id of the next sibling in the linked list

◆ operator[]() [1/2]

template<typename T >
data_type & open_cpp_utils::directed_tree< T >::operator[] ( node id)
inline

Getter for data associated with a node.

Parameters
idId of the node to access
Returns
Reference to the node's data

◆ operator[]() [2/2]

template<typename T >
const data_type & open_cpp_utils::directed_tree< T >::operator[] ( node id) const
inline

Constant getter for data associated with a node.

Parameters
nodeId of the node to access
Returns
Reference to the node's data

◆ parent()

template<typename T >
node open_cpp_utils::directed_tree< T >::parent ( node id) const
inline

Get the parent of a node. O(1)

Parameters
idNode id to reference
Returns
Node id of the parent

◆ prev_sibling()

template<typename T >
node open_cpp_utils::directed_tree< T >::prev_sibling ( node id) const
inline

Get the previous sibling of a node. O(1)

Parameters
idNode id to reference
Returns
Node id of the next sibling in the linked list

◆ traverse()

template<typename T >
template<typename O = pre_order, typename V >
void open_cpp_utils::directed_tree< T >::traverse ( V & visitor)
inline

Traverser-Visitor pattern for accessing the tree.

Template Parameters
VVisitor type.
OOrder type. Defaults to Pre-Order Traversal.
Parameters
visitor

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