Geant4  10.02.p01
G4KDNode.icc
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 //______________________________________________________________________
37 template<typename PointT>
38  G4KDNode<PointT>::G4KDNode(G4KDTree* tree,
39  PointT* point,
40  G4KDNode_Base* parent) :
41  G4KDNode_Base(tree, parent)
42  {
43  fPoint = point;
44  fValid = true;
45  }
46 
47 // Copy constructor should not be used
48 template<typename PointT>
49  G4KDNode<PointT>::G4KDNode(const G4KDNode<PointT>& right) :
50  G4KDNode_Base(right), fPoint(0)
51  {
52  fValid = false;
53  }
54 
55 // Assignement should not be used
56 template<typename PointT>
57  G4KDNode<PointT>& G4KDNode<PointT>::operator=(const G4KDNode<PointT>& right)
58  {
59  if(this == &right) return *this;
60  fPoint = right.fPoint;
61  fTree = right.fTree;
62  fLeft = right.fLeft;
63  fRight = right.fRight;
64  fParent = right.fParent;
65  fSide = right.fSide;
66  fAxis = right.fAxis;
67  return *this;
68  }
69 
70 template<typename PointT>
71  G4KDNode<PointT>::~G4KDNode()
72  {
73  }
74 
75 template<typename Position>
76  G4KDNode_Base* G4KDNode_Base::FindParent(const Position& x0)
77  {
78  G4KDNode_Base* aParent = 0;
79  G4KDNode_Base* next = this;
80  int split = -1;
81  while(next)
82  {
83  split = next->fAxis;
84  aParent = next;
85 
86  // works if node called "next" is valid
87  if(x0[split] > (*next)[split]) next = next->fRight;
88  else next = next->fLeft;
89  }
90  return aParent;
91  }
92 
93 template<typename PointT>
94  G4KDNode_Base* G4KDNode_Base::Insert(PointT* point)
95  {
96  G4KDNode_Base* aParent = FindParent(*point);
97  // TODO check p == aParent->pos
98  // Exception
99 
100  G4KDNode_Base* newNode = new G4KDNode<PointT>(fTree, point, aParent);
101 
102  if((*point)[aParent->fAxis] > (*aParent)[aParent->fAxis])
103  {
104  aParent->fRight = newNode;
105  newNode->fSide = 1;
106  }
107  else
108  {
109  aParent->fLeft = newNode;
110  newNode->fSide = -1;
111  }
112 
113  return newNode;
114  }
115 
116 template<typename PointT>
117  G4KDNode_Base* G4KDNode_Base::Insert(const PointT& point)
118  {
119  G4KDNode_Base* aParent = FindParent(point);
120  // TODO check p == aParent->pos
121  // Exception
122 
123  G4KDNode_Base* newNode = new G4KDNodeCopy<PointT>(fTree, point, aParent);
124 
125  if(point[aParent->fAxis] > (*aParent)[aParent->fAxis])
126  {
127  aParent->fRight = newNode;
128  newNode->fSide = 1;
129  }
130  else
131  {
132  aParent->fLeft = newNode;
133  newNode->fSide = -1;
134  }
135 
136  return newNode;
137  }
138