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