logo top
Main Page   Widgets   glibmm Namespaces   Book  

Glib::Tree< T > Class Template Reference

N-ary Trees — trees of data with any number of branches. More...

List of all members.

Public Types

typedef GNode* iterator
typedef sigc::slot
<gboolean, iterator>* 
TraverseFunc
typedef sigc::slot
<void, iterator>* 
ForeachFunc
typedef std::map
<GNode*, Tree<T>*> 
NodeMap

Public Member Functions

 Tree ()
 Creates a new GNode containing the given data.
 Tree (T& data)
 ~Tree ()
 Removes the instance and its children from the tree, freeing any memory allocated.
Tree<T>& insert (int position, Tree<T>& node)
 Inserts a Tree beneath the parent at the given position.
Tree<T>& insert_before (Tree<T>& sibling, Tree<T>& node)
 Inserts a Tree beneath the parent before the given sibling.
Tree<T>& insert_after (Tree<T>& sibling, Tree<T>& node)
 Inserts a Tree beneath the parent after the given sibling.
Tree<T>& append (Tree<T>& node)
 Inserts a Tree as the last child.
Tree<T>& prepend (Tree<T>& node)
 Inserts a Tree as the first child.
Tree<T>* insert_data (int position, T& data)
 Inserts a new Tree at the given position.
Tree<T>* insert_data_before (Tree<T>& sibling, T& data)
 Inserts a new Tree before the given sibling.
Tree<T>* append_data (T& data)
 Inserts a new Tree as the last child.
Tree<T>* prepend_data (T& data)
 Inserts a new Tree as the first child.
void reverse_children ()
 Reverses the order of the children.
Tree<T>* root () const
 Returns a pointer to the root of the tree.
void traverse (TraverseType order, TraverseFlags flags, int max_depth, TraverseFunc func)
 Traverses a tree starting at the current node It calls the given function for each node visited.
void foreach (TraverseFlags flags, ForeachFunc func)
 Calls a function for each of the children of a GNode.
Tree<T>* find_child (TraverseFlags flags, const T& data) const
 Finds the first child of a GNode with the given data.
Tree<T>* find (TraverseType order, TraverseFlags flags, const T& data) const
 Finds a node in a tree.
int index_of (const T& data) const
 Gets the position of the first child which contains the given data.
int position_of (const Tree<T>& child) const
 Gets the position with respect to its siblings.
Tree<T>* first_child () const
 Gets the first child.
Tree<T>* last_child () const
 Gets the last child.
Tree<T>* nth_child (int n) const
 Gets the nth child.
Tree<T>* first_sibling () const
 Gets the first sibling.
Tree<T>* prev_sibling () const
 Gets the prev sibling.
Tree<T>* next_sibling () const
 Gets the next sibling.
Tree<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.
unsigned int depth () const
 Gets the depth of this node The root node has a depth of 1.
unsigned int node_count (TraverseFlags flags) const
 Gets the number of nodes in a tree.
unsigned int child_count () const
 Gets the number children.
bool is_ancestor (const Tree<T>& descendant) const
 Returns TRUE if this is an ancestor of descendant.
unsigned int max_height () const
 Gets the maximum height of all branches beneath this node.
void unlink (Tree<T>& child)
 Unlinks a GNode from a tree, resulting in two separate trees.
iterator iter () const
 Accessor for this node's iterator.
data () const
 Accessor for this node's data.
Tree<T>* lookup (const iterator child) const
 Lookup a child by its iterator.
Tree<T>* parent (Tree<T>* newparent=NULL)
 Accessor for this node's parent Don't use this.
GNode* gobj ()
 For auto-wrapping.
const GNode* gobj () const

Static Protected Member Functions

static gboolean wrap_traverse_slot (GNode* node, gpointer slot)
static void wrap_foreach_slot (GNode* node, gpointer slot)

Protected Attributes

GNode* gobject_
 Leaving these unimplemented for now.
bool owns_gobject_
NodeMap children_
 Some metadata must be stored.
Tree<T>* parent_


Detailed Description

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

N-ary Trees — trees of data with any number of branches.

The Tree class and its associated functions provide a N-ary tree data structure, where nodes in the tree can contain arbitrary data.

