home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.2 (Developer) / NS_dev_3.2.iso / NextDeveloper / Headers / g++ / gen / SplaySet.ccP < prev    next >
Text File  |  1993-06-29  |  9KB  |  500 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, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. #ifdef __GNUG__
  20. #pragma implementation
  21. #endif
  22. #include <stream.h>
  23. #include "<T>.SplaySet.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>SplaySet::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>SplaySet::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>SplaySet::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>SplaySet::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>SplaySet::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.  
  190. Pix <T>SplaySet::add(<T&> item)
  191. {
  192.   <T>SplayNode* t = root;
  193.   if (t == 0)
  194.   {
  195.     ++count;
  196.     root = new <T>SplayNode(item);
  197.     return Pix(root);
  198.   }
  199.   int comp = <T>CMP(item, t->item);
  200.   if (comp == 0)
  201.     return Pix(t);
  202.  
  203.   <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
  204.   <T>SplayNode* l = dummy;
  205.   <T>SplayNode* r = dummy;
  206.   dummy->rt = dummy->lt = dummy->par = 0;
  207.  
  208.   while (comp != 0)
  209.   {
  210.     if (comp > 0)
  211.     {
  212.       <T>SplayNode* tr = t->rt;
  213.       if (tr == 0)
  214.       {
  215.         ++count;
  216.         tr = new <T>SplayNode(item);
  217.         comp = 0;
  218.       }
  219.       else
  220.         comp = <T>CMP(item, tr->item);
  221.         
  222.       if (comp <= 0)
  223.       {
  224.         l->rt = t; t->par = l;
  225.         l = t;
  226.         t = tr;
  227.       }
  228.       else 
  229.       {
  230.         <T>SplayNode* trr = tr->rt;
  231.         if (trr == 0)
  232.         {
  233.           ++count;
  234.           trr =  new <T>SplayNode(item);
  235.           comp = 0;
  236.         }
  237.         else
  238.           comp = <T>CMP(item, trr->item);
  239.  
  240.         if ((t->rt = tr->lt) != 0) t->rt->par = t;
  241.         tr->lt = t; t->par = tr;
  242.         l->rt = tr; tr->par = l;
  243.         l = tr;
  244.         t = trr;
  245.       }
  246.     }
  247.     else
  248.     {
  249.       <T>SplayNode* tl = t->lt;
  250.       if (tl == 0)
  251.       {
  252.         ++count;
  253.         tl = new <T>SplayNode(item);
  254.         comp = 0;
  255.       }
  256.       else
  257.         comp = <T>CMP(item, tl->item);
  258.  
  259.       if (comp >= 0)
  260.       {
  261.         r->lt = t; t->par = r;
  262.         r = t;
  263.         t = tl;
  264.       }
  265.       else
  266.       {
  267.         <T>SplayNode* tll = tl->lt;
  268.         if (tll == 0)
  269.         {
  270.           ++count;
  271.           tll = new <T>SplayNode(item);
  272.           comp = 0;
  273.         }
  274.         else
  275.           comp = <T>CMP(item, tll->item);
  276.  
  277.         if ((t->lt = tl->rt) != 0) t->lt->par = t;
  278.         tl->rt = t; t->par = tl;
  279.         r->lt = tl; tl->par = r;
  280.         r = tl;
  281.         t = tll;
  282.       }
  283.     }
  284.   }
  285.   if ((r->lt = t->rt) != 0) r->lt->par = r;
  286.   if ((l->rt = t->lt) != 0) l->rt->par = l;
  287.   if ((t->lt = dummy->rt) != 0) t->lt->par = t;
  288.   if ((t->rt = dummy->lt) != 0) t->rt->par = t;
  289.   t->par = 0;
  290.   root = t;
  291.   return Pix(root);
  292. }
  293.  
  294. void <T>SplaySet::del(<T&> key)
  295. {
  296.   <T>SplayNode* t = (<T>SplayNode*)(seek(key));
  297.   if (t == 0) return;
  298.  
  299.   <T>SplayNode* p = t->par;
  300.  
  301.   --count;
  302.   if (t->rt == 0)
  303.   {
  304.     if (t == root)
  305.     {
  306.       if ((root = t->lt) != 0) root->par = 0;
  307.     }
  308.     else if (t == p->lt)
  309.     {
  310.       if ((p->lt = t->lt) != 0) p->lt->par = p;
  311.     }
  312.     else
  313.       if ((p->rt = t->lt) != 0) p->rt->par = p;
  314.   }
  315.   else
  316.   {
  317.     <T>SplayNode* r = t->rt;
  318.     <T>SplayNode* l = r->lt;
  319.     for(;;)
  320.     {
  321.       if (l == 0)
  322.       {
  323.         if (t == root)
  324.         {
  325.           root = r;
  326.           r->par = 0;
  327.         }
  328.         else if (t == p->lt) 
  329.         {
  330.           p->lt = r;
  331.           r->par = p;
  332.         }
  333.         else
  334.         {
  335.           p->rt = r;
  336.           r->par = p;
  337.         }
  338.         if ((r->lt = t->lt) != 0) r->lt->par = r;
  339.         break;
  340.       }
  341.       else
  342.       {
  343.         if ((r->lt = l->rt) != 0) r->lt->par = r;
  344.         l->rt = r; r->par = l;
  345.         r = l;
  346.         l = l->lt;
  347.       }
  348.     }
  349.   }
  350.   delete t;
  351. }
  352.  
  353.  
  354. void <T>SplaySet::_kill(<T>SplayNode* t)
  355. {
  356.   if (t != 0)
  357.   {
  358.     _kill(t->lt);
  359.     _kill(t->rt);
  360.     delete t;
  361.   }
  362. }
  363.  
  364.  
  365. <T>SplayNode* <T>SplaySet::_copy(<T>SplayNode* t)
  366. {
  367.   if (t != 0)
  368.   {
  369.     <T>SplayNode* l = _copy(t->lt);
  370.     <T>SplayNode* r = _copy(t->rt);
  371.     <T>SplayNode* x = new <T>SplayNode(t->item, l, r);
  372.     if (l != 0) l->par = x;
  373.     if (r != 0) r->par = x;
  374.     return x;
  375.   }
  376.   else 
  377.     return 0;
  378. }
  379.  
  380. /* relationals */
  381.  
  382. int <T>SplaySet::operator == (<T>SplaySet& y)
  383. {
  384.   if (count != y.count)
  385.     return 0;
  386.   else
  387.   {
  388.     <T>SplayNode* t = leftmost();
  389.     <T>SplayNode* u = y.leftmost();
  390.     for (;;)
  391.     {
  392.       if (t == 0)
  393.         return 1;
  394.       else if (!<T>EQ(t->item, u->item))
  395.         return 0;
  396.       else
  397.       {
  398.         t = succ(t);
  399.         u = y.succ(u);
  400.       }
  401.     }
  402.   }
  403. }
  404.  
  405. int <T>SplaySet::operator <= (<T>SplaySet& y)
  406. {
  407.   if (count > y.count)
  408.     return 0;
  409.   else
  410.   {
  411.     <T>SplayNode* t = leftmost();
  412.     <T>SplayNode* u = y.leftmost();
  413.     for (;;)
  414.     {
  415.       if (t == 0)
  416.         return 1;
  417.       else if (u == 0)
  418.         return 0;
  419.       int cmp = <T>CMP(t->item, u->item);
  420.       if (cmp == 0)
  421.       {
  422.         t = succ(t);
  423.         u = y.succ(u);
  424.       }
  425.       else if (cmp < 0)
  426.         return 0;
  427.       else
  428.         u = y.succ(u);
  429.     }
  430.   }
  431. }
  432.  
  433.  
  434. void <T>SplaySet::operator |=(<T>SplaySet& y)
  435. {
  436.   if (&y == this) return;
  437.   <T>SplayNode* u = y.leftmost();
  438.   while (u != 0)
  439.   {
  440.     add(u->item);
  441.     u = y.succ(u);
  442.   }
  443. }
  444.  
  445. void <T>SplaySet::operator &= (<T>SplaySet& y)
  446. {
  447.   if (y.count == 0)
  448.     clear();
  449.   else if (&y != this && count != 0)
  450.   {
  451.     <T>SplayNode* t = leftmost();
  452.     while (t != 0)
  453.     {
  454.       <T>SplayNode* s = succ(t);
  455.       if (y.seek(t->item) == 0) del(t->item);
  456.       t = s;
  457.     }
  458.   }
  459. }
  460.  
  461.  
  462. void <T>SplaySet::operator -=(<T>SplaySet& y)
  463. {
  464.   if (&y == this)
  465.     clear();
  466.   else if (y.count != 0)
  467.   {
  468.     <T>SplayNode* t = leftmost();
  469.     while (t != 0)
  470.     {
  471.       <T>SplayNode* s = succ(t);
  472.       if (y.seek(t->item) != 0) del(t->item);
  473.       t = s;
  474.     }
  475.   }
  476. }
  477.  
  478. int <T>SplaySet::OK()
  479. {
  480.   int v = 1;
  481.   if (root == 0) 
  482.     v = count == 0;
  483.   else
  484.   {
  485.     int n = 1;
  486.     <T>SplayNode* trail = leftmost();
  487.     <T>SplayNode* t = succ(trail);
  488.     while (t != 0)
  489.     {
  490.       ++n;
  491.       v &= <T>CMP(trail->item, t->item) < 0;
  492.       trail = t;
  493.       t = succ(t);
  494.     }
  495.     v &= n == count;
  496.   }
  497.   if (!v) error("invariant failure");
  498.   return v;
  499. }
  500.