home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1868 / spaux.c next >
Encoding:
C/C++ Source or Header  |  1990-12-28  |  8.0 KB  |  326 lines
  1. /*
  2.   spaux.c:  This code implements the following operations on an event-set
  3.   or priority-queue implemented using splay trees:
  4.   
  5.   n = sphead( q )        n is the head item in q (not removed).
  6.   spdelete( n, q )        n is removed from q.
  7.   n = spnext( np, q )        n is the successor of np in q.
  8.   n = spprev( np, q )        n is the predecessor of np in q.
  9.   spenqbefore( n, np, q )    n becomes the predecessor of np in q.
  10.   spenqafter( n, np, q )    n becomes the successor of np in q.
  11.   
  12.   In the above, n and np are pointers to single items (type
  13.   SPBLK *); q is an event-set (type SPTREE *),
  14.   The type definitions for these are taken
  15.   from file sptree.h.  All of these operations rest on basic
  16.   splay tree operations from file sptree.c.
  17.   
  18.   The basic splay tree algorithms were originally presented in:
  19.   
  20.   Self Adjusting Binary Trees,
  21.   by D. D. Sleator and R. E. Tarjan,
  22.   Proc. ACM SIGACT Symposium on Theory
  23.   of Computing (Boston, Apr 1983) 235-245.
  24.   
  25.   The operations in this package supplement the operations from
  26.   file splay.h to provide support for operations typically needed
  27.   on the pending event set in discrete event simulation.  See, for
  28.   example,
  29.   
  30.   Introduction to Simula 67,
  31.   by Gunther Lamprecht, Vieweg & Sohn, Braucschweig, Wiesbaden, 1981.
  32.   (Chapter 14 contains the relevant discussion.)
  33.   
  34.   Simula Begin,
  35.   by Graham M. Birtwistle, et al, Studentlitteratur, Lund, 1979.
  36.   (Chapter 9 contains the relevant discussion.)
  37.   
  38.   Many of the routines in this package use the splay procedure,
  39.   for bottom-up splaying of the queue.  Consequently, item n in
  40.   delete and item np in all operations listed above must be in the
  41.   event-set prior to the call or the results will be
  42.   unpredictable (eg:  chaos will ensue).
  43.   
  44.   Note that, in all cases, these operations can be replaced with
  45.   the corresponding operations formulated for a conventional
  46.   lexicographically ordered tree.  The versions here all use the
  47.   splay operation to ensure the amortized bounds; this usually
  48.   leads to a very compact formulation of the operations
  49.   themselves, but it may slow the average performance.
  50.   
  51.   Alternative versions based on simple binary tree operations are
  52.   provided (commented out) for head, next, and prev, since these
  53.   are frequently used to traverse the entire data structure, and
  54.   the cost of traversal is independent of the shape of the
  55.   structure, so the extra time taken by splay in this context is
  56.   wasted.
  57.   
  58.   This code was written by:
  59.   Douglas W. Jones with assistance from Srinivas R. Sataluri
  60.   
  61.   Translated to C by David Brower, daveb@rtech.uucp
  62.   
  63.   Thu Oct  6 12:11:33 PDT 1988 (daveb) Fixed spdeq, which was broken
  64.      handling one-node trees.  I botched the pascal translation of
  65.      a VAR parameter.  Changed interface, so callers must also be
  66.     corrected to pass the node by address rather than value.
  67.   Mon Apr  3 15:18:32 PDT 1989 (daveb)
  68.       Apply fix supplied by Mark Moraes <moraes@csri.toronto.edu> to
  69.     spdelete(), which dropped core when taking out the last element
  70.     in a subtree -- that is, when the right subtree was empty and
  71.     the leftlink was also null, it tried to take out the leftlink's
  72.     uplink anyway.
  73.  */
  74.  
  75. # include    "sptree.h"
  76.  
  77.  
  78. /*----------------
  79.  *
  80.  * sphead() --    return the "lowest" element in the tree.
  81.  *
  82.  *    returns a reference to the head event in the event-set q,
  83.  *    represented as a splay tree; q->root ends up pointing to the head
  84.  *    event, and the old left branch of q is shortened, as if q had
  85.  *    been splayed about the head element; this is done by dequeueing
  86.  *    the head and then making the resulting queue the right son of
  87.  *    the head returned by spdeq; an alternative is provided which
  88.  *    avoids splaying but just searches for and returns a pointer to
  89.  *    the bottom of the left branch
  90.  */
  91. SPBLK *
  92. sphead( q )
  93.  
  94. register SPTREE * q;
  95.  
  96. {
  97.     register SPBLK * x;
  98.     
  99.     /* splay version, good amortized bound */
  100.     x = spdeq( &q->root );
  101.     if( x != NULL )
  102.     {
  103.         x->rightlink = q->root;
  104.         x->leftlink = NULL;
  105.         x->uplink = NULL;
  106.         if( q->root != NULL )
  107.         q->root->uplink = x;
  108.     }
  109.     q->root = x;
  110.     
  111.     /* alternative version, bad amortized bound,
  112.        but faster on the average */
  113.     
  114. # if 0
  115.     x = q->root;
  116.     while( x->leftlink != NULL )
  117.     x = x->leftlink;
  118. # endif
  119.     
  120.     return( x );
  121.     
  122. } /* sphead */
  123.  
  124.  
  125.  
  126. /*----------------
  127.  *
  128.  * spdelete() -- Delete node from a tree.
  129.  *
  130.  *    n is deleted from q; the resulting splay tree has been splayed
  131.  *    around its new root, which is the successor of n
  132.  *
  133.  */
  134. void
  135. spdelete( n, q )
  136.  
  137. register SPBLK * n;
  138. register SPTREE * q;
  139.  
  140. {
  141.     register SPBLK * x;
  142.     
  143.     splay( n, q );
  144.     x = spdeq( &q->root->rightlink );
  145.     if( x == NULL )        /* empty right subtree */
  146.     {
  147.         q->root = q->root->leftlink;
  148.         if (q->root) q->root->uplink = NULL;
  149.     }
  150.     else            /* non-empty right subtree */
  151.     {
  152.         x->uplink = NULL;
  153.         x->leftlink = q->root->leftlink;
  154.         x->rightlink = q->root->rightlink;
  155.         if( x->leftlink != NULL )
  156.         x->leftlink->uplink = x;
  157.         if( x->rightlink != NULL )
  158.         x->rightlink->uplink = x;
  159.         q->root = x;
  160.     }
  161.     
  162. } /* spdelete */
  163.  
  164.  
  165.  
  166. /*----------------
  167.  *
  168.  * spnext() -- return next higer item in the tree, or NULL.
  169.  *
  170.  *    return the successor of n in q, represented as a splay tree; the
  171.  *    successor becomes the root; two alternate versions are provided,
  172.  *    one which is shorter, but slower, and one which is faster on the
  173.  *    average because it does not do any splaying
  174.  *
  175.  */
  176. SPBLK *
  177. spnext( n, q )
  178.  
  179. register SPBLK * n;
  180. register SPTREE * q;
  181.  
  182. {
  183.     register SPBLK * next;
  184.     register SPBLK * x;
  185.     
  186.     /* splay version */
  187.     splay( n, q );
  188.     x = spdeq( &n->rightlink );
  189.     if( x != NULL )
  190.     {
  191.         x->leftlink = n;
  192.         n->uplink = x;
  193.         x->rightlink = n->rightlink;
  194.         n->rightlink = NULL;
  195.         if( x->rightlink != NULL )
  196.         x->rightlink->uplink = x;
  197.         q->root = x;
  198.         x->uplink = NULL;
  199.     }
  200.     next = x;
  201.     
  202.     /* shorter slower version;
  203.        deleting last "if" undoes the amortized bound */
  204.     
  205. # if 0
  206.     splay( n, q );
  207.     x = n->rightlink;
  208.     if( x != NULL )
  209.     while( x->leftlink != NULL )
  210.         x = x->leftlink;
  211.     next = x;
  212.     if( x != NULL )
  213.     splay( x, q );
  214. # endif
  215.     
  216.     return( next );
  217.     
  218. } /* spnext */
  219.  
  220.  
  221.  
  222. /*----------------
  223.  *
  224.  * spprev() -- return previous node in a tree, or NULL.
  225.  *
  226.  *    return the predecessor of n in q, represented as a splay tree;
  227.  *    the predecessor becomes the root; an alternate version is
  228.  *    provided which is faster on the average because it does not do
  229.  *    any splaying
  230.  *
  231.  */
  232. SPBLK *
  233. spprev( n, q )
  234.  
  235. register SPBLK * n;
  236. register SPTREE * q;
  237.  
  238. {
  239.     register SPBLK * prev;
  240.     register SPBLK * x;
  241.     
  242.     /* splay version;
  243.        note: deleting the last "if" undoes the amortized bound */
  244.     
  245.     splay( n, q );
  246.     x = n->leftlink;
  247.     if( x != NULL )
  248.     while( x->rightlink != NULL )
  249.         x = x->rightlink;
  250.     prev = x;
  251.     if( x != NULL )
  252.     splay( x, q );
  253.     
  254.     return( prev );
  255.     
  256. } /* spprev */
  257.  
  258.  
  259.  
  260. /*----------------
  261.  *
  262.  * spenqbefore() -- insert node before another in a tree.
  263.  *
  264.  *    returns pointer to n.
  265.  *
  266.  *    event n is entered in the splay tree q as the immediate
  267.  *    predecessor of n1; in doing so, n1 becomes the root of the tree
  268.  *    with n as its left son
  269.  *
  270.  */
  271. SPBLK *
  272. spenqbefore( n, n1, q )
  273.  
  274. register SPBLK * n;
  275. register SPBLK * n1;
  276. register SPTREE * q;
  277.  
  278. {
  279.     splay( n1, q );
  280.     n->key = n1->key;
  281.     n->leftlink = n1->leftlink;
  282.     if( n->leftlink != NULL )
  283.     n->leftlink->uplink = n;
  284.     n->rightlink = NULL;
  285.     n->uplink = n1;
  286.     n1->leftlink = n;
  287.     
  288.     return( n );
  289.     
  290. } /* spenqbefore */
  291.  
  292.  
  293.  
  294. /*----------------
  295.  *
  296.  * spenqafter() -- enter n after n1 in tree q.
  297.  *
  298.  *    returns a pointer to n.
  299.  *
  300.  *    event n is entered in the splay tree q as the immediate
  301.  *    successor of n1; in doing so, n1 becomes the root of the tree
  302.  *    with n as its right son
  303.  */
  304. SPBLK *
  305. spenqafter( n, n1, q )
  306.  
  307. register SPBLK * n;
  308. register SPBLK * n1;
  309. register SPTREE * q;
  310.  
  311. {
  312.     splay( n1, q );
  313.     n->key = n1->key;
  314.     n->rightlink = n1->rightlink;
  315.     if( n->rightlink != NULL )
  316.     n->rightlink->uplink = n;
  317.     n->leftlink = NULL;
  318.     n->uplink = n1;
  319.     n1->rightlink = n;
  320.     
  321.     return( n );
  322.     
  323. } /* spenqafter */
  324.  
  325.  
  326.