open-cpp-utils 0.0.1
Loading...
Searching...
No Matches
open_cpp_utils::directed_tree< T, Alloc > 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...
 
class  unordered
 

Public Types

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

Public Member Functions

 directed_tree ()
 Default constructor, creates tree with empty root.
 
 directed_tree (data_type &&data)
 
 directed_tree (const data_type &data)
 
bool valid (node id) const
 Check whether a node is valid. O(1)
 
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 last_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 next_id () const
 Get the next id that would be used if insert() were called.
 
node insert (const data_type &data, node p_id, node sib=0)
 Insert a node into the tree as a child of the provided node.
 
node insert (data_type &&data, node p_id, node sib=root)
 Insert a node into the tree as a child of the provided node.
 
void swap (node a, node b)
 
void clear ()
 
void erase (node id)
 Erase a node in the tree. O(n)
 
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 std::integral_constant< node, 0 > root {}
 

Detailed Description

template<typename T, class Alloc = std::allocator<T>>
class open_cpp_utils::directed_tree< T, Alloc >

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 , class Alloc = std::allocator<T>>
uint32_t open_cpp_utils::directed_tree< T, Alloc >::depth ( node id) const
inlinenodiscard

Get the depth of a node.

Parameters
id
Returns

◆ erase()

template<typename T , class Alloc = std::allocator<T>>
void open_cpp_utils::directed_tree< T, Alloc >::erase ( node id)
inline

Erase a node in the tree. O(n)

Parameters
idId of the node to erase

◆ first_child()

template<typename T , class Alloc = std::allocator<T>>
node open_cpp_utils::directed_tree< T, Alloc >::first_child ( node id) const
inlinenodiscard

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

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

◆ insert() [1/2]

template<typename T , class Alloc = std::allocator<T>>
node open_cpp_utils::directed_tree< T, Alloc >::insert ( const data_type & data,
node p_id,
node sib = 0 )
inline

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

Parameters
dataValue to insert
p_idId of the parent node
sibChild to insert before, passing root specifies to insert to the back
Returns
Id of the inserted node

◆ insert() [2/2]

template<typename T , class Alloc = std::allocator<T>>
node open_cpp_utils::directed_tree< T, Alloc >::insert ( data_type && data,
node p_id,
node sib = root )
inline

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

Parameters
dataValue to insert
p_idId of the parent node
sibChild to insert before, passing root specifies to insert to the back
Returns
Id of the inserted node

◆ last_child()

template<typename T , class Alloc = std::allocator<T>>
node open_cpp_utils::directed_tree< T, Alloc >::last_child ( node id) const
inlinenodiscard

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

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

◆ left_most()

template<typename T , class Alloc = std::allocator<T>>
node open_cpp_utils::directed_tree< T, Alloc >::left_most ( node id) const
inlinenodiscard

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_id()

template<typename T , class Alloc = std::allocator<T>>
node open_cpp_utils::directed_tree< T, Alloc >::next_id ( ) const
inline

Get the next id that would be used if insert() were called.

Returns
Next node id

◆ next_sibling()

template<typename T , class Alloc = std::allocator<T>>
node open_cpp_utils::directed_tree< T, Alloc >::next_sibling ( node id) const
inlinenodiscard

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 , class Alloc = std::allocator<T>>
data_type & open_cpp_utils::directed_tree< T, Alloc >::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 , class Alloc = std::allocator<T>>
const data_type & open_cpp_utils::directed_tree< T, Alloc >::operator[] ( node id) const
inlinenodiscard

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 , class Alloc = std::allocator<T>>
node open_cpp_utils::directed_tree< T, Alloc >::parent ( node id) const
inlinenodiscard

Get the parent of a node. O(1)

Parameters
idNode id to reference
Returns
Node id of the parent

◆ prev_sibling()

template<typename T , class Alloc = std::allocator<T>>
node open_cpp_utils::directed_tree< T, Alloc >::prev_sibling ( node id) const
inlinenodiscard

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 , class Alloc = std::allocator<T>>
template<typename O = pre_order, typename V >
void open_cpp_utils::directed_tree< T, Alloc >::traverse ( V & visitor)
inline

Traverser-Visitor pattern for accessing the tree.

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

◆ valid()

template<typename T , class Alloc = std::allocator<T>>
bool open_cpp_utils::directed_tree< T, Alloc >::valid ( node id) const
inlinenodiscard

Check whether a node is valid. O(1)

Parameters
idNode id to reference
Returns
Whether the valid flag is true in the node

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