/* (C) Copyright International Business Machines Corporation 23 January */
/* 1990.  All Rights Reserved. */
/*  */
/* See the file USERAGREEMENT distributed with this software for full */
/* terms and conditions of use. */
/* File: avlsubs.c */
/* Author: David F. Bacon */
#ifndef lint
static char sccsinfo[] = "@(#)avlsubs.c	1.3 3/13/90";
#endif

#include "li.h"
#include "storage.h"

/* for debugging, define this to be "(void) checkavlness(x)" */
#define CHECKAVLNESS(x) 

void fatalerror();

predef_exception
avltree_insert(table, key, root, value)
dfd_table *table;
valcell key;
avlnode_t **root;
valcell value;
{
    predef_exception insert();
    predef_exception rc;
    flag taller = FALSE;


    CHECKAVLNESS(*root);
    rc = insert(table, key, root, value, &taller);
    CHECKAVLNESS(*root);
    return(rc);
}

static predef_exception
insert(table, key, root, value, taller)
dfd_table *table;
valcell key;
avlnode_t **root;
valcell value;
flag *taller;
{
    void balanceleft(), balanceright();

    flag tallersubtree = FALSE;
    avlnode_t *newnode;
    comparison cmp;
    predef_exception err;


    if (*root is nil) {
	newnode = new(avlnode_t);
	if (newnode is nil)
	  return(Depletion);

	newnode->value = value;
	newnode->left = newnode->right = nil;
	newnode->balance = 0;

	*root = newnode;
	*taller = TRUE;
	return(Normal);
    }

    cmp = topcomp(value, (*root)->value, table, key);

    switch (cmp) {
      case CMP_EQUAL: {
	  return(DuplicateKey);
      }

      case CMP_LESS: {
	  err = insert(table, key, & (*root)->left, value, & tallersubtree);
	  if (err isnt Normal)
	    return(err);

	  if (not tallersubtree) 
	    *taller = FALSE;	/* no change at this level */
	  else
				/* was balanced, inserted to left; rebalance */
	    switch ((*root)->balance) {
	      case -1: {	/* was already left-heavy; do real work */
		  balanceleft(root, taller);
		  break;
	      }

	      case 0: {		/* was balanced; now leaning left */
		  (*root)->balance = -1;
		  *taller = TRUE;
		  break;
	      }

	      case 1: {		/* was leaning right; now balanced */
		  (*root)->balance = 0;
		  *taller = FALSE;
		  break;
	      }

	      default: {
		  fatalerror();
		  /*NOTREACHED*/
	      }
	    }

	  return(Normal);
      }				/* end of switch(cmp) case CMP_LESS */

      case CMP_GREATER: {
	  err = insert(table, key, & (*root)->right, value, & tallersubtree);
	  if (err isnt Normal)
	    return(err);

	  if (not tallersubtree) 
	    *taller = FALSE;	/* no change at this level */
	  else
				/* was balanced, inserted to right; fixup */
	    switch ((*root)->balance) {
	      case -1: {	/* was leaning left; now balanced */
		  (*root)->balance = 0;
		  *taller = FALSE;
		  break;
	      }

	      case 0: {		/* was balanced; now leaning right */
		  (*root)->balance = 1;
		  *taller = TRUE;
		  break;
	      }

	      case 1: {		/* was already right-heavy; do real work */
		  balanceright(root, taller);
		  break;
	      }

	      default: {
		  fatalerror();
		  /*NOTREACHED*/
	      }
	    }

	  return(Normal);
      }				/* end of switch(cmp) case CMP_GREATER */

      default: {		/* makes lint happy */
	  fatalerror();
	  /*NOTREACHED*/
      }
    }				/* end of switch(cmp) */
}


static void			/* root is imbalanced to the right; we fix. */
balanceright(root, taller)
avlnode_t **root;
flag *taller;
{
    void rotateleft(), rotateright();

    avlnode_t *rightchild;	/* right subtree of root */
    avlnode_t *rightleft;	/* left subtree of rightchild */


    rightchild = (*root)->right;

    switch (rightchild->balance) {
      case 0: {
	  fatalerror();		/* c'est impossible */
	  /*NOTREACHED*/
      }

      case 1: {			/* root and rightchild are leaning right, so */
				/*  we simply rotate root to the left. */
	  (*root)->balance = 0;
	  rightchild->balance = 0;
	  rotateleft(root);
	  *taller = FALSE;
	  return;
      }

      case -1: {		/* root is leaning right, rightchild is */
				/*  leaning left, so we have to do a double */
				/*  rotation. */
	  rightleft = rightchild->left;
	  
	  switch (rightleft->balance) {
	    case -1: {
		(*root)->balance = 0;
		rightchild->balance = 1;
		break;
	    }
	    case 0: {
		(*root)->balance = 0;
		rightchild->balance = 0;
		break;
	    }
	    case 1: {
		(*root)->balance = -1;
		rightchild->balance = 0;
		break;
	    }
	    default:
	      fatalerror();
	      /*NOTREACHED*/
	  }

	  rightleft->balance = 0;
	  rotateright(&rightchild);
				/* first, rotate rightchild to rebalance it */
	  (*root)->right = rightchild;
				/* make root point to new rightchild */

	  rotateleft(root);	/* now rotate the root to the left */
	  *taller = FALSE;
	  return;
      }

      default:
	fatalerror();
	/*NOTREACHED*/
    }
}



