/* GLIB - Library of useful routines for C programming
 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
 *
 * GNode: N-way tree implementation.
 * Copyright (C) 1998 Tim Janik
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
 */

/*
 * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
 * file for a list of people on the GLib Team.  See the ChangeLog
 * files for a list of changes.  These files are distributed with
 * GLib at ftp://ftp.gtk.org/pub/gtk/.
 */

/*
 * MT safe
 */

#include "config.h"

#include "gnode.h"

#include "gslice.h"

#include "gtestutils.h"

/**
 * SECTION:trees-nary
 * @title: N-ary Trees
 * @short_description: trees of data with any number of branches
 *
 * The #GNode struct and its associated functions provide a N-ary tree
 * data structure, where nodes in the tree can contain arbitrary data.
 *
 * To create a new tree use g_node_new().
 *
 * To insert a node into a tree use g_node_insert(),
 * g_node_insert_before(), g_node_append() and g_node_prepend().
 *
 * To create a new node and insert it into a tree use
 * g_node_insert_data(), g_node_insert_data_after(),
 * g_node_insert_data_before(), g_node_append_data()
 * and g_node_prepend_data().
 *
 * To reverse the children of a node use g_node_reverse_children().
 *
 * To find a node use g_node_get_root(), g_node_find(),
 * g_node_find_child(), g_node_child_index(), g_node_child_position(),
 * g_node_first_child(), g_node_last_child(), g_node_nth_child(),
 * g_node_first_sibling(), g_node_prev_sibling(), g_node_next_sibling()
 * or g_node_last_sibling().
 *
 * To get information about a node or tree use G_NODE_IS_LEAF(),
 * G_NODE_IS_ROOT(), g_node_depth(), g_node_n_nodes(),
 * g_node_n_children(), g_node_is_ancestor() or g_node_max_height().
 *
 * To traverse a tree, calling a function for each node visited in the
 * traversal, use g_node_traverse() or g_node_children_foreach().
 *
 * To remove a node or subtree from a tree use g_node_unlink() or
 * g_node_destroy().
 **/

/**
 * GNode:
 * @data: contains the actual data of the node.
 * @next: points to the node's next sibling (a sibling is another
 *        #GNode with the same parent).
 * @prev: points to the node's previous sibling.
 * @parent: points to the parent of the #GNode, or is %NULL if the
 *          #GNode is the root of the tree.
 * @children: points to the first child of the #GNode.  The other
 *            children are accessed by using the @next pointer of each
 *            child.
 *
 * The #GNode struct represents one node in a [n-ary tree][glib-N-ary-Trees].
 **/

#define g_node_alloc0()         g_slice_new0 (GNode)
#define g_node_free(node)       g_slice_free (GNode, node)

/* --- functions --- */
/**
 * g_node_new:
 * @data: the data of the new node
 *
 * Creates a new #GNode containing the given data.
 * Used to create the first node in a tree.
 *
 * Returns: a new #GNode
 */
GNode*
g_node_new (gpointer data)
{
  GNode *node = g_node_alloc0 ();
  node->data = data;
  return node;
}

static void
g_nodes_free (GNode *node)
{
  while (node)
    {
      GNode *next = node->next;
      if (node->children)
        g_nodes_free (node->children);
      g_node_free (node);
      node = next;
    }
}

/**
 * g_node_destroy:
 * @root: the root of the tree/subtree to destroy
 *
 * Removes @root and its children from the tree, freeing any memory
 * allocated.
 */
void
g_node_destroy (GNode *root)
{
  g_return_if_fail (root != NULL);
  
  if (!G_NODE_IS_ROOT (root))
    g_node_unlink (root);
  
  g_nodes_free (root);
}

/**
 * g_node_unlink:
 * @node: the #GNode to unlink, which becomes the root of a new tree
 *
 * Unlinks a #GNode from a tree, resulting in two separate trees.
 */
void
g_node_unlink (GNode *node)
{
  g_return_if_fail (node != NULL);
  
  if (node->prev)
    node->prev->next = node->next;
  else if (node->parent)
    node->parent->children = node->next;
  node->parent = NULL;
  if (node->next)
    {
      node->next->prev = node->prev;
      node->next = NULL;
    }
  node->prev = NULL;
}

