/*
spaux.c: This code implements the following operations on an event-set
or priority-queue implemented using splay trees:
n = sphead( q ) n is the head item in q (not removed).
spdelete( n, q ) n is removed from q.
n = spnext( np, q ) n is the successor of np in q.
n = spprev( np, q ) n is the predecessor of np in q.
spenqbefore( n, np, q ) n becomes the predecessor of np in q.
spenqafter( n, np, q ) n becomes the successor of np in q.
In the above, n and np are pointers to single items (type
SPBLK *); q is an event-set (type SPTREE *),
The type definitions for these are taken
from file sptree.h. All of these operations rest on basic
splay tree operations from file sptree.c.
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 operations in this package supplement the operations from
file splay.h to provide support for operations typically needed
on the pending event set in discrete event simulation. See, for
example,
Introduction to Simula 67,
by Gunther Lamprecht, Vieweg & Sohn, Braucschweig, Wiesbaden, 1981.
(Chapter 14 contains the relevant discussion.)
Simula Begin,
by Graham M. Birtwistle, et al, Studentlitteratur, Lund, 1979.
(Chapter 9 contains the relevant discussion.)
Many of the routines in this package use the splay procedure,
for bottom-up splaying of the queue. Consequently, item n in
delete and item np in all operations listed above must be in the
event-set prior to the call or the results will be
unpredictable (eg: chaos will ensue).
Note that, in all cases, these operations can be replaced with
the corresponding operations formulated for a conventional
lexicographically ordered tree. The versions here all use the
splay operation to ensure the amortized bounds; this usually
leads to a very compact formulation of the operations
themselves, but it may slow the average performance.
Alternative versions based on simple binary tree operations are
provided (commented out) for head, next, and prev, since these
are frequently used to traverse the entire data structure, and
the cost of traversal is independent of the shape of the
structure, so the extra time taken by splay in this context is
wasted.
This code was written by:
Douglas W. Jones with assistance from Srinivas R. Sataluri
Translated to C by David Brower, daveb@rtech.uucp
*/
# include "sptree.h"
/*----------------
*
* sphead() -- return the "lowest" element in the tree.
*
* returns a reference to the head event in the event-set q,
* represented as a splay tree; q->root ends up pointing to the head
* event, and the old left branch of q is shortened, as if q had
* been splayed about the head element; this is done by dequeueing
* the head and then making the resulting queue the right son of
* the head returned by spdeq; an alternative is provided which
* avoids splaying but just searches for and returns a pointer to
* the bottom of the left branch
*/
SPBLK *
sphead( q )
register SPTREE * q;
{
register SPBLK * x;
/* splay version, good amortized bound */
x = spdeq( q->root );
if( x != NULL )
{
x->rightlink = q->root;
x->leftlink = NULL;
x->uplink = NULL;
if( q->root != NULL )
q->root->uplink = x;
}
q->root = x;
/* alternative version, bad amortized bound,
but faster on the average */
# if 0
x = q->root;
while( x->leftlink != NULL )
x = x->leftlink;
# endif
return( x );
} /* sphead */
/*----------------
*
* spdelete() -- Delete node from a tree.
*
* n is deleted from q; the resulting splay tree has been splayed
* around its new root, which is the successor of n
*
*/
void
spdelete( n, q )
register SPBLK * n;
register SPTREE * q;
{
register SPBLK * x;
splay( n, q );
x = spdeq( q->root->rightlink );
if( x == NULL ) /* empty right subtree */
{
q->root = q->root->leftlink;
q->root->uplink = NULL;
}
else /* non-empty right subtree */
{
x->uplink = NULL;
x->leftlink = q->root->leftlink;
x->rightlink = q->root->rightlink;
if( x->leftlink != NULL )
x->leftlink->uplink = x;
if( x->rightlink != NULL )
x->rightlink->uplink = x;
q->root = x;
}
} /* spdelete */
/*----------------
*
* spnext() -- return next higer item in the tree, or NULL.
*
* return the successor of n in q, represented as a splay tree; the
* successor becomes the root; two alternate versions are provided,
* one which is shorter, but slower, and one which is faster on the
* average because it does not do any splaying
*
*/
SPBLK *
spnext( n, q )
register SPBLK * n;
register SPTREE * q;
{
register SPBLK * next;
register SPBLK * x;
/* splay version */
splay( n, q );
x = spdeq( n->rightlink );
if( x != NULL )
{
x->leftlink = n;
n->uplink = x;
x->rightlink = n->rightlink;
n->rightlink = NULL;
if( x->rightlink != NULL )
x->rightlink->uplink = x;
q->root = x;
x->uplink = NULL;
}
next = x;
/* shorter slower version;
deleting last "if" undoes the amortized bound */
# if 0
splay( n, q );
x = n->rightlink;
if( x != NULL )
while( x->leftlink != NULL )
x = x->leftlink;
next = x;
if( x != NULL )
splay( x, q );
# endif
return( next );
} /* spnext */
/*----------------
*
* spprev() -- return previous node in a tree, or NULL.
*
* return the predecessor of n in q, represented as a splay tree;
* the predecessor becomes the root; an alternate version is
* provided which is faster on the average because it does not do
* any splaying
*
*/
SPBLK *
spprev( n, q )
register SPBLK * n;
register SPTREE * q;
{
register SPBLK * prev;
register SPBLK * x;
/* splay version;
note: deleting the last "if" undoes the amortized bound */
splay( n, q );
x = n->leftlink;
if( x != NULL )
while( x->rightlink != NULL )
x = x->rightlink;
prev = x;
if( x != NULL )
splay( x, q );
return( prev );
} /* spprev */
/*----------------
*
* spenqbefore() -- insert node before another in a tree.
*
* returns pointer to n.
*
* event n is entered in the splay tree q as the immediate
* predecessor of n1; in doing so, n1 becomes the root of the tree
* with n as its left son
*
*/
SPBLK *
spenqbefore( n, n1, q )
register SPBLK * n;
register SPBLK * n1;
register SPTREE * q;
{
splay( n1, q );
n->key = n1->key;
n->leftlink = n1->leftlink;
if( n->leftlink != NULL )
n->leftlink->uplink = n;
n->rightlink = NULL;
n->uplink = n1;
n1->leftlink = n;
return( n );
} /* spenqbefore */
/*----------------
*
* spenqafter() -- enter n after n1 in tree q.
*
* returns a pointer to n.
*
* event n is entered in the splay tree q as the immediate
* successor of n1; in doing so, n1 becomes the root of the tree
* with n as its right son
*/
SPBLK *
spenqafter( n, n1, q )
register SPBLK * n;
register SPBLK * n1;
register SPTREE * q;
{
splay( n1, q );
n->key = n1->key;
n->rightlink = n1->rightlink;
if( n->rightlink != NULL )
n->rightlink->uplink = n;
n->leftlink = NULL;
n->uplink = n1;
n1->rightlink = n;
return( n );
} /* spenqafter */