home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / ledar34.zip / leda-r-3_4_tar / LEDA-3.4 / src / plane / _ps_tree.c < prev    next >
C/C++ Source or Header  |  1996-09-03  |  18KB  |  686 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA 3.4
  4. +
  5. +  _ps_tree.c
  6. +
  7. +  This file is part of the LEDA research version (LEDA-R) that can be 
  8. +  used free of charge in academic research and teaching. Any commercial
  9. +  use of this software requires a license which is distributed by the
  10. +  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
  11. +  (fax +49 681 31104).
  12. +
  13. +  Copyright (c) 1991-1996  by  Max-Planck-Institut fuer Informatik
  14. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  15. +  All rights reserved.
  16. + 
  17. *******************************************************************************/
  18. //--------------------------------------------------------------------
  19. //  
  20. //  Priority Search Trees
  21. //
  22. //  Renate Lassen   (1990)
  23. //
  24. // Implementation follows
  25. // Kurt Mehlhorn: Data Structures and Algorithms 3, section III.5.1.2
  26. //
  27. // -------------------------------------------------------------------
  28.  
  29. #include <LEDA/impl/ps_tree.h>
  30.  
  31.  
  32. // -------------------------------------------------------------
  33. // member functions
  34. // -------------------------------------------------------------
  35.  
  36. // -------------------------------------------------------------
  37. // lrot() , rrot() , ldrot() , rdrot()
  38. // Rotationen am Knoten p
  39.  
  40. void ps_tree::lrot(ps_item p, ps_item q)
  41. { 
  42.   x_typ xh ,yh;
  43.  
  44. //  cout << "lrot\n";
  45. //  cout << "p :" << p->split_value_x() << "\n";
  46. //  cout << "q :" << q->split_value_x() << "\n";
  47.   ps_item h = p->sohn[right];
  48. //  cout << "h :" << h->split_value_x() << "\n";
  49.   xh = h->x_value();
  50.   yh = h->y_value();
  51.   
  52.   p->sohn[right] = h->sohn[left];
  53.   h->sohn[left] = p;
  54.    
  55.   if (!q) root=h;
  56.   else
  57.   {
  58.    if ( p == q->sohn[left] )   q->sohn[left]=h;
  59.    else q->sohn[right]=h;
  60.   }; 
  61.   
  62.   h->x_val = p->x_value();
  63.   h->y_val = p->y_value();
  64.   p->x_val = p->y_val = 0;
  65.  
  66.   if (cmp(xh,yh,h->split_value_x(),h->split_value_y())>0)  
  67.       sink(h->sohn[right],xh,yh);
  68.   else  sink(p->sohn[right],xh,yh); 
  69.     
  70.   fill(p);
  71.   
  72.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  73.   h->gr=p->groesse()+h->sohn[right]->groesse();
  74. }
  75.  
  76. void ps_tree::rrot(ps_item p, ps_item q)
  77. { 
  78.   x_typ xh, yh;
  79.   
  80.   //cout << "rrot\n"; 
  81.  // cout << "p :" << p->split_value_x() << "\n";
  82.  // cout << "q :" << q->split_value_x() << "\n";
  83.   ps_item h = p->sohn[left];
  84.  // cout << "h :" << h->split_value_x() << "\n";
  85.   xh=h->x_value();
  86.   yh=h->y_value();
  87.   
  88.   p->sohn[left] = h->sohn[right];
  89.   h->sohn[right] = p;
  90.  
  91.   if (!q) root=h;
  92.   else
  93.   {
  94.    if ( p == q->sohn[left] ) q->sohn[left] = h;
  95.    else q->sohn[right] = h; 
  96.   };
  97.  
  98.   h->x_val = p->x_value();
  99.   h->y_val = p->y_value();
  100.   p->x_val = p->y_val = 0;
  101.   
  102.   if (cmp(xh,yh,h->split_value_x(),h->split_value_y())<=0)  
  103.       sink(h->sohn[left],xh,yh);
  104.   else sink(p->sohn[left],xh,yh);
  105.   
  106.   fill(p);
  107.  
  108.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  109.   h->gr=p->groesse()+h->sohn[left]->groesse();
  110. }
  111.  
  112. void ps_tree::ldrot(ps_item p, ps_item q)
  113. { 
  114.     
  115.   //cout << "ldrot\n";
  116.   ps_item h = p->sohn[right];
  117.   //ps_item t = h->sohn[left];
  118.   rrot(h,p);
  119.   lrot(p,q);
  120.  // cout << "p:" << p->split_value_x() << "\n";
  121.  // cout << "h:" << h->split_value_x() << "\n";
  122. }
  123.  
  124. void ps_tree::rdrot(ps_item p, ps_item q)
  125. {
  126.  
  127.   //cout << "rdrot\n";
  128.   ps_item h = p->sohn[left];
  129.   //ps_item t = h->sohn[right];
  130.   lrot(h,p);
  131.   rrot(p,q);
  132.  // cout << "p:" << p->split_value_x() << "\n";
  133.   //cout << "h:" << h->split_value_x() << "\n";
  134.   //cout << "t:" << t->split_value() << "\n";
  135. }
  136.  
  137. // ------------------------------------------------------------------
  138. // fill(ps_item)
  139. // fuellt Knoten bei Rotation wieder auf 
  140.   
  141. void ps_tree::fill(ps_item p)
  142. {
  143.  
  144.  int leer=0;
  145.  int diff=0;
  146.  //cout << "fill\n";
  147.  while (!p->blatt() && leer!=1)
  148.  {
  149.   diff=cmp(p->sohn[left]->y_value(),p->sohn[right]->y_value()); 
  150.   //cout << "diff = " << diff << "\n";
  151.   if (diff==0) leer=1;                                           // Kinder von p gefuellt ?
  152.   else if ( (diff<0 && p->sohn[left]->y_value()!=0) 
  153.             || (diff>0 && p->sohn[right]->y_value()==0))
  154.        {
  155.         p->x_val = p->sohn[left]->x_value();
  156.         p->y_val = p->sohn[left]->y_value();
  157.         p->sohn[left]->x_val = p->sohn[left]->y_val = 0;   
  158.   //cout <<"gefuellt von links :"<<p->split_value()<<":"<<p->x_value()<<":"<<p->y_value()<<"\n";
  159.         p = p->sohn[left];
  160.        }
  161.        else if ( (diff>0 && p->sohn[right]->y_value()!=0) 
  162.                  || (diff<0 && p->sohn[left]->y_value()==0)) 
  163.             {
  164.             p->x_val = p->sohn[right]->x_value();
  165.             p->y_val = p->sohn[right]->y_value();
  166.             p->sohn[right]->x_val = p->sohn[right]->y_val = 0;   
  167.             p->sohn[right]->x_val = p->sohn[right]->y_val =0;
  168.             p = p->sohn[right];
  169.             };
  170.  };
  171. }
  172.  
  173. // ------------------------------------------------------------------
  174. // sink() 
  175. // laesst Paar (x,y) im Unterbaum mit Wurzel p herabsinken.
  176.    
  177. ps_item ps_tree::sink(ps_item q, x_typ x, x_typ y)
  178. {
  179.  x_typ xh, yh, xneu=x;
  180.  x_typ yneu=y;
  181.  ps_item p =q;
  182.  ps_item inserted; 
  183.  
  184.  while(!p->blatt() && cmp(p->x_value(),0)!=0)
  185.  {
  186.   //cout << "sink\n";
  187.   //cout << p->split_value_x() << ":" << p->split_value_y() <<":"<< p->x_value() << ":" << p->y_value() <<"\n";
  188.   if (cmp(p->y_value(),0)!=0 && cmp(y,p->y_value())<0)
  189.   {                                                    // Tausch
  190.    xh=p->x_value();
  191.    yh=p->y_value();
  192.    p->x_val=x;
  193.    p->y_val=y;
  194.    x=xh;
  195.    y=yh;
  196.    if (cmp(p->x_value(),xneu)==0 && cmp(p->y_value(),yneu)==0) inserted=p;
  197.   //cout << "inserted in Tausch\n";
  198.   //cout << inserted->split_value() <<":"<< inserted->x_value() << ":" << inserted->y_value() <<"\n";
  199.   };
  200.   //cout << "hallo\n";
  201.   if (cmp(x,y,p->split_value_x(),p->split_value_y())<=0)   p=p->sohn[left];
  202.   else 
  203.   {
  204.    p=p->sohn[right]; 
  205.   //cout << p->split_value_x() << ":" << p->split_value_y() <<":"<< p->x_value() << ":" << p->y_value() <<"\n";
  206.   };
  207.  };
  208.  p->x_val=x;
  209.  p->y_val=y;
  210.  if (cmp(p->x_value(),xneu)==0 && cmp(p->y_value(),yneu)==0) inserted=p;
  211.  // cout << "inserted" << inserted->split_value_y() <<":"<< inserted->x_value() << ":" << inserted->y_value() <<"\n";
  212.  return inserted;
  213. }
  214.  
  215. // ------------------------------------------------------------------
  216. // search(x_typ,x_typ)
  217. // sucht Knoten, der das Paar (x,y) enthaelt,
  218. // oder Blatt, an dem neues Blatt fuer x angehaengt werden soll.
  219.  
  220.  
  221. ps_item ps_tree::search(x_typ x,x_typ y)
  222. {
  223.  ps_item p = root;
  224.  //ps_item q = 0;
  225.  
  226. // cout << "search\n";
  227.  if (root->blatt())
  228.  {
  229.   st.push(root);
  230.   return p;
  231.  }
  232.  else
  233.  {
  234.   st.push(p);
  235.   while ( !p->blatt() && p!=0 )
  236.   {
  237.    if ( cmp(x,p->x_value())==0 && cmp(y,p->y_value())==0) 
  238.    {
  239.     p=0;
  240.    }
  241.    else 
  242.    { 
  243.     if ( cmp(x,y,p->split_value_x(),p->split_value_y())<=0 ) p=p->sohn[left];
  244.     else p=p->sohn[right]; 
  245.     st.push(p);
  246.    }
  247.   }
  248.   return p;
  249.  }
  250. }  
  251.  
  252.   
  253. // ------------------------------------------------------------------
  254. // locate(x_typ x,x_typ y)
  255. // gibt Knoten oder Blatt mit Inhalt (x,y), falls existiert,
  256. //                                      0 , sonst.
  257.  
  258. ps_item ps_tree::locate(x_typ x,x_typ y)
  259. {
  260.  ps_item p = root;
  261.  ps_item q = 0;
  262.  
  263.  //cout << "locate\n";
  264.  while ( q==0 && p!=0 && cmp(y,p->y_value())>=0 )
  265.  {
  266.   st.push(p);
  267.   if ( cmp(x,p->x_value())==0 && cmp(y,p->y_value())==0) 
  268.   {
  269.    q=p;
  270.   }
  271.   else 
  272.   { 
  273.    if ( cmp(x,y,p->split_value_x(),p->split_value_y())<=0 ) p=p->sohn[left];
  274.    else p=p->sohn[right]; 
  275.   }
  276.  }
  277.  return q;
  278. }
  279.  
  280. // ------------------------------------------------------------------
  281. // delleaf(ps_item)
  282. // loescht Blatt von Paar (x,y) und Vater des Blattes.
  283. // ( Zwei Blaetter mit gemeinsamen Vater sind nie beide gefuellt. )
  284.   
  285. void ps_tree::delleaf(ps_item q)
  286. {
  287.  ps_item p;    
  288.  ps_item t;    
  289.  ps_item father;
  290.  x_typ xh,yh;
  291.  
  292.  //cout << "delleaf\n";
  293.  q->x_val=0;
  294.  q->y_val=0;
  295.  p=st.pop();
  296.  father=st.pop();
  297.  if (q==father->sohn[left] ) father->sohn[left]=0;
  298.  else father->sohn[right]=0;
  299.  delete (q);                                           // loescht Blatt
  300.  t= st.empty() ? 0 : st.top();
  301.  xh=father->x_value();
  302.  yh=father->y_value();
  303.  //cout << "xh: " << xh << "\n";
  304.  //cout << "yh: " << yh << "\n";
  305.   
  306.  if ( father->sohn[left]!=0) q=father->sohn[left];
  307.  else q=father->sohn[right];
  308.  if (t!=0)
  309.  {
  310.   if (father==t->sohn[left])  t->sohn[left]=q;
  311.   else  t->sohn[right]=q;
  312.  }
  313.  else root=q;
  314.  delete(father);                                       // loescht Vater
  315.  
  316.  //cout << "q-x_value: " << q->x_value() << "\n";
  317.  //cout << "q-y_value: " << q->y_value() << "\n";
  318.  //cout << "q-split_value: " << q->split_value() << "\n";
  319.  sink(q,xh,yh);
  320. }
  321.   
  322. // ------------------------------------------------------------------
  323. // insert(x_typ x,x_typ y)
  324. // fuegt ein neues Item (x,y) in den Baum ein
  325. //                 , falls noch nicht vorhanden, 
  326. // Fehlermeldung   ,sonst
  327. // gibt Zeiger auf eingefuegtes Blatt zurueck
  328.  
  329. ps_item ps_tree::insert(x_typ x,x_typ y)
  330. { 
  331.  ps_item p;
  332.  ps_item t;
  333.  ps_item father;
  334.  
  335.  if (!root)                                     // neuer Baum
  336.  {  
  337.   ps_item p=new ps_node(x,y,x,y);
  338.   root=p; 
  339.   anzahl=1; 
  340.   return p;
  341.  }
  342.  else
  343.  {
  344.   p=search(x,y);
  345.   //cout << "p-x_value: " << p->x_value() << "\n";
  346.   //cout << "p-y_value: " << p->y_value() << "\n";
  347.   //cout << "p-split_value_x: " << p->split_value_x() << "\n";
  348.   //cout << "p-split_value_y: " << p->split_value_y() << "\n";
  349.   
  350.   if (p==0)
  351.   {
  352.    error_handler(0,"point already there !");   // Warnung
  353.    st.clear();
  354.    return p;
  355.   }
  356.   else
  357.   {
  358.    ps_item q = new ps_node(0,0,p->split_value_x(),p->split_value_y());   
  359.    ps_item w = new ps_node(0,0,x,y);           // zwei neue Blaetter
  360.   //cout << "q-x_value: " << q->x_value() << "\n";
  361.   //cout << "q-y_value: " << q->y_value() << "\n";
  362.   //cout << "q-split_value_x: " << q->split_value_x() << "\n";
  363.   //cout << "q-split_value_y: " << q->split_value_y() << "\n";
  364.   //cout << "w-x_value: " << w->x_value() << "\n";
  365.   //cout << "w-y_value: " << w->y_value() << "\n";
  366.   //cout << "w-split_value_x: " << w->split_value_x() << "\n";
  367.   //cout << "w-split_value_y: " << w->split_value_y() << "\n";
  368.    if(cmp(p->split_value_x(),p->split_value_y(),x,y)<=0)
  369.    {
  370.     p->sohn[left]=q; 
  371.     p->sohn[right]=w; 
  372.    }
  373.    else
  374.    {
  375.     p->split_val[0] = x;
  376.     p->split_val[1] = y;
  377.     p->sohn[left]=w;
  378.     p->sohn[right]=q;
  379.    } 
  380.                    
  381.   //cout << "p-x_value: " << p->x_value() << "\n";
  382.   //cout << "p-y_value: " << p->y_value() << "\n";
  383.   //cout << "p-split_value_x: " << p->split_value_x() << "\n";
  384.   //cout << "p-split_value_y: " << p->split_value_y() << "\n";
  385.    while (!st.empty())                          // rebalancieren
  386.    { 
  387.     t=st.pop();
  388.    // cout << "stack\n";
  389.     father = st.empty() ? 0 : st.top();
  390.     t->gr++;  
  391.     float i = t->bal();
  392.   
  393.     //cout << "i" << i << "\n";
  394.     if (i < alpha)
  395.     {
  396.      if (t->sohn[right]->bal()<=d) lrot(t,father);
  397.      else ldrot(t,father);
  398.     }
  399.     else if (i>1-alpha) 
  400.     {
  401.       if (t->sohn[left]->bal() > d ) rrot(t,father);
  402.       else rdrot(t,father);
  403.     }
  404.    }
  405.    p = sink(root,x,y);
  406.    //cout<< p->split_value() <<":"<< p->x_value() << ":" << p->y_value() <<"\n";
  407.    return p;
  408.   }
  409.  } 
  410. }
  411. // ------------------------------------------------------------------
  412. // del()
  413. // loescht Item it im Baum mit x_value(it) = x ,
  414. //                             y_value(it) = y , falls existiert
  415. //         und gibt Zeiger auf it zurueck
  416. // 0 , sonst
  417.  
  418. ps_item ps_tree::del(x_typ x,x_typ y)
  419. { 
  420.  ps_item p;
  421.  ps_item t;
  422.  ps_item father;
  423.  ps_item deleted = new ps_node(x,y,0,0);
  424.  
  425.  if (root==0) 
  426.  {
  427.   error_handler(0,"Tree is empty");
  428.   return 0;                                          // leerer Baum
  429.  }
  430.  else
  431.  {
  432.   p=locate(x,y);
  433.   //cout << "located:"<<p->split_value()<<"\n";
  434.   if (p==0) 
  435.   {
  436.    error_handler(0,"Pair is not in tree ");
  437.    st.clear();
  438.    return 0;                                         // Paar nicht im Baum
  439.   }
  440.   else
  441.   { 
  442.    if (p->blatt()) 
  443.    {
  444.     if (p==root)
  445.     {
  446.      error_handler(0,"Root is deleted.");
  447.      p=st.pop();
  448.      root=0;
  449.      anzahl=0;
  450.      return p;                                       // Wurzel geloescht
  451.     } 
  452.     else
  453.     {
  454.      delleaf(p);                                 // (x,y) steht in einem Blatt
  455.     }
  456.    }
  457.    else                                          // (x,y) steht in einem Knoten
  458.    {
  459.     p->x_val = p->y_val = 0;
  460.     fill(p);
  461.     while (!p->blatt())                               // Knoteninhalt loeschen
  462.     {                                                 // und neu auffuellen
  463.      if (cmp(x,y,p->split_value_x(),p->split_value_y())<=0) p=p->sohn[left];
  464.      else p=p->sohn[right];
  465.      st.push(p);
  466.     };
  467.     
  468.     delleaf(p);                                    // loescht zugehoeriges Blatt
  469.    }
  470.  
  471.    while (!st.empty())                                 // rebalancieren
  472.    { 
  473.     t = st.pop();
  474.     //cout << "stack\n";
  475.     //cout << t->split_value()<<":"<<t->x_value()<<":"<<t->y_value()<<"\n";
  476.     father = st.empty() ? 0 : st.top() ;
  477.     t->gr--;              
  478.     float i=t->bal();
  479.     //cout << "i :" << i << "\n";
  480.     if (i<alpha)
  481.     { 
  482.      if (t->sohn[right]->bal() <= d) lrot(t,father);
  483.      else ldrot(t,father);
  484.     }
  485.     else if (i>1-alpha)
  486.     { 
  487.      if(t->sohn[left]->bal() > d) rrot(t,father);
  488.      else rdrot(t,father);
  489.     }
  490.    }
  491.    return(deleted);
  492.   }
  493.  }
  494. } 
  495.    
  496. //-----------------------------------------------------------------------
  497. //enumerate(x1,x2,y0,p)
  498. //gibt alle Punkte (x,y) aus Unterbaum mit Wurzel p
  499. //mit folgender Eigenschaft an :
  500. //  x1 <= x <= x2   &&   y <= y0 
  501. //Voraussetzung : x1 < x2
  502.  
  503. void ps_tree::enumerate(x_typ x1,x_typ x2,x_typ y0,ps_item p)
  504. {
  505.  if (cmp(y0,p->y_value())>=0 && p!=0)
  506.  {
  507.   if (cmp(x1,p->split_value_x())<=0 && cmp(p->split_value_x(),x2)<=0)
  508.   {
  509.    if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
  510.       cout <<p->split_value_x()<<"("<<p->x_value()<<","<<p->y_value()<<")\n";
  511.    enumerate(x1,x2,y0,p->sohn[left]); 
  512.    enumerate(x1,x2,y0,p->sohn[right]); 
  513.   }
  514.   else if (cmp(p->split_value_x(),x1)<=0) 
  515.        {
  516.         if(cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
  517.            cout <<p->split_value_x()<<"("<<p->x_value()<<","<<p->y_value()<<")\n";
  518.         enumerate(x1,x2,y0,p->sohn[right]);
  519.        }
  520.        else if (cmp(x2,p->split_value_x())<=0) 
  521.        {
  522.         if(cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
  523.            cout <<p->split_value_x()<<"("<<p->x_value()<<","<<p->y_value()<<")\n";
  524.         enumerate(x1,x2,y0,p->sohn[left]);
  525.        }
  526.  }
  527. }
  528.        
  529. //-----------------------------------------------------------------------
  530. //void pr_ps_tree(ps_item p;int blancs)
  531. //gibt den Baum mit Wurzel p aus
  532.  
  533. void ps_tree::pr_ps_tree(ps_item p,int blancs)
  534. {
  535.  if (p==0)
  536.    { for (int j=1;j<=blancs;j++) cout << " ";
  537.      cout << "NIL\n";
  538.      return;
  539.    }
  540.  else
  541.    { pr_ps_tree(p->sohn[left],blancs+10); 
  542.      for (int j=1;j<=blancs;j++) cout << " ";
  543.      cout << "(" << p->split_value_x() << "," << p->split_value_y() << "):";
  544.      cout << "(" << p->x_value() << "," << p->y_value() << ")\n";
  545.      pr_ps_tree(p->sohn[right],blancs+10); 
  546.    }
  547. }
  548.  
  549. //-----------------------------------------------------------------------
  550. //min_x_in_rect(x1,x2,y0,p)
  551. //sucht nach Paar (x,y) im Unterbaum von p 
  552. //mit folgender Eigenschaft :
  553. //  min { x ; es gibt y, so dass x1<=x<=x2 und y<=y0 } , falls existiert,
  554. //                                                   0 , sonst.
  555.  
  556. pair_item ps_tree::min_x_in_rect(x_typ x1,x_typ x2,x_typ y0,ps_item p)
  557. {
  558.  pair_item  c;
  559.  
  560.  if (p==0)
  561.  {
  562.   return 0;                                   // Baum ist leer.
  563.  }
  564.  else
  565.  {
  566.   c=new pair;
  567.   c->x_pkt=c->y_pkt=0;
  568.   c->valid=false;
  569.   if (cmp(y0,p->y_value())>=0)
  570.   {
  571.    if (!p->blatt())
  572.    {
  573.     if (cmp(x1,p->split_value_x())<=0) 
  574.         c=min_x_in_rect(x1,x2,y0,p->sohn[left]);
  575.     if (!c->valid && cmp(p->split_value_x(),x2)<0) 
  576.         c=min_x_in_rect(x1,x2,y0,p->sohn[right]);
  577.    }
  578.    if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0 
  579.        && cmp(p->y_value(),y0)<=0
  580.        && (!c->valid || cmp(p->x_value(),c->x_pkt)<0)     )
  581.    {
  582.     c->x_pkt=p->x_value();  
  583.     c->y_pkt=p->y_value();  
  584.     c->valid=true;
  585.    }
  586.   }
  587.   return c;
  588.  }
  589. }
  590.  
  591. //-----------------------------------------------------------------------
  592. //max_x_in_rect(x1,x2,y0,p)
  593. //sucht nach Paar (x,y) im Unterbaum von p 
  594. //mit folgender Eigenschaft :
  595. //  max { x ; es gibt y, so dass x1<=x<=x2 und y<=y0 } , falls existiert,
  596. //                                                   0 , sonst.
  597.  
  598. pair_item ps_tree::max_x_in_rect(x_typ x1,x_typ x2,x_typ y0,ps_item p)
  599. {
  600.  pair_item c;
  601.  
  602.  if (p==0) 
  603.  {
  604.   return 0;                                      // Baum ist leer.
  605.  }
  606.  else
  607.  {
  608.   c=new pair;
  609.   c->x_pkt=c->y_pkt=0;
  610.   c->valid=false;
  611.   if (cmp(y0,p->y_value())>=0)
  612.   {
  613.    if (!p->blatt())
  614.    {
  615.     if (cmp(p->split_value_x(),x2)<=0) 
  616.         c=max_x_in_rect(x1,x2,y0,p->sohn[right]);
  617.     if (!c->valid && cmp(x1,p->split_value_x())<0) 
  618.         c=max_x_in_rect(x1,x2,y0,p->sohn[left]);
  619.    }
  620.    if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0 
  621.        && cmp(p->y_value(),y0)<=0
  622.        && (!c->valid || cmp(p->x_value(),c->x_pkt)>0)     )
  623.    {
  624.     c->x_pkt=p->x_value();  
  625.     c->y_pkt=p->y_value();  
  626.     c->valid=true;
  627.    }
  628.   }
  629.   return c;
  630.  }
  631. }
  632.  
  633. //-----------------------------------------------------------------------
  634. //min_y_in_xrange(x1,x2,p)
  635. //sucht Paar (x,y) im Unterbaum von p
  636. //mit folgender Eigenschaft :
  637. // y = min { y ; es gibt x, so dass x1<=x<=x2 } , falls existiert,
  638. //                                            0 , sonst.
  639.  
  640. pair_item ps_tree::min_y_in_xrange(x_typ x1,x_typ x2,ps_item p)
  641. {
  642.  pair_item c1,c2;
  643.  
  644.  if (p==0)
  645.  {
  646.   return 0;                                      // Baum ist leer.
  647.  }
  648.  else
  649.  {
  650.   c1 = new pair;
  651.   c2 = new pair;
  652.   c1->x_pkt=c1->y_pkt=c2->x_pkt=c2->y_pkt=0; 
  653.   c1->valid=c2->valid=false;
  654.   if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
  655.   {
  656.    c1->x_pkt=p->x_value();
  657.    c1->y_pkt=p->y_value();
  658.    c1->valid=true;
  659.   }
  660.   else if (!p->blatt())
  661.   {
  662.    if (cmp(x1,p->split_value_x())<=0) c1=min_y_in_xrange(x1,x2,p->sohn[left]);
  663.    if (cmp(p->split_value_x(),x2)<0)  c2=min_y_in_xrange(x1,x2,p->sohn[right]);
  664.    if (!c1->valid || (c2->valid && cmp(c2->y_pkt,c1->y_pkt)<0)) c1=c2;
  665.   }
  666.   return c1;
  667.  } 
  668. }
  669.  
  670. //-----------------------------------------------------------------------
  671. // Funktion fuer Destruktor
  672. //-----------------------------------------------------------------------
  673.   
  674. void ps_tree::deltree(ps_item p)
  675. {
  676.  if (p)
  677.  {
  678.   if (!p->blatt())
  679.   {
  680.    deltree(p->sohn[left]);
  681.    deltree(p->sohn[right]);
  682.   }
  683.   delete(p);
  684.  }
  685. }
  686.