/*
 * tree.c
 * A package for managing generic binary trees.
 */
#include "tree.h"
#include <stdlib.h>

/* Prototypes of static functions: */
static void tree_del_node (Tree *p_tree, Node *p_node);
static void tree_reset_sub_tree (Node *p_node, int is_owner);

/* ------------------------------------------------------------------------
 * Function: tree_init
 */
Tree *tree_init (Comp_func f_comp, int is_owner)
{
  Tree    *p_tree;

  /* Sanity check: */
  if (f_comp == NULL)
    return (NULL);

  /* Allocate the Tree structure. */
  p_tree = (Tree *) malloc (sizeof(Tree));

  /* Set its fields (the tree is now empty). */
  p_tree->p_root = NULL;
  p_tree->n_objects = 0;
  p_tree->f_comp = f_comp;
  p_tree->is_owner = is_owner;

  return (p_tree);
}

/* ------------------------------------------------------------------------
 * Function: tree_insert
 */
void tree_insert (Tree *p_tree, void *p_obj)
{
  Node    *p_insert;      /* The new node we insert. */
  Node    *p_curr;        /* The current node we scan. */

  /* Sanity check: */
  if (p_tree == NULL || p_obj == NULL)
    return;

  /* Create a new node pointing to the new object. */
  p_insert = (Node *) malloc (sizeof(Node));

  p_insert->p_parent = NULL;
  p_insert->p_object = p_obj;
  p_insert->p_right = NULL;
  p_insert->p_left = NULL;

  /* If the tree is empty, set the new node as its root. */
  if (p_tree->p_root == NULL)
  {
    p_tree->p_root = p_insert;
    p_tree->n_objects = 1;

    return;
  }

  /* In case the tree is not empty, start scanning it from its root. */
  p_curr = p_tree->p_root;
  while (1)
  {
    /* Compare the inserted object with the object stored at the current
       node. */
    if (p_tree->f_comp (p_curr->p_object, p_obj) < 0)
    {
      /* The new object should be inserted at the left sub-tree of p_curr. */
      if (p_curr->p_left == NULL)
      {
        /* No left child - insert p_insert as p_curr's left child. */
        p_curr->p_left = p_insert;
        p_insert->p_parent = p_curr;
        break;
      }

      /* Proceed to the left sub-tree of p_curr. */
      p_curr = p_curr->p_left;
    }
    else
    {
      /* The new object should be inserted at the right sub-tree of p_curr. */
      if (p_curr->p_right == NULL)
      {
        /* No right child - insert p_insert as p_curr's right child. */
        p_curr->p_right = p_insert;
        p_insert->p_parent = p_curr;
        break;
      }

      /* Proceed to the right sub-tree of p_curr. */
      p_curr = p_curr->p_right;
    }
  }

  /* Update the number of objects in the tree. */
  p_tree->n_objects++;

  return;
}

/* ------------------------------------------------------------------------
 * Function: tree_find
 */
const Node *tree_find (const Tree *p_tree, void *p_obj)
{
  const Node  *p_curr;        /* The current node we scan. */
  int         res;            /* Current comparison result. */

  /* Sanity check: */
  if (p_tree == NULL || p_obj == NULL)
    return (NULL);

  /* Start scanning the tree it from its root. */
  p_curr = p_tree->p_root;

  while (p_curr != NULL)
  {
    /* Compare the queried object with the object stored at the current
       node. */
    res = p_tree->f_comp (p_curr->p_object, p_obj);

    if (res == 0)
    {
      /* The object was found at p_curr. */
      return (p_curr);
    }
    else if (res < 0)
    {
      /* Continue scanning the left sub-tree of p_curr. */
      p_curr = p_curr->p_left;
    }
    else
    {
      /* Continue scanning the right sub-tree of p_curr. */
      p_curr = p_curr->p_right;
    }
  }

  /* If we reached here, the queried object was not found. */
  return (NULL);
}

/* ------------------------------------------------------------------------
 * Function: tree_delete
 */
int tree_delete (Tree *p_tree, void *p_obj)
{
  Node  *p_del;             /* Points to the node to be deleted. */

  /* Sanity check: */
  if (p_tree == NULL || p_obj == NULL)
    return (0);

  /* Find the object in the tree. */
  p_del = (Node *) tree_find (p_tree, p_obj);

  if (p_del == NULL)
    /* The object is not found in the tree. */
    return (0);

  /* Delete the node containing p_obj from the tree: */
  tree_del_node (p_tree, p_del);

  return (1);
}

/* ------------------------------------------------------------------------
 * Function: tree_delete
 */
void tree_reset (Tree *p_tree)
{
  /* Sanity check: */
  if (p_tree == NULL)
    return;

  /* If the tree is not empty, delete the sub-tree rooted at the
     tree root (i.e. the entire tree). */
  if (p_tree->p_root != NULL)
    tree_reset_sub_tree (p_tree->p_root, p_tree->is_owner);

  /* Mark that the tree is now empty. */
  p_tree->p_root = NULL;
  p_tree->n_objects = 0;

  return;
}

/* ------------------------------------------------------------------------
 * Function: tree_min
 */
const Node *tree_min (const Tree *p_tree)
{
  const Node  *p_min;

  /* Sanity check: */
  if (p_tree == NULL)
    return (NULL);

  /* In case of an empty tree: */
  if (p_tree->p_root == NULL)
    return (NULL);

  /* Find the leftmost node in the tree and return it. */
  p_min = p_tree->p_root;

  while (p_min->p_left != NULL)
    p_min = p_min->p_left;

  return (p_min);
}

