G4KDTree Class Reference

#include <G4KDTree.hh>

Data Structures
class	HyperRect

Public Member Functions
void	Build ()
void	Clear ()
	G4KDTree (size_t dim=3)
size_t	GetDim () const
int	GetNbNodes () const
G4KDNode_Base *	GetRoot ()
template<typename PointT >
G4KDNode_Base *	Insert (const PointT &pos)
template<typename PointT >
G4KDNode_Base *	Insert (PointT *pos)
template<typename PointT >
G4KDNode_Base *	InsertMap (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	NoticeNodeDeactivation ()
void	operator delete (void *)
void *	operator new (size_t)
void	Print (std::ostream &out=G4cout) const
	~G4KDTree ()

Protected Member Functions
void	__Clear_Rec (G4KDNode_Base *node)
void	__InsertMap (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	__NearestToNode (G4KDNode_Base *source_node, G4KDNode_Base *node, const Position &pos, std::vector< G4KDNode_Base * > &result, double *result_dist_sq, HyperRect *fRect, int &nbresult)
template<typename Position >
void	__NearestToPosition (G4KDNode_Base *node, const Position &pos, G4KDNode_Base *&result, double *result_dist_sq, HyperRect *fRect)

Static Protected Member Functions
static G4Allocator< G4KDTree > *&	fgAllocator ()

Protected Attributes
size_t	fDim
G4KDMap *	fKDMap
int	fNbActiveNodes
int	fNbNodes
HyperRect *	fRect
G4KDNode_Base *	fRoot

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 70 of file G4KDTree.hh.

Constructor & Destructor Documentation

G4KDTree()

G4KDTree::G4KDTree

(

size_t

dim = 3

)

Definition at line 54 of file G4KDTree.cc.

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

References fDim, fNbActiveNodes, fNbNodes, fRect, and fRoot.

~G4KDTree()

G4KDTree::~G4KDTree

(

)

Definition at line 64 of file G4KDTree.cc.

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

References __Clear_Rec(), fKDMap, fRect, and fRoot.

Member Function Documentation

__Clear_Rec()

void G4KDTree::__Clear_Rec ( G4KDNode_Base *  node )

protected

Definition at line 107 of file G4KDTree.cc.

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

References __Clear_Rec(), G4KDNode_Base::GetLeft(), and G4KDNode_Base::GetRight().

Referenced by __Clear_Rec(), Clear(), and ~G4KDTree().

__InsertMap()

void G4KDTree::__InsertMap ( G4KDNode_Base *  node )

protected

Definition at line 117 of file G4KDTree.cc.

{
  fKDMap->Insert(node);
}

References fKDMap, and G4KDMap::Insert().

__NearestInRange()

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

Referenced by NearestInRange().

__NearestToNode()

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

Referenced by Nearest().

__NearestToPosition()

template<typename Position >

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

protected

Build()

void G4KDTree::Build

(

)

Definition at line 122 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;
      }
    }
  }
}

References G4KDTree::HyperRect::Extend(), fDim, fKDMap, fNbActiveNodes, fRect, fRoot, G4cout, G4endl, G4KDMap::GetSize(), G4KDNode_Base::Insert(), CLHEP::detail::n, G4KDMap::PopOutMiddle(), and G4KDTree::HyperRect::SetMinMax().

Clear()

void G4KDTree::Clear

(

)

Definition at line 94 of file G4KDTree.cc.

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

References __Clear_Rec(), fNbNodes, fRect, and fRoot.

Referenced by NoticeNodeDeactivation().

fgAllocator()

G4Allocator< G4KDTree > *& G4KDTree::fgAllocator ( )

staticprotected

Definition at line 46 of file G4KDTree.cc.

{
    G4ThreadLocalStatic G4Allocator<G4KDTree>* _instance = nullptr;
    return _instance;
}

References G4ThreadLocalStatic.

GetDim()

size_t G4KDTree::GetDim ( ) const

inline

Definition at line 86 of file G4KDTree.hh.

  {
    return fDim;
  }