/**
 * g_node_copy_deep:
 * @node: a #GNode
 * @copy_func: the function which is called to copy the data inside each node,
 *   or %NULL to use the original data.
 * @data: data to pass to @copy_func
 * 
 * Recursively copies a #GNode and its data.
 * 
 * Returns: a new #GNode containing copies of the data in @node.
 *
 * Since: 2.4
 **/
GNode*
g_node_copy_deep (GNode     *node, 
		  GCopyFunc  copy_func,
		  gpointer   data)
{
  GNode *new_node = NULL;

  if (copy_func == NULL)
	return g_node_copy (node);

  if (node)
    {
      GNode *child, *new_child;
      
      new_node = g_node_new (copy_func (node->data, data));
      
      for (child = g_node_last_child (node); child; child = child->prev) 
	{
	  new_child = g_node_copy_deep (child, copy_func, data);
	  g_node_prepend (new_node, new_child);
	}
    }
  
  return new_node;
}

/**
 * g_node_copy:
 * @node: a #GNode
 *
 * Recursively copies a #GNode (but does not deep-copy the data inside the 
 * nodes, see g_node_copy_deep() if you need that).
 *
 * Returns: a new #GNode containing the same data pointers
 */
GNode*
g_node_copy (GNode *node)
{
  GNode *new_node = NULL;
  
  if (node)
    {
      GNode *child;
      
      new_node = g_node_new (node->data);
      
      for (child = g_node_last_child (node); child; child = child->prev)
	g_node_prepend (new_node, g_node_copy (child));
    }
  
  return new_node;
}

/**
 * g_node_insert:
 * @parent: the #GNode to place @node under
 * @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 #GNode to insert
 *
 * Inserts a #GNode beneath the parent at the given position.
 *
 * Returns: the inserted #GNode
 */
GNode*
g_node_insert (GNode *parent,
	       gint   position,
	       GNode *node)
{
  g_return_val_if_fail (parent != NULL, node);
  g_return_val_if_fail (node != NULL, node);
  g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
  
  if (position > 0)
    return g_node_insert_before (parent,
				 g_node_nth_child (parent, position),
				 node);
  else if (position == 0)
    return g_node_prepend (parent, node);
  else /* if (position < 0) */
    return g_node_append (parent, node);
}

/**
 * g_node_insert_before:
 * @parent: the #GNode to place @node under
 * @sibling: the sibling #GNode to place @node before. 
 *     If sibling is %NULL, the node is inserted as the last child of @parent.
 * @node: the #GNode to insert
 *
 * Inserts a #GNode beneath the parent before the given sibling.
 *
 * Returns: the inserted #GNode
 */
GNode*
g_node_insert_before (GNode *parent,
		      GNode *sibling,
		      GNode *node)
{
  g_return_val_if_fail (parent != NULL, node);
  g_return_val_if_fail (node != NULL, node);
  g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
  if (sibling)
    g_return_val_if_fail (sibling->parent == parent, node);
  
  node->parent = parent;
  
  if (sibling)
    {
      if (sibling->prev)
	{
	  node->prev = sibling->prev;
	  node->prev->next = node;
	  node->next = sibling;
	  sibling->prev = node;
	}
      else
	{
	  node->parent->children = node;
	  node->next = sibling;
	  sibling->prev = node;
	}
    }
  else
    {
      if (parent->children)
	{
	  sibling = parent->children;
	  while (sibling->next)
	    sibling = sibling->next;
	  node->prev = sibling;
	  sibling->next = node;
	}
      else
	node->parent->children = node;
    }

  return node;
}

/**
 * g_node_insert_after:
 * @parent: the #GNode to place @node under
 * @sibling: the sibling #GNode to place @node after. 
 *     If sibling is %NULL, the node is inserted as the first child of @parent.
 * @node: the #GNode to insert
 *
 * Inserts a #GNode beneath the parent after the given sibling.
 *
 * Returns: the inserted #GNode
 */
GNode*
g_node_insert_after (GNode *parent,
		     GNode *sibling,
		     GNode *node)
{
  g_return_val_if_fail (parent != NULL, node);
  g_return_val_if_fail (node != NULL, node);
  g_return_val_if_fail (G_NODE_IS_ROOT (node), node);
  if (sibling)
    g_return_val_if_fail (sibling->parent == parent, node);

  node->parent = parent;

  if (sibling)
    {
      if (sibling->next)
	{
	  sibling->next->prev = node;
	}
      node->next = sibling->next;
      node->prev = sibling;
      sibling->next = node;
    }
  else
    {
      if (parent->children)
	{
	  node->next = parent->children;
	  parent->children->prev = node;
	}
      parent->children = node;
    }

  return node;
}