/* ------------------------------------------------------------------------
 * Function: tree_next
 */
const Node *tree_next (const Node *p_node)
{
  const Node  *p_succ;

  /* Sanity check: */
  if (p_node == NULL)
    return (NULL);

  /* Check if p_node has a right child and act accordingly. */
  if (p_node->p_right != NULL)
  {
    /* If the node has a right child, its successor is the leftmost
       child in the right sub-tree. */
    p_succ = p_node->p_right;

    while (p_succ->p_left != NULL)
      p_succ = p_succ->p_left;
  }
  else
  {
    /* Go up the tree until reaching an ancestor node from the left.
       This ancestor node is the successor of p_node in the tree. */
    p_succ = p_node;
    while (p_succ->p_parent != NULL &&
           p_succ == p_succ->p_parent->p_right)
    {
      p_succ = p_succ->p_parent;
    }

    p_succ = p_succ->p_parent;
  }

  return (p_succ);
}

/* ------------------------------------------------------------------------
 * Function: tree_max
 */
const Node *tree_max (const Tree *p_tree)
{
  const Node  *p_max;

  /* Sanity check: */
  if (p_tree == NULL)
    return (NULL);

  /* In case of an empty tree: */
  if (p_tree->p_root == NULL)
    return (NULL);

  /* Find the rightmost node in the tree and return it. */
  p_max = p_tree->p_root;

  while (p_max->p_right != NULL)
    p_max = p_max->p_right;

  return (p_max);

}

/* ------------------------------------------------------------------------
 * Function: tree_prev
 */
const Node *tree_prev (const Node *p_node)
{
  const Node  *p_pred;

  /* Sanity check: */
  if (p_node == NULL)
    return (NULL);

  /* Check if p_node has a left child and act accordingly. */
  if (p_node->p_left != NULL)
  {
    /* If the node has a left child, its predecessor is the rightmost
       child in the left sub-tree. */
    p_pred = p_node->p_left;

    while (p_pred->p_right != NULL)
      p_pred = p_pred->p_right;
  }
  else
  {
    /* Go up the tree until reaching an ancestor node from the right.
       This ancestor node is the predecessor of p_node in the tree. */
    p_pred = p_node;
    while (p_pred->p_parent != NULL &&
           p_pred == p_pred->p_parent->p_left)
    {
      p_pred = p_pred->p_parent;
    }

    p_pred = p_pred->p_parent;
  }

  return (p_pred);
}

/* ------------------------------------------------------------------------
 * Function: tree_del_node
 * Purpose:  Delete a node from a binary tree.
 * Input:    p_tree - The binary tree.
 *           p_node - A pointer to the node to be deleted.
 * Returns:  Nothing.
 */
static void tree_del_node (Tree *p_tree, Node *p_node)
{
  /* Check how many children p_node has and act accordingly. */
  if (p_node->p_left == NULL || p_node->p_right == NULL)
  {
    /* If one of the children is not NULL (but the other must be), keep
       a pointer to it. */
    Node  *p_child = NULL;

    if (p_node->p_left != NULL)
      p_child = p_node->p_left;
    else if (p_node->p_right != NULL)
      p_child = p_node->p_right;

    /* If necessary, free the object stored at p_node. */
    if (p_tree->is_owner)
      free (p_node->p_object);

    /* Link p_child directly to p_node's parent. */
    if (p_node->p_parent != NULL)
    {
      /* Check if p_node is a left or a right child, and link p_child
         instead of it. */
      if (p_node == p_node->p_parent->p_left)
        p_node->p_parent->p_left = p_child;
      else
        p_node->p_parent->p_right = p_child;
    }
    else
    {
      /* Make p_child the new tree root. */
      p_tree->p_root = p_child;
    }

    if (p_child != NULL)
      p_child->p_parent = p_node->p_parent;

    /* Free the node itself. */
    free (p_node);
  }
  else
  {
    /* The node to be deleted has two children: Find its successor, which
       is the leftmost node in its right sub-tree. */
    Node  *p_succ;
    void  *temp;

    p_succ = p_node->p_right;
    while (p_succ->p_left != NULL)
      p_succ = p_succ->p_left;

    /* Swap the objects pointed by p_node and its successor, so p_succ will
       store the object that we wish to delete. */
    temp = p_node->p_object;
    p_node->p_object = p_succ->p_object;
    p_succ->p_object = temp;

    /* Now we can simply delete p_succ recursively. Notice that it has one
       child at most, so the recursion will stop there. */
    tree_del_node (p_tree, p_succ);
  }

  return;
}

/* ------------------------------------------------------------------------
 * Function: tree_reset_sub_tree
 * Purpose:  Delete the entire sub-tree rooted at a given root.
 * Input:    p_node   - A pointer to the sub-tree root.
 *           is_owner - Does the tree own its objects (and should free them).
 * Returns:  Nothing.
 */
static void tree_reset_sub_tree (Node *p_node, int is_owner)
{
  /* If necessary, free the object. */
  if (is_owner)
    free (p_node->p_object);

  /* Free the left and right sub-trees recursively. */
  if (p_node->p_left != NULL)
    tree_reset_sub_tree (p_node->p_left, is_owner);

  if (p_node->p_right != NULL)
    tree_reset_sub_tree (p_node->p_right, is_owner);

  /* Free the node itself. */
  free (p_node);

  return;
}