/*
 * Tree Package Version 1.0, April 25, 1989.
 * Implementation by Eric Giguere.  This code is in the public domain.
 *
 * tree.c
 *
 * This module contains routines to create, search and modify simple
 * binary trees.  See the external documentation for information
 * on how to use the routines.
 *
 * External functions defined in this module:
 *
 *      tree_insert, tree_find, tree_delete, tree_burn
 *
 */

#define _NO_TREE_PROTOTYPES_

#include <stdio.h>
#include "tree.h"

/*
 * tree_insert -- Insert the given node into the given binary tree
 *                using the given comparison routine.  Returns
 *                TRUE if successful, FALSE if an error occurs.
 *                Duplicate keys are not permitted in the tree.
 */

int tree_insert( ins_node, root, cmp )
  tree_node  *ins_node, **root;
  int       (*cmp)();
  {
    tree_node *node;
    int        rel;

    /* Error-checking... */

    if( ins_node == NULL || root == NULL || cmp == NULL )
        return( FALSE );

    /* Initialize the internals of the node.  None of these
       fields should be changed outside of this module. */

    ins_node->parent = NULL;
    ins_node->left   = NULL;
    ins_node->right  = NULL;

    /* First element in tree? */

    if( *root == NULL )
      {
        *root = ins_node;
        return( TRUE );
      }

    /* Tree is non-empty, find spot to insert. */

    node = *root;

    for(;;)
      {
        rel = (*cmp)( ins_node, node );

        if( rel == 0 )
            return( FALSE ); /* Error -- key already in tree */

        if( rel < 0 )
          {
            if( node->left == NULL ) /* Insert new leaf */
              {
                node->left       = ins_node;
                ins_node->parent = node;
                break;
              }

            node  = node->left;
          }
        else
          {
            if( node->right == NULL ) /* Insert new leaf */
              {
                node->right      = ins_node;
                ins_node->parent = node;
                break;
              }

            node  = node->right;
          }
      }

    return( TRUE );
  }

/*
 * tree_find -- Search a binary tree using the given comparison function.
 *              A dummy node must be passed for use in comparing keys.
 *              Returns a pointer to the node or NULL if not found in
 *              the tree.
 */

tree_node *tree_find( key_node, root, cmp )
  tree_node  *key_node, **root;
  int       (*cmp)();
  {
    tree_node *node;
    int        rel;

    /* A bit of error-checking... */

    if( key_node == NULL || root == NULL || *root == NULL || cmp == NULL )
        return( NULL );

    node = *root;

    while( node != NULL )
      {
        /* Do comparison */

        rel = (*cmp)( key_node, node );

        if( rel == 0 )
            return( node );

        if( rel < 0 )
            node = node->left;
        else
            node = node->right;
      }

    return( NULL );
  }

/*
 * tree_delete -- Delete a given node from a binary tree.  The node must
 *                first be found using another routine such as tree_find.
 *                Returns a pointer to the deleted node -- the routine
 *                does no deallocation.
 */

tree_node *tree_delete( node, root )
  tree_node *node, **root;
  {
    tree_node *parent, *left, *right, *succ;
    int        is_left_child;

    /* Error-checking... */

    if( node == NULL || root == NULL || *root == NULL )
        return( NULL );

    parent = node->parent;
    left   = node->left;
    right  = node->right;

    if( parent != NULL )
        is_left_child = ( parent->left == node );
    else
        is_left_child = FALSE;

    /* Cases 1 and 2: node has no children or no right subtree */

    if( right == NULL )
      {
        if( parent != NULL )
          {
            if( is_left_child )
                parent->left  = left;
            else
                parent->right = left;

            if( left != NULL )
                left->parent = parent;
          }
        else
          {
            *root = left;

            if( left != NULL )
                left->parent = NULL;
          }

        return( node );
      }

    /*
     * Case 3: node has a right subtree, find the inorder successor
     *         and insert it in its place
     */

    for( succ = right; succ->left != NULL; succ = succ->left )
        ;

    succ->left        = left;

    if( left != NULL )
        left->parent  = succ;

    if( succ != right )
      {
        succ->parent->left = succ->right;

        if( succ->right != NULL )
            succ->right->parent = succ->parent;

        succ->right   = right;
        right->parent = succ;
      }

    succ->parent      = parent;

    if( parent != NULL )
      {
        if( is_left_child )
            parent->left  = succ;
        else
            parent->right = succ;
      }
    else
      {
        *root = succ;
      }

    return( node );
  }

/*
 * tree_burn -- Deletes all the nodes of a binary tree.  A pointer to
 *              a cleanup routine is passed as a parameter:  each node
 *              will be passed to this routine as it is removed from the
 *              tree.
 */

void tree_burn( node, func )
  tree_node  *node;
  void      (*func)();
  {
    if( node != NULL )
      {
        tree_burn( node->left, func );
        tree_burn( node->right, func );

        node->left   = NULL;
        node->parent = NULL;
        node->right  = NULL;

        if( func != NULL )
            (*func)( node );
      }
  }