glibmm: Glib::NodeTree< T > Class Template Reference

N-ary Trees - trees of data with any number of branches The NodeTree class and its associated functions provide an N-ary tree data structure, in which nodes in the tree can contain arbitrary data. More...

#include <glibmm/nodetree.h>

Public Types
enum class	TraverseType { IN_ORDER , PRE_ORDER , POST_ORDER , LEVEL_ORDER }

enum class	TraverseFlags { TraverseFlags::LEAVES = G_TRAVERSE_LEAVES , TraverseFlags::NON_LEAVES = G_TRAVERSE_NON_LEAVES , TraverseFlags::ALL = G_TRAVERSE_ALL , TraverseFlags::MASK = G_TRAVERSE_MASK }
	Specifies which nodes are visited during several of the NodeTree methods, including traverse() and find(). More...

using	TraverseFunc = sigc::slot< bool(NodeTree< T > &)>

using	ForeachFunc = sigc::slot< void(NodeTree< T > &)>

Public Member Functions
	NodeTree ()

	NodeTree (const T &the_data)

	NodeTree (const NodeTree< T > &node)

	~NodeTree ()
	Removes the instance and its children from the tree, freeing any memory allocated.

NodeTree< T > &	operator= (const NodeTree< T > &node)

GNode *	gobj ()
	Provides access to the underlying C GObject.

const GNode *	gobj () const
	Provides access to the underlying C GObject.

NodeTree< T > &	insert (int position, NodeTree< T > &node)
	Inserts a NodeTree beneath the parent at the given position.

NodeTree< T > &	insert_before (NodeTree< T > &sibling, NodeTree< T > &node)
	Inserts a NodeTree beneath the parent before the given sibling.

NodeTree< T > &	insert_after (NodeTree< T > &sibling, NodeTree< T > &node)
	Inserts a NodeTree beneath the parent after the given sibling.

NodeTree< T > &	append (NodeTree< T > &node)
	Inserts a NodeTree as the last child.

NodeTree< T > &	prepend (NodeTree< T > &node)
	Inserts a NodeTree as the first child.

NodeTree< T > *	insert_data (int position, const T &the_data)
	Inserts a new NodeTree at the given position.

NodeTree< T > *	insert_data_before (NodeTree< T > &sibling, const T &the_data)
	Inserts a new NodeTree before the given sibling.

NodeTree< T > *	append_data (const T &the_data)
	Inserts a new NodeTree as the last child.

NodeTree< T > *	prepend_data (const T &the_data)
	Inserts a new NodeTree as the first child.

void	reverse_children ()
	Reverses the order of the children.

NodeTree< T > *	get_root ()
	Returns a pointer to the root of the tree.

const NodeTree< T > *	get_root () const

void	traverse (const TraverseFunc &func, TraverseType order=TraverseType::IN_ORDER, TraverseFlags flags=TraverseFlags::ALL, int max_depth=-1)
	Traverses a tree starting at the current node.

void	foreach (const ForeachFunc &func, TraverseFlags flags=TraverseFlags::ALL)
	Calls a function for each of the children of a NodeTree.

NodeTree< T > *	find_child (const T &the_data, TraverseFlags flags=TraverseFlags::ALL)
	Finds the first child of a NodeTree with the given data.

const NodeTree< T > *	find_child (const T &the_data, TraverseFlags flags=TraverseFlags::ALL) const
	Finds the first child of a NodeTree with the given data.

NodeTree< T > *	find (const T &the_data, TraverseType order=TraverseType::IN_ORDER, TraverseFlags flags=TraverseFlags::ALL)
	Finds a node in a tree.

const NodeTree< T > *	find (const T &the_data, TraverseType order=TraverseType::IN_ORDER, TraverseFlags flags=TraverseFlags::ALL) const
	Finds a node in a tree.

int	child_index (const T &the_data) const
	Gets the position of the first child which contains the given data.

int	child_position (const NodeTree< T > &child) const
	Gets the position with respect to its siblings.

NodeTree< T > *	first_child ()
	Gets the first child.

const NodeTree< T > *	first_child () const
	Gets the first child.

NodeTree< T > *	last_child ()
	Gets the last child.

const NodeTree< T > *	last_child () const
	Gets the last child.

NodeTree< T > *	nth_child (int n)
	Gets the nth child.

const NodeTree< T > *	nth_child (int n) const
	Gets the nth child.

NodeTree< T > *	first_sibling ()
	Gets the first sibling.

const NodeTree< T > *	first_sibling () const
	Gets the first sibling.

