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

# 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>`

List of all members.

## Public Types

enum

TraverseFlags {
TRAVERSE_LEAVES = G_TRAVERSE_LEAVES,
TRAVERSE_NON_LEAVES = G_TRAVERSE_NON_LEAVES,
TRAVERSE_ALL = G_TRAVERSE_ALL,
TRAVERSE_MASK = G_TRAVERSE_MASK
}

| Specifies which nodes are visited during several of the NodeTree methods, including traverse() and find(). More...
typedef sigc::slot< bool, NodeTree< T >& > | TraverseFunc
typedef sigc::slot< void, NodeTree< T >& > | ForeachFunc

## 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=TRAVERSE_IN_ORDER, TraverseFlags flags=TRAVERSE_ALL, int max_depth=-1)
| Traverses a tree starting at the current node.
void | foreach (const ForeachFunc& func, TraverseFlags flags=TRAVERSE_ALL)
| Calls a function for each of the children of a NodeTree.
NodeTree< T >* | find_child (const T& the_data, TraverseFlags flags=TRAVERSE_ALL)
| Finds the first child of a NodeTree with the given data.
const NodeTree< T >* | find_child (const T& the_data, TraverseFlags flags=TRAVERSE_ALL) const
| Finds the first child of a NodeTree with the given data.
NodeTree< T >* | find (const T& the_data, TraverseType order=TRAVERSE_IN_ORDER, TraverseFlags flags=TRAVERSE_ALL)
| Finds a node in a tree.
const NodeTree< T >* | find (const T& the_data, TraverseType order=TRAVERSE_IN_ORDER, TraverseFlags flags=TRAVERSE_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=TRAVERSE_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

template <typename T >

typedef sigc::slot<void, NodeTree<T>&> Glib::NodeTree< T >::ForeachFunc

template <typename T >

typedef sigc::slot<bool, NodeTree<T>&> Glib::NodeTree< T >::TraverseFunc

## Constructor & Destructor Documentation

template <typename T >

Glib::NodeTree< T >::NodeTree | ( |  | ) | `[inline]`

template <typename T >

Glib::NodeTree< T >::NodeTree | ( | const T & | the_data | ) | `[inline, explicit]`

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:

  | node | the 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:

  | data | the 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:

  | data | The 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:

  | child | A child

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

template <typename T >

const T& Glib::NodeTree< T >::data | ( |  | ) | const`[inline]`

Accessor for this node's data.

template <typename T >

T& Glib::NodeTree< T >::data | ( |  | ) | `[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 >

const NodeTree<T>* Glib::NodeTree< T >::find | ( | const T & | the_data,
|  | TraverseType | order = `TRAVERSE_IN_ORDER`,
|  | TraverseFlags | flags = `TRAVERSE_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.
  | data | The data for which to search.

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

template <typename T >

NodeTree<T>* Glib::NodeTree< T >::find | ( | const T & | the_data,
|  | TraverseType | order = `TRAVERSE_IN_ORDER`,
|  | TraverseFlags | flags = `TRAVERSE_ALL` |
| ) |  |  | `[inline]`

Finds a node in a tree.

Parameters:

  | order | The order in which nodes are visited: IN_ORDER, TRAVERSE_PRE_ORDER, TRAVERSE_POST_ORDER, or TRAVERSE_LEVEL_ORDER
  | flags | Which types of children are to be visited: one of TRAVERSE_ALL, TRAVERSE_LEAVES and TRAVERSE_NON_LEAVES.
  | data | The data for which to search.

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

template <typename T >

const NodeTree<T>* Glib::NodeTree< T >::find_child | ( | const T & | the_data,
|  | TraverseFlags | flags = `TRAVERSE_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 TRAVERSE_ALL, TRAVERSE_LEAVES and TRAVERSE_NON_LEAVES.
  | data | The data for which to search.

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

template <typename T >

NodeTree<T>* Glib::NodeTree< T >::find_child | ( | const T & | the_data,
|  | TraverseFlags | flags = `TRAVERSE_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 TRAVERSE_ALL, TRAVERSE_LEAVES and TRAVERSE_NON_LEAVES.
  | data | The data for which to search.

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

template <typename T >

const NodeTree<T>* Glib::NodeTree< T >::first_child | ( |  | ) | const`[inline]`

Gets the first child.

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

template <typename T >

NodeTree<T>* Glib::NodeTree< T >::first_child | ( |  | ) | `[inline]`

Gets the first child.

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

template <typename T >

const NodeTree<T>* Glib::NodeTree< T >::first_sibling | ( |  | ) | const`[inline]`

Gets the first sibling.

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

template <typename T >

NodeTree<T>* Glib::NodeTree< T >::first_sibling | ( |  | ) | `[inline]`

Gets the first sibling.

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

template <typename T >

void Glib::NodeTree< T >::foreach | ( | const ForeachFunc & | func,
|  | TraverseFlags | flags = `TRAVERSE_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.

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 >

const NodeTree<T>* Glib::NodeTree< T >::get_root | ( |  | ) | const`[inline]`

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 GNode* Glib::NodeTree< T >::gobj | ( |  | ) | const`[inline]`

Provides access to the underlying C GObject.

template <typename T >

GNode* Glib::NodeTree< T >::gobj | ( |  | ) | `[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:

  | 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

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

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

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
  | data | the 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:

  | sibling | the sibling NodeTree to place node before.
  | data | the 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:

  | descendant | A 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 >

const NodeTree<T>* Glib::NodeTree< T >::last_child | ( |  | ) | const`[inline]`

Gets the last child.

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

template <typename T >

NodeTree<T>* Glib::NodeTree< T >::last_child | ( |  | ) | `[inline]`

Gets the last child.

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

template <typename T >

const NodeTree<T>* Glib::NodeTree< T >::last_sibling | ( |  | ) | const`[inline]`

Gets the last sibling.

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

template <typename T >

NodeTree<T>* Glib::NodeTree< T >::last_sibling | ( |  | ) | `[inline]`

Gets the last sibling.

Returns:
  The last sibling, or 0 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 0 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 0 if the node has no siblings.

template <typename T >

guint Glib::NodeTree< T >::node_count | ( | TraverseFlags | flags = `TRAVERSE_ALL` | ) | const`[inline]`

Gets the number of nodes in a tree.

Parameters:

  | flags | Which types of children are to be counted: one of TRAVERSE_ALL, TRAVERSE_LEAVES and TRAVERSE_NON_LEAVES

Returns:
  The number of nodes in the tree.

template <typename T >

const NodeTree<T>* Glib::NodeTree< T >::nth_child | ( | int | n | ) | const`[inline]`

Gets the nth child.

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

template <typename T >

NodeTree<T>* Glib::NodeTree< T >::nth_child | ( | int | n | ) | `[inline]`

Gets the nth child.

Returns:
  The nth child, or 0 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:

  | data | the data for the NodeTree

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:

  | data | the data for the new NodeTree

Returns:
  the new NodeTree

template <typename T >

const NodeTree<T>* Glib::NodeTree< T >::prev_sibling | ( |  | ) | const`[inline]`

Gets the previous sibling.

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

template <typename T >

NodeTree<T>* Glib::NodeTree< T >::prev_sibling | ( |  | ) | `[inline]`

Gets the previous sibling.

Returns:
  The previous sibling, or 0 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 = `TRAVERSE_IN_ORDER`,
|  | TraverseFlags | flags = `TRAVERSE_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

template <typename T >

void Glib::NodeTree< T >::unlink | ( |  | ) | `[inline]`

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