home *** CD-ROM | disk | FTP | other *** search
/ Mega Top 1 / os2_top1.zip / os2_top1 / APPS / TEKST / TXI2IPF1 / SOURCE.ZIP / gen / String_int_AVLMap.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-02-04  |  13.8 KB  |  614 lines
  1. ///////////////////////////////////////////////////////////////////////////////
  2. // $Id: String_int_AVLMap.cc,v 1.1 1993/02/04 15:16:12 ak Exp $
  3. ///////////////////////////////////////////////////////////////////////////////
  4. // $Log: String_int_AVLMap.cc,v $
  5. // Revision 1.1  1993/02/04  15:16:12  ak
  6. // Initial revision
  7. //
  8. ///////////////////////////////////////////////////////////////////////////////
  9.  
  10. static char *rcsid = "$Id: String_int_AVLMap.cc,v 1.1 1993/02/04 15:16:12 ak Exp $";
  11.  
  12. // This may look like C code, but it is really -*- C++ -*-
  13. /*
  14. Copyright (C) 1988 Free Software Foundation
  15.     written by Doug Lea (dl@rocky.oswego.edu)
  16.  
  17. This file is part of the GNU C++ Library.  This library is free
  18. software; you can redistribute it and/or modify it under the terms of
  19. the GNU Library General Public License as published by the Free
  20. Software Foundation; either version 2 of the License, or (at your
  21. option) any later version.  This library is distributed in the hope
  22. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  23. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  24. PURPOSE.  See the GNU Library General Public License for more details.
  25. You should have received a copy of the GNU Library General Public
  26. License along with this library; if not, write to the Free Software
  27. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  28. */
  29.  
  30. #ifdef __GNUG__
  31. #pragma implementation
  32. #endif
  33. #include <stream.h>
  34. #include "info.h"
  35.  
  36.  
  37. /*
  38.  constants & inlines for maintaining balance & thread status in tree nodes
  39. */
  40.  
  41. #define AVLBALANCEMASK    3
  42. #define AVLBALANCED       0
  43. #define AVLLEFTHEAVY      1
  44. #define AVLRIGHTHEAVY     2
  45.  
  46. #define LTHREADBIT        4
  47. #define RTHREADBIT        8
  48.  
  49.  
  50. static inline int bf(StringintAVLNode* t)
  51. {
  52.   return t->stat & AVLBALANCEMASK;
  53. }
  54.  
  55. static inline void set_bf(StringintAVLNode* t, int b)
  56. {
  57.   t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK);
  58. }
  59.  
  60.  
  61. static inline int rthread(StringintAVLNode* t)
  62. {
  63.   return t->stat & RTHREADBIT;
  64. }
  65.  
  66. static inline void set_rthread(StringintAVLNode* t, int b)
  67. {
  68.   if (b)
  69.     t->stat |= RTHREADBIT;
  70.   else
  71.     t->stat &= ~RTHREADBIT;
  72. }
  73.  
  74. static inline int lthread(StringintAVLNode* t)
  75. {
  76.   return t->stat & LTHREADBIT;
  77. }
  78.  
  79. static inline void set_lthread(StringintAVLNode* t, int b)
  80. {
  81.   if (b)
  82.     t->stat |= LTHREADBIT;
  83.   else
  84.     t->stat &= ~LTHREADBIT;
  85. }
  86.  
  87. /*
  88.  traversal primitives
  89. */
  90.  
  91.  
  92. StringintAVLNode* StringintAVLMap::leftmost()
  93. {
  94.   StringintAVLNode* t = root;
  95.   if (t != 0) while (t->lt != 0) t = t->lt;
  96.   return t;
  97. }
  98.  
  99. StringintAVLNode* StringintAVLMap::rightmost()
  100. {
  101.   StringintAVLNode* t = root;
  102.   if (t != 0) while (t->rt != 0) t = t->rt;
  103.   return t;
  104. }
  105.  
  106. StringintAVLNode* StringintAVLMap::succ(StringintAVLNode* t)
  107. {
  108.   StringintAVLNode* r = t->rt;
  109.   if (!rthread(t)) while (!lthread(r)) r = r->lt;
  110.   return r;
  111. }
  112.  
  113. StringintAVLNode* StringintAVLMap::pred(StringintAVLNode* t)
  114. {
  115.   StringintAVLNode* l = t->lt;
  116.   if (!lthread(t)) while (!rthread(l)) l = l->rt;
  117.   return l;
  118. }
  119.  
  120.  
  121. Pix StringintAVLMap::seek(String& key)
  122. {
  123.   StringintAVLNode* t = root;
  124.   if (t == 0)
  125.     return 0;
  126.   for (;;)
  127.   {
  128.     int cmp = StringCMP(key, t->item);
  129.     if (cmp == 0)
  130.       return Pix(t);
  131.     else if (cmp < 0)
  132.     {
  133.       if (lthread(t))
  134.         return 0;
  135.       else
  136.         t = t->lt;
  137.     }
  138.     else if (rthread(t))
  139.       return 0;
  140.     else
  141.       t = t->rt;
  142.   }
  143. }
  144.  
  145.  
  146. /*
  147.  The combination of threads and AVL bits make adding & deleting
  148.  interesting, but very awkward.
  149.  
  150.  We use the following statics to avoid passing them around recursively
  151. */
  152.  
  153. static int _need_rebalancing;   // to send back balance info from rec. calls
  154. static String*   _target_item;     // add/del_item target
  155. static StringintAVLNode* _found_node; // returned added/deleted node
  156. static int    _already_found;   // for deletion subcases
  157.  
  158.  
  159. void StringintAVLMap:: _add(StringintAVLNode*& t)
  160. {
  161.   int cmp = StringCMP(*_target_item, t->item);
  162.   if (cmp == 0)
  163.   {
  164.     _found_node = t;
  165.     return;
  166.   }
  167.   else if (cmp < 0)
  168.   {
  169.     if (lthread(t))
  170.     {
  171.       ++count;
  172.       _found_node = new StringintAVLNode(*_target_item, def);
  173.       set_lthread(_found_node, 1);
  174.       set_rthread(_found_node, 1);
  175.       _found_node->lt = t->lt;
  176.       _found_node->rt = t;
  177.       t->lt = _found_node;
  178.       set_lthread(t, 0);
  179.       _need_rebalancing = 1;
  180.     }
  181.     else
  182.       _add(t->lt);
  183.     if (_need_rebalancing)
  184.     {
  185.       switch(bf(t))
  186.       {
  187.       case AVLRIGHTHEAVY:
  188.         set_bf(t, AVLBALANCED);
  189.         _need_rebalancing = 0;
  190.         return;
  191.       case AVLBALANCED:
  192.         set_bf(t, AVLLEFTHEAVY);
  193.         return;
  194.       case AVLLEFTHEAVY:
  195.         StringintAVLNode* l = t->lt;
  196.         if (bf(l) == AVLLEFTHEAVY)
  197.         {
  198.           if (rthread(l))
  199.             t->lt = l;
  200.           else
  201.             t->lt = l->rt;
  202.           set_lthread(t, rthread(l));
  203.           l->rt = t;
  204.           set_rthread(l, 0);
  205.           set_bf(t, AVLBALANCED);
  206.           set_bf(l, AVLBALANCED);
  207.           t = l;
  208.           _need_rebalancing = 0;
  209.         }
  210.         else
  211.         {
  212.           StringintAVLNode* r = l->rt;
  213.           set_rthread(l, lthread(r));
  214.           if (lthread(r))
  215.             l->rt = r;
  216.           else
  217.             l->rt = r->lt;
  218.           r->lt = l;
  219.           set_lthread(r, 0);
  220.           set_lthread(t, rthread(r));
  221.           if (rthread(r))
  222.             t->lt = r;
  223.           else
  224.             t->lt = r->rt;
  225.           r->rt = t;
  226.           set_rthread(r, 0);
  227.           if (bf(r) == AVLLEFTHEAVY)
  228.             set_bf(t, AVLRIGHTHEAVY);
  229.           else
  230.             set_bf(t, AVLBALANCED);
  231.           if (bf(r) == AVLRIGHTHEAVY)
  232.             set_bf(l, AVLLEFTHEAVY);
  233.           else
  234.             set_bf(l, AVLBALANCED);
  235.           set_bf(r, AVLBALANCED);
  236.           t = r;
  237.           _need_rebalancing = 0;
  238.           return;
  239.         }
  240.       }
  241.     }
  242.   }
  243.   else
  244.   {
  245.     if (rthread(t))
  246.     {
  247.       ++count;
  248.       _found_node = new StringintAVLNode(*_target_item, def);
  249.       set_rthread(t, 0);
  250.       set_lthread(_found_node, 1);
  251.       set_rthread(_found_node, 1);
  252.       _found_node->lt = t;
  253.       _found_node->rt = t->rt;
  254.       t->rt = _found_node;
  255.       _need_rebalancing = 1;
  256.     }
  257.     else
  258.       _add(t->rt);
  259.     if (_need_rebalancing)
  260.     {
  261.       switch(bf(t))
  262.       {
  263.       case AVLLEFTHEAVY:
  264.         set_bf(t, AVLBALANCED);
  265.         _need_rebalancing = 0;
  266.         return;
  267.       case AVLBALANCED:
  268.         set_bf(t, AVLRIGHTHEAVY);
  269.         return;
  270.       case AVLRIGHTHEAVY:
  271.         StringintAVLNode* r = t->rt;
  272.         if (bf(r) == AVLRIGHTHEAVY)
  273.         {
  274.           if (lthread(r))
  275.             t->rt = r;
  276.           else
  277.             t->rt = r->lt;
  278.           set_rthread(t, lthread(r));
  279.           r->lt = t;
  280.           set_lthread(r, 0);
  281.           set_bf(t, AVLBALANCED);
  282.           set_bf(r, AVLBALANCED);
  283.           t = r;
  284.           _need_rebalancing = 0;
  285.         }
  286.         else
  287.         {
  288.           StringintAVLNode* l = r->lt;
  289.           set_lthread(r, rthread(l));
  290.           if (rthread(l))
  291.             r->lt = l;
  292.           else
  293.             r->lt = l->rt;
  294.           l->rt = r;
  295.           set_rthread(l, 0);
  296.           set_rthread(t, lthread(l));
  297.           if (lthread(l))
  298.             t->rt = l;
  299.           else
  300.             t->rt = l->lt;
  301.           l->lt = t;
  302.           set_lthread(l, 0);
  303.           if (bf(l) == AVLRIGHTHEAVY)
  304.             set_bf(t, AVLLEFTHEAVY);
  305.           else
  306.             set_bf(t, AVLBALANCED);
  307.           if (bf(l) == AVLLEFTHEAVY)
  308.             set_bf(r, AVLRIGHTHEAVY);
  309.           else
  310.             set_bf(r, AVLBALANCED);
  311.           set_bf(l, AVLBALANCED);
  312.           t = l;
  313.           _need_rebalancing = 0;
  314.           return;
  315.         }
  316.       }
  317.     }
  318.   }
  319. }
  320.  
  321.  
  322. int& StringintAVLMap::operator [] (String& item)
  323. {
  324.   if (root == 0)
  325.   {
  326.     ++count;
  327.     root = new StringintAVLNode(item, def);
  328.     set_rthread(root, 1);
  329.     set_lthread(root, 1);
  330.     return root->cont;
  331.   }
  332.   else
  333.   {
  334.     _target_item = &item;
  335.     _need_rebalancing = 0;
  336.     _add(root);
  337.     return _found_node->cont;
  338.   }
  339. }
  340.  
  341.  
  342. void StringintAVLMap::_del(StringintAVLNode* par, StringintAVLNode*& t)
  343. {
  344.   int comp;
  345.   if (_already_found)
  346.   {
  347.     if (rthread(t))
  348.       comp = 0;
  349.     else
  350.       comp = 1;
  351.   }
  352.   else
  353.     comp = StringCMP(*_target_item, t->item);
  354.   if (comp == 0)
  355.   {
  356.     if (lthread(t) && rthread(t))
  357.     {
  358.       _found_node = t;
  359.       if (t == par->lt)
  360.       {
  361.         set_lthread(par, 1);
  362.         par->lt = t->lt;
  363.       }
  364.       else
  365.       {
  366.         set_rthread(par, 1);
  367.         par->rt = t->rt;
  368.       }
  369.       _need_rebalancing = 1;
  370.       return;
  371.     }
  372.     else if (lthread(t))
  373.     {
  374.       _found_node = t;
  375.       StringintAVLNode* s = succ(t);
  376.       if (s != 0 && lthread(s))
  377.         s->lt = t->lt;
  378.       t = t->rt;
  379.       _need_rebalancing = 1;
  380.       return;
  381.     }
  382.     else if (rthread(t))
  383.     {
  384.       _found_node = t;
  385.       StringintAVLNode* p = pred(t);
  386.       if (p != 0 && rthread(p))
  387.         p->rt = t->rt;
  388.       t = t->lt;
  389.       _need_rebalancing = 1;
  390.       return;
  391.     }
  392.     else                        // replace item & find someone deletable
  393.     {
  394.       StringintAVLNode* p = pred(t);
  395.       t->item = p->item;
  396.       t->cont = p->cont;
  397.       _already_found = 1;
  398.       comp = -1;                // fall through below to left
  399.     }
  400.   }
  401.  
  402.   if (comp < 0)
  403.   {
  404.     if (lthread(t))
  405.       return;
  406.     _del(t, t->lt);
  407.     if (!_need_rebalancing)
  408.       return;
  409.     switch (bf(t))
  410.     {
  411.     case AVLLEFTHEAVY:
  412.       set_bf(t, AVLBALANCED);
  413.       return;
  414.     case AVLBALANCED:
  415.       set_bf(t, AVLRIGHTHEAVY);
  416.       _need_rebalancing = 0;
  417.       return;
  418.     case AVLRIGHTHEAVY:
  419.       StringintAVLNode* r = t->rt;
  420.       switch (bf(r))
  421.       {
  422.       case AVLBALANCED:
  423.         if (lthread(r))
  424.           t->rt = r;
  425.         else
  426.           t->rt = r->lt;
  427.         set_rthread(t, lthread(r));
  428.         r->lt = t;
  429.         set_lthread(r, 0);
  430.         set_bf(t, AVLRIGHTHEAVY);
  431.         set_bf(r, AVLLEFTHEAVY);
  432.         _need_rebalancing = 0;
  433.         t = r;
  434.         return;
  435.       case AVLRIGHTHEAVY:
  436.         if (lthread(r))
  437.           t->rt = r;
  438.         else
  439.           t->rt = r->lt;
  440.         set_rthread(t, lthread(r));
  441.         r->lt = t;
  442.         set_lthread(r, 0);
  443.         set_bf(t, AVLBALANCED);
  444.         set_bf(r, AVLBALANCED);
  445.         t = r;
  446.         return;
  447.       case AVLLEFTHEAVY:
  448.         StringintAVLNode* l = r->lt;
  449.         set_lthread(r, rthread(l));
  450.         if (rthread(l))
  451.           r->lt = l;
  452.         else
  453.           r->lt = l->rt;
  454.         l->rt = r;
  455.         set_rthread(l, 0);
  456.         set_rthread(t, lthread(l));
  457.         if (lthread(l))
  458.           t->rt = l;
  459.         else
  460.           t->rt = l->lt;
  461.         l->lt = t;
  462.         set_lthread(l, 0);
  463.         if (bf(l) == AVLRIGHTHEAVY)
  464.           set_bf(t, AVLLEFTHEAVY);
  465.         else
  466.           set_bf(t, AVLBALANCED);
  467.         if (bf(l) == AVLLEFTHEAVY)
  468.           set_bf(r, AVLRIGHTHEAVY);
  469.         else
  470.           set_bf(r, AVLBALANCED);
  471.         set_bf(l, AVLBALANCED);
  472.         t = l;
  473.         return;
  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.       StringintAVLNode* l = t->lt;
  495.       switch (bf(l))
  496.       {
  497.       case AVLBALANCED:
  498.         if (rthread(l))
  499.           t->lt = l;
  500.         else
  501.           t->lt = l->rt;
  502.         set_lthread(t, rthread(l));
  503.         l->rt = t;
  504.         set_rthread(l, 0);
  505.         set_bf(t, AVLLEFTHEAVY);
  506.         set_bf(l, AVLRIGHTHEAVY);
  507.         _need_rebalancing = 0;
  508.         t = l;
  509.         return;
  510.       case AVLLEFTHEAVY:
  511.         if (rthread(l))
  512.           t->lt = l;
  513.         else
  514.           t->lt = l->rt;
  515.         set_lthread(t, rthread(l));
  516.         l->rt = t;
  517.         set_rthread(l, 0);
  518.         set_bf(t, AVLBALANCED);
  519.         set_bf(l, AVLBALANCED);
  520.         t = l;
  521.         return;
  522.       case AVLRIGHTHEAVY:
  523.         StringintAVLNode* r = l->rt;
  524.         set_rthread(l, lthread(r));
  525.         if (lthread(r))
  526.           l->rt = r;
  527.         else
  528.           l->rt = r->lt;
  529.         r->lt = l;
  530.         set_lthread(r, 0);
  531.         set_lthread(t, rthread(r));
  532.         if (rthread(r))
  533.           t->lt = r;
  534.         else
  535.           t->lt = r->rt;
  536.         r->rt = t;
  537.         set_rthread(r, 0);
  538.         if (bf(r) == AVLLEFTHEAVY)
  539.           set_bf(t, AVLRIGHTHEAVY);
  540.         else
  541.           set_bf(t, AVLBALANCED);
  542.         if (bf(r) == AVLRIGHTHEAVY)
  543.           set_bf(l, AVLLEFTHEAVY);
  544.         else
  545.           set_bf(l, AVLBALANCED);
  546.         set_bf(r, AVLBALANCED);
  547.         t = r;
  548.         return;
  549.       }
  550.     }
  551.   }
  552. }
  553.  
  554.  
  555.  
  556. void StringintAVLMap::del(String& item)
  557. {
  558.   if (root == 0) return;
  559.   _need_rebalancing = 0;
  560.   _already_found = 0;
  561.   _found_node = 0;
  562.   _target_item = &item;
  563.   _del(root, root);
  564.   if (_found_node)
  565.   {
  566.     delete(_found_node);
  567.     if (--count == 0)
  568.       root = 0;
  569.   }
  570. }
  571.  
  572. void StringintAVLMap::_kill(StringintAVLNode* t)
  573. {
  574.   if (t != 0)
  575.   {
  576.     if (!lthread(t)) _kill(t->lt);
  577.     if (!rthread(t)) _kill(t->rt);
  578.     delete t;
  579.   }
  580. }
  581.  
  582.  
  583. StringintAVLMap::StringintAVLMap(StringintAVLMap& b) :StringintMap(b.def)
  584. {
  585.   root = 0;
  586.   count = 0;
  587.   for (Pix i = b.first(); i != 0; b.next(i))
  588.     (*this)[b.key(i)] = b.contents(i);
  589. }
  590.  
  591.  
  592. int StringintAVLMap::OK()
  593. {
  594.   int v = 1;
  595.   if (root == 0)
  596.     v = count == 0;
  597.   else
  598.   {
  599.     int n = 1;
  600.     StringintAVLNode* trail = leftmost();
  601.     StringintAVLNode* t = succ(trail);
  602.     while (t != 0)
  603.     {
  604.       ++n;
  605.       v &= StringCMP(trail->item, t->item) < 0;
  606.       trail = t;
  607.       t = succ(t);
  608.     }
  609.     v &= n == count;
  610.   }
  611.   if (!v) error("invariant failure");
  612.   return v;
  613. }
  614.