#include <G4KDTree.hh>

Collaboration diagram for G4KDTree:

Classes
class	HyperRect

Public Member Functions
	G4KDTree (size_t dim=3)

	~G4KDTree ()

void	Clear ()

void	Print (std::ostream &out=G4cout) const

void	Build ()

void	NoticeNodeDeactivation ()

size_t	GetDim () const

int	GetNbNodes () const

G4KDNode_Base *	GetRoot ()

template<typename PointT >
G4KDNode_Base *	InsertMap (PointT *pos)

template<typename PointT >
G4KDNode_Base *	Insert (PointT *pos)

template<typename PointT >
G4KDNode_Base *	Insert (const PointT &pos)

template<typename Position >
G4KDTreeResultHandle	Nearest (const Position &pos)

G4KDTreeResultHandle	Nearest (G4KDNode_Base *node)

template<typename Position >
G4KDTreeResultHandle	NearestInRange (const Position &pos, const double &range)

G4KDTreeResultHandle	NearestInRange (G4KDNode_Base *node, const double &range)

void *	operator new (size_t)

void	operator delete (void *)

Protected Member Functions
void	__InsertMap (G4KDNode_Base *node)

void	__Clear_Rec (G4KDNode_Base *node)

template<typename Position >
int	__NearestInRange (G4KDNode_Base node, const Position &pos, const double &range_sq, const double &range, G4KDTreeResult &list, int ordered, G4KDNode_Base source_node=0)

template<typename Position >
void	__NearestToPosition (G4KDNode_Base node, const Position &pos, G4KDNode_Base &result, double result_dist_sq, HyperRect fRect)

template<typename Position >
void	__NearestToNode (G4KDNode_Base source_node, G4KDNode_Base node, const Position &pos, std::vector< G4KDNode_Base * > &result, double result_dist_sq, HyperRect fRect, int &nbresult)

Protected Attributes
HyperRect *	fRect

G4KDNode_Base *	fRoot

size_t	fDim

int	fNbNodes

int	fNbActiveNodes

G4KDMap *	fKDMap

G4ThreadLocalStatic G4Allocator< G4KDTree > *	fgAllocator

Friends
class	G4KDNode_Base

Detailed Description

G4KDTree is used by the ITManager to locate the neareast neighbours. A kdtree sorts out node in such a way that it reduces the number of node check. The results of this search can be retrieved by G4KDTreeResultHandle.

Definition at line 72 of file G4KDTree.hh.

Constructor & Destructor Documentation

G4KDTree::G4KDTree ( size_t dim = 3 )

Definition at line 50 of file G4KDTree.cc.

                            :
     fKDMap(new G4KDMap(k))
 {
   fDim = k;
   fRoot = 0;
   fRect = 0;
   fNbNodes = 0;
   fNbActiveNodes = 0;
 }

G4KDTree::~G4KDTree ( )

Definition at line 60 of file G4KDTree.cc.

 {
   if (fRoot) __Clear_Rec(fRoot);
   fRoot = 0;
 
   if (fRect)
   {
     delete fRect;
     fRect = 0;
   }
 
   if (fKDMap) delete fKDMap;
 }

Here is the call graph for this function:

Member Function Documentation

void G4KDTree::__Clear_Rec ( G4KDNode_Base * node )

protected

