home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume14 / splay-tree / spaux.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-05-08  |  7.5 KB  |  316 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.  */
  64.  
  65. # include    "sptree.h"
  66.  
  67.  
  68. /*----------------
  69.  *
  70.  * sphead() --    return the "lowest" element in the tree.
  71.  *
  72.  *    returns a reference to the head event in the event-set q,
  73.  *    represented as a splay tree; q->root ends up pointing to the head
  74.  *    event, and the old left branch of q is shortened, as if q had
  75.  *    been splayed about the head element; this is done by dequeueing
  76.  *    the head and then making the resulting queue the right son of
  77.  *    the head returned by spdeq; an alternative is provided which
  78.  *    avoids splaying but just searches for and returns a pointer to
  79.  *    the bottom of the left branch
  80.  */
  81. SPBLK *
  82. sphead( q )
  83.  
  84. register SPTREE * q;
  85.  
  86. {
  87.     register SPBLK * x;
  88.     
  89.     /* splay version, good amortized bound */
  90.     x = spdeq( q->root );
  91.     if( x != NULL )
  92.     {
  93.         x->rightlink = q->root;
  94.         x->leftlink = NULL;
  95.         x->uplink = NULL;
  96.         if( q->root != NULL )
  97.         q->root->uplink = x;
  98.     }
  99.     q->root = x;
  100.     
  101.     /* alternative version, bad amortized bound,
  102.        but faster on the average */
  103.     
  104. # if 0
  105.     x = q->root;
  106.     while( x->leftlink != NULL )
  107.     x = x->leftlink;
  108. # endif
  109.     
  110.     return( x );
  111.     
  112. } /* sphead */
  113.  
  114.  
  115.  
  116. /*----------------
  117.  *
  118.  * spdelete() -- Delete node from a tree.
  119.  *
  120.  *    n is deleted from q; the resulting splay tree has been splayed
  121.  *    around its new root, which is the successor of n
  122.  *
  123.  */
  124. void
  125. spdelete( n, q )
  126.  
  127. register SPBLK * n;
  128. register SPTREE * q;
  129.  
  130. {
  131.     register SPBLK * x;
  132.     
  133.     splay( n, q );
  134.     x = spdeq( q->root->rightlink );
  135.     if( x == NULL )        /* empty right subtree */
  136.     {
  137.         q->root = q->root->leftlink;
  138.         q->root->uplink = NULL;
  139.     }
  140.     else            /* non-empty right subtree */
  141.     {
  142.         x->uplink = NULL;
  143.         x->leftlink = q->root->leftlink;
  144.         x->rightlink = q->root->rightlink;
  145.         if( x->leftlink != NULL )
  146.         x->leftlink->uplink = x;
  147.         if( x->rightlink != NULL )
  148.         x->rightlink->uplink = x;
  149.         q->root = x;
  150.     }
  151.     
  152. } /* spdelete */
  153.  
  154.  
  155.  
  156. /*----------------
  157.  *
  158.  * spnext() -- return next higer item in the tree, or NULL.
  159.  *
  160.  *    return the successor of n in q, represented as a splay tree; the
  161.  *    successor becomes the root; two alternate versions are provided,
  162.  *    one which is shorter, but slower, and one which is faster on the
  163.  *    average because it does not do any splaying
  164.  *
  165.  */
  166. SPBLK *
  167. spnext( n, q )
  168.  
  169. register SPBLK * n;
  170. register SPTREE * q;
  171.  
  172. {
  173.     register SPBLK * next;
  174.     register SPBLK * x;
  175.     
  176.     /* splay version */
  177.     splay( n, q );
  178.     x = spdeq( n->rightlink );
  179.     if( x != NULL )
  180.     {
  181.         x->leftlink = n;
  182.         n->uplink = x;
  183.         x->rightlink = n->rightlink;
  184.         n->rightlink = NULL;
  185.         if( x->rightlink != NULL )
  186.         x->rightlink->uplink = x;
  187.         q->root = x;
  188.         x->uplink = NULL;
  189.     }
  190.     next = x;
  191.     
  192.     /* shorter slower version;
  193.        deleting last "if" undoes the amortized bound */
  194.     
  195. # if 0
  196.     splay( n, q );
  197.     x = n->rightlink;
  198.     if( x != NULL )
  199.     while( x->leftlink != NULL )
  200.         x = x->leftlink;
  201.     next = x;
  202.     if( x != NULL )
  203.     splay( x, q );
  204. # endif
  205.     
  206.     return( next );
  207.     
  208. } /* spnext */
  209.  
  210.  
  211.  
  212. /*----------------
  213.  *
  214.  * spprev() -- return previous node in a tree, or NULL.
  215.  *
  216.  *    return the predecessor of n in q, represented as a splay tree;
  217.  *    the predecessor becomes the root; an alternate version is
  218.  *    provided which is faster on the average because it does not do
  219.  *    any splaying
  220.  *
  221.  */
  222. SPBLK *
  223. spprev( n, q )
  224.  
  225. register SPBLK * n;
  226. register SPTREE * q;
  227.  
  228. {
  229.     register SPBLK * prev;
  230.     register SPBLK * x;
  231.     
  232.     /* splay version;
  233.        note: deleting the last "if" undoes the amortized bound */
  234.     
  235.     splay( n, q );
  236.     x = n->leftlink;
  237.     if( x != NULL )
  238.     while( x->rightlink != NULL )
  239.         x = x->rightlink;
  240.     prev = x;
  241.     if( x != NULL )
  242.     splay( x, q );
  243.     
  244.     return( prev );
  245.     
  246. } /* spprev */
  247.  
  248.  
  249.  
  250. /*----------------
  251.  *
  252.  * spenqbefore() -- insert node before another in a tree.
  253.  *
  254.  *    returns pointer to n.
  255.  *
  256.  *    event n is entered in the splay tree q as the immediate
  257.  *    predecessor of n1; in doing so, n1 becomes the root of the tree
  258.  *    with n as its left son
  259.  *
  260.  */
  261. SPBLK *
  262. spenqbefore( n, n1, q )
  263.  
  264. register SPBLK * n;
  265. register SPBLK * n1;
  266. register SPTREE * q;
  267.  
  268. {
  269.     splay( n1, q );
  270.     n->key = n1->key;
  271.     n->leftlink = n1->leftlink;
  272.     if( n->leftlink != NULL )
  273.     n->leftlink->uplink = n;
  274.     n->rightlink = NULL;
  275.     n->uplink = n1;
  276.     n1->leftlink = n;
  277.     
  278.     return( n );
  279.     
  280. } /* spenqbefore */
  281.  
  282.  
  283.  
  284. /*----------------
  285.  *
  286.  * spenqafter() -- enter n after n1 in tree q.
  287.  *
  288.  *    returns a pointer to n.
  289.  *
  290.  *    event n is entered in the splay tree q as the immediate
  291.  *    successor of n1; in doing so, n1 becomes the root of the tree
  292.  *    with n as its right son
  293.  */
  294. SPBLK *
  295. spenqafter( n, n1, q )
  296.  
  297. register SPBLK * n;
  298. register SPBLK * n1;
  299. register SPTREE * q;
  300.  
  301. {
  302.     splay( n1, q );
  303.     n->key = n1->key;
  304.     n->rightlink = n1->rightlink;
  305.     if( n->rightlink != NULL )
  306.     n->rightlink->uplink = n;
  307.     n->leftlink = NULL;
  308.     n->uplink = n1;
  309.     n1->rightlink = n;
  310.     
  311.     return( n );
  312.     
  313. } /* spenqafter */
  314.  
  315.  
  316.