static void			/* root is imbalanced to the left; we fix. */
balanceleft(root, taller)
avlnode_t **root;
flag *taller;
{
    void rotateleft(), rotateright();

    avlnode_t *leftchild;	/* right subtree of root */
    avlnode_t *leftright;	/* right subtree of leftchild */


    leftchild = (*root)->left;

    switch (leftchild->balance) {
      case 0: {
	  fatalerror();		/* c'est impossible */
	  /*NOTREACHED*/
      }

      case -1: {		/* root and leftchild are leaning left, so */
				/*  we simply rotate root to the right. */
	  (*root)->balance = 0;
	  leftchild->balance = 0;
	  rotateright(root);
	  *taller = FALSE;
	  return;
      }

      case 1: {			/* root is leaning left, leftchild is */
				/*  leaning right, so we have to do a double */
				/*  rotation. */
	  leftright = leftchild->right;
	  
	  switch (leftright->balance) {
	    case -1: {
		(*root)->balance = 1;
		leftchild->balance = 0;
		break;
	    }
	    case 0: {
		(*root)->balance = 0;
		leftchild->balance = 0;
		break;
	    }
	    case 1: {
		(*root)->balance = 0;
		leftchild->balance = -1;
		break;
	    }
	    default:
	      fatalerror();
	      /*NOTREACHED*/
	  }

	  leftright->balance = 0;
	  rotateleft(&leftchild);
				/* first, rotate leftchild to rebalance it */
	  (*root)->left = leftchild;
				/* make root point to new leftchild */

	  rotateright(root);	/* now rotate the root to the left */
	  *taller = FALSE;
	  return;
      }

      default:
	fatalerror();
	/*NOTREACHED*/
    }
}


static void
rotateleft(root)
avlnode_t **root;
{
    avlnode_t *newroot;

    if (*root is nil) 
      fatalerror();

    if ((*root)->right is nil)
      fatalerror();

    newroot = (*root)->right;	/* right subtree becomes new root */
    (*root)->right = newroot->left; /* hoist left subtree up into old root */
    newroot->left = *root;	/* put old root in left subtree of newroot */
    *root = newroot;		/* reset root */
}


static void
rotateright(root)
avlnode_t **root;
{
    avlnode_t *newroot;

    if (*root is nil) 
      fatalerror();

    if ((*root)->left is nil)
      fatalerror();

    newroot = (*root)->left;	/* left subtree becomes new root */
    (*root)->left = newroot->right; /* hoist right subtree up into old root */
    newroot->right = *root;	/* put old root in right subtree of newroot */
    *root = newroot;		/* reset root */
}


void
avltree_delete(table, key, pos, root, value)
dfd_table *table;
valcell key;
avl_position *pos;
avlnode_t **root;
valcell value;
{
    void delete();

    flag shorter = FALSE;


    CHECKAVLNESS(*root);
    delete(table, key, pos, root, value, &shorter);
    CHECKAVLNESS(*root);
}


static void
delete(table, key, pos, root, value, shorter)
dfd_table *table;
valcell key;
avl_position *pos;
avlnode_t **root;
valcell value;
flag *shorter;
{
    void hoistpredecessor(), rebalanceleft(), rebalanceright();
    void avl_rm_from_path(), avl_truncate_path();

    comparison cmp;
    avlnode_t *deadnode;


    if (*root is nil) {
	fatalerror();
	/*NOTREACHED*/
    }

    cmp = topcomp(value, (*root)->value, table, key);

    switch (cmp) {
      case -1: {		/* look to your left */
	  delete(table, key, pos, & (*root)->left, value, shorter);
	  if (*shorter) 
	    rebalanceleft(root, shorter, pos);
	  break;
      }

      case 1: {			/* look to your right */
	  delete(table, key, pos, & (*root)->right, value, shorter);
	  if (*shorter) 
	    rebalanceright(root, shorter, pos);
	  break;
      }

      case 0: {			/* found it. */
	  deadnode = *root;
	  if ((*root)->right is nil) {
	      *root = (*root)->left;
	      *shorter = TRUE;
	      dispose(deadnode, avlnode_t);
	  }
	  else 
	    if ((*root)->left is nil) {
		*root = (*root)->right;
		*shorter = TRUE;
		avl_rm_from_path(*root, pos);
		dispose(deadnode, avlnode_t);
	    }
	    else {		/* hard case: node to be deleted has two */
				/*  children.  hoist up the inorder */
				/*  predecessor rather than deleting this */
				/*  node. */
		avl_truncate_path(*root, pos);
		hoistpredecessor(root, & (*root)->left, shorter, pos);
		if (*shorter)
		  rebalanceleft(root, shorter, pos);
	    }
      }
    }
}

