home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / gnu / g__lib / splaymap.ccp < prev    next >
Encoding:
Text File  |  1993-07-23  |  7.8 KB  |  405 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>.<C>.SplayMap.h"
  27.  
  28.  
  29. /* 
  30.  
  31.  struct to simulate the special `null' node in the Sleater & Tarjan JACM 1985
  32.  splay tree algorithms
  33.  
  34.  All routines use a version of their `simple top-down' splay alg. (p 669)
  35.  
  36. */
  37.  
  38. struct _dummySplayNode
  39. {
  40.   <T><C>SplayNode*    lt;
  41.   <T><C>SplayNode*    rt;
  42.   <T><C>SplayNode*    par;
  43. } _dummy_null;
  44.  
  45.  
  46. /*
  47.  traversal primitives
  48. */
  49.  
  50.  
  51. <T><C>SplayNode* <T><C>SplayMap::leftmost()
  52. {
  53.   <T><C>SplayNode* t = root;
  54.   if (t != 0) while (t->lt != 0) t = t->lt;
  55.   return t;
  56. }
  57.  
  58. <T><C>SplayNode* <T><C>SplayMap::rightmost()
  59. {
  60.   <T><C>SplayNode* t = root;
  61.   if (t != 0) while (t->rt != 0) t = t->rt;
  62.   return t;
  63. }
  64.  
  65. <T><C>SplayNode* <T><C>SplayMap::succ(<T><C>SplayNode* t)
  66. {
  67.   if (t == 0)
  68.     return 0;
  69.   if (t->rt != 0)
  70.   {
  71.     t = t->rt;
  72.     while (t->lt != 0) t = t->lt;
  73.     return t;
  74.   }
  75.   else
  76.   {
  77.     for (;;)
  78.     {
  79.       if (t->par == 0 || t == t->par->lt)
  80.         return t->par;
  81.       else
  82.         t = t->par;
  83.     }
  84.   }
  85. }
  86.  
  87. <T><C>SplayNode* <T><C>SplayMap::pred(<T><C>SplayNode* t)
  88. {
  89.   if (t == 0)
  90.     return 0;
  91.   else if (t->lt != 0)
  92.   {
  93.     t = t->lt;
  94.     while (t->rt != 0) t = t->rt;
  95.     return t;
  96.   }
  97.   else
  98.   {
  99.     for (;;)
  100.     {
  101.       if (t->par == 0 || t == t->par->rt)
  102.         return t->par;
  103.       else
  104.         t = t->par;
  105.     }
  106.   }
  107. }
  108.  
  109.  
  110. Pix <T><C>SplayMap::seek(<T&> key)
  111. {
  112.   <T><C>SplayNode* t = root;
  113.   if (t == 0)
  114.     return 0;
  115.  
  116.   int comp = <T>CMP(key, t->item);
  117.   if (comp == 0)
  118.     return Pix(t);
  119.  
  120.   <T><C>SplayNode* dummy = (<T><C>SplayNode*)(&_dummy_null);
  121.   <T><C>SplayNode* l = dummy;
  122.   <T><C>SplayNode* r = dummy;
  123.   dummy->rt = dummy->lt = dummy->par = 0;
  124.  
  125.   while (comp != 0)
  126.   {
  127.     if (comp > 0)
  128.     {
  129.       <T><C>SplayNode* tr = t->rt;
  130.       if (tr == 0)
  131.         break;
  132.       else
  133.       {
  134.         comp = <T>CMP(key, tr->item);
  135.         if (comp <= 0 || tr->rt == 0)
  136.         {
  137.           l->rt = t; t->par = l;
  138.           l = t;
  139.           t = tr;
  140.           if (comp >= 0)
  141.             break;
  142.         }
  143.         else
  144.         {
  145.           if ((t->rt = tr->lt) != 0) t->rt->par = t;
  146.           tr->lt = t; t->par = tr;
  147.           l->rt = tr; tr->par = l;
  148.           l = tr;
  149.           t = tr->rt;
  150.           comp = <T>CMP(key, t->item);
  151.         }
  152.       }
  153.     }
  154.     else
  155.     {
  156.       <T><C>SplayNode* tl = t->lt;
  157.       if (tl == 0)
  158.         break;
  159.       else
  160.       {
  161.         comp = <T>CMP(key, tl->item);
  162.         if (comp >= 0 || tl->lt == 0)
  163.         {
  164.           r->lt = t; t->par = r;
  165.           r = t;
  166.           t = tl;
  167.           if (comp <= 0)
  168.             break;
  169.         }
  170.         else
  171.         {
  172.           if ((t->lt = tl->rt) != 0) t->lt->par = t;
  173.           tl->rt = t; t->par = tl;
  174.           r->lt = tl; tl->par = r;
  175.           r = tl;
  176.           t = tl->lt;
  177.           comp = <T>CMP(key, t->item);
  178.         }
  179.       }
  180.     }
  181.   }
  182.   if ((r->lt = t->rt) != 0) r->lt->par = r;
  183.   if ((l->rt = t->lt) != 0) l->rt->par = l;
  184.   if ((t->lt = dummy->rt) != 0) t->lt->par = t;
  185.   if ((t->rt = dummy->lt) != 0) t->rt->par = t;
  186.   t->par = 0;
  187.   root = t;
  188.   return (comp == 0) ? Pix(t) : 0;
  189. }
  190.  
  191.  
  192. <C>& <T><C>SplayMap::operator [] (<T&> item)
  193. {
  194.   <T><C>SplayNode* t = root;
  195.   if (t == 0)
  196.   {
  197.     ++count;
  198.     root = new <T><C>SplayNode(item, def);
  199.     return root->cont;
  200.   }
  201.   int comp = <T>CMP(item, t->item);
  202.   if (comp == 0)
  203.     return t->cont;
  204.  
  205.   <T><C>SplayNode* dummy = (<T><C>SplayNode*)(&_dummy_null);
  206.   <T><C>SplayNode* l = dummy;
  207.   <T><C>SplayNode* r = dummy;
  208.   dummy->rt = dummy->lt = dummy->par = 0;
  209.  
  210.   while (comp != 0)
  211.   {
  212.     if (comp > 0)
  213.     {
  214.       <T><C>SplayNode* tr = t->rt;
  215.       if (tr == 0)
  216.       {
  217.         ++count;
  218.         tr = new <T><C>SplayNode(item, def);
  219.         comp = 0;
  220.       }
  221.       else
  222.         comp = <T>CMP(item, tr->item);
  223.         
  224.       if (comp <= 0)
  225.       {
  226.         l->rt = t; t->par = l;
  227.         l = t;
  228.         t = tr;
  229.       }
  230.       else 
  231.       {
  232.         <T><C>SplayNode* trr = tr->rt;
  233.         if (trr == 0)
  234.         {
  235.           ++count;
  236.           trr =  new <T><C>SplayNode(item, def);
  237.           comp = 0;
  238.         }
  239.         else
  240.           comp = <T>CMP(item, trr->item);
  241.  
  242.         if ((t->rt = tr->lt) != 0) t->rt->par = t;
  243.         tr->lt = t; t->par = tr;
  244.         l->rt = tr; tr->par = l;
  245.         l = tr;
  246.         t = trr;
  247.       }
  248.     }
  249.     else
  250.     {
  251.       <T><C>SplayNode* tl = t->lt;
  252.       if (tl == 0)
  253.       {
  254.         ++count;
  255.         tl = new <T><C>SplayNode(item, def);
  256.         comp = 0;
  257.       }
  258.       else
  259.         comp = <T>CMP(item, tl->item);
  260.  
  261.       if (comp >= 0)
  262.       {
  263.         r->lt = t; t->par = r;
  264.         r = t;
  265.         t = tl;
  266.       }
  267.       else
  268.       {
  269.         <T><C>SplayNode* tll = tl->lt;
  270.         if (tll == 0)
  271.         {
  272.           ++count;
  273.           tll = new <T><C>SplayNode(item, def);
  274.           comp = 0;
  275.         }
  276.         else
  277.           comp = <T>CMP(item, tll->item);
  278.  
  279.         if ((t->lt = tl->rt) != 0) t->lt->par = t;
  280.         tl->rt = t; t->par = tl;
  281.         r->lt = tl; tl->par = r;
  282.         r = tl;
  283.         t = tll;
  284.       }
  285.     }
  286.   }
  287.   if ((r->lt = t->rt) != 0) r->lt->par = r;
  288.   if ((l->rt = t->lt) != 0) l->rt->par = l;
  289.   if ((t->lt = dummy->rt) != 0) t->lt->par = t;
  290.   if ((t->rt = dummy->lt) != 0) t->rt->par = t;
  291.   t->par = 0;
  292.   root = t;
  293.   return root->cont;
  294. }
  295.  
  296. void <T><C>SplayMap::del(<T&> key)
  297. {
  298.   <T><C>SplayNode* t = (<T><C>SplayNode*)(seek(key));
  299.   if (t == 0) return;
  300.  
  301.   <T><C>SplayNode* p = t->par;
  302.  
  303.   --count;
  304.   if (t->rt == 0)
  305.   {
  306.     if (t == root)
  307.     {
  308.       if ((root = t->lt) != 0) root->par = 0;
  309.     }
  310.     else if (t == p->lt)
  311.     {
  312.       if ((p->lt = t->lt) != 0) p->lt->par = p;
  313.     }
  314.     else
  315.       if ((p->rt = t->lt) != 0) p->rt->par = p;
  316.   }
  317.   else
  318.   {
  319.     <T><C>SplayNode* r = t->rt;
  320.     <T><C>SplayNode* l = r->lt;
  321.     for(;;)
  322.     {
  323.       if (l == 0)
  324.       {
  325.         if (t == root)
  326.         {
  327.           root = r;
  328.           r->par = 0;
  329.         }
  330.         else if (t == p->lt) 
  331.         {
  332.           p->lt = r;
  333.           r->par = p;
  334.         }
  335.         else
  336.         {
  337.           p->rt = r;
  338.           r->par = p;
  339.         }
  340.         if ((r->lt = t->lt) != 0) r->lt->par = r;
  341.         break;
  342.       }
  343.       else
  344.       {
  345.         if ((r->lt = l->rt) != 0) r->lt->par = r;
  346.         l->rt = r; r->par = l;
  347.         r = l;
  348.         l = l->lt;
  349.       }
  350.     }
  351.   }
  352.   delete t;
  353. }
  354.  
  355.  
  356. void <T><C>SplayMap::_kill(<T><C>SplayNode* t)
  357. {
  358.   if (t != 0)
  359.   {
  360.     _kill(t->lt);
  361.     _kill(t->rt);
  362.     delete t;
  363.   }
  364. }
  365.  
  366.  
  367. <T><C>SplayNode* <T><C>SplayMap::_copy(<T><C>SplayNode* t)
  368. {
  369.   if (t != 0)
  370.   {
  371.     <T><C>SplayNode* l = _copy(t->lt);
  372.     <T><C>SplayNode* r = _copy(t->rt);
  373.     <T><C>SplayNode* x = new <T><C>SplayNode(t->item, t->cont, l, r);
  374.     if (l != 0) l->par = x;
  375.     if (r != 0) r->par = x;
  376.     return x;
  377.   }
  378.   else 
  379.     return 0;
  380. }
  381.  
  382.  
  383. int <T><C>SplayMap::OK()
  384. {
  385.   int v = 1;
  386.   if (root == 0) 
  387.     v = count == 0;
  388.   else
  389.   {
  390.     int n = 1;
  391.     <T><C>SplayNode* trail = leftmost();
  392.     <T><C>SplayNode* t = succ(trail);
  393.     while (t != 0)
  394.     {
  395.       ++n;
  396.       v &= <T>CMP(trail->item, t->item) < 0;
  397.       trail = t;
  398.       t = succ(t);
  399.     }
  400.     v &= n == count;
  401.   }
  402.   if (!v) error("invariant failure");
  403.   return v;
  404. }
  405.