_seg_tree.c

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

/*******************************************************************************
+
+  LEDA  3.0
+
+
+  _seg_tree.c
+
+
+  Copyright (c) 1992  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 6600 Saarbruecken, FRG     
+  All rights reserved.
+ 
*******************************************************************************/



// ------------------------------------------------------------------
//
// full dynamic Segment Trees
//
// Michael Wenzel     (1990)
//
// Implementation as described in
// Kurt Mehlhorn: Data Structures and Algorithms 3
//
// ------------------------------------------------------------------


#include <LEDA/impl/seg_tree.h>

enum left_or_right {left = 0, right = 1};

#undef TEST
#undef DUMP

#ifdef TEST
#define DPRINT(x) cout << x
#else
#define DPRINT(x)
#endif

#ifdef DUMP
#define DDUMP(x) cout << x
#else
#define DDUMP(x)
#endif

ostream& operator<<(ostream& s, h_segment& h) 
{ 
  s<<"("<<(int)h._x0<<","<<(int)h._x1<<";"<<(int)h._y<<")";
  return s;
}

//-------------------------------------------------------------------
// member functions
//-------------------------------------------------------------------

int seg_node_tree::cmp(GenPtr x,GenPtr y) const
{ return father->seg_cmp((h_segment_p)x,(h_segment_p)y); }

// ------------------------------------------------------------
// query
// returns a List of all items it with y0 <= y(it) <= y1

list<seg_tree_item> seg_node_tree::query(GenPtr y0, GenPtr y1)
{ 
  DPRINT(" query in nodelist\n");

  list<seg_tree_item> L;
 

  h_segment_p r = father->new_y_h_segment(y0);
  seg_tree_item it = locate(r);

  if (it)
  { while ( it!=min() && father->cmp_dim2(key(it)->_y,y0)==0) it = pred(it);
    while ( it && father->cmp_dim2(key(it)->_y,y1)<=0)
    { L.append(it);
      it = succ(it);
     }
   }

  delete r;
  return L;
}


//-------------------------------------------------------------------
// all_items
// returns all items in the nodelist

list<seg_tree_item> seg_node_tree::all_items()
{
  list<seg_tree_item> L;
  seg_tree_item z;

  forall_seg_tree_items(z,*this)
    L.append(z);
  
  return L;
}


//-------------------------------------------------------------------

Segment_Tree::Segment_Tree() : r(this)  {} 
Segment_Tree::~Segment_Tree() { clear(root); }

int Segment_Tree::seg_cmp(h_segment_p p, h_segment_p q)
{ int a;
  if (a = cmp_dim2(p->y(), q->y())) return a;
  if (a = cmp_dim1(p->x0(),q->x0())) return a;
  return cmp_dim1(p->x1(), q->x1());
}

// ------------------------------------------------------------
// empty
// returns true, iff for all seg_tree_items it in nodelist(it):
//                 key(it) is not a start- or endoordinate of key(it)

int Segment_Tree::empty(bb_item it)
{
  DPRINT(" empty of "<<(int)key(it)<<"\n");
  int erg=true;
  seg_tree_item i;

  forall_seg_tree_items(i,*info(it))
    if ( (cmp(key(it),x0(i))==0) || (cmp(key(it),x1(i))==0) )
      erg = false;

  DPRINT("empty ergibt "<<erg<<"\n");
  return erg;
}   

// ------------------------------------------------------------
// lrot() , rrot() , ldrot() , rdrot()
// Rotationen am Knoten p

void Segment_Tree::lrot(bb_item p, bb_item q)
{
  bb_item h = p->sohn[right];

  DDUMP("lrot "<< (int)key(p)) ; 
    if (q) DDUMP(" Vater " << (int)key(q));
  DDUMP("\n");

  p->sohn[right] = h->sohn[left];
  h->sohn[left] = p;
  if (!q)
    root=h;
  else
  { if (cmp(key(h),key(q))>0)
      q->sohn[right]=h;
    else
      q->sohn[left]=h;
  }
  p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  h->gr=p->groesse()+h->sohn[right]->groesse();

						// update nodelists
 seg_tree_item i;

 bb_item re=p->sohn[right];
 bb_item s=p->sohn[left];

 seg_node_list help = info(h);
 info(h) = info(p);

 info(p) = new seg_node_tree(this);

 forall_seg_tree_items(i,*(info(re)))
   if ( ( (!re->blatt()) 
	  ||((!start_coord(re,i))&&(!end_coord(re,i))) )
      && ( (!s->blatt())
	   ||((!start_coord(s,i))&&(!end_coord(s,i))) ) 
      && (info(s)->member(r.key(i))) )

     info(p)->insert(r.key(i));
 
 forall_seg_tree_items(i,*(info(p)))
 { info(re)->del(r.key(i));
   info(s)->del(r.key(i));
 }

 forall_seg_tree_items(i,*help)
 { info(re)->insert(r.key(i));
   info(h->sohn[right])->insert(r.key(i));
 } 

 delete help;

}

