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