_ps_tree.c

数据类型和算法库LEDA 数据类型和算法库LEDA

  //cout << "p-x_value: " << p->x_value() << "\n";
  //cout << "p-y_value: " << p->y_value() << "\n";
  //cout << "p-split_value_x: " << p->split_value_x() << "\n";
  //cout << "p-split_value_y: " << p->split_value_y() << "\n";
  
  if (p==0)
  {
   error_handler(0,"point already there !");   // Warnung
   st.clear();
   return p;
  }
  else
  {
   ps_item q = new ps_node(0,0,p->split_value_x(),p->split_value_y());   
   ps_item w = new ps_node(0,0,x,y);           // zwei neue Blaetter
  //cout << "q-x_value: " << q->x_value() << "\n";
  //cout << "q-y_value: " << q->y_value() << "\n";
  //cout << "q-split_value_x: " << q->split_value_x() << "\n";
  //cout << "q-split_value_y: " << q->split_value_y() << "\n";
  //cout << "w-x_value: " << w->x_value() << "\n";
  //cout << "w-y_value: " << w->y_value() << "\n";
  //cout << "w-split_value_x: " << w->split_value_x() << "\n";
  //cout << "w-split_value_y: " << w->split_value_y() << "\n";
   if(cmp(p->split_value_x(),p->split_value_y(),x,y)<=0)
   {
    p->sohn[left]=q; 
    p->sohn[right]=w; 
   }
   else
   {
    p->split_val[0] = x;
    p->split_val[1] = y;
    p->sohn[left]=w;
    p->sohn[right]=q;
   } 
				   
  //cout << "p-x_value: " << p->x_value() << "\n";
  //cout << "p-y_value: " << p->y_value() << "\n";
  //cout << "p-split_value_x: " << p->split_value_x() << "\n";
  //cout << "p-split_value_y: " << p->split_value_y() << "\n";
   while (!st.empty())                          // rebalancieren
   { 
    t=st.pop();
   // cout << "stack\n";
    father = st.empty() ? 0 : st.top();
    t->gr++;  
    float i = t->bal();
  
    //cout << "i" << i << "\n";
    if (i < alpha)
    {
     if (t->sohn[right]->bal()<=d) lrot(t,father);
     else ldrot(t,father);
    }
    else if (i>1-alpha) 
    {
      if (t->sohn[left]->bal() > d ) rrot(t,father);
      else rdrot(t,father);
    }
   }
   p = sink(root,x,y);
   //cout<< p->split_value() <<":"<< p->x_value() << ":" << p->y_value() <<"\n";
   return p;
  }
 } 
}
// ------------------------------------------------------------------
// del()
// loescht Item it im Baum mit x_value(it) = x ,
//                             y_value(it) = y , falls existiert
//         und gibt Zeiger auf it zurueck
// 0 , sonst

ps_item ps_tree::del(x_typ x,x_typ y)
{ 
 ps_item p;
 ps_item t;
 ps_item father;
 ps_item deleted = new ps_node(x,y,0,0);
 
 if (root==0) 
 {
  error_handler(0,"Tree is empty");
  return 0;                                          // leerer Baum
 }
 else
 {
  p=locate(x,y);
  //cout << "located:"<<p->split_value()<<"\n";
  if (p==0) 
  {
   error_handler(0,"Pair is not in tree ");
   st.clear();
   return 0;                                         // Paar nicht im Baum
  }
  else
  { 
   if (p->blatt()) 
   {
    if (p==root)
    {
     error_handler(0,"Root is deleted.");
     p=st.pop();
     root=0;
     anzahl=0;
     return p;                                       // Wurzel geloescht
    } 
    else
    {
     delleaf(p);                                 // (x,y) steht in einem Blatt
    }
   }
   else                                          // (x,y) steht in einem Knoten
   {
    p->x_val = p->y_val = 0;
    fill(p);
    while (!p->blatt())                               // Knoteninhalt loeschen
    {                                                 // und neu auffuellen
     if (cmp(x,y,p->split_value_x(),p->split_value_y())<=0) p=p->sohn[left];
     else p=p->sohn[right];
     st.push(p);
    };
    
    delleaf(p);                                    // loescht zugehoeriges Blatt
   }
 
   while (!st.empty())                                 // rebalancieren
   { 
    t = st.pop();
    //cout << "stack\n";
    //cout << t->split_value()<<":"<<t->x_value()<<":"<<t->y_value()<<"\n";
    father = st.empty() ? 0 : st.top() ;
    t->gr--;              
    float i=t->bal();
    //cout << "i :" << i << "\n";
    if (i<alpha)
    { 
     if (t->sohn[right]->bal() <= d) lrot(t,father);
     else ldrot(t,father);
    }
    else if (i>1-alpha)
    { 
     if(t->sohn[left]->bal() > d) rrot(t,father);
     else rdrot(t,father);
    }
   }
   return(deleted);
  }
 }
} 
   
//-----------------------------------------------------------------------
//enumerate(x1,x2,y0,p)
//gibt alle Punkte (x,y) aus Unterbaum mit Wurzel p
//mit folgender Eigenschaft an :
//  x1 <= x <= x2   &&   y <= y0 
//Voraussetzung : x1 < x2