/**
 * g_node_prepend:
 * @parent: the #GNode to place the new #GNode under
 * @node: the #GNode to insert
 *
 * Inserts a #GNode as the first child of the given parent.
 *
 * Returns: the inserted #GNode
 */
GNode*
g_node_prepend (GNode *parent,
		GNode *node)
{
  g_return_val_if_fail (parent != NULL, node);
  
  return g_node_insert_before (parent, parent->children, node);
}

/**
 * g_node_get_root:
 * @node: a #GNode
 *
 * Gets the root of a tree.
 *
 * Returns: the root of the tree
 */
GNode*
g_node_get_root (GNode *node)
{
  g_return_val_if_fail (node != NULL, NULL);
  
  while (node->parent)
    node = node->parent;
  
  return node;
}

/**
 * g_node_is_ancestor:
 * @node: a #GNode
 * @descendant: a #GNode
 *
 * Returns %TRUE if @node is an ancestor of @descendant.
 * This is true if node is the parent of @descendant, 
 * or if node is the grandparent of @descendant etc.
 *
 * Returns: %TRUE if @node is an ancestor of @descendant
 */
gboolean
g_node_is_ancestor (GNode *node,
		    GNode *descendant)
{
  g_return_val_if_fail (node != NULL, FALSE);
  g_return_val_if_fail (descendant != NULL, FALSE);
  
  while (descendant)
    {
      if (descendant->parent == node)
	return TRUE;
      
      descendant = descendant->parent;
    }
  
  return FALSE;
}

/**
 * g_node_depth:
 * @node: a #GNode
 *
 * Gets the depth of a #GNode.
 *
 * If @node is %NULL the depth is 0. 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 the #GNode
 */
guint
g_node_depth (GNode *node)
{
  guint depth = 0;
  
  while (node)
    {
      depth++;
      node = node->parent;
    }
  
  return depth;
}

/**
 * g_node_reverse_children:
 * @node: a #GNode.
 *
 * Reverses the order of the children of a #GNode.
 * (It doesn't change the order of the grandchildren.)
 */
void
g_node_reverse_children (GNode *node)
{
  GNode *child;
  GNode *last;
  
  g_return_if_fail (node != NULL);
  
  child = node->children;
  last = NULL;
  while (child)
    {
      last = child;
      child = last->next;
      last->next = last->prev;
      last->prev = child;
    }
  node->children = last;
}

/**
 * g_node_max_height:
 * @root: a #GNode
 *
 * Gets the maximum height of all branches beneath a #GNode.
 * This is the maximum distance from the #GNode to all leaf nodes.
 *
 * If @root is %NULL, 0 is returned. If @root has no children, 
 * 1 is returned. If @root has children, 2 is returned. And so on.
 *
 * Returns: the maximum height of the tree beneath @root
 */
guint
g_node_max_height (GNode *root)
{
  GNode *child;
  guint max_height = 0;
  
  if (!root)
    return 0;
  
  child = root->children;
  while (child)
    {
      guint tmp_height;
      
      tmp_height = g_node_max_height (child);
      if (tmp_height > max_height)
	max_height = tmp_height;
      child = child->next;
    }
  
  return max_height + 1;
}

static gboolean
g_node_traverse_pre_order (GNode	    *node,
			   GTraverseFlags    flags,
			   GNodeTraverseFunc func,
			   gpointer	     data)
{
  if (node->children)
    {
      GNode *child;
      
      if ((flags & G_TRAVERSE_NON_LEAFS) &&
	  func (node, data))
	return TRUE;
      
      child = node->children;
      while (child)
	{
	  GNode *current;
	  
	  current = child;
	  child = current->next;
	  if (g_node_traverse_pre_order (current, flags, func, data))
	    return TRUE;
	}
    }
  else if ((flags & G_TRAVERSE_LEAFS) &&
	   func (node, data))
    return TRUE;
  
  return FALSE;
}

