| Geant4 Cross Reference |
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 // Author: Mathieu Karamitros
28
29 // The code is developed in the framework of the ESA AO7146
30 //
31 // We would be very happy hearing from you, send us your feedback! :)
32 //
33 // In order for Geant4-DNA to be maintained and still open-source,
34 // article citations are crucial.
35 // If you use Geant4-DNA chemistry and you publish papers about your software,
36 // in addition to the general paper on Geant4-DNA:
37 //
38 // Int. J. Model. Simul. Sci. Comput. 1 (2010) 157–178
39 //
40 // we would be very happy if you could please also cite the following
41 // reference papers on chemistry:
42 //
43 // J. Comput. Phys. 274 (2014) 841-882
44 // Prog. Nucl. Sci. Tec. 2 (2011) 503-508
45
46 #ifndef G4KDNODE_HH
47 #define G4KDNODE_HH
48
49 #include <list>
50 #include <vector>
51 #include <deque>
52 #include <ostream>
53
54 // geant4
55 #include "G4Types.hh"
56 #include "G4Allocator.hh"
57
58 class G4KDTree;
59 class G4KDMap;
60
61 class G4KDNode_Base
62 {
63 public:
64 //----------------------------
65 // For root node :
66 // parent = 0, axis = 0, side = 0
67 G4KDNode_Base(G4KDTree*, G4KDNode_Base* /*parent*/);
68 virtual ~G4KDNode_Base();
69 virtual double operator[](std::size_t) const = 0;
70 virtual void InactiveNode();
71 virtual bool IsValid() const{ return true; }
72
73 //----------------------------
74 inline G4KDTree* GetTree() const {return fTree;}
75 inline void SetTree(G4KDTree* tree) {fTree = tree;}
76
77 //----------------------------
78 G4int GetDim() const;
79 inline G4int GetAxis() const{return (G4int)fAxis;}
80 inline G4KDNode_Base* GetParent(){return fParent;}
81 inline G4KDNode_Base* GetLeft(){return fLeft;}
82 inline G4KDNode_Base* GetRight(){return fRight;}
83
84 //----------------------------
85 template<typename Position>
86 G4KDNode_Base* FindParent(const Position& x0);
87
88 template<typename PointT>
89 G4KDNode_Base* Insert(PointT* point);
90 template<typename PointT>
91 G4KDNode_Base* Insert(const PointT& point);
92 G4int Insert(G4KDNode_Base* newNode);
93
94 void PullSubTree();
95 void RetrieveNodeList(std::list<G4KDNode_Base*>& node_list);
96
97 void Print(std::ostream& out, G4int level = 0) const;
98
99 // std::vector<std::deque<G4KDNode_Base*>::iterator>*
100 // GetIteratorsForSortingAlgo(G4KDMap*);
101 // std::map<G4KDMap*, std::vector<std::deque<G4KDNode_Base*>::iterator>>*
102 // fpIteratorInSortingAlgo;
103
104 protected:
105 //°°°°°°°°°°°
106 // Members
107 //°°°°°°°°°°°
108 std::size_t fAxis; // axis : x, y, z ...
109 G4int fSide; // left/right
110 /* fSide == 0 : Is the root node
111 * fSide == -1 : It is the left of the parent node
112 * fSide == 1 : It is the right of the parent node
113 */
114
115 G4KDTree* fTree{nullptr};
116 G4KDNode_Base *fLeft{nullptr}, *fRight{nullptr}, *fParent{nullptr};
117 /* Left : fLeft->fPosition[axis] < this->fPosition[axis]
118 * Right : fRight->fPosition[axis] > this->fPosition[axis]
119 * Root node : fParent = 0
120 */
121 private:
122 G4KDNode_Base(const G4KDNode_Base& right);
123 G4KDNode_Base& operator=(const G4KDNode_Base& right);
124 };
125
126 /**
127 * G4KDNode stores one entity in G4KDTree
128 * This class is for internal use only
129 */
130
131 template<typename PointT>
132 class G4KDNode : public G4KDNode_Base
133 {
134 public:
135 //----------------------------
136 // For root node :
137 // parent = 0, axis = 0, side = 0
138 G4KDNode(G4KDTree*, PointT* /*point*/, G4KDNode_Base* /*parent*/);
139 ~G4KDNode() override;
140
141 void *operator new(std::size_t);
142 void operator delete(void *);
143
144 inline PointT* GetPoint()
145 {
146 return fPoint;
147 }
148
149 G4double operator[](std::size_t i) const override
150 {
151 if(fPoint == nullptr) abort();
152 return (*fPoint)[(G4int)i];
153 }
154
155 void InactiveNode() override
156 {
157 fValid = false;
158 G4KDNode_Base::InactiveNode();
159 }
160
161 G4bool IsValid() const override
162 {
163 return fValid;
164 }
165
166 protected:
167 PointT* fPoint;
168 G4bool fValid;
169
170 private:
171 G4KDNode(const G4KDNode<PointT>& right);
172 G4KDNode& operator=(const G4KDNode<PointT>& right);
173
174 static G4ThreadLocal G4Allocator<G4KDNode<PointT>>* fgAllocator;
175 };
176
177 template<typename PointT>
178 G4ThreadLocal G4Allocator<G4KDNode<PointT>>*
179 G4KDNode<PointT>::fgAllocator = nullptr;
180
181 template<typename PointT>
182 void* G4KDNode<PointT>::operator new(std::size_t)
183 {
184 if(!fgAllocator) fgAllocator = new G4Allocator<G4KDNode<PointT> >;
185 return (void *) fgAllocator->MallocSingle();
186 }
187
188 template<typename PointT>
189 void G4KDNode<PointT>::operator delete(void *aNode)
190 {
191 fgAllocator->FreeSingle((G4KDNode<PointT> *) aNode);
192 }
193
194 /**
195 * G4KDNode stores one entity in G4KDTree
196 * This class is for internal use only
197 */
198
199 template<typename PointCopyT>
200 class G4KDNodeCopy: public G4KDNode_Base
201 {
202 public:
203 //----------------------------
204 // For root node :
205 // parent = 0, axis = 0, side = 0
206 G4KDNodeCopy(G4KDTree* tree,
207 const PointCopyT& point,
208 G4KDNode_Base* parent) :
209 G4KDNode_Base(tree, parent)
210 {
211 fPoint = point;
212 fValid = true;
213 }
214
215 ~G4KDNodeCopy() override= default;
216
217 void *operator new(std::size_t)
218 {
219 if(!fgAllocator) fgAllocator = new G4Allocator<G4KDNodeCopy<PointCopyT>>;
220 return (void *) fgAllocator->MallocSingle();
221 }
222
223 void operator delete(void* aNode)
224 {
225 fgAllocator->FreeSingle((G4KDNodeCopy<PointCopyT>*) aNode);
226 }
227
228 inline const PointCopyT& GetPoint()
229 {
230 return fPoint;
231 }
232
233 double operator[](std::size_t i) const override
234 {
235 return fPoint[i];
236 }
237
238 void InactiveNode() override
239 {
240 fValid = false;
241 G4KDNode_Base::InactiveNode();
242 }
243
244 bool IsValid() const override
245 {
246 return fValid;
247 }
248
249 protected:
250 PointCopyT fPoint;
251 G4bool fValid;
252
253 private:
254 G4KDNodeCopy(const G4KDNodeCopy<PointCopyT>& right) :
255 G4KDNode_Base(right), fPoint(0)
256 {
257 fValid = false;
258 }
259
260 G4KDNodeCopy<PointCopyT>&
261 operator=(const G4KDNodeCopy<PointCopyT>& right)
262 {
263 if(this == &right) return *this;
264 fPoint = right.fPoint;
265 fTree = right.fTree;
266 fLeft = right.fLeft;
267 fRight = right.fRight;
268 fParent = right.fParent;
269 fSide = right.fSide;
270 fAxis = right.fAxis;
271 return *this;
272 }
273
274 static G4ThreadLocal G4Allocator<G4KDNodeCopy<PointCopyT>>* fgAllocator;
275 };
276
277 template<typename PointT>
278 G4ThreadLocal G4Allocator<G4KDNodeCopy<PointT>>*
279 G4KDNodeCopy<PointT>::fgAllocator = nullptr;
280
281 #include "G4KDNode.icc"
282
283 #endif // G4KDNODE_HH
284