home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / programming / libg_ / libgpp / !libgpp / gen / ccp / SplayBag < prev    next >
Text File  |  1995-06-16  |  8KB  |  446 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>.SplayBag.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>SplayBag::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>SplayBag::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>SplayBag::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>SplayBag::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.  
  108. Pix <T>SplayBag::seek(<T&> key, Pix i)
  109. {
  110.   if (root == 0) return 0;
  111.  
  112.   <T>SplayNode* t = (<T>SplayNode*) i;
  113.   if (t != 0)
  114.   {
  115.     int cmp = <T>CMP(key, t->item);
  116.     if (cmp == 0)
  117.     {
  118.       t = succ(t);
  119.       if (t != 0 && <T>EQ(key, t->item))
  120.         return Pix(t);
  121.       else
  122.         return 0;
  123.     }
  124.     else if (cmp < 0)
  125.       return 0;
  126.   }
  127.  
  128.   t = root;
  129.   int comp = <T>CMP(key, t->item);
  130.   if (comp == 0)
  131.     return Pix(t);
  132.  
  133.   <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
  134.   <T>SplayNode* l = dummy;
  135.   <T>SplayNode* r = dummy;
  136.   dummy->rt = dummy->lt = dummy->par = 0;
  137.  
  138.   while (comp != 0)
  139.   {
  140.     if (comp > 0)
  141.     {
  142.       <T>SplayNode* tr = t->rt;
  143.       if (tr == 0)
  144.         break;
  145.       else
  146.       {
  147.         comp = <T>CMP(key, tr->item);
  148.         if (comp <= 0 || tr->rt == 0)
  149.         {
  150.           l->rt = t; t->par = l;
  151.           l = t;
  152.           t = tr;
  153.           if (comp >= 0)
  154.             break;
  155.         }
  156.         else
  157.         {
  158.           if ((t->rt = tr->lt) != 0) t->rt->par = t;
  159.           tr->lt = t; t->par = tr;
  160.           l->rt = tr; tr->par = l;
  161.           l = tr;
  162.           t = tr->rt;
  163.           comp = <T>CMP(key, t->item);
  164.         }
  165.       }
  166.     }
  167.     else
  168.     {
  169.       <T>SplayNode* tl = t->lt;
  170.       if (tl == 0)
  171.         break;
  172.       else
  173.       {
  174.         comp = <T>CMP(key, tl->item);
  175.         if (comp >= 0 || tl->lt == 0)
  176.         {
  177.           r->lt = t; t->par = r;
  178.           r = t;
  179.           t = tl;
  180.           if (comp <= 0)
  181.             break;
  182.         }
  183.         else
  184.         {
  185.           if ((t->lt = tl->rt) != 0) t->lt->par = t;
  186.           tl->rt = t; t->par = tl;
  187.           r->lt = tl; tl->par = r;
  188.           r = tl;
  189.           t = tl->lt;
  190.           comp = <T>CMP(key, t->item);
  191.         }
  192.       }
  193.     }
  194.   }
  195.   if ((r->lt = t->rt) != 0) r->lt->par = r;
  196.   if ((l->rt = t->lt) != 0) l->rt->par = l;
  197.   if ((t->lt = dummy->rt) != 0) t->lt->par = t;
  198.   if ((t->rt = dummy->lt) != 0) t->rt->par = t;
  199.   t->par = 0;
  200.   root = t;
  201.   if (comp != 0)
  202.     return 0;
  203.   else
  204.   {
  205.     l = pred(t);
  206.     while (l != 0 && <T>EQ(l->item, key)) { t = l; l = pred(l); }
  207.     return Pix(t);
  208.   }
  209. }
  210.  
  211. int <T>SplayBag::nof(<T&> item)
  212. {
  213.   int n = 0;
  214.   <T>SplayNode* t = (<T>SplayNode*)(seek(item));
  215.   if (t != 0)
  216.   {
  217.     do
  218.     {
  219.       ++n;
  220.       t = succ(t);
  221.     } while (t != 0 && <T>EQ(item, t->item));
  222.   }
  223.   return n;
  224. }
  225.  
  226. Pix <T>SplayBag::add(<T&> item)
  227. {
  228.   ++count;
  229.   <T>SplayNode* newnode = new <T>SplayNode(item);
  230.   <T>SplayNode* t = root;
  231.   if (t == 0)
  232.   {
  233.     root = newnode;
  234.     return Pix(root);
  235.   }
  236.  
  237.   int comp = <T>CMP(item, t->item);
  238.  
  239.   <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
  240.   <T>SplayNode* l = dummy;
  241.   <T>SplayNode* r = dummy;
  242.   dummy->rt = dummy->lt = dummy->par = 0;
  243.   
  244.   int done = 0;
  245.   while (!done)
  246.   {
  247.     if (comp >= 0)
  248.     {
  249.       <T>SplayNode* tr = t->rt;
  250.       if (tr == 0)
  251.       {
  252.         tr = newnode;
  253.         comp = 0; done = 1;
  254.       }
  255.       else
  256.         comp = <T>CMP(item, tr->item);
  257.         
  258.       if (comp <= 0)
  259.       {
  260.         l->rt = t; t->par = l;
  261.         l = t;
  262.         t = tr;
  263.       }
  264.       else 
  265.       {
  266.         <T>SplayNode* trr = tr->rt;
  267.         if (trr == 0)
  268.         {
  269.           trr =  newnode;
  270.           comp = 0; done = 1;
  271.         }
  272.         else
  273.           comp = <T>CMP(item, trr->item);
  274.  
  275.         if ((t->rt = tr->lt) != 0) t->rt->par = t;
  276.         tr->lt = t; t->par = tr;
  277.         l->rt = tr; tr->par = l;
  278.         l = tr;
  279.         t = trr;
  280.       }
  281.     }
  282.     else
  283.     {
  284.       <T>SplayNode* tl = t->lt;
  285.       if (tl == 0)
  286.       {
  287.         tl = newnode;
  288.         comp = 0; done = 1;
  289.       }
  290.       else
  291.         comp = <T>CMP(item, tl->item);
  292.  
  293.       if (comp >= 0)
  294.       {
  295.         r->lt = t; t->par = r;
  296.         r = t;
  297.         t = tl;
  298.       }
  299.       else
  300.       {
  301.         <T>SplayNode* tll = tl->lt;
  302.         if (tll == 0)
  303.         {
  304.           tll = newnode;
  305.           comp = 0; done = 1;
  306.         }
  307.         else
  308.           comp = <T>CMP(item, tll->item);
  309.  
  310.         if ((t->lt = tl->rt) != 0) t->lt->par = t;
  311.         tl->rt = t; t->par = tl;
  312.         r->lt = tl; tl->par = r;
  313.         r = tl;
  314.         t = tll;
  315.       }
  316.     }
  317.   }
  318.   if ((r->lt = t->rt) != 0) r->lt->par = r;
  319.   if ((l->rt = t->lt) != 0) l->rt->par = l;
  320.   if ((t->lt = dummy->rt) != 0) t->lt->par = t;
  321.   if ((t->rt = dummy->lt) != 0) t->rt->par = t;
  322.   t->par = 0;
  323.   root = t;
  324.   return Pix(root);
  325. }
  326.  
  327. void <T>SplayBag::_del(<T>SplayNode* t)
  328. {
  329.   if (t == 0) return;
  330.  
  331.   <T>SplayNode* p = t->par;
  332.  
  333.   --count;
  334.   if (t->rt == 0)
  335.   {
  336.     if (t == root)
  337.     {
  338.       if ((root = t->lt) != 0) root->par = 0;
  339.     }
  340.     else if (t == p->lt)
  341.     {
  342.       if ((p->lt = t->lt) != 0) p->lt->par = p;
  343.     }
  344.     else
  345.       if ((p->rt = t->lt) != 0) p->rt->par = p;
  346.   }
  347.   else
  348.   {
  349.     <T>SplayNode* r = t->rt;
  350.     <T>SplayNode* l = r->lt;
  351.     for(;;)
  352.     {
  353.       if (l == 0)
  354.       {
  355.         if (t == root)
  356.         {
  357.           root = r;
  358.           r->par = 0;
  359.         }
  360.         else if (t == p->lt) 
  361.         {
  362.           p->lt = r;
  363.           r->par = p;
  364.         }
  365.         else
  366.         {
  367.           p->rt = r;
  368.           r->par = p;
  369.         }
  370.         if ((r->lt = t->lt) != 0) r->lt->par = r;
  371.         break;
  372.       }
  373.       else
  374.       {
  375.         if ((r->lt = l->rt) != 0) r->lt->par = r;
  376.         l->rt = r; r->par = l;
  377.         r = l;
  378.         l = l->lt;
  379.       }
  380.     }
  381.   }
  382.   delete t;
  383. }
  384.  
  385.  
  386. void <T>SplayBag::remove(<T&> key)
  387. {
  388.   <T>SplayNode* t = (<T>SplayNode*)(seek(key));
  389.   while (t != 0)
  390.   {
  391.     _del(t);
  392.     t = (<T>SplayNode*)(seek(key));
  393.   }
  394. }
  395.  
  396.  
  397. void <T>SplayBag::_kill(<T>SplayNode* t)
  398. {
  399.   if (t != 0)
  400.   {
  401.     _kill(t->lt);
  402.     _kill(t->rt);
  403.     delete t;
  404.   }
  405. }
  406.  
  407.  
  408. <T>SplayNode* <T>SplayBag::_copy(<T>SplayNode* t)
  409. {
  410.   if (t != 0)
  411.   {
  412.     <T>SplayNode* l = _copy(t->lt);
  413.     <T>SplayNode* r = _copy(t->rt);
  414.     <T>SplayNode* x = new <T>SplayNode(t->item, l, r);
  415.     if (l != 0) l->par = x;
  416.     if (r != 0) r->par = x;
  417.     return x;
  418.   }
  419.   else 
  420.     return 0;
  421. }
  422.  
  423. int <T>SplayBag::OK()
  424. {
  425.   int v = 1;
  426.   if (root == 0) 
  427.     v = count == 0;
  428.   else
  429.   {
  430.     int n = 1;
  431.     <T>SplayNode* trail = leftmost();
  432.     <T>SplayNode* t = succ(trail);
  433.     while (t != 0)
  434.     {
  435.       ++n;
  436.       v &= <T>CMP(trail->item, t->item) <= 0;
  437.       trail = t;
  438.       t = succ(t);
  439.     }
  440.     v &= n == count;
  441.   }
  442.   if (!v) error("invariant failure");
  443.   return v;
  444. }
  445.  
  446.