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