Geant4  10.00.p02
G4KDNode.cc
Go to the documentation of this file.
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 // $Id: G4KDNode.cc 64057 2012-10-30 15:04:49Z gcosmo $
27 //
28 // Author: Mathieu Karamitros (kara (AT) cenbg . in2p3 . fr)
29 //
30 // History:
31 // -----------
32 // 10 Oct 2011 M.Karamitros created
33 //
34 // -------------------------------------------------------------------
35 
36 #include "globals.hh"
37 #include "G4KDNode.hh"
38 #include "G4KDTree.hh"
39 
40 //*********************************************
41 
42 //______________________________________________________________________
43 // Node functions
44 
45 void* GetData(G4KDNode* node)
46 {
47  return node->GetData() ;
48 }
49 
50 const double* GetNodePosition(G4KDNode* node)
51 {
52  return node->GetPosition() ;
53 }
54 
55 //______________________________________________________________________
56 
58 {
59  if(!node) return ;
60  node->InactiveNode() ;
61 }
62 
63 void Free(G4KDNode*& node)
64 {
65  if(node)
66  delete node ;
67  node = 0;
68 }
69 //*********************************************
70 
71 G4KDNode::G4KDNode(G4KDTree* tree, const double* position, void* data,
72  G4KDNode* parent, int axis) :
73  fPosition(0), fData(data), fTree(tree),
74  fLeft(0), fRight(0), fParent(parent)
75 {
76  fSide = 0;
77  fAxis = axis;
78  SetPosition(position);
79 }
80 
81 // Copy constructor should not be used
83  fPosition(0), fData(0), fTree(0),
84  fLeft(0), fRight(0), fParent(0)
85 {
86  fSide = 0;
87  fAxis = 0;
88  fPosition = 0;
89 }
90 
91 // Assignement should not be used
93 {
94  if (this == &right) return *this;
95  fPosition = 0;
96  fData = right.fData;
97  fTree = right.fTree;
98  fLeft = right.fLeft;
99  fRight = right.fRight;
100  fParent = right.fParent;
101  fSide = right.fSide;
102  fAxis = right.fAxis;
103  SetPosition(right.fPosition);
104  return *this;
105 }
106 
108 {
109  delete[] fPosition;
110 }
111 
113 {
114  if(fTree)
115  return fTree->GetDim();
116  else
117  return -1;
118 }
119 
121 {
122  fData = 0 ;
123 }
124 
125 int G4KDNode::SetPosition(const double* newposition)
126 {
127  if(!newposition) return -1;
128  if(!fPosition)
129  {
130  fPosition = new double[fTree->fDim];
131  }
132 
133  memcpy(fPosition, newposition, fTree->fDim * sizeof(double));
134 
135  return 0;
136 }
137 
138 G4KDNode* G4KDNode::FindParent(const double* x0)
139 {
140  G4KDNode* aParent = 0 ;
141  G4KDNode* next = this ;
142  int split = -1 ;
143  while(next)
144  {
145  split = next->fAxis ;
146  aParent = next ;
147 
148  if(x0[split] > next->fPosition[split])
149  next = next->fRight ;
150  else
151  next = next->fLeft ;
152  }
153  return aParent ;
154 }
155 
156 G4KDNode* G4KDNode::Insert(const double* p, void* data)
157 {
158  G4KDNode* aParent = FindParent(p);
159  // TODO check p == aParent->pos
160  // Exception
161 
162  G4KDNode* newNode = new G4KDNode(fTree, p, data, aParent,
163  aParent->fAxis +1 < fTree->fDim? aParent->fAxis+1:0);
164 
165  if(p[aParent->fAxis] > aParent->fPosition[aParent->fAxis])
166  {
167  aParent->fRight = newNode ;
168  newNode->fSide = 1 ;
169  }
170  else
171  {
172  aParent->fLeft = newNode ;
173  newNode->fSide = -1 ;
174  }
175 
176  return newNode ;
177 }
178 
179 
180 int G4KDNode::Insert(G4KDNode* newNode, double* p)
181 {
182  G4KDNode* aParent = FindParent(p);
183  // TODO check p == aParent->pos
184  // Exception
185 
186  newNode->fAxis = aParent->fAxis +1 < fTree->fDim? aParent->fAxis+1:0;
187  newNode->fParent = aParent ;
188 
189  if(p[aParent->fAxis] > aParent->fPosition[aParent->fAxis])
190  {
191  aParent->fRight = newNode ;
192  newNode->fSide = 1 ;
193  }
194  else
195  {
196  aParent->fLeft = newNode ;
197  newNode->fSide = -1 ;
198  }
199 
200  newNode->fRight = 0;
201  newNode->fLeft = 0;
202 
203  return 0 ;
204 }
205 
206 int G4KDNode::Insert(G4KDNode* newNode, const double& x, const double& y, const double& z)
207 {
208  double p[3] ;
209  p[0] = x;
210  p[1] = y ;
211  p[2] = z ;
212  return Insert(newNode, p);
213 }
214 
216 {
217  return Insert(newNode, newNode->fPosition);
218 }
219 
221 {
222  if(fParent)
223  {
224  if(fSide == -1)
225  {
226  fParent->fLeft = 0;
227  }
228  else
229  fParent->fRight = 0;
230  }
231  if(fLeft) fLeft -> PullSubTree();
232  if(fRight) fRight-> PullSubTree();
233 
234  fParent = 0 ;
235  fRight = 0 ;
236  fLeft = 0 ;
237  fTree = 0 ;
238 }
239 
240 void G4KDNode::RetrieveNodeList(std::list<G4KDNode*>& output)
241 {
242  output.push_back(this);
243 
244  if(fLeft)
245  fLeft->RetrieveNodeList(output);
246 
247  if(fRight)
248  fRight->RetrieveNodeList(output);
249 }
void InactiveNode()
Definition: G4KDNode.cc:120
void Free(G4KDNode *&node)
Definition: G4KDNode.cc:63
G4KDNode * fLeft
Definition: G4KDNode.hh:102
G4double z
Definition: TRTMaterials.hh:39
G4KDTree is used by the ITManager to locate the neareast neighbours.
Definition: G4KDTree.hh:62
int fAxis
Definition: G4KDNode.hh:93
G4KDNode * FindParent(const double *x0)
Definition: G4KDNode.cc:138
void RetrieveNodeList(std::list< G4KDNode * > &node_list)
Definition: G4KDNode.cc:240
G4KDNode * Insert(const double *p, void *data)
Definition: G4KDNode.cc:156
void * fData
Definition: G4KDNode.hh:94
double * fPosition
Definition: G4KDNode.hh:92
G4KDNode & operator=(const G4KDNode &right)
Definition: G4KDNode.cc:92
int fSide
Definition: G4KDNode.hh:95
void * GetData(G4KDNode *node)
Definition: G4KDNode.cc:45
G4KDNode stores one entity in G4KDTree This class is for internal use only.
Definition: G4KDNode.hh:50
const double * GetNodePosition(G4KDNode *node)
Definition: G4KDNode.cc:50
G4KDTree * fTree
Definition: G4KDNode.hh:101
G4KDNode * fParent
Definition: G4KDNode.hh:102
void * GetData()
Definition: G4KDNode.hh:117
int fDim
Definition: G4KDTree.hh:65
int SetPosition(const double *newposition)
Definition: G4KDNode.cc:125
int position
Definition: filter.cc:7
const double * GetPosition()
Definition: G4KDNode.hh:127
int GetDim()
Definition: G4KDTree.hh:143
virtual ~G4KDNode()
Definition: G4KDNode.cc:107
G4KDNode * fRight
Definition: G4KDNode.hh:102
G4KDNode(G4KDTree *, const double *, void *, G4KDNode *, int axis0)
Definition: G4KDNode.cc:71
void PullSubTree()
Definition: G4KDNode.cc:220
void InactiveNode(G4KDNode *node)
Definition: G4KDNode.cc:57
int GetDim()
Definition: G4KDNode.cc:112