static void
hoistpredecessor(target, pred, shorter, pos)
avlnode_t **target, **pred;
flag *shorter;
avl_position *pos;
{
    avlnode_t *deadnode;


    if ((*pred)->right isnt nil) { /* recurse and keep looking right */
	hoistpredecessor(target, & (*pred)->right, shorter, pos);
	if (*shorter)
	  rebalanceright(pred, shorter, pos);
    }
    else {			/* found target's inorder predecessor */
	(*target)->value = (*pred)->value;
				/* move this value to target... */
	deadnode = *pred;	/* ...and delete it... */
	*pred = (*pred)->left;	/* pull up the left subtree */
	*shorter = TRUE;
	dispose(deadnode, avlnode_t);
    }
}


static void
rebalanceleft(root, shorter, pos)
avlnode_t **root;
flag *shorter;
avl_position *pos;
{
    void avl_add_to_path();

    avlnode_t *rightchild;


    switch ((*root)->balance) {
      case -1: {
	  (*root)->balance = 0;	/* was unbalanced to left, but deleted it */
	  return;
      }

      case 0: {
	  (*root)->balance = 1;	/* was balanced, now leaning right */
	  *shorter = FALSE;	/* and no longer shortened */
	  return;
      }

      case 1: {
	  rightchild = (*root)->right;
	  switch (rightchild->balance) {
	    case 0: {
		(*root)->balance = 1;
		rightchild->balance = -1;
		*shorter = FALSE;
		rotateleft(root);
		avl_add_to_path((*root)->left, *root, AVL_LEFT, pos);
		return;
	    }

	    case 1: {
		(*root)->balance = 0;
		rightchild->balance = 0;
		rotateleft(root);
		avl_add_to_path((*root)->left, *root, AVL_LEFT, pos);
		return;
	    }

	    case -1: {
		switch (rightchild->left->balance) {
		  case -1: {
		      (*root)->balance = 0;
		      rightchild->balance = 1;
		      break;
		  }

		  case 0: {
		      (*root)->balance = 0;
		      rightchild->balance = 0;
		      break;		      
		  }

		  case 1: {
		      (*root)->balance = -1;
		      rightchild->balance = 0;
		      break;		      
		  }
		}
		rightchild->left->balance = 0;

		rotateright(& rightchild);
		(*root)->right = rightchild;
		rotateleft(root);
		avl_add_to_path((*root)->left, *root, AVL_LEFT, pos);
		return;
	    }
	  }
      }
    }
}


static void
rebalanceright(root, shorter, pos)
avlnode_t **root;
flag *shorter;
avl_position *pos;
{
    void avl_add_to_path();

    avlnode_t *leftchild;


    switch ((*root)->balance) {
      case 1: {
	  (*root)->balance = 0;	/* was unbalanced to right, but deleted it */
	  return;
      }

      case 0: {
	  (*root)->balance = -1; /* was balanced, now leaning left */
	  *shorter = FALSE;	/* and no longer shortened */
	  return;
      }

      case -1: {
	  leftchild = (*root)->left;
	  switch (leftchild->balance) {
	    case 0: {
		(*root)->balance = -1;
		leftchild->balance = 1;
		*shorter = FALSE;
		rotateright(root);
		avl_add_to_path((*root)->right, *root, AVL_RIGHT, pos);
		return;
	    }

	    case -1: {
		(*root)->balance = 0;
		leftchild->balance = 0;
		rotateright(root);
		avl_add_to_path((*root)->right, *root, AVL_RIGHT, pos);
		return;
	    }

	    case 1: {
		switch (leftchild->right->balance) {
		  case 1: {
		      (*root)->balance = 0;
		      leftchild->balance = -1;
		      break;
		  }

		  case 0: {
		      (*root)->balance = 0;
		      leftchild->balance = 0;
		      break;		      
		  }

		  case -1: {
		      (*root)->balance = 1;
		      leftchild->balance = 0;
		      break;		      
		  }
		}
		leftchild->right->balance = 0;

		rotateleft(& leftchild);
		(*root)->left = leftchild;
		rotateright(root);
		avl_add_to_path((*root)->right, *root, AVL_RIGHT, pos);
		return;
	    }
	  }
      }
    }
}



static void
fatalerror()
{
    exit(1);
    /*NOTREACHED*/
}


#ifdef DEBUG

static int
checkavlness(root)
avlnode_t *root;
{
    int lheight, rheight;


    if (root is nil)
      return(0);

    lheight = checkavlness(root->left);
    rheight = checkavlness(root->right);

    if (rheight-lheight isnt root->balance or abs(rheight-lheight) > 1)
      abort_nili("checkavlness");

    return(max(lheight,rheight) + 1);
}

#endif DEBUG