static gboolean
g_node_depth_traverse_pre_order (GNode		  *node,
				 GTraverseFlags	   flags,
				 guint		   depth,
				 GNodeTraverseFunc func,
				 gpointer	   data)
{
  if (node->children)
    {
      GNode *child;
      
      if ((flags & G_TRAVERSE_NON_LEAFS) &&
	  func (node, data))
	return TRUE;
      
      depth--;
      if (!depth)
	return FALSE;
      
      child = node->children;
      while (child)
	{
	  GNode *current;
	  
	  current = child;
	  child = current->next;
	  if (g_node_depth_traverse_pre_order (current, flags, depth, func, data))
	    return TRUE;
	}
    }
  else if ((flags & G_TRAVERSE_LEAFS) &&
	   func (node, data))
    return TRUE;
  
  return FALSE;
}

static gboolean
g_node_traverse_post_order (GNode	     *node,
			    GTraverseFlags    flags,
			    GNodeTraverseFunc func,
			    gpointer	      data)
{
  if (node->children)
    {
      GNode *child;
      
      child = node->children;
      while (child)
	{
	  GNode *current;
	  
	  current = child;
	  child = current->next;
	  if (g_node_traverse_post_order (current, flags, func, data))
	    return TRUE;
	}
      
      if ((flags & G_TRAVERSE_NON_LEAFS) &&
	  func (node, data))
	return TRUE;
      
    }
  else if ((flags & G_TRAVERSE_LEAFS) &&
	   func (node, data))
    return TRUE;
  
  return FALSE;
}

static gboolean
g_node_depth_traverse_post_order (GNode		   *node,
				  GTraverseFlags    flags,
				  guint		    depth,
				  GNodeTraverseFunc func,
				  gpointer	    data)
{
  if (node->children)
    {
      depth--;
      if (depth)
	{
	  GNode *child;
	  
	  child = node->children;
	  while (child)
	    {
	      GNode *current;
	      
	      current = child;
	      child = current->next;
	      if (g_node_depth_traverse_post_order (current, flags, depth, func, data))
		return TRUE;
	    }
	}
      
      if ((flags & G_TRAVERSE_NON_LEAFS) &&
	  func (node, data))
	return TRUE;
      
    }
  else if ((flags & G_TRAVERSE_LEAFS) &&
	   func (node, data))
    return TRUE;
  
  return FALSE;
}

static gboolean
g_node_traverse_in_order (GNode		   *node,
			  GTraverseFlags    flags,
			  GNodeTraverseFunc func,
			  gpointer	    data)
{
  if (node->children)
    {
      GNode *child;
      GNode *current;
      
      child = node->children;
      current = child;
      child = current->next;
      
      if (g_node_traverse_in_order (current, flags, func, data))
	return TRUE;
      
      if ((flags & G_TRAVERSE_NON_LEAFS) &&
	  func (node, data))
	return TRUE;
      
      while (child)
	{
	  current = child;
	  child = current->next;
	  if (g_node_traverse_in_order (current, flags, func, data))
	    return TRUE;
	}
    }
  else if ((flags & G_TRAVERSE_LEAFS) &&
	   func (node, data))
    return TRUE;
  
  return FALSE;
}

static gboolean
g_node_depth_traverse_in_order (GNode		 *node,
				GTraverseFlags	  flags,
				guint		  depth,
				GNodeTraverseFunc func,
				gpointer	  data)
{
  if (node->children)
    {
      depth--;
      if (depth)
	{
	  GNode *child;
	  GNode *current;
	  
	  child = node->children;
	  current = child;
	  child = current->next;
	  
	  if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
	    return TRUE;
	  
	  if ((flags & G_TRAVERSE_NON_LEAFS) &&
	      func (node, data))
	    return TRUE;
	  
	  while (child)
	    {
	      current = child;
	      child = current->next;
	      if (g_node_depth_traverse_in_order (current, flags, depth, func, data))
		return TRUE;
	    }
	}
      else if ((flags & G_TRAVERSE_NON_LEAFS) &&
	       func (node, data))
	return TRUE;
    }
  else if ((flags & G_TRAVERSE_LEAFS) &&
	   func (node, data))
    return TRUE;
  
  return FALSE;
}

static gboolean
g_node_traverse_level (GNode		 *node,
		       GTraverseFlags	  flags,
		       guint		  level,
		       GNodeTraverseFunc  func,
		       gpointer	          data,
		       gboolean          *more_levels)
{
  if (level == 0) 
    {
      if (node->children)
	{
	  *more_levels = TRUE;
	  return (flags & G_TRAVERSE_NON_LEAFS) && func (node, data);
	}
      else
	{
	  return (flags & G_TRAVERSE_LEAFS) && func (node, data);
	}
    }
  else 
    {
      node = node->children;
      
      while (node)
	{
	  if (g_node_traverse_level (node, flags, level - 1, func, data, more_levels))
	    return TRUE;

	  node = node->next;
	}
    }

  return FALSE;
}

