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

guma::rkdtree_base Class Template Reference

#include <guma_rkdtree.h>

Inheritance diagram for guma::rkdtree_base::

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

Public Methods

 rkdtree_base (int dim)
 ~rkdtree_base ()
GULAPI int nearest_neighbors (const U &P, int m, gul::Ptr< kdnnrec< U, V > > &M)
void split_recs (gul::List< gul::ListNode< kdrec< U, V > > > &recs, const V &key, int i, gul::List< gul::ListNode< kdrec< U, V > > > &recs1, gul::List< gul::ListNode< kdrec< U, V > > > &recs2, gul::List< gul::ListNode< kdrec< U, V > > > &C)
void split_recs (gul::List< gul::ListNode< kdrec< U, V > > > &recs, const U &X, int i, gul::List< gul::ListNode< kdrec< U, V > > > &recs1, gul::List< gul::ListNode< kdrec< U, V > > > &recs2, gul::List< gul::ListNode< kdrec< U, V > > > &C)
GULAPI void dump_statistics ()
GULAPI void dump_tree ()

Public Attributes

int m_dim
kdtnode< U, V > * m_root

template<class U, class V>
class guma::rkdtree_base< U, V >

Constructor & Destructor Documentation

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

Definition at line 232 of file guma_rkdtree.h.

References m_dim.

Referenced by guma::rkdtree::rkdtree(). 

00232 { m_dim = dim; m_root = 0; }

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

Definition at line 233 of file guma_rkdtree.h.

References GULAPI. 

00233 { delete m_root; }

Member Function Documentation

template<class U, class V>
GULAPI void guma::rkdtree_base< U, V >::dump_statistics (    ) 
 

Definition at line 408 of file guma_rkdtree.cpp.

References GULAPI, and m_root. 

00409 {
00410   int max_height = 0;
00411   double avg_pathlen = 0;
00412   int avg_count = 0;
00413 
00414   if( m_root )
00415   {
00416     cout << "nelems (without collision records) = " << m_root->m_nelems << "\n";
00417     m_root->height( 1, &max_height, &avg_count, &avg_pathlen );
00418     cout << "max height = " << max_height << "\n";
00419     cout << "average pathlen = " << avg_pathlen/((double)avg_count) << "\n";
00420   }
00421   else
00422   {
00423     cout << "empty tree\n";
00424   }
00425 }

template<class U, class V>
GULAPI void guma::rkdtree_base< U, V >::dump_tree (    ) 
 

Definition at line 428 of file guma_rkdtree.cpp.

References GULAPI, m_dim, and m_root. 

00429 {
00430   if( m_root )
00431   {
00432     m_root->dump(m_dim,0);
00433   }
00434   else
00435   {
00436     cout << "empty tree\n";
00437   }
00438 }

template<class U, class V>
GULAPI int guma::rkdtree_base< U, V >::nearest_neighbors (  const U &    P,
int    m,
gul::Ptr< kdnnrec< U, V > > &    M
) 
 

Definition at line 357 of file guma_rkdtree.cpp.

References GULAPI, m_dim, m_root, and gul::Swap(). 

00359 {
00360   Ptr<V> D;
00361   V d;
00362   ListNode< kdtsnode<U,V> > *sn;
00363   List< ListNode< kdtsnode<U,V> > > S1,S2;
00364   List< ListNode< kdtsnode<U,V> > >* stack1 = &S1, *stack2 = &S2;
00365   const kdtnode<U,V> *curnod;
00366   int i, nEl;
00367   Ptr<kdnnrec<U,V> *> pm;
00368   
00369   if( (m <= 0) || (!m_root) ) return 0;
00370   
00371   kdtsearch<U,V> nns(m_dim,m);
00372 
00373   D.reserve_pool(m_dim);
00374   for( i = 0; i < m_dim; i++ )
00375     D[i] = (V)0;
00376   d = 0;
00377   
00378   sn = new ListNode< kdtsnode<U,V> >( kdtsnode<U,V>(m_root,D,d) );
00379   stack1->Append(sn);
00380   
00381   while( !stack1->IsEmpty() )
00382   {
00383     sn = stack1->First();
00384     while( sn )
00385     {
00386       curnod = sn->el.m_n;
00387       D = sn->el.m_D;
00388       d = sn->el.m_d;
00389       stack1->Remove( sn );
00390       delete sn;
00391 
00392       nns.process_node( P, curnod, D, d, *stack2 );
00393 
00394       sn = stack1->First();
00395     }
00396 
00397     Swap( stack1, stack2 );
00398   }
00399 
00400   nEl = nns.m_neighbors.ConvertToArray(&pm);
00401   for( i = 0; i < nEl; i++ )
00402     M[i] = *(pm[i]);
00403 
00404   return nEl;
00405 }

template<class U, class V>
void guma::rkdtree_base< U, V >::split_recs (  gul::List< gul::ListNode< kdrec< U, V > > > &    recs,
const U &    X,
int    i,
gul::List< gul::ListNode< kdrec< U, V > > > &    recs1,
gul::List< gul::ListNode< kdrec< U, V > > > &    recs2,
gul::List< gul::ListNode< kdrec< U, V > > > &    C
)  [inline]
 

Definition at line 243 of file guma_rkdtree.h.

References GULAPI, and split_recs(). 

00248   {
00249     split_recs( recs, X[i], i, recs1, recs2, C );
00250   }

template<class U, class V>
void guma::rkdtree_base< U, V >::split_recs (  gul::List< gul::ListNode< kdrec< U, V > > > &    recs,
const V &    key,
int    i,
gul::List< gul::ListNode< kdrec< U, V > > > &    recs1,
gul::List< gul::ListNode< kdrec< U, V > > > &    recs2,
gul::List< gul::ListNode< kdrec< U, V > > > &    C
) 
 

Definition at line 123 of file guma_rkdtree.cpp.

Referenced by guma::rkdtree::split(), and split_recs(). 

00127 {
00128   ListNode< kdrec<U,V> > *r;
00129   int sign;
00130   
00131   r = recs.First();
00132   while( r )
00133   {
00134     recs.Remove(r);
00135 
00136     sign = rtr<V>::cmp( r->el[i], key );
00137     if( sign < 0 )
00138     {
00139       recs1.Append(r);
00140     }
00141     else if( sign > 0 )
00142     {
00143       recs2.Append(r);
00144     }
00145     else
00146       C.Append(r);
00147 
00148     r = recs.First();
00149   }
00150 }

Member Data Documentation

template<class U, class V>
int guma::rkdtree_base::m_dim
 

Definition at line 229 of file guma_rkdtree.h.

Referenced by dump_tree(), guma::rkdtree::insert(), nearest_neighbors(), guma::rkdtree::remove(), and rkdtree_base().

template<class U, class V>
kdtnode<U,V>* guma::rkdtree_base::m_root
 

Definition at line 230 of file guma_rkdtree.h.

Referenced by dump_statistics(), dump_tree(), guma::rkdtree::insert(), nearest_neighbors(), and guma::rkdtree::remove().

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