/*
 *
 *  sptree.c:  The following code implements the basic operations on
 *  an event-set or priority-queue implemented using splay trees:
 *
 *  SPTREE *spinit( compare )	Make a new tree
 *  int spempty();		Is tree empty?
 *  SPBLK *spenq( n, q )	Insert n in q after all equal keys.
 *  SPBLK *spdeq( q )		Return first key in q, removing it.
 *  SPBLK *spenqprior( n, q )	Insert n in q before all equal keys.
 *  void splay( n, q )		n (already in q) becomes the root.
 *
 *  In the above, n points to an SPBLK type, while q points to an
 *  SPTREE.
 *
 *  The implementation used here is based on the implementation
 *  which was used in the tests of splay trees reported in:
 *
 *    An Empirical Comparison of Priority-Queue and Event-Set Implementations,
 *	by Douglas W. Jones, Comm. ACM 29, 4 (Apr. 1986) 300-311.
 *
 *  The changes made include the addition of the enqprior
 *  operation and the addition of up-links to allow for the splay
 *  operation.  The basic splay tree algorithms were originally
 *  presented in:
 *
 *	Self Adjusting Binary Trees,
 *		by D. D. Sleator and R. E. Tarjan,
 *			Proc. ACM SIGACT Symposium on Theory
 *			of Computing (Boston, Apr 1983) 235-245.
 *
 *  The enq and enqprior routines use variations on the
 *  top-down splay operation, while the splay routine is bottom-up.
 *  All are coded for speed.
 *
 *  Written by:
 *    Douglas W. Jones
 *
 *  Translated to C by:
 *    David Brower, daveb@rtech.uucp
 *
 */

# include "sptree.h"

/* USER SUPPLIED! */

extern char *emalloc();


/*----------------
 *
 * spinit() -- initialize an empty splay tree
 *
 */
SPTREE *
spinit()
{
    register SPTREE * q;

    q = (SPTREE *) emalloc( sizeof( *q ) );

    q->lookups = 0;
    q->lkpcmps = 0;
    q->enqs = 0;
    q->enqcmps = 0;
    q->splays = 0;
    q->splayloops = 0;
    q->root = NULL;
    return( q );
}

/*----------------
 *
 * spempty() -- is an event-set represented as a splay tree empty?
 */
int
spempty( q )

SPTREE *q;

{
    return( q == NULL || q->root == NULL );
}


/*----------------
 *
 *  spenq() -- insert item in a tree.
 *
 *  put n in q after all other nodes with the same key; when this is
 *  done, n will be the root of the splay tree representing q, all nodes
 *  in q with keys less than or equal to that of n will be in the
 *  left subtree, all with greater keys will be in the right subtree;
 *  the tree is split into these subtrees from the top down, with rotations
 *  performed along the way to shorten the left branch of the right subtree
 *  and the right branch of the left subtree
 */
SPBLK *
spenq( n, q )

register SPBLK * n;
register SPTREE * q;

{
    register SPBLK * left;	/* the rightmost node in the left tree */
    register SPBLK * right;	/* the leftmost node in the right tree */
    register SPBLK * next;	/* the root of the unsplit part */
    register SPBLK * temp;

    register char * key;
    register int Sct;		/* Strcmp value */

    q->enqs++;
    n->uplink = NULL;
    next = q->root;
    q->root = n;
    if( next == NULL )	/* trivial enq */
    {
        n->leftlink = NULL;
        n->rightlink = NULL;
    }
    else		/* difficult enq */
    {
        key = n->key;
        left = n;
        right = n;

        /* n's left and right children will hold the right and left
	   splayed trees resulting from splitting on n->key;
	   note that the children will be reversed! */

	q->enqcmps++;
        if ( STRCMP( next->key, key ) > 0 )
	    goto two;

    one:	/* assert next->key <= key */

	do	/* walk to the right in the left tree */
	{
            temp = next->rightlink;
            if( temp == NULL )
	    {
                left->rightlink = next;
                next->uplink = left;
                right->leftlink = NULL;
                goto done;	/* job done, entire tree split */
            }

	    q->enqcmps++;
            if( STRCMP( temp->key, key ) > 0 )
	    {
                left->rightlink = next;
                next->uplink = left;
                left = next;
                next = temp;
                goto two;	/* change sides */
            }

            next->rightlink = temp->leftlink;
            if( temp->leftlink != NULL )
	    	temp->leftlink->uplink = next;
            left->rightlink = temp;
            temp->uplink = left;
            temp->leftlink = next;
            next->uplink = temp;
            left = temp;
            next = temp->rightlink;
            if( next == NULL )
	    {
                right->leftlink = NULL;
                goto done;	/* job done, entire tree split */
            }

	    q->enqcmps++;

	} while( STRCMP( next->key, key ) <= 0 );	/* change sides */

    two:	/* assert next->key > key */

	do	/* walk to the left in the right tree */
	{
            temp = next->leftlink;
            if( temp == NULL )
	    {
                right->leftlink = next;
                next->uplink = right;
                left->rightlink = NULL;
                goto done;	/* job done, entire tree split */
            }

	    q->enqcmps++;
            if( STRCMP( temp->key, key ) <= 0 )
	    {
                right->leftlink = next;
                next->uplink = right;
                right = next;
                next = temp;
                goto one;	/* change sides */
            }
            next->leftlink = temp->rightlink;
            if( temp->rightlink != NULL )
	    	temp->rightlink->uplink = next;
            right->leftlink = temp;
            temp->uplink = right;
            temp->rightlink = next;
            next->uplink = temp;
            right = temp;
            next = temp->leftlink;
            if( next == NULL )
	    {
                left->rightlink = NULL;
                goto done;	/* job done, entire tree split */
            }

	    q->enqcmps++;

	} while( STRCMP( next->key, key ) > 0 );	/* change sides */

        goto one;

    done:	/* split is done, branches of n need reversal */

        temp = n->leftlink;
        n->leftlink = n->rightlink;
        n->rightlink = temp;
    }

    return( n );

} /* spenq */


