Rooted-Directed Tree. More...

#include <rdtree.h>

Collaboration diagram for fennec::rdtree< TypeT, AllocT >:

Detailed Description

template<typename TypeT, typename AllocT = allocator<TypeT>>
struct fennec::rdtree< TypeT, AllocT >

Template Parameters

TypeT	Data type
AllocT	Allocator Type

Public Member Functions
Constructors & Destructor
template<typename... ArgsT>
constexpr	rdtree (ArgsT &&...args)
	Root Constructor, constructs the root node of the tree.

constexpr	rdtree (const rdtree &tree)
	Copy Constructor, copies the contents of `tree`

constexpr	rdtree (rdtree &&tree) noexcept
	Move Constructor, takes ownership over the contents of `tree`

Assignment
constexpr rdtree &	operator= (const rdtree &rhs)
	Copy Assignment Operator.

constexpr rdtree &	operator= (rdtree &&rhs) noexcept
	Move Assignment Operator.

Properties
constexpr size_t	size () const

constexpr size_t	capacity () const

constexpr bool	empty () const

constexpr size_t	parent (size_t i) const

constexpr size_t	child (size_t i, size_t n=0) const

constexpr size_t	next (size_t i, size_t n=0) const

constexpr size_t	prev (size_t i, size_t n=0) const

constexpr size_t	left_most (size_t i) const

constexpr size_t	right_most (size_t i) const

constexpr size_t	depth (size_t i) const

constexpr size_t	num_children (size_t i) const

constexpr size_t	next_id () const

constexpr value_t &	operator[] (size_t i)

constexpr const value_t &	operator[] (size_t i) const

constexpr size_t	insert (size_t parent, size_t next, const value_t &val)
	Insertion, creates a node in the tree with parent `parent`

constexpr size_t	insert (size_t parent, size_t next, value_t &&val)
	Insertion, creates a node in the tree with parent `parent`

template<typename... ArgsT>
constexpr size_t	emplace (size_t parent, size_t next, ArgsT &&...args)
	Insertion, creates a node in the tree with parent `parent`

constexpr void	swap (size_t i0, size_t i1)
	Swap two nodes.

constexpr void	erase (size_t i)
	Erase a node in the tree and all of it's children.

template<typename OrderT , typename VisitorT >
constexpr void	traverse (VisitorT &&visit, size_t i=root)
	Traverse the tree using a specified order and visiting functor.

Constructor & Destructor Documentation

◆ rdtree() [1/3]

template<typename TypeT , typename AllocT = allocator<TypeT>>

template<typename... ArgsT>

constexpr fennec::rdtree< TypeT, AllocT >::rdtree ( ArgsT &&... args )

inlineexplicitconstexpr

Template Parameters

ArgsT The argument types

Parameters

args	The arguments to construct the root with

◆ rdtree() [2/3]

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr fennec::rdtree< TypeT, AllocT >::rdtree ( const rdtree< TypeT, AllocT > & tree )

inlineconstexpr

Parameters

tree	the rdtree to copy

◆ rdtree() [3/3]

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr fennec::rdtree< TypeT, AllocT >::rdtree ( rdtree< TypeT, AllocT > && tree )

inlineconstexprnoexcept

Parameters

tree	the rdtree to move

Member Function Documentation

◆ operator=() [1/2]

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr rdtree & fennec::rdtree< TypeT, AllocT >::operator= ( const rdtree< TypeT, AllocT > & rhs )

inlineconstexpr

Parameters

rhs	the rdtree to copy

Returns: this after copying the contents of rhs

◆ operator=() [2/2]

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr rdtree & fennec::rdtree< TypeT, AllocT >::operator= ( rdtree< TypeT, AllocT > && rhs )

inlineconstexprnoexcept

Parameters

rhs	the rdtree to move

Returns: this after taking ownership over the contents of rhs

◆ size()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr size_t fennec::rdtree< TypeT, AllocT >::size ( ) const

inlineconstexpr

Returns: The number of nodes in the tree

◆ capacity()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr size_t fennec::rdtree< TypeT, AllocT >::capacity ( ) const

inlineconstexpr

Returns: The capacity of the underlying allocation

◆ empty()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr bool fennec::rdtree< TypeT, AllocT >::empty ( ) const

inlineconstexpr

Returns: true when there are no nodes in the tree, false otherwise

◆ parent()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr size_t fennec::rdtree< TypeT, AllocT >::parent ( size_t i ) const

inlineconstexpr

Parameters

i	The id of the node to check

Returns: The id of the parent node

◆ child()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr size_t fennec::rdtree< TypeT, AllocT >::child	(	size_t	i,
		size_t	n = `0`
	)		const

inlineconstexpr

Parameters

i	The id of the node to check

Returns: The id of the child node

◆ next()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr size_t fennec::rdtree< TypeT, AllocT >::next	(	size_t	i,
		size_t	n = `0`
	)		const

