_rs_tree.c

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

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


#include <LEDA/impl/rs_tree.h>

//
// (Generalized) Randomized Search Trees
// -------------------------------------
// by C.Aragon and R.Seidel
//
//
// variable probability distribution
// doubly-linked with pred-succ-pointer
//
// 6/92, M.Paul
//

/* still to implement: conc, split */



// create empty rs_tree
// with dummy node at root, where all leafs are pointing to
//
rs_tree::rs_tree( double pr )
{
  root = new rst_node ;
  r_child(root) = p_item(root) = s_item(root) = root ;

  // value of l_child(root) and parent(root) are always undefined

  count = 0 ;  
  if( pr>0 && pr<1 )
    log_prob = log(pr) ;
  else
    log_prob = 0 ;
}



// create copy of rst
//
rs_tree::rs_tree( const rs_tree& rst )
{
  root = new rst_node ;				// create empty tree
  r_child(root) = p_item(root) = s_item(root) = root ;
  l_child(root) = parent(root) = 0 ;
  count = 0 ;  log_prob = rst.log_prob ;

  register rst_item p = rst.first_item() ;

  while( p ) {					// insert all elements
    insert( p->key, p->inf ) ;
    rst.copy_key( p->key ) ;  
    rst.copy_inf( p->inf ) ;
    p = rst.next_item(p) ;
  }
}



// assignment operator
//
rs_tree& rs_tree::operator=( const rs_tree& rst )
{
  clear() ;  
  log_prob = rst.log_prob ;

  register rst_item p = rst.first_item() ;

  while( p ) {
    insert( p->key, p->inf ) ;
    p = rst.next_item(p) ;
  }

  return *this ;
}



// delete rs_tree
//
rs_tree::~rs_tree()
{
  clear() ;
  delete root ;
}



// clear all entries in rs_tree
//
void rs_tree::clear()
{
  register rst_item q,
		    p = first_item() ;
		  
  while( p ) {
    clear_key( p->key ) ;  clear_inf( p->inf ) ;
    q = next_item(p) ;
    delete p ;
    p = q ;
  }

  r_child(root) = p_item(root) = s_item(root) = root ;
  l_child(root) = parent(root) = 0 ;
  count = 0 ;
}



// returns entry with searchkey and assigns parent
//
rst_item rs_tree::search( GenPtr searchkey, rst_item& parent ) const 
{
  register GenPtr key = searchkey ;
  root->key = key ;				// ensure stop at root

  register rst_item pp = root,			// parent of p 
		    p = r_child(pp) ;		// actual node

  if( int_type() ) {
    register GenPtr k = p->key ;		// actual key

    while( k != key ) {
      pp = p ;
      if( long(key) < long(k) ) 
        p = l_child(p) ; 
      else 
        p = r_child(p) ;
      k = p->key ;
    } ;
  }
  else {
    register int k = cmp(key,p->key) ;		// actual comparison

    while( k ) {
      pp = p ;
      if( k<0 ) 
        p = l_child(p) ; 
      else 
        p = r_child(p) ;
      k = cmp(key,p->key) ;
    } ;
  }

  parent = pp ;
  return (p==root) ? 0 : p ;
}



// locate item with key >= searchkey
//
rst_item rs_tree::locate( GenPtr searchkey ) const
{ 
  if( empty() )
    return 0 ;
    
  rst_item pp,
           p = search( searchkey, pp ) ; 
  
  if( !p ) {
    if( cmp(searchkey,pp->key) < 0 )
      p = pp ;
    else
      p = succ(pp) ;
  }

  return p ;
}



// locate item with key <= searchkey
//
rst_item rs_tree::locate_pred( GenPtr searchkey ) const
{ 
  if( empty() )
    return 0 ;
    
  rst_item pp,
           p = search( searchkey, pp ) ; 
  
  if( !p ) {
    if( cmp(searchkey,pp->key) < 0 )
      p = pred(pp) ;
    else
      p = pp ;
  }

  return p ;
}



