Structure defining a binary tree. More...

#include <bintree.h>

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

Detailed Description

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

Template Parameters

TypeT	The data type
AllocT	An allocator class

Public Member Functions
constexpr size_t	size () const

constexpr bool	empty () const

constexpr size_t	capacity () const

constexpr size_t	next_id () const

constexpr size_t	root () const

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

Constructors & Destructor
constexpr	bintree ()
	Default Constructor, initializes an empty tree.

constexpr	bintree (bintree &&tree) noexcept
	Move Constructor, takes ownership of a tree.

constexpr	bintree (const bintree &tree)
	Copy Constructor, copies a tree.

constexpr	~bintree ()
	Destructor, clears the tree.

Navigation
constexpr size_t	parent (size_t i) const

constexpr size_t	grandparent (size_t i) const

constexpr size_t	left (size_t i) const

constexpr size_t	right (size_t i) const

constexpr size_t	child (size_t i, bool dir) const

constexpr bool	direction (size_t i) const

constexpr size_t	sibling (size_t i) const
	\(O(1)\)

constexpr size_t	depth (size_t i) const

constexpr size_t	left_most (size_t i) const
	\(O(\log n)\)

constexpr size_t	right_most (size_t i) const
	\(O(\log n)\)

Access
constexpr value_t &	operator[] (size_t i)

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

Modifiers
constexpr size_t	insert_left (size_t p, value_t &&val)
	Move Left Insertion, constructs a new node as the left child of `p`

constexpr size_t	insert_left (size_t p, const value_t &val)
	Copy Left Insertion, constructs a new node as the left child of `p`

template<typename... ArgsT>
constexpr size_t	emplace_left (size_t p, ArgsT &&...args)
	Emplace Left Insertion, constructs a new node as the left child of `p`

constexpr size_t	insert_right (size_t p, value_t &&val)
	Move Right Insertion, constructs a new node as the right child of `p`

constexpr size_t	insert_right (size_t p, const value_t &val)
	Copy Right Insertion, constructs a new node as the right child of `p`

template<typename... ArgsT>
constexpr size_t	emplace_right (size_t p, ArgsT &&...args)
	Emplace Right Insertion, constructs a new node as the right child of `p`

constexpr size_t	rotate (size_t sub, bool dir)
	Perform a Tree Rotation at `i` in the specified direction.

constexpr size_t	insert (size_t p, bool d, value_t &&val)
	Move Insertion, bool d, constructs a new node as the child of `p`

constexpr size_t	insert (size_t p, bool d, const value_t &val)
	Copy Insertion, bool d, constructs a new node as the child of `p`

template<typename... ArgsT>
constexpr size_t	emplace (size_t p, bool d, ArgsT &&...args)
	Emplace Insertion, constructs a new node as the child of `p`

constexpr void	clear ()
	Clears the tree, destroying all elements.

Constructor & Destructor Documentation

◆ bintree() [1/2]

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

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

inlineconstexprnoexcept

Parameters

tree	The tree to take ownership of

◆ bintree() [2/2]

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

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

inlineconstexpr

Parameters

tree	The tree to copy

Member Function Documentation

◆ size()

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

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

inlineconstexpr

Returns: The number of elements in the tree

◆ empty()

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

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

inlineconstexpr

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

◆ capacity()

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

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

inlineconstexpr

Returns: The capacity of the underlying allocation

◆ next_id()

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

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

inlineconstexpr

Returns: The next id to be returned by insert or emplace.

◆ root()

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

constexpr size_t fennec::bintree< TypeT, AllocT >::root ( ) const

inlineconstexpr

Returns: The next id to be returned by insert or emplace.

◆ parent()

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

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

inlineconstexpr

\(O(1)\)

Parameters

i	The node id

Returns: The parent of node i

◆ grandparent()

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

constexpr size_t fennec::bintree< TypeT, AllocT >::grandparent ( size_t i ) const

inlineconstexpr

\(O(1)\)

Parameters

i	The node id

Returns: The grandparent of node i

◆ left()

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

constexpr size_t fennec::bintree< TypeT, AllocT >::left ( size_t i ) const

inlineconstexpr

\(O(1)\)

Parameters

i	The node id

Returns: The left child of node i

◆ right()

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

constexpr size_t fennec::bintree< TypeT, AllocT >::right ( size_t i ) const

inlineconstexpr

\(O(1)\)

Parameters

i	The node id

Returns: The right child of node i

◆ child()

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

constexpr size_t fennec::bintree< TypeT, AllocT >::child	(	size_t	i,
		bool	dir
	)		const

inlineconstexpr

\(O(1)\)

Parameters

i	The node id
dir	The direction to go `true` for right, `false` for left

Returns: The child in the direction specified by dir

◆ direction()

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

constexpr bool fennec::bintree< TypeT, AllocT >::direction ( size_t i ) const

inlineconstexpr

\(O(1)\)

Parameters

i	The node id

Returns: true if i is the right node of parent(i), false otherwise

◆ sibling()

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

constexpr size_t fennec::bintree< TypeT, AllocT >::sibling ( size_t i ) const

inlineconstexpr

Parameters

i	The id of the node

Returns: The id of the sibling of i

◆ depth()

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

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

