_range_tree.c

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

    DDUMP(" bei leerem Baum ");
    t->insert_tuple(x);
                                          // rebalance tree and insert 
					  // tuple into nodelists  

    if (!st.empty())                     // insert correct tuple
    { it1=st.pop();                      // node needs no rebalancing
      DDUMP("bei " << (int)(key(it1)) << " " );
      if (it==bb_tree::max())
      { inf(it1)->insert_tuple(x);     
        x->set_cmp(x->dimension()-dim+1);
      }
      else
      { y= key(succ(it));
	inf(it1)->insert_tuple(y);
        y->set_cmp(y->dimension()-dim+1);
      }
    }

    while (!st.empty())
    { it=st.pop();
      DDUMP("bei " << (int)(key(it)) << " " );
      inf(it)->insert_tuple(x);
      it1 = st.empty() ? 0 : st.top();
      it->gr++;  
      float i = it->bal();
      DDUMP("rebal cur=" << (int)(key(it)) << " groesse= " << it->groesse() << " bal= " << i << " in dimension " << dim  << "\n");

      if (i < alpha)
	if (it->sohn[right]->bal()<=d) lrot(it,it1); 
	else ldrot(it,it1); 
      else if (i>1-alpha) 
             if (it->sohn[left]->bal() > d ) rrot(it,it1);
	     else rdrot(it,it1);
    }
    x->set_cmp(help_dim);
    return key(inserted);
  }
}

//-------------------------------------------------------------------
// delete
// delete a tuple in a range_tree:
// - delete tuple in all nodetrees on the path of the main tree
//   from the root to the tuple
// - delete tuple in main tree

void range_tree::del(tuplep x)

{ 
  tuplep y = del_tuple(x);
  if (y)
  { clear_tuple(y);
    delete y;
  }
}

tuplep range_tree::del_tuple(tuplep x)

{
  DPRINT("delete tuple " << (int)x << " in "  << dim << " dimension\n");

  tuplep deleted;
  int help_dim = x->cmp_dim();
  x->set_cmp(x->dimension()-dim+1);
  if (dim==1)
  { bb_item p,father;
    p = sdel(x);
    if (p)
    { 
      deleted=key(p);
      delete (p);
      if (!st.empty())
        delete (st.pop());
      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 dimension " << dim << "\n");

	tuplep help = key(p);
	int help_dimp = help->cmp_dim();
	help->set_cmp(help->dimension());
        if (i<alpha)
          if (p->sohn[right]->bal() <= d) bb_tree::lrot(p,father);
          else bb_tree::ldrot(p,father);
        else if (i>1-alpha)
               if(p->sohn[left]->bal() > d) bb_tree::rrot(p,father);
               else bb_tree::rdrot(p,father);
        help->set_cmp(help_dimp);
      }
    }
    x->set_cmp(help_dim);
    return deleted; 
  }

  else
  { if (empty()) return 0;
    if (size()==1)                     // only one tuple
    { DDUMP("delete only element\n");
      tuplep y=key(root);
      if ( tuple_cmp(x,y) == 0 )
      { delete(inf(root));
	bb_tree::clear();
        return y;                
      }
    }

    bb_item it,it1;

    x->set_cmp(x->dimension()-dim+1);

    it1 = sdel(x);
    if (!it1) return 0;                  // tuple not in tree
    deleted = key(it1);


    bb_item it2 = pred(it1);
                                         // delete nodelist of it1 or pred(it1)
    it = st.pop();

    if (tuple_cmp(x,key(bb_tree::max()))>=0)
    { DDUMP("old maximum deleted\n");    // old maximum deleted
      delete(inf(it1));
      inf(it)->del_tuple(x);
      it2->inf = it->inf;
    }
    else
      delete(inf(it));

    DDUMP((int)(key(it1)) << " geloescht\n" );

    delete it;
    delete it1; 
					 // rebalance tree
					 // and delete tuple out of nodelists
    while (!st.empty())
    { 
      it=st.pop();
      inf(it)->del_tuple(x); 

      it1 = st.empty() ? 0 : st.top() ;
      it->gr--;              

      float i=it->bal();
      DDUMP("rebal cur=" << (int)(key(it)) << " groesse= " << it->groesse() << " bal= " << i << " in dimension " << dim << "\n");
      if (i<alpha)
        if (it->sohn[right]->bal() <= d) lrot(it,it1);
        else ldrot(it,it1);
      else if (i>1-alpha)
             if(it->sohn[left]->bal() > d) rrot(it,it1);
             else rdrot(it,it1);
    }

    x->set_cmp(help_dim);
    return deleted;
  }
}