NodeTree< T > *	prev_sibling ()
	Gets the previous sibling.

const NodeTree< T > *	prev_sibling () const
	Gets the previous sibling.

NodeTree< T > *	next_sibling ()
	Gets the next sibling.

const NodeTree< T > *	next_sibling () const
	Gets the next sibling.

NodeTree< T > *	last_sibling ()
	Gets the last sibling.

const NodeTree< T > *	last_sibling () const
	Gets the last sibling.

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

bool	is_root () const
	Returns true if this is the root node.

guint	depth () const
	Gets the depth of this node.

guint	node_count (TraverseFlags flags=TraverseFlags::ALL) const
	Gets the number of nodes in a tree.

guint	child_count () const
	Gets the number children.

bool	is_ancestor (const NodeTree< T > &descendant) const
	Returns true if this is an ancestor of descendant.

guint	get_max_height () const
	Gets the maximum height of all branches beneath this node.

void	unlink ()
	Unlinks a node from a tree, resulting in two separate trees.

T &	data ()
	Accessor for this node's data.

const T &	data () const
	Accessor for this node's data.

const NodeTree< T > *	parent () const
	Accessor for this node's parent.

Detailed Description

template<typename T>
class Glib::NodeTree< T >

N-ary Trees - trees of data with any number of branches The NodeTree class and its associated functions provide an N-ary tree data structure, in which nodes in the tree can contain arbitrary data.

To insert a node into a tree use insert(), insert_before(), append() or prepend().

To create a new node and insert it into a tree use insert_data(), insert_data_before(), append_data() and prepend_data().

To reverse the children of a node use reverse_children().

To find a node use root(), find(), find_child(), index_of(), child_index(), first_child(), last_child(), nth_child(), first_sibling(), prev_sibling(), next_sibling() or last_sibling().

To get information about a node or tree use is_leaf(), is_root(), depth(), node_count(), child_count(), is_ancestor() or max_height().

To traverse a tree, calling a function for each node visited in the traversal, use traverse() or foreach().

To remove a node or subtree from a tree use unlink().

Since glibmm 2.18:

Member Typedef Documentation

◆ ForeachFunc

template <typename T >

using Glib::NodeTree< T >::ForeachFunc = sigc::slot<void(NodeTree<T>&)>

◆ TraverseFunc

template <typename T >

using Glib::NodeTree< T >::TraverseFunc = sigc::slot<bool(NodeTree<T>&)>

Member Enumeration Documentation

◆ TraverseType

template <typename T >

enum class Glib::NodeTree::TraverseType

strong

Enumerator
IN_ORDER	Vists a node's left child first, then the node itself, then its right child. This is the one to use if you want the output sorted according to the compare function.
PRE_ORDER	Visits a node, then its children.
POST_ORDER	Visits the node's children, then the node itself.
LEVEL_ORDER	Is not implemented for [balanced binary trees][glib-Balanced-Binary-Trees]. For [n-ary trees][glib-N-ary-Trees], it vists the root node first, then its children, then its grandchildren, and so on. Note that this is less efficient than the other orders.

Constructor & Destructor Documentation

◆ NodeTree() [1/3]

template <typename T >

Glib::NodeTree< T >::NodeTree ( )

inline

◆ NodeTree() [2/3]

template <typename T >

Glib::NodeTree< T >::NodeTree ( const T & the_data )

inlineexplicit

◆ NodeTree() [3/3]

template <typename T >

Glib::NodeTree< T >::NodeTree ( const NodeTree< T > & node )

inline

◆ ~NodeTree()

template <typename T >

Glib::NodeTree< T >::~NodeTree ( )

inline

Removes the instance and its children from the tree, freeing any memory allocated.

Member Function Documentation

◆ append()

template <typename T >

NodeTree< T > & Glib::NodeTree< T >::append ( NodeTree< T > & node )

inline

Inserts a NodeTree as the last child.

Parameters

node	the NodeTree to append

Returns: the new NodeTree

◆ append_data()

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::append_data ( const T & the_data )

inline

Inserts a new NodeTree as the last child.

Parameters

the_data the data for the new NodeTree

Returns: the new NodeTree

◆ child_count()

template <typename T >

guint Glib::NodeTree< T >::child_count ( ) const

inline

Gets the number children.

Returns: The number of children.

◆ child_index()

template <typename T >

int Glib::NodeTree< T >::child_index ( const T & the_data ) const

inline

Gets the position of the first child which contains the given data.

