Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members  

guma::rkdtree Class Template Reference

#include <guma_rkdtree.h>

Inheritance diagram for guma::rkdtree::

guma::rkdtree_base gul::pool_object List of all members.

Public Methods

 rkdtree (int dim)
 ~rkdtree ()
void insert (const U *rec)
void remove (const U *rec, gul::List< gul::ListNode< kdrec< U, V > > > &outrecs)
GULAPI kdtnode< U, V > * insert (kdtnode< U, V > *T, const kdrec< U, V > &rec)
GULAPI kdtnode< U, V > * remove (kdtnode< U, V > *T, const kdrec< U, V > &rec, gul::List< gul::ListNode< kdrec< U, V > > > &outrecs)
void split (kdtnode< U, V > *T, const V &key, int i, kdtnode< U, V > **retL, kdtnode< U, V > **retR, gul::List< gul::ListNode< kdrec< U, V > > > &C)
void split (kdtnode< U, V > *T, const kdrec< U, V > &X, int i, kdtnode< U, V > **retL, kdtnode< U, V > **retR, gul::List< gul::ListNode< kdrec< U, V > > > &C)
kdtnode< U, V > * join (kdtnode< U, V > *A, kdtnode< U, V > *B, int i)

template<class U, class V, class Rand>
class guma::rkdtree< U, V, Rand >

Constructor & Destructor Documentation

template<class U, class V, class Rand>
guma::rkdtree< U, V, Rand >::rkdtree (  int    dim )  [inline]
 

Definition at line 264 of file guma_rkdtree.h.

References guma::rkdtree_base::rkdtree_base(). 

00264 : rkdtree_base<U,V>(dim) { }

template<class U, class V, class Rand>
guma::rkdtree< U, V, Rand >::~rkdtree (    )  [inline]
 

Definition at line 265 of file guma_rkdtree.h. 

00265 { }

Member Function Documentation

template<class U, class V, class Rand>
GULAPI kdtnode< U, V > * guma::rkdtree< U, V, Rand >::insert (  kdtnode< U, V > *    T,
const kdrec< U, V > &    rec
) 
 

Definition at line 443 of file guma_rkdtree.cpp.

References GULAPI, insert(), guma::rkdtree_base::m_dim, and split(). 

00445 {
00446   int n,sign,k;
00447   double p;
00448   kdtnode<U,V> *L, *R, *root, *S, *Sold;
00449   
00450   if( !T )
00451   {
00452     k = (int)(Rand::Random()*(double)m_dim);
00453     return new kdtnode<U,V>(rec, k);
00454   }
00455   
00456   n = T->m_nelems;
00457   p = Rand::Random();
00458 
00459   if( p*((double)(n+1)) < (double)n ) // becomes not root
00460   {
00461     sign = rtr<V>::cmp( rec[T->m_disc], T->key() );
00462 
00463     if( sign < 0 )
00464     {
00465       if( !T->m_left )
00466       {
00467         k = (int)(Rand::Random()*(double)m_dim);
00468         T->set_left( new kdtnode<U,V>(rec, k) );
00469       }
00470       else
00471       {
00472         Sold = T->m_left;
00473         S = insert( T->m_left, rec );
00474         if( S != Sold ) 
00475           T->set_left(S);
00476       }
00477     }
00478     else if( sign > 0 )
00479     {
00480       if( !T->m_right )
00481       {
00482         k = (int)(Rand::Random()*(double)m_dim);
00483         T->set_right( new kdtnode<U,V>(rec, k) );
00484       }
00485       else
00486       {
00487         Sold = T->m_right;
00488         S = insert( T->m_right, rec );
00489         if( S != Sold ) 
00490           T->set_right(S);
00491       }
00492     }
00493     else   // collision
00494     {
00495       T->add_rec( rec );
00496     }
00497 
00498     root = T;
00499   }
00500   else
00501   {
00502     k = (int)(Rand::Random()*(double)m_dim);
00503     root = new kdtnode<U,V>(rec, k);
00504 
00505     split( T, rec, k, &L, &R, root->m_recs );
00506     root->set_childs(L, R);
00507   }
00508 
00509   return root;
00510 }

template<class U, class V, class Rand>
void guma::rkdtree< U, V, Rand >::insert (  const U *    rec )  [inline]
 

