Forward declaration used by CRTP helpers before the full node definition. 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
	Adapter that exposes a node's children through an Iterator type. More...

struct	Flags

class	Iterator
	Preorder iterator over a tree rooted at a Tree_Node. More...

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
	Returns the embedded child-list link.

Dlink *	get_sibling_list () noexcept
	Returns the embedded sibling-list link.

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
	Sets the root flag.

void	set_is_leaf (bool value) noexcept
	Sets the leaf flag.

void	set_is_leftmost (bool value) noexcept
	Sets the leftmost-sibling flag.

void	set_is_rightmost (bool value) noexcept
	Sets the rightmost-sibling flag.

	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 to the right of this node.

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 forest.

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 >

Forward declaration used by CRTP helpers before the full node definition.

Generic m-ary tree node.

The Tree_Node<Key> class defines general trees of any order. Each node owns two intrusive Dlink members: sibling, which links the node with the other children of the same parent, and child, which serves as the header of the node's child list.

Internal link invariants

The representation deliberately avoids storing an explicit parent pointer. To make get_parent() O(1), the embedded child link also participates in the chain from a parent to its leftmost descendant. If a node is the leftmost child of its parent, that node's child link is connected with the parent's child-list header. Walking left across siblings to the leftmost node and then following this shared child-list spine yields the parent.

Consequently, functions that change the first child or the first sibling must preserve both structures at once:

the horizontal sibling list described by sibling;
the vertical leftmost-child spine described by child.

In particular, insert_leftmost_child(), insert_rightmost_child(), insert_left_sibling(), insert_right_sibling(), join(), and insert_tree_to_right() must keep the manual root/leaf/leftmost/ rightmost flags synchronized with the Dlink topology. A stale flag can make navigation such as get_parent() return the wrong node or trip an internal assertion.

Template Parameters

T	data type stored in each tree node.

Definition at line 113 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 912 of file tpl_tree_node.H.

◆ Item_Type

template<class T >

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

Definition at line 154 of file tpl_tree_node.H.

◆ iterator

template<class T >

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

Definition at line 912 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 179 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 289 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 293 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 912 of file tpl_tree_node.H.

◆ begin() [2/2]

template<class T >

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

inlinenoexcept

Definition at line 912 of file tpl_tree_node.H.

◆ cbegin() [1/2]

template<class T >

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

inlinenoexcept

Definition at line 912 of file tpl_tree_node.H.

◆ cbegin() [2/2]

template<class T >

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

inlinenoexcept

Definition at line 912 of file tpl_tree_node.H.

◆ cend() [1/2]

template<class T >

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

inlinenoexcept

Definition at line 912 of file tpl_tree_node.H.

◆ cend() [2/2]

template<class T >

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

inlinenoexcept

Definition at line 912 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 130 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 658 of file tpl_tree_node.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tree_Node< T >::for_each_child(), and Aleph::Tree_Node< T >::get_key().

Referenced by TEST(), and TEST().

◆ children_it()

template<class T >

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

inline

Definition at line 774 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 646 of file tpl_tree_node.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Tree_Node< T >::for_each_child().

Referenced by TEST().

◆ end() [1/2]

template<class T >

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

inlinenoexcept

Definition at line 912 of file tpl_tree_node.H.

◆ end() [2/2]

template<class T >

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

inlinenoexcept

Definition at line 912 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 639 of file tpl_tree_node.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ 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 632 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::Tree_Node< T >::level_traverse(), print_forest_deway(), and print_forest_par().

◆ 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 344 of file tpl_tree_node.H.

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

Referenced by TEST(), and TEST().

◆ get_child_list()

template<class T >

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

inlinenoexcept

Returns the embedded child-list link.

This is a low-level structural primitive used by tree algorithms and tests. It is not a stable child iterator. Mutating the returned Dlink directly requires preserving the child/sibling topology and the root/leaf/leftmost/rightmost flags described in the class invariants.

Returns: pointer to the embedded Dlink used as this node's child-list header and, for leftmost children, as part of the upward spine.

Definition at line 191 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 173 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 168 of file tpl_tree_node.H.

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

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

◆ get_it()

template<class T >

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

inline

Definition at line 907 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 162 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 157 of file tpl_tree_node.H.

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

Referenced by Aleph::Gen_Mo_On_Tree_Node< T, Policy >::build(), Aleph::Tree_Node< T >::children(), deway(), Convertir::operator()(), Write_Node::operator()(), Write_Df::operator()(), Write_Low::operator()(), WriteNode::operator()(), Write::operator()(), ProcessWriter::operator()(), Write_Ciudad::operator()(), GT_Tree< GT >::operator()(), print_forest_deway(), print_forest_par(), print_tree(), TEST(), TEST(), 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 613 of file tpl_tree_node.H.

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

◆ 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 316 of file tpl_tree_node.H.

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

Referenced by Aleph::Gen_Mo_On_Tree_Node< T, Policy >::build(), Aleph::Cnode::clone(), Aleph::Prefix_Tree_Map< T >::Node::clone_into(), 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(), 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 298 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 593 of file tpl_tree_node.H.

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

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 354 of file tpl_tree_node.H.

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

Referenced by Aleph::Gen_Mo_On_Tree_Node< T, Policy >::build(), Aleph::Tree_Node< T >::insert_left_sibling(), TEST(), TEST(), 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 325 of file tpl_tree_node.H.

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

