home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.2 (Developer) / NS_dev_3.2.iso / NextDeveloper / Headers / g++ / gen / AVLSet.ccP < prev    next >
Text File  |  1993-06-29  |  17KB  |  881 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>.AVLSet.h"
  24. #include <stdlib.h>
  25.  
  26.  
  27. /*
  28.  constants & inlines for maintaining balance & thread status in tree nodes
  29. */
  30.  
  31. #define AVLBALANCEMASK    3
  32. #define AVLBALANCED       0
  33. #define AVLLEFTHEAVY      1
  34. #define AVLRIGHTHEAVY     2
  35.  
  36. #define LTHREADBIT        4
  37. #define RTHREADBIT        8
  38.  
  39.  
  40. static inline int bf(<T>AVLNode* t)
  41. {
  42.   return t->stat & AVLBALANCEMASK;
  43. }
  44.  
  45. static inline void set_bf(<T>AVLNode* t, int b)
  46. {
  47.   t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK);
  48. }
  49.  
  50.  
  51. static inline int rthread(<T>AVLNode* t)
  52. {
  53.   return t->stat & RTHREADBIT;
  54. }
  55.  
  56. static inline void set_rthread(<T>AVLNode* t, int b)
  57. {
  58.   if (b)
  59.     t->stat |= RTHREADBIT;
  60.   else
  61.     t->stat &= ~RTHREADBIT;
  62. }
  63.  
  64. static inline int lthread(<T>AVLNode* t)
  65. {
  66.   return t->stat & LTHREADBIT;
  67. }
  68.  
  69. static inline void set_lthread(<T>AVLNode* t, int b)
  70. {
  71.   if (b)
  72.     t->stat |= LTHREADBIT;
  73.   else
  74.     t->stat &= ~LTHREADBIT;
  75. }
  76.  
  77. /*
  78.  traversal primitives
  79. */
  80.  
  81.  
  82. <T>AVLNode* <T>AVLSet::leftmost()
  83. {
  84.   <T>AVLNode* t = root;
  85.   if (t != 0) while (t->lt != 0) t = t->lt;
  86.   return t;
  87. }
  88.  
  89. <T>AVLNode* <T>AVLSet::rightmost()
  90. {
  91.   <T>AVLNode* t = root;
  92.   if (t != 0) while (t->rt != 0) t = t->rt;
  93.   return t;
  94. }
  95.  
  96. <T>AVLNode* <T>AVLSet::succ(<T>AVLNode* t)
  97. {
  98.   <T>AVLNode* r = t->rt;
  99.   if (!rthread(t)) while (!lthread(r)) r = r->lt;
  100.   return r;
  101. }
  102.  
  103. <T>AVLNode* <T>AVLSet::pred(<T>AVLNode* t)
  104. {
  105.   <T>AVLNode* l = t->lt;
  106.   if (!lthread(t)) while (!rthread(l)) l = l->rt;
  107.   return l;
  108. }
  109.  
  110.  
  111. Pix <T>AVLSet::seek(<T&> key)
  112. {
  113.   <T>AVLNode* t = root;
  114.   if (t == 0)
  115.     return 0;
  116.   for (;;)
  117.   {
  118.     int cmp = <T>CMP(key, t->item);
  119.     if (cmp == 0)
  120.       return Pix(t);
  121.     else if (cmp < 0)
  122.     {
  123.       if (lthread(t))
  124.         return 0;
  125.       else
  126.         t = t->lt;
  127.     }
  128.     else if (rthread(t))
  129.       return 0;
  130.     else
  131.       t = t->rt;
  132.   }
  133. }
  134.  
  135.  
  136. /*
  137.  The combination of threads and AVL bits make adding & deleting
  138.  interesting, but very awkward.
  139.  
  140.  We use the following statics to avoid passing them around recursively
  141. */
  142.  
  143. static int _need_rebalancing;   // to send back balance info from rec. calls
  144. static <T>*   _target_item;     // add/del_item target
  145. static <T>AVLNode* _found_node; // returned added/deleted node
  146. static int    _already_found;   // for deletion subcases
  147.  
  148. static <T>AVLNode** _hold_nodes;       // used for rebuilding trees
  149. static int  _max_hold_index;              // # elements-1 in _hold_nodes
  150.  
  151.  
  152. void <T>AVLSet:: _add(<T>AVLNode*& t)
  153. {
  154.   int cmp = <T>CMP(*_target_item, t->item);
  155.   if (cmp == 0)
  156.   {
  157.     _found_node = t;
  158.     return;
  159.   }
  160.   else if (cmp < 0)
  161.   {
  162.     if (lthread(t))
  163.     {
  164.       ++count;
  165.       _found_node = new <T>AVLNode(*_target_item);
  166.       set_lthread(_found_node, 1);
  167.       set_rthread(_found_node, 1);
  168.       _found_node->lt = t->lt;
  169.       _found_node->rt = t;
  170.       t->lt = _found_node;
  171.       set_lthread(t, 0);
  172.       _need_rebalancing = 1;
  173.     }
  174.     else
  175.       _add(t->lt);
  176.     if (_need_rebalancing)
  177.     {
  178.       switch(bf(t))
  179.       {
  180.       case AVLRIGHTHEAVY:
  181.         set_bf(t, AVLBALANCED);
  182.         _need_rebalancing = 0;
  183.         return;
  184.       case AVLBALANCED:
  185.         set_bf(t, AVLLEFTHEAVY);
  186.         return;
  187.       case AVLLEFTHEAVY:
  188.         <T>AVLNode* l = t->lt;
  189.         if (bf(l) == AVLLEFTHEAVY)
  190.         {
  191.           if (rthread(l))
  192.             t->lt = l;
  193.           else
  194.             t->lt = l->rt;
  195.           set_lthread(t, rthread(l));
  196.           l->rt = t;
  197.           set_rthread(l, 0);
  198.           set_bf(t, AVLBALANCED);
  199.           set_bf(l, AVLBALANCED);
  200.           t = l;
  201.           _need_rebalancing = 0;
  202.         }
  203.         else
  204.         {
  205.           <T>AVLNode* r = l->rt;
  206.           set_rthread(l, lthread(r));
  207.           if (lthread(r))
  208.             l->rt = r;
  209.           else
  210.             l->rt = r->lt;
  211.           r->lt = l;
  212.           set_lthread(r, 0);
  213.           set_lthread(t, rthread(r));
  214.           if (rthread(r))
  215.             t->lt = r;
  216.           else
  217.             t->lt = r->rt;
  218.           r->rt = t;
  219.           set_rthread(r, 0);
  220.           if (bf(r) == AVLLEFTHEAVY)
  221.             set_bf(t, AVLRIGHTHEAVY);
  222.           else
  223.             set_bf(t, AVLBALANCED);
  224.           if (bf(r) == AVLRIGHTHEAVY)
  225.             set_bf(l, AVLLEFTHEAVY);
  226.           else
  227.             set_bf(l, AVLBALANCED);
  228.           set_bf(r, AVLBALANCED);
  229.           t = r;
  230.           _need_rebalancing = 0;
  231.           return;
  232.         }
  233.       }
  234.     }
  235.   }
  236.   else
  237.   {
  238.     if (rthread(t))
  239.     {
  240.       ++count;
  241.       _found_node = new <T>AVLNode(*_target_item);
  242.       set_rthread(t, 0);
  243.       set_lthread(_found_node, 1);
  244.       set_rthread(_found_node, 1);
  245.       _found_node->lt = t;
  246.       _found_node->rt = t->rt;
  247.       t->rt = _found_node;
  248.       _need_rebalancing = 1;
  249.     }
  250.     else
  251.       _add(t->rt);
  252.     if (_need_rebalancing)
  253.     {
  254.       switch(bf(t))
  255.       {
  256.       case AVLLEFTHEAVY:
  257.         set_bf(t, AVLBALANCED);
  258.         _need_rebalancing = 0;
  259.         return;
  260.       case AVLBALANCED:
  261.         set_bf(t, AVLRIGHTHEAVY);
  262.         return;
  263.       case AVLRIGHTHEAVY:
  264.         <T>AVLNode* r = t->rt;
  265.         if (bf(r) == AVLRIGHTHEAVY)
  266.         {
  267.           if (lthread(r))
  268.             t->rt = r;
  269.           else
  270.             t->rt = r->lt;
  271.           set_rthread(t, lthread(r));
  272.           r->lt = t;
  273.           set_lthread(r, 0);
  274.           set_bf(t, AVLBALANCED);
  275.           set_bf(r, AVLBALANCED);
  276.           t = r;
  277.           _need_rebalancing = 0;
  278.         }
  279.         else
  280.         {
  281.           <T>AVLNode* l = r->lt;
  282.           set_lthread(r, rthread(l));
  283.           if (rthread(l))
  284.             r->lt = l;
  285.           else
  286.             r->lt = l->rt;
  287.           l->rt = r;
  288.           set_rthread(l, 0);
  289.           set_rthread(t, lthread(l));
  290.           if (lthread(l))
  291.             t->rt = l;
  292.           else
  293.             t->rt = l->lt;
  294.           l->lt = t;
  295.           set_lthread(l, 0);
  296.           if (bf(l) == AVLRIGHTHEAVY)
  297.             set_bf(t, AVLLEFTHEAVY);
  298.           else
  299.             set_bf(t, AVLBALANCED);
  300.           if (bf(l) == AVLLEFTHEAVY)
  301.             set_bf(r, AVLRIGHTHEAVY);
  302.           else
  303.             set_bf(r, AVLBALANCED);
  304.           set_bf(l, AVLBALANCED);
  305.           t = l;
  306.           _need_rebalancing = 0;
  307.           return;
  308.         }
  309.       }
  310.     }
  311.   }
  312. }
  313.  
  314.     
  315. Pix <T>AVLSet::add(<T&> item)
  316. {
  317.   if (root == 0)
  318.   {
  319.     ++count;
  320.     root = new <T>AVLNode(item);
  321.     set_rthread(root, 1);
  322.     set_lthread(root, 1);
  323.     return Pix(root);
  324.   }
  325.   else
  326.   {
  327.     _target_item = &item;
  328.     _need_rebalancing = 0;
  329.     _add(root);
  330.     return Pix(_found_node);
  331.   }
  332. }
  333.  
  334.  
  335. void <T>AVLSet::_del(<T>AVLNode* par, <T>AVLNode*& t)
  336. {
  337.   int comp;
  338.   if (_already_found)
  339.   {
  340.     if (rthread(t))
  341.       comp = 0;
  342.     else
  343.       comp = 1;
  344.   }
  345.   else 
  346.     comp = <T>CMP(*_target_item, t->item);
  347.   if (comp == 0)
  348.   {
  349.     if (lthread(t) && rthread(t))
  350.     {
  351.       _found_node = t;
  352.       if (t == par->lt)
  353.       {
  354.         set_lthread(par, 1);
  355.         par->lt = t->lt;
  356.       }
  357.       else
  358.       {
  359.         set_rthread(par, 1);
  360.         par->rt = t->rt;
  361.       }
  362.       _need_rebalancing = 1;
  363.       return;
  364.     }
  365.     else if (lthread(t))
  366.     {
  367.       _found_node = t;
  368.       <T>AVLNode* s = succ(t);
  369.       if (s != 0 && lthread(s))
  370.         s->lt = t->lt;
  371.       t = t->rt;
  372.       _need_rebalancing = 1;
  373.       return;
  374.     }
  375.     else if (rthread(t))
  376.     {
  377.       _found_node = t;
  378.       <T>AVLNode* p = pred(t);
  379.       if (p != 0 && rthread(p))
  380.         p->rt = t->rt;
  381.       t = t->lt;
  382.       _need_rebalancing = 1;
  383.       return;
  384.     }
  385.     else                        // replace item & find someone deletable
  386.     {
  387.       <T>AVLNode* p = pred(t);
  388.       t->item = p->item;
  389.       _already_found = 1;
  390.       comp = -1;                // fall through below to left
  391.     }
  392.   }
  393.  
  394.   if (comp < 0)
  395.   {
  396.     if (lthread(t))
  397.       return;
  398.     _del(t, t->lt);
  399.     if (!_need_rebalancing)
  400.       return;
  401.     switch (bf(t))
  402.     {
  403.     case AVLLEFTHEAVY:
  404.       set_bf(t, AVLBALANCED);
  405.       return;
  406.     case AVLBALANCED:
  407.       set_bf(t, AVLRIGHTHEAVY);
  408.       _need_rebalancing = 0;
  409.       return;
  410.     case AVLRIGHTHEAVY:
  411.       <T>AVLNode* r = t->rt;
  412.       switch (bf(r))
  413.       {
  414.       case AVLBALANCED:
  415.         if (lthread(r))
  416.           t->rt = r;
  417.         else
  418.           t->rt = r->lt;
  419.         set_rthread(t, lthread(r));
  420.         r->lt = t;
  421.         set_lthread(r, 0);
  422.         set_bf(t, AVLRIGHTHEAVY);
  423.         set_bf(r, AVLLEFTHEAVY);
  424.         _need_rebalancing = 0;
  425.         t = r;
  426.         return;
  427.       case AVLRIGHTHEAVY:
  428.         if (lthread(r))
  429.           t->rt = r;
  430.         else
  431.           t->rt = r->lt;
  432.         set_rthread(t, lthread(r));
  433.         r->lt = t;
  434.         set_lthread(r, 0);
  435.         set_bf(t, AVLBALANCED);
  436.         set_bf(r, AVLBALANCED);
  437.         t = r;
  438.         return;
  439.       case AVLLEFTHEAVY:
  440.         <T>AVLNode* l = r->lt;
  441.         set_lthread(r, rthread(l));
  442.         if (rthread(l))
  443.           r->lt = l;
  444.         else
  445.           r->lt = l->rt;
  446.         l->rt = r;
  447.         set_rthread(l, 0);
  448.         set_rthread(t, lthread(l));
  449.         if (lthread(l))
  450.           t->rt = l;
  451.         else
  452.           t->rt = l->lt;
  453.         l->lt = t;
  454.         set_lthread(l, 0);
  455.         if (bf(l) == AVLRIGHTHEAVY)
  456.           set_bf(t, AVLLEFTHEAVY);
  457.         else
  458.           set_bf(t, AVLBALANCED);
  459.         if (bf(l) == AVLLEFTHEAVY)
  460.           set_bf(r, AVLRIGHTHEAVY);
  461.         else
  462.           set_bf(r, AVLBALANCED);
  463.         set_bf(l, AVLBALANCED);
  464.         t = l;
  465.         return;
  466.       }
  467.     }
  468.   }
  469.   else
  470.   {
  471.     if (rthread(t))
  472.       return;
  473.     _del(t, t->rt);
  474.     if (!_need_rebalancing)
  475.       return;
  476.     switch (bf(t))
  477.     {
  478.     case AVLRIGHTHEAVY:
  479.       set_bf(t, AVLBALANCED);
  480.       return;
  481.     case AVLBALANCED:
  482.       set_bf(t, AVLLEFTHEAVY);
  483.       _need_rebalancing = 0;
  484.       return;
  485.     case AVLLEFTHEAVY:
  486.       <T>AVLNode* l = t->lt;
  487.       switch (bf(l))
  488.       {
  489.       case AVLBALANCED:
  490.         if (rthread(l))
  491.           t->lt = l;
  492.         else
  493.           t->lt = l->rt;
  494.         set_lthread(t, rthread(l));
  495.         l->rt = t;
  496.         set_rthread(l, 0);
  497.         set_bf(t, AVLLEFTHEAVY);
  498.         set_bf(l, AVLRIGHTHEAVY);
  499.         _need_rebalancing = 0;
  500.         t = l;
  501.         return;
  502.       case AVLLEFTHEAVY:
  503.         if (rthread(l))
  504.           t->lt = l;
  505.         else
  506.           t->lt = l->rt;
  507.         set_lthread(t, rthread(l));
  508.         l->rt = t;
  509.         set_rthread(l, 0);
  510.         set_bf(t, AVLBALANCED);
  511.         set_bf(l, AVLBALANCED);
  512.         t = l;
  513.         return;
  514.       case AVLRIGHTHEAVY:
  515.         <T>AVLNode* r = l->rt;
  516.         set_rthread(l, lthread(r));
  517.         if (lthread(r))
  518.           l->rt = r;
  519.         else
  520.           l->rt = r->lt;
  521.         r->lt = l;
  522.         set_lthread(r, 0);
  523.         set_lthread(t, rthread(r));
  524.         if (rthread(r))
  525.           t->lt = r;
  526.         else
  527.           t->lt = r->rt;
  528.         r->rt = t;
  529.         set_rthread(r, 0);
  530.         if (bf(r) == AVLLEFTHEAVY)
  531.           set_bf(t, AVLRIGHTHEAVY);
  532.         else
  533.           set_bf(t, AVLBALANCED);
  534.         if (bf(r) == AVLRIGHTHEAVY)
  535.           set_bf(l, AVLLEFTHEAVY);
  536.         else
  537.           set_bf(l, AVLBALANCED);
  538.         set_bf(r, AVLBALANCED);
  539.         t = r;
  540.         return;
  541.       }
  542.     }
  543.   }
  544. }
  545.  
  546.         
  547.  
  548. void <T>AVLSet::del(<T&> item)
  549. {
  550.   if (root == 0) return;
  551.   _need_rebalancing = 0;
  552.   _already_found = 0;
  553.   _found_node = 0;
  554.   _target_item = &item;
  555.   _del(root, root);
  556.   if (_found_node)
  557.   {
  558.     delete(_found_node);
  559.     if (--count == 0)
  560.       root = 0;
  561.   }
  562. }
  563.  
  564. // build an ordered array of pointers to tree nodes back into a tree
  565. // we know that at least one element exists
  566.  
  567. static <T>AVLNode* _do_treeify(int lo, int hi, int& h)
  568. {
  569.   int lh, rh;
  570.   int mid = (lo + hi) / 2;
  571.   <T>AVLNode* t = _hold_nodes[mid];
  572.   if (lo > mid - 1)
  573.   {
  574.     set_lthread(t, 1);
  575.     if (mid == 0)
  576.       t->lt = 0;
  577.     else
  578.       t->lt = _hold_nodes[mid-1];
  579.     lh = 0;
  580.   }
  581.   else
  582.   {
  583.     set_lthread(t, 0);
  584.     t->lt = _do_treeify(lo, mid-1, lh);
  585.   }
  586.   if (hi < mid + 1)
  587.   {
  588.     set_rthread(t, 1);
  589.     if (mid == _max_hold_index)
  590.       t->rt = 0;
  591.     else
  592.       t->rt = _hold_nodes[mid+1];
  593.     rh = 0;
  594.   }
  595.   else 
  596.   {
  597.     set_rthread(t, 0);
  598.     t->rt = _do_treeify(mid+1, hi, rh);
  599.   }
  600.   if (lh == rh)
  601.   {
  602.     set_bf(t, AVLBALANCED);
  603.     h = lh + 1;
  604.   }
  605.   else if (lh == rh - 1)
  606.   {
  607.     set_bf(t, AVLRIGHTHEAVY);
  608.     h = rh + 1;
  609.   }
  610.   else if (rh == lh - 1)
  611.   {
  612.     set_bf(t, AVLLEFTHEAVY);
  613.     h = lh + 1;
  614.   }
  615.   else                          // can't happen
  616.     abort();
  617.  
  618.   return t;
  619. }
  620.  
  621. static <T>AVLNode* _treeify(int n)
  622. {
  623.   <T>AVLNode* t;
  624.   if (n == 0)
  625.     t = 0;
  626.   else
  627.   {
  628.     int b;
  629.     _max_hold_index = n-1;
  630.     t = _do_treeify(0, _max_hold_index, b);
  631.   }
  632.   delete _hold_nodes;
  633.   return t;
  634. }
  635.  
  636.  
  637. void <T>AVLSet::_kill(<T>AVLNode* t)
  638. {
  639.   if (t != 0)
  640.   {
  641.     if (!lthread(t)) _kill(t->lt);
  642.     if (!rthread(t)) _kill(t->rt);
  643.     delete t;
  644.   }
  645. }
  646.  
  647.  
  648. <T>AVLSet::<T>AVLSet(<T>AVLSet& b)
  649. {
  650.   if ((count = b.count) == 0)
  651.   {
  652.     root = 0;
  653.   }
  654.   else
  655.   {
  656.     _hold_nodes = new <T>AVLNodePtr [count];
  657.     <T>AVLNode* t = b.leftmost();
  658.     int i = 0;
  659.     while (t != 0)
  660.     {
  661.       _hold_nodes[i++] = new <T>AVLNode(t->item);
  662.       t = b.succ(t);
  663.     }
  664.     root = _treeify(count);
  665.   }
  666. }
  667.  
  668.  
  669. int <T>AVLSet::operator == (<T>AVLSet& y)
  670. {
  671.   if (count != y.count)
  672.     return 0;
  673.   else
  674.   {
  675.     <T>AVLNode* t = leftmost();
  676.     <T>AVLNode* u = y.leftmost();
  677.     for (;;)
  678.     {
  679.       if (t == 0)
  680.         return 1;
  681.       else if (!(<T>EQ(t->item, u->item)))
  682.         return 0;
  683.       else
  684.       {
  685.         t = succ(t);
  686.         u = y.succ(u);
  687.       }
  688.     }
  689.   }
  690. }
  691.  
  692. int <T>AVLSet::operator <= (<T>AVLSet& y)
  693. {
  694.   if (count > y.count)
  695.     return 0;
  696.   else
  697.   {
  698.     <T>AVLNode* t = leftmost();
  699.     <T>AVLNode* u = y.leftmost();
  700.     for (;;)
  701.     {
  702.       if (t == 0)
  703.         return 1;
  704.       else if (u == 0)
  705.         return 0;
  706.       int cmp = <T>CMP(t->item, u->item);
  707.       if (cmp == 0)
  708.       {
  709.         t = succ(t);
  710.         u = y.succ(u);
  711.       }
  712.       else if (cmp < 0)
  713.         return 0;
  714.       else
  715.         u = y.succ(u);
  716.     }
  717.   }
  718. }
  719.  
  720. void <T>AVLSet::operator |=(<T>AVLSet& y)
  721. {
  722.   <T>AVLNode* t = leftmost();
  723.   <T>AVLNode* u = y.leftmost();
  724.   int rsize = count + y.count;
  725.   _hold_nodes = new <T>AVLNodePtr [rsize];
  726.   int k = 0;
  727.   for (;;)
  728.   {
  729.     if (t == 0)
  730.     {
  731.       while (u != 0)
  732.       {
  733.         _hold_nodes[k++] = new <T>AVLNode(u->item);
  734.         u = y.succ(u);
  735.       }
  736.       break;
  737.     }
  738.     else if (u == 0)
  739.     {
  740.       while (t != 0)
  741.       {
  742.         _hold_nodes[k++] = t;
  743.         t = succ(t);
  744.       }
  745.       break;
  746.     }
  747.     int cmp = <T>CMP(t->item, u->item);
  748.     if (cmp == 0)
  749.     {
  750.       _hold_nodes[k++] = t;
  751.       t = succ(t);
  752.       u = y.succ(u);
  753.     }
  754.     else if (cmp < 0)
  755.     {
  756.       _hold_nodes[k++] = t;
  757.       t = succ(t);
  758.     }
  759.     else
  760.     {
  761.       _hold_nodes[k++] = new <T>AVLNode(u->item);
  762.       u = y.succ(u);
  763.     }
  764.   }
  765.   root = _treeify(k);
  766.   count = k;
  767. }
  768.  
  769. void <T>AVLSet::operator &= (<T>AVLSet& y)
  770. {
  771.   <T>AVLNode* t = leftmost();
  772.   <T>AVLNode* u = y.leftmost();
  773.   int rsize = (count < y.count)? count : y.count;
  774.   _hold_nodes = new <T>AVLNodePtr [rsize];
  775.   int k = 0;
  776.   for (;;)
  777.   {
  778.     if (t == 0)
  779.       break;
  780.     if (u == 0)
  781.     {
  782.       while (t != 0)
  783.       {
  784.         <T>AVLNode* tmp = succ(t);
  785.         delete t;
  786.         t = tmp;
  787.       }
  788.       break;
  789.     }
  790.     int cmp = <T>CMP(t->item, u->item);
  791.     if (cmp == 0)
  792.     {
  793.       _hold_nodes[k++] = t;
  794.       t = succ(t);
  795.       u = y.succ(u);
  796.     }
  797.     else if (cmp < 0)
  798.     {
  799.       <T>AVLNode* tmp = succ(t);
  800.       delete t;
  801.       t = tmp;
  802.     }
  803.     else
  804.       u = y.succ(u);
  805.   }
  806.   root = _treeify(k);
  807.   count = k;
  808. }
  809.  
  810.  
  811. void <T>AVLSet::operator -=(<T>AVLSet& y)
  812. {
  813.   <T>AVLNode* t = leftmost();
  814.   <T>AVLNode* u = y.leftmost();
  815.   int rsize = count;
  816.   _hold_nodes = new <T>AVLNodePtr [rsize];
  817.   int k = 0;
  818.   for (;;)
  819.   {
  820.     if (t == 0)
  821.       break;
  822.     else if (u == 0)
  823.     {
  824.       while (t != 0)
  825.       {
  826.         _hold_nodes[k++] = t;
  827.         t = succ(t);
  828.       }
  829.       break;
  830.     }
  831.     int cmp = <T>CMP(t->item, u->item);
  832.     if (cmp == 0)
  833.     {
  834.       <T>AVLNode* tmp = succ(t);
  835.       delete t;
  836.       t = tmp;
  837.       u = y.succ(u);
  838.     }
  839.     else if (cmp < 0)
  840.     {
  841.       _hold_nodes[k++] = t;
  842.       t = succ(t);
  843.     }
  844.     else
  845.       u = y.succ(u);
  846.   }
  847.   root = _treeify(k);
  848.   count = k;
  849. }
  850.  
  851. int <T>AVLSet::owns(Pix i)
  852. {
  853.   if (i == 0) return 0;
  854.   for (<T>AVLNode* t = leftmost(); t != 0; t = succ(t)) 
  855.     if (Pix(t) == i) return 1;
  856.   return 0;
  857. }
  858.  
  859. int <T>AVLSet::OK()
  860. {
  861.   int v = 1;
  862.   if (root == 0) 
  863.     v = count == 0;
  864.   else
  865.   {
  866.     int n = 1;
  867.     <T>AVLNode* trail = leftmost();
  868.     <T>AVLNode* t = succ(trail);
  869.     while (t != 0)
  870.     {
  871.       ++n;
  872.       v &= <T>CMP(trail->item, t->item) < 0;
  873.       trail = t;
  874.       t = succ(t);
  875.     }
  876.     v &= n == count;
  877.   }
  878.   if (!v) error("invariant failure");
  879.   return v;
  880. }
  881.