_iv_tree.c

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

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


// -------------------------------------------------------------------
//
//  Interval Trees
//
//  Michael Seel   (1990/91)
//
// Implementation as described in
// Kurt Mehlhorn: Data Structures and Algorithms 3, section VIII.5.1.1
//
// -------------------------------------------------------------------

#include <LEDA/impl/iv_tree.h>


// -------------------------------------------------------------
// member functions von iv_tree
// -------------------------------------------------------------

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

void iv_tree::lrot(iv_item p, iv_item q)

// p ist der zentrale Knoten um den rotiert wird
// q ist der Vater von p

{ 
  iv_item h = p->son[_right];
  p->son[_right] = h->son[_left];
  h->son[_left] = p;
   
  if (!q) root=h;
  else
  {
   if ( p == q->son[_left] )   q->son[_left]=h;
   else q->son[_right]=h;
  }; 
  
  p->gr=p->son[_left]->groesse()+p->son[_right]->groesse();
  h->gr=p->groesse()+h->son[_right]->groesse();

  reorganize_nodelist(h,p);
}

void iv_tree::rrot(iv_item p, iv_item q)

// p ist der zentrale Knoten um den rotiert wird
// q ist der Vater von p

{ 
  iv_item h = p->son[_left];
  p->son[_left] = h->son[_right];
  h->son[_right] = p;

  if (!q) root=h;
  else
  {
   if ( p == q->son[_left] ) q->son[_left] = h;
   else q->son[_right] = h; 
  };

  p->gr=p->son[_left]->groesse()+p->son[_right]->groesse();
  h->gr=p->groesse()+h->son[_left]->groesse();

  reorganize_nodelist(h,p);
}

void iv_tree::ldrot(iv_item p, iv_item q)
{ 
  iv_item h = p->son[_right];
  iv_item t = h->son[_left];
  rrot(h,p);
  lrot(p,q);
}

void iv_tree::rdrot(iv_item p, iv_item q)
{
  iv_item h = p->son[_left];
  iv_item t = h->son[_right];
  lrot(h,p);
  rrot(p,q);
}
 
// ------------------------------------------------------------------
// reorganize_nodelist()
// reorganisiert die nach der Rotation falsch mit Intervallen belegten
// Nodelists entsprechend neu.

void iv_tree::reorganize_nodelist(iv_item father, iv_item son)
{
  // nach Aendern des Dictionary-Typs in perfekte BB_trees mit Konstruk-
  // tionsprozedur, die aus einer Liste von n geordneten Knoten ein neu-
  // es Dictionary in Zeit O(n) erzeugt, werden von den folgenden 4 Ite-
  // rationen je 2 in ein Misch_Sort Verfahren abgeaendert und die so
  // auf father und son verteilten Intervalle in Linearzeit in die Kno-
  // ten dictionarys eingebunden

  dic_item it;
  nodelist_p fx = new nodelist;
  nodelist_p fy = new nodelist;
  nodelist_p sx = new nodelist;
  nodelist_p sy = new nodelist;

  forall_items(it,*(father->x_nodelist())) // father->x_nodelist
		 			       // liefert Pointer
		 			       // auf x-Dictionary
      {
	 if (split_in_x_interval(father , x_nodelist(father)->key(it)))
	    fx->insert(x_nodelist(father)->key(it),x_nodelist(father)->inf(it));
         else
	    sx->insert(x_nodelist(father)->key(it),x_nodelist(father)->inf(it));
      };
  // die x-Knotenliste des Vaters wird durchsucht und alle passenden
  // Intervalle der Vater-Knotenliste zugeordnet, Rest an den Sohn

  forall_items(it,*(son->x_nodelist())) // son->x_nodelist
		         		    // liefert Pointer
				            // auf x-Dictionary
      {
	 if (split_in_x_interval(father , x_nodelist(son)->key(it))) 
	    fx->insert(x_nodelist(son)->key(it),x_nodelist(son)->inf(it));
         else
	    sx->insert(x_nodelist(son)->key(it),x_nodelist(son)->inf(it));
      };
  // die x-Knotenliste des Sohns wird durchsucht und alle passenden
  // Intervalle der Vater-Knotenliste zugeordnet, Rest an den Sohn


  forall_items(it,*(father->y_nodelist())) // father->y_nodelist
		        	               // liefert Pointer
				               // auf y-Dictionary
      {
	 if (split_in_y_interval(father , y_nodelist(father)->key(it)))
	    fy->insert(y_nodelist(father)->key(it),y_nodelist(father)->inf(it));
         else
	    sy->insert(y_nodelist(father)->key(it),y_nodelist(father)->inf(it));
      };
  // die y-Knotenliste des Vaters wird durchsucht und alle passenden
  // Intervalle der Vater-Knotenliste zugeordnet, Rest an den Sohn

  forall_items(it,*(son->y_nodelist())) // son->y_nodelist
					    // liefert Pointer
					    // auf y-Dictionary
      {
	 if (split_in_y_interval(father, y_nodelist(son)->key(it)))
	    fy->insert(y_nodelist(son)->key(it),y_nodelist(son)->inf(it));
         else
	    sy->insert(y_nodelist(son)->key(it),y_nodelist(son)->inf(it));
      };
  // die y-Knotenliste des Sohns wird durchsucht und alle passenden
  // Intervalle der Vater-Knotenliste zugeordnet, Rest an den Sohn

  delete x_nodelist(father);
  delete y_nodelist(father);
  delete x_nodelist(son);
  delete y_nodelist(son);
  // alte Dictionaries werden geloescht und freigegeben
  father->x_nl = fx;
  father->y_nl = fy;
  son->x_nl = sx;
  son->y_nl = sy;
  // Knotenlisten werden mit neu angeordneten Dictionaries intialisiert
}