To insert a node into a tree use insert(), insert_before(), append() and 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(), position_of(), 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().


Member Typedef Documentation

template <typename T>
typedef GNode* Glib::Tree<T>::iterator

template <typename T>
typedef sigc::slot<gboolean, iterator>* Glib::Tree<T>::TraverseFunc

template <typename T>
typedef sigc::slot<void, iterator>* Glib::Tree<T>::ForeachFunc

template <typename T>
typedef std::map<GNode*,Tree<T>*> Glib::Tree<T>::NodeMap


Constructor & Destructor Documentation

template <typename T>
Glib::Tree<T>::Tree (  )  [inline]

Creates a new GNode containing the given data.

Used to create the first node in a tree.

template <typename T>
Glib::Tree<T>::Tree ( T &  data  )  [inline, explicit]

template <typename T>
Glib::Tree<T>::~Tree (  )  [inline]

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


Member Function Documentation

template <typename T>
Tree<T>& Glib::Tree<T>::insert ( int  position,
Tree<T>&  node 
) [inline]

Inserts a Tree 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 Tree to insert
Returns:
the inserted Tree

template <typename T>
Tree<T>& Glib::Tree<T>::insert_before ( Tree<T>&  sibling,
Tree<T>&  node 
) [inline]

Inserts a Tree beneath the parent before the given sibling.

Parameters:
sibling the sibling Tree to place node before.
node the Tree to insert
Returns:
the inserted Tree

template <typename T>
Tree<T>& Glib::Tree<T>::insert_after ( Tree<T>&  sibling,
Tree<T>&  node 
) [inline]

Inserts a Tree beneath the parent after the given sibling.

Parameters:
sibling the sibling Tree to place node after.
node the Tree to insert
Returns:
the inserted Tree

template <typename T>
Tree<T>& Glib::Tree<T>::append ( Tree<T>&  node  )  [inline]

Inserts a Tree as the last child.

Parameters:
node the Tree to append
Returns:
the new Tree

template <typename T>
Tree<T>& Glib::Tree<T>::prepend ( Tree<T>&  node  )  [inline]

Inserts a Tree as the first child.

Parameters:
data the data for the Tree
Returns:
the Tree

template <typename T>
Tree<T>* Glib::Tree<T>::insert_data ( int  position,
T &  data 
) [inline]

Inserts a new Tree at the given position.

Parameters:
position the position to place the new Tree at. If position is -1, the new Tree is inserted as the last child of parent
data the data for the new Tree
Returns:
the new Tree

template <typename T>
Tree<T>* Glib::Tree<T>::insert_data_before ( Tree<T>&  sibling,
T &  data 
) [inline]

Inserts a new Tree before the given sibling.

Parameters:
sibling the sibling Tree to place node before.
data the data for the new Tree
Returns:
the new Tree

template <typename T>
Tree<T>* Glib::Tree<T>::append_data ( T &  data  )  [inline]

Inserts a new Tree as the last child.

Parameters:
data the data for the new Tree
Returns:
the new Tree

template <typename T>
Tree<T>* Glib::Tree<T>::prepend_data ( T &  data  )  [inline]

Inserts a new Tree as the first child.

Parameters:
data the data for the new Tree
Returns:
the new Tree

template <typename T>
void Glib::Tree<T>::reverse_children (  )  [inline]

Reverses the order of the children.

template <typename T>
Tree<T>* Glib::Tree<T>::root (  )  const [inline]

Returns a pointer to the root of the tree.

Returns:
a pointer to the root of the tree