inlineconstexpr

\(O(\log n)\)

Parameters

i	The node id

Returns: The depth of node i

◆ left_most()

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

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

inlineconstexpr

Parameters

i	The node id

Returns: The id of the left-most node of i

◆ right_most()

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

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

inlineconstexpr

Parameters

i	The node id

Returns: The id of the right-most node of i

◆ operator[]() [1/2]

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

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

inlineconstexpr

\(O(1)\)

Parameters

i	The node id

Returns: nullptr if node i does not exist, otherwise, a pointer to the value of node i

◆ operator[]() [2/2]

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

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

inlineconstexpr

Const Access, \(O(1)\)

Parameters

i	The node id

Returns: nullptr if node i does not exist, otherwise, a pointer to the value of node i

◆ insert_left() [1/2]

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

constexpr size_t fennec::bintree< TypeT, AllocT >::insert_left	(	size_t	p,
		value_t &&	val
	)

inlineconstexpr

If the left node of p already exists, the move assignment operator is used instead

Parameters

p	The parent node
val	The object to move into the new node

Returns: The id of the new node

◆ insert_left() [2/2]

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

constexpr size_t fennec::bintree< TypeT, AllocT >::insert_left	(	size_t	p,
		const value_t &	val
	)

inlineconstexpr

If the left node of p already exists, the copy assignment operator is used instead

Parameters

p	The parent node
val	The object to copy to the new node

Returns: The id of the new node

◆ emplace_left()

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

template<typename... ArgsT>

constexpr size_t fennec::bintree< TypeT, AllocT >::emplace_left	(	size_t	p,
		ArgsT &&...	args
	)

inlineconstexpr

If the left node of p already exists, the move assignment operator is used instead

Parameters

p	The parent node
args	The arguments to construct the new node with

Returns: The id of the new node

◆ insert_right() [1/2]

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

constexpr size_t fennec::bintree< TypeT, AllocT >::insert_right	(	size_t	p,
		value_t &&	val
	)

inlineconstexpr

If the right node of p already exists, the move assignment operator is used instead

Parameters

p	The parent node
val	The object to move into the new node

Returns: The id of the new node

◆ insert_right() [2/2]

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

constexpr size_t fennec::bintree< TypeT, AllocT >::insert_right	(	size_t	p,
		const value_t &	val
	)

inlineconstexpr

If the right node of p already exists, the copy assignment operator is used instead

Parameters

p	The parent node
val	The object to copy to the new node

Returns: The id of the new node

◆ emplace_right()

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

template<typename... ArgsT>

constexpr size_t fennec::bintree< TypeT, AllocT >::emplace_right	(	size_t	p,
		ArgsT &&...	args
	)

inlineconstexpr

If the right node of p already exists, the move assignment operator is used instead

Parameters

p	The parent node
args	The arguments to construct the new node with

Returns: The id of the new node

◆ rotate()

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

constexpr size_t fennec::bintree< TypeT, AllocT >::rotate	(	size_t	sub,
		bool	dir
	)

inlineconstexpr

Parameters

i	The root node for the rotation
dir	The direction to rotate, `true` for right, `false` for left

◆ insert() [1/2]

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

constexpr size_t fennec::bintree< TypeT, AllocT >::insert	(	size_t	p,
		bool	d,
		value_t &&	val
	)

inlineconstexpr

If the child of p already exists, the move assignment operator is used instead

Parameters

p	The parent node
d	The direction to insert
val	The object to move into the new node

Returns: The id of the new node

◆ insert() [2/2]

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

constexpr size_t fennec::bintree< TypeT, AllocT >::insert	(	size_t	p,
		bool	d,
		const value_t &	val
	)

inlineconstexpr

If the child of p already exists, the copy assignment operator is used instead

Parameters

p	The parent node
d	The direction to insert
val	The object to copy to the new node

Returns: The id of the new node

◆ emplace()

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

template<typename... ArgsT>

constexpr size_t fennec::bintree< TypeT, AllocT >::emplace	(	size_t	p,
		bool	d,
		ArgsT &&...	args
	)

inlineconstexpr

If the child of p already exists, the move assignment operator is used instead

Parameters

p	The parent node
d	The direction to insert
args	The arguments to construct the new node with

Returns: The id of the new node

◆ traverse()

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

template<typename OrderT , typename VisitorT >

constexpr void fennec::bintree< TypeT, AllocT >::traverse	(	VisitorT &&	visit,
		size_t	i
	)

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/bintree.h

Detailed Description

Public Member Functions

Constructor & Destructor Documentation

◆ bintree() [1/2]

◆ bintree() [2/2]

Member Function Documentation

◆ size()

◆ empty()

◆ capacity()

◆ next_id()

◆ root()

◆ parent()

◆ grandparent()

◆ left()

◆ right()

◆ child()

◆ direction()

◆ sibling()

◆ depth()

◆ left_most()

◆ right_most()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ insert_left() [1/2]

◆ insert_left() [2/2]

◆ emplace_left()

◆ insert_right() [1/2]

◆ insert_right() [2/2]

◆ emplace_right()

◆ rotate()

◆ insert() [1/2]

◆ insert() [2/2]

◆ emplace()

◆ traverse()