Parameters

the_data The data to find.

Returns: The index of the child which contains data, or -1 if the data is not found.

◆ child_position()

template <typename T >

int Glib::NodeTree< T >::child_position ( const NodeTree< T > & child ) const

inline

Gets the position with respect to its siblings.

child must be a child of node. The first child is numbered 0, the second 1, and so on.

Parameters

child A child

Returns: The position of child with respect to its siblings.

◆ data() [1/2]

template <typename T >

T & Glib::NodeTree< T >::data ( )

inline

Accessor for this node's data.

◆ data() [2/2]

template <typename T >

const T & Glib::NodeTree< T >::data ( ) const

inline

Accessor for this node's data.

◆ depth()

template <typename T >

guint Glib::NodeTree< T >::depth ( ) const

inline

Gets the depth of this node.

The root node has a depth of 1. For the children of the root node the depth is 2. And so on.

Returns: the depth of this node

◆ find() [1/2]

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::find	(	const T &	the_data,
		TraverseType	order = `TraverseType::IN_ORDER`,
		TraverseFlags	flags = `TraverseFlags::ALL`
	)

inline

Finds a node in a tree.

Parameters

order	The order in which nodes are visited: TraverseType::IN_ORDER, TraverseType::PRE_ORDER, TraverseType::POST_ORDER, or TraverseType::LEVEL_ORDER
flags	Which types of children are to be visited: one of TraverseFlags::ALL, TraverseFlags::LEAVES or TraverseFlags::NON_LEAVES.
the_data	The data for which to search.

Returns: The found node, or nullptr if the data is not found.

◆ find() [2/2]

template <typename T >

const NodeTree< T > * Glib::NodeTree< T >::find	(	const T &	the_data,
		TraverseType	order = `TraverseType::IN_ORDER`,
		TraverseFlags	flags = `TraverseFlags::ALL`
	)		const

inline

Finds a node in a tree.

Parameters

order	The order in which nodes are visited.
flags	Which types of children are to be visited.
the_data	The data for which to search.

Returns: The found node, or nullptr if the data is not found.

◆ find_child() [1/2]

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::find_child	(	const T &	the_data,
		TraverseFlags	flags = `TraverseFlags::ALL`
	)

inline

Finds the first child of a NodeTree with the given data.

Parameters

flags	Which types of children are to be visited, one of TraverseFlags::ALL, TraverseFlags::LEAVES or TraverseFlags::NON_LEAVES.
the_data	The data for which to search.

Returns: the found child, or nullptr if the data is not found

◆ find_child() [2/2]

template <typename T >

const NodeTree< T > * Glib::NodeTree< T >::find_child	(	const T &	the_data,
		TraverseFlags	flags = `TraverseFlags::ALL`
	)		const

inline

Finds the first child of a NodeTree with the given data.

Parameters

flags	Which types of children are to be visited, one of TraverseFlags::ALL, TraverseFlags::LEAVES or TraverseFlags::NON_LEAVES.
the_data	The data for which to search.

Returns: the found child, or nullptr if the data is not found

◆ first_child() [1/2]

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::first_child ( )

inline

Gets the first child.

Returns: The first child, or nullptr if the node has no children.

◆ first_child() [2/2]

template <typename T >

const NodeTree< T > * Glib::NodeTree< T >::first_child ( ) const

inline

Gets the first child.

Returns: The first child, or nullptr if the node has no children.

◆ first_sibling() [1/2]

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::first_sibling ( )

inline

Gets the first sibling.

Returns: The first sibling, or nullptr if the node has no siblings.

◆ first_sibling() [2/2]

template <typename T >

const NodeTree< T > * Glib::NodeTree< T >::first_sibling ( ) const

inline

Gets the first sibling.

Returns: The first sibling, or nullptr if the node has no siblings.

◆ foreach()

template <typename T >

void Glib::NodeTree< T >::foreach	(	const ForeachFunc &	func,
		TraverseFlags	flags = `TraverseFlags::ALL`
	)

inline

Calls a function for each of the children of a NodeTree.

Note that it doesn't descend beneath the child nodes.

Parameters

flags	Wwhich types of children are to be visited.
func	The slot to invoke for each visited node.

◆ get_max_height()

template <typename T >

guint Glib::NodeTree< T >::get_max_height ( ) const

inline

Gets the maximum height of all branches beneath this node.

This is the maximum distance from the node to all leaf nodes. If root has no children, 1 is returned. If root has children, 2 is returned. And so on.

Returns: The maximum height of all branches.

