home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / basic / _tree_co.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  12.3 KB  |  578 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _tree_collection.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. // dyna_trees.c
  18.  
  19. #include <LEDA/tree_collection.h>
  20.  
  21. #define BIG MAXFLOAT
  22.  
  23.  
  24.  
  25. void dyna_trees::splay(d_vertex x) {
  26.      d_vertex y, z, zz, a, b, c, d;
  27.      double   mincost_a,
  28.           mincost_b,
  29.           mincost_c,
  30.           mincost_d,
  31.           mincost_x,
  32.           mincost_y,
  33.           mincost_z,
  34.           
  35.           cost_x,
  36.           cost_y,
  37.           cost_z;
  38.  
  39.      
  40.      while (x->parent) {
  41.       // splay-step : 
  42.  
  43.       y=x->parent; // Vater von x
  44.       z=y->parent; // Grossvater von x (oder 0)
  45.       zz = (z==0) ? 0 : z->parent; // Urgrossvater von z (oder 0)
  46.  
  47.       // 1.Fall: x hat Vater, aber keinen Grossvater
  48.  
  49.       if (z==0){ 
  50.         if (y->left==x) { 
  51.             // x wurzel des linken unterbaums  (1)
  52.             a=x->left;
  53.             b=x->right;
  54.             c=y->right;
  55.             x->parent=0;
  56.             x->right=y;
  57.             y->parent=x;
  58.             y->left=b;
  59.             if (b) b->parent=y;
  60.  
  61.             x->successor=y->successor;
  62.             y->successor=0;
  63.  
  64.             mincost_a = (a) ? a->dmin + x->dmin + y->dmin : BIG;
  65.             mincost_b = (b) ? b->dmin + x->dmin + y->dmin : BIG;
  66.             mincost_c = (c) ? c->dmin + y->dmin : BIG;
  67.             mincost_x = x->dmin + y->dmin;
  68.             mincost_y = y->dmin;
  69.             cost_x    = x->dcost + mincost_x;
  70.             cost_y    = y->dcost + mincost_y;
  71.             
  72.             mincost_x = mincost_y;
  73.             mincost_y = (mincost_b <= mincost_c) ? mincost_b : mincost_c;
  74.             if (cost_y <= mincost_y) mincost_y = cost_y;
  75.             x->dcost = cost_x - mincost_x;
  76.             y->dcost = cost_y - mincost_y;
  77.             x->dmin  = mincost_x;
  78.             y->dmin  = mincost_y - mincost_x;
  79.             if (a) a->dmin  = mincost_a - mincost_x;
  80.             if (b) b->dmin  = mincost_b - mincost_y;
  81.             if (c) c->dmin  = mincost_c - mincost_y;
  82.         }
  83.         else {
  84.             // x wurzel des rechten unterbaums (2)
  85.             a=y->left;
  86.             b=x->left;
  87.             c=x->right;
  88.             x->parent=0;
  89.             x->left=y;
  90.             y->parent=x;
  91.             y->right=b;
  92.             if (b) b->parent=y;
  93.             
  94.             x->successor=y->successor;
  95.             y->successor=0;
  96.             
  97.             mincost_a = (a) ? a->dmin + y->dmin : BIG;
  98.             mincost_b = (b) ? b->dmin + x->dmin + y->dmin : BIG;
  99.             mincost_c = (c) ? c->dmin + x->dmin + y->dmin : BIG;
  100.             mincost_x = x->dmin + y->dmin;
  101.             mincost_y = y->dmin;
  102.             cost_x    = x->dcost + mincost_x;
  103.             cost_y    = y->dcost + mincost_y;
  104.             
  105.             mincost_x = mincost_y;
  106.             mincost_y = (mincost_a <= mincost_b) ? mincost_a : mincost_b;
  107.             if (cost_y <= mincost_y) mincost_y = cost_y;
  108.             x->dcost = cost_x - mincost_x;
  109.             y->dcost = cost_y - mincost_y;
  110.             x->dmin  = mincost_x;
  111.             y->dmin  = mincost_y - mincost_x;
  112.             if (a) a->dmin  = mincost_a - mincost_y;
  113.             if (b) b->dmin  = mincost_b - mincost_y;
  114.             if (c) c->dmin  = mincost_c - mincost_x;           
  115.         };
  116.         continue;
  117.       };
  118.       
  119.       // 2.Fall: x hat also Grossvater, x und parent(x) linke (rechte)
  120.       //           Soehne.
  121.       // Linke Soehne:
  122.  
  123.       if ((z->left==y)&&(y->left==x)){   //  (3)
  124.         a=x->left;
  125.         b=x->right;
  126.         c=y->right;
  127.         d=z->right;
  128.         y->left=b;
  129.         if (b) b->parent=y;
  130.         z->left=c;
  131.         if (c) c->parent=z;
  132.         x->right=y;
  133.         y->parent=x;
  134.         y->right=z;
  135.         z->parent=y;
  136.         if (zz) {
  137.             if (zz->left==z){
  138.              zz->left=x;
  139.             }
  140.             else{
  141.              zz->right=x;
  142.             };
  143.         }
  144.         else {     //  z is solid-tree-root
  145.             x->successor=z->successor;    
  146.             z->successor=0;
  147.         }; 
  148.         x->parent=zz;
  149.         
  150.         mincost_a = (a) ? a->dmin + x->dmin + y->dmin + z->dmin : BIG;
  151.         mincost_b = (b) ? b->dmin + x->dmin + y->dmin + z->dmin : BIG;
  152.         mincost_c = (c) ? c->dmin + y->dmin + z->dmin : BIG;
  153.         mincost_d = (d) ? d->dmin + z->dmin : BIG;
  154.         mincost_x =     x->dmin + y->dmin + z->dmin;
  155.         mincost_y =     y->dmin + z->dmin;
  156.         mincost_z =     z->dmin;
  157.         cost_x     = mincost_x + x->dcost;
  158.         cost_y     = mincost_y + y->dcost;
  159.         cost_z     = mincost_z + z->dcost;
  160.         
  161.         mincost_x = mincost_z;
  162.         mincost_z = (mincost_c <= mincost_d) ? mincost_c : mincost_d;
  163.         if (cost_z <= mincost_z) mincost_z = cost_z;
  164.         mincost_y = (mincost_b <= mincost_z) ? mincost_b : mincost_z;
  165.         if (cost_y <= mincost_y) mincost_y = cost_y;
  166.         x->dcost = cost_x - mincost_x;
  167.         y->dcost = cost_y - mincost_y;
  168.         z->dcost = cost_z - mincost_z;
  169.         x->dmin = mincost_x;
  170.         y->dmin = mincost_y - mincost_x;
  171.         z->dmin = mincost_z - mincost_y;
  172.         if (a) a->dmin    = mincost_a - mincost_x;
  173.         if (b) b->dmin    = mincost_b - mincost_y;
  174.         if (c) c->dmin    = mincost_c - mincost_z;
  175.         if (d) d->dmin    = mincost_d - mincost_z;
  176.  
  177.         continue;
  178.       };
  179.       
  180.       // Rechte Soehne:   (4)
  181.       
  182.       if ((z->right==y)&&(y->right==x)){
  183.         a=z->left;
  184.         b=y->left;
  185.         c=x->left;
  186.         d=x->right;
  187.         z->right=b;
  188.         if (b) b->parent=z;
  189.         z->parent=y;
  190.         y->left=z;
  191.         y->right=c;
  192.         if (c) c->parent=y;
  193.         y->parent=x;
  194.         x->left=y;
  195.         if (zz) {
  196.             if (zz->left==z){
  197.              zz->left=x;
  198.             }
  199.             else{
  200.              zz->right=x;
  201.             };
  202.         }
  203.         else { 
  204.             x->successor=z->successor;
  205.             z->successor=0;
  206.         };
  207.         x->parent=zz;
  208.         
  209.         mincost_a = (a) ? a->dmin + z->dmin : BIG;
  210.         mincost_b = (b) ? b->dmin + y->dmin + z->dmin : BIG;
  211.         mincost_c = (c) ? c->dmin + x->dmin + y->dmin + z->dmin : BIG;
  212.         mincost_d = (d) ? d->dmin + x->dmin + y->dmin + z->dmin : BIG;
  213.         mincost_x =     x->dmin + y->dmin + z->dmin;
  214.         mincost_y =     y->dmin + z->dmin;
  215.         mincost_z =     z->dmin;
  216.         cost_x     = mincost_x + x->dcost;
  217.         cost_y     = mincost_y + y->dcost;
  218.         cost_z     = mincost_z + z->dcost;
  219.         
  220.         mincost_x = mincost_z;
  221.         mincost_z = (mincost_a <= mincost_b) ? mincost_a : mincost_b;
  222.         if (cost_z <= mincost_z) mincost_z = cost_z;
  223.         mincost_y = (mincost_c <= mincost_z) ? mincost_c : mincost_z;
  224.         if (cost_y <= mincost_y) mincost_y = cost_y;
  225.         x->dcost = cost_x - mincost_x;
  226.         y->dcost = cost_y - mincost_y;
  227.         z->dcost = cost_z - mincost_z;
  228.         x->dmin = mincost_x;
  229.         y->dmin = mincost_y - mincost_x;
  230.         z->dmin = mincost_z - mincost_y;
  231.         if (a) a->dmin    = mincost_a - mincost_z;
  232.         if (b) b->dmin    = mincost_b - mincost_z;
  233.         if (c) c->dmin    = mincost_c - mincost_y;
  234.         if (d) d->dmin    = mincost_d - mincost_x;
  235.  
  236.         continue;
  237.       };
  238.       
  239.  
  240.       // 3.Fall: x linkes, p(x) rechtes Kind (oder umgekehrt)
  241.       // Zuerst x links, p(x) rechts:
  242.       
  243.       if ((z->right==y)&&(y->left==x)){   // (5)
  244.         a=z->left;
  245.         b=x->left;
  246.         c=x->right;
  247.         d=y->right;
  248.         z->right=b;
  249.         if (b) b->parent=z;
  250.         z->parent=x;
  251.         x->left=z;
  252.         y->left=c;
  253.         if (c) c->parent=y;
  254.         y->parent=x;
  255.         x->right=y;
  256.         if (zz) {
  257.             if (zz->left==z){
  258.              zz->left=x;
  259.             }
  260.             else{
  261.              zz->right=x;
  262.             };
  263.         } 
  264.         else {
  265.             x->successor=z->successor;
  266.             z->successor=0;
  267.         };
  268.         x->parent=zz;
  269.         
  270.         mincost_a = (a) ? a->dmin + z->dmin : BIG;
  271.         mincost_b = (b) ? b->dmin + x->dmin + y->dmin + z->dmin : BIG;
  272.         mincost_c = (c) ? c->dmin + x->dmin + y->dmin + z->dmin : BIG;
  273.         mincost_d = (d) ? d->dmin + y->dmin + z->dmin : BIG;
  274.         mincost_x =     x->dmin + y->dmin + z->dmin;
  275.         mincost_y =     y->dmin + z->dmin;
  276.         mincost_z =     z->dmin;
  277.         cost_x     = mincost_x + x->dcost;
  278.         cost_y     = mincost_y + y->dcost;
  279.         cost_z     = mincost_z + z->dcost;
  280.         
  281.         mincost_x = mincost_z;
  282.         mincost_z = (mincost_a <= mincost_b) ? mincost_a : mincost_b;
  283.         if (cost_z <= mincost_z) mincost_z = cost_z;
  284.         mincost_y = (mincost_c <= mincost_d) ? mincost_c : mincost_d;
  285.         if (cost_y <= mincost_y) mincost_y = cost_y;
  286.         x->dcost = cost_x - mincost_x;
  287.         y->dcost = cost_y - mincost_y;
  288.         z->dcost = cost_z - mincost_z;
  289.         x->dmin = mincost_x;
  290.         y->dmin = mincost_y - mincost_x;
  291.         z->dmin = mincost_z - mincost_x;
  292.         if (a) a->dmin    = mincost_a - mincost_z;
  293.         if (b) b->dmin    = mincost_b - mincost_z;
  294.         if (c) c->dmin    = mincost_c - mincost_y;
  295.         if (d) d->dmin    = mincost_d - mincost_y;
  296.  
  297.         continue;
  298.       };
  299.       
  300.       // Nun x rechts, p(x) links:
  301.       
  302.       if ((z->left==y)&&(y->right==x)){    // (6)
  303.         a=y->left;
  304.         b=x->left;
  305.         c=x->right;
  306.         d=z->right;
  307.         y->right=b;
  308.         if (b) b->parent=y;
  309.         y->parent=x;
  310.         x->left=y;
  311.         z->left=c;
  312.         if (c) c->parent=z;
  313.         z->parent=x;
  314.         x->right=z;
  315.         if (zz) {
  316.             if (zz->left==z){
  317.              zz->left=x;
  318.             }
  319.             else{
  320.              zz->right=x;
  321.             };
  322.         }
  323.         else {
  324.             x->successor=z->successor;
  325.             z->successor=0;
  326.         };
  327.         x->parent=zz;
  328.         
  329.         mincost_a = (a) ? a->dmin + y->dmin + z->dmin : BIG;
  330.         mincost_b = (b) ? b->dmin + x->dmin + y->dmin + z->dmin : BIG;
  331.         mincost_c = (c) ? c->dmin + x->dmin + y->dmin + z->dmin : BIG;
  332.         mincost_d = (d) ? d->dmin + z->dmin : BIG;
  333.         mincost_x =     x->dmin + y->dmin + z->dmin;
  334.         mincost_y =     y->dmin + z->dmin;
  335.         mincost_z =     z->dmin;
  336.         cost_x     = mincost_x + x->dcost;
  337.         cost_y     = mincost_y + y->dcost;
  338.         cost_z     = mincost_z + z->dcost;
  339.         
  340.         mincost_x = mincost_z;
  341.         mincost_z = (mincost_c <= mincost_d) ? mincost_c : mincost_d;
  342.         if (cost_z <= mincost_z) mincost_z = cost_z;
  343.         mincost_y = (mincost_a <= mincost_b) ? mincost_a : mincost_b;
  344.         if (cost_y <= mincost_y) mincost_y = cost_y;
  345.         x->dcost = cost_x - mincost_x;
  346.         y->dcost = cost_y - mincost_y;
  347.         z->dcost = cost_z - mincost_z;
  348.         x->dmin = mincost_x;
  349.         y->dmin = mincost_y - mincost_x;
  350.         z->dmin = mincost_z - mincost_x;
  351.         if (a) a->dmin    = mincost_a - mincost_y;
  352.         if (b) b->dmin    = mincost_b - mincost_y;
  353.         if (c) c->dmin    = mincost_c - mincost_z;
  354.         if (d) d->dmin    = mincost_d - mincost_z;
  355.  
  356.       };
  357.      };
  358. }
  359.  
  360.  
  361. d_vertex dyna_trees::assemble(d_vertex u, d_vertex v, d_vertex w)
  362. {
  363.      double mincost_u,
  364.         mincost_v,
  365.         mincost_w,
  366.         cost_v;
  367.  
  368.      v->left=u;
  369.      v->right=w;
  370.      if (u) u->parent=v;
  371.      if (w) w->parent=v;
  372.      
  373.      mincost_u = (u) ? u->dmin : BIG;
  374.      mincost_v =       v->dmin;
  375.      mincost_w = (w) ? w->dmin : BIG;
  376.      cost_v = mincost_v + v->dcost;
  377.      
  378.      mincost_v = (mincost_u <= mincost_w) ? mincost_u : mincost_w;
  379.      if (cost_v < mincost_v) mincost_v = cost_v;
  380.      v->dcost = cost_v - mincost_v;
  381.      v->dmin = mincost_v;
  382.      if (u) u->dmin = mincost_u - mincost_v;
  383.      if (w) w->dmin = mincost_w - mincost_v;
  384.  
  385.      return v;
  386. };
  387.  
  388.  
  389. void   dyna_trees::disassemble(d_vertex v, d_vertex& v1, d_vertex& v2) {
  390.      double mincost_v1,
  391.         mincost_v2;
  392.  
  393.  
  394.      v1=v->left;
  395.      v2=v->right;
  396.      if (v1) v1->parent=0;
  397.      if (v2) v2->parent=0;
  398.      v->left=0;
  399.      v->right=0;
  400.  
  401.      mincost_v1 = (v1) ? v1->dmin + v->dmin : BIG;
  402.      mincost_v2 = (v2) ? v2->dmin + v->dmin : BIG;
  403.  
  404.      if (v1) v1->dmin = mincost_v1;
  405.      if (v2) v2->dmin = mincost_v2;
  406.      
  407.      v->dmin += v->dcost;
  408.      v->dcost = 0;
  409. }
  410.  
  411.  
  412. d_vertex dyna_trees::makepath(void* i)
  413. {
  414.      if (first==0) {
  415.       first=last=new d_node(i);
  416.      }
  417.      else {
  418.       last->next=new d_node(i);
  419.       last=last->next;
  420.      };
  421.      return last;
  422. }
  423.  
  424.  
  425. d_vertex dyna_trees::findpath(d_vertex v)
  426. {
  427.      splay(v);
  428.      return v;
  429. }
  430.  
  431.  
  432.  
  433. d_vertex dyna_trees::findpathcost(d_path p, double& d)
  434. {
  435.      d_vertex w;
  436.      w=p;
  437.      
  438.      while( !( (w->dcost==0) && ( (w->right==0)||(w->right->dmin>0) ) ) ) {
  439.       if (w->right) {
  440.         if (w->right->dmin == 0) {
  441.              w=w->right;
  442.         } else {
  443.              if (w->dcost>0) w=w->left;
  444.         }  
  445.       }
  446.       else {
  447.         if (w->dcost>0) w=w->left;
  448.       };
  449.      };
  450.      splay(w);
  451.      d=w->dmin;
  452.      return w;
  453. }
  454.  
  455.  
  456.  
  457. d_vertex dyna_trees::findtail(d_path p)
  458. {
  459.      d_vertex w;
  460.      w=p;
  461.      
  462.      while(w->right) {
  463.       w=w->right;
  464.      };
  465.      splay(w);
  466.      return w;
  467. }
  468.  
  469.  
  470.  
  471. void dyna_trees::addpathcost(d_path p, double x)
  472. {
  473.      p->dmin += x;
  474. }
  475.  
  476.  
  477.  
  478. d_vertex dyna_trees::join(d_path p, d_path v, d_path q)
  479. {
  480.      return assemble(p, v, q);
  481. }
  482.  
  483.  
  484.  
  485. void dyna_trees::split(d_vertex v, d_vertex& v1, d_vertex& v2)
  486. {
  487.      splay(v);
  488.      disassemble(v, v1, v2);
  489. }
  490.  
  491.  
  492.  
  493. d_path dyna_trees::expose(d_vertex v)
  494. {
  495.      d_path   p,
  496.           q,
  497.           r;
  498.      d_vertex w;
  499.      
  500.      p=0;
  501.      while (v) {
  502.       w=findpath(v)->successor;
  503.       split(v,q,r);
  504.       if (q) q->successor=v;
  505.       p=join(p, v, r);
  506.       v=w;
  507.      };
  508.      p->successor=0;
  509.      return p;
  510. }
  511.  
  512.  
  513. d_vertex dyna_trees::maketree(void* i)
  514. {
  515.      copy_inf(i);
  516.  
  517.      d_vertex v;
  518.      v=makepath(i);
  519.      v->successor=0;
  520.      return v;
  521. }
  522.  
  523.  
  524. d_vertex dyna_trees::findroot(d_vertex v)
  525. {
  526.      return findtail(expose(v));
  527. }
  528.  
  529.  
  530.  
  531. d_vertex dyna_trees::findcost(d_vertex v, double& d)
  532. {
  533.      return findpathcost(expose(v),d);
  534. }
  535.  
  536.  
  537.  
  538. void dyna_trees::addcost(d_vertex v, double x)
  539. {
  540.      addpathcost(expose(v),x);
  541. }
  542.  
  543.  
  544.  
  545. void dyna_trees::link(d_vertex v, d_vertex w)
  546. {
  547.      join( (d_vertex) 0, expose(v), expose(w) )->successor=0;
  548. }
  549.  
  550.  
  551.  
  552. void dyna_trees::cut(d_vertex v) 
  553. {
  554.      d_path p,q;
  555.      
  556.      expose(v);
  557.      split(v,p,q);
  558.      v->successor=q->successor=0;
  559. }
  560.  
  561.  
  562.  
  563. dyna_trees::~dyna_trees()
  564. {
  565.      d_node *x, 
  566.         *y;
  567.       
  568.      x=first;
  569.      while(x) {
  570.       y=x->next;
  571.       delete x;
  572.       x=y;
  573.      };
  574. }
  575.  
  576.  
  577.  
  578.