_range_tree.c

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

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



// ------------------------------------------------------------------
//
// d-dimensional Range Trees
//
// Michael Wenzel     (1990)
//
// Implementation follows
// Data Structure Lecture, K. Mehlhorn, Summer 1989
// K. Mehlhorn: Data Structures and Algorithms, Vol. 3
//
// ------------------------------------------------------------------

#include <LEDA/impl/range_tree.h>

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

#undef TEST
#undef DUMP
#undef STAT

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

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

#ifdef STAT
#define DSTAT print_statistics() 
#else
#define DSTAT
#endif

//------------------------------------------------------------------
// member-functions of class tuple
//
// Michael Wenzel          (1990)
//------------------------------------------------------------------

  tuple::tuple()
      { 
	d=0;
	t=0; }

  tuple::tuple(GenPtr a, GenPtr b)
      { 
	d=2;
	t=new GenPtr[2]; 
        t[0] = a;
        t[1] = b; }

  tuple::tuple(GenPtr a, GenPtr b, GenPtr c)
      { 
	d=3;
	t=new GenPtr[3]; 
        t[0] = a;
        t[1] = b;  
        t[2] = c;  }

  tuple::tuple(int dim)
      { 
	d=dim;
        inf = 0;
	t=new GenPtr[dim]; }

  tuple::~tuple()
      { if (t)
          delete t;
      }

//-------------------------------------------------------------------
//  RANGE TREE
//-------------------------------------------------------------------


int range_tree::tuple_cmp(tuplep p, tuplep q) const
{  int i = p->cmp_dim();
   int stop = (i==0) ? p->d-1 : i-1;
   int res;
   while ((res=cmp_tuple_entry(i,p,q))==0 && i!=stop) 
     i=(i+1)%p->d;
   return res;
}
    
// ------------------------------------------------------------
// lrot() , rrot() , ldrot() , rdrot()
// Rotationen am Knoten p

