home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c017 / 7.ddi / GPPLIB.ZIP / AVLASSOC.CC < prev    next >
Encoding:
C/C++ Source or Header  |  1988-08-17  |  15.6 KB  |  708 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 GNU CC.
  7.  
  8. GNU CC is distributed in the hope that it will be useful,
  9. but WITHOUT ANY WARRANTY.  No author or distributor
  10. accepts responsibility to anyone for the consequences of using it
  11. or for whether it serves any particular purpose or works at all,
  12. unless he says so in writing.  Refer to the GNU CC General Public
  13. License for full details.
  14.  
  15. Everyone is granted permission to copy, modify and redistribute
  16. GNU CC, but only under the conditions described in the
  17. GNU CC General Public License.   A copy of this license is
  18. supposed to have been given to you along with GNU CC so you
  19. can know your rights and responsibilities.  It should be in a
  20. file named COPYING.  Among other things, the copyright notice
  21. and this notice must be preserved on all copies.  
  22. */
  23.  
  24. #include <stream.h>
  25. #include <assert.h>
  26. #include "<T><U>AVLAssoc.h"
  27.  
  28.  
  29. // error handling
  30.  
  31.  
  32. void default_<T><U>AVLAssoc_error_handler(char* msg)
  33. {
  34.   cerr << "Fatal <T><U>AVLAssoc error. " << msg << "\n";
  35.   exit(1);
  36. }
  37.  
  38. one_arg_error_handler_t <T><U>AVLAssoc_error_handler = default_<T><U>AVLAssoc_error_handler;
  39.  
  40. one_arg_error_handler_t set_<T><U>AVLAssoc_error_handler(one_arg_error_handler_t f)
  41. {
  42.   one_arg_error_handler_t old = <T><U>AVLAssoc_error_handler;
  43.   <T><U>AVLAssoc_error_handler = f;
  44.   return old;
  45. }
  46.  
  47. void <T><U>AVLAssoc::error(const char* msg)
  48. {
  49.   (*<T><U>AVLAssoc_error_handler)(msg);
  50. }
  51.  
  52.  
  53. /*
  54.  constants & inlines for maintaining balance & thread status in tree nodes
  55. */
  56.  
  57. #define AVLBALANCEMASK    3
  58. #define AVLBALANCED       0
  59. #define AVLLEFTHEAVY      1
  60. #define AVLRIGHTHEAVY     2
  61.  
  62. #define LTHREADBIT        4
  63. #define RTHREADBIT        8
  64.  
  65.  
  66. static inline int bf(<T><U>AVLAssocNode* t)
  67. {
  68.   return t->stat & AVLBALANCEMASK;
  69. }
  70.  
  71. static inline void set_bf(<T><U>AVLAssocNode* t, int b)
  72. {
  73.   t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK);
  74. }
  75.  
  76.  
  77. static inline int rthread(<T><U>AVLAssocNode* t)
  78. {
  79.   return t->stat & RTHREADBIT;
  80. }
  81.  
  82. static inline void set_rthread(<T><U>AVLAssocNode* t, int b)
  83. {
  84.   if (b)
  85.     t->stat |= RTHREADBIT;
  86.   else
  87.     t->stat &= ~RTHREADBIT;
  88. }
  89.  
  90. static inline int lthread(<T><U>AVLAssocNode* t)
  91. {
  92.   return t->stat & LTHREADBIT;
  93. }
  94.  
  95. static inline void set_lthread(<T><U>AVLAssocNode* t, int b)
  96. {
  97.   if (b)
  98.     t->stat |= LTHREADBIT;
  99.   else
  100.     t->stat &= ~LTHREADBIT;
  101. }
  102.  
  103. /*
  104.  traversal primitives
  105. */
  106.  
  107.  
  108. <T><U>AVLAssocNode* <T><U>AVLAssoc::leftmost()
  109. {
  110.   <T><U>AVLAssocNode* t = root;
  111.   if (t != 0) while (t->lt != 0) t = t->lt;
  112.   return t;
  113. }
  114.  
  115. <T><U>AVLAssocNode* <T><U>AVLAssoc::rightmost()
  116. {
  117.   <T><U>AVLAssocNode* t = root;
  118.   if (t != 0) while (t->rt != 0) t = t->rt;
  119.   return t;
  120. }
  121.  
  122. <T><U>AVLAssocNode* <T><U>AVLAssoc::succ(<T><U>AVLAssocNode* t)
  123. {
  124.   <T><U>AVLAssocNode* r = t->rt;
  125.   if (!rthread(t)) while (!lthread(r)) r = r->lt;
  126.   return r;
  127. }
  128.  
  129. <T><U>AVLAssocNode* <T><U>AVLAssoc::pred(<T><U>AVLAssocNode* t)
  130. {
  131.   <T><U>AVLAssocNode* l = t->lt;
  132.   if (!lthread(t)) while (!rthread(l)) l = l->rt;
  133.   return l;
  134. }
  135.  
  136.  
  137. int <T><U>AVLAssoc::contains(<T&> key)
  138. {
  139.   <T><U>AVLAssocNode* t = root;
  140.   if (t == 0)
  141.     return 0;
  142.   for (;;)
  143.   {
  144.     int comp = key_key_cmp(key, t->key);
  145.     if (comp == 0)
  146.       return 1;
  147.     else if (comp < 0)
  148.     {
  149.       if (lthread(t))
  150.         return 0;
  151.       else
  152.         t = t->lt;
  153.     }
  154.     else if (rthread(t))
  155.       return 0;
  156.     else
  157.       t = t->rt;
  158.   }
  159. }
  160.  
  161.  
  162. /*
  163.  The combination of threads and AVL bits make adding & deleting
  164.  interesting, but very awkward.
  165.  
  166.  We use the following statics to avoid passing them around recursively
  167. */
  168.  
  169. static int _need_rebalancing;   // to send back balance info from rec. calls
  170. static <T>*   _target_item;     // add/del target
  171. static <T><U>AVLAssocNode* _target_node; // found or inserted node
  172. static <T><U>AVLAssocNode* _mark_for_deletion; // must put off 
  173.                                                // actualling killing
  174.                                                // deleted nodes in _del
  175. static <T><U>AVLAssocNode** _hold_nodes;       // used for rebuilding trees
  176. static int  _max_hold_index;              // # elements-1 in _hold_nodes
  177.  
  178. void <T><U>AVLAssoc:: _add(<T><U>AVLAssocNode*& t)
  179. {
  180.   int cmp = key_key_cmp(*_target_item, t->key);
  181.   if (cmp == 0)
  182.   {
  183.     _target_node = t;
  184.     return;
  185.   }
  186.   else if (cmp < 0)
  187.   {
  188.     if (lthread(t))
  189.     {
  190.       ++cnt;
  191.       <T><U>AVLAssocNode* q = new <T><U>AVLAssocNode(*_target_item);
  192.       set_lthread(q, 1);
  193.       set_rthread(q, 1);
  194.       q->lt = t->lt;
  195.       q->rt = t;
  196.       t->lt = q;
  197.       set_lthread(t, 0);
  198.       _target_node = q;
  199.       _need_rebalancing = 1;
  200.     }
  201.     else
  202.       _add(t->lt);
  203.     if (_need_rebalancing)
  204.     {
  205.       switch(bf(t))
  206.       {
  207.       case AVLRIGHTHEAVY:
  208.         set_bf(t, AVLBALANCED);
  209.         _need_rebalancing = 0;
  210.         return;
  211.       case AVLBALANCED:
  212.         set_bf(t, AVLLEFTHEAVY);
  213.         return;
  214.       case AVLLEFTHEAVY:
  215.         <T><U>AVLAssocNode* l = t->lt;
  216.         if (bf(l) == AVLLEFTHEAVY)
  217.         {
  218.           if (rthread(l))
  219.             t->lt = l;
  220.           else
  221.             t->lt = l->rt;
  222.           set_lthread(t, rthread(l));
  223.           l->rt = t;
  224.           set_rthread(l, 0);
  225.           set_bf(t, AVLBALANCED);
  226.           set_bf(l, AVLBALANCED);
  227.           t = l;
  228.           _need_rebalancing = 0;
  229.         }
  230.         else
  231.         {
  232.           <T><U>AVLAssocNode* r = l->rt;
  233.           set_rthread(l, lthread(r));
  234.           if (lthread(r))
  235.             l->rt = r;
  236.           else
  237.             l->rt = r->lt;
  238.           r->lt = l;
  239.           set_lthread(r, 0);
  240.           set_lthread(t, rthread(r));
  241.           if (rthread(r))
  242.             t->lt = r;
  243.           else
  244.             t->lt = r->rt;
  245.           r->rt = t;
  246.           set_rthread(r, 0);
  247.           if (bf(r) == AVLLEFTHEAVY)
  248.             set_bf(t, AVLRIGHTHEAVY);
  249.           else
  250.             set_bf(t, AVLBALANCED);
  251.           if (bf(r) == AVLRIGHTHEAVY)
  252.             set_bf(l, AVLLEFTHEAVY);
  253.           else
  254.             set_bf(l, AVLBALANCED);
  255.           set_bf(r, AVLBALANCED);
  256.           t = r;
  257.           _need_rebalancing = 0;
  258.           return;
  259.         }
  260.       }
  261.     }
  262.   }
  263.   else
  264.   {
  265.     if (rthread(t))
  266.     {
  267.       ++cnt;
  268.       <T><U>AVLAssocNode* q = new <T><U>AVLAssocNode(*_target_item);
  269.       set_rthread(t, 0);
  270.       set_lthread(q, 1);
  271.       set_rthread(q, 1);
  272.       q->lt = t;
  273.       q->rt = t->rt;
  274.       t->rt = q;
  275.       _target_node = q;
  276.       _need_rebalancing = 1;
  277.     }
  278.     else
  279.       _add(t->rt);
  280.     if (_need_rebalancing)
  281.     {
  282.       switch(bf(t))
  283.       {
  284.       case AVLLEFTHEAVY:
  285.         set_bf(t, AVLBALANCED);
  286.         _need_rebalancing = 0;
  287.         return;
  288.       case AVLBALANCED:
  289.         set_bf(t, AVLRIGHTHEAVY);
  290.         return;
  291.       case AVLRIGHTHEAVY:
  292.         <T><U>AVLAssocNode* r = t->rt;
  293.         if (bf(r) == AVLRIGHTHEAVY)
  294.         {
  295.           if (lthread(r))
  296.             t->rt = r;
  297.           else
  298.             t->rt = r->lt;
  299.           set_rthread(t, lthread(r));
  300.           r->lt = t;
  301.           set_lthread(r, 0);
  302.           set_bf(t, AVLBALANCED);
  303.           set_bf(r, AVLBALANCED);
  304.           t = r;
  305.           _need_rebalancing = 0;
  306.         }
  307.         else
  308.         {
  309.           <T><U>AVLAssocNode* l = r->lt;
  310.           set_lthread(r, rthread(l));
  311.           if (rthread(l))
  312.             r->lt = l;
  313.           else
  314.             r->lt = l->rt;
  315.           l->rt = r;
  316.           set_rthread(l, 0);
  317.           set_rthread(t, lthread(l));
  318.           if (lthread(l))
  319.             t->rt = l;
  320.           else
  321.             t->rt = l->lt;
  322.           l->lt = t;
  323.           set_lthread(l, 0);
  324.           if (bf(l) == AVLRIGHTHEAVY)
  325.             set_bf(t, AVLLEFTHEAVY);
  326.           else
  327.             set_bf(t, AVLBALANCED);
  328.           if (bf(l) == AVLLEFTHEAVY)
  329.             set_bf(r, AVLRIGHTHEAVY);
  330.           else
  331.             set_bf(r, AVLBALANCED);
  332.           set_bf(l, AVLBALANCED);
  333.           t = l;
  334.           _need_rebalancing = 0;
  335.           return;
  336.         }
  337.       }
  338.     }
  339.   }
  340. }
  341.     
  342. <U>& <T><U>AVLAssoc::operator [] (<T&> item)
  343. {
  344.   if (root == 0)
  345.   {
  346.     ++cnt;
  347.     root = new <T><U>AVLAssocNode(item);
  348.     set_rthread(root, 1);
  349.     set_lthread(root, 1);
  350.     return root->cont;
  351.   }
  352.   else
  353.   {
  354.     _target_item = &item;
  355.     _need_rebalancing = 0;
  356.     _add(root);
  357.     return _target_node->cont;
  358.   }
  359. }
  360.  
  361.  
  362. void <T><U>AVLAssoc::_del(<T><U>AVLAssocNode* par, <T><U>AVLAssocNode*& t)
  363. {
  364.   int comp = key_key_cmp(*_target_item, t->key);
  365.   if (comp == 0)
  366.   {
  367.     if (lthread(t) && rthread(t))
  368.     {
  369.       _mark_for_deletion = t;
  370.       if (t == par->lt)
  371.       {
  372.         set_lthread(par, 1);
  373.         par->lt = t->lt;
  374.       }
  375.       else
  376.       {
  377.         set_rthread(par, 1);
  378.         par->rt = t->rt;
  379.       }
  380.       _need_rebalancing = 1;
  381.       return;
  382.     }
  383.     else if (lthread(t))
  384.     {
  385.       _mark_for_deletion = t;
  386.       <T><U>AVLAssocNode* s = succ(t);
  387.       if (s != 0 && lthread(s))
  388.         s->lt = t->lt;
  389.       t = t->rt;
  390.       _need_rebalancing = 1;
  391.       return;
  392.     }
  393.     else if (rthread(t))
  394.     {
  395.       _mark_for_deletion = t;
  396.       <T><U>AVLAssocNode* p = pred(t);
  397.       if (p != 0 && rthread(p))
  398.         p->rt = t->rt;
  399.       t = t->lt;
  400.       _need_rebalancing = 1;
  401.       return;
  402.     }
  403.     else                        // replace item & find someone deletable
  404.     {
  405.       <T><U>AVLAssocNode* p = pred(t);
  406.       t->key = p->key;
  407.       t->cont = p->cont;
  408.       _target_item = &p->key;
  409.       comp = -1;                // fall through below to left
  410.     }
  411.   }
  412.  
  413.   if (comp < 0)
  414.   {
  415.     if (lthread(t))
  416.       return;
  417.     _del(t, t->lt);
  418.     if (!_need_rebalancing)
  419.       return;
  420.     switch (bf(t))
  421.     {
  422.     case AVLLEFTHEAVY:
  423.       set_bf(t, AVLBALANCED);
  424.       return;
  425.     case AVLBALANCED:
  426.       set_bf(t, AVLRIGHTHEAVY);
  427.       _need_rebalancing = 0;
  428.       return;
  429.     case AVLRIGHTHEAVY:
  430.       <T><U>AVLAssocNode* r = t->rt;
  431.       switch (bf(r))
  432.       {
  433.       case AVLBALANCED:
  434.         if (lthread(r))
  435.           t->rt = r;
  436.         else
  437.           t->rt = r->lt;
  438.         set_rthread(t, lthread(r));
  439.         r->lt = t;
  440.         set_lthread(r, 0);
  441.         set_bf(t, AVLRIGHTHEAVY);
  442.         set_bf(r, AVLLEFTHEAVY);
  443.         _need_rebalancing = 0;
  444.         t = r;
  445.         return;
  446.       case AVLRIGHTHEAVY:
  447.         if (lthread(r))
  448.           t->rt = r;
  449.         else
  450.           t->rt = r->lt;
  451.         set_rthread(t, lthread(r));
  452.         r->lt = t;
  453.         set_lthread(r, 0);
  454.         set_bf(t, AVLBALANCED);
  455.         set_bf(r, AVLBALANCED);
  456.         t = r;
  457.         return;
  458.       case AVLLEFTHEAVY:
  459.         <T><U>AVLAssocNode* l = r->lt;
  460.         set_lthread(r, rthread(l));
  461.         if (rthread(l))
  462.           r->lt = l;
  463.         else
  464.           r->lt = l->rt;
  465.         l->rt = r;
  466.         set_rthread(l, 0);
  467.         set_rthread(t, lthread(l));
  468.         if (lthread(l))
  469.           t->rt = l;
  470.         else
  471.           t->rt = l->lt;
  472.         l->lt = t;
  473.         set_lthread(l, 0);
  474.         if (bf(l) == AVLRIGHTHEAVY)
  475.           set_bf(t, AVLLEFTHEAVY);
  476.         else
  477.           set_bf(t, AVLBALANCED);
  478.         if (bf(l) == AVLLEFTHEAVY)
  479.           set_bf(r, AVLRIGHTHEAVY);
  480.         else
  481.           set_bf(r, AVLBALANCED);
  482.         set_bf(l, AVLBALANCED);
  483.         t = l;
  484.         return;
  485.       }
  486.     }
  487.   }
  488.   else
  489.   {
  490.     if (rthread(t))
  491.       return;
  492.     _del(t, t->rt);
  493.     if (!_need_rebalancing)
  494.       return;
  495.     switch (bf(t))
  496.     {
  497.     case AVLRIGHTHEAVY:
  498.       set_bf(t, AVLBALANCED);
  499.       return;
  500.     case AVLBALANCED:
  501.       set_bf(t, AVLLEFTHEAVY);
  502.       _need_rebalancing = 0;
  503.       return;
  504.     case AVLLEFTHEAVY:
  505.       <T><U>AVLAssocNode* l = t->lt;
  506.       switch (bf(l))
  507.       {
  508.       case AVLBALANCED:
  509.         if (rthread(l))
  510.           t->lt = l;
  511.         else
  512.           t->lt = l->rt;
  513.         set_lthread(t, rthread(l));
  514.         l->rt = t;
  515.         set_rthread(l, 0);
  516.         set_bf(t, AVLLEFTHEAVY);
  517.         set_bf(l, AVLRIGHTHEAVY);
  518.         _need_rebalancing = 0;
  519.         t = l;
  520.         return;
  521.       case AVLLEFTHEAVY:
  522.         if (rthread(l))
  523.           t->lt = l;
  524.         else
  525.           t->lt = l->rt;
  526.         set_lthread(t, rthread(l));
  527.         l->rt = t;
  528.         set_rthread(l, 0);
  529.         set_bf(t, AVLBALANCED);
  530.         set_bf(l, AVLBALANCED);
  531.         t = l;
  532.         return;
  533.       case AVLRIGHTHEAVY:
  534.         <T><U>AVLAssocNode* r = l->rt;
  535.         set_rthread(l, lthread(r));
  536.         if (lthread(r))
  537.           l->rt = r;
  538.         else
  539.           l->rt = r->lt;
  540.         r->lt = l;
  541.         set_lthread(r, 0);
  542.         set_lthread(t, rthread(r));
  543.         if (rthread(r))
  544.           t->lt = r;
  545.         else
  546.           t->lt = r->rt;
  547.         r->rt = t;
  548.         set_rthread(r, 0);
  549.         if (bf(r) == AVLLEFTHEAVY)
  550.           set_bf(t, AVLRIGHTHEAVY);
  551.         else
  552.           set_bf(t, AVLBALANCED);
  553.         if (bf(r) == AVLRIGHTHEAVY)
  554.           set_bf(l, AVLLEFTHEAVY);
  555.         else
  556.           set_bf(l, AVLBALANCED);
  557.         set_bf(r, AVLBALANCED);
  558.         t = r;
  559.         return;
  560.       }
  561.     }
  562.   }
  563. }
  564.  
  565.         
  566. int <T><U>AVLAssoc::del(<T&> key)
  567. {
  568.   _need_rebalancing = 0;
  569.   _mark_for_deletion = 0;
  570.   _target_item = &key;
  571.   _del(root, root);
  572.   if (_mark_for_deletion)
  573.   {
  574.     delete(_mark_for_deletion);
  575.     --cnt;
  576.     return 1;
  577.   }
  578.   else
  579.     return 0;
  580. }
  581.  
  582. // build an ordered array of pointers to tree nodes back into a tree
  583. // we know that at least one element exists
  584.  
  585. static <T><U>AVLAssocNode* _do_treeify(int lo, int hi, int& h)
  586. {
  587.   int lh, rh;
  588.   int mid = (lo + hi) / 2;
  589.   <T><U>AVLAssocNode* t = _hold_nodes[mid];
  590.   if (lo > mid - 1)
  591.   {
  592.     set_lthread(t, 1);
  593.     if (mid == 0)
  594.       t->lt = 0;
  595.     else
  596.       t->lt = _hold_nodes[mid-1];
  597.     lh = 0;
  598.   }
  599.   else
  600.   {
  601.     set_lthread(t, 0);
  602.     t->lt = _do_treeify(lo, mid-1, lh);
  603.   }
  604.   if (hi < mid + 1)
  605.   {
  606.     set_rthread(t, 1);
  607.     if (mid == _max_hold_index)
  608.       t->rt = 0;
  609.     else
  610.       t->rt = _hold_nodes[mid+1];
  611.     rh = 0;
  612.   }
  613.   else 
  614.   {
  615.     set_rthread(t, 0);
  616.     t->rt = _do_treeify(mid+1, hi, rh);
  617.   }
  618.   if (lh == rh)
  619.   {
  620.     set_bf(t, AVLBALANCED);
  621.     h = lh + 1;
  622.   }
  623.   else if (lh == rh - 1)
  624.   {
  625.     set_bf(t, AVLRIGHTHEAVY);
  626.     h = rh + 1;
  627.   }
  628.   else if (rh == lh - 1)
  629.   {
  630.     set_bf(t, AVLLEFTHEAVY);
  631.     h = lh + 1;
  632.   }
  633.   else                          // can't happen
  634.     abort();
  635.  
  636.   return t;
  637. }
  638.  
  639. static <T><U>AVLAssocNode* _treeify(int n)
  640. {
  641.   <T><U>AVLAssocNode* t;
  642.   if (n == 0)
  643.     t = 0;
  644.   else
  645.   {
  646.     int b;
  647.     _max_hold_index = n-1;
  648.     t = _do_treeify(0, _max_hold_index, b);
  649.   }
  650.   delete _hold_nodes;
  651.   return t;
  652. }
  653.  
  654.  
  655. void <T><U>AVLAssoc::_kill(<T><U>AVLAssocNode* t)
  656. {
  657.   if (t != 0)
  658.   {
  659.     if (!lthread(t)) _kill(t->lt);
  660.     if (!rthread(t)) _kill(t->rt);
  661.     delete t;
  662.   }
  663. }
  664.  
  665.  
  666. <T><U>AVLAssoc::<T><U>AVLAssoc(<T><U>AVLAssoc& b)
  667. {
  668.   if ((cnt = b.cnt) == 0)
  669.   {
  670.     root = 0;
  671.   }
  672.   else
  673.   {
  674.     _hold_nodes = new <T><U>AVLAssocNodePtr [cnt];
  675.     <T><U>AVLAssocNode* t = b.leftmost();
  676.     int i = 0;
  677.     while (t != 0)
  678.     {
  679.       _hold_nodes[i++] = new <T><U>AVLAssocNode(t->key, t->cont);
  680.       t = b.succ(t);
  681.     }
  682.     root = _treeify(cnt);
  683.   }
  684. }
  685.  
  686. <T><U>AVLAssoc& <T><U>AVLAssoc:: operator = (<T><U>AVLAssoc& b)
  687. {
  688.   if (b.root != root)
  689.   {
  690.     clear();
  691.     if ((cnt = b.cnt) == 0)
  692.       root = 0;
  693.     else
  694.     {
  695.       _hold_nodes = new <T><U>AVLAssocNodePtr [cnt];
  696.       <T><U>AVLAssocNode* t = b.leftmost();
  697.       int i = 0;
  698.       while (t != 0)
  699.       {
  700.         _hold_nodes[i++] = new <T><U>AVLAssocNode(t->key, t->cont);
  701.         t = b.succ(t);
  702.       }
  703.       root = _treeify(cnt);
  704.     }
  705.   }
  706. }
  707.  
  708.