Definition at line 267 of file guma_rkdtree.h.

References guma::rkdtree_base::m_root.

Referenced by insert(). 

00267 { m_root = insert(m_root, kdrec<U,V>(rec)); }

template<class U, class V, class Rand>
kdtnode< U, V > * guma::rkdtree< U, V, Rand >::join (  kdtnode< U, V > *    A,
kdtnode< U, V > *    B,
int    i
) 
 

Definition at line 658 of file guma_rkdtree.cpp.

References split().

Referenced by remove(), and split(). 

00659 {
00660   kdtnode<U,V> *root, *A1, *A2, *B1, *B2;
00661   int n,m,j;
00662   double p;
00663   
00664   if( (!A) && (!B) ) return 0;  
00665 
00666   // note: the trees which shall be joined shouldn't have parents,
00667   // since the parents aren't updated in this function
00668 
00669   if( !A ) { B->m_parent = 0; return B; }
00670   if( !B ) { A->m_parent = 0; return A; }
00671 
00672   A->m_parent = 0;
00673   B->m_parent = 0;
00674   
00675   n = A->m_nelems;
00676   m = B->m_nelems;
00677   p = Rand::Random();
00678 
00679   if( p*((double)(n+m)) < (double)n ) // root of A becomes new root
00680   {
00681     j = A->m_disc;
00682     root = A;
00683 
00684     if( j == i )
00685     {
00686       A2 = join( A->m_right, B, i );
00687       root->set_right( A2 );
00688     } 
00689     else
00690     {
00691       split( B, A->key(), j, &B1, &B2, A->m_recs );
00692       A1 = join( A->m_left, B1, i );
00693       A2 = join( A->m_right, B2, i );
00694       A->set_childs( A1, A2 );
00695     }
00696   }
00697   else    // root of B becomes new root
00698   {
00699     j = B->m_disc;
00700     root = B;
00701 
00702     if( j == i )
00703     {
00704       B1 = join( A, B->m_left, i );
00705       root->set_left( B1 );
00706     } 
00707     else
00708     {
00709       split( A, B->key(), j, &A1, &A2, B->m_recs );
00710       B1 = join( A1, B->m_left, i );
00711       B2 = join( A2, B->m_right, i );
00712       B->set_childs( B1, B2 );
00713     }
00714   }
00715 
00716   return root;
00717 }

template<class U, class V, class Rand>
GULAPI kdtnode< U, V > * guma::rkdtree< U, V, Rand >::remove (  kdtnode< U, V > *    T,
const kdrec< U, V > &    rec,
gul::List< gul::ListNode< kdrec< U, V > > > &    outrecs
) 
 

Definition at line 513 of file guma_rkdtree.cpp.

References gul::ListNode::el, GULAPI, join(), guma::rkdtree_base::m_dim, gul::ListNode::next, and remove(). 

00517 {
00518   int sign,i;
00519   kdtnode<U,V> *L,*Lold,*R,*Rold,*Told;
00520   gul::ListNode< kdrec<U,V> > *r,*r_next;
00521   gul::List< gul::ListNode< kdrec<U,V> > > dummyrecs;
00522 
00523   if( !T ) return 0;
00524 
00525   // search record which shall be removed
00526   sign = rtr<V>::cmp( rec[T->m_disc], T->key() );
00527     
00528   if( sign < 0 )
00529   {
00530     Lold = T->m_left;
00531     L = remove(T->m_left,rec,outrecs);
00532     if( L != Lold ) T->set_left(L);
00533   }
00534   else if( sign > 0 )
00535   {
00536     Rold = T->m_right;
00537     R = remove(T->m_right,rec,outrecs);
00538     if( R != Rold ) T->set_right(R);
00539   }
00540   else // found a node which is identical in its discriminant component
00541   {
00542     // remove records which are completely identical to 'rec'
00543     r = T->m_recs.First();
00544     while( r )
00545     {
00546       for( i = 0; i < m_dim; i++ )
00547       {
00548         sign = rtr<V>::cmp( r->el[i], rec[i] );
00549         if( sign != 0 ) break;
00550       }
00551       r_next = r->next;
00552       if( sign == 0 )  
00553       {
00554         T->m_recs.Remove(r);
00555         outrecs.Append(r);
00556       }
00557       r = r_next;
00558     }
00559 
00560     // remove node if necessary
00561     if( T->m_recs.nElems == 0 )
00562     {
00563       i = T->m_disc;
00564       Told = T;
00565       T->unlink(&L,&R,dummyrecs);
00566       T = join( L, R, i );
00567       delete Told; // deleting T now prevents Tnew==Told
00568     }
00569   }
00570   return T;
00571 }