/*----------------
 *
 *  spdeq() -- return and remove head node from a subtree.
 *
 *  remove and return the head node from the node set; this deletes
 *  (and returns) the leftmost node from q, replacing it with its right
 *  subtree (if there is one); on the way to the leftmost node, rotations
 *  are performed to shorten the left branch of the tree
 */
SPBLK *
spdeq( n )

register SPBLK * n;

{
    register SPBLK * deq;		/* one to return */
    register SPBLK * next;       	/* the next thing to deal with */
    register SPBLK * left;      	/* the left child of next */
    register SPBLK * farleft;		/* the left child of left */
    register SPBLK * farfarleft;	/* the left child of farleft */

    if( n == NULL )
    {
        deq = NULL;
    }
    else
    {
        next = n;
        left = next->leftlink;
        if( left == NULL )
	{
            deq = next;
            n = next->rightlink;
            if( n != NULL )
		n->uplink = NULL;
        }
	else for(;;)
	{
            /* next is not it, left is not NULL, might be it */
            farleft = left->leftlink;
            if( farleft == NULL )
	    {
                deq = left;
                next->leftlink = left->rightlink;
                if( left->rightlink != NULL )
		    left->rightlink->uplink = next;
		break;
            }

            /* next, left are not it, farleft is not NULL, might be it */
            farfarleft = farleft->leftlink;
            if( farfarleft == NULL )
	    {
                deq = farleft;
                left->leftlink = farleft->rightlink;
                if( farleft->rightlink != NULL )
		    farleft->rightlink->uplink = left;
		break;
            }

            /* next, left, farleft are not it, rotate */
            next->leftlink = farleft;
            farleft->uplink = next;
            left->leftlink = farleft->rightlink;
            if( farleft->rightlink != NULL )
		farleft->rightlink->uplink = left;
            farleft->rightlink = left;
            left->uplink = farleft;
            next = farleft;
            left = farfarleft;
	}
    }

    return( deq );

} /* spdeq */


/*----------------
 *
 *  spenqprior() -- insert into tree before other equal keys.
 *
 *  put n in q before all other nodes with the same key; after this is
 *  done, n will be the root of the splay tree representing q, all nodes in
 *  q with keys less than that of n will be in the left subtree, all with
 *  greater or equal keys will be in the right subtree; the tree is split
 *  into these subtrees from the top down, with rotations performed along
 *  the way to shorten the left branch of the right subtree and the right
 *  branch of the left subtree; the logic of spenqprior is exactly the
 *  same as that of spenq except for a substitution of comparison
 *  operators
 */
SPBLK *
spenqprior( n, q )

register SPBLK * n;
SPTREE * q;