◆ get_root() [1/2]

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::get_root ( )

inline

Returns a pointer to the root of the tree.

Returns: A pointer to the root of the tree.

◆ get_root() [2/2]

template <typename T >

const NodeTree< T > * Glib::NodeTree< T >::get_root ( ) const

inline

◆ gobj() [1/2]

template <typename T >

GNode * Glib::NodeTree< T >::gobj ( )

inline

Provides access to the underlying C GObject.

◆ gobj() [2/2]

template <typename T >

const GNode * Glib::NodeTree< T >::gobj ( ) const

inline

Provides access to the underlying C GObject.

◆ insert()

template <typename T >

NodeTree< T > & Glib::NodeTree< T >::insert	(	int	position,
		NodeTree< T > &	node
	)

inline

Inserts a NodeTree beneath the parent at the given position.

Parameters

position	the position to place node at, with respect to its siblings If position is -1, node is inserted as the last child of parent
node	the NodeTree to insert

Returns: the inserted NodeTree

◆ insert_after()

template <typename T >

NodeTree< T > & Glib::NodeTree< T >::insert_after	(	NodeTree< T > &	sibling,
		NodeTree< T > &	node
	)

inline

Inserts a NodeTree beneath the parent after the given sibling.

Parameters

sibling	the sibling NodeTree to place node after.
node	the NodeTree to insert

Returns: the inserted NodeTree

◆ insert_before()

template <typename T >

NodeTree< T > & Glib::NodeTree< T >::insert_before	(	NodeTree< T > &	sibling,
		NodeTree< T > &	node
	)

inline

Inserts a NodeTree beneath the parent before the given sibling.

Parameters

sibling	the sibling NodeTree to place node before.
node	the NodeTree to insert

Returns: the inserted NodeTree

◆ insert_data()

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::insert_data	(	int	position,
		const T &	the_data
	)

inline

Inserts a new NodeTree at the given position.

Parameters

position	the position to place the new NodeTree at. If position is -1, the new NodeTree is inserted as the last child of parent
the_data	the data for the new NodeTree

Returns: the new NodeTree

◆ insert_data_before()

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::insert_data_before	(	NodeTree< T > &	sibling,
		const T &	the_data
	)

inline

Inserts a new NodeTree before the given sibling.

Parameters

sibling	the sibling NodeTree to place node before.
the_data	the data for the new NodeTree

Returns: the new NodeTree

◆ is_ancestor()

template <typename T >

bool Glib::NodeTree< T >::is_ancestor ( const NodeTree< T > & descendant ) const

inline

Returns true if this is an ancestor of descendant.

This is true if this is the parent of descendant, or if this is the grandparent of descendant etc.

Parameters

descendant A node.

Returns: true if this is an ancestor of descendant.

◆ is_leaf()

template <typename T >

bool Glib::NodeTree< T >::is_leaf ( ) const

inline

Returns true if this is a leaf node.

Returns: true if this is a leaf node.

◆ is_root()

template <typename T >

bool Glib::NodeTree< T >::is_root ( ) const

inline

Returns true if this is the root node.

Returns: true if this is the root node.

◆ last_child() [1/2]

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::last_child ( )

inline

Gets the last child.

Returns: The last child, or nullptr if the node has no children.

◆ last_child() [2/2]

template <typename T >

const NodeTree< T > * Glib::NodeTree< T >::last_child ( ) const

inline

Gets the last child.

Returns: The last child, or nullptr if the node has no children.

◆ last_sibling() [1/2]

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::last_sibling ( )

inline

Gets the last sibling.

Returns: The last sibling, or nullptr if the node has no siblings.

◆ last_sibling() [2/2]

template <typename T >

const NodeTree< T > * Glib::NodeTree< T >::last_sibling ( ) const

inline

Gets the last sibling.

Returns: The last sibling, or nullptr if the node has no siblings.

◆ next_sibling() [1/2]

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::next_sibling ( )

inline

Gets the next sibling.

Returns: The next sibling, or nullptr if the node has no siblings.

◆ next_sibling() [2/2]

template <typename T >

const NodeTree< T > * Glib::NodeTree< T >::next_sibling ( ) const

inline

Gets the next sibling.

Returns: The next sibling, or nullptr if the node has no siblings.

◆ node_count()

template <typename T >

guint Glib::NodeTree< T >::node_count ( TraverseFlags flags = TraverseFlags::ALL ) const

inline

Gets the number of nodes in a tree.

Parameters

