Generic m-ary trees. More...

#include <tpl_tree_node.H>

Inheritance diagram for Aleph::Tree_Node< T >:

Collaboration diagram for Aleph::Tree_Node< T >:

Classes
class	Children_Iterator
	Iterator over the children of this. More...

struct	Children_Set

struct	Flags

class	Iterator

Public Types
using	Item_Type = Tree_Node *

using	key_type = T
	Generic data type stored in the node.

using	iterator = __iterator< Tree_Node >

using	const_iterator = __const_iterator< Tree_Node >

Public Member Functions
T &	get_key () noexcept
	Returns a modifiable reference to the node contents.

constexpr const T &	get_key () const noexcept

T &	get_data () noexcept
	Returns a modifiable reference to the node contents.

constexpr const T &	get_data () const noexcept

Dlink *	get_child_list () noexcept

Dlink *	get_sibling_list () noexcept

constexpr bool	is_root () const noexcept
	Returns true if this is the root of the general tree.

constexpr bool	is_leaf () const noexcept
	Returns true if this is a leaf node.

constexpr bool	is_leftmost () const noexcept
	Returns true if this is the leftmost node among its siblings.

constexpr bool	is_rightmost () const noexcept
	Returns true if this is the rightmost node among its siblings.

void	set_is_root (bool value) noexcept

void	set_is_leaf (bool value) noexcept

void	set_is_leftmost (bool value) noexcept

void	set_is_rightmost (bool value) noexcept

	Tree_Node ()=default
	Empty constructor (undefined key).

	Tree_Node (const T &d)
	Constructor with data value __data.

	Tree_Node (T &&d)

Tree_Node *	get_left_sibling () const noexcept
	Returns the left sibling of this.

Tree_Node *	get_right_sibling () const noexcept
	Returns the right sibling of this.

Tree_Node *	get_left_child () const noexcept
	Returns the leftmost child of this.

Tree_Node *	get_right_child () const noexcept
	Returns the rightmost child of this.

Tree_Node *	get_child (const size_t i) const noexcept
	Returns the i-th child of this.

Tree_Node *	get_parent () const noexcept
	Returns the parent of this.

void	insert_right_sibling (Tree_Node *p) noexcept
	Inserts p as the right sibling of this.

void	insert_left_sibling (Tree_Node *p)
	Inserts p as the left sibling of this.

void	insert_leftmost_child (Tree_Node *p) noexcept
	Inserts p as the leftmost child of this.

void	insert_rightmost_child (Tree_Node *p) noexcept
	Inserts p as the rightmost child of this.

Tree_Node *	join (Tree_Node *tree)
	join `tree` as subtree of root `this`

void	insert_tree_to_right (Tree_Node *tree)
	Insert `tree` to the right of `this`

Tree_Node *	get_left_tree () const noexcept
	Returns the tree to the left of this.

Tree_Node *	get_right_tree () const noexcept
	Returns the tree to the right of this.

Tree_Node *	get_last_tree () const
	Returns the rightmost tree of the forest containing this.

template<template< typename > class Container = DynList>
Container< Tree_Node * >	trees () const
	Return a list with all trees belonging to the forrest.

template<typename Operation >
void	for_each_child (Operation &op) const
	Visits each child of this and executes the operation on the child node.

template<typename Operation >
void	for_each_child (Operation &&op=Operation()) const

template<template< typename > class Container = DynList>
Container< Tree_Node * >	children_nodes () const
	Returns a list with the child nodes of this.

template<template< typename > class Container = DynList>
Container< T >	children () const
	Returns a list with the contents of the children of this.

template<class Operation >
bool	traverse (Operation op)
	Preorder traversal over all nodes executing op.

template<class Operation >
bool	traverse (Operation op) const

template<class Op >
bool	level_traverse (Op op)

template<class Op >
bool	level_traverse (Op op) const

Children_Iterator	children_it () const

Iterator	get_it () const

iterator	begin () noexcept

iterator	end () noexcept

const_iterator	begin () const noexcept

const_iterator	end () const noexcept

const_iterator	cbegin () const noexcept

const_iterator	cend () const noexcept

const_iterator	cbegin () noexcept

const_iterator	cend () noexcept

Public Member Functions inherited from Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >
auto	for_each (Operation &operation) const -> decltype(self())
	Apply an operation to each element (read-only).

auto	for_each (Operation &operation) -> decltype(self())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

auto	for_each (Operation &&operation=Operation()) const -> decltype(self())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

auto	for_each (Operation &&operation=Operation()) -> decltype(self())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

auto	mutable_for_each (Operation &operation) -> decltype(self())
	Apply an operation to each element (mutable).

auto	mutable_for_each (Operation &&operation=Operation()) -> decltype(self())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool	all (Operation &operation) const
	Test if all elements satisfy a predicate.

