home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer) / NeXT_Developer-3.3.iso / NextDeveloper / Headers / g++ / gen / BSTSet.ccP < prev    next >
Encoding:
Text File  |  1995-02-06  |  7.1 KB  |  379 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>.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.   int comp;
  120.   for (;;)
  121.   {
  122.     if (t == 0)
  123.     {
  124.       ++count;
  125.       t = new <T>BSTNode(item);
  126.       if (comp > 0)
  127.         p->lt = t;
  128.       else
  129.         p->rt = t;
  130.       t->par = p;
  131.       return Pix(t);
  132.     }
  133.     p = t;
  134.     comp = <T>CMP(t->item, item);
  135.     if (comp == 0)
  136.       return Pix(t);
  137.     else if (comp > 0)
  138.       t = t->lt;
  139.     else
  140.       t = t->rt;
  141.   }
  142. }
  143.  
  144.  
  145. void <T>BSTSet::del(<T&> key)
  146. {
  147.   <T>BSTNode* t = root;
  148.   <T>BSTNode* p = root;
  149.   int comp;
  150.   for (;;)
  151.   {
  152.     if (t == 0)
  153.       return;
  154.     comp = <T>CMP(key, t->item);
  155.     if (comp == 0)
  156.     {
  157.       --count;
  158.       <T>BSTNode* repl;
  159.       if (t->lt == 0)
  160.         repl = t->rt;
  161.       else if (t->rt == 0)
  162.         repl = t->lt;
  163.       else
  164.       {
  165.         <T>BSTNode* prepl = t;
  166.         repl = t->lt;
  167.         while (repl->rt != 0)
  168.         {
  169.           prepl = repl;
  170.           repl = repl->rt;
  171.         }
  172.         if (prepl != t)
  173.         {
  174.           prepl->rt = repl->lt;
  175.           if (prepl->rt != 0) prepl->rt->par = prepl;
  176.           repl->lt = t->lt;
  177.           if (repl->lt != 0) repl->lt->par = repl;
  178.         }
  179.         repl->rt = t->rt;
  180.         if (repl->rt != 0) repl->rt->par = repl;
  181.       }
  182.       if (t == root)
  183.       {
  184.         root = repl;
  185.         if (repl != 0) repl->par = 0;
  186.       }
  187.       else
  188.       {
  189.         if (t == p->lt)
  190.           p->lt = repl;
  191.         else
  192.           p->rt = repl;
  193.         if (repl != 0) repl->par = p;
  194.       }
  195.       delete t;
  196.       return;
  197.     }
  198.     p = t;
  199.     if (comp < 0)
  200.       t = t->lt;
  201.     else
  202.       t = t->rt;
  203.   }
  204. }
  205.  
  206.  
  207. void <T>BSTSet::_kill(<T>BSTNode* t)
  208. {
  209.   if (t != 0)
  210.   {
  211.     _kill(t->lt);
  212.     _kill(t->rt);
  213.     delete t;
  214.   }
  215. }
  216.  
  217. <T>BSTNode* <T>BSTSet::_copy(<T>BSTNode* t)
  218. {
  219.   if (t == 0)
  220.     return 0;
  221.   else
  222.   {
  223.     <T>BSTNode* u = new <T>BSTNode(t->item, _copy(t->lt), _copy(t->rt));
  224.     if (u->lt != 0) u->lt->par = u;
  225.     if (u->rt != 0) u->rt->par = u;
  226.     return u;
  227.   }
  228. }
  229.  
  230.  
  231. int <T>BSTSet::operator == (<T>BSTSet& y)
  232. {
  233.   if (count != y.count)
  234.     return 0;
  235.   else
  236.   {
  237.     <T>BSTNode* t = leftmost();
  238.     <T>BSTNode* u = y.leftmost();
  239.     for (;;)
  240.     {
  241.       if (t == 0)
  242.         return 1;
  243.       else if (!<T>EQ(t->item, u->item))
  244.         return 0;
  245.       else
  246.       {
  247.         t = succ(t);
  248.         u = y.succ(u);
  249.       }
  250.     }
  251.   }
  252. }
  253.  
  254. int <T>BSTSet::operator <= (<T>BSTSet& y)
  255. {
  256.   if (count > y.count)
  257.     return 0;
  258.   else
  259.   {
  260.     <T>BSTNode* t = leftmost();
  261.     <T>BSTNode* u = y.leftmost();
  262.     for (;;)
  263.     {
  264.       if (t == 0)
  265.         return 1;
  266.       else if (u == 0)
  267.         return 0;
  268.       int cmp = <T>CMP(t->item, u->item);
  269.       if (cmp == 0)
  270.       {
  271.         t = succ(t);
  272.         u = y.succ(u);
  273.       }
  274.       else if (cmp < 0)
  275.         return 0;
  276.       else
  277.         u = y.succ(u);
  278.     }
  279.   }
  280. }
  281.  
  282.  
  283. // linear-time, zero space overhead binary tree rebalancing from
  284. // Stout & Warren, ``Tree rebalancing in linear space and time''
  285. // CACM, Sept, 1986, p902.
  286.  
  287.  
  288. void <T>BSTSet::balance()
  289. {
  290.   if (count <= 2) return; // don't bother -- 
  291.                           // also we assume non-null root, below
  292.  
  293.   // make re-attaching the root easy via trickery
  294.  
  295.   struct _fake_node { _fake_node *lt, *rt, *par; } fake_root;
  296.  
  297.   fake_root.rt = (_fake_node*)root; 
  298.   fake_root.par = 0;
  299.   <T>BSTNode* pseudo_root = (<T>BSTNode*)&fake_root;
  300.  
  301.   // phase 1: tree-to-vine
  302.  
  303.   <T>BSTNode* vine_tail = pseudo_root;
  304.   <T>BSTNode* remainder = root;
  305.  
  306.   while (remainder != 0)
  307.   {
  308.     if (remainder->lt == 0)
  309.     {
  310.       vine_tail = remainder;
  311.       remainder = remainder->rt;
  312.     }
  313.     else
  314.     {
  315.       <T>BSTNode* tmp = remainder->lt;
  316.       remainder->lt = tmp->rt;
  317.       if (remainder->lt != 0) remainder->lt->par = remainder;
  318.       tmp->rt = remainder;
  319.       remainder->par = tmp;
  320.       vine_tail->rt = remainder = tmp;
  321.     }
  322.   }
  323.  
  324.   // phase 2: vine-to-tree
  325.   
  326.   // Uses the slightly simpler version adapted from
  327.   // Day ``Balancing a binary tree'' Computer Journal, Nov. 1976,
  328.   // since it's not generally important whether the `stray' leaves are
  329.   // on the left or on the right.
  330.  
  331.   unsigned int spines = count - 1;
  332.   while (spines > 1)
  333.   {
  334.     int compressions = spines >> 1; // compress every other node
  335.     spines -= compressions + 1;     // halve for next time
  336.  
  337.     <T>BSTNode* scanner = pseudo_root;
  338.     while (compressions-- > 0)
  339.     {
  340.       <T>BSTNode* child = scanner->rt;
  341.       <T>BSTNode* grandchild = child->rt;
  342.       scanner->rt = grandchild;
  343.       grandchild->par = scanner;
  344.       child->rt = grandchild->lt;
  345.       if (child->rt != 0) child->rt->par = child;
  346.       grandchild->lt = child;
  347.       child->par = grandchild;
  348.       scanner = grandchild;
  349.     }
  350.   }
  351.  
  352.   root = pseudo_root->rt;
  353.   root->par = 0;
  354. }
  355.  
  356.  
  357. int <T>BSTSet::OK()
  358. {
  359.   int v = 1;
  360.   if (root == 0) 
  361.     v = count == 0;
  362.   else
  363.   {
  364.     int n = 1;
  365.     <T>BSTNode* trail = leftmost();
  366.     <T>BSTNode* t = succ(trail);
  367.     while (t != 0)
  368.     {
  369.       ++n;
  370.       v &= <T>CMP(trail->item, t->item) < 0;
  371.       trail = t;
  372.       t = succ(t);
  373.     }
  374.     v &= n == count;
  375.   }
  376.   if (!v) error("invariant failure");
  377.   return v;
  378. }
  379.