void Segment_Tree::rrot(bb_item p, bb_item q)
{
  bb_item h = p->sohn[left];

  DDUMP("rrot "<< (int)key(p)) ; 
    if (q) DDUMP(" Vater " << (int)key(q));
  DDUMP("\n");

  p->sohn[left] = h->sohn[right];
  h->sohn[right] = p;
  if (!q) root=h;
  else
  { if (cmp(key(h),key(q))>0)
      q->sohn[right] = h;
    else
      q->sohn[left] = h; }
  p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  h->gr=p->groesse()+h->sohn[left]->groesse();

						// update nodelists
 seg_tree_item i;

 bb_item re=p->sohn[right];
 bb_item s=p->sohn[left];

 seg_node_list help = info(h);
 info(h) = info(p);

 info(p) = new seg_node_tree(this);
 /* forall_seg_tree_items(i,*(info(s)))
    if (info(re)->member(r.key(i)))
      info(p)->insert(r.key(i));    */
 
 forall_seg_tree_items(i,*(info(s)))
   if ( ( (!s->blatt()) 
	  ||((!start_coord(s,i))&&(!end_coord(s,i))) )
      && ( (!re->blatt())
	   ||((!start_coord(re,i))&&(!end_coord(re,i))) ) 
      && (info(re)->member(r.key(i))) )

     info(p)->insert(r.key(i));

 forall_seg_tree_items(i,*(info(p)))
 { info(re)->del(r.key(i));
   info(s)->del(r.key(i));
 }

 forall_seg_tree_items(i,*help)
 { info(s)->insert(r.key(i));
   info(h->sohn[left])->insert(r.key(i));
 } 

 delete help;

}

void Segment_Tree::ldrot(bb_item p, bb_item q)
{
  bb_item h = p->sohn[right];
  bb_item g = h->sohn[left];

  DDUMP("ldrot "<< (int)key(p)) ; 
    if (q) DDUMP(" Vater " << (int)key(q));
  DDUMP("\n");

  rrot(h,p);
  lrot(p,q);

  /*
  p->sohn[right] = g->sohn[left];
  h->sohn[left] =  g->sohn[right];
  g->sohn[left] = p;
  g->sohn[right] = h;
  if (!q) root=g;
  else
  { if (cmp(key(h),key(q))>0)
      q->sohn[right] =g ;
    else 
      q->sohn[left] = g ; }
  p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  h->gr=h->sohn[left]->groesse()+h->sohn[right]->groesse();
  g->gr=p->groesse()+h->groesse();
						// update nodelists
  seg_tree_item i;

  seg_node_list help = info(g);
  info(g) = info(p);
  info(p) = new seg_node_tree(this);

  forall_seg_tree_items(i,*help)
    info(p->sohn[right])->insert(r.key(i));

  forall_seg_tree_items(i,*(info(p->sohn[left])))
    if (info(p->sohn[right])->member(r.key(i)))
      info(p)->insert(r.key(i));

  forall_seg_tree_items(i,*(info(p)))
  { info(p->sohn[left])->del(r.key(i));
    info(p->sohn[right])->del(r.key(i));
  }
  
  forall_seg_tree_items(i,*(info(h)))
    info(p->sohn[right])->insert(r.key(i));

  forall_seg_tree_items(i,*(info(h->sohn[left])))
    if (info(h->sohn[right])->member(r.key(i)))
      info(h)->insert(r.key(i));

  seg_node_list help1 = info(h->sohn[right]);
  info(h->sohn[right]) = new seg_node_tree(this);

  forall_seg_tree_items(i,*help1)
  { if (!((info(h->sohn[left]))->member(r.key(i))))
      info(h->sohn[right])->insert(r.key(i));
    else
      info(h->sohn[left])->del(r.key(i));
  }

  forall_seg_tree_items(i,*help)
    info(h->sohn[left])->insert(r.key(i));

  delete help;
  delete help1;
*/
   
}