void range_tree::lrot(bb_item p, bb_item q)
{
  bb_item h = p->sohn[right];
  int help_dim = key(h)->cmp_dim();
  key(h)->set_cmp(key(h)->dimension()-dim+1);

  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 (tuple_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
  list<range_tree_item> L;
  range_tree_item x;

  bb_item s = p->sohn[left];
  if (s->blatt())
    inf(h)->insert_tuple(key(s));
  else
  { L = inf(s)->all_tuples();
    forall(x,L) inf(h)->insert_tuple(x);
    L.clear();
  }

  s = h->sohn[right];
  if (s->blatt())
    inf(h)->del_tuple(key(s));
  else
  { L = inf(s)->all_tuples();
    forall(x,L) inf(p)->del_tuple(x);
  }

  key(h)->set_cmp(help_dim);
}

void range_tree::rrot(bb_item p, bb_item q)
{
  bb_item h = p->sohn[left];
  int help_dim = key(h)->cmp_dim();
  key(h)->set_cmp(key(h)->dimension()-dim+1);

  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 (tuple_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
  list<range_tree_item> L;
  range_tree_item x;
  bb_item s = p->sohn[right];
  if (s->blatt())
    inf(h)->insert_tuple(key(s));
  else
  { L = inf(s)->all_tuples();
    forall(x,L) inf(h)->insert_tuple(x);
    L.clear();
  }

  s = h->sohn[left];
  if (s->blatt())
    inf(p)->del_tuple(key(s));
  else
  { L = inf(s)->all_tuples();
    forall(x,L) inf(p)->del_tuple(x);
  }
  key(h)->set_cmp(help_dim);
}

void range_tree::ldrot(bb_item p, bb_item q)
{
  bb_item h = p->sohn[right];
  bb_item g = h->sohn[left];
  int help_dim = key(h)->cmp_dim();
  key(h)->set_cmp(key(h)->dimension()-dim+1);

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

  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 (tuple_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
  list<range_tree_item> L;
  range_tree_item x;
  range_tree* help = (range_tree*)g->inf;

  g->inf = p->inf;

  bb_item s = p->sohn[right];
  if (s->blatt())
    inf(h)->del_tuple(key(s));
  else
  { L = inf(s)->all_tuples();
    forall(x,L) inf(h)->del_tuple(x);
    L.clear();
  }

  s = h->sohn[left];
  if (s->blatt())
    help->del_tuple(key(s));
  else
  { L = inf(s)->all_tuples();
    forall(x,L) help->del_tuple(x);
    L.clear();
  }

  s = p->sohn[left];
  if (s->blatt())
    help->insert_tuple(key(s));
  else
  { L = inf(s)->all_tuples();
    forall(x,L) help->insert_tuple(x);
  }

  p->inf = (GenPtr) help;
  key(h)->set_cmp(help_dim);
}

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

{
  bb_item h = p->sohn[left];
  bb_item g = h->sohn[right];
  int help_dim = key(h)->cmp_dim();
  key(h)->set_cmp(key(h)->dimension()-dim+1);

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

  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 (tuple_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
  list<range_tree_item> L;
  range_tree_item x;
  range_tree* help = (range_tree*)g->inf;

  g->inf = p->inf;

  bb_item s = p->sohn[left];
  if (s->blatt())
    inf(h)->del_tuple(key(s));
  else
  { L = inf(s)->all_tuples();
    forall(x,L) inf(h)->del_tuple(x);
    L.clear();
  }

  s = h->sohn[right];
  if (s->blatt())
    help->del_tuple(key(s));
  else
  { L = inf(s)->all_tuples();
    forall(x,L) help->del_tuple(x);
    L.clear();
  }

  s = p->sohn[right];
  if (s->blatt())
    help->insert_tuple(key(s));
  else
  { L = inf(s)->all_tuples();
    forall(x,L) help->insert_tuple(x);
  }

  p->inf = (GenPtr) help;
  key(h)->set_cmp(help_dim);
}
 
// ------------------------------------------------------------
// check(x,y,z)                              
// check if a tuple x lies between y and z
// some coordinates are already checked

bool range_tree::check(tuplep x, tuplep y, tuplep z)

{ bool found=true;
  int help_dim = x->cmp_dim();

  for (int i=x->dimension()-dim+1;i<=x->dimension();i++)
  { x->set_cmp(i);
    if ((tuple_cmp(x,y)<0)||(tuple_cmp(x,z)>0)) 
    { x->set_cmp(help_dim);
      return false;
    }
  }
  x->set_cmp(help_dim);
  return found;
}


//-------------------------------------------------------------------
// insert_tuple
// insert a tuple into a range_tree:             
// - insert tuple according to first coordinate in main tree (bb-alpha)
// - insert tuple according to second coordinate in all nodetrees
//   on the path of the main tree from the root to the tuple

range_tree_item range_tree::insert_tuple(tuple* x)

{ bb_tree_item inserted;
  tuplep y;
  int help_dim = x->cmp_dim();
  x->set_cmp(x->dimension()-dim+1);

  DPRINT("insert tuple " << (int)x << " in "  << dim << " dimension ") ;
  DPRINT("and comparedimension " << x->cmp_dim() << "\n");

  if (inserted=rm_tree::lookup(x)) 
  { 
    tuplep y=key(inserted);
    clear_inf((GenPtr&)y);                 // clear tuple and change inf
    y->info() = x->info();
    copy_inf((GenPtr&)y);
    clear_tuple(x);
    delete x;
 
    return y;
  }

  if (dim==1) 
  { bb_tree_item t,father;
    inserted = sinsert(x,0);

    if (!st.empty())
      st.pop();                       // pop father of leaf
  
                                      // 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 Dimension 1\n");

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

    return key(inserted);
  }

  else
  { bb_tree_item it,it1;                
    range_tree*  t = new_range_tree(dim-1);

    it = sinsert(x,t);
    inserted = it ;