home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / libg++-2.7.1-bin.lha / lib / g++-include / gen / BSTSet.ccP < prev    next >
Text File  |  1996-10-12  |  7KB  |  378 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>.BSTSet.h"
  24.  
  25.  
  26. /*
  27.  traversal primitives
  28. */
  29.  
  30.  
  31. <T>BSTNode* <T>BSTSet::leftmost()
  32. {
  33.   <T>BSTNode* t = root;
  34.   if (t != 0) while (t->lt != 0) t = t->lt;
  35.   return t;
  36. }
  37.  
  38. <T>BSTNode* <T>BSTSet::rightmost()
  39. {
  40.   <T>BSTNode* t = root;
  41.   if (t != 0) while (t->rt != 0) t = t->rt;
  42.   return t;
  43. }
  44.  
  45. <T>BSTNode* <T>BSTSet::succ(<T>BSTNode* t)
  46. {
  47.   if (t == 0)
  48.     return 0;
  49.   if (t->rt != 0)
  50.   {
  51.     t = t->rt;
  52.     while (t->lt != 0) t = t->lt;
  53.     return t;
  54.   }
  55.   else
  56.   {
  57.     for (;;)
  58.     {
  59.       if (t->par == 0 || t == t->par->lt)
  60.         return t->par;
  61.       else
  62.         t = t->par;
  63.     }
  64.   }
  65. }
  66.  
  67. <T>BSTNode* <T>BSTSet::pred(<T>BSTNode* t)
  68. {
  69.   if (t == 0)
  70.     return 0;
  71.   else if (t->lt != 0)
  72.   {
  73.     t = t->lt;
  74.     while (t->rt != 0) t = t->rt;
  75.     return t;
  76.   }
  77.   else
  78.   {
  79.     for (;;)
  80.     {
  81.       if (t->par == 0 || t == t->par->rt)
  82.         return t->par;
  83.       else
  84.         t = t->par;
  85.     }
  86.   }
  87. }
  88.  
  89.  
  90. Pix <T>BSTSet::seek(<T&> key)
  91. {
  92.   <T>BSTNode* t = root;
  93.   for (;;)
  94.   {
  95.     if (t == 0)
  96.       return 0;
  97.     int comp = <T>CMP(key, t->item);
  98.     if (comp == 0)
  99.       return Pix(t);
  100.     else if (comp < 0)
  101.       t = t->lt;
  102.     else
  103.       t = t->rt;
  104.   }
  105. }
  106.  
  107.  
  108. Pix <T>BSTSet::add(<T&> item)
  109. {
  110.   if (root == 0)
  111.   {
  112.     ++count;
  113.     root = new <T>BSTNode(item);
  114.     return Pix(root);
  115.   }
  116.  
  117.   <T>BSTNode* t = root;
  118.   <T>BSTNode* p = root;
  119.   for (;;)
  120.   {
  121.     int comp = <T>CMP(t->item, item);
  122.     if (comp == 0)
  123.       return Pix(t);
  124.     else if (comp > 0)
  125.       t = t->lt;
  126.     else
  127.       t = t->rt;
  128.     if (t == 0)
  129.     {
  130.       ++count;
  131.       t = new <T>BSTNode(item);
  132.       if (comp > 0)
  133.         p->lt = t;
  134.       else
  135.         p->rt = t;
  136.       t->par = p;
  137.       return Pix(t);
  138.     }
  139.     p = t;
  140.   }
  141. }
  142.  
  143.  
  144. void <T>BSTSet::del(<T&> key)
  145. {
  146.   <T>BSTNode* t = root;
  147.   <T>BSTNode* p = root;
  148.   int comp;
  149.   for (;;)
  150.   {
  151.     if (t == 0)
  152.       return;
  153.     comp = <T>CMP(key, t->item);
  154.     if (comp == 0)
  155.     {
  156.       --count;
  157.       <T>BSTNode* repl;
  158.       if (t->lt == 0)
  159.         repl = t->rt;
  160.       else if (t->rt == 0)
  161.         repl = t->lt;
  162.       else
  163.       {
  164.         <T>BSTNode* prepl = t;
  165.         repl = t->lt;
  166.         while (repl->rt != 0)
  167.         {
  168.           prepl = repl;
  169.           repl = repl->rt;
  170.         }
  171.         if (prepl != t)
  172.         {
  173.           prepl->rt = repl->lt;
  174.           if (prepl->rt != 0) prepl->rt->par = prepl;
  175.           repl->lt = t->lt;
  176.           if (repl->lt != 0) repl->lt->par = repl;
  177.         }
  178.         repl->rt = t->rt;
  179.         if (repl->rt != 0) repl->rt->par = repl;
  180.       }
  181.       if (t == root)
  182.       {
  183.         root = repl;
  184.         if (repl != 0) repl->par = 0;
  185.       }
  186.       else
  187.       {
  188.         if (t == p->lt)
  189.           p->lt = repl;
  190.         else
  191.           p->rt = repl;
  192.         if (repl != 0) repl->par = p;
  193.       }
  194.       delete t;
  195.       return;
  196.     }
  197.     p = t;
  198.     if (comp < 0)
  199.       t = t->lt;
  200.     else
  201.       t = t->rt;
  202.   }
  203. }
  204.  
  205.  
  206. void <T>BSTSet::_kill(<T>BSTNode* t)
  207. {
  208.   if (t != 0)
  209.   {
  210.     _kill(t->lt);
  211.     _kill(t->rt);
  212.     delete t;
  213.   }
  214. }
  215.  
  216. <T>BSTNode* <T>BSTSet::_copy(<T>BSTNode* t)
  217. {
  218.   if (t == 0)
  219.     return 0;
  220.   else
  221.   {
  222.     <T>BSTNode* u = new <T>BSTNode(t->item, _copy(t->lt), _copy(t->rt));
  223.     if (u->lt != 0) u->lt->par = u;
  224.     if (u->rt != 0) u->rt->par = u;
  225.     return u;
  226.   }
  227. }
  228.  
  229.  
  230. int <T>BSTSet::operator == (<T>BSTSet& y)
  231. {
  232.   if (count != y.count)
  233.     return 0;
  234.   else
  235.   {
  236.     <T>BSTNode* t = leftmost();
  237.     <T>BSTNode* u = y.leftmost();
  238.     for (;;)
  239.     {
  240.       if (t == 0)
  241.         return 1;
  242.       else if (!<T>EQ(t->item, u->item))
  243.         return 0;
  244.       else
  245.       {
  246.         t = succ(t);
  247.         u = y.succ(u);
  248.       }
  249.     }
  250.   }
  251. }
  252.  
  253. int <T>BSTSet::operator <= (<T>BSTSet& y)
  254. {
  255.   if (count > y.count)
  256.     return 0;
  257.   else
  258.   {
  259.     <T>BSTNode* t = leftmost();
  260.     <T>BSTNode* u = y.leftmost();
  261.     for (;;)
  262.     {
  263.       if (t == 0)
  264.         return 1;
  265.       else if (u == 0)
  266.         return 0;
  267.       int cmp = <T>CMP(t->item, u->item);
  268.       if (cmp == 0)
  269.       {
  270.         t = succ(t);
  271.         u = y.succ(u);
  272.       }
  273.       else if (cmp < 0)
  274.         return 0;
  275.       else
  276.         u = y.succ(u);
  277.     }
  278.   }
  279. }
  280.  
  281.  
  282. // linear-time, zero space overhead binary tree rebalancing from
  283. // Stout & Warren, ``Tree rebalancing in linear space and time''
  284. // CACM, Sept, 1986, p902.
  285.  
  286.  
  287. void <T>BSTSet::balance()
  288. {
  289.   if (count <= 2) return; // don't bother -- 
  290.                           // also we assume non-null root, below
  291.  
  292.   // make re-attaching the root easy via trickery
  293.  
  294.   struct _fake_node { _fake_node *lt, *rt, *par; } fake_root;
  295.  
  296.   fake_root.rt = (_fake_node*)root; 
  297.   fake_root.par = 0;
  298.   <T>BSTNode* pseudo_root = (<T>BSTNode*)&fake_root;
  299.  
  300.   // phase 1: tree-to-vine
  301.  
  302.   <T>BSTNode* vine_tail = pseudo_root;
  303.   <T>BSTNode* remainder = root;
  304.  
  305.   while (remainder != 0)
  306.   {
  307.     if (remainder->lt == 0)
  308.     {
  309.       vine_tail = remainder;
  310.       remainder = remainder->rt;
  311.     }
  312.     else
  313.     {
  314.       <T>BSTNode* tmp = remainder->lt;
  315.       remainder->lt = tmp->rt;
  316.       if (remainder->lt != 0) remainder->lt->par = remainder;
  317.       tmp->rt = remainder;
  318.       remainder->par = tmp;
  319.       vine_tail->rt = remainder = tmp;
  320.     }
  321.   }
  322.  
  323.   // phase 2: vine-to-tree
  324.   
  325.   // Uses the slightly simpler version adapted from
  326.   // Day ``Balancing a binary tree'' Computer Journal, Nov. 1976,
  327.   // since it's not generally important whether the `stray' leaves are
  328.   // on the left or on the right.
  329.  
  330.   unsigned int spines = count - 1;
  331.   while (spines > 1)
  332.   {
  333.     int compressions = spines >> 1; // compress every other node
  334.     spines -= compressions + 1;     // halve for next time
  335.  
  336.     <T>BSTNode* scanner = pseudo_root;
  337.     while (compressions-- > 0)
  338.     {
  339.       <T>BSTNode* child = scanner->rt;
  340.       <T>BSTNode* grandchild = child->rt;
  341.       scanner->rt = grandchild;
  342.       grandchild->par = scanner;
  343.       child->rt = grandchild->lt;
  344.       if (child->rt != 0) child->rt->par = child;
  345.       grandchild->lt = child;
  346.       child->par = grandchild;
  347.       scanner = grandchild;
  348.     }
  349.   }
  350.  
  351.   root = pseudo_root->rt;
  352.   root->par = 0;
  353. }
  354.  
  355.  
  356. int <T>BSTSet::OK()
  357. {
  358.   int v = 1;
  359.   if (root == 0) 
  360.     v = count == 0;
  361.   else
  362.   {
  363.     int n = 1;
  364.     <T>BSTNode* trail = leftmost();
  365.     <T>BSTNode* t = succ(trail);
  366.     while (t != 0)
  367.     {
  368.       ++n;
  369.       v &= <T>CMP(trail->item, t->item) < 0;
  370.       trail = t;
  371.       t = succ(t);
  372.     }
  373.     v &= n == count;
  374.   }
  375.   if (!v) error("invariant failure");
  376.   return v;
  377. }
  378.