// ------------------------------------------------------------
// search()
// nachher: st = ( pk ,..., p1 ) mit 
//          pk = locate(y) , p1 = root 
//          p1 , ... , pk ist Suchpfad nach y
// liefert inneren Knoten k mit key(k) = y , falls existiert
//         0                               , sonst

iv_item iv_tree::search(split_item x)

{ 
  st.clear();
  iv_item p = root;
  iv_item searched = 0;

  if (!root) return 0;         // Baum leer
  while (!p->blatt())
  { 
    if (cmp(x,split_value(p))<=0)
    {
      if (cmp(x,split_value(p))==0) searched = p;
      st.push(p);
      p = p->son[_left];
    }
    else
    {
      st.push(p);
      p = p->son[_right];
    }
  }
  st.push(p);
  return searched;
}


// ------------------------------------------------------------------
// iv_insert(x_typ,x_typ)
// fuegt ein neues Intervall (x,y) in den Baum ein
// gibt Zeiger auf Knoten, in dessen Knotenliste Intervall
// eingefuegt wurde, zurueck.

iv_item iv_tree::iv_insert(x_typ x, x_typ y)
{
 if (y<x)
 {
  error_handler(0,"kein Intervall zum einfuegen");
  return 0;
 }
 else
 {
  interval_item x_iv = new interval(x,y);
  interval_item y_iv = new interval(y,x);
  return ins(x_iv,y_iv,++interval_nb);
 }
}

// ------------------------------------------------------------------
// ins(interval_item,interval_item,int)
// fuegt den entsprechenden Knoten in die Grundstruktur mit dem 
// entsprechenden split_value und fuegt die beiden Intervalle am
// entsprechenden Knoten in die Knotenlisten

iv_item iv_tree::ins(interval_item x, interval_item y, int lfnr) 
{
 iv_item p;
 iv_item t;
 iv_item father;
 split_pair x_pair(x->koo1,-lfnr);
 split_item x_split = &x_pair; 
 
 if (!root)                                     // neuer Baum
 { 
  root = new iv_node(x_split);
  anzahl=1;
 }
 else     // Baum existiert schon !!
  if (root->blatt())
  {
    if (cmp(x_split,split_value(root))<0)
    {
     iv_item help = new iv_node(x_split);
     root = new iv_node(x_split,node,help,root);
     if (x_split->key1==split_value(root->son[_right])->key1)
      nodelist_swap(root , root->son[_right]);
     anzahl++;
    }
    else
     if (cmp(x_split,split_value(root))>0)
     {
      iv_item help = new iv_node(x_split);
      root = new iv_node(split_value(root),node,root,help);
      nodelist_swap(root , root->son[_left]);
      anzahl++;
     }
  }
  else // in Knoten von nicht trivialem Baum wird eingefuegt
  {
    search(x_split);
    p = st.pop();
    father = st.top();
  
    if(cmp(x_split,split_value(p))<0)
    {
     iv_item help = new iv_node(x_split);
     p = new iv_node(x_split,node,help,p);
     // neuer Knoten in p mit split x, x-Blatt links, p-Blatt rechts
     if (x_split->key1==split_value(p->son[_right])->key1)
      nodelist_swap(p , p->son[_right]);

     if (cmp(split_value(p),split_value(father))<=0)
       father->son[_left] = p;
     else
       father->son[_right] = p;
     anzahl++;
    }
    else
     if (cmp(x_split,split_value(p))>0)
     {           
      iv_item help = new iv_node(x_split);
      p = new iv_node(split_value(p),node,p,help);
      // neuer Knoten in p mit split p, p-Blatt links, x-Blatt rechts
      nodelist_swap(p , p->son[_left]);

      if (cmp(split_value(p),split_value(father))<=0)
        father->son[_left] = p;
      else
        father->son[_right] = p;
      anzahl++;
     }
  }

  while (!st.empty())                          // rebalancieren
  { 
    t=st.pop();
    father = st.empty() ? 0 : st.top();
    t->gr++;  
    float i = t->bal();
    if (i < alpha)
    {
     if (t->son[_right]->bal()<=d)
       lrot(t,father);
     else
       ldrot(t,father);
    }
    else
    if (i>1-alpha) 
    {
      if (t->son[_left]->bal()>d)
	rrot(t,father);
      else
	rdrot(t,father);
    }
  }
  
  p = sink(root,x,y,lfnr);
  return p;	
}


