home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / programming / libg_ / libgpp / !libgpp / gen / ccp / SplayPQ < prev    next >
Text File  |  1995-06-16  |  10KB  |  524 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17. */
  18.  
  19. #ifdef __GNUG__
  20. #pragma implementation
  21. #endif
  22. #include <stream.h>
  23. #include "<T>.SplayPQ.h"
  24.  
  25.  
  26. /* 
  27.  
  28.  struct to simulate the special `null' node in the Sleater & Tarjan JACM 1985
  29.  splay tree algorithms
  30.  
  31.  All routines use a version of their `simple top-down' splay alg. (p 669)
  32.  
  33. */
  34.  
  35. struct _dummySplayNode
  36. {
  37.   <T>SplayNode*    lt;
  38.   <T>SplayNode*    rt;
  39.   <T>SplayNode*    par;
  40. } _dummy_null;
  41.  
  42.  
  43. /*
  44.  traversal primitives
  45. */
  46.  
  47.  
  48. <T>SplayNode* <T>SplayPQ::leftmost()
  49. {
  50.   <T>SplayNode* t = root;
  51.   if (t != 0) while (t->lt != 0) t = t->lt;
  52.   return t;
  53. }
  54.  
  55. <T>SplayNode* <T>SplayPQ::rightmost()
  56. {
  57.   <T>SplayNode* t = root;
  58.   if (t != 0) while (t->rt != 0) t = t->rt;
  59.   return t;
  60. }
  61.  
  62. <T>SplayNode* <T>SplayPQ::succ(<T>SplayNode* t)
  63. {
  64.   if (t == 0)
  65.     return 0;
  66.   if (t->rt != 0)
  67.   {
  68.     t = t->rt;
  69.     while (t->lt != 0) t = t->lt;
  70.     return t;
  71.   }
  72.   else
  73.   {
  74.     for (;;)
  75.     {
  76.       if (t->par == 0 || t == t->par->lt)
  77.         return t->par;
  78.       else
  79.         t = t->par;
  80.     }
  81.   }
  82. }
  83.  
  84. <T>SplayNode* <T>SplayPQ::pred(<T>SplayNode* t)
  85. {
  86.   if (t == 0)
  87.     return 0;
  88.   else if (t->lt != 0)
  89.   {
  90.     t = t->lt;
  91.     while (t->rt != 0) t = t->rt;
  92.     return t;
  93.   }
  94.   else
  95.   {
  96.     for (;;)
  97.     {
  98.       if (t->par == 0 || t == t->par->rt)
  99.         return t->par;
  100.       else
  101.         t = t->par;
  102.     }
  103.   }
  104. }
  105.  
  106.  
  107. Pix <T>SplayPQ::seek(<T&> key)
  108. {
  109.   <T>SplayNode* t = root;
  110.   if (t == 0)
  111.     return 0;
  112.  
  113.   int comp = <T>CMP(key, t->item);
  114.   if (comp == 0)
  115.     return Pix(t);
  116.  
  117.   <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
  118.   <T>SplayNode* l = dummy;
  119.   <T>SplayNode* r = dummy;
  120.   dummy->rt = dummy->lt = dummy->par = 0;
  121.  
  122.   while (comp != 0)
  123.   {
  124.     if (comp > 0)
  125.     {
  126.       <T>SplayNode* tr = t->rt;
  127.       if (tr == 0)
  128.         break;
  129.       else
  130.       {
  131.         comp = <T>CMP(key, tr->item);
  132.         if (comp <= 0 || tr->rt == 0)
  133.         {
  134.           l->rt = t; t->par = l;
  135.           l = t;
  136.           t = tr;
  137.           if (comp >= 0)
  138.             break;
  139.         }
  140.         else
  141.         {
  142.           if ((t->rt = tr->lt) != 0) t->rt->par = t;
  143.           tr->lt = t; t->par = tr;
  144.           l->rt = tr; tr->par = l;
  145.           l = tr;
  146.           t = tr->rt;
  147.           comp = <T>CMP(key, t->item);
  148.         }
  149.       }
  150.     }
  151.     else
  152.     {
  153.       <T>SplayNode* tl = t->lt;
  154.       if (tl == 0)
  155.         break;
  156.       else
  157.       {
  158.         comp = <T>CMP(key, tl->item);
  159.         if (comp >= 0 || tl->lt == 0)
  160.         {
  161.           r->lt = t; t->par = r;
  162.           r = t;
  163.           t = tl;
  164.           if (comp <= 0)
  165.             break;
  166.         }
  167.         else
  168.         {
  169.           if ((t->lt = tl->rt) != 0) t->lt->par = t;
  170.           tl->rt = t; t->par = tl;
  171.           r->lt = tl; tl->par = r;
  172.           r = tl;
  173.           t = tl->lt;
  174.           comp = <T>CMP(key, t->item);
  175.         }
  176.       }
  177.     }
  178.   }
  179.   if ((r->lt = t->rt) != 0) r->lt->par = r;
  180.   if ((l->rt = t->lt) != 0) l->rt->par = l;
  181.   if ((t->lt = dummy->rt) != 0) t->lt->par = t;
  182.   if ((t->rt = dummy->lt) != 0) t->rt->par = t;
  183.   t->par = 0;
  184.   root = t;
  185.   return (comp == 0) ? Pix(t) : 0;
  186. }
  187.  
  188.  
  189. Pix <T>SplayPQ::enq(<T&> item)
  190. {
  191.   ++count;
  192.   <T>SplayNode* newnode = new <T>SplayNode(item);
  193.   <T>SplayNode* t = root;
  194.   if (t == 0)
  195.   {
  196.     root = newnode;
  197.     return Pix(root);
  198.   }
  199.  
  200.   int comp = <T>CMP(item, t->item);
  201.  
  202.   <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
  203.   <T>SplayNode* l = dummy;
  204.   <T>SplayNode* r = dummy;
  205.   dummy->rt = dummy->lt = dummy->par = 0;
  206.   
  207.   int done = 0;
  208.   while (!done)
  209.   {
  210.     if (comp >= 0)
  211.     {
  212.       <T>SplayNode* tr = t->rt;
  213.       if (tr == 0)
  214.       {
  215.         tr = newnode;
  216.         comp = 0; done = 1;
  217.       }
  218.       else
  219.         comp = <T>CMP(item, tr->item);
  220.         
  221.       if (comp <= 0)
  222.       {
  223.         l->rt = t; t->par = l;
  224.         l = t;
  225.         t = tr;
  226.       }
  227.       else 
  228.       {
  229.         <T>SplayNode* trr = tr->rt;
  230.         if (trr == 0)
  231.         {
  232.           trr =  newnode;
  233.           comp = 0; done = 1;
  234.         }
  235.         else
  236.           comp = <T>CMP(item, trr->item);
  237.  
  238.         if ((t->rt = tr->lt) != 0) t->rt->par = t;
  239.         tr->lt = t; t->par = tr;
  240.         l->rt = tr; tr->par = l;
  241.         l = tr;
  242.         t = trr;
  243.       }
  244.     }
  245.     else
  246.     {
  247.       <T>SplayNode* tl = t->lt;
  248.       if (tl == 0)
  249.       {
  250.         tl = newnode;
  251.         comp = 0; done = 1;
  252.       }
  253.       else
  254.         comp = <T>CMP(item, tl->item);
  255.  
  256.       if (comp >= 0)
  257.       {
  258.         r->lt = t; t->par = r;
  259.         r = t;
  260.         t = tl;
  261.       }
  262.       else
  263.       {
  264.         <T>SplayNode* tll = tl->lt;
  265.         if (tll == 0)
  266.         {
  267.           tll = newnode;
  268.           comp = 0; done = 1;
  269.         }
  270.         else
  271.           comp = <T>CMP(item, tll->item);
  272.  
  273.         if ((t->lt = tl->rt) != 0) t->lt->par = t;
  274.         tl->rt = t; t->par = tl;
  275.         r->lt = tl; tl->par = r;
  276.         r = tl;
  277.         t = tll;
  278.       }
  279.     }
  280.   }
  281.   if ((r->lt = t->rt) != 0) r->lt->par = r;
  282.   if ((l->rt = t->lt) != 0) l->rt->par = l;
  283.   if ((t->lt = dummy->rt) != 0) t->lt->par = t;
  284.   if ((t->rt = dummy->lt) != 0) t->rt->par = t;
  285.   t->par = 0;
  286.   root = t;
  287.   return Pix(root);
  288. }
  289.  
  290.  
  291. void <T>SplayPQ::del(Pix pix)
  292. {
  293.   <T>SplayNode* t = (<T>SplayNode*)pix;
  294.   if (t == 0) return;
  295.  
  296.   <T>SplayNode* p = t->par;
  297.  
  298.   --count;
  299.   if (t->rt == 0)
  300.   {
  301.     if (t == root)
  302.     {
  303.       if ((root = t->lt) != 0) root->par = 0;
  304.     }
  305.     else if (t == p->lt)
  306.     {
  307.       if ((p->lt = t->lt) != 0) p->lt->par = p;
  308.     }
  309.     else
  310.       if ((p->rt = t->lt) != 0) p->rt->par = p;
  311.   }
  312.   else
  313.   {
  314.     <T>SplayNode* r = t->rt;
  315.     <T>SplayNode* l = r->lt;
  316.     for(;;)
  317.     {
  318.       if (l == 0)
  319.       {
  320.         if (t == root)
  321.         {
  322.           root = r;
  323.           r->par = 0;
  324.         }
  325.         else if (t == p->lt) 
  326.         {
  327.           p->lt = r;
  328.           r->par = p;
  329.         }
  330.         else
  331.         {
  332.           p->rt = r;
  333.           r->par = p;
  334.         }
  335.         if ((r->lt = t->lt) != 0) r->lt->par = r;
  336.         break;
  337.       }
  338.       else
  339.       {
  340.         if ((r->lt = l->rt) != 0) r->lt->par = r;
  341.         l->rt = r; r->par = l;
  342.         r = l;
  343.         l = l->lt;
  344.       }
  345.     }
  346.   }
  347.   delete t;
  348. }
  349.  
  350. <T>& <T>SplayPQ::front()
  351. {
  352.   if (root == 0)
  353.     error ("min: empty tree\n");
  354. //  else 
  355.   {
  356.     <T>SplayNode* t = root;
  357.     <T>SplayNode* l = root->lt;
  358.     for(;;)
  359.     {
  360.       if (l == 0)
  361.       {
  362.         root = t;
  363.         root->par = 0;
  364.         return root->item;
  365.       }
  366.       else
  367.       {
  368.         if ((t->lt = l->rt) != 0) t->lt->par = t;
  369.         l->rt = t; t->par = l;
  370.         t = l;
  371.         l = l->lt;
  372.       }
  373.     }
  374.   }
  375. }
  376.  
  377. void <T>SplayPQ::del_front()
  378. {
  379.   if (root != 0)
  380.   {
  381.     --count;
  382.     <T>SplayNode* t = root;
  383.     <T>SplayNode* l = root->lt;
  384.     if (l == 0)
  385.     {
  386.       if ((root = t->rt) != 0) root->par = 0;
  387.       delete t;
  388.     }
  389.     else
  390.     {
  391.       for(;;)
  392.       {
  393.         <T>SplayNode* ll = l->lt;
  394.         if (ll == 0)
  395.         {
  396.           if ((t->lt = l->rt) != 0) t->lt->par = t;
  397.           delete l;
  398.           break;
  399.         }
  400.         else
  401.         {
  402.           <T>SplayNode* lll = ll->lt;
  403.           if (lll == 0)
  404.           {
  405.             if ((l->lt = ll->rt) != 0) l->lt->par = l;
  406.             delete ll;
  407.             break;
  408.           }
  409.           else
  410.           {
  411.             t->lt = ll; ll->par = t;
  412.             if ((l->lt = ll->rt) != 0) l->lt->par = l;
  413.             ll->rt = l; l->par = ll;
  414.             t = ll;
  415.             l = lll;
  416.           }
  417.         }
  418.       }
  419.     }
  420.   }
  421. }
  422.  
  423. <T> <T>SplayPQ::deq()
  424. {
  425.   if (root == 0)
  426.     error("deq: empty tree");
  427. //  else
  428.   {
  429.     --count;
  430.     <T>SplayNode* t = root;
  431.     <T>SplayNode* l = root->lt;
  432.     if (l == 0)
  433.     {
  434.       if ((root = t->rt) != 0) root->par = 0;
  435.       <T> res = t->item;
  436.       delete t;
  437.       return res;
  438.     }
  439.     else
  440.     {
  441.       for(;;)
  442.       {
  443.         <T>SplayNode* ll = l->lt;
  444.         if (ll == 0)
  445.         {
  446.           if ((t->lt = l->rt) != 0) t->lt->par = t;
  447.           <T> res = l->item;
  448.           delete l;
  449.           return res;
  450.         }
  451.         else
  452.         {
  453.           <T>SplayNode* lll = ll->lt;
  454.           if (lll == 0)
  455.           {
  456.             if ((l->lt = ll->rt) != 0) l->lt->par = l;
  457.             <T> res = ll->item;
  458.             delete ll;
  459.             return res;
  460.           }
  461.           else
  462.           {
  463.             t->lt = ll; ll->par = t;
  464.             if ((l->lt = ll->rt) != 0) l->lt->par = l;
  465.             ll->rt = l; l->par = ll;
  466.             t = ll;
  467.             l = lll;
  468.           }
  469.         }
  470.       }
  471.     }
  472.   }
  473. }
  474.  
  475.  
  476. void <T>SplayPQ::_kill(<T>SplayNode* t)
  477. {
  478.   if (t != 0)
  479.   {
  480.     _kill(t->lt);
  481.     _kill(t->rt);
  482.     delete t;
  483.   }
  484. }
  485.  
  486.  
  487. <T>SplayNode* <T>SplayPQ::_copy(<T>SplayNode* t)
  488. {
  489.   if (t != 0)
  490.   {
  491.     <T>SplayNode* l = _copy(t->lt);
  492.     <T>SplayNode* r = _copy(t->rt);
  493.     <T>SplayNode* x = new <T>SplayNode(t->item, l, r);
  494.     if (l != 0) l->par = x;
  495.     if (r != 0) r->par = x;
  496.     return x;
  497.   }
  498.   else 
  499.     return 0;
  500. }
  501.  
  502. int <T>SplayPQ::OK()
  503. {
  504.   int v = 1;
  505.   if (root == 0) 
  506.     v = count == 0;
  507.   else
  508.   {
  509.     int n = 1;
  510.     <T>SplayNode* trail = leftmost();
  511.     <T>SplayNode* t = succ(trail);
  512.     while (t != 0)
  513.     {
  514.       ++n;
  515.       v &= <T>CMP(trail->item, t->item) < 0;
  516.       trail = t;
  517.       t = succ(t);
  518.     }
  519.     v &= n == count;
  520.   }
  521.   if (!v) error("invariant failure");
  522.   return v;
  523. }
  524.