bool	all (Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool	forall (Operation &operation) const
	Alias for all().

bool	forall (Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

bool	exists (Operation &operation) const
	Test if any element satisfies a predicate.

bool	exists (Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Container< __Type >	maps (Operation &operation) const
	Transform elements using a mapping function.

Container< __Type >	maps (Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

__Type	foldl (const __Type &init, std::function< __Type(const __Type &, const Tree_Node< T > * &)> operation) const
	Left fold (reduce) with initial value.

__Type	fold_left (std::function< __Type(const __Type &, const Tree_Node< T > * &)> operation, const __Type &init) const
	Left fold with operation first (alternative signature).

Tree_Node< T > *	fold (const Tree_Node< T > * &init, Operation &operation) const
	Simple fold with same type for accumulator and elements.

Tree_Node< T > *	fold (const Tree_Node< T > * &init, Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

DynList< Tree_Node< T > * >	filter (Operation &operation) const
	Filter elements by a predicate.

DynList< Tree_Node< T > * >	filter (Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

DynList< std::tuple< Tree_Node< T > *, size_t > >	pfilter (Operation &operation) const
	Filter with position information.

DynList< std::tuple< Tree_Node< T > *, size_t > >	pfilter (Operation &&operation=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

std::pair< DynList< Tree_Node< T > * >, DynList< Tree_Node< T > * > >	partition (Operation &op) const
	Partition elements by a predicate.

std::pair< DynList< Tree_Node< T > * >, DynList< Tree_Node< T > * > >	partition (Operation &&op=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

std::tuple< DynList< Tree_Node< T > * >, DynList< Tree_Node< T > * > >	tpartition (Operation &op) const
	Partition returning tuple instead of pair.

std::tuple< DynList< Tree_Node< T > * >, DynList< Tree_Node< T > * > >	tpartition (Operation &&op=Operation()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

size_t	length () const noexcept
	Count the number of elements.

Container< Tree_Node< T > * >	rev () const
	Create a reversed copy.

Container< Tree_Node< T > * >	take (const size_t n) const
	Take the first n elements.

Container< Tree_Node< T > * >	drop (const size_t n) const
	Skip the first n elements.

Tree_Node< T > *	sum (const Tree_Node< T > * &init=Tree_Node< T > *{}) const
	Compute the sum of all elements.

Tree_Node< T > *	product (const Tree_Node< T > * &init) const
	Compute the product of all elements.

const Tree_Node< T > * *	min () const
	Find the minimum element.

const Tree_Node< T > * *	max () const
	Find the maximum element.

const Tree_Node< T > * *	min_by (Compare cmp) const
	Find the minimum element using a custom comparator.

const Tree_Node< T > * *	max_by (Compare cmp) const
	Find the maximum element using a custom comparator.

bool	has_value (const Tree_Node< T > * &val) const
	Check if container has a value.

bool	none (Predicate &pred) const
	Check if no element satisfies a predicate.

bool	none (Predicate &&pred) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

size_t	count_if (Predicate pred) const
	Count elements satisfying a predicate.

const Tree_Node< T > * *	first () const
	Get the first element.

Tree_Node< T > *	first_or (const Tree_Node< T > * &default_val) const
	Get the first element or a default value.

const Tree_Node< T > * *	last () const
	Get the last element.

Tree_Node< T > *	last_or (const Tree_Node< T > * &default_val) const
	Get the last element or a default value.

Container< std::pair< size_t, Tree_Node< T > * > >	enumerate () const
	Enumerate elements with their indices.

size_t	find_index (Predicate pred) const
	Find the index of the first element satisfying a predicate.

size_t	index_of (const Tree_Node< T > * &val) const
	Find the index of a specific value.

Container< Tree_Node< T > * >	unique () const
	Remove consecutive duplicate elements.

Container< Tree_Node< T > * >	unique_by (EqPred eq) const
	Remove consecutive duplicates using a custom equality predicate.

Container< Tree_Node< T > * >	intersperse (const Tree_Node< T > * &sep) const
	Intersperse a separator between elements.

Container< Container< Tree_Node< T > * > >	chunk (size_t n) const
	Split into chunks of fixed size.

Container< Container< Tree_Node< T > * > >	sliding (size_t size, size_t step=1) const
	Create sliding windows of fixed size.

std::vector< Tree_Node< T > * >	to_vector () const
	Convert to std::vector.

DynListType	to_dynlist () const
	Convert container to DynList.

StringType	join (const StringType &sep=StringType{", "}) const
	Join elements into a string with separator.

std::string	join_str (const std::string &sep=", ") const
	Join string elements with separator.

Container< std::pair< Tree_Node< T > *, typename Other::Item_Type > >	zip_with (const Other &other) const
	Zip with another container.

Private Member Functions
Tree_Node *	upper_link () const noexcept

Tree_Node *	lower_link () const noexcept

Tree_Node *	left_link () const noexcept

Tree_Node *	right_link () const noexcept

Static Private Member Functions
static Tree_Node *	child_to_Tree_Node (Dlink *link) noexcept

static Tree_Node *	sibling_to_Tree_Node (Dlink *link) noexcept

template<class Operation >
static bool	preorder (const Tree_Node *root, Operation &op)

Private Attributes
T	data

Dlink	child

Dlink	sibling

Flags	flags

Friends
const_iterator	cbegin (const Tree_Node &s) noexcept

const_iterator	cend (const Tree_Node &s) noexcept

const_iterator	begin (const Tree_Node &s) noexcept

const_iterator	end (const Tree_Node &s) noexcept

iterator	begin (Tree_Node &s) noexcept

iterator	end (Tree_Node &s) noexcept

Additional Inherited Members
Protected Member Functions inherited from Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >
const Tree_Node< T > &	self () const noexcept

Tree_Node< T > &	self () noexcept

Detailed Description

template<class T>
class Aleph::Tree_Node< T >

Generic m-ary trees.

The Tree_Node<Key> class defines general trees of any order, represented by linked lists.

Parameters

Key	the data type stored in each tree node.

Definition at line 88 of file tpl_tree_node.H.

Member Typedef Documentation

◆ const_iterator

template<class T >

using Aleph::Tree_Node< T >::const_iterator = __const_iterator< Tree_Node >

Definition at line 767 of file tpl_tree_node.H.

◆ Item_Type

template<class T >

using Aleph::Tree_Node< T >::Item_Type = Tree_Node*

Definition at line 131 of file tpl_tree_node.H.

◆ iterator

template<class T >

using Aleph::Tree_Node< T >::iterator = __iterator< Tree_Node >

Definition at line 767 of file tpl_tree_node.H.

◆ key_type

template<class T >

using Aleph::Tree_Node< T >::key_type = T

Generic data type stored in the node.

Definition at line 144 of file tpl_tree_node.H.

Constructor & Destructor Documentation

◆ Tree_Node() [1/3]

template<class T >

Aleph::Tree_Node< T >::Tree_Node ( )

default

Empty constructor (undefined key).

◆ Tree_Node() [2/3]

template<class T >

Aleph::Tree_Node< T >::Tree_Node ( const T & d )

inline

Constructor with data value __data.

Definition at line 174 of file tpl_tree_node.H.

◆ Tree_Node() [3/3]

template<class T >

Aleph::Tree_Node< T >::Tree_Node ( T && d )

inline

Definition at line 177 of file tpl_tree_node.H.

Member Function Documentation

◆ begin() [1/2]

template<class T >

const_iterator Aleph::Tree_Node< T >::begin ( ) const

inlinenoexcept

Definition at line 767 of file tpl_tree_node.H.

◆ begin() [2/2]

template<class T >

iterator Aleph::Tree_Node< T >::begin ( )

inlinenoexcept

Definition at line 767 of file tpl_tree_node.H.

◆ cbegin() [1/2]

template<class T >

const_iterator Aleph::Tree_Node< T >::cbegin ( ) const

inlinenoexcept

Definition at line 767 of file tpl_tree_node.H.

◆ cbegin() [2/2]

template<class T >

const_iterator Aleph::Tree_Node< T >::cbegin ( )

inlinenoexcept

Definition at line 767 of file tpl_tree_node.H.

◆ cend() [1/2]

template<class T >

const_iterator Aleph::Tree_Node< T >::cend ( ) const

inlinenoexcept

Definition at line 767 of file tpl_tree_node.H.

◆ cend() [2/2]

template<class T >

const_iterator Aleph::Tree_Node< T >::cend ( )

inlinenoexcept

Definition at line 767 of file tpl_tree_node.H.

◆ child_to_Tree_Node()

template<class T >

static Tree_Node * Aleph::Tree_Node< T >::child_to_Tree_Node ( Dlink * link )

inlinestaticprivatenoexcept

Definition at line 106 of file tpl_tree_node.H.

Referenced by Aleph::Tree_Node< T >::lower_link(), and Aleph::Tree_Node< T >::upper_link().

◆ children()

template<class T >

template<template< typename > class Container = DynList>

Container< T > Aleph::Tree_Node< T >::children ( ) const

inline

Returns a list with the contents of the children of this.

Definition at line 539 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::for_each_child(), Aleph::Tree_Node< T >::get_key(), and Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps().

Referenced by TEST(), and TEST().

◆ children_it()

template<class T >

Children_Iterator Aleph::Tree_Node< T >::children_it ( ) const

inline

Definition at line 646 of file tpl_tree_node.H.

◆ children_nodes()

template<class T >

template<template< typename > class Container = DynList>

Container< Tree_Node * > Aleph::Tree_Node< T >::children_nodes ( ) const

inline

Returns a list with the child nodes of this.

Definition at line 530 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::for_each_child(), and Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps().

Referenced by TEST().

◆ end() [1/2]

template<class T >

const_iterator Aleph::Tree_Node< T >::end ( ) const

inlinenoexcept

Definition at line 767 of file tpl_tree_node.H.

◆ end() [2/2]

template<class T >

iterator Aleph::Tree_Node< T >::end ( )

inlinenoexcept

Definition at line 767 of file tpl_tree_node.H.

◆ for_each_child() [1/2]

template<class T >

template<typename Operation >

void Aleph::Tree_Node< T >::for_each_child ( Operation && op = Operation() ) const

inline

Definition at line 523 of file tpl_tree_node.H.

References Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps().

◆ for_each_child() [2/2]

template<class T >

template<typename Operation >

void Aleph::Tree_Node< T >::for_each_child ( Operation & op ) const

inline

Visits each child of this and executes the operation on the child node.

Definition at line 515 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::child, and Aleph::Tree_Node< T >::get_left_child().

Referenced by Aleph::Tree_Node< T >::children(), Aleph::Tree_Node< T >::children_nodes(), Aleph::Cnode::clone(), and Aleph::Tree_Node< T >::level_traverse().

◆ get_child()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::get_child ( const size_t i ) const

inlinenoexcept

Returns the i-th child of this.

Parameters

[in] i ordinal of the child to access.

Returns: pointer to the i-th child of this; nullptr if it does not exist.

Definition at line 227 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::get_left_child(), Aleph::Tree_Node< T >::get_right_sibling(), and Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps().

Referenced by TEST(), and TEST().

◆ get_child_list()

template<class T >

Dlink * Aleph::Tree_Node< T >::get_child_list ( )

inlinenoexcept

Definition at line 146 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::child.

Referenced by TEST().

◆ get_data() [1/2]

template<class T >

constexpr const T & Aleph::Tree_Node< T >::get_data ( ) const

inlineconstexprnoexcept

Definition at line 141 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::data.

◆ get_data() [2/2]

template<class T >

T & Aleph::Tree_Node< T >::get_data ( )

inlinenoexcept

Returns a modifiable reference to the node contents.

Definition at line 139 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::data.

Referenced by Aleph::Tree_Node< T >::get_key(), and Aleph::Tree_Node< T >::get_key().

◆ get_it()

template<class T >

Iterator Aleph::Tree_Node< T >::get_it ( ) const

inline

Definition at line 762 of file tpl_tree_node.H.

Referenced by TEST(), and TEST().

◆ get_key() [1/2]

template<class T >

constexpr const T & Aleph::Tree_Node< T >::get_key ( ) const

inlineconstexprnoexcept

Definition at line 136 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::get_data().

◆ get_key() [2/2]

template<class T >

T & Aleph::Tree_Node< T >::get_key ( )

inlinenoexcept

Returns a modifiable reference to the node contents.

Definition at line 134 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::get_data().

Referenced by Aleph::Tree_Node< T >::children(), deway(), Convertir::operator()(), Write_Node::operator()(), Write_Df::operator()(), Write_Low::operator()(), WriteNode::operator()(), print_tree(), TEST(), TEST(), TEST(), TEST(), and TEST_F().

◆ get_last_tree()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::get_last_tree ( ) const

inline

Returns the rightmost tree of the forest containing this.

Throws range_error if this is not the leftmost tree of the forest.

Definition at line 494 of file tpl_tree_node.H.

References ah_range_error_if, Aleph::Tree_Node< T >::is_leftmost(), Aleph::Tree_Node< T >::left_link(), and Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps().

◆ get_left_child()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::get_left_child ( ) const

inlinenoexcept

Returns the leftmost child of this.

Definition at line 199 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::is_leaf(), and Aleph::Tree_Node< T >::lower_link().

Referenced by Aleph::Cnode::clone(), RandomTreeTest::count_nodes(), delete_tree(), RandomTreeTest::destroy_tree(), deway(), Aleph::Tree_Node< T >::for_each_child(), Aleph::Tree_Node< T >::get_child(), Aleph::Tree_Node< T >::insert_left_sibling(), Aleph::Tree_Node< T >::insert_leftmost_child(), Aleph::Tree_Node< T >::Iterator::next_ne(), print_tree(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), and RandomTreeTest::tree_height().

◆ get_left_sibling()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::get_left_sibling ( ) const

inlinenoexcept

Returns the left sibling of this.

Definition at line 181 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::is_leftmost(), and Aleph::Tree_Node< T >::left_link().

Referenced by Aleph::Tree_Node< T >::insert_left_sibling(), and TEST().

◆ get_left_tree()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::get_left_tree ( ) const

inlinenoexcept

Returns the tree to the left of this.

Definition at line 474 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::is_leftmost(), Aleph::Tree_Node< T >::left_link(), and Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps().

Referenced by TEST().

◆ get_parent()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::get_parent ( ) const

inlinenoexcept

Returns the parent of this.

Definition at line 237 of file tpl_tree_node.H.

References CHILD_LIST, Aleph::Tree_Node< T >::is_root(), ISLEFTMOST, ISROOT, Aleph::Tree_Node< T >::left_link(), and Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps().

Referenced by Aleph::Tree_Node< T >::insert_left_sibling(), and TEST().

◆ get_right_child()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::get_right_child ( ) const

inlinenoexcept

Returns the rightmost child of this.

Definition at line 208 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::is_leaf(), ISLEFTMOST, Aleph::Tree_Node< T >::lower_link(), and Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps().

Referenced by Aleph::Tree_Node< T >::Iterator::next_ne(), TEST(), and TEST().

◆ get_right_sibling()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::get_right_sibling ( ) const

inlinenoexcept

Returns the right sibling of this.

Definition at line 190 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::is_rightmost(), and Aleph::Tree_Node< T >::right_link().

Referenced by delete_tree(), RandomTreeTest::destroy_tree(), deway(), deway(), Aleph::Tree_Node< T >::get_child(), Aleph::Tree_Node< T >::insert_right_sibling(), main(), Aleph::Tree_Node< T >::Children_Iterator::next_ne(), TEST(), TEST_F(), and TEST_F().

◆ get_right_tree()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::get_right_tree ( ) const

inlinenoexcept

Returns the tree to the right of this.

Definition at line 483 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::is_rightmost(), Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps(), and Aleph::Tree_Node< T >::right_link().

Referenced by Aleph::Tree_Node< T >::insert_tree_to_right(), TEST(), and Aleph::Tree_Node< T >::trees().

◆ get_sibling_list()

template<class T >

Dlink * Aleph::Tree_Node< T >::get_sibling_list ( )

inlinenoexcept

Definition at line 148 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::sibling.

Referenced by TEST().

◆ insert_left_sibling()

template<class T >

void Aleph::Tree_Node< T >::insert_left_sibling ( Tree_Node< T > * p )

inline

Inserts p as the left sibling of this.

Parameters

[in] p node to insert as left sibling.

Definition at line 293 of file tpl_tree_node.H.

◆ insert_leftmost_child()

template<class T >

void Aleph::Tree_Node< T >::insert_leftmost_child ( Tree_Node< T > * p )

inlinenoexcept

Inserts p as the leftmost child of this.

Parameters

[in] p node to insert.

Definition at line 348 of file tpl_tree_node.H.

References CHILD_LIST, Aleph::Dlink::cut_list(), Aleph::Dlink::del(), Aleph::Tree_Node< T >::get_left_child(), Aleph::Dlink::insert(), Aleph::Tree_Node< T >::is_leaf(), Aleph::Tree_Node< T >::lower_link(), Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps(), root(), Aleph::Tree_Node< T >::set_is_leaf(), and SIBLING_LIST.

Referenced by TEST(), and TEST().

◆ insert_right_sibling()

template<class T >

void Aleph::Tree_Node< T >::insert_right_sibling ( Tree_Node< T > * p )

inlinenoexcept

Inserts p as the right sibling of this.

Parameters

[in] p node to insert as right sibling.

Definition at line 258 of file tpl_tree_node.H.

References CHILD_LIST, Aleph::Tree_Node< T >::get_right_sibling(), Aleph::Dlink::insert(), Aleph::Tree_Node< T >::is_rightmost(), Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps(), Aleph::Tree_Node< T >::set_is_rightmost(), and SIBLING_LIST.

Referenced by TEST().

◆ insert_rightmost_child()

template<class T >

void Aleph::Tree_Node< T >::insert_rightmost_child ( Tree_Node< T > * p )

inlinenoexcept

Inserts p as the rightmost child of this.

Parameters

[in] p node to insert.

Definition at line 388 of file tpl_tree_node.H.

References CHILD_LIST, Aleph::Tree_Node< T >::is_leaf(), Aleph::Tree_Node< T >::left_link(), Aleph::Tree_Node< T >::lower_link(), Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps(), Aleph::Tree_Node< T >::set_is_leaf(), Aleph::Tree_Node< T >::set_is_rightmost(), and SIBLING_LIST.

Referenced by Aleph::Cnode::clone(), and TEST().

◆ insert_tree_to_right()

template<class T >

void Aleph::Tree_Node< T >::insert_tree_to_right ( Tree_Node< T > * tree )

inline

Insert tree to the right of this

Assuming that this is part of a forrest, this method insert tree to the right of this.

Be careful with the fact that tree will not always be inserted as the rightmost tree, but as the tree to right of this.

Parameters

[in] tree the tree to insert

Exceptions

domain_error if tree is not root

Definition at line 453 of file tpl_tree_node.H.

References ah_domain_error_if, Aleph::Tree_Node< T >::get_right_tree(), Aleph::Tree_Node< T >::is_rightmost(), Aleph::Tree_Node< T >::is_root(), Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps(), Aleph::Tree_Node< T >::set_is_leftmost(), Aleph::Tree_Node< T >::set_is_rightmost(), and SIBLING_LIST.

◆ is_leaf()

template<class T >

constexpr bool Aleph::Tree_Node< T >::is_leaf ( ) const

inlineconstexprnoexcept

Returns true if this is a leaf node.

Definition at line 154 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::flags, and Aleph::Tree_Node< T >::Flags::is_leaf.

Referenced by Aleph::Tree_Node< T >::get_left_child(), Aleph::Tree_Node< T >::get_right_child(), Aleph::Tree_Node< T >::insert_left_sibling(), Aleph::Tree_Node< T >::insert_leftmost_child(), Aleph::Tree_Node< T >::insert_rightmost_child(), Aleph::Tree_Node< T >::join(), TEST(), and TEST().

◆ is_leftmost()

template<class T >

constexpr bool Aleph::Tree_Node< T >::is_leftmost ( ) const

inlineconstexprnoexcept

Returns true if this is the leftmost node among its siblings.

Definition at line 157 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::flags, and Aleph::Tree_Node< T >::Flags::is_leftmost.

Referenced by Aleph::Tree_Node< T >::get_last_tree(), Aleph::Tree_Node< T >::get_left_sibling(), Aleph::Tree_Node< T >::get_left_tree(), Aleph::Tree_Node< T >::insert_left_sibling(), Aleph::Tree_Node< T >::join(), TEST(), and TEST().

◆ is_rightmost()

template<class T >

constexpr bool Aleph::Tree_Node< T >::is_rightmost ( ) const

inlineconstexprnoexcept

Returns true if this is the rightmost node among its siblings.

Definition at line 160 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::flags, and Aleph::Tree_Node< T >::Flags::is_rightmost.

Referenced by Aleph::Tree_Node< T >::get_right_sibling(), Aleph::Tree_Node< T >::get_right_tree(), Aleph::Tree_Node< T >::insert_left_sibling(), Aleph::Tree_Node< T >::insert_right_sibling(), Aleph::Tree_Node< T >::insert_tree_to_right(), Aleph::Tree_Node< T >::join(), TEST(), and TEST().

◆ is_root()

template<class T >

constexpr bool Aleph::Tree_Node< T >::is_root ( ) const

inlineconstexprnoexcept

Returns true if this is the root of the general tree.

Definition at line 151 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::flags, and Aleph::Tree_Node< T >::Flags::is_root.

Referenced by Aleph::Tree_Node< T >::get_parent(), Aleph::Tree_Node< T >::insert_left_sibling(), Aleph::Tree_Node< T >::insert_tree_to_right(), Aleph::Tree_Node< T >::join(), TEST(), and TEST().

◆ join()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::join ( Tree_Node< T > * tree )

inline

join tree as subtree of root this

Definition at line 415 of file tpl_tree_node.H.

◆ left_link()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::left_link ( ) const

inlineprivatenoexcept

Definition at line 119 of file tpl_tree_node.H.

References Aleph::Dlink::get_prev(), Aleph::Tree_Node< T >::sibling, and Aleph::Tree_Node< T >::sibling_to_Tree_Node().

Referenced by Aleph::Tree_Node< T >::get_last_tree(), Aleph::Tree_Node< T >::get_left_sibling(), Aleph::Tree_Node< T >::get_left_tree(), Aleph::Tree_Node< T >::get_parent(), Aleph::Tree_Node< T >::insert_rightmost_child(), and Aleph::Tree_Node< T >::join().

◆ level_traverse() [1/2]

template<class T >

template<class Op >

bool Aleph::Tree_Node< T >::level_traverse ( Op op )

inline

Definition at line 583 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::for_each_child(), Aleph::DynListQueue< T >::get(), Aleph::DynListQueue< T >::is_empty(), Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps(), and Aleph::DynListQueue< T >::put().

Referenced by Aleph::Tree_Node< T >::level_traverse().

◆ level_traverse() [2/2]

template<class T >

template<class Op >

bool Aleph::Tree_Node< T >::level_traverse ( Op op ) const

inline

Definition at line 597 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::level_traverse().

◆ lower_link()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::lower_link ( ) const

inlineprivatenoexcept

Definition at line 114 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::child, Aleph::Tree_Node< T >::child_to_Tree_Node(), and Aleph::Dlink::get_next().

Referenced by Aleph::Tree_Node< T >::get_left_child(), Aleph::Tree_Node< T >::get_right_child(), Aleph::Tree_Node< T >::insert_left_sibling(), Aleph::Tree_Node< T >::insert_leftmost_child(), Aleph::Tree_Node< T >::insert_rightmost_child(), and Aleph::Tree_Node< T >::join().

◆ preorder()

template<class T >

template<class Operation >

static bool Aleph::Tree_Node< T >::preorder	(	const Tree_Node< T > *	root,
		Operation &	op
	)

inlinestaticprivate

Definition at line 552 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::child, Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps(), Aleph::Tree_Node< T >::preorder(), and root().

Referenced by Aleph::Tree_Node< T >::preorder(), and Aleph::Tree_Node< T >::traverse().

◆ right_link()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::right_link ( ) const

inlineprivatenoexcept

Definition at line 124 of file tpl_tree_node.H.

References Aleph::Dlink::get_next(), Aleph::Tree_Node< T >::sibling, and Aleph::Tree_Node< T >::sibling_to_Tree_Node().

Referenced by Aleph::Tree_Node< T >::get_right_sibling(), and Aleph::Tree_Node< T >::get_right_tree().

◆ set_is_leaf()

template<class T >

void Aleph::Tree_Node< T >::set_is_leaf ( bool value )

inlinenoexcept

Definition at line 164 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::flags, and Aleph::Tree_Node< T >::Flags::is_leaf.

Referenced by Aleph::Tree_Node< T >::insert_leftmost_child(), Aleph::Tree_Node< T >::insert_rightmost_child(), and Aleph::Tree_Node< T >::join().

◆ set_is_leftmost()

template<class T >

void Aleph::Tree_Node< T >::set_is_leftmost ( bool value )

inlinenoexcept

Definition at line 166 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::flags, and Aleph::Tree_Node< T >::Flags::is_leftmost.

Referenced by Aleph::Tree_Node< T >::insert_left_sibling(), Aleph::Tree_Node< T >::insert_tree_to_right(), and Aleph::Tree_Node< T >::join().

◆ set_is_rightmost()

template<class T >

void Aleph::Tree_Node< T >::set_is_rightmost ( bool value )

inlinenoexcept

Definition at line 168 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::flags, and Aleph::Tree_Node< T >::Flags::is_rightmost.

Referenced by Aleph::Tree_Node< T >::insert_left_sibling(), Aleph::Tree_Node< T >::insert_right_sibling(), Aleph::Tree_Node< T >::insert_rightmost_child(), Aleph::Tree_Node< T >::insert_tree_to_right(), and Aleph::Tree_Node< T >::join().

◆ set_is_root()

template<class T >

void Aleph::Tree_Node< T >::set_is_root ( bool value )

inlinenoexcept

Definition at line 162 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::flags, and Aleph::Tree_Node< T >::Flags::is_root.

Referenced by Aleph::Tree_Node< T >::insert_left_sibling(), and Aleph::Tree_Node< T >::join().

◆ sibling_to_Tree_Node()

template<class T >

static Tree_Node * Aleph::Tree_Node< T >::sibling_to_Tree_Node ( Dlink * link )

inlinestaticprivatenoexcept

Definition at line 107 of file tpl_tree_node.H.

Referenced by Aleph::Tree_Node< T >::left_link(), and Aleph::Tree_Node< T >::right_link().

◆ traverse() [1/2]

template<class T >

template<class Operation >

bool Aleph::Tree_Node< T >::traverse ( Operation op )

inline

Preorder traversal over all nodes executing op.

Definition at line 572 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::preorder().

Referenced by TEST(), TEST(), and Aleph::Tree_Node< T >::traverse().

◆ traverse() [2/2]

template<class T >

template<class Operation >

bool Aleph::Tree_Node< T >::traverse ( Operation op ) const

inline

Definition at line 578 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::traverse().

◆ trees()

template<class T >

template<template< typename > class Container = DynList>

Container< Tree_Node * > Aleph::Tree_Node< T >::trees ( ) const

inline

Return a list with all trees belonging to the forrest.

Definition at line 504 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::get_right_tree(), and Aleph::FunctionalMixin< Tree_Node< T >, Tree_Node< T > * >::maps().

◆ upper_link()

template<class T >

Tree_Node * Aleph::Tree_Node< T >::upper_link ( ) const

inlineprivatenoexcept

Definition at line 109 of file tpl_tree_node.H.

References Aleph::Tree_Node< T >::child, Aleph::Tree_Node< T >::child_to_Tree_Node(), and Aleph::Dlink::get_prev().

Friends And Related Symbol Documentation

◆ begin [1/2]

template<class T >

const_iterator begin ( const Tree_Node< T > & s )

friend

Definition at line 767 of file tpl_tree_node.H.

◆ begin [2/2]

template<class T >

iterator begin ( Tree_Node< T > & s )

friend

Definition at line 767 of file tpl_tree_node.H.

◆ cbegin

template<class T >

const_iterator cbegin ( const Tree_Node< T > & s )

friend

Definition at line 767 of file tpl_tree_node.H.

◆ cend

template<class T >

const_iterator cend ( const Tree_Node< T > & s )

friend

Definition at line 767 of file tpl_tree_node.H.

◆ end [1/2]

template<class T >

const_iterator end ( const Tree_Node< T > & s )

friend

Definition at line 767 of file tpl_tree_node.H.

◆ end [2/2]

template<class T >

iterator end ( Tree_Node< T > & s )

friend

Definition at line 767 of file tpl_tree_node.H.

Member Data Documentation

◆ child

template<class T >

Dlink Aleph::Tree_Node< T >::child

private

Definition at line 91 of file tpl_tree_node.H.

Referenced by Aleph::Tree_Node< T >::for_each_child(), Aleph::Tree_Node< T >::get_child_list(), Aleph::Tree_Node< T >::lower_link(), Aleph::Tree_Node< T >::preorder(), and Aleph::Tree_Node< T >::upper_link().

◆ data

template<class T >

T Aleph::Tree_Node< T >::data

private

Definition at line 90 of file tpl_tree_node.H.

Referenced by Aleph::Tree_Node< T >::get_data(), and Aleph::Tree_Node< T >::get_data().

◆ flags

template<class T >

Flags Aleph::Tree_Node< T >::flags

private

Definition at line 104 of file tpl_tree_node.H.

Referenced by Aleph::Tree_Node< T >::is_leaf(), Aleph::Tree_Node< T >::is_leftmost(), Aleph::Tree_Node< T >::is_rightmost(), Aleph::Tree_Node< T >::is_root(), Aleph::Tree_Node< T >::set_is_leaf(), Aleph::Tree_Node< T >::set_is_leftmost(), Aleph::Tree_Node< T >::set_is_rightmost(), and Aleph::Tree_Node< T >::set_is_root().

◆ sibling

template<class T >

Dlink Aleph::Tree_Node< T >::sibling

private

Definition at line 92 of file tpl_tree_node.H.

Referenced by Aleph::Tree_Node< T >::get_sibling_list(), Aleph::Tree_Node< T >::left_link(), and Aleph::Tree_Node< T >::right_link().

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

tpl_tree_node.H

Classes

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ Item_Type

◆ iterator

◆ key_type

Constructor & Destructor Documentation

◆ Tree_Node() [1/3]

◆ Tree_Node() [2/3]

◆ Tree_Node() [3/3]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin() [1/2]

◆ cbegin() [2/2]

◆ cend() [1/2]

◆ cend() [2/2]

◆ child_to_Tree_Node()

◆ children()

◆ children_it()

◆ children_nodes()

◆ end() [1/2]

◆ end() [2/2]

◆ for_each_child() [1/2]

◆ for_each_child() [2/2]

◆ get_child()

◆ get_child_list()

◆ get_data() [1/2]

◆ get_data() [2/2]

◆ get_it()

◆ get_key() [1/2]

◆ get_key() [2/2]

◆ get_last_tree()

◆ get_left_child()

◆ get_left_sibling()

◆ get_left_tree()

◆ get_parent()

◆ get_right_child()

◆ get_right_sibling()

◆ get_right_tree()

◆ get_sibling_list()

◆ insert_left_sibling()

◆ insert_leftmost_child()

◆ insert_right_sibling()

◆ insert_rightmost_child()

◆ insert_tree_to_right()

◆ is_leaf()

◆ is_leftmost()

◆ is_rightmost()

◆ is_root()

◆ join()

◆ left_link()

◆ level_traverse() [1/2]

◆ level_traverse() [2/2]

◆ lower_link()

◆ preorder()

◆ right_link()

◆ set_is_leaf()

◆ set_is_leftmost()

◆ set_is_rightmost()

◆ set_is_root()

◆ sibling_to_Tree_Node()

◆ traverse() [1/2]

◆ traverse() [2/2]

◆ trees()

◆ upper_link()

Friends And Related Symbol Documentation

◆ begin [1/2]

◆ begin [2/2]

◆ cbegin

◆ cend

◆ end [1/2]