/*
 * bst.c (Binary Search Tree)
 * Craig Kelley
 * 5 Nov 95
 *
 * A binary tree package
 */

#include "bst.h"

static node_ptr traverse(node_ptr tree, T_OBJECT value);
static int less_than(T_OBJECT value, T_OBJECT value2);
static int is_equal(T_OBJECT value, T_OBJECT value2);
static node_ptr find_value(node_ptr node, T_OBJECT value);

/*
 * less_than
 */

static int less_than(T_OBJECT value, T_OBJECT value2) {

   if (value < value2)
      return 1;
   else
      return 0;
}

static int is_equal(T_OBJECT value, T_OBJECT value2) {

   if (value == value2)
      return 1;
   else
      return 0;
}


/*
 * find_value
 */

static node_ptr find_value(node_ptr node, T_OBJECT value) {
   
   if (is_equal(node->value, value))
       return node;
   
   if (less_than(value, node->value))   /* If it's on the left */
      if (node->l_child == T_END)
	 return node;
      else
	 node = traverse(node->l_child, value);
   else                                 /* It's on the right */
      if (node->r_child == T_END)
	 return node;
      else
	 node = traverse(node->r_child, value);

   return (node);
}

/*
 * traverse tree
 */

static node_ptr traverse(node_ptr tree, T_OBJECT value) {

   if (less_than(value, tree->value)) 	/* If it's on the left */
      if (tree->l_child == T_END)
	 return tree;
      else
	 tree = traverse(tree->l_child, value);
   else					/* It's on the right */
      if (tree->r_child == T_END)
	 return tree;
      else
	 tree = traverse(tree->r_child, value);

   return (tree);
}
      
/*
 * BST_replace
 */

int BST_replace (tree_ptr tree, T_OBJECT value, T_OBJECT value2) {

   node_ptr anode;
   if (tree->tree == T_END)             /* nothing in tree */
      return (T_FAIL);
   
   anode = find_value(tree->tree, value);
   if (is_equal(anode->value, value))
      anode->value = value2;
   else					/* didn't find value */
      return (T_FAIL);
   return (T_OK);
   
}

/*
 * BST_deletemin
 */

T_OBJECT BST_deletemin (tree_ptr tree) {

   T_OBJECT temp;
   node_ptr anode;
   
   if (tree->tree == T_END)		/* nothing in tree */
      return (T_FAIL);
   anode = tree->tree;
   while (anode->l_child != T_END) 
      anode = anode->l_child;
   temp = anode->value;
   BST_delete (tree, temp);
   return temp;
   
}

/*
 * BST_member
 */

int BST_member (tree_ptr tree, T_OBJECT value) {

   node_ptr anode;
   
   if (tree->tree == T_END)             /* nothing in tree */
      return (T_FAIL);
   anode = find_value(tree->tree, value);
   if (is_equal(anode->value, value))
      return (T_OK);
   else
      return (T_FAIL);
}


/*
 * BST_delete
 */

int BST_delete (tree_ptr tree, T_OBJECT value) {

   node_ptr anode, bnode;
   
   if (tree->tree == T_END)		/* nothing in tree */
      return (T_FAIL);
   anode = find_value(tree->tree, value);
   if (is_equal(anode->value, value)) 	/* if item was found in tree */
      if (anode->r_child == T_END)	/* if there are no right children */
	 if (anode->l_child == T_END)	/* it's a leaf we're erasing */
	    T_delete_branch(anode);
	 else {				/* otherwise, link left child */
	    bnode = anode->l_child;	/* to the parent of anode */
	    bnode->parent = anode->parent;
	    if (anode->parent == T_TOP) /* if it's the top, then we */
	       tree->tree = bnode;	/* must make the list point */
	    else			/* to the new node. */
	       if (anode->parent->l_child == anode)
		  anode->parent->l_child = bnode;
	       else
		  anode->parent->r_child = bnode;
	    T_delete_branch(anode);
	 }	    
      else {
	 bnode = anode->r_child;
	 while (bnode->l_child != T_END) /* find smallest value in right */
	    bnode = bnode->l_child;	/* children. */
	 anode->value = bnode->value;	/* swap values */
	 T_delete_branch(bnode);	/* erase the unused node */
      }
   else					/* value not found in tree */
      return (T_FAIL);
   return (T_OK);
}

/*
 * BST_insert
 */   

int BST_insert(tree_ptr tree, T_OBJECT value) {

   node_ptr anode;			/* a node place-holder */
   int returnvalue;
   
   returnvalue = T_OK;
   if (tree->tree == T_END) { 		/* new tree? */
      tree->tree = new_node(value, T_END);
      return (T_OK);
   }
      
   anode = traverse(tree->tree,value);
   if (less_than(value, anode->value)) 
      T_new_child(anode, T_LEFT, value);
   else
      T_new_child(anode, T_RIGHT, value);
   
   if ((anode->l_child == T_END) && (anode->r_child == T_END))
      returnvalue = T_FAIL;
   return (returnvalue);		/* return error level */

}


/*
 * BST_makenull
 *
 * Make a new tree
 *
 * Input:  The object to be placed in the new tree.
 * Output: A pointer to that tree, or T_END if it failed.
 */

tree_ptr BST_makenull() {

   tree_ptr new;
   
   new = malloc(sizeof (tree_head));
   if (new == NULL)			/* if malloc fails */
      return T_END;
   new->tree = T_END;			/* make zero nodes */
   return (new);
  
}