home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer) / NeXT_Developer-3.3.iso / NextDeveloper / Headers / g++ / gen / RAVLMap.ccP < prev    next >
Encoding:
Text File  |  1995-02-06  |  14.1 KB  |  691 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.     {
  239.         <T><C>RAVLNode* l = t->lt;
  240.         if (bf(l) == AVLLEFTHEAVY)
  241.         {
  242.       t->rank -= l->rank;
  243.           if (rthread(l))
  244.             t->lt = l;
  245.           else
  246.             t->lt = l->rt;
  247.           set_lthread(t, rthread(l));
  248.           l->rt = t;
  249.           set_rthread(l, 0);
  250.           set_bf(t, AVLBALANCED);
  251.           set_bf(l, AVLBALANCED);
  252.           t = l;
  253.           _need_rebalancing = 0;
  254.         }
  255.         else
  256.         {
  257.           <T><C>RAVLNode* r = l->rt;
  258.       r->rank += l->rank;
  259.       t->rank -= r->rank;
  260.           set_rthread(l, lthread(r));
  261.           if (lthread(r))
  262.             l->rt = r;
  263.           else
  264.             l->rt = r->lt;
  265.           r->lt = l;
  266.           set_lthread(r, 0);
  267.           set_lthread(t, rthread(r));
  268.           if (rthread(r))
  269.             t->lt = r;
  270.           else
  271.             t->lt = r->rt;
  272.           r->rt = t;
  273.           set_rthread(r, 0);
  274.           if (bf(r) == AVLLEFTHEAVY)
  275.             set_bf(t, AVLRIGHTHEAVY);
  276.           else
  277.             set_bf(t, AVLBALANCED);
  278.           if (bf(r) == AVLRIGHTHEAVY)
  279.             set_bf(l, AVLLEFTHEAVY);
  280.           else
  281.             set_bf(l, AVLBALANCED);
  282.           set_bf(r, AVLBALANCED);
  283.           t = r;
  284.           _need_rebalancing = 0;
  285.           return;
  286.         }
  287.     }
  288.       }
  289.     }
  290.   }
  291.   else
  292.   {
  293.     if (rthread(t))
  294.     {
  295.       ++count;
  296.       _found_node = new <T><C>RAVLNode(*_target_item, def);
  297.       set_rthread(t, 0);
  298.       set_lthread(_found_node, 1);
  299.       set_rthread(_found_node, 1);
  300.       _found_node->lt = t;
  301.       _found_node->rt = t->rt;
  302.       t->rt = _found_node;
  303.       _need_rebalancing = 1;
  304.       _rank_changed = 1;
  305.     }
  306.     else
  307.       _add(t->rt);
  308.     if (_need_rebalancing)
  309.     {
  310.       switch(bf(t))
  311.       {
  312.       case AVLLEFTHEAVY:
  313.         set_bf(t, AVLBALANCED);
  314.         _need_rebalancing = 0;
  315.         return;
  316.       case AVLBALANCED:
  317.         set_bf(t, AVLRIGHTHEAVY);
  318.         return;
  319.       case AVLRIGHTHEAVY:
  320.     {
  321.         <T><C>RAVLNode* r = t->rt;
  322.         if (bf(r) == AVLRIGHTHEAVY)
  323.         {
  324.       r->rank += t->rank;
  325.           if (lthread(r))
  326.             t->rt = r;
  327.           else
  328.             t->rt = r->lt;
  329.           set_rthread(t, lthread(r));
  330.           r->lt = t;
  331.           set_lthread(r, 0);
  332.           set_bf(t, AVLBALANCED);
  333.           set_bf(r, AVLBALANCED);
  334.           t = r;
  335.           _need_rebalancing = 0;
  336.         }
  337.         else
  338.         {
  339.           <T><C>RAVLNode* l = r->lt;
  340.       r->rank -= l->rank;
  341.       l->rank += t->rank;
  342.           set_lthread(r, rthread(l));
  343.           if (rthread(l))
  344.             r->lt = l;
  345.           else
  346.             r->lt = l->rt;
  347.           l->rt = r;
  348.           set_rthread(l, 0);
  349.           set_rthread(t, lthread(l));
  350.           if (lthread(l))
  351.             t->rt = l;
  352.           else
  353.             t->rt = l->lt;
  354.           l->lt = t;
  355.           set_lthread(l, 0);
  356.           if (bf(l) == AVLRIGHTHEAVY)
  357.             set_bf(t, AVLLEFTHEAVY);
  358.           else
  359.             set_bf(t, AVLBALANCED);
  360.           if (bf(l) == AVLLEFTHEAVY)
  361.             set_bf(r, AVLRIGHTHEAVY);
  362.           else
  363.             set_bf(r, AVLBALANCED);
  364.           set_bf(l, AVLBALANCED);
  365.           t = l;
  366.           _need_rebalancing = 0;
  367.           return;
  368.         }
  369.     }
  370.       }
  371.     }
  372.   }
  373. }
  374.  
  375.     
  376. <C>& <T><C>RAVLMap::operator [] (<T&> item)
  377. {
  378.   if (root == 0)
  379.   {
  380.     ++count;
  381.     root = new <T><C>RAVLNode(item, def);
  382.     set_rthread(root, 1);
  383.     set_lthread(root, 1);
  384.     return root->cont;
  385.   }
  386.   else
  387.   {
  388.     _target_item = &item;
  389.     _need_rebalancing = 0;
  390.     _rank_changed = 0;
  391.     _add(root);
  392.     return _found_node->cont;
  393.   }
  394. }
  395.  
  396.  
  397. void <T><C>RAVLMap::_del(<T><C>RAVLNode* par, <T><C>RAVLNode*& t)
  398. {
  399.   int comp;
  400.   if (_already_found)
  401.   {
  402.     if (rthread(t))
  403.       comp = 0;
  404.     else
  405.       comp = 1;
  406.   }
  407.   else 
  408.     comp = <T>CMP(*_target_item, t->item);
  409.   if (comp == 0)
  410.   {
  411.     if (lthread(t) && rthread(t))
  412.     {
  413.       _found_node = t;
  414.       if (t == par->lt)
  415.       {
  416.         set_lthread(par, 1);
  417.         par->lt = t->lt;
  418.       }
  419.       else
  420.       {
  421.         set_rthread(par, 1);
  422.         par->rt = t->rt;
  423.       }
  424.       _need_rebalancing = 1;
  425.       _rank_changed = 1;
  426.       return;
  427.     }
  428.     else if (lthread(t))
  429.     {
  430.       _found_node = t;
  431.       <T><C>RAVLNode* s = succ(t);
  432.       if (s != 0 && lthread(s))
  433.         s->lt = t->lt;
  434.       t = t->rt;
  435.       _need_rebalancing = 1;
  436.       _rank_changed = 1;
  437.       return;
  438.     }
  439.     else if (rthread(t))
  440.     {
  441.       _found_node = t;
  442.       <T><C>RAVLNode* p = pred(t);
  443.       if (p != 0 && rthread(p))
  444.         p->rt = t->rt;
  445.       t = t->lt;
  446.       _need_rebalancing = 1;
  447.       _rank_changed = 1;
  448.       return;
  449.     }
  450.     else                        // replace item & find someone deletable
  451.     {
  452.       <T><C>RAVLNode* p = pred(t);
  453.       t->item = p->item;
  454.       t->cont = p->cont;
  455.       _already_found = 1;
  456.       comp = -1;                // fall through below to left
  457.     }
  458.   }
  459.  
  460.   if (comp < 0)
  461.   {
  462.     if (lthread(t))
  463.       return;
  464.     _del(t, t->lt);
  465.     if (_rank_changed) --t->rank;
  466.     if (!_need_rebalancing)
  467.       return;
  468.     switch (bf(t))
  469.     {
  470.     case AVLLEFTHEAVY:
  471.       set_bf(t, AVLBALANCED);
  472.       return;
  473.     case AVLBALANCED:
  474.       set_bf(t, AVLRIGHTHEAVY);
  475.       _need_rebalancing = 0;
  476.       return;
  477.     case AVLRIGHTHEAVY:
  478.       {
  479.       <T><C>RAVLNode* r = t->rt;
  480.       switch (bf(r))
  481.       {
  482.       case AVLBALANCED:
  483.     r->rank += t->rank;
  484.         if (lthread(r))
  485.           t->rt = r;
  486.         else
  487.           t->rt = r->lt;
  488.         set_rthread(t, lthread(r));
  489.         r->lt = t;
  490.         set_lthread(r, 0);
  491.         set_bf(t, AVLRIGHTHEAVY);
  492.         set_bf(r, AVLLEFTHEAVY);
  493.         _need_rebalancing = 0;
  494.         t = r;
  495.         return;
  496.       case AVLRIGHTHEAVY:
  497.     r->rank += t->rank;
  498.         if (lthread(r))
  499.           t->rt = r;
  500.         else
  501.           t->rt = r->lt;
  502.         set_rthread(t, lthread(r));
  503.         r->lt = t;
  504.         set_lthread(r, 0);
  505.         set_bf(t, AVLBALANCED);
  506.         set_bf(r, AVLBALANCED);
  507.         t = r;
  508.         return;
  509.       case AVLLEFTHEAVY:
  510.     {
  511.         <T><C>RAVLNode* l = r->lt;
  512.     r->rank -= l->rank;
  513.     l->rank += t->rank;
  514.         set_lthread(r, rthread(l));
  515.         if (rthread(l))
  516.           r->lt = l;
  517.         else
  518.           r->lt = l->rt;
  519.         l->rt = r;
  520.         set_rthread(l, 0);
  521.         set_rthread(t, lthread(l));
  522.         if (lthread(l))
  523.           t->rt = l;
  524.         else
  525.           t->rt = l->lt;
  526.         l->lt = t;
  527.         set_lthread(l, 0);
  528.         if (bf(l) == AVLRIGHTHEAVY)
  529.           set_bf(t, AVLLEFTHEAVY);
  530.         else
  531.           set_bf(t, AVLBALANCED);
  532.         if (bf(l) == AVLLEFTHEAVY)
  533.           set_bf(r, AVLRIGHTHEAVY);
  534.         else
  535.           set_bf(r, AVLBALANCED);
  536.         set_bf(l, AVLBALANCED);
  537.         t = l;
  538.         return;
  539.     }
  540.       }
  541.     }
  542.     }
  543.   }
  544.   else
  545.   {
  546.     if (rthread(t))
  547.       return;
  548.     _del(t, t->rt);
  549.     if (!_need_rebalancing)
  550.       return;
  551.     switch (bf(t))
  552.     {
  553.     case AVLRIGHTHEAVY:
  554.       set_bf(t, AVLBALANCED);
  555.       return;
  556.     case AVLBALANCED:
  557.       set_bf(t, AVLLEFTHEAVY);
  558.       _need_rebalancing = 0;
  559.       return;
  560.     case AVLLEFTHEAVY:
  561.       {
  562.       <T><C>RAVLNode* l = t->lt;
  563.       switch (bf(l))
  564.       {
  565.       case AVLBALANCED:
  566.     t->rank -= l->rank;
  567.         if (rthread(l))
  568.           t->lt = l;
  569.         else
  570.           t->lt = l->rt;
  571.         set_lthread(t, rthread(l));
  572.         l->rt = t;
  573.         set_rthread(l, 0);
  574.         set_bf(t, AVLLEFTHEAVY);
  575.         set_bf(l, AVLRIGHTHEAVY);
  576.         _need_rebalancing = 0;
  577.         t = l;
  578.         return;
  579.       case AVLLEFTHEAVY:
  580.     t->rank -= l->rank;
  581.         if (rthread(l))
  582.           t->lt = l;
  583.         else
  584.           t->lt = l->rt;
  585.         set_lthread(t, rthread(l));
  586.         l->rt = t;
  587.         set_rthread(l, 0);
  588.         set_bf(t, AVLBALANCED);
  589.         set_bf(l, AVLBALANCED);
  590.         t = l;
  591.         return;
  592.       case AVLRIGHTHEAVY:
  593.     {
  594.         <T><C>RAVLNode* r = l->rt;
  595.     r->rank += l->rank;
  596.     t->rank -= r->rank;
  597.         set_rthread(l, lthread(r));
  598.         if (lthread(r))
  599.           l->rt = r;
  600.         else
  601.           l->rt = r->lt;
  602.         r->lt = l;
  603.         set_lthread(r, 0);
  604.         set_lthread(t, rthread(r));
  605.         if (rthread(r))
  606.           t->lt = r;
  607.         else
  608.           t->lt = r->rt;
  609.         r->rt = t;
  610.         set_rthread(r, 0);
  611.         if (bf(r) == AVLLEFTHEAVY)
  612.           set_bf(t, AVLRIGHTHEAVY);
  613.         else
  614.           set_bf(t, AVLBALANCED);
  615.         if (bf(r) == AVLRIGHTHEAVY)
  616.           set_bf(l, AVLLEFTHEAVY);
  617.         else
  618.           set_bf(l, AVLBALANCED);
  619.         set_bf(r, AVLBALANCED);
  620.         t = r;
  621.         return;
  622.     }
  623.       }
  624.       }
  625.     }
  626.   }
  627. }
  628.  
  629.  
  630. void <T><C>RAVLMap::del(<T&> item)
  631. {
  632.   if (root == 0) return;
  633.   _need_rebalancing = 0;
  634.   _already_found = 0;
  635.   _found_node = 0;
  636.   _rank_changed = 0;
  637.   _target_item = &item;
  638.   _del(root, root);
  639.   if (_found_node)
  640.   {
  641.     delete(_found_node);
  642.     if (--count == 0)
  643.       root = 0;
  644.   }
  645. }
  646.  
  647. void <T><C>RAVLMap::_kill(<T><C>RAVLNode* t)
  648. {
  649.   if (t != 0)
  650.   {
  651.     if (!lthread(t)) _kill(t->lt);
  652.     if (!rthread(t)) _kill(t->rt);
  653.     delete t;
  654.   }
  655. }
  656.  
  657.  
  658. <T><C>RAVLMap::<T><C>RAVLMap(<T><C>RAVLMap& b) :<T><C>Map(b.def)
  659. {
  660.   root = 0;
  661.   count = 0;
  662.   for (Pix i = b.first(); i != 0; b.next(i)) 
  663.     (*this)[b.key(i)] = b.contents(i);
  664. }
  665.  
  666.  
  667. int <T><C>RAVLMap::OK()
  668. {
  669.   int v = 1;
  670.   if (root == 0) 
  671.     v = count == 0;
  672.   else
  673.   {
  674.     int n = 1;
  675.     <T><C>RAVLNode* trail = leftmost();
  676.     v &= rankof(trail->item) == n;
  677.     <T><C>RAVLNode* t = succ(trail);
  678.     while (t != 0)
  679.     {
  680.       ++n;
  681.       v &= <T>CMP(trail->item, t->item) < 0;
  682.       v &= rankof(t->item) == n;
  683.       trail = t;
  684.       t = succ(t);
  685.     }
  686.     v &= n == count;
  687.   }
  688.   if (!v) error("invariant failure");
  689.   return v;
  690. }
  691.