flags Which types of children are to be counted: one of TraverseFlags::ALL, TraverseFlags::LEAVES or TraverseFlags::NON_LEAVES

Returns: The number of nodes in the tree.

◆ nth_child() [1/2]

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::nth_child ( int n )

inline

Gets the nth child.

Returns: The nth child, or nullptr if n is too large.

◆ nth_child() [2/2]

template <typename T >

const NodeTree< T > * Glib::NodeTree< T >::nth_child ( int n ) const

inline

Gets the nth child.

Returns: The nth child, or nullptr if n is too large.

◆ operator=()

template <typename T >

NodeTree< T > & Glib::NodeTree< T >::operator= ( const NodeTree< T > & node )

inline

◆ parent()

template <typename T >

const NodeTree< T > * Glib::NodeTree< T >::parent ( ) const

inline

Accessor for this node's parent.

Returns: The node's parent.

◆ prepend()

template <typename T >

NodeTree< T > & Glib::NodeTree< T >::prepend ( NodeTree< T > & node )

inline

Inserts a NodeTree as the first child.

Parameters

node	the NodeTree to prepend

Returns: the NodeTree

◆ prepend_data()

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::prepend_data ( const T & the_data )

inline

Inserts a new NodeTree as the first child.

Parameters

the_data the data for the new NodeTree

Returns: the new NodeTree

◆ prev_sibling() [1/2]

template <typename T >

NodeTree< T > * Glib::NodeTree< T >::prev_sibling ( )

inline

Gets the previous sibling.

Returns: The previous sibling, or nullptr if the node has no siblings.

◆ prev_sibling() [2/2]

template <typename T >

const NodeTree< T > * Glib::NodeTree< T >::prev_sibling ( ) const

inline

Gets the previous sibling.

Returns: The previous sibling, or nullptr if the node has no siblings.

◆ reverse_children()

template <typename T >

void Glib::NodeTree< T >::reverse_children ( )

inline

Reverses the order of the children.

◆ traverse()

template <typename T >

void Glib::NodeTree< T >::traverse	(	const TraverseFunc &	func,
		TraverseType	order = `TraverseType::IN_ORDER`,
		TraverseFlags	flags = `TraverseFlags::ALL`,
		int	max_depth = `-1`
	)

inline

Traverses a tree starting at the current node.

It calls the given function for each node visited. The traversal can be halted at any point by returning true from func.

Parameters

order	The order in which nodes are visited.
flags	Which types of children are to be visited.
max_depth	The maximum depth of the traversal. Nodes below this depth will not be visited. If max_depth is -1 all nodes in the tree are visited. If max_depth is 1, only the root is visited. If max_depth is 2, the root and its children are visited. And so on.
func	the slot to invoke for each visited child

◆ unlink()

template <typename T >

void Glib::NodeTree< T >::unlink ( )

inline

Unlinks a node from a tree, resulting in two separate trees.

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ ForeachFunc

◆ TraverseFunc

Member Enumeration Documentation

◆ TraverseType

Constructor & Destructor Documentation

◆ NodeTree() [1/3]

◆ NodeTree() [2/3]

◆ NodeTree() [3/3]

◆ ~NodeTree()

Member Function Documentation

◆ append()

◆ append_data()

◆ child_count()

◆ child_index()

◆ child_position()

◆ data() [1/2]

◆ data() [2/2]

◆ depth()

◆ find() [1/2]

◆ find() [2/2]

◆ find_child() [1/2]

◆ find_child() [2/2]

◆ first_child() [1/2]

◆ first_child() [2/2]

◆ first_sibling() [1/2]

◆ first_sibling() [2/2]

◆ foreach()

◆ get_max_height()

◆ get_root() [1/2]

◆ get_root() [2/2]

◆ gobj() [1/2]

◆ gobj() [2/2]

◆ insert()

◆ insert_after()

◆ insert_before()

◆ insert_data()

◆ insert_data_before()

◆ is_ancestor()

◆ is_leaf()

◆ is_root()

◆ last_child() [1/2]

◆ last_child() [2/2]

◆ last_sibling() [1/2]

◆ last_sibling() [2/2]

◆ next_sibling() [1/2]

◆ next_sibling() [2/2]

◆ node_count()

◆ nth_child() [1/2]

◆ nth_child() [2/2]

◆ operator=()

◆ parent()

◆ prepend()

◆ prepend_data()

◆ prev_sibling() [1/2]

◆ prev_sibling() [2/2]

◆ reverse_children()

◆ traverse()

◆ unlink()