home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.2 (Developer) / NS_dev_3.2.iso / NextDeveloper / Headers / g++ / gen / AVLMap.ccP < prev    next >
Text File  |  1993-06-29  |  13KB  |  603 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>.<C>.AVLMap.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><C>AVLNode* t)
  40. {
  41.   return t->stat & AVLBALANCEMASK;
  42. }
  43.  
  44. static inline void set_bf(<T><C>AVLNode* t, int b)
  45. {
  46.   t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK);
  47. }
  48.  
  49.  
  50. static inline int rthread(<T><C>AVLNode* t)
  51. {
  52.   return t->stat & RTHREADBIT;
  53. }
  54.  
  55. static inline void set_rthread(<T><C>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><C>AVLNode* t)
  64. {
  65.   return t->stat & LTHREADBIT;
  66. }
  67.  
  68. static inline void set_lthread(<T><C>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><C>AVLNode* <T><C>AVLMap::leftmost()
  82. {
  83.   <T><C>AVLNode* t = root;
  84.   if (t != 0) while (t->lt != 0) t = t->lt;
  85.   return t;
  86. }
  87.  
  88. <T><C>AVLNode* <T><C>AVLMap::rightmost()
  89. {
  90.   <T><C>AVLNode* t = root;
  91.   if (t != 0) while (t->rt != 0) t = t->rt;
  92.   return t;
  93. }
  94.  
  95. <T><C>AVLNode* <T><C>AVLMap::succ(<T><C>AVLNode* t)
  96. {
  97.   <T><C>AVLNode* r = t->rt;
  98.   if (!rthread(t)) while (!lthread(r)) r = r->lt;
  99.   return r;
  100. }
  101.  
  102. <T><C>AVLNode* <T><C>AVLMap::pred(<T><C>AVLNode* t)
  103. {
  104.   <T><C>AVLNode* l = t->lt;
  105.   if (!lthread(t)) while (!rthread(l)) l = l->rt;
  106.   return l;
  107. }
  108.  
  109.  
  110. Pix <T><C>AVLMap::seek(<T&> key)
  111. {
  112.   <T><C>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><C>AVLNode* _found_node; // returned added/deleted node
  145. static int    _already_found;   // for deletion subcases
  146.  
  147.  
  148. void <T><C>AVLMap:: _add(<T><C>AVLNode*& t)
  149. {
  150.   int cmp = <T>CMP(*_target_item, t->item);
  151.   if (cmp == 0)
  152.   {
  153.     _found_node = t;
  154.     return;
  155.   }
  156.   else if (cmp < 0)
  157.   {
  158.     if (lthread(t))
  159.     {
  160.       ++count;
  161.       _found_node = new <T><C>AVLNode(*_target_item, def);
  162.       set_lthread(_found_node, 1);
  163.       set_rthread(_found_node, 1);
  164.       _found_node->lt = t->lt;
  165.       _found_node->rt = t;
  166.       t->lt = _found_node;
  167.       set_lthread(t, 0);
  168.       _need_rebalancing = 1;
  169.     }
  170.     else
  171.       _add(t->lt);
  172.     if (_need_rebalancing)
  173.     {
  174.       switch(bf(t))
  175.       {
  176.       case AVLRIGHTHEAVY:
  177.         set_bf(t, AVLBALANCED);
  178.         _need_rebalancing = 0;
  179.         return;
  180.       case AVLBALANCED:
  181.         set_bf(t, AVLLEFTHEAVY);
  182.         return;
  183.       case AVLLEFTHEAVY:
  184.         <T><C>AVLNode* l = t->lt;
  185.         if (bf(l) == AVLLEFTHEAVY)
  186.         {
  187.           if (rthread(l))
  188.             t->lt = l;
  189.           else
  190.             t->lt = l->rt;
  191.           set_lthread(t, rthread(l));
  192.           l->rt = t;
  193.           set_rthread(l, 0);
  194.           set_bf(t, AVLBALANCED);
  195.           set_bf(l, AVLBALANCED);
  196.           t = l;
  197.           _need_rebalancing = 0;
  198.         }
  199.         else
  200.         {
  201.           <T><C>AVLNode* r = l->rt;
  202.           set_rthread(l, lthread(r));
  203.           if (lthread(r))
  204.             l->rt = r;
  205.           else
  206.             l->rt = r->lt;
  207.           r->lt = l;
  208.           set_lthread(r, 0);
  209.           set_lthread(t, rthread(r));
  210.           if (rthread(r))
  211.             t->lt = r;
  212.           else
  213.             t->lt = r->rt;
  214.           r->rt = t;
  215.           set_rthread(r, 0);
  216.           if (bf(r) == AVLLEFTHEAVY)
  217.             set_bf(t, AVLRIGHTHEAVY);
  218.           else
  219.             set_bf(t, AVLBALANCED);
  220.           if (bf(r) == AVLRIGHTHEAVY)
  221.             set_bf(l, AVLLEFTHEAVY);
  222.           else
  223.             set_bf(l, AVLBALANCED);
  224.           set_bf(r, AVLBALANCED);
  225.           t = r;
  226.           _need_rebalancing = 0;
  227.           return;
  228.         }
  229.       }
  230.     }
  231.   }
  232.   else
  233.   {
  234.     if (rthread(t))
  235.     {
  236.       ++count;
  237.       _found_node = new <T><C>AVLNode(*_target_item, def);
  238.       set_rthread(t, 0);
  239.       set_lthread(_found_node, 1);
  240.       set_rthread(_found_node, 1);
  241.       _found_node->lt = t;
  242.       _found_node->rt = t->rt;
  243.       t->rt = _found_node;
  244.       _need_rebalancing = 1;
  245.     }
  246.     else
  247.       _add(t->rt);
  248.     if (_need_rebalancing)
  249.     {
  250.       switch(bf(t))
  251.       {
  252.       case AVLLEFTHEAVY:
  253.         set_bf(t, AVLBALANCED);
  254.         _need_rebalancing = 0;
  255.         return;
  256.       case AVLBALANCED:
  257.         set_bf(t, AVLRIGHTHEAVY);
  258.         return;
  259.       case AVLRIGHTHEAVY:
  260.         <T><C>AVLNode* r = t->rt;
  261.         if (bf(r) == AVLRIGHTHEAVY)
  262.         {
  263.           if (lthread(r))
  264.             t->rt = r;
  265.           else
  266.             t->rt = r->lt;
  267.           set_rthread(t, lthread(r));
  268.           r->lt = t;
  269.           set_lthread(r, 0);
  270.           set_bf(t, AVLBALANCED);
  271.           set_bf(r, AVLBALANCED);
  272.           t = r;
  273.           _need_rebalancing = 0;
  274.         }
  275.         else
  276.         {
  277.           <T><C>AVLNode* l = r->lt;
  278.           set_lthread(r, rthread(l));
  279.           if (rthread(l))
  280.             r->lt = l;
  281.           else
  282.             r->lt = l->rt;
  283.           l->rt = r;
  284.           set_rthread(l, 0);
  285.           set_rthread(t, lthread(l));
  286.           if (lthread(l))
  287.             t->rt = l;
  288.           else
  289.             t->rt = l->lt;
  290.           l->lt = t;
  291.           set_lthread(l, 0);
  292.           if (bf(l) == AVLRIGHTHEAVY)
  293.             set_bf(t, AVLLEFTHEAVY);
  294.           else
  295.             set_bf(t, AVLBALANCED);
  296.           if (bf(l) == AVLLEFTHEAVY)
  297.             set_bf(r, AVLRIGHTHEAVY);
  298.           else
  299.             set_bf(r, AVLBALANCED);
  300.           set_bf(l, AVLBALANCED);
  301.           t = l;
  302.           _need_rebalancing = 0;
  303.           return;
  304.         }
  305.       }
  306.     }
  307.   }
  308. }
  309.  
  310.     
  311. <C>& <T><C>AVLMap::operator [] (<T&> item)
  312. {
  313.   if (root == 0)
  314.   {
  315.     ++count;
  316.     root = new <T><C>AVLNode(item, def);
  317.     set_rthread(root, 1);
  318.     set_lthread(root, 1);
  319.     return root->cont;
  320.   }
  321.   else
  322.   {
  323.     _target_item = &item;
  324.     _need_rebalancing = 0;
  325.     _add(root);
  326.     return _found_node->cont;
  327.   }
  328. }
  329.  
  330.  
  331. void <T><C>AVLMap::_del(<T><C>AVLNode* par, <T><C>AVLNode*& t)
  332. {
  333.   int comp;
  334.   if (_already_found)
  335.   {
  336.     if (rthread(t))
  337.       comp = 0;
  338.     else
  339.       comp = 1;
  340.   }
  341.   else 
  342.     comp = <T>CMP(*_target_item, t->item);
  343.   if (comp == 0)
  344.   {
  345.     if (lthread(t) && rthread(t))
  346.     {
  347.       _found_node = t;
  348.       if (t == par->lt)
  349.       {
  350.         set_lthread(par, 1);
  351.         par->lt = t->lt;
  352.       }
  353.       else
  354.       {
  355.         set_rthread(par, 1);
  356.         par->rt = t->rt;
  357.       }
  358.       _need_rebalancing = 1;
  359.       return;
  360.     }
  361.     else if (lthread(t))
  362.     {
  363.       _found_node = t;
  364.       <T><C>AVLNode* s = succ(t);
  365.       if (s != 0 && lthread(s))
  366.         s->lt = t->lt;
  367.       t = t->rt;
  368.       _need_rebalancing = 1;
  369.       return;
  370.     }
  371.     else if (rthread(t))
  372.     {
  373.       _found_node = t;
  374.       <T><C>AVLNode* p = pred(t);
  375.       if (p != 0 && rthread(p))
  376.         p->rt = t->rt;
  377.       t = t->lt;
  378.       _need_rebalancing = 1;
  379.       return;
  380.     }
  381.     else                        // replace item & find someone deletable
  382.     {
  383.       <T><C>AVLNode* p = pred(t);
  384.       t->item = p->item;
  385.       t->cont = p->cont;
  386.       _already_found = 1;
  387.       comp = -1;                // fall through below to left
  388.     }
  389.   }
  390.  
  391.   if (comp < 0)
  392.   {
  393.     if (lthread(t))
  394.       return;
  395.     _del(t, t->lt);
  396.     if (!_need_rebalancing)
  397.       return;
  398.     switch (bf(t))
  399.     {
  400.     case AVLLEFTHEAVY:
  401.       set_bf(t, AVLBALANCED);
  402.       return;
  403.     case AVLBALANCED:
  404.       set_bf(t, AVLRIGHTHEAVY);
  405.       _need_rebalancing = 0;
  406.       return;
  407.     case AVLRIGHTHEAVY:
  408.       <T><C>AVLNode* r = t->rt;
  409.       switch (bf(r))
  410.       {
  411.       case AVLBALANCED:
  412.         if (lthread(r))
  413.           t->rt = r;
  414.         else
  415.           t->rt = r->lt;
  416.         set_rthread(t, lthread(r));
  417.         r->lt = t;
  418.         set_lthread(r, 0);
  419.         set_bf(t, AVLRIGHTHEAVY);
  420.         set_bf(r, AVLLEFTHEAVY);
  421.         _need_rebalancing = 0;
  422.         t = r;
  423.         return;
  424.       case AVLRIGHTHEAVY:
  425.         if (lthread(r))
  426.           t->rt = r;
  427.         else
  428.           t->rt = r->lt;
  429.         set_rthread(t, lthread(r));
  430.         r->lt = t;
  431.         set_lthread(r, 0);
  432.         set_bf(t, AVLBALANCED);
  433.         set_bf(r, AVLBALANCED);
  434.         t = r;
  435.         return;
  436.       case AVLLEFTHEAVY:
  437.         <T><C>AVLNode* l = r->lt;
  438.         set_lthread(r, rthread(l));
  439.         if (rthread(l))
  440.           r->lt = l;
  441.         else
  442.           r->lt = l->rt;
  443.         l->rt = r;
  444.         set_rthread(l, 0);
  445.         set_rthread(t, lthread(l));
  446.         if (lthread(l))
  447.           t->rt = l;
  448.         else
  449.           t->rt = l->lt;
  450.         l->lt = t;
  451.         set_lthread(l, 0);
  452.         if (bf(l) == AVLRIGHTHEAVY)
  453.           set_bf(t, AVLLEFTHEAVY);
  454.         else
  455.           set_bf(t, AVLBALANCED);
  456.         if (bf(l) == AVLLEFTHEAVY)
  457.           set_bf(r, AVLRIGHTHEAVY);
  458.         else
  459.           set_bf(r, AVLBALANCED);
  460.         set_bf(l, AVLBALANCED);
  461.         t = l;
  462.         return;
  463.       }
  464.     }
  465.   }
  466.   else
  467.   {
  468.     if (rthread(t))
  469.       return;
  470.     _del(t, t->rt);
  471.     if (!_need_rebalancing)
  472.       return;
  473.     switch (bf(t))
  474.     {
  475.     case AVLRIGHTHEAVY:
  476.       set_bf(t, AVLBALANCED);
  477.       return;
  478.     case AVLBALANCED:
  479.       set_bf(t, AVLLEFTHEAVY);
  480.       _need_rebalancing = 0;
  481.       return;
  482.     case AVLLEFTHEAVY:
  483.       <T><C>AVLNode* l = t->lt;
  484.       switch (bf(l))
  485.       {
  486.       case AVLBALANCED:
  487.         if (rthread(l))
  488.           t->lt = l;
  489.         else
  490.           t->lt = l->rt;
  491.         set_lthread(t, rthread(l));
  492.         l->rt = t;
  493.         set_rthread(l, 0);
  494.         set_bf(t, AVLLEFTHEAVY);
  495.         set_bf(l, AVLRIGHTHEAVY);
  496.         _need_rebalancing = 0;
  497.         t = l;
  498.         return;
  499.       case AVLLEFTHEAVY:
  500.         if (rthread(l))
  501.           t->lt = l;
  502.         else
  503.           t->lt = l->rt;
  504.         set_lthread(t, rthread(l));
  505.         l->rt = t;
  506.         set_rthread(l, 0);
  507.         set_bf(t, AVLBALANCED);
  508.         set_bf(l, AVLBALANCED);
  509.         t = l;
  510.         return;
  511.       case AVLRIGHTHEAVY:
  512.         <T><C>AVLNode* r = l->rt;
  513.         set_rthread(l, lthread(r));
  514.         if (lthread(r))
  515.           l->rt = r;
  516.         else
  517.           l->rt = r->lt;
  518.         r->lt = l;
  519.         set_lthread(r, 0);
  520.         set_lthread(t, rthread(r));
  521.         if (rthread(r))
  522.           t->lt = r;
  523.         else
  524.           t->lt = r->rt;
  525.         r->rt = t;
  526.         set_rthread(r, 0);
  527.         if (bf(r) == AVLLEFTHEAVY)
  528.           set_bf(t, AVLRIGHTHEAVY);
  529.         else
  530.           set_bf(t, AVLBALANCED);
  531.         if (bf(r) == AVLRIGHTHEAVY)
  532.           set_bf(l, AVLLEFTHEAVY);
  533.         else
  534.           set_bf(l, AVLBALANCED);
  535.         set_bf(r, AVLBALANCED);
  536.         t = r;
  537.         return;
  538.       }
  539.     }
  540.   }
  541. }
  542.  
  543.         
  544.  
  545. void <T><C>AVLMap::del(<T&> item)
  546. {
  547.   if (root == 0) return;
  548.   _need_rebalancing = 0;
  549.   _already_found = 0;
  550.   _found_node = 0;
  551.   _target_item = &item;
  552.   _del(root, root);
  553.   if (_found_node)
  554.   {
  555.     delete(_found_node);
  556.     if (--count == 0)
  557.       root = 0;
  558.   }
  559. }
  560.  
  561. void <T><C>AVLMap::_kill(<T><C>AVLNode* t)
  562. {
  563.   if (t != 0)
  564.   {
  565.     if (!lthread(t)) _kill(t->lt);
  566.     if (!rthread(t)) _kill(t->rt);
  567.     delete t;
  568.   }
  569. }
  570.  
  571.  
  572. <T><C>AVLMap::<T><C>AVLMap(<T><C>AVLMap& b) :<T><C>Map(b.def)
  573. {
  574.   root = 0;
  575.   count = 0;
  576.   for (Pix i = b.first(); i != 0; b.next(i)) 
  577.     (*this)[b.key(i)] = b.contents(i);
  578. }
  579.  
  580.  
  581. int <T><C>AVLMap::OK()
  582. {
  583.   int v = 1;
  584.   if (root == 0) 
  585.     v = count == 0;
  586.   else
  587.   {
  588.     int n = 1;
  589.     <T><C>AVLNode* trail = leftmost();
  590.     <T><C>AVLNode* t = succ(trail);
  591.     while (t != 0)
  592.     {
  593.       ++n;
  594.       v &= <T>CMP(trail->item, t->item) < 0;
  595.       trail = t;
  596.       t = succ(t);
  597.     }
  598.     v &= n == count;
  599.   }
  600.   if (!v) error("invariant failure");
  601.   return v;
  602. }
  603.