// ------------------------------------------------------------------
// sink()
// laesst Intervall im Baum bis zu dem Knoten v abwaerts gleiten an dem 
// gilt: 1.Komponente von split_value(v) <in> Intervall <Teilmenge von> x_range(v)

iv_item iv_tree::sink(iv_item v, interval_item x, interval_item y, int lfnr)
{
   if (v)
   {
     if (split_in_x_interval(v,x))
     {
       if (x_nodelist(v)->lookup(x))
       {
         error_handler(0,"Interval wurde schon eingefuegt!\n");
	 split_pair h(x->koo1,-lfnr);
	 split_item hi=&h;
	 del(hi);
	 return 0;
       }
       x_nodelist(v)->insert(x,lfnr);
       y_nodelist(v)->insert(y,lfnr);
       return v;
     }
     else
     {
       if (x->cmp(x->koo2,split_value(v)->key1) < 0)
       { 
	 return sink(v->son[_left],x,y,lfnr);
       }
       else
       if (x->cmp(split_value(v)->key1,x->koo1) < 0)
       {
	 return sink(v->son[_right],x,y,lfnr);
       }
     }
   }

   return 0;
}

// ------------------------------------------------------------------
// iv_delete(x_typ,x_typ)
// loescht ein Intervall (x,y) aus dem Baum
// gibt Zeiger auf geloeschtes intervall zurueck 

void iv_tree::iv_delete(x_typ x, x_typ y)
{
  if (y<x) 
  {
   error_handler(0,"kein Intervall!\n");
   return;
  }
  else
  if (!root) error_handler(0,"Baum ist leer!\n");
  else
  {
   iv_item v = root;
   interval xi(x,y);
   interval yi(y,x);
   interval_item x_iv = &xi;
   interval_item y_iv = &yi; 
   while ( !split_in_x_interval(v,x_iv) && !v->blatt() )
   {
    if (split_value(v)->cmp(y,split_value(v)->key1) < 0)
    {
      v = v->son[_left];
    }
    if (split_value(v)->cmp(split_value(v)->key1,x) < 0) 
    {
      v = v->son[_right];
    }
   }
   // nun ist v der Knoten an dem das Intervall [x,y] abgespeichert sein muesste
   dic_item help1 = x_nodelist(v)->lookup(x_iv);
   dic_item help2 = y_nodelist(v)->lookup(y_iv);
   if (!(help1 && help2))
   {
    error_handler(0,"Intervall nicht vorhanden!\n");
    return;
   }
   else
   {
    split_pair s(x_nodelist(v)->key(help1)->koo1,-x_nodelist(v)->inf(help1));
    split_item search_split = &s; 
    x_nodelist(v)->del_item(help1);
    y_nodelist(v)->del_item(help2);
    if (!del(search_split)) 
      error_handler(1,"Intervall geloescht, Grundstruktur nicht in Ordnung\n");
   } 
  }
}


// ------------------------------------------------------------------
// del()
// loescht Item it im Baum mit split(it)=y , falls existiert
// gibt 1 zurueck, falls existent und geloescht
// gibt 0 zurueck, falls nicht existent

int iv_tree::del(split_item y)
{
  st.clear();
  if (root==0) return 0;                         // s.n.

  if (root->blatt())                             // Wurzel loeschen
    if (cmp(y,split_value(root))==0)
    {