//-------------------------------------------------------------------
// query
// returns all tuples x in the range_tree with
//     lower.project(i) <= x.project(i) <= upper.project(i)
//     for x.cmp_dim() <= i <= dim
// by:
// - perform for all tuples x with 
//   lower.project(1) <= x.project(1) <= upper.project(1)
//   a query in a (d-1) dimensional Range-tree 

void range_tree::query_tuples(tuplep lower, tuplep upper, 
                                                    list<range_tree_item>& L)
{ 
  DPRINT("query in dimension " << dim << " on " << (int)(key(root)) << "\n");

  L.clear();

  if (size()==0) return;

  int help_diml = lower->cmp_dim();
  int help_dimu = upper->cmp_dim();

  lower->set_cmp(lower->dimension()-dim+1);
  upper->set_cmp(upper->dimension()-dim+1);

  bb_tree_item it;
  tuplep y,y1;
  
  L.clear();

  if (size()==0) return;

  if (dim==1)                        // one - dimensional tree
  { it=locate(lower);
    while( it && (tuple_cmp(upper,key(it)) >=  0) )
    { DDUMP((int)(key(it)) << "betrachtet\n");
      L.append(key(it));
      it = succ(it);
    }
    lower->set_cmp(help_diml);
    upper->set_cmp(help_dimu);
    return;
  }

                                     // >= 2 dimensional tree
  it=root;
  if (size()==1)                     // no recursive calls
  { 
    if (check(key(it),lower,upper)) L.append(key(it));
    lower->set_cmp(help_diml);
    upper->set_cmp(help_dimu);
    return;
  }

                                     // look for nodetrees
				     // necessary: access to nodes of bb_tree
  bb_tree_item it1=root;   
  while ((it==it1)&&(!it->blatt()))
  { y=key(it);
    y1=key(it1);
    DDUMP(" same path " << (int)y1 << "\n");
    lower->set_cmp(lower->dimension()-dim+1);
    upper->set_cmp(upper->dimension()-dim+1);
    if ( tuple_cmp(lower,y)<=0 ) it=it->sohn[left];
      else it=it->sohn[right];
    if ( tuple_cmp(upper,y1)<=0 ) it1=it1->sohn[left];
      else it1=it1->sohn[right];
  }
				     // now paths to lower and upper part
                                     // or it is a leaf
  y=key(it);
  if (it->blatt())
  { 
    if (check(y,lower,upper)) L.append(y);

    if(it!=it1)                      // it leaf, it != it1 => search on upper path
    { list<range_tree_item> L1;
      while (!it1->blatt())
      { lower->set_cmp(lower->dimension()-dim+1);
        upper->set_cmp(upper->dimension()-dim+1);
        y1=key(it1);
	DDUMP(" upper path " << (int)y1 << "\n");
	if ( tuple_cmp(upper,y1)<=0 ) it1=it1->sohn[left];
	else
	{ bb_item it2=it1->sohn[left];
	  if (!it2->blatt())
	    info(it2)->query_tuples(lower,upper,L1);
          else 
	    if (check(key(it2),lower,upper)) L1.append(key(it2)); 
	  L.conc(L1);
	  it1=it1->sohn[right];
        }
      }
      if (check(key(it1),lower,upper)) L.append(key(it1)); 
    }
    lower->set_cmp(help_diml);
    upper->set_cmp(help_dimu);
    return;
  }

                                     // it no leaf => paths parted 
  list<range_tree_item> L1;
  while (!it->blatt())
  { y=key(it);
    DDUMP(" lower path " << (int)y << "\n");
    lower->set_cmp(lower->dimension()-dim+1);
    upper->set_cmp(upper->dimension()-dim+1);
    if ( tuple_cmp(lower,y)>0 ) it=it->sohn[right];
    else
    { bb_item it2=it->sohn[right];
      if (!it2->blatt())
        info(it2)->query_tuples(lower,upper,L1);
      else 
	if (check(key(it2),lower,upper)) L1.append(key(it2)); 
      L.conc(L1);
      it=it->sohn[left];
    }
  } 
  if (check(key(it),lower,upper)) L.append(key(it));

  while (!it1->blatt())
  { y1=key(it1);
    DDUMP(" upper path " << (int)y1 << "\n");
    lower->set_cmp(lower->dimension()-dim+1);
    upper->set_cmp(upper->dimension()-dim+1);
    if ( tuple_cmp(upper,y1)<=0 ) it1=it1->sohn[left];
    else
    { bb_item it2=it1->sohn[left];
      if (!it2->blatt())
        info(it2)->query_tuples(lower,upper,L1);
      else 
	if (check(key(it2),lower,upper)) L1.append(key(it2)); 
      L.conc(L1);
      it1=it1->sohn[right];
    }
  }
  if (check(key(it1),lower,upper)) L.append(key(it1)); 

  lower->set_cmp(help_diml);
  upper->set_cmp(help_dimu);
  return;
}

