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

/* ------------------------------------------------------------------------
 * 	Local static subroutines
 */

extern	int	balance_l	( HEADER** );
extern	int	balance_r	( HEADER** );
extern	int	descend		( HEADER**, HEADER** );
extern	int	del		( HEADER** );

/* ------------------------------------------------------------------------ */

static	HEADER	*Key;
static	int	(*Cmp) ();
static	int	Notfound;

/* ------------------------------------------------------------------------ */

static	int	balance_l( pp )
HEADER	**pp;
{
	/*  This routine is called when the left branch of the current
	 *  subtree (pointed to by p) has shrunk.  It adjusts the balance
	 *  factors and rebalances if necessary, modifying *pp to point
	 *  at the new root (after the rebalance).  Returns 1 if the
	 *  tree got smaller as a result of the delete or the rebalance
	 *  operation, else returns 0.
	 */
	 
	register HEADER	*p, *p1, *p2;
	int		b1, b2;
	int		got_smaller = 1;

	p = *pp;

	switch( p->bal )
	{
	case L: p->bal = B;				break;
	case B: p->bal = R;	got_smaller = 0;	break;	
	case R:						/* Rebalance	*/
		p1 = p->right;
		b1 = p1->bal;

		if( b1 >= B )				/* Single RR	*/
		{
			p->right  = p1->left;
			p1->left  = p;
			
			if( b1 != B )
				p->bal = p1->bal = B;
			else
			{
				p->bal   = R;
				p1->bal  = L;
				got_smaller = 0;
			}
			p = p1;
		}
		else					/* Double RL	*/
		{
			p2        = p1->left;
			b2        = p2->bal;
			p1->left  = p2->right;
			p2->right = p1;
			p->right  = p2->left;
			p2->left  = p;
			p->bal    = (b2 == R) ? L : B ;
			p1->bal   = (b2 == L) ? R : B ;
			p         = p2;
			p2->bal   = B;
		}
	}

	*pp = p;
	return got_smaller;
}

/* ------------------------------------------------------------------------ */

static	int	balance_r( pp )
HEADER	**pp;
{
	/*	Same as balance_l but is called when a right subtree
	 *	has been made smaller.
	 */
	 
	register HEADER	*p, *p1, *p2;
	int		b1, b2;
	int		got_smaller = 1;
	
	p = *pp;
	
	switch( p->bal )
	{
	case R: p->bal = B;				break;
	case B: p->bal = L;	got_smaller = 0;	break;
	case L:							/* rebalance */
		p1 = p->left;
		b1 = p1->bal;

		if( b1 <= B )					/* Single LL */
		{
			p->left   = p1->right;
			p1->right = p;

			if( b1 != B )
				p->bal = p1->bal = B;
			else
			{
				p->bal      = L;
				p1->bal     = R;
				got_smaller = 0;
			}
			p        = p1;
		}
	else
		{
			p2        = p1->right;			/* Double RL */
			b2        = p2->bal;
			p1->right = p2->left;
			p2->left  = p1;
			p->left   = p2->right;
			p2->right = p;
			p->bal    = (b2 == L) ? R : B ;
			p1->bal   = (b2 == R) ? L : B ;
			p         = p2;
			p2->bal   = B;
		}
	}
	
	*pp = p;
	return got_smaller ;
}

/* ------------------------------------------------------------------------ */

static	int	descend( rootp, dpp )
HEADER		**rootp;		/* Address of root of current node  */
HEADER		**dpp;			/* Address of node to be deleted    */
{
	/*  Does the actual delete when the root node has both left and
	 *  right decendants.  Descends to the rightmost node of the
	 *  left subtree and the copies the contents of that node
	 *  to the node-to-be-deleted (*dpp).  Then the node-to-be-deleted
	 *  is modified to point to the former rightmost node.
	 */

	if( (*rootp)->right )
		return( descend ( &(*rootp)->right, dpp) )
						? balance_r(rootp) : 0 ;
	else
	{
		memcpy( *dpp + 1, *rootp + 1, (*rootp)->size );
		
		*dpp	= (*rootp);
		*rootp	= (*rootp)->left;
		return 1;
	}
}

/* ------------------------------------------------------------------------ */

static	int	del( rootp )
HEADER		**rootp;
{
	/* Delete Key from tree pointed to by *rootp.  Return 1 if the size
	 * of the tree has been reduced, 0 otherwise.
	 */
	 
	HEADER	*dp;			/* Pointer to node to delete	*/
	int	got_smaller = 0;	/* set TRUE if tree shrinks	*/
	static int relation;
	
	if( !*rootp )
		Notfound = 1;
	else
	{
		relation = (*Cmp) (Key, *rootp + 1);
		
		if( relation < 0 )			/* Go Left	*/
		{
			if( del( &(*rootp)->left) )
				got_smaller = balance_l( rootp );
		}
		else if( relation > 0 )			/* Go Right	*/
		{
			if( del( &(*rootp)->right) )
				got_smaller = balance_r( rootp );
		}
		else
		{
			dp = *rootp ;
			
			if( dp->right == NULL )
			{
				*rootp      = dp->left;
				got_smaller = 1;
			}
			else if( dp->left == NULL )
			{
				*rootp      = dp->right;
				got_smaller = 1;
			}
			else if( descend( &(*rootp)->left, &dp ) )
			{
				got_smaller = balance_l( rootp );
			}
			
			free ( dp );
		}
	}
	
	return got_smaller;
}

/* ------------------------------------------------------------------------ */

int	delete( rootp, key, cmp )
HEADER	**rootp;
HEADER	*key;
int	(*cmp) ();
{
	/*  Cmp is a comparison routine called with (*cmp) (key, node);
	 *  where "key" is the second argument to delete and "node"
	 *  is a pointer to one node in the tree.  It should return
	 *  <0 if key<node 0  if key==node >0 if key>node.  Returns
	 *  1 if the node was deleted, 0 if the node wasn't in the
	 *  tree.
	 */
	 
	Cmp      = cmp;
	Key      = key;
	Notfound = 0;

	del( rootp );
	
	return !Notfound;
}