{

    register SPBLK * left;	/* the rightmost node in the left tree */
    register SPBLK * right;	/* the leftmost node in the right tree */
    register SPBLK * next;	/* the root of unsplit part of tree */
    register SPBLK * temp;
    register int Sct;		/* Strcmp value */
    register char *key;

    n->uplink = NULL;
    next = q->root;
    q->root = n;
    if( next == NULL )	/* trivial enq */
    {
        n->leftlink = NULL;
        n->rightlink = NULL;
    }
    else		/* difficult enq */
    {
        key = n->key;
        left = n;
        right = n;

        /* n's left and right children will hold the right and left
	   splayed trees resulting from splitting on n->key;
	   note that the children will be reversed! */

        if( STRCMP( next->key, key ) >= 0 )
	    goto two;

    one:	/* assert next->key < key */

	do	/* walk to the right in the left tree */
	{
            temp = next->rightlink;
            if( temp == NULL )
	    {
                left->rightlink = next;
                next->uplink = left;
                right->leftlink = NULL;
                goto done;	/* job done, entire tree split */
            }
            if( STRCMP( temp->key, key ) >= 0 )
	    {
                left->rightlink = next;
                next->uplink = left;
                left = next;
                next = temp;
                goto two;	/* change sides */
            }
            next->rightlink = temp->leftlink;
            if( temp->leftlink != NULL )
		temp->leftlink->uplink = next;
            left->rightlink = temp;
            temp->uplink = left;
            temp->leftlink = next;
            next->uplink = temp;
            left = temp;
            next = temp->rightlink;
            if( next == NULL )
	    {
                right->leftlink = NULL;
                goto done;	/* job done, entire tree split */
            }

	} while( STRCMP( next->key, key ) < 0 );	/* change sides */

    two:	/* assert next->key >= key */

	do	 /* walk to the left in the right tree */
	{
            temp = next->leftlink;
            if( temp == NULL )
	    {
                right->leftlink = next;
                next->uplink = right;
                left->rightlink = NULL;
                goto done;	/* job done, entire tree split */
            }
            if( STRCMP( temp->key, key ) < 0 )
	    {
                right->leftlink = next;
                next->uplink = right;
                right = next;
                next = temp;
                goto one;	/* change sides */
            }
            next->leftlink = temp->rightlink;
            if( temp->rightlink != NULL )
		temp->rightlink->uplink = next;
            right->leftlink = temp;
            temp->uplink = right;
            temp->rightlink = next;
            next->uplink = temp;
            right = temp;
            next = temp->leftlink;
            if( next == NULL )
	    {
                left->rightlink = NULL;
                goto done;	/* job done, entire tree split */
            }

	} while( STRCMP( next->key, key ) >= 0 );	/* change sides */

        goto one;

    done:	/* split is done, branches of n need reversal */

        temp = n->leftlink;
        n->leftlink = n->rightlink;
        n->rightlink = temp;
    }

    return( n );

} /* spenqprior */

/*----------------
 *
 *  splay() -- reorganize the tree.
 *
 *  the tree is reorganized so that n is the root of the
 *  splay tree representing q; results are unpredictable if n is not
 *  in q to start with; q is split from n up to the old root, with all
 *  nodes to the left of n ending up in the left subtree, and all nodes
 *  to the right of n ending up in the right subtree; the left branch of
 *  the right subtree and the right branch of the left subtree are
 *  shortened in the process
 *
 *  this code assumes that n is not NULL and is in q; it can sometimes
 *  detect n not in q and complain
 */

void
splay( n, q )

register SPBLK * n;
SPTREE * q;

{
    register SPBLK * up;	/* points to the node being dealt with */
    register SPBLK * prev;	/* a descendent of up, already dealt with */
    register SPBLK * upup;	/* the parent of up */
    register SPBLK * upupup;	/* the grandparent of up */
    register SPBLK * left;	/* the top of left subtree being built */
    register SPBLK * right;	/* the top of right subtree being built */

    left = n->leftlink;
    right = n->rightlink;
    prev = n;
    up = prev->uplink;

    q->splays++;

    while( up != NULL )
    {
	q->splayloops++;

        /* walk up the tree towards the root, splaying all to the left of
	   n into the left subtree, all to right into the right subtree */

        upup = up->uplink;
        if( up->leftlink == prev )	/* up is to the right of n */
	{
            if( upup != NULL && upup->leftlink == up )  /* rotate */
	    {
                upupup = upup->uplink;
                upup->leftlink = up->rightlink;
                if( upup->leftlink != NULL )
		    upup->leftlink->uplink = upup;
                up->rightlink = upup;
                upup->uplink = up;
                if( upupup == NULL )
		    q->root = up;
		else if( upupup->leftlink == upup )
		    upupup->leftlink = up;
		else
		    upupup->rightlink = up;
                up->uplink = upupup;
                upup = upupup;
            }
            up->leftlink = right;
            if( right != NULL )
		right->uplink = up;
            right = up;

        }
	else				/* up is to the left of n */
	{
            if( upup != NULL && upup->rightlink == up )	/* rotate */
	    {
                upupup = upup->uplink;
                upup->rightlink = up->leftlink;
                if( upup->rightlink != NULL )
		    upup->rightlink->uplink = upup;
                up->leftlink = upup;
                upup->uplink = up;
                if( upupup == NULL )
		    q->root = up;
		else if( upupup->rightlink == upup )
		    upupup->rightlink = up;
		else
		    upupup->leftlink = up;
                up->uplink = upupup;
                upup = upupup;
            }
            up->rightlink = left;
            if( left != NULL )
		left->uplink = up;
            left = up;
        }
        prev = up;
        up = upup;
    }

# ifdef DEBUG
    if( q->root != prev )
    {
/*	fprintf(stderr, " *** bug in splay: n not in q *** " ); */
	abort();
    }
# endif

    n->leftlink = left;
    n->rightlink = right;
    if( left != NULL )
	left->uplink = n;
    if( right != NULL )
	right->uplink = n;
    q->root = n;
    n->uplink = NULL;

} /* splay */