static gboolean
g_node_depth_traverse_level (GNode             *node,
			     GTraverseFlags	flags,
			     gint		depth,
			     GNodeTraverseFunc  func,
			     gpointer	        data)
{
  guint level;
  gboolean more_levels;

  level = 0;  
  while (depth < 0 || level != (guint) depth)
    {
      more_levels = FALSE;
      if (g_node_traverse_level (node, flags, level, func, data, &more_levels))
	return TRUE;
      if (!more_levels)
	break;
      level++;
    }
  return FALSE;
}

/**
 * g_node_traverse:
 * @root: the root #GNode of the tree to traverse
 * @order: the order in which nodes are visited - %G_IN_ORDER, 
 *     %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER.
 * @flags: which types of children are to be visited, one of 
 *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_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 function to call for each visited #GNode
 * @data: user data to pass to the function
 *
 * Traverses a tree starting at the given root #GNode.
 * It calls the given function for each node visited.
 * The traversal can be halted at any point by returning %TRUE from @func.
 * @func must not do anything that would modify the structure of the tree.
 */

/**
 * GTraverseType:
 * @G_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.
 * @G_PRE_ORDER: visits a node, then its children.
 * @G_POST_ORDER: visits the node's children, then the node itself.
 * @G_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.
 *
 * Specifies the type of traversal performed by g_tree_traverse(),
 * g_node_traverse() and g_node_find(). The different orders are
 * illustrated here:
 * - In order: A, B, C, D, E, F, G, H, I
 *   ![](Sorted_binary_tree_inorder.svg)
 * - Pre order: F, B, A, D, C, E, G, I, H
 *   ![](Sorted_binary_tree_preorder.svg)
 * - Post order: A, C, E, D, B, H, I, G, F
 *   ![](Sorted_binary_tree_postorder.svg)
 * - Level order: F, B, G, A, D, I, C, E, H
 *   ![](Sorted_binary_tree_breadth-first_traversal.svg)
 */

/**
 * GTraverseFlags:
 * @G_TRAVERSE_LEAVES: only leaf nodes should be visited. This name has
 *                     been introduced in 2.6, for older version use
 *                     %G_TRAVERSE_LEAFS.
 * @G_TRAVERSE_NON_LEAVES: only non-leaf nodes should be visited. This
 *                         name has been introduced in 2.6, for older
 *                         version use %G_TRAVERSE_NON_LEAFS.
 * @G_TRAVERSE_ALL: all nodes should be visited.
 * @G_TRAVERSE_MASK: a mask of all traverse flags.
 * @G_TRAVERSE_LEAFS: identical to %G_TRAVERSE_LEAVES.
 * @G_TRAVERSE_NON_LEAFS: identical to %G_TRAVERSE_NON_LEAVES.
 *
 * Specifies which nodes are visited during several of the tree
 * functions, including g_node_traverse() and g_node_find().
 **/
/**
 * GNodeTraverseFunc:
 * @node: a #GNode.
 * @data: user data passed to g_node_traverse().
 *
 * Specifies the type of function passed to g_node_traverse(). The
 * function is called with each of the nodes visited, together with the
 * user data passed to g_node_traverse(). If the function returns
 * %TRUE, then the traversal is stopped.
 *
 * Returns: %TRUE to stop the traversal.
 **/
void
g_node_traverse (GNode		  *root,
		 GTraverseType	   order,
		 GTraverseFlags	   flags,
		 gint		   depth,
		 GNodeTraverseFunc func,
		 gpointer	   data)
{
  g_return_if_fail (root != NULL);
  g_return_if_fail (func != NULL);
  g_return_if_fail (order <= G_LEVEL_ORDER);
  g_return_if_fail (flags <= G_TRAVERSE_MASK);
  g_return_if_fail (depth == -1 || depth > 0);
  
  switch (order)
    {
    case G_PRE_ORDER:
      if (depth < 0)
	g_node_traverse_pre_order (root, flags, func, data);
      else
	g_node_depth_traverse_pre_order (root, flags, depth, func, data);
      break;
    case G_POST_ORDER:
      if (depth < 0)
	g_node_traverse_post_order (root, flags, func, data);
      else
	g_node_depth_traverse_post_order (root, flags, depth, func, data);
      break;
    case G_IN_ORDER:
      if (depth < 0)
	g_node_traverse_in_order (root, flags, func, data);
      else
	g_node_depth_traverse_in_order (root, flags, depth, func, data);
      break;
    case G_LEVEL_ORDER:
      g_node_depth_traverse_level (root, flags, depth, func, data);
      break;
    }
}