void ps_tree::enumerate(x_typ x1,x_typ x2,x_typ y0,ps_item p)
{
 if (cmp(y0,p->y_value())>=0 && p!=0)
 {
  if (cmp(x1,p->split_value_x())<=0 && cmp(p->split_value_x(),x2)<=0)
  {
   if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
      cout <<p->split_value_x()<<"("<<p->x_value()<<","<<p->y_value()<<")\n";
   enumerate(x1,x2,y0,p->sohn[left]); 
   enumerate(x1,x2,y0,p->sohn[right]); 
  }
  else if (cmp(p->split_value_x(),x1)<=0) 
       {
        if(cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
           cout <<p->split_value_x()<<"("<<p->x_value()<<","<<p->y_value()<<")\n";
        enumerate(x1,x2,y0,p->sohn[right]);
       }
       else if (cmp(x2,p->split_value_x())<=0) 
       {
        if(cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
           cout <<p->split_value_x()<<"("<<p->x_value()<<","<<p->y_value()<<")\n";
        enumerate(x1,x2,y0,p->sohn[left]);
       }
 }
}
   	
//-----------------------------------------------------------------------
//void pr_ps_tree(ps_item p;int blancs)
//gibt den Baum mit Wurzel p aus

void ps_tree::pr_ps_tree(ps_item p,int blancs)
{
 if (p==0)
   { for (int j=1;j<=blancs;j++) cout << " ";
     cout << "NIL\n";
     return;
   }
 else
   { pr_ps_tree(p->sohn[left],blancs+10); 
     for (int j=1;j<=blancs;j++) cout << " ";
     cout << "(" << p->split_value_x() << "," << p->split_value_y() << "):";
     cout << "(" << p->x_value() << "," << p->y_value() << ")\n";
     pr_ps_tree(p->sohn[right],blancs+10); 
   }
}
 
//-----------------------------------------------------------------------
//min_x_in_rect(x1,x2,y0,p)
//sucht nach Paar (x,y) im Unterbaum von p 
//mit folgender Eigenschaft :
//  min { x ; es gibt y, so dass x1<=x<=x2 und y<=y0 } , falls existiert,
//                                                   0 , sonst.

pair_item ps_tree::min_x_in_rect(x_typ x1,x_typ x2,x_typ y0,ps_item p)
{
 pair_item  c;

 if (p==0)
 {
  return 0;                                   // Baum ist leer.
 }
 else
 {
  c=new pair;
  c->x_pkt=c->y_pkt=0;
  c->valid=false;
  if (cmp(y0,p->y_value())>=0)
  {
   if (!p->blatt())
   {
    if (cmp(x1,p->split_value_x())<=0) 
        c=min_x_in_rect(x1,x2,y0,p->sohn[left]);
    if (!c->valid && cmp(p->split_value_x(),x2)<0) 
        c=min_x_in_rect(x1,x2,y0,p->sohn[right]);
   }
   if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0 
       && cmp(p->y_value(),y0)<=0
       && (!c->valid || cmp(p->x_value(),c->x_pkt)<0)     )
   {
    c->x_pkt=p->x_value();  
    c->y_pkt=p->y_value();  
    c->valid=true;
   }
  }
  return c;
 }
}

//-----------------------------------------------------------------------
//max_x_in_rect(x1,x2,y0,p)
//sucht nach Paar (x,y) im Unterbaum von p 
//mit folgender Eigenschaft :
//  max { x ; es gibt y, so dass x1<=x<=x2 und y<=y0 } , falls existiert,
//                                                   0 , sonst.

pair_item ps_tree::max_x_in_rect(x_typ x1,x_typ x2,x_typ y0,ps_item p)
{
 pair_item c;

 if (p==0) 
 {
  return 0;                                      // Baum ist leer.
 }
 else
 {
  c=new pair;
  c->x_pkt=c->y_pkt=0;
  c->valid=false;
  if (cmp(y0,p->y_value())>=0)
  {
   if (!p->blatt())
   {
    if (cmp(p->split_value_x(),x2)<=0) 
        c=max_x_in_rect(x1,x2,y0,p->sohn[right]);
    if (!c->valid && cmp(x1,p->split_value_x())<0) 
        c=max_x_in_rect(x1,x2,y0,p->sohn[left]);
   }
   if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0 
       && cmp(p->y_value(),y0)<=0
       && (!c->valid || cmp(p->x_value(),c->x_pkt)>0)     )
   {
    c->x_pkt=p->x_value();  
    c->y_pkt=p->y_value();  
    c->valid=true;
   }
  }
  return c;
 }
}
 
//-----------------------------------------------------------------------
//min_y_in_xrange(x1,x2,p)
//sucht Paar (x,y) im Unterbaum von p
//mit folgender Eigenschaft :
// y = min { y ; es gibt x, so dass x1<=x<=x2 } , falls existiert,
//                                            0 , sonst.
 
pair_item ps_tree::min_y_in_xrange(x_typ x1,x_typ x2,ps_item p)
{
 pair_item c1,c2;

 if (p==0)
 {
  return 0;                                      // Baum ist leer.
 }
 else
 {
  c1 = new pair;
  c2 = new pair;
  c1->x_pkt=c1->y_pkt=c2->x_pkt=c2->y_pkt=0; 
  c1->valid=c2->valid=false;
  if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
  {
   c1->x_pkt=p->x_value();
   c1->y_pkt=p->y_value();
   c1->valid=true;
  }
  else if (!p->blatt())
  {
   if (cmp(x1,p->split_value_x())<=0) c1=min_y_in_xrange(x1,x2,p->sohn[left]);
   if (cmp(p->split_value_x(),x2)<0)  c2=min_y_in_xrange(x1,x2,p->sohn[right]);
   if (!c1->valid || (c2->valid && cmp(c2->y_pkt,c1->y_pkt)<0)) c1=c2;
  }
  return c1;
 } 
}
 
//-----------------------------------------------------------------------
// Funktion fuer Destruktor
//-----------------------------------------------------------------------
  
void ps_tree::deltree(ps_item p)
{
 if (p)
 {
  if (!p->blatt())
  {
   deltree(p->sohn[left]);
   deltree(p->sohn[right]);
  }
  delete(p);
 }
}