// insert new element with integer key as child of leaf pn
//
rst_item rs_tree::int_insert_at_item( rst_item pn,
				      GenPtr searchkey, GenPtr inf )
{
  root->prio = MAXINT ; 			// ensure stop at root

  register int prio = rand_prio() ;
  register GenPtr key = searchkey ;
  register rst_item p,
		    pp = pn ;
  count++ ;					// create new node
  p = new rst_node ;
  p->key = key ;  p->prio = prio ;  p->inf = inf ;
  copy_key( p->key ) ; copy_inf( p->inf ) ;

  register rst_item pl, pr ;

  if( key<pp->key ) {	 			// update pred-succ-ptr
    pl = p_item(pp) ;  pr = pp ;
  }
  else {
    pr = s_item(pp) ;  pl = pp ;
  }
  s_item(pl) = p ;  p_item(p) = pl ;  s_item(p) = pr ;  p_item(pr) = p ;
  
  pl = pr = root ;				// children of p

  while( prio > pp->prio ) {			// rotate p up
    if( long(key) < long(pp->key) ) {
      l_child(pp) = pr ;  parent(pr) = pp ;
      pr = pp ;  pp = parent(pp) ;
    }
    else {
      r_child(pp) = pl ;  parent(pl) = pp ;
      pl = pp ;  pp = parent(pp) ;
    }
  } ;

  if( prio==pp->prio && long(key) < long(pp->key) ) {		// one more rot 
    l_child(pp) = pr ;  parent(pr) = pp ;	// not needed for corr.
    pr = pp ;  pp = parent(pp) ;
  }

  l_child(p) = pl ;  parent(pl) = p ;		// insert rs node
  r_child(p) = pr ;  parent(pr) = p ;

  if( long(key) < long(pp->key) )
    l_child(pp) = p ;
  else
    r_child(pp) = p ;
  parent(p) = pp ;

  return p ;
}



// insert new element with generic key as child of leaf pn
//
rst_item rs_tree::gen_insert_at_item( rst_item pn,
				      GenPtr searchkey, GenPtr inf )
{
  root->prio = MAXINT ; 			// ensure stop at root

  register int prio = rand_prio() ;
  register GenPtr key = searchkey ;
  register rst_item p,
		    pp = pn ;
  count++ ;					// create new node
  p = new rst_node ;
  p->key = key ;  p->prio = prio ;  p->inf = inf ;
  copy_key( p->key ) ; copy_inf( p->inf ) ;

  register rst_item pl, pr ;

  if( cmp(key,pp->key) < 0 ) { 			// update pred-succ-ptr
    pl = p_item(pp) ;  pr = pp ;
  }
  else {
    pr = s_item(pp) ;  pl = pp ;
  }
  s_item(pl) = p ;  p_item(p) = pl ;  s_item(p) = pr ;  p_item(pr) = p ;
  
  pl = pr = root ;				// children of p

  while( prio > pp->prio ) {			// rotate p up
    if( cmp(key,pp->key) < 0 ) {
      l_child(pp) = pr ;  parent(pr) = pp ;
      pr = pp ;  pp = parent(pp) ;
    }
    else {
      r_child(pp) = pl ;  parent(pl) = pp ;
      pl = pp ;  pp = parent(pp) ;
    }
  } ;

  if( prio==pp->prio && cmp(key,pp->key)<0 ) {	// one more rot 
    l_child(pp) = pr ;  parent(pr) = pp ;	// not needed for corr.
    pr = pp ;  pp = parent(pp) ;
  }

  l_child(p) = pl ;  parent(pl) = p ;		// insert rs node
  r_child(p) = pr ;  parent(pr) = p ;

  if( cmp(key,pp->key) < 0 )
    l_child(pp) = p ;
  else
    r_child(pp) = p ;
  parent(p) = pp ;

  return p ;
}



// delete item 
//
void rs_tree::del_item( rst_item p )
{
  root->prio = -1 ; 				// ensure stop at root

  register rst_item pp = parent(p),
		    pl = p_item(p),
	   	    pr = s_item(p) ;  
  s_item(pl) = pr ;  p_item(pr) = pl ;		// update pred-succ-ptr

  register rst_dir dir = ( p==r_child(pp) ? rst_right : rst_left ) ;

  pl = l_child(p) ;  pr = r_child(p) ;		// delete item
  clear_key( p->key ) ;  clear_inf( p->inf ) ;
  delete p ;  count-- ;

  while( pl != pr ) {				// rebalance tree
    if( pr->prio > pl->prio ) {			// rotate right child up
      child(pp,dir) = pr ;  parent(pr) = pp ;
      pp = pr ;  dir = rst_left ;  pr = child(pp,dir) ;  
    }
    else {					// rotate left child up
      child(pp,dir) = pl ;  parent(pl) = pp ;
      pp = pl ;  dir = rst_right ;  pl = child(pp,dir) ;  
    }
  } ;
  child(pp,dir) = root ;
}



