/* GLIB - Library of useful routines for C programming

 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald

 *

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

#include "gatomic.h"

#include "gtestutils.h"

#include "gslice.h"

/**

 * SECTION:trees-binary

 * @title: Balanced Binary Trees

 * @short_description: a sorted collection of key/value pairs optimized

 *                     for searching and traversing in order

 *

 * The #GTree structure and its associated functions provide a sorted

 * collection of key/value pairs optimized for searching and traversing

 * in order.

 *

 * To create a new #GTree use g_tree_new().

 *

 * To insert a key/value pair into a #GTree use g_tree_insert().

 *

 * To lookup the value corresponding to a given key, use

 * g_tree_lookup() and g_tree_lookup_extended().

 *

 * To find out the number of nodes in a #GTree, use g_tree_nnodes(). To

 * get the height of a #GTree, use g_tree_height().

 *

 * To traverse a #GTree, calling a function for each node visited in

 * the traversal, use g_tree_foreach().

 *

 * To remove a key/value pair use g_tree_remove().

 *

 * To destroy a #GTree, use g_tree_destroy().

 **/

#undef G_TREE_DEBUG

#define MAX_GTREE_HEIGHT 40

typedef struct _GTreeNode  GTreeNode;

/**

 * GTree:

 *

 * The GTree struct is an opaque data structure representing a

 * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be

 * accessed only by using the following functions.

 */

struct _GTree

{

  GTreeNode        *root;

  GCompareDataFunc  key_compare;

  GDestroyNotify    key_destroy_func;

  GDestroyNotify    value_destroy_func;

  gpointer          key_compare_data;

  guint             nnodes;

  gint              ref_count;

};

struct _GTreeNode

{

  gpointer   key;         /* key for this node */

  gpointer   value;       /* value stored at this node */

  GTreeNode *left;        /* left subtree */

  GTreeNode *right;       /* right subtree */

  gint8      balance;     /* height (right) - height (left) */

  guint8     left_child;

  guint8     right_child;

};

static GTreeNode* g_tree_node_new                   (gpointer       key,

                                                     gpointer       value);

static void       g_tree_insert_internal            (GTree         *tree,

                                                     gpointer       key,

                                                     gpointer       value,

                                                     gboolean       replace);

static gboolean   g_tree_remove_internal            (GTree         *tree,

                                                     gconstpointer  key,

                                                     gboolean       steal);

static GTreeNode* g_tree_node_balance               (GTreeNode     *node);

static GTreeNode *g_tree_find_node                  (GTree         *tree,

                                                     gconstpointer  key);

static gint       g_tree_node_pre_order             (GTreeNode     *node,

                                                     GTraverseFunc  traverse_func,

                                                     gpointer       data);

static gint       g_tree_node_in_order              (GTreeNode     *node,

                                                     GTraverseFunc  traverse_func,

                                                     gpointer       data);

static gint       g_tree_node_post_order            (GTreeNode     *node,

                                                     GTraverseFunc  traverse_func,

                                                     gpointer       data);

static gpointer   g_tree_node_search                (GTreeNode     *node,

                                                     GCompareFunc   search_func,

                                                     gconstpointer  data);

static GTreeNode* g_tree_node_rotate_left           (GTreeNode     *node);

static GTreeNode* g_tree_node_rotate_right          (GTreeNode     *node);

#ifdef G_TREE_DEBUG

static void       g_tree_node_check                 (GTreeNode     *node);

#endif

static GTreeNode*

g_tree_node_new (gpointer key,

                 gpointer value)

{

  GTreeNode *node = g_slice_new (GTreeNode);

  node->balance = 0;

  node->left = NULL;

  node->right = NULL;

  node->left_child = FALSE;

  node->right_child = FALSE;

  node->key = key;

  node->value = value;

  return node;

}

/**

 * g_tree_new:

 * @key_compare_func: the function used to order the nodes in the #GTree.

 *   It should return values similar to the standard strcmp() function -

 *   0 if the two arguments are equal, a negative value if the first argument 

 *   comes before the second, or a positive value if the first argument comes 

 *   after the second.

 * 

 * Creates a new #GTree.

 * 

 * Returns: a newly allocated #GTree

 */

GTree *

g_tree_new (GCompareFunc key_compare_func)