template<class U, class V, class Rand>
void guma::rkdtree< U, V, Rand >::remove (  const U *    rec,
gul::List< gul::ListNode< kdrec< U, V > > > &    outrecs
)  [inline]
 

Definition at line 268 of file guma_rkdtree.h.

References GULAPI, and guma::rkdtree_base::m_root.

Referenced by remove(). 

00269   { 
00270     m_root = remove(m_root, kdrec<U,V>(rec), outrecs);
00271   }

template<class U, class V, class Rand>
void guma::rkdtree< U, V, Rand >::split (  kdtnode< U, V > *    T,
const kdrec< U, V > &    X,
int    i,
kdtnode< U, V > **    retL,
kdtnode< U, V > **    retR,
gul::List< gul::ListNode< kdrec< U, V > > > &    C
)  [inline]
 

Definition at line 282 of file guma_rkdtree.h.

References split(). 

00285   {
00286     split( T, X[i], i, retL, retR, C );
00287   }

template<class U, class V, class Rand>
void guma::rkdtree< U, V, Rand >::split (  kdtnode< U, V > *    T,
const V &    key,
int    i,
kdtnode< U, V > **    retL,
kdtnode< U, V > **    retR,
gul::List< gul::ListNode< kdrec< U, V > > > &    C
) 
 

Definition at line 574 of file guma_rkdtree.cpp.

References join(), and guma::rkdtree_base::split_recs().

Referenced by insert(), join(), and split(). 

00578 {
00579   kdtnode<U,V> *L, *R, *TL, *TR, *L1, *L2, *R1, *R2, *LR, *RL;
00580   List< ListNode< kdrec<U,V> > > recs,recs1,recs2;
00581   int j, sign;
00582   
00583   // if T is empty return empty trees 
00584   if( !T )
00585   {
00586     *retL = 0;
00587     *retR = 0;
00588     return;
00589   }
00590 
00591   // note: the tree which shall be splitted shouldn't have a parent,
00592   // since the parent isn't updated in this function
00593   T->m_parent = 0;
00594 
00595   j = T->m_disc;
00596   
00597   // T has the same discriminant j
00598   if( j == i )
00599   {
00600     sign = rtr<V>::cmp( T->key(), key );
00601     
00602     // Y[j] < X[i]
00603     if( sign < 0 )
00604     {
00605       L = T;
00606       split( L->m_right, key, i, &LR, &R, C );
00607       L->set_right(LR);
00608     }
00609     // Y[j] > X[i]
00610     else if( sign > 0 )
00611     {
00612       R = T;
00613       split( R->m_left, key, i, &L, &RL, C );
00614       R->set_left(RL);
00615     }
00616     else
00617     {
00618       T->unlink(&L,&R,C);
00619       delete T;     
00620     }
00621   }
00622   // T has a different discriminant j
00623   else
00624   {
00625     T->unlink( &TL, &TR, recs );
00626     split_recs( recs, key, i, recs1, recs2, C );
00627     split( TL, key, i, &L1, &L2, C );
00628     split( TR, key, i, &R1, &R2, C );
00629 
00630     if( recs1.nElems )
00631     {
00632       L = new kdtnode<U,V>( recs1, j );
00633       L->set_childs( L1, R1 );
00634     }
00635     else
00636     {
00637       L = join( L1, R1, j );
00638     }
00639     
00640     if( recs2.nElems )
00641     {
00642       R = new kdtnode<U,V>( recs2, j );
00643       R->set_childs( L2, R2 );
00644     }
00645     else
00646     {
00647       R = join( L2, R2, j );
00648     }
00649 
00650     delete T;
00651   }
00652 
00653   *retL = L;
00654   *retR = R;
00655 }

The documentation for this class was generated from the following files:
Generated on Mon Jan 21 04:18:03 2002 for GUL 0.6 - Geometry Utility Library by doxygen1.2.13.1 written by Dimitri van Heesch, © 1997-2001