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

 *

 * SPDX-License-Identifier: LGPL-2.1-or-later

 *

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

/**

 * 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: (scope call): 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: (scope call): 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;

  }