static gboolean
g_node_find_func (GNode	   *node,
		  gpointer  data)
{
  gpointer *d = data;
  
  if (*d != node->data)
    return FALSE;
  
  *(++d) = node;
  
  return TRUE;
}

/**
 * g_node_find:
 * @root: the root #GNode of the tree to search
 * @order: the order in which nodes are visited - %G_IN_ORDER, 
 *     %G_PRE_ORDER, %G_POST_ORDER, or %G_LEVEL_ORDER
 * @flags: which types of children are to be searched, one of 
 *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
 * @data: the data to find
 *
 * Finds a #GNode in a tree.
 *
 * Returns: the found #GNode, or %NULL if the data is not found
 */
GNode*
g_node_find (GNode	    *root,
	     GTraverseType   order,
	     GTraverseFlags  flags,
	     gpointer        data)
{
  gpointer d[2];
  
  g_return_val_if_fail (root != NULL, NULL);
  g_return_val_if_fail (order <= G_LEVEL_ORDER, NULL);
  g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
  
  d[0] = data;
  d[1] = NULL;
  
  g_node_traverse (root, order, flags, -1, g_node_find_func, d);
  
  return d[1];
}

static void
g_node_count_func (GNode	 *node,
		   GTraverseFlags flags,
		   guint	 *n)
{
  if (node->children)
    {
      GNode *child;
      
      if (flags & G_TRAVERSE_NON_LEAFS)
	(*n)++;
      
      child = node->children;
      while (child)
	{
	  g_node_count_func (child, flags, n);
	  child = child->next;
	}
    }
  else if (flags & G_TRAVERSE_LEAFS)
    (*n)++;
}

/**
 * g_node_n_nodes:
 * @root: a #GNode
 * @flags: which types of children are to be counted, one of 
 *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
 *
 * Gets the number of nodes in a tree.
 *
 * Returns: the number of nodes in the tree
 */
guint
g_node_n_nodes (GNode	       *root,
		GTraverseFlags  flags)
{
  guint n = 0;
  
  g_return_val_if_fail (root != NULL, 0);
  g_return_val_if_fail (flags <= G_TRAVERSE_MASK, 0);
  
  g_node_count_func (root, flags, &n);
  
  return n;
}

/**
 * g_node_last_child:
 * @node: a #GNode (must not be %NULL)
 *
 * Gets the last child of a #GNode.
 *
 * Returns: the last child of @node, or %NULL if @node has no children
 */
GNode*
g_node_last_child (GNode *node)
{
  g_return_val_if_fail (node != NULL, NULL);
  
  node = node->children;
  if (node)
    while (node->next)
      node = node->next;
  
  return node;
}

/**
 * g_node_nth_child:
 * @node: a #GNode
 * @n: the index of the desired child
 *
 * Gets a child of a #GNode, using the given index.
 * The first child is at index 0. If the index is 
 * too big, %NULL is returned.
 *
 * Returns: the child of @node at index @n
 */
GNode*
g_node_nth_child (GNode *node,
		  guint	 n)
{
  g_return_val_if_fail (node != NULL, NULL);
  
  node = node->children;
  if (node)
    while ((n-- > 0) && node)
      node = node->next;
  
  return node;
}

/**
 * g_node_n_children:
 * @node: a #GNode
 *
 * Gets the number of children of a #GNode.
 *
 * Returns: the number of children of @node
 */
guint
g_node_n_children (GNode *node)
{
  guint n = 0;
  
  g_return_val_if_fail (node != NULL, 0);
  
  node = node->children;
  while (node)
    {
      n++;
      node = node->next;
    }
  
  return n;
}

/**
 * g_node_find_child:
 * @node: a #GNode
 * @flags: which types of children are to be searched, one of 
 *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
 * @data: the data to find
 *
 * Finds the first child of a #GNode with the given data.
 *
 * Returns: the found child #GNode, or %NULL if the data is not found
 */
