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 / AVLSet.ccP < prev    next >
Text File  |  1996-10-12  |  18KB  |  893 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>.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.     {
  189.         <T>AVLNode* l = t->lt;
  190.         if (bf(l) == AVLLEFTHEAVY)
  191.         {
  192.           if (rthread(l))
  193.             t->lt = l;
  194.           else
  195.             t->lt = l->rt;
  196.           set_lthread(t, rthread(l));
  197.           l->rt = t;
  198.           set_rthread(l, 0);
  199.           set_bf(t, AVLBALANCED);
  200.           set_bf(l, AVLBALANCED);
  201.           t = l;
  202.           _need_rebalancing = 0;
  203.         }
  204.         else
  205.         {
  206.           <T>AVLNode* r = l->rt;
  207.           set_rthread(l, lthread(r));
  208.           if (lthread(r))
  209.             l->rt = r;
  210.           else
  211.             l->rt = r->lt;
  212.           r->lt = l;
  213.           set_lthread(r, 0);
  214.           set_lthread(t, rthread(r));
  215.           if (rthread(r))
  216.             t->lt = r;
  217.           else
  218.             t->lt = r->rt;
  219.           r->rt = t;
  220.           set_rthread(r, 0);
  221.           if (bf(r) == AVLLEFTHEAVY)
  222.             set_bf(t, AVLRIGHTHEAVY);
  223.           else
  224.             set_bf(t, AVLBALANCED);
  225.           if (bf(r) == AVLRIGHTHEAVY)
  226.             set_bf(l, AVLLEFTHEAVY);
  227.           else
  228.             set_bf(l, AVLBALANCED);
  229.           set_bf(r, AVLBALANCED);
  230.           t = r;
  231.           _need_rebalancing = 0;
  232.           return;
  233.         }
  234.     }
  235.       }
  236.     }
  237.   }
  238.   else
  239.   {
  240.     if (rthread(t))
  241.     {
  242.       ++count;
  243.       _found_node = new <T>AVLNode(*_target_item);
  244.       set_rthread(t, 0);
  245.       set_lthread(_found_node, 1);
  246.       set_rthread(_found_node, 1);
  247.       _found_node->lt = t;
  248.       _found_node->rt = t->rt;
  249.       t->rt = _found_node;
  250.       _need_rebalancing = 1;
  251.     }
  252.     else
  253.       _add(t->rt);
  254.     if (_need_rebalancing)
  255.     {
  256.       switch(bf(t))
  257.       {
  258.       case AVLLEFTHEAVY:
  259.         set_bf(t, AVLBALANCED);
  260.         _need_rebalancing = 0;
  261.         return;
  262.       case AVLBALANCED:
  263.         set_bf(t, AVLRIGHTHEAVY);
  264.         return;
  265.       case AVLRIGHTHEAVY:
  266.     {
  267.         <T>AVLNode* r = t->rt;
  268.         if (bf(r) == AVLRIGHTHEAVY)
  269.         {
  270.           if (lthread(r))
  271.             t->rt = r;
  272.           else
  273.             t->rt = r->lt;
  274.           set_rthread(t, lthread(r));
  275.           r->lt = t;
  276.           set_lthread(r, 0);
  277.           set_bf(t, AVLBALANCED);
  278.           set_bf(r, AVLBALANCED);
  279.           t = r;
  280.           _need_rebalancing = 0;
  281.         }
  282.         else
  283.         {
  284.           <T>AVLNode* l = r->lt;
  285.           set_lthread(r, rthread(l));
  286.           if (rthread(l))
  287.             r->lt = l;
  288.           else
  289.             r->lt = l->rt;
  290.           l->rt = r;
  291.           set_rthread(l, 0);
  292.           set_rthread(t, lthread(l));
  293.           if (lthread(l))
  294.             t->rt = l;
  295.           else
  296.             t->rt = l->lt;
  297.           l->lt = t;
  298.           set_lthread(l, 0);
  299.           if (bf(l) == AVLRIGHTHEAVY)
  300.             set_bf(t, AVLLEFTHEAVY);
  301.           else
  302.             set_bf(t, AVLBALANCED);
  303.           if (bf(l) == AVLLEFTHEAVY)
  304.             set_bf(r, AVLRIGHTHEAVY);
  305.           else
  306.             set_bf(r, AVLBALANCED);
  307.           set_bf(l, AVLBALANCED);
  308.           t = l;
  309.           _need_rebalancing = 0;
  310.           return;
  311.         }
  312.     }
  313.       }
  314.     }
  315.   }
  316. }
  317.  
  318.     
  319. Pix <T>AVLSet::add(<T&> item)
  320. {
  321.   if (root == 0)
  322.   {
  323.     ++count;
  324.     root = new <T>AVLNode(item);
  325.     set_rthread(root, 1);
  326.     set_lthread(root, 1);
  327.     return Pix(root);
  328.   }
  329.   else
  330.   {
  331.     _target_item = &item;
  332.     _need_rebalancing = 0;
  333.     _add(root);
  334.     return Pix(_found_node);
  335.   }
  336. }
  337.  
  338.  
  339. void <T>AVLSet::_del(<T>AVLNode* par, <T>AVLNode*& t)
  340. {
  341.   int comp;
  342.   if (_already_found)
  343.   {
  344.     if (rthread(t))
  345.       comp = 0;
  346.     else
  347.       comp = 1;
  348.   }
  349.   else 
  350.     comp = <T>CMP(*_target_item, t->item);
  351.   if (comp == 0)
  352.   {
  353.     if (lthread(t) && rthread(t))
  354.     {
  355.       _found_node = t;
  356.       if (t == par->lt)
  357.       {
  358.         set_lthread(par, 1);
  359.         par->lt = t->lt;
  360.       }
  361.       else
  362.       {
  363.         set_rthread(par, 1);
  364.         par->rt = t->rt;
  365.       }
  366.       _need_rebalancing = 1;
  367.       return;
  368.     }
  369.     else if (lthread(t))
  370.     {
  371.       _found_node = t;
  372.       <T>AVLNode* s = succ(t);
  373.       if (s != 0 && lthread(s))
  374.         s->lt = t->lt;
  375.       t = t->rt;
  376.       _need_rebalancing = 1;
  377.       return;
  378.     }
  379.     else if (rthread(t))
  380.     {
  381.       _found_node = t;
  382.       <T>AVLNode* p = pred(t);
  383.       if (p != 0 && rthread(p))
  384.         p->rt = t->rt;
  385.       t = t->lt;
  386.       _need_rebalancing = 1;
  387.       return;
  388.     }
  389.     else                        // replace item & find someone deletable
  390.     {
  391.       <T>AVLNode* p = pred(t);
  392.       t->item = p->item;
  393.       _already_found = 1;
  394.       comp = -1;                // fall through below to left
  395.     }
  396.   }
  397.  
  398.   if (comp < 0)
  399.   {
  400.     if (lthread(t))
  401.       return;
  402.     _del(t, t->lt);
  403.     if (!_need_rebalancing)
  404.       return;
  405.     switch (bf(t))
  406.     {
  407.     case AVLLEFTHEAVY:
  408.       set_bf(t, AVLBALANCED);
  409.       return;
  410.     case AVLBALANCED:
  411.       set_bf(t, AVLRIGHTHEAVY);
  412.       _need_rebalancing = 0;
  413.       return;
  414.     case AVLRIGHTHEAVY:
  415.       {
  416.       <T>AVLNode* r = t->rt;
  417.       switch (bf(r))
  418.       {
  419.       case AVLBALANCED:
  420.         if (lthread(r))
  421.           t->rt = r;
  422.         else
  423.           t->rt = r->lt;
  424.         set_rthread(t, lthread(r));
  425.         r->lt = t;
  426.         set_lthread(r, 0);
  427.         set_bf(t, AVLRIGHTHEAVY);
  428.         set_bf(r, AVLLEFTHEAVY);
  429.         _need_rebalancing = 0;
  430.         t = r;
  431.         return;
  432.       case AVLRIGHTHEAVY:
  433.         if (lthread(r))
  434.           t->rt = r;
  435.         else
  436.           t->rt = r->lt;
  437.         set_rthread(t, lthread(r));
  438.         r->lt = t;
  439.         set_lthread(r, 0);
  440.         set_bf(t, AVLBALANCED);
  441.         set_bf(r, AVLBALANCED);
  442.         t = r;
  443.         return;
  444.       case AVLLEFTHEAVY:
  445.     {
  446.         <T>AVLNode* l = r->lt;
  447.         set_lthread(r, rthread(l));
  448.         if (rthread(l))
  449.           r->lt = l;
  450.         else
  451.           r->lt = l->rt;
  452.         l->rt = r;
  453.         set_rthread(l, 0);
  454.         set_rthread(t, lthread(l));
  455.         if (lthread(l))
  456.           t->rt = l;
  457.         else
  458.           t->rt = l->lt;
  459.         l->lt = t;
  460.         set_lthread(l, 0);
  461.         if (bf(l) == AVLRIGHTHEAVY)
  462.           set_bf(t, AVLLEFTHEAVY);
  463.         else
  464.           set_bf(t, AVLBALANCED);
  465.         if (bf(l) == AVLLEFTHEAVY)
  466.           set_bf(r, AVLRIGHTHEAVY);
  467.         else
  468.           set_bf(r, AVLBALANCED);
  469.         set_bf(l, AVLBALANCED);
  470.         t = l;
  471.         return;
  472.     }
  473.       }
  474.     }
  475.     }
  476.   }
  477.   else
  478.   {
  479.     if (rthread(t))
  480.       return;
  481.     _del(t, t->rt);
  482.     if (!_need_rebalancing)
  483.       return;
  484.     switch (bf(t))
  485.     {
  486.     case AVLRIGHTHEAVY:
  487.       set_bf(t, AVLBALANCED);
  488.       return;
  489.     case AVLBALANCED:
  490.       set_bf(t, AVLLEFTHEAVY);
  491.       _need_rebalancing = 0;
  492.       return;
  493.     case AVLLEFTHEAVY:
  494.       {
  495.       <T>AVLNode* l = t->lt;
  496.       switch (bf(l))
  497.       {
  498.       case AVLBALANCED:
  499.         if (rthread(l))
  500.           t->lt = l;
  501.         else
  502.           t->lt = l->rt;
  503.         set_lthread(t, rthread(l));
  504.         l->rt = t;
  505.         set_rthread(l, 0);
  506.         set_bf(t, AVLLEFTHEAVY);
  507.         set_bf(l, AVLRIGHTHEAVY);
  508.         _need_rebalancing = 0;
  509.         t = l;
  510.         return;
  511.       case AVLLEFTHEAVY:
  512.         if (rthread(l))
  513.           t->lt = l;
  514.         else
  515.           t->lt = l->rt;
  516.         set_lthread(t, rthread(l));
  517.         l->rt = t;
  518.         set_rthread(l, 0);
  519.         set_bf(t, AVLBALANCED);
  520.         set_bf(l, AVLBALANCED);
  521.         t = l;
  522.         return;
  523.       case AVLRIGHTHEAVY:
  524.     {
  525.         <T>AVLNode* r = l->rt;
  526.         set_rthread(l, lthread(r));
  527.         if (lthread(r))
  528.           l->rt = r;
  529.         else
  530.           l->rt = r->lt;
  531.         r->lt = l;
  532.         set_lthread(r, 0);
  533.         set_lthread(t, rthread(r));
  534.         if (rthread(r))
  535.           t->lt = r;
  536.         else
  537.           t->lt = r->rt;
  538.         r->rt = t;
  539.         set_rthread(r, 0);
  540.         if (bf(r) == AVLLEFTHEAVY)
  541.           set_bf(t, AVLRIGHTHEAVY);
  542.         else
  543.           set_bf(t, AVLBALANCED);
  544.         if (bf(r) == AVLRIGHTHEAVY)
  545.           set_bf(l, AVLLEFTHEAVY);
  546.         else
  547.           set_bf(l, AVLBALANCED);
  548.         set_bf(r, AVLBALANCED);
  549.         t = r;
  550.         return;
  551.     }
  552.       }
  553.       }
  554.     }
  555.   }
  556. }
  557.  
  558.         
  559.  
  560. void <T>AVLSet::del(<T&> item)
  561. {
  562.   if (root == 0) return;
  563.   _need_rebalancing = 0;
  564.   _already_found = 0;
  565.   _found_node = 0;
  566.   _target_item = &item;
  567.   _del(root, root);
  568.   if (_found_node)
  569.   {
  570.     delete(_found_node);
  571.     if (--count == 0)
  572.       root = 0;
  573.   }
  574. }
  575.  
  576. // build an ordered array of pointers to tree nodes back into a tree
  577. // we know that at least one element exists
  578.  
  579. static <T>AVLNode* _do_treeify(int lo, int hi, int& h)
  580. {
  581.   int lh, rh;
  582.   int mid = (lo + hi) / 2;
  583.   <T>AVLNode* t = _hold_nodes[mid];
  584.   if (lo > mid - 1)
  585.   {
  586.     set_lthread(t, 1);
  587.     if (mid == 0)
  588.       t->lt = 0;
  589.     else
  590.       t->lt = _hold_nodes[mid-1];
  591.     lh = 0;
  592.   }
  593.   else
  594.   {
  595.     set_lthread(t, 0);
  596.     t->lt = _do_treeify(lo, mid-1, lh);
  597.   }
  598.   if (hi < mid + 1)
  599.   {
  600.     set_rthread(t, 1);
  601.     if (mid == _max_hold_index)
  602.       t->rt = 0;
  603.     else
  604.       t->rt = _hold_nodes[mid+1];
  605.     rh = 0;
  606.   }
  607.   else 
  608.   {
  609.     set_rthread(t, 0);
  610.     t->rt = _do_treeify(mid+1, hi, rh);
  611.   }
  612.   if (lh == rh)
  613.   {
  614.     set_bf(t, AVLBALANCED);
  615.     h = lh + 1;
  616.   }
  617.   else if (lh == rh - 1)
  618.   {
  619.     set_bf(t, AVLRIGHTHEAVY);
  620.     h = rh + 1;
  621.   }
  622.   else if (rh == lh - 1)
  623.   {
  624.     set_bf(t, AVLLEFTHEAVY);
  625.     h = lh + 1;
  626.   }
  627.   else                          // can't happen
  628.     abort();
  629.  
  630.   return t;
  631. }
  632.  
  633. static <T>AVLNode* _treeify(int n)
  634. {
  635.   <T>AVLNode* t;
  636.   if (n == 0)
  637.     t = 0;
  638.   else
  639.   {
  640.     int b;
  641.     _max_hold_index = n-1;
  642.     t = _do_treeify(0, _max_hold_index, b);
  643.   }
  644.   delete _hold_nodes;
  645.   return t;
  646. }
  647.  
  648.  
  649. void <T>AVLSet::_kill(<T>AVLNode* t)
  650. {
  651.   if (t != 0)
  652.   {
  653.     if (!lthread(t)) _kill(t->lt);
  654.     if (!rthread(t)) _kill(t->rt);
  655.     delete t;
  656.   }
  657. }
  658.  
  659.  
  660. <T>AVLSet::<T>AVLSet(<T>AVLSet& b)
  661. {
  662.   if ((count = b.count) == 0)
  663.   {
  664.     root = 0;
  665.   }
  666.   else
  667.   {
  668.     _hold_nodes = new <T>AVLNodePtr [count];
  669.     <T>AVLNode* t = b.leftmost();
  670.     int i = 0;
  671.     while (t != 0)
  672.     {
  673.       _hold_nodes[i++] = new <T>AVLNode(t->item);
  674.       t = b.succ(t);
  675.     }
  676.     root = _treeify(count);
  677.   }
  678. }
  679.  
  680.  
  681. int <T>AVLSet::operator == (<T>AVLSet& y)
  682. {
  683.   if (count != y.count)
  684.     return 0;
  685.   else
  686.   {
  687.     <T>AVLNode* t = leftmost();
  688.     <T>AVLNode* u = y.leftmost();
  689.     for (;;)
  690.     {
  691.       if (t == 0)
  692.         return 1;
  693.       else if (!(<T>EQ(t->item, u->item)))
  694.         return 0;
  695.       else
  696.       {
  697.         t = succ(t);
  698.         u = y.succ(u);
  699.       }
  700.     }
  701.   }
  702. }
  703.  
  704. int <T>AVLSet::operator <= (<T>AVLSet& y)
  705. {
  706.   if (count > y.count)
  707.     return 0;
  708.   else
  709.   {
  710.     <T>AVLNode* t = leftmost();
  711.     <T>AVLNode* u = y.leftmost();
  712.     for (;;)
  713.     {
  714.       if (t == 0)
  715.         return 1;
  716.       else if (u == 0)
  717.         return 0;
  718.       int cmp = <T>CMP(t->item, u->item);
  719.       if (cmp == 0)
  720.       {
  721.         t = succ(t);
  722.         u = y.succ(u);
  723.       }
  724.       else if (cmp < 0)
  725.         return 0;
  726.       else
  727.         u = y.succ(u);
  728.     }
  729.   }
  730. }
  731.  
  732. void <T>AVLSet::operator |=(<T>AVLSet& y)
  733. {
  734.   <T>AVLNode* t = leftmost();
  735.   <T>AVLNode* u = y.leftmost();
  736.   int rsize = count + y.count;
  737.   _hold_nodes = new <T>AVLNodePtr [rsize];
  738.   int k = 0;
  739.   for (;;)
  740.   {
  741.     if (t == 0)
  742.     {
  743.       while (u != 0)
  744.       {
  745.         _hold_nodes[k++] = new <T>AVLNode(u->item);
  746.         u = y.succ(u);
  747.       }
  748.       break;
  749.     }
  750.     else if (u == 0)
  751.     {
  752.       while (t != 0)
  753.       {
  754.         _hold_nodes[k++] = t;
  755.         t = succ(t);
  756.       }
  757.       break;
  758.     }
  759.     int cmp = <T>CMP(t->item, u->item);
  760.     if (cmp == 0)
  761.     {
  762.       _hold_nodes[k++] = t;
  763.       t = succ(t);
  764.       u = y.succ(u);
  765.     }
  766.     else if (cmp < 0)
  767.     {
  768.       _hold_nodes[k++] = t;
  769.       t = succ(t);
  770.     }
  771.     else
  772.     {
  773.       _hold_nodes[k++] = new <T>AVLNode(u->item);
  774.       u = y.succ(u);
  775.     }
  776.   }
  777.   root = _treeify(k);
  778.   count = k;
  779. }
  780.  
  781. void <T>AVLSet::operator &= (<T>AVLSet& y)
  782. {
  783.   <T>AVLNode* t = leftmost();
  784.   <T>AVLNode* u = y.leftmost();
  785.   int rsize = (count < y.count)? count : y.count;
  786.   _hold_nodes = new <T>AVLNodePtr [rsize];
  787.   int k = 0;
  788.   for (;;)
  789.   {
  790.     if (t == 0)
  791.       break;
  792.     if (u == 0)
  793.     {
  794.       while (t != 0)
  795.       {
  796.         <T>AVLNode* tmp = succ(t);
  797.         delete t;
  798.         t = tmp;
  799.       }
  800.       break;
  801.     }
  802.     int cmp = <T>CMP(t->item, u->item);
  803.     if (cmp == 0)
  804.     {
  805.       _hold_nodes[k++] = t;
  806.       t = succ(t);
  807.       u = y.succ(u);
  808.     }
  809.     else if (cmp < 0)
  810.     {
  811.       <T>AVLNode* tmp = succ(t);
  812.       delete t;
  813.       t = tmp;
  814.     }
  815.     else
  816.       u = y.succ(u);
  817.   }
  818.   root = _treeify(k);
  819.   count = k;
  820. }
  821.  
  822.  
  823. void <T>AVLSet::operator -=(<T>AVLSet& y)
  824. {
  825.   <T>AVLNode* t = leftmost();
  826.   <T>AVLNode* u = y.leftmost();
  827.   int rsize = count;
  828.   _hold_nodes = new <T>AVLNodePtr [rsize];
  829.   int k = 0;
  830.   for (;;)
  831.   {
  832.     if (t == 0)
  833.       break;
  834.     else if (u == 0)
  835.     {
  836.       while (t != 0)
  837.       {
  838.         _hold_nodes[k++] = t;
  839.         t = succ(t);
  840.       }
  841.       break;
  842.     }
  843.     int cmp = <T>CMP(t->item, u->item);
  844.     if (cmp == 0)
  845.     {
  846.       <T>AVLNode* tmp = succ(t);
  847.       delete t;
  848.       t = tmp;
  849.       u = y.succ(u);
  850.     }
  851.     else if (cmp < 0)
  852.     {
  853.       _hold_nodes[k++] = t;
  854.       t = succ(t);
  855.     }
  856.     else
  857.       u = y.succ(u);
  858.   }
  859.   root = _treeify(k);
  860.   count = k;
  861. }
  862.  
  863. int <T>AVLSet::owns(Pix i)
  864. {
  865.   if (i == 0) return 0;
  866.   for (<T>AVLNode* t = leftmost(); t != 0; t = succ(t)) 
  867.     if (Pix(t) == i) return 1;
  868.   return 0;
  869. }
  870.  
  871. int <T>AVLSet::OK()
  872. {
  873.   int v = 1;
  874.   if (root == 0) 
  875.     v = count == 0;
  876.   else
  877.   {
  878.     int n = 1;
  879.     <T>AVLNode* trail = leftmost();
  880.     <T>AVLNode* t = succ(trail);
  881.     while (t != 0)
  882.     {
  883.       ++n;
  884.       v &= <T>CMP(trail->item, t->item) < 0;
  885.       trail = t;
  886.       t = succ(t);
  887.     }
  888.     v &= n == count;
  889.   }
  890.   if (!v) error("invariant failure");
  891.   return v;
  892. }
  893.