_seg_tree.c

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

				// insert end_coordinate

  if (!(end=bb_tree::lookup(x1)))   // new coordinate
  { h=new seg_node_tree(this);
    end = sinsert(x1,h);
    t=end;

    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)
  	  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);
    }
  }              // end coordinate inserted


     // insert segment into nodelists of leaves of coordinates

  info(start)->insert(i);  
  info(end)->insert(i);

  p=t=root;
  GenPtr x2,x3;

                         // same path
  while (p==t)  // start and end coordinate assigned to different leaves
  { x2=key(p);
    DDUMP(" same path " << (int)x0 << " " << (int)x1 << " " << (int)x2 << "\n");
    if ( cmp(x0,x2)<=0 ) p=p->sohn[left];
      else p=p->sohn[right];
    if ( cmp(x1,x2)<=0 ) t=t->sohn[left];
      else t=t->sohn[right];
  }
				     // now paths to lower and upper part
  while (!p->blatt())                // follow lower path
  { 
    x2=key(p);
    DDUMP(" lower path " << (int)x0 << " " << (int)x2 << "\n");
    if ( cmp(x0,x2)>0 ) 
      p=p->sohn[right];
    else
    { info(p->sohn[right])->insert(i);   // insertion into nodelist
      p=p->sohn[left];
    } 
  }

  while (!t->blatt())               // follow upper path
  { 
    x3=key(t);
    DDUMP(" upper path " << (int)x1 << " " << (int)x3 << "\n");
    if ( cmp(x1,x3)<=0 ) 
      t=t->sohn[left];
    else
    { info(t->sohn[left])->insert(i);  // insertion into nodelist
      t=t->sohn[right];
    } 
  }

#ifdef DUMP
  print_tree();
#endif

  return (r.insert(i)); 
}


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

void Segment_Tree::del(GenPtr x0, GenPtr x1, GenPtr y)

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

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

  bb_item p,q,s,t,father;
  seg_tree_item z;
  seg_node_list help;
  h_segment_p deleted;
  h_segment_p i = new h_segment(x0,x1,y);

  if (!(t=r.lookup(i)))          // segment not in tree
  { delete i;
    DDUMP("delete: segment not in tree\n");
    return;
  }

  deleted = r.key(t);
  r.del(i);                      // delete in tree of all segments

  s=t=root;
  GenPtr x2,x3;

				 // delete segment in nodelists

  while ((s==t)&&(!s->blatt()))       // same path
  { x2=key(s);
    x3=key(t);
    DDUMP(" same path " << (int)x2 << " groesse " << s->groesse() << "\n");
    if ( cmp(x0,x2)<=0 ) s=s->sohn[left];
      else s=s->sohn[right];
    if ( cmp(x1,x3)<=0 ) t=t->sohn[left];
      else t=t->sohn[right];
  }
				     // now paths to lower and upper part
  while (!s->blatt())                // follow lower path
  { 
    x2=key(s);
    DDUMP(" lower path " << (int)x2 << " groesse " << s->groesse() << "\n");
    if ( cmp(x0,x2)>0 ) 
      s=s->sohn[right];
    else
    { info(s->sohn[right])->del(i);   // delete out of nodelist
      s=s->sohn[left];
    } 
  }
  info(s)->del(i);

  while (!t->blatt())               // follow upper path
  { 
    x3=key(t);
    DDUMP(" upper path " << (int)x3 << " groesse " << t->groesse() << "\n");
    if ( cmp(x1,x3)<=0 ) 
      t=t->sohn[left];
    else
    { info(t->sohn[left])->del(i);   // delete out of nodelist
      t=t->sohn[right];
    } 
  }
  info(t)->del(i);
				    // delete in main tree if necessary

  if(empty(s))                      // delete item of start coordinate
  {
    sdel(x0);
    if (!st.empty())                // father exists 
    { q = st.pop();                 // pop father of leaf and set nodelist

      if (!st.empty())
      { p = st.top();
	if (cmp(key(q),key(p))<=0)  // left son deleted
          p = p->sohn[left];
        else                        // right son deleted
	  p = p->sohn[right];
      } 
      else                          // root deleted 
	p = root;

                                          // set nodelist
      help = info(p);
      info(p) = info(q);

      if (p->blatt())
	forall_seg_tree_items(z,*help)
	  if ((start_coord(p,z))||(end_coord(p,z)))
	    info(p)->insert(r.key(z));

      delete help;
      delete q;
    }

    delete info(s);
    delete s;
                               // rebalancieren
    while (!st.empty())
    { p=st.pop();
      father = st.empty() ? 0 : st.top();
      p->gr--;  
      float i = p->bal();

      DDUMP("rebal cur=" << (int)key(p) << " groesse= " << p->groesse() << " bal= " << i << " in main tree \n");

      if (i < alpha)
        if (p->sohn[right]->bal()<=d) lrot(p,father);
        else ldrot(p,father);
      else if (i>1-alpha) 
             if (p->sohn[left]->bal() > d ) rrot(p,father);
  	   else rdrot(p,father);
    }
  }

  if(empty(t))                      // delete item of end coordinate
  {
    sdel(x1);
    if (!st.empty())                // father exists 
    { q = st.pop();                 // pop father of leaf and set nodelist

      if (!st.empty())
      { p = st.top();
	if (cmp(key(q),key(p))<=0)  // left son deleted
          p = p->sohn[left];
        else                        // right son deleted
	  p = p->sohn[right];
      } 
      else                          // root deleted 
	p = root;
                                          // set nodelist
      help = info(p);
      info(p) = info(q);

      if (p->blatt())
	forall_seg_tree_items(z,*help)
	  if ((start_coord(p,z))||(end_coord(p,z)))
	    info(p)->insert(r.key(z));

      delete help;
      delete q;
    }

    delete info(t);
    delete t;

                               // rebalancieren
    while (!st.empty())
    { p=st.pop();
      father = st.empty() ? 0 : st.top();
      p->gr--;  
      float i = p->bal();

      DDUMP("rebal cur=" << (int)key(p) << " groesse= " << p->groesse() << " bal= " << i << " in main tree \n");

      if (i < alpha)
        if (p->sohn[right]->bal()<=d) lrot(p,father);
        else ldrot(p,father);
      else if (i>1-alpha) 
             if (p->sohn[left]->bal() > d ) rrot(p,father);
  	   else rdrot(p,father);
    }
  }