{

  g_return_val_if_fail (key_compare_func != NULL, NULL);

  return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,

                          NULL, NULL);

}

/**

 * g_tree_new_with_data:

 * @key_compare_func: qsort()-style comparison function

 * @key_compare_data: data to pass to comparison function

 * 

 * Creates a new #GTree with a comparison function that accepts user data.

 * See g_tree_new() for more details.

 * 

 * Returns: a newly allocated #GTree

 */

GTree *

g_tree_new_with_data (GCompareDataFunc key_compare_func,

                      gpointer         key_compare_data)

{

  g_return_val_if_fail (key_compare_func != NULL, NULL);

  return g_tree_new_full (key_compare_func, key_compare_data, 

                          NULL, NULL);

}

/**

 * g_tree_new_full:

 * @key_compare_func: qsort()-style comparison function

 * @key_compare_data: data to pass to comparison function

 * @key_destroy_func: a function to free the memory allocated for the key 

 *   used when removing the entry from the #GTree or %NULL if you don't

 *   want to supply such a function

 * @value_destroy_func: a function to free the memory allocated for the 

 *   value used when removing the entry from the #GTree or %NULL if you 

 *   don't want to supply such a function

 * 

 * Creates a new #GTree like g_tree_new() and allows to specify functions 

 * to free the memory allocated for the key and value that get called when 

 * removing the entry from the #GTree.

 * 

 * Returns: a newly allocated #GTree

 */

GTree *

g_tree_new_full (GCompareDataFunc key_compare_func,

                 gpointer         key_compare_data,

                 GDestroyNotify   key_destroy_func,

                 GDestroyNotify   value_destroy_func)

{

  GTree *tree;

  g_return_val_if_fail (key_compare_func != NULL, NULL);

  tree = g_slice_new (GTree);

  tree->root               = NULL;

  tree->key_compare        = key_compare_func;

  tree->key_destroy_func   = key_destroy_func;

  tree->value_destroy_func = value_destroy_func;

  tree->key_compare_data   = key_compare_data;

  tree->nnodes             = 0;

  tree->ref_count          = 1;

  return tree;

}

static inline GTreeNode *

g_tree_first_node (GTree *tree)

{

  GTreeNode *tmp;

  if (!tree->root)

    return NULL;

  tmp = tree->root;

  while (tmp->left_child)

    tmp = tmp->left;

  return tmp;

} 

static inline GTreeNode *

g_tree_node_previous (GTreeNode *node)

{

  GTreeNode *tmp;

  tmp = node->left;

  if (node->left_child)

    while (tmp->right_child)

      tmp = tmp->right;

  return tmp;

}

static inline GTreeNode *

g_tree_node_next (GTreeNode *node)

{

  GTreeNode *tmp;

  tmp = node->right;

  if (node->right_child)

    while (tmp->left_child)

      tmp = tmp->left;

  return tmp;

}

static void

g_tree_remove_all (GTree *tree)

{

  GTreeNode *node;

  GTreeNode *next;

  g_return_if_fail (tree != NULL);

  node = g_tree_first_node (tree);

  while (node)

    {

      next = g_tree_node_next (node);

      if (tree->key_destroy_func)

        tree->key_destroy_func (node->key);

      if (tree->value_destroy_func)

        tree->value_destroy_func (node->value);

      g_slice_free (GTreeNode, node);

      node = next;

    }

  tree->root = NULL;

  tree->nnodes = 0;

}

/**

 * g_tree_ref:

 * @tree: a #GTree

 *

 * Increments the reference count of @tree by one.

 *

 * It is safe to call this function from any thread.

 *

 * Returns: the passed in #GTree

 *

 * Since: 2.22

 */

GTree *

g_tree_ref (GTree *tree)

{

  g_return_val_if_fail (tree != NULL, NULL);

  g_atomic_int_inc (&tree->ref_count);

  return tree;

}

/**

 * g_tree_unref:

 * @tree: a #GTree

 *

 * Decrements the reference count of @tree by one.

 * If the reference count drops to 0, all keys and values will

 * be destroyed (if destroy functions were specified) and all

 * memory allocated by @tree will be released.

 *

 * It is safe to call this function from any thread.

 *

 * Since: 2.22

 */

void

g_tree_unref (GTree *tree)

{

  g_return_if_fail (tree != NULL);

  if (g_atomic_int_dec_and_test (&tree->ref_count))

    {

      g_tree_remove_all (tree);

      g_slice_free (GTree, tree);

    }

}

/**

 * g_tree_destroy:

 * @tree: a #GTree

 * 

 * Removes all keys and values from the #GTree and decreases its

 * reference count by one. If keys and/or values are dynamically

 * allocated, you should either free them first or create the #GTree

 * using g_tree_new_full(). In the latter case the destroy functions

 * you supplied will be called on all keys and values before destroying

 * the #GTree.

 */

void

g_tree_destroy (GTree *tree)

{

  g_return_if_fail (tree != NULL);

  g_tree_remove_all (tree);

  g_tree_unref (tree);

}

/**

 * g_tree_insert:

 * @tree: a #GTree

 * @key: the key to insert

 * @value: the value corresponding to the key

 * 

 * Inserts a key/value pair into a #GTree.

 *

 * If the given key already exists in the #GTree its corresponding value

 * is set to the new value. If you supplied a @value_destroy_func when

 * creating the #GTree, the old value is freed using that function. If

 * you supplied a @key_destroy_func when creating the #GTree, the passed

 * key is freed using that function.

 *

 * The tree is automatically 'balanced' as new key/value pairs are added,

 * so that the distance from the root to every leaf is as small as possible.

 */

void

g_tree_insert (GTree    *tree,

               gpointer  key,

               gpointer  value)

{

  g_return_if_fail (tree != NULL);

  g_tree_insert_internal (tree, key, value, FALSE);

#ifdef G_TREE_DEBUG

  g_tree_node_check (tree->root);

#endif

}

/**

 * g_tree_replace:

 * @tree: a #GTree

 * @key: the key to insert

 * @value: the value corresponding to the key

 * 

 * Inserts a new key and value into a #GTree similar to g_tree_insert().

 * The difference is that if the key already exists in the #GTree, it gets 

 * replaced by the new key. If you supplied a @value_destroy_func when 

 * creating the #GTree, the old value is freed using that function. If you 

 * supplied a @key_destroy_func when creating the #GTree, the old key is 

 * freed using that function. 

 *

 * The tree is automatically 'balanced' as new key/value pairs are added,

 * so that the distance from the root to every leaf is as small as possible.

 */

void

g_tree_replace (GTree    *tree,

                gpointer  key,

                gpointer  value)

{

  g_return_if_fail (tree != NULL);

  g_tree_insert_internal (tree, key, value, TRUE);

#ifdef G_TREE_DEBUG

  g_tree_node_check (tree->root);

#endif

}

/* internal insert routine */

static void

g_tree_insert_internal (GTree    *tree,

                        gpointer  key,

                        gpointer  value,

                        gboolean  replace)

{

  GTreeNode *node;

  GTreeNode *path[MAX_GTREE_HEIGHT];

  int idx;

  g_return_if_fail (tree != NULL);

  if (!tree->root)

    {

      tree->root = g_tree_node_new (key, value);

      tree->nnodes++;

      return;

    }

  idx = 0;

  path[idx++] = NULL;

  node = tree->root;

  while (1)

    {

      int cmp = tree->key_compare (key, node->key, tree->key_compare_data);

      if (cmp == 0)

        {

          if (tree->value_destroy_func)

            tree->value_destroy_func (node->value);

          node->value = value;

          if (replace)

            {

              if (tree->key_destroy_func)

                tree->key_destroy_func (node->key);

              node->key = key;

            }

          else

            {

              /* free the passed key */

              if (tree->key_destroy_func)

                tree->key_destroy_func (key);

            }

          return;

        }

      else if (cmp < 0)

        {

          if (node->left_child)

            {

              path[idx++] = node;

              node = node->left;

            }

          else

            {

              GTreeNode *child = g_tree_node_new (key, value);

              child->left = node->left;

              child->right = node;

              node->left = child;

              node->left_child = TRUE;

              node->balance -= 1;

              tree->nnodes++;

              break;

            }

        }

      else

        {

          if (node->right_child)

            {

              path[idx++] = node;

              node = node->right;

            }

          else

            {

              GTreeNode *child = g_tree_node_new (key, value);

              child->right = node->right;

              child->left = node;

              node->right = child;

              node->right_child = TRUE;

              node->balance += 1;

              tree->nnodes++;

              break;

            }

        }

    }

  /* Restore balance. This is the goodness of a non-recursive

   * implementation, when we are done with balancing we 'break'

   * the loop and we are done.

   */

  while (1)

    {

      GTreeNode *bparent = path[--idx];

      gboolean left_node = (bparent && node == bparent->left);

      g_assert (!bparent || bparent->left == node || bparent->right == node);

      if (node->balance < -1 || node->balance > 1)

        {

          node = g_tree_node_balance (node);

          if (bparent == NULL)

            tree->root = node;

          else if (left_node)

            bparent->left = node;

          else

            bparent->right = node;

        }

      if (node->balance == 0 || bparent == NULL)

        break;

      if (left_node)

        bparent->balance -= 1;

      else

        bparent->balance += 1;

      node = bparent;

    }

}

/**

 * g_tree_remove:

 * @tree: a #GTree

 * @key: the key to remove

 * 

 * Removes a key/value pair from a #GTree.

 *

 * If the #GTree was created using g_tree_new_full(), the key and value 

 * are freed using the supplied destroy functions, otherwise you have to 

 * make sure that any dynamically allocated values are freed yourself.

 * If the key does not exist in the #GTree, the function does nothing.

 *

 * Returns: %TRUE if the key was found (prior to 2.8, this function

 *     returned nothing)

 */

gboolean

g_tree_remove (GTree         *tree,

               gconstpointer  key)

{

  gboolean removed;

  g_return_val_if_fail (tree != NULL, FALSE);

  removed = g_tree_remove_internal (tree, key, FALSE);

#ifdef G_TREE_DEBUG

  g_tree_node_check (tree->root);

#endif

  return removed;

}

/**

 * g_tree_steal:

 * @tree: a #GTree

 * @key: the key to remove

 * 

 * Removes a key and its associated value from a #GTree without calling 

 * the key and value destroy functions.

 *

 * If the key does not exist in the #GTree, the function does nothing.

 *

 * Returns: %TRUE if the key was found (prior to 2.8, this function

 *     returned nothing)

 */

gboolean

g_tree_steal (GTree         *tree,

              gconstpointer  key)

{

  gboolean removed;

  g_return_val_if_fail (tree != NULL, FALSE);

  removed = g_tree_remove_internal (tree, key, TRUE);

#ifdef G_TREE_DEBUG

  g_tree_node_check (tree->root);

#endif

  return removed;

}

/* internal remove routine */

static gboolean

g_tree_remove_internal (GTree         *tree,

                        gconstpointer  key,

                        gboolean       steal)

