ECCE @ EIC Software
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
G4KDTree.cc
Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file G4KDTree.cc
1 //
2 // ********************************************************************
3 // * License and Disclaimer *
4 // * *
5 // * The Geant4 software is copyright of the Copyright Holders of *
6 // * the Geant4 Collaboration. It is provided under the terms and *
7 // * conditions of the Geant4 Software License, included in the file *
8 // * LICENSE and available at http://cern.ch/geant4/license . These *
9 // * include a list of copyright holders. *
10 // * *
11 // * Neither the authors of this software system, nor their employing *
12 // * institutes,nor the agencies providing financial support for this *
13 // * work make any representation or warranty, express or implied, *
14 // * regarding this software system or assume any liability for its *
15 // * use. Please see the license in the file LICENSE and URL above *
16 // * for the full disclaimer and the limitation of liability. *
17 // * *
18 // * This code implementation is the result of the scientific and *
19 // * technical work of the GEANT4 collaboration. *
20 // * By using, copying, modifying or distributing the software (or *
21 // * any work based on the software) you agree to acknowledge its *
22 // * use in resulting scientific publications, and indicate your *
23 // * acceptance of all terms of the Geant4 Software license. *
24 // ********************************************************************
25 //
26 /*
27  * G4KDTree.cc
28  *
29  * Created on: 22 oct. 2013
30  * Author: kara
31  */
32 
33 #include "globals.hh"
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <cmath>
37 #include "G4KDTree.hh"
38 #include "G4KDMap.hh"
39 #include "G4KDNode.hh"
40 #include "G4KDTreeResult.hh"
41 #include <list>
42 #include <iostream>
43 
44 using namespace std;
45 
47 {
48  G4ThreadLocalStatic G4Allocator<G4KDTree>* _instance = nullptr;
49  return _instance;
50 }
51 
52 //______________________________________________________________________
53 // KDTree methods
55  fKDMap(new G4KDMap(k))
56 {
57  fDim = k;
58  fRoot = 0;
59  fRect = 0;
60  fNbNodes = 0;
61  fNbActiveNodes = 0;
62 }
63 
65 {
66  if (fRoot) __Clear_Rec(fRoot);
67  fRoot = 0;
68 
69  if (fRect)
70  {
71  delete fRect;
72  fRect = 0;
73  }
74 
75  if (fKDMap) delete fKDMap;
76 }
77 
78 void* G4KDTree::operator new(size_t)
79 {
80  if (!fgAllocator()) fgAllocator() = new G4Allocator<G4KDTree>;
81  return (void *) fgAllocator()->MallocSingle();
82 }
83 
84 void G4KDTree::operator delete(void *aNode)
85 {
86  fgAllocator()->FreeSingle((G4KDTree*) aNode);
87 }
88 
89 void G4KDTree::Print(std::ostream& out) const
90 {
91  if (fRoot) fRoot->Print(out);
92 }
93 
95 {
97  fRoot = 0;
98  fNbNodes = 0;
99 
100  if (fRect)
101  {
102  delete fRect;
103  fRect = 0;
104  }
105 }
106 
108 {
109  if (!node) return;
110 
111  if (node->GetLeft()) __Clear_Rec(node->GetLeft());
112  if (node->GetRight()) __Clear_Rec(node->GetRight());
113 
114  delete node;
115 }
116 
118 {
119  fKDMap->Insert(node);
120 }
121 
123 {
124  size_t Nnodes = fKDMap->GetSize();
125 
126  G4cout << "********************" << G4endl;
127  G4cout << "template<typename PointT> G4KDTree<PointT>::Build" << G4endl;
128  G4cout << "Map size = " << Nnodes << G4endl;
129 
130  G4KDNode_Base* root = fKDMap->PopOutMiddle(0);
131 
132  if(root == 0) return;
133 
134  fRoot = root;
135  fNbActiveNodes++;
136  fRect = new HyperRect(fDim);
137  fRect->SetMinMax(*fRoot, *fRoot);
138 
139  Nnodes--;
140 
141  G4KDNode_Base* parent = fRoot;
142 
143  for (size_t n = 0; n < Nnodes; n += fDim)
144  {
145  for (size_t dim = 0; dim < fDim; dim++)
146  {
148  if (node)
149  {
150  parent->Insert(node);
151  fNbActiveNodes++;
152  fRect->Extend(*node);
153  parent = node;
154  }
155  }
156  }
157 }
158 
160 {
161  // G4cout << "Nearest(node)" << G4endl ;
162  if (!fRect)
163  {
164  G4cout << "Tree empty" << G4endl;
165  return 0;
166  }
167 
168  std::vector<G4KDNode_Base* > result;
169  double dist_sq = DBL_MAX;
170 
171  /* Duplicate the bounding hyperrectangle, we will work on the copy */
172  HyperRect *newrect = new HyperRect(*fRect);
173 
174  /* Search for the nearest neighbour recursively */
175  int nbresult = 0;
176 
177  __NearestToNode(node, fRoot, *node, result, &dist_sq, newrect, nbresult);
178 
179  /* Free the copy of the hyperrect */
180  delete newrect;
181 
182  /* Store the result */
183  if (!result.empty())
184  {
185  G4KDTreeResultHandle rset(new G4KDTreeResult(this));
186  int j = 0;
187  while (j<nbresult)
188  {
189  rset->Insert(dist_sq, result[j]);
190  j++;
191  }
192  rset->Rewind();
193 
194  return rset;
195  }
196  else
197  {
198  return 0;
199  }
200 }
201 
203  const double& range)
204 {
205  if (!node) return 0;
206  int ret(-1);
207 
208  G4KDTreeResult *rset = new G4KDTreeResult(this);
209 
210  const double range_sq = sqr(range);
211 
212  if ((ret = __NearestInRange(fRoot, *node, range_sq, range, *rset, 0, node)) == -1)
213  {
214  delete rset;
215  return 0;
216  }
217  rset->Sort();
218  rset->Rewind();
219  return rset;
220 }