#ifdef DUMP
  print_tree();
#endif



  clear_dim1(x0);
  clear_dim1(x1);
  clear_dim2(y);
  clear_info(inf(deleted));

  delete i;
  delete deleted;
}

//-------------------------------------------------------------------
// query
// returns all items it in the Segment_tree with
//     x0(it) <= x <= x1(it) and y0 <= y(it) <= y1
//    
// by:
// - look for x in the main tree   
//   
// - for all nodes on the path perform a query(y0,y1) on nodelists

list<seg_tree_item> Segment_Tree::query(GenPtr x, GenPtr y0, GenPtr y1)

{ 
  DPRINT("query in main tree " << (int)x << " " << (int)y0 << " " << (int)y1 << "\n");

  bb_item it;
  seg_tree_item z;
  list<seg_tree_item> L,l;

  search(x);
  if (st.empty()) return L;

  if (cmp(x,key(st.top()))==0)             // x-coordinate in tree
    while (!st.empty())
    { it = st.pop();
      l = info(it)->query(y0,y1);
      L.conc(l);
    }

  else                                     // x-coordinate not in tree
  {
     if ((cmp(x,key(bb_tree::min()))<0) || (cmp(x,key(bb_tree::max()))>0))
       return L;
   
     list<seg_tree_item> L1;
     while (!st.empty())
     { it = st.pop();
       L1 = info(it)->query(y0,y1);
       forall(z,L1)
	 if ((cmp(x,x0(z))>=0) && (cmp(x,x1(z))<=0))
	   L.append(z);
       L1.clear();
     }
  }

  return L;
}

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

list<seg_tree_item> Segment_Tree::x_infinity_query(GenPtr y0, GenPtr y1)
{
  return r.query(y0,y1);
}

//-------------------------------------------------------------------
// y_infinity_query
// returns a List of all items it with x0(it) <= x <= x1(it)

list<seg_tree_item> Segment_Tree::y_infinity_query(GenPtr x)
{
  bb_item it;
  seg_tree_item z;
  list<seg_tree_item> L;

  search(x);
  if (st.empty()) return L;

  if (cmp(x,key(st.top()))==0)             // x-coordinate in tree
    while (!st.empty())
    { it = st.pop();
      forall_seg_tree_items(z,*(info(it)))
      L.append(z);
    }

  else                                     // x-coordinate not in tree
  {
     if ((cmp(x,key(bb_tree::min()))<0) || (cmp(x,key(bb_tree::max()))>0))
       return L;
   
     list<seg_tree_item> L1;
     while (!st.empty())
     { it = st.pop();
       forall_seg_tree_items(z,*(info(it)))
	 if ((cmp(x,x0(z))>=0) && (cmp(x,x1(z))<=0))
	   L.append(z);
     }
  }

  return L;
}


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

list<seg_tree_item> Segment_Tree::all_items()
{
  return r.all_items();
}


//-------------------------------------------------------------------
// lookup
// returns a seg_tree_item it with key(it) = (x0,x1,y) if there is one

seg_tree_item Segment_Tree::lookup(GenPtr x0, GenPtr x1, GenPtr y)
{ 
  DPRINT(" lookup in main tree " << (int)x0 << " " << (int)x1 << " " << (int)y << "\n");
  h_segment_p z = new h_segment(x0,x1,y);
  seg_tree_item i = r.lookup(z);   
  delete z;
  return i;
}


//-------------------------------------------------------------------
// clear_tree
// delete all Items and Tree of Items

void Segment_Tree::clear_tree()
{
  if (!root) return;

  clear(root);

  seg_tree_item z;
  h_segment_p q;

  forall_seg_tree_items(z,r)
  { 
    q=r.key(z);
    clear_dim1(x0(q));
    clear_dim1(x1(q));
    clear_dim2(y(q));
    clear_info(inf(q));
    delete q;
  }
  r.clear();

  first = iterator = 0;
  anzahl = 0;
}

//-------------------------------------------------------------------
// clear
// delete nodelists and nodes


void Segment_Tree::clear(bb_item& it)
{
  if (it == 0) return;
  
  if(!it->blatt())
  { clear(it->sohn[left]);
    clear(it->sohn[right]);
  }

  delete info(it);
  delete it;
  it = 0;

}

//-------------------------------------------------------------------
// print     
// prints the tree with nodelists

void Segment_Tree::print(bb_item it,string s)
{
  if (!it) return;

  seg_tree_item i;

  if (!it->blatt())
    print(it->sohn[left],s+"     ");

  cout<< s << (int)key(it) <<"\n";
  cout<< s ; 
  forall_seg_tree_items(i,*info(it))
    cout << "[" << (int)r.key(i) << "]:" << *(r.key(i)) << " ";
  newline;

  if (!it->blatt())
    print(it->sohn[right],s+"     ");
}