Definition at line 103 of file G4KDTree.cc.

 {
   if (!node) return;
 
   if (node->GetLeft()) __Clear_Rec(node->GetLeft());
   if (node->GetRight()) __Clear_Rec(node->GetRight());
 
   delete node;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void G4KDTree::__InsertMap ( G4KDNode_Base * node )

protected

Definition at line 113 of file G4KDTree.cc.

 {
   fKDMap->Insert(node);
 }

Here is the call graph for this function:

template<typename Position >

int G4KDTree::__NearestInRange	(	G4KDNode_Base *	node,
		const Position &	pos,
		const double &	range_sq,
		const double &	range,
		G4KDTreeResult &	list,
		int	ordered,
		G4KDNode_Base *	source_node = `0`
	)

protected

Here is the caller graph for this function:

template<typename Position >

void G4KDTree::__NearestToNode	(	G4KDNode_Base *	source_node,
		G4KDNode_Base *	node,
		const Position &	pos,
		std::vector< G4KDNode_Base * > &	result,
		double *	result_dist_sq,
		HyperRect *	fRect,
		int &	nbresult
	)

protected

Here is the caller graph for this function:

template<typename Position >

void G4KDTree::__NearestToPosition	(	G4KDNode_Base *	node,
		const Position &	pos,
		G4KDNode_Base *&	result,
		double *	result_dist_sq,
		HyperRect *	fRect
	)

protected

void G4KDTree::Build ( void )

Definition at line 118 of file G4KDTree.cc.

 {
   size_t Nnodes = fKDMap->GetSize();
 
   G4cout << "********************" << G4endl;
   G4cout << "template<typename PointT> G4KDTree<PointT>::Build" << G4endl;
   G4cout << "Map size = " << Nnodes << G4endl;
 
   G4KDNode_Base* root = fKDMap->PopOutMiddle(0);
 
   if(root == 0) return;
 
   fRoot = root;
   fNbActiveNodes++;
   fRect = new HyperRect(fDim);
   fRect->SetMinMax(*fRoot, *fRoot);
 
   Nnodes--;
 
   G4KDNode_Base* parent = fRoot;
 
   for (size_t n = 0; n < Nnodes; n += fDim)
   {
     for (size_t dim = 0; dim < fDim; dim++)
     {
       G4KDNode_Base* node = fKDMap->PopOutMiddle(dim);
       if (node)
       {
         parent->Insert(node);
         fNbActiveNodes++;
         fRect->Extend(*node);
         parent = node;
       }
     }
   }
 }

Here is the call graph for this function:

void G4KDTree::Clear ( )

Definition at line 90 of file G4KDTree.cc.

 {
   __Clear_Rec(fRoot);
   fRoot = 0;
   fNbNodes = 0;
 
   if (fRect)
   {
     delete fRect;
     fRect = 0;
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

size_t G4KDTree::GetDim ( ) const

inline

Definition at line 88 of file G4KDTree.hh.

   {
     return fDim;
   }

Here is the caller graph for this function:

int G4KDTree::GetNbNodes ( ) const

inline

Definition at line 92 of file G4KDTree.hh.

   {
     return fNbNodes;
   }

G4KDNode_Base* G4KDTree::GetRoot ( )

inline

Definition at line 96 of file G4KDTree.hh.

   {
     return fRoot;
   }

template<typename PointT >

G4KDNode_Base* G4KDTree::Insert ( PointT * pos )

template<typename PointT >

G4KDNode_Base* G4KDTree::Insert ( const PointT & pos )

template<typename PointT >

G4KDNode_Base* G4KDTree::InsertMap ( PointT * pos )

template<typename Position >

G4KDTreeResultHandle G4KDTree::Nearest ( const Position & pos )

G4KDTreeResultHandle G4KDTree::Nearest ( G4KDNode_Base * node )

Definition at line 155 of file G4KDTree.cc.

 {
   //    G4cout << "Nearest(node)" << G4endl ;
   if (!fRect)
   {
     G4cout << "Tree empty" << G4endl;
     return 0;
   }
 
   std::vector<G4KDNode_Base* > result;
   double dist_sq = DBL_MAX;
 
   /* Duplicate the bounding hyperrectangle, we will work on the copy */
   HyperRect *newrect = new HyperRect(*fRect);
 
   /* Search for the nearest neighbour recursively */
   int nbresult = 0;
 
   __NearestToNode(node, fRoot, *node, result, &dist_sq, newrect, nbresult);
 
   /* Free the copy of the hyperrect */
   delete newrect;
 
   /* Store the result */
   if (!result.empty())
   {
     G4KDTreeResultHandle rset(new G4KDTreeResult(this));
     int j = 0;
     while (j<nbresult)
     {
       rset->Insert(dist_sq, result[j]);
       j++;
     }
     rset->Rewind();
 
     return rset;
   }
   else
   {
     return 0;
   }
 }

Here is the call graph for this function:

template<typename Position >

G4KDTreeResultHandle G4KDTree::NearestInRange	(	const Position &	pos,
		const double &	range
	)

G4KDTreeResultHandle G4KDTree::NearestInRange	(	G4KDNode_Base *	node,
		const double &	range
	)

Definition at line 198 of file G4KDTree.cc.

 {
   if (!node) return 0;
   int ret(-1);
 
   G4KDTreeResult *rset = new G4KDTreeResult(this);
 
   const double range_sq = sqr(range);
 
   if ((ret = __NearestInRange(fRoot, *node, range_sq, range, *rset, 0, node)) == -1)
   {
     delete rset;
     return 0;
   }
   rset->Sort();
   rset->Rewind();
   return rset;
 }

Here is the call graph for this function:

void G4KDTree::NoticeNodeDeactivation ( )

inline

Definition at line 82 of file G4KDTree.hh.

   {
     fNbActiveNodes--;
     if (fNbActiveNodes <= 0) Clear();
   }

Here is the call graph for this function:

Here is the caller graph for this function:

void G4KDTree::operator delete ( void * aNode )

Definition at line 80 of file G4KDTree.cc.

 {
   fgAllocator->FreeSingle((G4KDTree*) aNode);
 }

void * G4KDTree::operator new ( size_t )

Definition at line 74 of file G4KDTree.cc.

 {
   if (!fgAllocator) fgAllocator = new G4Allocator<G4KDTree>;
   return (void *) fgAllocator->MallocSingle();
 }

Here is the call graph for this function:

void G4KDTree::Print ( std::ostream & out = G4cout ) const

Definition at line 85 of file G4KDTree.cc.

 {
   if (fRoot) fRoot->Print(out);
 }

Here is the call graph for this function:

Friends And Related Function Documentation

friend class G4KDNode_Base

friend

Definition at line 74 of file G4KDTree.hh.

Member Data Documentation

size_t G4KDTree::fDim

protected

Definition at line 270 of file G4KDTree.hh.

G4ThreadLocal G4Allocator< G4KDTree > * G4KDTree::fgAllocator

protected

Definition at line 275 of file G4KDTree.hh.

G4KDMap* G4KDTree::fKDMap

protected

Definition at line 273 of file G4KDTree.hh.

int G4KDTree::fNbActiveNodes

protected

Definition at line 272 of file G4KDTree.hh.

int G4KDTree::fNbNodes

protected

Definition at line 271 of file G4KDTree.hh.

HyperRect* G4KDTree::fRect

protected

Definition at line 268 of file G4KDTree.hh.

G4KDNode_Base* G4KDTree::fRoot

protected

Definition at line 269 of file G4KDTree.hh.

The documentation for this class was generated from the following files:

source/geant4.10.03.p03/source/processes/electromagnetic/dna/management/include/G4KDTree.hh
source/geant4.10.03.p03/source/processes/electromagnetic/dna/management/src/G4KDTree.cc

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation