/*
 * frost_tree.c
 *
 *  Created on: Jul 3, 2012
 *      Author: ergino
 */

#include "frost_tree.h"
#include "frost_mem.h"
#include <stdio.h>
#include "utilities_debug/cabot_assert.h"
#include "ice_streamer.h"

#define TRACE_VERBOSE(x)   printf x

#undef G_TREE_DEBUG

#define MAX_FROST_Tree_HEIGHT 40

typedef struct _FROST_TreeNode  FROST_TreeNode;

/**
 * FROST_Tree:
 *
 * The <structname>FROST_Tree</structname> struct is an opaque data
 * structure representing a <link
 * linkend="glib-Balanced-Binary-Trees">Balanced Binary Tree</link>. It
 * should be accessed only by using the following functions.
 **/
struct _FROST_Tree
{
  FROST_TreeNode        *root;
  FROSTCompareDataFunc  key_compare;
  FROSTDestroyNotify    key_destroy_func;
  FROSTDestroyNotify    value_destroy_func;
  frost_pointer          key_compare_data;
  frost_uint             nnodes;
  frost_int              ref_count;
};

struct _FROST_TreeNode
{
  frost_pointer   key;         /* key for this node */
  frost_pointer   value;       /* value stored at this node */
  FROST_TreeNode *left;        /* left subtree */
  FROST_TreeNode *right;       /* right subtree */
  frost_int8      balance;     /* height (left) - height (right) */
  frost_uint8     left_child;
  frost_uint8     right_child;
};


FROST_TreeNode* frost_tree_node_new                   (frost_pointer       key,
                             frost_pointer       value);
static void       frost_tree_insert_internal            (FROST_Tree         *tree,
                             frost_pointer       key,
                             frost_pointer       value,
                             frost_bool       replace);
static frost_bool   frost_tree_remove_internal            (FROST_Tree         *tree,
                             frost_constpointer  key,
                             frost_bool       steal);
static FROST_TreeNode* frost_tree_node_balance               (FROST_TreeNode     *node);
static FROST_TreeNode *frost_tree_find_node                  (FROST_Tree         *tree,
                             frost_constpointer  key);
static frost_int       frost_tree_node_pre_order             (FROST_TreeNode     *node,
                             FROSTTraverseFunc  traverse_func,
                             frost_pointer       data);
static frost_int       frost_tree_node_in_order              (FROST_TreeNode     *node,
                             FROSTTraverseFunc  traverse_func,
                             frost_pointer       data);
static frost_int       frost_tree_node_post_order            (FROST_TreeNode     *node,
                             FROSTTraverseFunc  traverse_func,
                             frost_pointer       data);
static frost_pointer   frost_tree_node_search                (FROST_TreeNode     *node,
                             FROSTCompareFunc   search_func,
                             frost_constpointer  data);
static FROST_TreeNode* frost_tree_node_rotate_left           (FROST_TreeNode     *node);
static FROST_TreeNode* frost_tree_node_rotate_right          (FROST_TreeNode     *node);
#ifdef G_TREE_DEBUG
static void       frost_tree_node_check                 (FROST_TreeNode     *node);
#endif


FROST_TreeNode*
frost_tree_node_new (frost_pointer key,
         frost_pointer value)
{
  FROST_TreeNode *node = frost_new (FROST_TreeNode,1);

  node->balance = 0;
  node->left = NULL;
  node->right = NULL;
  node->left_child = frost_false;
  node->right_child = frost_false;
  node->key = key;
  node->value = value;

  return node;
}

/**
 * frost_tree_new:
 * @key_compare_func: the function used to order the nodes in the #FROST_Tree.
 *   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 #FROST_Tree.
 *
 * Return value: a new #FROST_Tree.
 **/
FROST_Tree*
frost_tree_new (FROSTCompareFunc key_compare_func)
{
  frost_return_val_if_fail (key_compare_func != NULL, NULL);

  return frost_tree_new_full ((FROSTCompareDataFunc) key_compare_func, NULL,
                          NULL, NULL);
}

/**
 * frost_tree_new_with_data:
 * @key_compare_func: qsort()-style comparison function.
 * @key_compare_data: data to pass to comparison function.
 *
 * Creates a new #FROST_Tree with a comparison function that accepts user data.
 * See frost_tree_new() for more details.
 *
 * Return value: a new #FROST_Tree.
 **/
FROST_Tree*
frost_tree_new_with_data (FROSTCompareDataFunc key_compare_func,
              frost_pointer         key_compare_data)
{
  frost_return_val_if_fail (key_compare_func != NULL, NULL);

  return frost_tree_new_full (key_compare_func, key_compare_data,
              NULL, NULL);
}

/**
 * frost_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 #FROST_Tree 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 #FROST_Tree or %NULL if you
 *   don't want to supply such a function.
 *
 * Creates a new #FROST_Tree like frost_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 #FROST_Tree.
 *
 * Return value: a new #FROST_Tree.
 **/
FROST_Tree*
frost_tree_new_full (FROSTCompareDataFunc key_compare_func,
         frost_pointer         key_compare_data,
                 FROSTDestroyNotify   key_destroy_func,
         FROSTDestroyNotify   value_destroy_func)
{
  FROST_Tree *tree;

  frost_return_val_if_fail (key_compare_func != NULL, NULL);

  tree = frost_new (FROST_Tree,1);
  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;
}

FROST_TreeNode *
frost_tree_first_node (FROST_Tree *tree)
{
  FROST_TreeNode *tmp;

  if (!tree->root)
    return NULL;

  tmp = tree->root;

  while (tmp->left_child)
    tmp = tmp->left;

  return tmp;
}

FROST_TreeNode *
frost_tree_node_previous (FROST_TreeNode *node)
{
  FROST_TreeNode *tmp;

  tmp = node->left;

  if (node->left_child)
    while (tmp->right_child)
      tmp = tmp->right;

  return tmp;
}

FROST_TreeNode *
frost_tree_node_next (FROST_TreeNode *node)
{
  FROST_TreeNode *tmp;

  tmp = node->right;

  if (node->right_child)
    while (tmp->left_child)
      tmp = tmp->left;

  return tmp;
}

void
frost_tree_remove_all (FROST_Tree *tree)
{
  FROST_TreeNode *node;
  FROST_TreeNode *next;

  frost_return_if_fail (tree != NULL);

  node = frost_tree_first_node (tree);

  while (node)
    {
      next = frost_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);
      frost_free (node);// TODO: Important this can generate memory leak: frost_slice_free (FROST_Tree, tree);

      node = next;
    }

  tree->root = NULL;
  tree->nnodes = 0;
}

/**
 * frost_tree_ref:
 * @tree: a #FROST_Tree.
 *
 * Increments the reference count of @tree by one.  It is safe to call
 * this function from any thread.
 *
 * Return value: the passed in #FROST_Tree.
 *
 * Since: 2.22
 **/
FROST_Tree *
frost_tree_ref (FROST_Tree *tree)
{
  frost_return_val_if_fail (tree != NULL, NULL);

  frost_atomic_int_inc (&tree->ref_count);

  return tree;
}

/**
 * frost_tree_unref:
 * @tree: a #FROST_Tree.
 *
 * 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
frost_tree_unref (FROST_Tree *tree)
{
  frost_return_if_fail (tree != NULL);

  if (frost_atomic_int_dec_and_test (&tree->ref_count))
    {
      frost_tree_remove_all (tree);
      frost_free (tree);// TODO: Important this can generate memory leak: frost_slice_free (FROST_Tree, tree);
      tree = 0 ;
    }
}

/**
 * frost_tree_destroy:
 * @tree: a #FROST_Tree.
 *
 * Removes all keys and values from the #FROST_Tree and decreases its
 * reference count by one. If keys and/or values are dynamically
 * allocated, you should either free them first or create the #FROST_Tree
 * using frost_tree_new_full().  In the latter case the destroy functions
 * you supplied will be called on all keys and values before destroying
 * the #FROST_Tree.
 **/
void
frost_tree_destroy (FROST_Tree *tree)
{
  frost_return_if_fail (tree != NULL);

  frost_tree_remove_all (tree);
  frost_tree_unref (tree);
}

/**
 * frost_tree_insert:
 * @tree: a #FROST_Tree.
 * @key: the key to insert.
 * @value: the value corresponding to the key.
 *
 * Inserts a key/value pair into a #FROST_Tree. If the given key already exists
 * in the #FROST_Tree its corresponding value is set to the new value. If you
 * supplied a value_destroy_func when creating the #FROST_Tree, the old value is
 * freed using that function. If you supplied a @key_destroy_func when
 * creating the #FROST_Tree, 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
frost_tree_insert (FROST_Tree    *tree,
           frost_pointer  key,
           frost_pointer  value)
{
  frost_return_if_fail (tree != NULL);

  frost_tree_insert_internal (tree, key, value, frost_false);

#ifdef G_TREE_DEBUG
  frost_tree_node_check (tree->root);
#endif
}

/**
 * frost_tree_replace:
 * @tree: a #FROST_Tree.
 * @key: the key to insert.
 * @value: the value corresponding to the key.
 *
 * Inserts a new key and value into a #FROST_Tree similar to frost_tree_insert().
 * The difference is that if the key already exists in the #FROST_Tree, it gets
 * replaced by the new key. If you supplied a @value_destroy_func when
 * creating the #FROST_Tree, the old value is freed using that function. If you
 * supplied a @key_destroy_func when creating the #FROST_Tree, the old key is
 * freed using that function.tree
 *
 * 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
frost_tree_replace (FROST_Tree    *tree,
        frost_pointer  key,
        frost_pointer  value)
{
  frost_return_if_fail (tree != NULL);

  frost_tree_insert_internal (tree, key, value, frost_true);

#ifdef G_TREE_DEBUG
  frost_tree_node_check (tree->root);
#endif
}

/* internal insert routine */
void
frost_tree_insert_internal (FROST_Tree    *tree,
                        frost_pointer  key,
                        frost_pointer  value,
                        frost_bool  replace)
{
  FROST_TreeNode *node;
  FROST_TreeNode *path[MAX_FROST_Tree_HEIGHT];
  int idx;

  frost_return_if_fail (tree != NULL);

  if (!tree->root)
    {
      tree->root = frost_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
            {
              FROST_TreeNode *child = frost_tree_node_new (key, value);

              child->left = node->left;
              child->right = node;
              node->left = child;
              node->left_child = frost_true;
              node->balance -= 1;

          tree->nnodes++;

              break;
            }
        }
      else
        {
          if (node->right_child)
            {
              path[idx++] = node;
              node = node->right;
            }
          else
            {
              FROST_TreeNode *child = frost_tree_node_new (key, value);

              child->right = node->right;
              child->left = node;
              node->right = child;
              node->right_child = frost_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)
    {
      FROST_TreeNode *bparent = path[--idx];
      frost_bool left_node = (bparent && node == bparent->left);
      CABOT_ASSERT (!bparent || bparent->left == node || bparent->right == node);

      if (node->balance < -1 || node->balance > 1)
        {
          node = frost_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;
    }
}

/**
 * frost_tree_remove:
 * @tree: a #FROST_Tree.
 * @key: the key to remove.
 *
 * Removes a key/value pair from a #FROST_Tree.
 *
 * If the #FROST_Tree was created using frost_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 #FROST_Tree, the function does nothing.
 *
 * Returns: %frost_true if the key was found (prior to 2.8, this function returned
 *   nothing)
 **/
frost_bool
frost_tree_remove (FROST_Tree         *tree,
           frost_constpointer  key)
{
  frost_bool removed;

  frost_return_val_if_fail (tree != NULL, frost_false);

  removed = frost_tree_remove_internal (tree, key, frost_false);

#ifdef G_TREE_DEBUG
  frost_tree_node_check (tree->root);
#endif

  return removed;
}

/**
 * frost_tree_steal:
 * @tree: a #FROST_Tree.
 * @key: the key to remove.
 *
 * Removes a key and its associated value from a #FROST_Tree without calling
 * the key and value destroy functions.
 *
 * If the key does not exist in the #FROST_Tree, the function does nothing.
 *
 * Returns: %frost_true if the key was found (prior to 2.8, this function returned
 *    nothing)
 **/
frost_bool
frost_tree_steal (FROST_Tree         *tree,
              frost_constpointer  key)
{
  frost_bool removed;

  frost_return_val_if_fail (tree != NULL, frost_false);

  removed = frost_tree_remove_internal (tree, key, frost_true);

#ifdef G_TREE_DEBUG
  frost_tree_node_check (tree->root);
#endif

  return removed;
}

/* internal remove routine */
frost_bool
frost_tree_remove_internal (FROST_Tree         *tree,
                        frost_constpointer  key,
                        frost_bool       steal)
{
  FROST_TreeNode *node, *parent, *balance;
  FROST_TreeNode *path[MAX_FROST_Tree_HEIGHT];
  int idx;
  frost_bool left_node;

  frost_return_val_if_fail (tree != NULL, frost_false);

  if (!tree->root)
    return frost_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 frost_false;

      path[idx++] = node;
      node = node->left;
        }
      else
        {
          if (!node->right_child)
            return frost_false;

      path[idx++] = node;
      node = node->right;
        }
    }

  /* the following code is almost equal to frost_tree_remove_node,
     except that we do not have to call frost_tree_node_parent. */
  balance = parent = path[--idx];
  CABOT_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 = frost_false;
              parent->left = node->left;
              parent->balance += 1;
            }
          else
            {
              parent->right_child = frost_false;
              parent->right = node->right;
              parent->balance -= 1;
            }
        }
      else /* node has a right child */
        {
          FROST_TreeNode *tmp = frost_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)
        {
          FROST_TreeNode *tmp = frost_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!) */
        {
      FROST_TreeNode *prev = node->left;
      FROST_TreeNode *next = node->right;
      FROST_TreeNode *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 = frost_false;
          nextp->balance += 1;

          next->right_child = frost_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 = frost_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)
      {
    FROST_TreeNode *bparent = path[--idx];
    CABOT_ASSERT (!bparent || bparent->left == balance || bparent->right == balance);
    left_node = (bparent && balance == bparent->left);

    if(balance->balance < -1 || balance->balance > 1)
      {
        balance = frost_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);
    }

  frost_free (node);// TODO: Important this can generate memory leak:frost_slice_free (FROST_TreeNode,node);
  node = 0;
  tree->nnodes--;

  return frost_true;
}

/**
 * frost_tree_lookup:
 * @tree: a #FROST_Tree.
 * @key: the key to look up.
 *
 * Gets the value corresponding to the given key. Since a #FROST_Tree is
 * automatically balanced as key/value pairs are added, key lookup is very
 * fast.
 *
 * Return value: the value corresponding to the key, or %NULL if the key was
 * not found.
 **/
frost_pointer
frost_tree_lookup (FROST_Tree         *tree,
           frost_constpointer  key)
{
  FROST_TreeNode *node;

  frost_return_val_if_fail (tree != NULL, NULL);

  node = frost_tree_find_node (tree, key);

  return node ? node->value : NULL;
}

/**
 * frost_tree_lookup_extended:
 * @tree: a #FROST_Tree.
 * @lookup_key: the key to look up.
 * @orifrost_key: returns the original key.
 * @value: returns the value associated with the key.
 *
 * Looks up a key in the #FROST_Tree, returning the original key and the
 * associated value and a #frost_bool which is %frost_true if the key was found. This
 * is useful if you need to free the memory allocated for the original key,
 * for example before calling frost_tree_remove().
 *
 * Return value: %frost_true if the key was found in the #FROST_Tree.
 **/
frost_bool
frost_tree_lookup_extended (FROST_Tree         *tree,
                        frost_constpointer  lookup_key,
                        frost_pointer      *orig_key,
                        frost_pointer      *value)
{
  FROST_TreeNode *node;

  frost_return_val_if_fail (tree != NULL, frost_false);

  node = frost_tree_find_node (tree, lookup_key);

  if (node)
    {
      if (orig_key)
        *orig_key = node->key;
      if (value)
        *value = node->value;
      return frost_true;
    }
  else
    return frost_false;
}

/**
 * frost_tree_foreach:
 * @tree: a #FROST_Tree.
 * @func: the function to call for each node visited. If this function
 *   returns %frost_true, the traversal is stopped.
 * @user_data: user data to pass to the function.
 *
 * Calls the given function for each of the key/value pairs in the #FROST_Tree.
 * The function is passed the key and value of each pair, and the given
 * @data parameter. The tree is traversed in sorted order.
 *
 * The tree may not be modified while iterating over it (you can't
 * add/remove items). To remove all items matching a predicate, you need
 * to add each item to a list in your #FROSTTraverseFunc as you walk over
 * the tree, then walk the list and remove each item.
 **/
void
frost_tree_foreach (FROST_Tree         *tree,
                FROSTTraverseFunc  func,
                frost_pointer       user_data)
{
  FROST_TreeNode *node;

  frost_return_if_fail (tree != NULL);

  if (!tree->root)
    return;

  node = frost_tree_first_node (tree);

  while (node)
    {
      if ((*func) (node->key, node->value, user_data))
    break;

      node = frost_tree_node_next (node);
    }
}


/**
 * 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 <link
 *                 linkend="glib-Balanced-Binary-Trees">Balanced Binary
 *                 Trees</link>.  For <link
 *                 linkend="glib-N-ary-Trees">N-ary Trees</link>, 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 traveral performed by frost_tree_traverse(),
 * frost_node_traverse() and frost_node_find().
 **/
void
frost_tree_traverse (FROST_Tree         *tree,
         FROSTTraverseFunc  traverse_func,
         FROSTTraverseType  traverse_type,
         frost_pointer       user_data)
{
  frost_return_if_fail (tree != NULL);

  if (!tree->root)
    return;

  switch (traverse_type)
    {
    case ICE_PRE_ORDER:
      frost_tree_node_pre_order (tree->root, traverse_func, user_data);
      break;

    case ICE_IN_ORDER:
      frost_tree_node_in_order (tree->root, traverse_func, user_data);
      break;

    case ICE_POST_ORDER:
      frost_tree_node_post_order (tree->root, traverse_func, user_data);
      break;

    case ICE_LEVEL_ORDER:
      TRACE_VERBOSE(("frost_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.\n"));
      break;
    }
}

/**
 * frost_tree_search:
 * @tree: a #FROST_Tree.
 * @search_func: a function used to search the #FROST_Tree.
 * @user_data: the data passed as the second argument to the @search_func
 * function.
 *
 * Searches a #FROST_Tree using @search_func.
 *
 * The @search_func is called with a pointer to the key of a key/value pair in
 * the tree, and the passed in @user_data. If @search_func returns 0 for a
 * key/value pair, then frost_tree_search_func() will return the value of that
 * pair. If @search_func returns -1,  searching will proceed among the
 * key/value pairs that have a smaller key; if @search_func returns 1,
 * searching will proceed among the key/value pairs that have a larger key.
 *
 * Return value: the value corresponding to the found key, or %NULL if the key
 * was not found.
 **/
frost_pointer
frost_tree_search (FROST_Tree         *tree,
           FROSTCompareFunc   search_func,
           frost_constpointer  user_data)
{
  frost_return_val_if_fail (tree != NULL, NULL);

  if (tree->root)
    return frost_tree_node_search (tree->root, search_func, user_data);
  else
    return NULL;
}

/**
 * frost_tree_height:
 * @tree: a #FROST_Tree.
 *
 * Gets the height of a #FROST_Tree.
 *
 * If the #FROST_Tree contains no nodes, the height is 0.
 * If the #FROST_Tree contains only one root node the height is 1.
 * If the root node has children the height is 2, etc.
 *
 * Return value: the height of the #FROST_Tree.
 **/
frost_int
frost_tree_height (FROST_Tree *tree)
{
  FROST_TreeNode *node;
  frost_int height;

  frost_return_val_if_fail (tree != NULL, 0);

  if (!tree->root)
    return 0;

  height = 0;
  node = tree->root;

  while (1)
    {
      height += 1 + MAX(node->balance, 0);

      if (!node->left_child)
    return height;

      node = node->left;
    }
}

/**
 * frost_tree_nnodes:
 * @tree: a #FROST_Tree.
 *
 * Gets the number of nodes in a #FROST_Tree.
 *
 * Return value: the number of nodes in the #FROST_Tree.
 **/
frost_int
frost_tree_nnodes (FROST_Tree *tree)
{
  frost_return_val_if_fail (tree != NULL, 0);

  return tree->nnodes;
}

FROST_TreeNode*
frost_tree_node_balance (FROST_TreeNode *node)
{
  if (node->balance < -1)
    {
      if (node->left->balance > 0)
    node->left = frost_tree_node_rotate_left (node->left);
      node = frost_tree_node_rotate_right (node);
    }
  else if (node->balance > 1)
    {
      if (node->right->balance < 0)
    node->right = frost_tree_node_rotate_right (node->right);
      node = frost_tree_node_rotate_left (node);
    }

  return node;
}

FROST_TreeNode *
frost_tree_find_node (FROST_Tree        *tree,
          frost_constpointer key)
{
  FROST_TreeNode *node;
  frost_int cmp;

  node = tree->root;
  if (!node)
    return NULL;

  while (1)
    {
      cmp = tree->key_compare (key, node->key, tree->key_compare_data);
      if (cmp == 0)
    return node;
      else if (cmp < 0)
    {
      if (!node->left_child)
        return NULL;

      node = node->left;
    }
      else
    {
      if (!node->right_child)
        return NULL;

      node = node->right;
    }
    }
}

frost_int
frost_tree_node_pre_order (FROST_TreeNode     *node,
               FROSTTraverseFunc  traverse_func,
               frost_pointer       data)
{
  if ((*traverse_func) (node->key, node->value, data))
    return frost_true;

  if (node->left_child)
    {
      if (frost_tree_node_pre_order (node->left, traverse_func, data))
    return frost_true;
    }

  if (node->right_child)
    {
      if (frost_tree_node_pre_order (node->right, traverse_func, data))
    return frost_true;
    }

  return frost_false;
}

frost_int
frost_tree_node_in_order (FROST_TreeNode     *node,
              FROSTTraverseFunc  traverse_func,
              frost_pointer       data)
{
  if (node->left_child)
    {
      if (frost_tree_node_in_order (node->left, traverse_func, data))
    return frost_true;
    }

  if ((*traverse_func) (node->key, node->value, data))
    return frost_true;

  if (node->right_child)
    {
      if (frost_tree_node_in_order (node->right, traverse_func, data))
    return frost_true;
    }

  return frost_false;
}

frost_int
frost_tree_node_post_order (FROST_TreeNode     *node,
            FROSTTraverseFunc  traverse_func,
            frost_pointer       data)
{
  if (node->left_child)
    {
      if (frost_tree_node_post_order (node->left, traverse_func, data))
    return frost_true;
    }

  if (node->right_child)
    {
      if (frost_tree_node_post_order (node->right, traverse_func, data))
    return frost_true;
    }

  if ((*traverse_func) (node->key, node->value, data))
    return frost_true;

  return frost_false;
}

frost_pointer
frost_tree_node_search (FROST_TreeNode     *node,
            FROSTCompareFunc   search_func,
            frost_constpointer  data)
{
  frost_int dir;

  if (!node)
    return NULL;

  while (1)
    {
      dir = (* search_func) (node->key, data);
      if (dir == 0)
    return node->value;
      else if (dir < 0)
    {
      if (!node->left_child)
        return NULL;

      node = node->left;
    }
      else
    {
      if (!node->right_child)
        return NULL;

      node = node->right;
    }
    }
}

FROST_TreeNode*
frost_tree_node_rotate_left (FROST_TreeNode *node)
{
  FROST_TreeNode *right;
  frost_int a_bal;
  frost_int b_bal;

  right = node->right;

  if (right->left_child)
    node->right = right->left;
  else
    {
      node->right_child = frost_false;
      node->right = right;
      right->left_child = frost_true;
    }
  right->left = node;

  a_bal = node->balance;
  b_bal = right->balance;

  if (b_bal <= 0)
    {
      if (a_bal >= 1)
    right->balance = b_bal - 1;
      else
    right->balance = a_bal + b_bal - 2;
      node->balance = a_bal - 1;
    }
  else
    {
      if (a_bal <= b_bal)
    right->balance = a_bal - 2;
      else
    right->balance = b_bal - 1;
      node->balance = a_bal - b_bal - 1;
    }

  return right;
}

FROST_TreeNode*
frost_tree_node_rotate_right (FROST_TreeNode *node)
{
  FROST_TreeNode *left;
  frost_int a_bal;
  frost_int b_bal;

  left = node->left;

  if (left->right_child)
    node->left = left->right;
  else
    {
      node->left_child = frost_false;
      node->left = left;
      left->right_child = frost_true;
    }
  left->right = node;

  a_bal = node->balance;
  b_bal = left->balance;

  if (b_bal <= 0)
    {
      if (b_bal > a_bal)
    left->balance = b_bal + 1;
      else
    left->balance = a_bal + 2;
      node->balance = a_bal - b_bal + 1;
    }
  else
    {
      if (a_bal <= -1)
    left->balance = b_bal + 1;
      else
    left->balance = a_bal + b_bal + 2;
      node->balance = a_bal + 1;
    }

  return left;
}

#ifdef G_TREE_DEBUG
frost_int
frost_tree_node_height (FROST_TreeNode *node)
{
  frost_int left_height;
  frost_int right_height;

  if (node)
    {
      left_height = 0;
      right_height = 0;

      if (node->left_child)
    left_height = frost_tree_node_height (node->left);

      if (node->right_child)
    right_height = frost_tree_node_height (node->right);

      return MAX (left_height, right_height) + 1;
    }

  return 0;
}

void
frost_tree_node_check (FROST_TreeNode *node)
{
  frost_int left_height;
  frost_int right_height;
  frost_int balance;
  FROST_TreeNode *tmp;

  if (node)
    {
      if (node->left_child)
    {
      tmp = frost_tree_node_previous (node);
      CABOT_ASSERT (tmp->right == node);
    }

      if (node->right_child)
    {
      tmp = frost_tree_node_next (node);
      CABOT_ASSERT (tmp->left == node);
    }

      left_height = 0;
      right_height = 0;

      if (node->left_child)
    left_height = frost_tree_node_height (node->left);
      if (node->right_child)
    right_height = frost_tree_node_height (node->right);

      balance = right_height - left_height;
      CABOT_ASSERT (balance == node->balance);

      if (node->left_child)
    frost_tree_node_check (node->left);
      if (node->right_child)
    frost_tree_node_check (node->right);
    }
}

void
frost_tree_node_dump (FROST_TreeNode *node,
          frost_int       indent)
{
  frost_print ("%*s%c\n", indent, "", *(char *)node->key);

  if (node->left_child)
    frost_tree_node_dump (node->left, indent + 2);
  else if (node->left)
    frost_print ("%*s<%c\n", indent + 2, "", *(char *)node->left->key);

  if (node->right_child)
    frost_tree_node_dump (node->right, indent + 2);
  else if (node->right)
    frost_print ("%*s>%c\n", indent + 2, "", *(char *)node->right->key);
}


void
frost_tree_dump (FROST_Tree *tree)
{
  if (tree->root)
    frost_tree_node_dump (tree->root, 0);
}
#endif