void Segment_Tree::rdrot(bb_item p, bb_item q)

{
  bb_item h = p->sohn[left];
  bb_item g = h->sohn[right];

  DDUMP("rdrot "<< (int)key(p)) ; 
    if (q) DDUMP(" Vater " << (int)key(q));
  DDUMP("\n");

  lrot(h,p);
  rrot(p,q);

/*  p->sohn[left] = g->sohn[right];
  h->sohn[right] =  g->sohn[left];
  g->sohn[right] = p;
  g->sohn[left] = h;
  if (!q) root=g;
  else
  { if (cmp(key(h),key(q))>0)
      q->sohn[right] =g ;
    else 
      q->sohn[left] = g ; }
  p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  h->gr=h->sohn[left]->groesse()+h->sohn[right]->groesse();
  g->gr=p->groesse()+h->groesse();
						// update nodelists
  seg_tree_item i;

  seg_node_list help = info(g);
  info(g) = info(p);
  info(p) = new seg_node_tree(this);

  forall_seg_tree_items(i,*help)
    info(p->sohn[left])->insert(r.key(i));

  forall_seg_tree_items(i,*(info(p->sohn[right])))
    if (info(p->sohn[left])->member(r.key(i)))
      info(p)->insert(r.key(i));

  forall_seg_tree_items(i,*(info(p)))
  { info(p->sohn[left])->del(r.key(i));
    info(p->sohn[right])->del(r.key(i));
  }
  
  forall_seg_tree_items(i,*(info(h)))
    info(p->sohn[left])->insert(r.key(i));

  forall_seg_tree_items(i,*(info(h->sohn[right])))
    if (info(h->sohn[left])->member(r.key(i)))
      info(h)->insert(r.key(i));

  seg_node_list help1 = info(h->sohn[left]);
  info(h->sohn[left]) = new seg_node_tree(this);

  forall_seg_tree_items(i,*help1)
  { if (!((info(h->sohn[right]))->member(r.key(i))))
      info(h->sohn[left])->insert(r.key(i));
    else
      info(h->sohn[right])->del(r.key(i));
  }

  forall_seg_tree_items(i,*help)
    info(h->sohn[right])->insert(r.key(i));

  delete help;
  delete help1;
*/
   
}
 

//-------------------------------------------------------------------
// insert
// insert a segment into a Segment_tree:             
// - insert x-coordinates in main tree (bb-alpha) 
//          and rotate (if necessary)
// - insert segment on nodes 
//          immediately below the paths to x-coordinates
// - insert segment into the tree of all segments

seg_tree_item Segment_Tree::insert(GenPtr x0, GenPtr x1, GenPtr y, GenPtr inf)

{
  DPRINT(" insert segment " << (int)x0 << " " << (int)x1 << " " << (int)y << " in main tree \n" );

  seg_tree_item inserted,j;

  if (!(cmp(x0,x1)))                         // empty segment
    return 0;

  copy_dim1(x0);
  copy_dim1(x1);
  copy_dim2(y);
  copy_info(inf);

  h_segment_p i = new h_segment(x0,x1,y,inf);

  if (inserted=r.lookup(i)) 
  { delete i;
    r.info(inserted)=inf;
    return inserted;
  }

  bb_item t,father,p;
  bb_item start,end;
  seg_node_list h;

				// insert start_coordinate

  if (!(start=bb_tree::lookup(x0)))        // new coordinate
  { h=new seg_node_tree(this);
    start = sinsert(x0,h);
    t=start;
  
    if (!st.empty())
    { father = st.pop();         // pop father of leaf and set nodelist
      h=new seg_node_tree(this);
      info(father) = h;
      p = succ(t); 
      if (p)
      { list<seg_tree_item> L;
        L=info(p)->all_items();
        forall(j,L)
  	{ DDUMP("Item "<<*(r.key(j))<<" in Knoten "<<(int)key(p)<<"\n");
          if (end_coord(p,j))
            info(t)->insert(r.key(j));
          else if (!start_coord(p,j))
               { info(father)->insert(r.key(j));
                 info(p)->del(r.key(j));
               }
        }
      }
    }
    
                                 // rebalancieren
    while (!st.empty())
    { t=st.pop();
      father = st.empty() ? 0 : st.top();
      t->gr++;  
      float i = t->bal();

      DDUMP("rebal cur=" << (int)key(t) << " groesse= " << t->groesse() << " bal= " << i << " in main tree\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);
    }
  }              // start coordinate inserted