Referenced by Aleph::Cnode::Clone_Target_Rollback::Clone_Target_Rollback(), Aleph::Cnode::Clone_Target_Rollback::~Clone_Target_Rollback(), 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 307 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(), Aleph::Tree_Node< T >::Children_Iterator::next_ne(), TEST(), 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 602 of file tpl_tree_node.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tree_Node< T >::is_rightmost(), 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

Returns the embedded sibling-list link.

This is a low-level structural primitive used by tree algorithms and tests. It is not a public sibling iterator. Mutating the returned Dlink directly requires keeping neighboring sibling flags and parent-spine links consistent.

Returns: pointer to the embedded Dlink that links this node with its left and right siblings, or with adjacent roots when this node belongs to a forest.

Definition at line 207 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 418 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 471 of file tpl_tree_node.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), 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(), root(), Aleph::Tree_Node< T >::set_is_leaf(), and SIBLING_LIST.

Referenced by TEST(), TEST(), and TEST().

◆ insert_right_sibling()

template<class T >

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

inlinenoexcept

Inserts p to the right of this node.

If this node is not a root, p is inserted as the next sibling in the same child list and therefore stops being a root. If this node is a root, p is inserted as the next root in the same forest, preserving p->is_root().

Parameters

[in] p node to insert as right sibling.

Definition at line 378 of file tpl_tree_node.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), CHILD_LIST, Aleph::Tree_Node< T >::get_right_sibling(), Aleph::Dlink::insert(), Aleph::Tree_Node< T >::insert_tree_to_right(), Aleph::Tree_Node< T >::is_rightmost(), Aleph::Tree_Node< T >::is_root(), 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 510 of file tpl_tree_node.H.

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

Referenced by Aleph::__graph_to_tree_node(), Aleph::Cnode::clone(), Aleph::Prefix_Tree_Map< T >::Node::clone_into(), Aleph::Graph_To_Tree_Node< GT, Key, Convert, SA >::graph_to_tree(), Aleph::Prefix_Tree_Map< T >::Node::insert_suffix(), TEST(), 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 forest, this method inserts 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 573 of file tpl_tree_node.H.

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

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

◆ 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 219 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 225 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(), 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 231 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(), TEST(), 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 213 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_right_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 536 of file tpl_tree_node.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), CHILD_LIST, 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 >::left_link(), Aleph::Tree_Node< T >::lower_link(), Aleph::Tree_Node< T >::set_is_leaf(), Aleph::Tree_Node< T >::set_is_leftmost(), Aleph::Tree_Node< T >::set_is_rightmost(), Aleph::Tree_Node< T >::set_is_root(), SIBLING_LINK, and SIBLING_LIST.

◆ left_link()

template<class T >

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

inlineprivatenoexcept

Definition at line 143 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 >::get_right_child(), 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 701 of file tpl_tree_node.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tree_Node< T >::for_each_child(), Aleph::DynListQueue< T >::get(), Aleph::DynListQueue< T >::is_empty(), 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 719 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 138 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 670 of file tpl_tree_node.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::Tree_Node< T >::child, preorder, and root().

◆ right_link()

template<class T >

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

inlineprivatenoexcept

Definition at line 148 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

Sets the leaf flag.

This is a low-level structural operation. It must only be used when the child-list topology already represents the same leaf/non-leaf state.

Parameters

[in] value new leaf flag value.

Definition at line 255 of file tpl_tree_node.H.

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

Referenced by Aleph::Cnode::Clone_Target_Rollback::~Clone_Target_Rollback(), 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

Sets the leftmost-sibling flag.

This is a low-level structural operation. It must only be used when the sibling list and the leftmost-child parent spine already represent the same state.

Parameters

[in] value new leftmost flag value.

Definition at line 268 of file tpl_tree_node.H.

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

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

Sets the rightmost-sibling flag.

This is a low-level structural operation. It must only be used when the sibling list already represents the same rightmost/non-rightmost state.

Parameters

[in] value new rightmost flag value.

Definition at line 280 of file tpl_tree_node.H.

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

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

Sets the root flag.

This is a low-level structural operation. It must only be used when the Dlink topology already represents the same root/non-root state.

Parameters

[in] value new root flag value.

Definition at line 243 of file tpl_tree_node.H.

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

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 131 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 689 of file tpl_tree_node.H.

References 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 695 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 forest.

Definition at line 622 of file tpl_tree_node.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Tree_Node< T >::get_right_tree().

◆ upper_link()

template<class T >

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

inlineprivatenoexcept

Definition at line 133 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 912 of file tpl_tree_node.H.

◆ begin [2/2]

template<class T >

iterator begin ( Tree_Node< T > & s )

friend

Definition at line 912 of file tpl_tree_node.H.

◆ cbegin

template<class T >

const_iterator cbegin ( const Tree_Node< T > & s )

friend

Definition at line 912 of file tpl_tree_node.H.

◆ cend

template<class T >

const_iterator cend ( const Tree_Node< T > & s )

friend

Definition at line 912 of file tpl_tree_node.H.

◆ end [1/2]

template<class T >

const_iterator end ( const Tree_Node< T > & s )

friend

Definition at line 912 of file tpl_tree_node.H.

◆ end [2/2]

template<class T >

iterator end ( Tree_Node< T > & s )

friend

Definition at line 912 of file tpl_tree_node.H.

Member Data Documentation

◆ child

template<class T >

Dlink Aleph::Tree_Node< T >::child

private

Definition at line 116 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 115 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 128 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 117 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]