Geant4  10.01
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, PointT* point,
39  G4KDNode_Base* parent) : G4KDNode_Base(tree, parent)
40 {
41  fPoint = point;
42  fValid = true;
43 }
44 
45 // Copy constructor should not be used
46 template <typename PointT>
47 G4KDNode<PointT>::G4KDNode(const G4KDNode<PointT>& right): G4KDNode_Base(right),
48  fPoint(0)
49 {
50  fValid = false;
51 }
52 
53 // Assignement should not be used
54 template <typename PointT>
55 G4KDNode<PointT>& G4KDNode<PointT>::operator=(const G4KDNode<PointT>& right)
56 {
57  if (this == &right) return *this;
58  fPoint = right.fPoint;
59  fTree = right.fTree;
60  fLeft = right.fLeft;
61  fRight = right.fRight;
62  fParent = right.fParent;
63  fSide = right.fSide;
64  fAxis = right.fAxis;
65  return *this;
66 }
67 
68 template <typename PointT>
69 G4KDNode<PointT>::~G4KDNode()
70 {
71 }
72 
73 template <typename Position>
74 G4KDNode_Base* G4KDNode_Base::FindParent(const Position& x0)
75 {
76  G4KDNode_Base* aParent = 0 ;
77  G4KDNode_Base* next = this ;
78  int split = -1 ;
79  while(next)
80  {
81  split = next->fAxis ;
82  aParent = next ;
83 
84  // works if node called "next" is valid
85  if(x0[split] > (*next)[split])
86  next = next->fRight ;
87  else
88  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