References fDim.

Referenced by G4KDNode_Base::GetDim(), and G4KDNode_Base::Insert().

GetNbNodes()

int G4KDTree::GetNbNodes ( ) const

inline

Definition at line 90 of file G4KDTree.hh.

  {
    return fNbNodes;
  }

References fNbNodes.

GetRoot()

G4KDNode_Base * G4KDTree::GetRoot ( )

inline

Definition at line 94 of file G4KDTree.hh.

  {
    return fRoot;
  }

References fRoot.

Insert() [1/2]

template<typename PointT >

G4KDNode_Base * G4KDTree::Insert

(

const PointT &

pos

)

Insert() [2/2]

template<typename PointT >

G4KDNode_Base * G4KDTree::Insert

(

PointT *

pos

)

InsertMap()

template<typename PointT >

G4KDNode_Base * G4KDTree::InsertMap

(

PointT *

pos

)

Nearest() [1/2]

template<typename Position >

G4KDTreeResultHandle G4KDTree::Nearest

(

const Position &

pos

)

Nearest() [2/2]

G4KDTreeResultHandle G4KDTree::Nearest

(

G4KDNode_Base *

node

)

Definition at line 159 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;
  }
}

References __NearestToNode(), DBL_MAX, fRect, fRoot, G4cout, and G4endl.

NearestInRange() [1/2]

template<typename Position >

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

NearestInRange() [2/2]

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

Definition at line 202 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;
}

References __NearestInRange(), fRoot, G4KDTreeResult::Rewind(), G4KDTreeResult::Sort(), and sqr().

NoticeNodeDeactivation()

void G4KDTree::NoticeNodeDeactivation ( )

inline

Definition at line 80 of file G4KDTree.hh.

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

References Clear(), and fNbActiveNodes.

Referenced by G4KDNode_Base::InactiveNode().

operator delete()

void G4KDTree::operator delete

(

void *

aNode

)

Definition at line 84 of file G4KDTree.cc.

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

operator new()

void * G4KDTree::operator new

(

size_t

)

Definition at line 78 of file G4KDTree.cc.

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

References G4Allocator< Type >::MallocSingle().

Print()

void G4KDTree::Print

(

std::ostream &

out = G4cout

)

const

Definition at line 89 of file G4KDTree.cc.

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

References fRoot, and G4KDNode_Base::Print().

Friends And Related Function Documentation

G4KDNode_Base

friend class G4KDNode_Base

friend

Definition at line 72 of file G4KDTree.hh.

Field Documentation

fDim

size_t G4KDTree::fDim

protected

Definition at line 268 of file G4KDTree.hh.

Referenced by Build(), G4KDNode_Base::G4KDNode_Base(), G4KDTree(), and GetDim().

fKDMap

G4KDMap* G4KDTree::fKDMap

protected

Definition at line 271 of file G4KDTree.hh.

Referenced by __InsertMap(), Build(), and ~G4KDTree().

fNbActiveNodes

int G4KDTree::fNbActiveNodes

protected

Definition at line 270 of file G4KDTree.hh.

Referenced by Build(), G4KDTree(), and NoticeNodeDeactivation().

fNbNodes

int G4KDTree::fNbNodes

protected

Definition at line 269 of file G4KDTree.hh.

Referenced by Clear(), G4KDTree(), and GetNbNodes().

fRect

HyperRect* G4KDTree::fRect

protected

Definition at line 266 of file G4KDTree.hh.

Referenced by Build(), Clear(), G4KDTree(), Nearest(), and ~G4KDTree().

fRoot

G4KDNode_Base* G4KDTree::fRoot

protected

Definition at line 267 of file G4KDTree.hh.

Referenced by Build(), Clear(), G4KDTree(), GetRoot(), Nearest(), NearestInRange(), Print(), and ~G4KDTree().

---

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

• source/processes/electromagnetic/dna/management/include/G4KDTree.hh
• source/processes/electromagnetic/dna/management/src/G4KDTree.cc