template <typename T>
void Glib::Tree<T>::traverse ( TraverseType  order,
TraverseFlags  flags,
int  max_depth,
TraverseFunc  func 
) [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: TRAVERSE_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
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 depth is 1, only the root is visited. If 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::Tree<T>::foreach ( TraverseFlags  flags,
ForeachFunc  func 
) [inline]

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

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

Parameters:
flags which types of children are to be visited, one of TRAVERSE_ALL, TRAVERSE_LEAVES and TRAVERSE_NON_LEAVES
func the slot to invoke for each visited node

template <typename T>
Tree<T>* Glib::Tree<T>::find_child ( TraverseFlags  flags,
const T &  data 
) const [inline]

Finds the first child of a GNode 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 user data to pass to the function
Returns:
the found child, or NULL if the data is not found

template <typename T>
Tree<T>* Glib::Tree<T>::find ( TraverseType  order,
TraverseFlags  flags,
const T &  data 
) const [inline]

Finds a node in a tree.

Parameters:
order The order in which nodes are visited: TRAVERSE_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
Returns:
the found node, or NULL if the data is not found

template <typename T>
int Glib::Tree<T>::index_of ( const T &  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::Tree<T>::position_of ( const Tree<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>
Tree<T>* Glib::Tree<T>::first_child (  )  const [inline]

Gets the first child.

Returns:
the first child, or NULL if node has no children

template <typename T>
Tree<T>* Glib::Tree<T>::last_child (  )  const [inline]

Gets the last child.

Returns:
the last child, or NULL if node has no children

template <typename T>
Tree<T>* Glib::Tree<T>::nth_child ( int  n  )  const [inline]

Gets the nth child.

Returns:
the nth child, or NULL if n is too large

template <typename T>
Tree<T>* Glib::Tree<T>::first_sibling (  )  const [inline]

Gets the first sibling.

Returns:
the first sibling, or NULL if node has no siblings

template <typename T>
Tree<T>* Glib::Tree<T>::prev_sibling (  )  const [inline]

Gets the prev sibling.

Returns:
the prev sibling, or NULL if node has no siblings

template <typename T>
Tree<T>* Glib::Tree<T>::next_sibling (  )  const [inline]

Gets the next sibling.

Returns:
the next sibling, or NULL if node has no siblings

template <typename T>
Tree<T>* Glib::Tree<T>::last_sibling (  )  const [inline]

Gets the last sibling.

Returns:
the last sibling, or NULL if node has no siblings

template <typename T>
bool Glib::Tree<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::Tree<T>::is_root (  )  const [inline]

Returns true if this is the root node.

Returns:
true if this is the root node.

template <typename T>
unsigned int Glib::Tree<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>
unsigned int Glib::Tree<T>::node_count ( TraverseFlags  flags  )  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>
unsigned int Glib::Tree<T>::child_count (  )  const [inline]

Gets the number children.

Returns:
the number of children

template <typename T>
bool Glib::Tree<T>::is_ancestor ( const Tree<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>
unsigned int Glib::Tree<T>::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>
void Glib::Tree<T>::unlink ( Tree<T>&  child  )  [inline]

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

template <typename T>
iterator Glib::Tree<T>::iter (  )  const [inline]

Accessor for this node's iterator.

template <typename T>
T Glib::Tree<T>::data (  )  const [inline]

Accessor for this node's data.

template <typename T>
Tree<T>* Glib::Tree<T>::lookup ( const iterator  child  )  const [inline]

Lookup a child by its iterator.

Parameters:
child the iterator of the desired child
Returns:
the child if found, else NULL

template <typename T>
Tree<T>* Glib::Tree<T>::parent ( Tree<T>*  newparent = NULL  )  [inline]

Accessor for this node's parent Don't use this.

Parameters:
newparent A new parent for this node, NULL to get the current parent
Returns:
the node's parent

template <typename T>
GNode* Glib::Tree<T>::gobj (  )  [inline]

For auto-wrapping.

template <typename T>
const GNode* Glib::Tree<T>::gobj (  )  const [inline]

template <typename T>
static gboolean Glib::Tree<T>::wrap_traverse_slot ( GNode *  node,
gpointer  slot 
) [inline, static, protected]

template <typename T>
static void Glib::Tree<T>::wrap_foreach_slot ( GNode *  node,
gpointer  slot 
) [inline, static, protected]


Member Data Documentation

template <typename T>
GNode* Glib::Tree<T>::gobject_ [protected]

Leaving these unimplemented for now.

template <typename T>
bool Glib::Tree<T>::owns_gobject_ [protected]

template <typename T>
NodeMap Glib::Tree<T>::children_ [protected]

Some metadata must be stored.

template <typename T>
Tree<T>* Glib::Tree<T>::parent_ [protected]


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

Generated for glibmm 2.4 by Doxygen 1.5.3 © 1997-2001