/*
 * Tree Package Version 1.0, April 25, 1989.
 * Implementation by Eric Giguere.  This code is in the public domain.
 *
 * splay.c
 *
 * Routines to create, search and modify binary splay trees.
 * Refer to the external documentation for details.
 *
 * External functions defined in this module:
 *
 *      splay_insert, splay_find, splay_delete, splay_burn
 *
 */

#define _NO_SPLAY_PROTOTYPES_

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

static void       splay();
static splay_node *srot_left(), *srot_right();
static splay_node *drot_left(), *drot_right();
static void       rot_cleanup();

/*
 * splay_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.
 *                 Tree is splayed after a successful insertion only.
 */

int splay_insert( ins_node, root, cmp )
  splay_node  *ins_node, **root;
  int        (*cmp)();
  {
    splay_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;
          }
      }

    splay( ins_node, root );
    return( TRUE );
  }

/*
 * splay_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 is splayed after search, using
 *               the last node searched.
 */

splay_node *splay_find( key_node, root, cmp )
  splay_node  *key_node, **root;
  int        (*cmp)();
  {
    splay_node *node, *parent;
    int        rel;

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

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

    node   = *root;
    parent =  NULL;

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

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

        if( rel == 0 )
          {
            splay( node, root );
            return( node );
          }

        parent = node;

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

    if( parent != NULL )
        splay( parent, root );

    return( NULL );
  }

/*
 * splay_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.  The tree is splayed after the
 *                 node is deleted (using its former parent).
 */

splay_node *splay_delete( node, root )
  splay_node *node, **root;
  {
    splay_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;

            splay( parent, root );
          }
        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;

        splay( parent, root );
      }
    else
      {
        *root = succ;
      }

    return( node );
  }

/*
 * splay_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.  This routine is identical to tree_burn.
 */

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

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

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

/*
 * splay -- "Splay" a node by moving it to the root of the tree using
 *          double rotations where possible.
 */

static void splay( node, root )
  splay_node *node, **root;
  {
    splay_node *parent, *gparent;

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

    parent  = node->parent;
    gparent = NULL;

    if( parent != NULL )
        gparent = parent->parent;

    /* Perform double rotations until we reach or are one
       level away from the root of the tree. */

    while( parent != NULL && gparent != NULL )
      {
        if( gparent->left == parent && parent->left == node )
          {
            /* Two single rotations right */

            node = srot_right( srot_right( gparent, root ), root );
          }
        else if( gparent->right == parent && parent->left == node )
          {
            /* Double rotation left */

            node = drot_left( gparent, root );
          }
        else if( gparent->right == parent && parent->right == node )
          {
            /* Two single rotation left */

            node = srot_left( srot_left( gparent, root ), root );
          }
        else /* gparent->left == parent && parent->right == node */
          {
            /* Double rotation right */

            node = drot_right( gparent, root );
          }

        parent  = node->parent;
        gparent = NULL;

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

    /* Might have to perform a final single rotation. */

    if( parent != NULL )
      {
        if( parent->left == node )
            srot_right( parent, root );
        else
            srot_left( parent, root );
      }

    return;
  }

/*
 *------------------------------------------------------
 * The following code was basically stolen from AVL.C
 *------------------------------------------------------
 */

/*
 * srot_left -- Perform a single left rotation.
 */

static splay_node *srot_left( pivot, root, ins )
  splay_node *pivot, **root;
  int       ins;
  {
    splay_node *child, *parent;

    parent        = pivot->parent;
    child         = pivot->right;
    pivot->right  = child->left;
    child->left   = pivot;
    child->parent = parent;
    pivot->parent = child;

    rot_cleanup( pivot, child, root, parent, child );

    return( child );
  }

/*
 * srot_right -- Perform a single right rotation.
 */

static splay_node *srot_right( pivot, root, ins )
  splay_node *pivot, **root;
  int       ins;
  {
    splay_node *child, *parent;

    parent        = pivot->parent;
    child         = pivot->left;
    pivot->left   = child->right;
    child->right  = pivot;
    child->parent = parent;
    pivot->parent = child;

    rot_cleanup( pivot, child, root, parent, child );

    return( child );
  }

/*
 * drot_left -- Perform a double left rotation.
 */

static splay_node *drot_left( pivot, root )
  splay_node *pivot, **root;
  {
    splay_node *child, *gchild, *parent;

    parent         = pivot->parent;
    child          = pivot->right;
    gchild         = child->left;
    pivot->right   = gchild->left;
    child->left    = gchild->right;
    gchild->right  = child;
    gchild->left   = pivot;
    gchild->parent = parent;
    pivot->parent  = gchild;
    child->parent  = gchild;

    rot_cleanup( pivot, child, root, parent, gchild );

    return( gchild );
  }

/*
 * drot_right -- Perform a double right rotation.
 */

static splay_node *drot_right( pivot, root )
  splay_node *pivot, **root;
  {
    splay_node *child, *gchild, *parent;

    parent         = pivot->parent;
    child          = pivot->left;
    gchild         = child->right;
    pivot->left    = gchild->right;
    child->right   = gchild->left;
    gchild->left   = child;
    gchild->right  = pivot;
    gchild->parent = parent;
    pivot->parent  = gchild;
    child->parent  = gchild;

    rot_cleanup( pivot, child, root, parent, gchild );

    return( gchild );
  }

/*
 * rot_cleanup -- Cleanup some miscellaneous pointers after
 *                performing a single or double rotation.
 */

static void rot_cleanup( pivot, child, root, parent, new_root )
  splay_node  *pivot, *child;
  splay_node **root;
  splay_node  *parent, *new_root;
  {
    if( pivot->left != NULL )
        pivot->left->parent = pivot;

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

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

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

    if( *root == pivot )
        *root = new_root;

    if( parent != NULL )
      {
        if( parent->left == pivot )
            parent->left = new_root;
        else
            parent->right = new_root;
      }
  }