inlineconstexpr

Parameters

i	The id of the node to check

Returns: The id of the next node

◆ prev()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr size_t fennec::rdtree< TypeT, AllocT >::prev	(	size_t	i,
		size_t	n = `0`
	)		const

inlineconstexpr

Parameters

i	The id of the node to check

Returns: The id of the previous node

◆ left_most()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr size_t fennec::rdtree< TypeT, AllocT >::left_most ( size_t i ) const

inlineconstexpr

Parameters

i	the node to start at

Returns: the left-most child of node i

◆ right_most()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr size_t fennec::rdtree< TypeT, AllocT >::right_most ( size_t i ) const

inlineconstexpr

Parameters

i	the node to start at

Returns: the right-most child of node i

◆ depth()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr size_t fennec::rdtree< TypeT, AllocT >::depth ( size_t i ) const

inlineconstexpr

Parameters

i	The id of the node to check

Returns: The depth of the node

◆ num_children()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr size_t fennec::rdtree< TypeT, AllocT >::num_children ( size_t i ) const

inlineconstexpr

Parameters

i	The id of the node to check

Returns: The number of children the node has

◆ next_id()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr size_t fennec::rdtree< TypeT, AllocT >::next_id ( ) const

inlineconstexpr

Returns: The next node id were insert or emplace to be called

◆ operator[]() [1/2]

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr value_t & fennec::rdtree< TypeT, AllocT >::operator[] ( size_t i )

inlineconstexpr

Parameters

i	The id of the node to access

Returns: A reference to the value of the node wrapped in an optional

◆ operator[]() [2/2]

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr const value_t & fennec::rdtree< TypeT, AllocT >::operator[] ( size_t i ) const

inlineconstexpr

Parameters

i	The id of the node to access

Returns: A const-qualified reference to the value of the node wrapped in an optional

◆ insert() [1/2]

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr size_t fennec::rdtree< TypeT, AllocT >::insert	(	size_t	parent,
		size_t	next,
		const value_t &	val
	)

inlineconstexpr

Parameters

parent	the parent node, if `npos` sets the value of the root node
next	the next node, as an index relative to the parent, i.e. parent[0] == parent.child, parent[1] == parent.child.next
val	the value to insert

Returns: the index of the created node

◆ insert() [2/2]

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr size_t fennec::rdtree< TypeT, AllocT >::insert	(	size_t	parent,
		size_t	next,
		value_t &&	val
	)

inlineconstexpr

Parameters

parent	the parent node, if `npos` sets the value of the root node
next	the next node, as an index relative to the parent
val	the value to insert

Returns: the index of the created node

◆ emplace()

template<typename TypeT , typename AllocT = allocator<TypeT>>

template<typename... ArgsT>

constexpr size_t fennec::rdtree< TypeT, AllocT >::emplace	(	size_t	parent,
		size_t	next,
		ArgsT &&...	args
	)

inlineconstexpr

Parameters

parent	the parent node, if `npos` sets the value of the root node
next	the next node, as an index relative to the parent, i.e. parent[0] == parent.child, parent[1] == parent.child.next
args	the args to construct the value to insert

Returns: the index of the created node

◆ swap()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr void fennec::rdtree< TypeT, AllocT >::swap	(	size_t	i0,
		size_t	i1
	)

inlineconstexpr

Parameters

i0	The id of the first node
i1	The id of the second node

◆ erase()

template<typename TypeT , typename AllocT = allocator<TypeT>>

constexpr void fennec::rdtree< TypeT, AllocT >::erase ( size_t i )

inlineconstexpr

Parameters

i	the index of the node

◆ traverse()

template<typename TypeT , typename AllocT = allocator<TypeT>>

template<typename OrderT , typename VisitorT >

constexpr void fennec::rdtree< TypeT, AllocT >::traverse	(	VisitorT &&	visit,
		size_t	i = `root`
	)

inlineconstexpr

The visitor should accept a reference to a value of type TypeT and a size_t which contains the node's id. The visitor should return one of the following values in the fennec::traversal_control_ enum

Template Parameters

OrderT	The order with which to traverse the tree.
VisitorT	The visitor, should fulfill the signature `uint8_t visit(TypeT&, size_t)`

Parameters

visit	The visiting object
i	The node to start at

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

include/fennec/containers/rdtree.h

Detailed Description

Public Member Functions

Properties

Constructor & Destructor Documentation

◆ rdtree() [1/3]

◆ rdtree() [2/3]

◆ rdtree() [3/3]

Member Function Documentation

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ size()

◆ capacity()

◆ empty()

◆ parent()

◆ child()

◆ next()

◆ prev()

◆ left_most()

◆ right_most()

◆ depth()

◆ num_children()

◆ next_id()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ insert() [1/2]

◆ insert() [2/2]

◆ emplace()

◆ swap()

◆ erase()

◆ traverse()