开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
_eb_tree.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：14k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

_eb_tree.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _eb_tree.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. #include <LEDA/impl/eb_tree.h>
  16. // Stefan  Naeher ( 1989 )
  17. // Michael Wenzel ( 1990 ) 
  20. // ----------------------------------------------------------
  21. //
  22. // Konstruktor & Destruktor
  23. //
  25. l_stratified::l_stratified(stratified_ptr b, int x)
  26. {
  27.   int t = b->min2();
  29.   if ( x == b->min() )
  30.   {
  31.     ma = t;
  32.     mi = b->max();
  33.   }
  35.   if ( x == t )
  36.   {
  37.     ma = b->min();
  38.     mi = b->max();
  39.   }
  41.   if ( x == b->max() )
  42.   {
  43.     ma = b->min();
  44.     mi = t;
  45.   }
  47. }
  50. stratified::stratified(int i)  
  51. { 
  53.   mi = ma = -1;
  54.   sz = 0; 
  55.   k = i;
  56.   top = 0;
  57.   bot = 0;
  59. }
  61. stratified::stratified(l_stratified_ptr l, int i)
  62. { 
  64.   mi = l->min();
  65.   ma = l->max();
  66.   sz = 2;
  67.   k = i;
  68.   top = 0;
  69.   bot = 0;
  71. }
  74. stratified::~stratified()  
  75. { 
  76.                                          // deallocate memory of sub-structures
  77.   if ((k>1) && (sz>2))
  78.   {                                      // delete stratified trees of bot
  79.     bot->clear(k);
  81.     if ( k <= 8 )
  82.       delete bot->l;
  83.     else
  84.       delete bot->d;
  85.     delete bot;
  87.     if ( top->size() <= 2 )
  88.       delete top;
  89.     else
  90.       delete (stratified_ptr)top;
  92.     top = 0;
  93.     bot = 0;
  95.   }
  97. }
  99. // ----------------------------------------------------------
  100. //
  101. // min2                  
  102. //
  103. // liefert 2. kleinstes Element, falls sz > 2
  104. //
  105. // -1 , sonst
  106. //
  107. // ----------------------------------------------------------
  109. int stratified::min2()
  111. {
  112.   if ( sz < 3 )
  113.     return -1;
  115.   int z = top->min();
  116.   l_stratified_ptr l_bot_ptr = l_stratified_ptr(bot->lookup(z,k));
  118.   return (mal_pot_2(z,down(k))) | (l_bot_ptr->min());
  120. }
  123. // ----------------------------------------------------------
  124. //
  125. // max2                  
  126. //
  127. // liefert 2. groesstes Element, falls sz > 2
  128. //
  129. // -1 , sonst
  130. //
  131. // ----------------------------------------------------------
  133. int stratified::max2()
  135. {
  136.   if ( sz < 3 )
  137.     return -1;
  139.   int z = top->max();
  140.   l_stratified_ptr l_bot_ptr = l_stratified_ptr(bot->lookup(z,k));
  142.   return (mal_pot_2(z,down(k))) | (l_bot_ptr->max());
  144. }
  147. // ----------------------------------------------------------
  148. //
  149. // succ                  
  150. //
  151. // liefert Nachfolger von x im Baum auf dieser Rekursionsstufe
  152. //                    falls existiert
  153. // -1 , sonst
  154. //
  155. // ----------------------------------------------------------
  157. int stratified::succ(int x) 
  159. {
  160.   if ( x >= ma ) return -1;
  161.   if ( x <  mi ) return mi;
  162.   if ( sz == 2 ) return ma;               // mi < x < ma
  164.                                           // sz >= 2 &&  k>1
  165.   int x1 = high_bits(x); 
  166.   int x2 = low_bits(x); 
  168.   GenPtr p = bot->lookup(x1,k);
  169.   l_stratified_ptr l_bot_ptr = l_stratified_ptr(p);
  171.   if ( (l_bot_ptr) && (l_bot_ptr->max()>x2) )
  172.   { 
  173.     if ( l_bot_ptr->size() <= 2 )             // l_stratified Struktur
  174.         return ( mal_pot_2(x1,down(k))) | ( l_bot_ptr->succ(x2) ) ;
  175.     else
  176.     {
  177.       stratified_ptr bot_ptr = stratified_ptr(p) ;
  178.       return (mal_pot_2(x1,down(k))) | (bot_ptr->succ(x2)) ;
  179.     }
  180.   }
  181.   else                                   // succ nicht in bot-Unterstruktur
  182.   {
  183.     int z;
  184.     
  185.     if ( top->size() <= 2 )
  186.       z = top->succ(x1); 
  187.     else
  188.       z = ((stratified_ptr)top)->succ(x1); 
  190.     if ( z == -1 ) 
  191.       return ma;                         // x unmittelbar vor Maximum
  193.     l_stratified_ptr l_bot_ptr = l_stratified_ptr(bot->lookup(z,k));
  195.     return (mal_pot_2(z,down(k))) | (l_bot_ptr->min()) ;
  196.   }
  198. }
  200. // ----------------------------------------------------------
  201. //
  202. // pred                  
  203. //
  204. // liefert Vorgaenger von x im Baum auf dieser Rekursionsstufe
  205. //                    falls existiert
  206. // -1 , sonst
  207. //
  208. // ----------------------------------------------------------
  210. int stratified::pred(int x) 
  212. {
  213.   if ( x >  ma ) return ma;
  214.   if ( x <= mi ) return -1;
  215.   if ( sz == 2 ) return mi;               // mi < x < ma
  217.   // sz > 2 && k > 1
  218.   int x1 = high_bits(x); 
  219.   int x2 = low_bits(x); 
  221.   GenPtr p = bot->lookup(x1,k);
  222.   l_stratified_ptr l_bot_ptr = l_stratified_ptr(p);
  224.   if ( (l_bot_ptr) && (l_bot_ptr->min()<x2) ) 
  225.   {
  226.     if ( l_bot_ptr->size() <= 2 )             // l_stratified Struktur
  227.         return ( mal_pot_2(x1,down(k))) | ( l_bot_ptr->pred(x2) ) ;
  228.     else
  229.     {
  230.       stratified_ptr bot_ptr = stratified_ptr(p) ;
  231.       return (mal_pot_2(x1,down(k))) | (bot_ptr->pred(x2)) ;
  232.     }
  233.   }
  235.   else                                        // pred nicht in top-Unterstruktur
  236.     
  237.   {
  238.     int z;
  240.     if ( top->size() <= 2 )
  241.       z = top->pred(x1); 
  242.     else
  243.       z = ((stratified_ptr)top)->pred(x1); 
  245.     if ( z == -1 ) 
  246.       return mi;                              // x unmittelbar vor Maximum
  248.     l_stratified_ptr l_bot_ptr = l_stratified_ptr(bot->lookup(z,k));
  250.     return (mal_pot_2(z,down(k))) | (l_bot_ptr->max() ) ;
  251.   }
  253. } 
  255. // --------------------------------------------------------------- 
  256. //
  257. // member   
  258. //
  259. // liefert 1, falls Element in der Struktur
  260. //
  261. //         0, sonst
  262. //
  263. // ----------------------------------------------------------
  265. int stratified::member(int x)
  266. { 
  267.   if (( x == ma )||( x == mi ))
  268.     return 1;
  270.   if (( x < mi )||( x > ma ))
  271.     return 0;
  273.   if ( sz == 2 )
  274.     return 0;
  276.      // sz > 2 && k > 1
  277.   int x1 = high_bits(x); 
  278.   int x2 = low_bits(x); 
  280.   GenPtr p = bot->lookup(x1,k);
  281.   l_stratified_ptr l_bot_ptr = l_stratified_ptr(p);
  283.   if (l_bot_ptr)
  285.     if ( l_bot_ptr->size() <= 2 )    // l_stratified Struktur
  286.       return l_bot_ptr->member(x2);
  288.     else
  289.     {
  290.       stratified_ptr bot_ptr = stratified_ptr(p);
  291.       return bot_ptr->member(x2);                  
  292.     }
  294.   else
  295.     return 0;                
  297. }
  299. // ----------------------------------------------------------
  300. //
  301. // insert           
  302. //
  303. // fuegt ein Element x rekursiv in den Baum ein
  304. //
  305. // liefert 1, falls es eingefuegt wurde
  306. //
  307. //         0, falls es schon Element dewr Struktur war
  308. //
  309. // ----------------------------------------------------------
  311. int stratified::insert(int x)
  312. { 
  313.   int inserted = 0;
  315.   if ( ( x == mi ) || ( x == ma ) )      // Element in Structure
  316.     return 0;
  318.   switch (sz)
  319.   {
  321.     case 0: 
  322.      {
  323.        mi = ma = x;
  325.        inserted = 1;
  326.                break;
  327.              }
  329.     case 1:
  330.      {                           // incremental construction iff sz > 2
  331.                if ( x > mi ) 
  332.          ma = x;
  333.        else
  334.          mi = x;
  336.        inserted = 1;
  337.                break;
  338.              }
  340.     default: {                           // => k>1
  342.        if ( x > ma )
  343.        { 
  344.  int t = ma;
  345.  ma = x;
  346.  x = t;
  347.                }
  348.  
  349.                if ( x < mi )
  350.        { 
  351.  int t = mi;
  352.  mi = x;
  353.  x = t;
  354.                }
  356.                int x1 = high_bits(x);
  357.                int x2 = low_bits(x);
  359.                                          // for incremental construction
  361.                if ( top == 0 )           // allocate new structures
  362.                { 
  363.          top = new l_stratified(); 
  364.                  bot = new b_dict(k);
  365.                }          
  367.                GenPtr& p = bot->lookup(x1,k);
  368.                l_stratified_ptr l_bot_ptr = l_stratified_ptr(p);
  370.        if ( l_bot_ptr )
  371.                {
  372.                  if ( l_bot_ptr->size() == 1 )
  373.    inserted = l_bot_ptr->insert(x2);
  374.  else
  375.                  {
  376.    stratified_ptr bot_ptr;
  378.    if ( l_bot_ptr->size() == 2 ) 
  379.                    {
  380.      if ( !l_bot_ptr->member(x2) ) 
  381.                      {
  382.        bot_ptr = new stratified(l_bot_ptr,down(k));
  383.                        inserted = bot_ptr->insert(x2);
  385.        p = (GenPtr)bot_ptr;
  387.        delete l_bot_ptr;
  388.                      }
  389.                    }
  390.    else       // l_bot_ptr was a bot_ptr
  391.                    {
  392.                      bot_ptr = stratified_ptr(p) ;
  393.                      inserted = bot_ptr->insert(x2);
  394.                    }
  395.                  }
  397.                }
  398.                else                // no top entry 
  399.        {
  400.                  l_bot_ptr = new l_stratified(x2);
  402.  if ( top->size() <= 1 )
  403.    top->insert(x1);
  404.                  else
  405.                  { 
  406.    stratified_ptr ntop;
  408.    if ( top->size() == 2 )
  409.    { 
  410.      ntop = new stratified(top,up(k));
  411.      delete top;
  412.      top = (l_stratified_ptr)ntop;
  413.                    }
  414.    else
  415.      ntop = (stratified_ptr)top;
  417.            ntop->insert(x1);
  418.                  }
  420.          GenPtr help = GenPtr(l_bot_ptr);
  421.          bot->insert(x1,help,k);
  422.  inserted = 1;
  423.                }
  424.                break;
  425.              }                           // default case
  427.   }                                      // switch
  429.   if ( inserted )
  430.     sz++;
  432.   return inserted;
  434. }
  436. // ----------------------------------------------------------
  437. //
  438. // del              
  439. //
  440. // streicht ein Element x rekursiv aus dem Baum 
  441. //
  442. // liefert 1, falls es gestrichen wurde
  443. //
  444. //         0, falls es nicht Element der Struktur war
  445. //
  446. // ----------------------------------------------------------
  448. int stratified::del(int x)
  450. { 
  452.   int deleted = 0;
  454.   switch (sz)
  455.   {
  457.     case 0 : break;
  459.     case 1 :
  460.      { 
  461.                if ( x == mi )
  462.        { 
  463.          mi = ma = -1;
  464.  deleted = 1;
  465.                }
  466.        break;
  467.              }
  471.     case 2 :
  472.              {
  473.                if ( x == mi ) 
  474.                {
  475.          mi = ma;
  476.          deleted = 1;
  477.        }
  479.                if ( x == ma )
  480.                {
  481.          ma = mi;
  482.          deleted = 1;
  483.        }
  485.        break;
  486.              }
  488.     case 3 :       
  489.                                    /* delete incremental construction */
  490.              {           
  491.                int t = min2();     /* third element */
  493.                if ( x == mi )      /* new minimum   */
  494.                {
  495.           mi = t;
  496.   deleted = 1;
  497.                }
  499.                if ( x == ma )      /* new maximum   */
  500.                {
  501.           ma = t;
  502.   deleted = 1;
  503.                }
  505.        if ( x == t )
  506.  deleted = 1;
  508.                if ( deleted )
  509.                 /* delete stratified trees of bot  */
  510.                {
  511.                  bot->clear(k);
  512.  if ( k <= 8 )
  513.                    delete bot->l;
  514.                  else
  515.                    delete bot->d;
  516.                  delete bot;
  517.                  bot = 0;
  519.                  delete top;
  520.                  top = 0;
  521.                }                   /* incremental construction deleted */
  523.        break;
  524.              }         
  526.     default :
  527.              {
  528.        l_stratified_ptr l_bot_ptr;
  529.        stratified_ptr bot_ptr;
  531.                if ( x == ma )                 /* delete maximum */
  532.                {
  533.  int z = max2();
  534.  ma = z;
  535.          x = z;
  536.                }
  538.                if ( x == mi )                /* delete minimum */
  539.                {
  540.  int z = min2();
  541.  mi = z;
  542.          x = z;
  543.                }
  545.                int x1 = high_bits(x);
  546.                int x2 = low_bits(x);
  548.                GenPtr& p = bot->lookup(x1,k);
  550.        if (!p)
  551.  return 0;                  /* element not in structure */
  553.                l_bot_ptr = l_stratified_ptr(p) ;
  555.                if ( l_bot_ptr->size() <= 2 )
  556.        {
  557.                  deleted = l_bot_ptr->del(x2);
  559.                  if ( l_bot_ptr->size() == 0 )  /* delete structure */
  560.          {
  561.                    delete l_bot_ptr;
  562.   
  563.    if ( top->size() <= 2 )
  564.      top->del(x1);
  565.                    else
  566.    {
  567.      stratified_ptr ntop = (stratified_ptr)top;
  568.      if ( ntop->sz == 3 )
  569.      { 
  570.        top = new l_stratified(ntop,x1);
  571.        delete ntop;
  572.                      }
  573.      else
  574.                        ntop->del(x1);
  575.                    } 
  577.                    bot->del(x1,k);
  578.                  }
  579.                }
  581.                else                                  /* stratified structure */
  582.                {
  583.                  bot_ptr = stratified_ptr(p) ;
  585.                  if ( bot_ptr->sz == 3 )              /* change into l_stratified */
  586.                  {
  587.    if ( bot_ptr->member(x2) )
  588.    {
  589.      l_bot_ptr = new l_stratified(bot_ptr,x2);
  590.      deleted = 1;
  592.                      p = (GenPtr)l_bot_ptr;
  594.                      delete bot_ptr;
  596.                    }
  597.                  }
  598.                  else                               /* size >= 4 */
  599.                    deleted = bot_ptr->del(x2);
  600.                }
  602.        break;
  603.              }
  605.   }
  607.   if ( deleted ) 
  608.     sz--;
  610.   return deleted;
  611. }
  613. // ----------------------------------------------------------
  614. //
  615. // print            
  616. //
  617. // druckt alle Elemente des Baumes aus            
  618. //
  619. // ----------------------------------------------------------
  621. void stratified::print()
  622. { 
  623.   int i = -1;
  624.   while ((i=succ(i))>=0)
  625.     cout << i << " ";
  626. }
  628. // -------------------------------------------------------
  629. // clear
  630. //
  631. // loescht alle Elemente, zerstoert Unterbaeume und 
  632. // setzt Dictionary auf Leerzustand
  633. //
  634. // ----------------------------------------------------------
  636. b_dict::b_dict(int k) 
  637. { if ( k <= 8 ) 
  638.    { l = new GenPtr[pot_2(up(k))];
  639.      for (int i = 0; i < pot_2(up(k)); i++) l[i] = 0;
  640.     }
  641.   else 
  642.    d = new dp_hash;
  643. }
  645. void b_dict::clear(int k)
  646. { 
  647.   if ( k <= 8 )
  648.   {
  649.     for (int i = 0; i < pot_2(up(k)); i++)
  650.     { 
  651.       l_stratified_ptr l_bot_ptr=l_stratified_ptr(l[i]);
  652.       if  (l_bot_ptr)
  653.         if (l_bot_ptr->size()<=2) 
  654.           delete l_bot_ptr;
  655.         else
  656.         { 
  657.           stratified_ptr bot_ptr=stratified_ptr(l[i]);
  658.           delete bot_ptr;
  659.         }
  660.     }
  662.     return;
  663.   }
  664.       
  665.                          // b_dict was a hashing structure
  668.   stp s = new subtable[d->n];
  669.   stp pos = s;
  670.   int i=0;
  672.   while (i<d->sM)                        // Headertables loeschen
  673.   {
  674.     if (d->htablep[i])
  675.     {
  676.       d->htablep[i]->give_elements(pos,d->anf,d->ende);
  677.       delete d->htablep[i];                         
  678.     }
  679.     i++;
  680.   }
  682.   for (i=0 ; i<d->n ; i++)
  683.   { 
  684.     l_stratified_ptr l_bot_ptr=l_stratified_ptr(s[i].info());
  685.     if  (l_bot_ptr)
  686.       if (l_bot_ptr->size()<=2) 
  687.         delete l_bot_ptr;
  688.       else
  689.       { 
  690.         stratified_ptr bot_ptr=stratified_ptr(s[i].info());
  691.         delete bot_ptr;
  692.       }
  693.   }
  695.   // free ((char*)d->htablep) ;             // Speicher freigeben
  697.   delete[] d->htablep;
  699.   if (d->anf)
  700.     delete d->anf;
  702.   delete s;
  704.   d->n = 0;                              // Leerinitialisierung
  705.   d->M=4;
  706.   d->sM=13;
  707.   d->k= 1 + (rand_int() & maxprim);
  708.   d->bed=-17;
  709.   d->htablep= new htp[d->sM];   //calloc(d->sM,sizeof(htp));
  710.   d->anf = d->wo = d->ende = 0;
  712. }