/* 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

 * Portions copyright (c) 2006-2009 Nokia Corporation.  All rights reserved.

 *

 * 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 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, write to the

 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,

 * Boston, MA 02111-1307, USA.

 */

/*

 * 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 "glib.h"

#include "galias.h"

EXPORT_C void g_node_push_allocator (gpointer dummy) { /* present for binary compat only */ }

EXPORT_C void g_node_pop_allocator  (void)           { /* present for binary compat only */ }

#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

 */

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

 */

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

 */

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

 * 

 * Return value: a new #GNode containing copies of the data in @node.

 *

 * Since: 2.4

 **/

EXPORT_C 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

 */

EXPORT_C 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

 */

EXPORT_C 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

 */

EXPORT_C 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

 */

EXPORT_C 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

 */

EXPORT_C 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

 */

EXPORT_C 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

 */

EXPORT_C 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

 */

EXPORT_C 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.)

 */

EXPORT_C 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

 */

EXPORT_C 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;