/*******************************************************************************
+
+  LEDA 3.5
+
+  _seg_tree.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  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 << "(" << h._x0 << "," << h._x1 << ";" << 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(bb1_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(bb1_item p, bb1_item q)
{
  bb1_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;

 bb1_item re=p->sohn[right];
 bb1_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(bb1_item p, bb1_item q)
{
  bb1_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;

 bb1_item re=p->sohn[right];
 bb1_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(bb1_item p, bb1_item q)
{
  bb1_item h = p->sohn[right];
  //bb1_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(bb1_item p, bb1_item q)

{
  bb1_item h = p->sohn[left];
  //bb1_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;
  }

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

				// insert start_coordinate

  if (!(start=bb1_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



				// insert end_coordinate

  if (!(end=bb1_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 ;

  bb1_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");

  bb1_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(bb1_tree::min()))<0) || (cmp(x,key(bb1_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)
{
  bb1_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(bb1_tree::min()))<0) || (cmp(x,key(bb1_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(bb1_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(bb1_item it,string s)
{
  if (!it) return;

  seg_tree_item i;

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

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

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