{

  GTreeNode *node, *parent, *balance;

  GTreeNode *path[MAX_GTREE_HEIGHT];

  int idx;

  gboolean left_node;

  g_return_val_if_fail (tree != NULL, FALSE);

  if (!tree->root)

    return FALSE;

  idx = 0;

  path[idx++] = NULL;

  node = tree->root;

  while (1)

    {

      int cmp = tree->key_compare (key, node->key, tree->key_compare_data);

      if (cmp == 0)

        break;

      else if (cmp < 0)

        {

          if (!node->left_child)

            return FALSE;

          path[idx++] = node;

          node = node->left;

        }

      else

        {

          if (!node->right_child)

            return FALSE;

          path[idx++] = node;

          node = node->right;

        }

    }

  /* The following code is almost equal to g_tree_remove_node,

   * except that we do not have to call g_tree_node_parent.

   */

  balance = parent = path[--idx];

  g_assert (!parent || parent->left == node || parent->right == node);

  left_node = (parent && node == parent->left);

  if (!node->left_child)

    {

      if (!node->right_child)

        {

          if (!parent)

            tree->root = NULL;

          else if (left_node)

            {

              parent->left_child = FALSE;

              parent->left = node->left;

              parent->balance += 1;

            }

          else

            {

              parent->right_child = FALSE;

              parent->right = node->right;

              parent->balance -= 1;

            }

        }

      else /* node has a right child */

        {

          GTreeNode *tmp = g_tree_node_next (node);

          tmp->left = node->left;

          if (!parent)

            tree->root = node->right;

          else if (left_node)

            {

              parent->left = node->right;

              parent->balance += 1;

            }

          else

            {

              parent->right = node->right;

              parent->balance -= 1;

            }

        }

    }

  else /* node has a left child */

    {

      if (!node->right_child)

        {

          GTreeNode *tmp = g_tree_node_previous (node);

          tmp->right = node->right;

          if (parent == NULL)

            tree->root = node->left;

          else if (left_node)

            {

              parent->left = node->left;

              parent->balance += 1;

            }

          else

            {

              parent->right = node->left;

              parent->balance -= 1;

            }

        }

      else /* node has a both children (pant, pant!) */

        {

          GTreeNode *prev = node->left;

          GTreeNode *next = node->right;

          GTreeNode *nextp = node;

          int old_idx = idx + 1;

          idx++;

          /* path[idx] == parent */

          /* find the immediately next node (and its parent) */

          while (next->left_child)

            {

              path[++idx] = nextp = next;

              next = next->left;

            }

          path[old_idx] = next;

          balance = path[idx];

          /* remove 'next' from the tree */

          if (nextp != node)

            {

              if (next->right_child)

                nextp->left = next->right;

              else

                nextp->left_child = FALSE;

              nextp->balance += 1;

              next->right_child = TRUE;

              next->right = node->right;

            }

          else

            node->balance -= 1;

          /* set the prev to point to the right place */

          while (prev->right_child)

            prev = prev->right;

          prev->right = next;

          /* prepare 'next' to replace 'node' */

          next->left_child = TRUE;

          next->left = node->left;

          next->balance = node->balance;

          if (!parent)

            tree->root = next;

          else if (left_node)

            parent->left = next;

          else

            parent->right = next;

        }

    }

  /* restore balance */

  if (balance)

    while (1)

      {

        GTreeNode *bparent = path[--idx];

        g_assert (!bparent || bparent->left == balance || bparent->right == balance);

        left_node = (bparent && balance == bparent->left);

        if(balance->balance < -1 || balance->balance > 1)

          {

            balance = g_tree_node_balance (balance);

            if (!bparent)

              tree->root = balance;

            else if (left_node)

              bparent->left = balance;

            else

              bparent->right = balance;

          }

        if (balance->balance != 0 || !bparent)

          break;

        if (left_node)

          bparent->balance += 1;

        else

          bparent->balance -= 1;

        balance = bparent;

      }

  if (!steal)

    {

      if (tree->key_destroy_func)

        tree->key_destroy_func (node->key);

      if (tree->value_destroy_func)

        tree->value_destroy_func (node->value);

    }

  g_slice_free (GTreeNode, node);

  tree->nnodes--;

  return TRUE;

}

/**

 * g_tree_lookup:

 * @tree: a #GTree

 * @key: the key to look up

 * 

 * Gets the value corresponding to the given key. Since a #GTree is 

 * automatically balanced as key/value pairs are added, key lookup

 * is O(log n) (where n is the number of key/value pairs in the tree).

 *

 * Returns: the value corresponding to the key, or %NULL

 *     if the key was not found

 */

gpointer

g_tree_lookup (GTree         *tree,

               gconstpointer  key)

{

  GTreeNode *node;

  g_return_val_if_fail (tree != NULL, NULL);

  node = g_tree_find_node (tree, key);

  return node ? node->value : NULL;

}

/**

 * g_tree_lookup_extended:

 * @tree: a #GTree

 * @lookup_key: the key to look up

 * @orig_key: (optional) (nullable): returns the original key

 * @value: (optional) (nullable): returns the value associated with the key

 * 

 * Looks up a key in the #GTree, returning the original key and the

 * associated value. This is useful if you need to free the memory

 * allocated for the original key, for example before calling

 * g_tree_remove().

 * 

 * Returns: %TRUE if the key was found in the #GTree

 */

gboolean

g_tree_lookup_extended (GTree         *tree,

                        gconstpointer  lookup_key,

                        gpointer      *orig_key,

                        gpointer      *value)

{

  GTreeNode *node;

  g_return_val_if_fail (tree != NULL, FALSE);

  node = g_tree_find_node (tree, lookup_key);

  if (node)

    {

      if (orig_key)