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

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

 
NodeTree< T >& operator= (const NodeTree< T >& node)
 
GNode* gobj ()
 Provides access to the underlying C GObject. More...

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

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

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

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

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

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

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

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

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

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

 
void reverse_children ()
 Reverses the order of the children. More...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 
guint child_count () const
 Gets the number children. More...

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

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

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

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

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

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

 

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

template <typename T >
using Glib::NodeTree< T >::ForeachFunc = sigc::slot<void(NodeTree<T>&)>
template <typename T >
using Glib::NodeTree< T >::TraverseFunc = sigc::slot<bool(NodeTree<T>&)>

Constructor & Destructor Documentation

template <typename T >
Glib::NodeTree< T >::NodeTree ( )
inline
template <typename T >
Glib::NodeTree< T >::NodeTree ( const T &  the_data)
inlineexplicit
template <typename T >
Glib::NodeTree< T >::NodeTree ( const NodeTree< T >&  node)
inline
template <typename T >
Glib::NodeTree< T >::~NodeTree ( )
inline

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

Member Function Documentation

template <typename T >
NodeTree<T>& Glib::NodeTree< T >::append ( NodeTree< T >&  node)
inline

Inserts a NodeTree as the last child.

Parameters
nodethe NodeTree to append
Returns
the new NodeTree
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_datathe data for the new NodeTree
Returns
the new NodeTree
template <typename T >
guint Glib::NodeTree< T >::child_count ( ) const
inline

Gets the number children.

Returns
The number of children.
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_dataThe data to find.
Returns
The index of the child which contains data, or -1 if the data is not found.
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
childA child
Returns
The position of child with respect to its siblings.
template <typename T >
T& Glib::NodeTree< T >::data ( )
inline

Accessor for this node's data.

template <typename T >
const T& Glib::NodeTree< T >::data ( ) const
inline

Accessor for this node's data.

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
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
orderThe order in which nodes are visited: TraverseType::IN_ORDER, TraverseType::PRE_ORDER, TraverseType::POST_ORDER, or TraverseType::LEVEL_ORDER
flagsWhich types of children are to be visited: one of TraverseFlags::ALL, TraverseFlags::LEAVES or TraverseFlags::NON_LEAVES.
the_dataThe data for which to search.
Returns
The found node, or nullptr if the data is not found.
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
orderThe order in which nodes are visited.
flagsWhich types of children are to be visited.
the_dataThe data for which to search.
Returns
The found node, or nullptr if the data is not found.
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
flagsWhich types of children are to be visited, one of TraverseFlags::ALL, TraverseFlags::LEAVES or TraverseFlags::NON_LEAVES.
the_dataThe data for which to search.
Returns
the found child, or nullptr if the data is not found
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
flagsWhich types of children are to be visited, one of TraverseFlags::ALL, TraverseFlags::LEAVES or TraverseFlags::NON_LEAVES.
the_dataThe data for which to search.
Returns
the found child, or nullptr if the data is not found
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.
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.
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.
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.
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
flagsWwhich types of children are to be visited.
funcThe slot to invoke for each visited node.
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.
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.
template <typename T >
const NodeTree<T>* Glib::NodeTree< T >::get_root ( ) const
inline
template <typename T >
GNode* Glib::NodeTree< T >::gobj ( )
inline

Provides access to the underlying C GObject.

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

Provides access to the underlying C GObject.

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
positionthe position to place node at, with respect to its siblings If position is -1, node is inserted as the last child of parent
nodethe NodeTree to insert
Returns
the inserted NodeTree
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
siblingthe sibling NodeTree to place node after.
nodethe NodeTree to insert
Returns
the inserted NodeTree
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
siblingthe sibling NodeTree to place node before.
nodethe NodeTree to insert
Returns
the inserted NodeTree
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
positionthe position to place the new NodeTree at. If position is -1, the new NodeTree is inserted as the last child of parent
the_datathe data for the new NodeTree
Returns
the new NodeTree
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
siblingthe sibling NodeTree to place node before.
the_datathe data for the new NodeTree
Returns
the new NodeTree
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
descendantA node.
Returns
true if this is an ancestor of descendant.
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.
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.
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.
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.
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.
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.
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.
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.
template <typename T >
guint Glib::NodeTree< T >::node_count ( TraverseFlags  flags = TraverseFlags::ALL) const
inline

Gets the number of nodes in a tree.

Parameters
flagsWhich 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.
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.
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.
template <typename T >
NodeTree<T>& Glib::NodeTree< T >::operator= ( const NodeTree< T >&  node)
inline
template <typename T >
const NodeTree<T>* Glib::NodeTree< T >::parent ( ) const
inline

Accessor for this node's parent.

Returns
The node's parent.
template <typename T >
NodeTree<T>& Glib::NodeTree< T >::prepend ( NodeTree< T >&  node)
inline

Inserts a NodeTree as the first child.

Parameters
nodethe NodeTree to prepend
Returns
the NodeTree
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_datathe data for the new NodeTree
Returns
the new NodeTree
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.
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.
template <typename T >
void Glib::NodeTree< T >::reverse_children ( )
inline

Reverses the order of the children.

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
orderThe order in which nodes are visited.
flagsWhich types of children are to be visited.
max_depthThe 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.
functhe slot to invoke for each visited child
template <typename T >
void Glib::NodeTree< T >::unlink ( )
inline

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