// reverse a subsequence of items, assuming that all keys are
// in the correct order afterwards
//
void rs_tree::reverse_items( rst_item pl, rst_item pr )
{
  int prio ;
  register rst_item ppl = p_item(pl),  		// pred of pl
		    ppr = s_item(pr),  		// succ of pr
 	   	    ql, qr ;

  while( (pl!=pr) && (pl!=ppl) ) {		// pl and pr didnt't
						// met up to now
    // swap all of pl and pr except the key
						// swap parents
    ql = parent(pl) ;  qr = parent(pr) ;  
    if( pl==r_child(ql) )
      r_child(ql) = pr ;
    else
      l_child(ql) = pr ;
    if( pr==r_child(qr) )
      r_child(qr) = pl ;
    else
      l_child(qr) = pl ;
    parent(pl ) = qr ; parent(pr) = ql ;  
						// swap left children
    ql = l_child(pl) ;  qr = l_child(pr) ;
    if( ql != qr ) {				// at least one exists
      l_child(pl) = qr ; parent(qr) = pl ;
      l_child(pr) = ql ; parent(ql) = pr ;
    }
						// swap right children
    ql = r_child(pl) ;  qr = r_child(pr) ;
    if( ql != qr ) {				// at least one exists
      r_child(pl) = qr ; parent(qr) = pl ;
      r_child(pr) = ql ; parent(ql) = pr ;
    }
						// swap priorities
    prio = pl->prio ;  pl->prio = pr->prio ;  
    pr->prio = prio ;
						// swap pred-succ-ptrs
    s_item(ppl) = pr ;  p_item(ppr) = pl ;
    ql = pl ;  pl = s_item(pl) ;   		// shift pl and pr
    qr = pr ;  pr = p_item(pr) ;
    s_item(ql) = ppr ;  p_item(qr) = ppl ;
    ppl = qr ;  ppr = ql ;			// shift ppl and ppr
  }
  // correct "inner" pred-succ-ptrs

  p_item(ppr) = pl ;  s_item(ppl) = pr ;

  if( pl==pr ) {				// odd-length subseq.
    p_item(pl) = ppl ;  s_item(pr) = ppr ;  
  }
}



// print the whole tree
//
void rs_tree::print_tree() 
{
  string ins = "" ;

  newline ;  newline ;  cout.flush() ;
  if( root != r_child(root) )
    print_tree( r_child(root), ins ) ;
  else 
    cout << "EMPTY\n" ;
  newline ;
}

// print subtree of item p 
//
void rs_tree::print_tree( rst_item p, string ins ) 
{
  if( r_child(p) != root )
    print_tree( r_child(p), ins+"    " ) ;

  cout << ins << "(" ;  print_key( p->key ) ;
  cout << string( ",%d)\n", p->prio ) ;  cout.flush() ;

  if( l_child(p) != root )
    print_tree( l_child(p), ins+"    " ) ;
}



// print all informations of the tree
//
void rs_tree::print_all_items()
{
  rst_item p = root ;

  newline ;  newline ;
  do
    print_item(p) ;
  while( (p=next_item(p)) ) ;
  newline ;
}



// print all informations of an item
//
void rs_tree::print_item( rst_item p )
{
  if( p==root )
    cout << "  ROOT: " << int(p) ;
  else
    cout << "  this: " << int(p) ;
  cout << ",  parent: " << int(parent(p)) ;
  cout << ",  l_child: " << int(l_child(p)) ;
  cout << ",  r_child: " << int(r_child(p)) ;
  newline ;
  cout << "p_item: " << int(p_item(p)) ;
  cout << ",  s_item: " << int(s_item(p))  ;
  if( p!=root ) {
    newline ;
    cout << "key: " ;  print_key(key(p)) ;
    cout << ",  prio: " << p->prio ;
    cout << ",  inf: " ;  print_inf(inf(p)) ;
  }
  newline ;  newline ;
}