//-------------------------------------------------------------------
// all_tuples
// returns all range_tree_items x in the range_tree 

list<range_tree_item> range_tree::all_tuples()

{ 
  DPRINT("all_tuples of " << int(this) << " in dimension " << dim << "\n");
  
  bb_item it;
  list<range_tree_item> L;

  init_iterator();
  while (it=rm_tree::move_iterator())
    L.append(key(it));

  return L;

}


//--------------------------------------------------------------------
// Minima & Maxima

range_tree_item range_tree::min(int i)
{ if (i>dim || i<1)
    return 0;
  else 
  { range_p r=this; 
    while (--i) r=(range_p)r->root->inf;
    return key(((bb_tree*)r)->min()); 
  }
}

range_tree_item range_tree::max(int i)
{ if (i>dim || i<1)
    return 0;
  else 
  { range_p r=this; 
    while (--i) r=(range_p)r->root->inf;
    return key(((bb_tree*)r)->max()); 
  }
}

//--------------------------------------------------------------------
//  Clear & Destruktor
//  


void range_tree::clear_tuple(tuplep& y) 
{ 
   DPRINT("clear von " << (int)y << "\n");
   clear_key((GenPtr&)y);
   clear_inf((GenPtr&)y);
}

void range_tree::del_tree(bb_item p)
{ 
  if (!p->blatt())
  {  
     delete inf(p);
     del_tree(p->sohn[left]);
     del_tree(p->sohn[right]); 
  }
  else
    if (p==bb_tree::max())
      delete inf(p);

  delete(p);

}

void range_tree::clear()
{ range_tree_item it;
  list<range_tree_item> L=all_tuples();
  forall(it,L) 
  { 
     clear_tuple(it);
     delete it;       
  }

  if (dim==1)
    bb_tree::clear();
  else
    if (root)
      del_tree(root);

  root=0;
  anzahl=0;
  first=0;
}


range_tree::~range_tree()
{ 

   DPRINT("Destruktor in Dimension " << dim << "\n");

   if (root)
   { del_tree(root);
     root = 0;
   }

}

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