GNode*
g_node_find_child (GNode	  *node,
		   GTraverseFlags  flags,
		   gpointer	   data)
{
  g_return_val_if_fail (node != NULL, NULL);
  g_return_val_if_fail (flags <= G_TRAVERSE_MASK, NULL);
  
  node = node->children;
  while (node)
    {
      if (node->data == data)
	{
	  if (G_NODE_IS_LEAF (node))
	    {
	      if (flags & G_TRAVERSE_LEAFS)
		return node;
	    }
	  else
	    {
	      if (flags & G_TRAVERSE_NON_LEAFS)
		return node;
	    }
	}
      node = node->next;
    }
  
  return NULL;
}

/**
 * g_node_child_position:
 * @node: a #GNode
 * @child: a child of @node
 *
 * Gets the position of a #GNode with respect to its siblings.
 * @child must be a child of @node. The first child is numbered 0, 
 * the second 1, and so on.
 *
 * Returns: the position of @child with respect to its siblings
 */
gint
g_node_child_position (GNode *node,
		       GNode *child)
{
  guint n = 0;
  
  g_return_val_if_fail (node != NULL, -1);
  g_return_val_if_fail (child != NULL, -1);
  g_return_val_if_fail (child->parent == node, -1);
  
  node = node->children;
  while (node)
    {
      if (node == child)
	return n;
      n++;
      node = node->next;
    }
  
  return -1;
}

/**
 * g_node_child_index:
 * @node: a #GNode
 * @data: the data to find
 *
 * Gets the position of the first child of a #GNode 
 * which contains the given data.
 *
 * Returns: the index of the child of @node which contains 
 *     @data, or -1 if the data is not found
 */
gint
g_node_child_index (GNode    *node,
		    gpointer  data)
{
  guint n = 0;
  
  g_return_val_if_fail (node != NULL, -1);
  
  node = node->children;
  while (node)
    {
      if (node->data == data)
	return n;
      n++;
      node = node->next;
    }
  
  return -1;
}

/**
 * g_node_first_sibling:
 * @node: a #GNode
 *
 * Gets the first sibling of a #GNode.
 * This could possibly be the node itself.
 *
 * Returns: the first sibling of @node
 */
GNode*
g_node_first_sibling (GNode *node)
{
  g_return_val_if_fail (node != NULL, NULL);
  
  if (node->parent)
    return node->parent->children;
  
  while (node->prev)
    node = node->prev;
  
  return node;
}

/**
 * g_node_last_sibling:
 * @node: a #GNode
 *
 * Gets the last sibling of a #GNode.
 * This could possibly be the node itself.
 *
 * Returns: the last sibling of @node
 */
GNode*
g_node_last_sibling (GNode *node)
{
  g_return_val_if_fail (node != NULL, NULL);
  
  while (node->next)
    node = node->next;
  
  return node;
}

/**
 * g_node_children_foreach:
 * @node: a #GNode
 * @flags: which types of children are to be visited, one of 
 *     %G_TRAVERSE_ALL, %G_TRAVERSE_LEAVES and %G_TRAVERSE_NON_LEAVES
 * @func: the function to call for each visited node
 * @data: user data to pass to the function
 *
 * Calls a function for each of the children of a #GNode. Note that it
 * doesn't descend beneath the child nodes. @func must not do anything
 * that would modify the structure of the tree.
 */
/**
 * GNodeForeachFunc:
 * @node: a #GNode.
 * @data: user data passed to g_node_children_foreach().
 *
 * Specifies the type of function passed to g_node_children_foreach().
 * The function is called with each child node, together with the user
 * data passed to g_node_children_foreach().
 **/
void
g_node_children_foreach (GNode		  *node,
			 GTraverseFlags	   flags,
			 GNodeForeachFunc  func,
			 gpointer	   data)
{
  g_return_if_fail (node != NULL);
  g_return_if_fail (flags <= G_TRAVERSE_MASK);
  g_return_if_fail (func != NULL);
  
  node = node->children;
  while (node)
    {
      GNode *current;
      
      current = node;
      node = current->next;
      if (G_NODE_IS_LEAF (current))
	{
	  if (flags & G_TRAVERSE_LEAFS)
	    func (current, data);
	}
      else
	{
	  if (flags & G_TRAVERSE_NON_LEAFS)
	    func (current, data);
	}
    }
}