/*
 * tree.c
 * Craig Kelley
 * 9 Oct 95
 */

#include "btree.h"

static node_ptr new_node(T_OBJECT value, node_ptr parent);

/*
 * T_insert_child
 *
 * Inserts a child at a specific place (T_LEFT, T_RIGHT) in a tree node.
 *
 * Input:  A Pointer to a Tree (as defined with T_new or T_insert)
 *         The child before which to insert (L_END for the end of the list)
 *         The object you wish to store there
 * Output: T_OK on success T_FAIL on failure
 */   

int T_new_child(node_ptr node, int child, T_OBJECT value) {

   node_ptr newnode;			/* our new node */

   switch (child) {
   case T_RIGHT:
      if (node->r_child != T_END)	/* erase the r_child if it's there */
	 if ((T_delete_branch(node->r_child)) != T_OK)
	    return T_FAIL;
      newnode = new_node(value, node);	/* create the new node */
      if (newnode == T_END)		/* if create failed... */
	 return T_FAIL;
      node->r_child = newnode;		/* point parent to child */
      return T_OK;
      break;
   case T_LEFT:
      if (node->l_child != T_END)	/* erase the l_child if it's there */
	 if ((T_delete_branch(node->l_child)) != T_OK)
	    return T_FAIL;
      newnode = new_node(value, node);
      if (newnode == T_END)
	 return T_FAIL;
      node->l_child = newnode;
      return T_OK;
      break;
   default:
      return T_FAIL;			/* bad child passed */
   }
      
   return (T_OK);		        /* make gcc happy */

}

/*
 * T_delete_branch
 *
 * Recursivly deletes a tree and all of it's children (you can send any
 * portion of a tree and everything below it will be erased.
 *
 * Input:  A Pointer to a tree (as defined with T_new or T_insert)
 * Output: T_OK on success T_FAIL on failure
 */

int T_delete_branch(node_ptr node) {

   if (node == T_TOP) return (T_FAIL);	/* validate pointer to tree */
   if (node->l_child != T_END)    	/* traverse tree */
      if ((T_delete_branch(node->l_child)) == T_FAIL)
	 return T_FAIL;
   if (node->r_child != T_END)
      if ((T_delete_branch(node->r_child)) == T_FAIL)
	 return T_FAIL;

   free(node);				/* deallocate memory (can't check) */
   return (T_OK);
}


/*
 * T_retrieve
 *
 * Return the value at this node
 *
 * Input:  A Pointer to a tree (as defined with T_new or T_insert)
 * Output: The value associated with this node (T_OBJECT)
 */

T_OBJECT T_retrieve(node_ptr node) {

   return (node->value);		/* return the value */

}

/*
 * T_change
 *
 * Edit the contents of a tree node.
 *
 * Input:  A Pointer to a tree (as defined with T_new or T_insert)
 *         A new object (T_OBJECT)
 * Output: T_OK on success T_FAIL on failure
 */

int T_change(node_ptr node, T_OBJECT newvalue) {

   if (node == T_END)			/* make sure it's valid */
      return (T_FAIL);
   node->value = newvalue;
   return (T_OK);
   
}

/*
 * T_next
 *
 * Get the pointer to the next node
 *
 * Input:  A Pointer to a tree (as defined with T_new or T_insert)
 *         The ordenal child (first, second, ..)
 * Output: A Pointer to the next node associated with that child or
 *         T_END if that child doesn't exist 
 */

node_ptr T_next(node_ptr node, int child) {

   switch (child) {
   case T_LEFT:
      return (node->l_child);
      break;
   case T_RIGHT:
      return (node->r_child);
      break;
   default:
      return (T_END);			/* bad child passed */
   }

}

/*
 * T_previous
 *
 * Get the pointer to the previous node (it's parent)
 *
 * Input:  A pointer to a tree node (as defined with T_new or T_insert)
 * Output: A pointer to it's parent or T_END if it's the root.
 */

node_ptr T_previous(node_ptr node) {

   if (node == T_END) return (T_END);	/* sanity check on args */
   return (node->parent);

}


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

node_ptr T_new(T_OBJECT value) {

   node_ptr newbie;
   
   newbie = new_node(value, T_TOP);	/* create a node with no parent */
   return (newbie);

}

/*
 * STATIC new_node
 *
 * Do the dirty work for T_new or T_insert
 *
 * Input:  A value for the tree, a pointer to it's parent
 * Output: The pointer to the new node.  It also stores the value in
 *         the tree struct and set's it's parent.
 */

static node_ptr new_node(T_OBJECT value, node_ptr parent) {

   node_ptr baby;

   baby = malloc(sizeof (tree_node));	/* get memory */
   if (baby == NULL)			/* standard test for malloc */
      return T_END;
   (baby -> value) = value;	/* assign current value to this child */
   (baby -> l_child) = T_END;
   (baby -> r_child) = T_END;
   (baby -> parent) = parent;
   
   return baby;
}