2 // ********************************************************************
3 // * License and Disclaimer *
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. *
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. *
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 // ********************************************************************
26 // $Id: G4KDNode.cc 64057 2012-10-30 15:04:49Z gcosmo $
28 // Author: Mathieu Karamitros (kara (AT) cenbg . in2p3 . fr)
32 // 10 Oct 2011 M.Karamitros created
34 // -------------------------------------------------------------------
36 //______________________________________________________________________
37 template<typename PointT>
38 G4KDNode<PointT>::G4KDNode(G4KDTree* tree,
40 G4KDNode_Base* parent) :
41 G4KDNode_Base(tree, parent)
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)
55 // Assignement should not be used
56 template<typename PointT>
57 G4KDNode<PointT>& G4KDNode<PointT>::operator=(const G4KDNode<PointT>& right)
59 if(this == &right) return *this;
60 fPoint = right.fPoint;
63 fRight = right.fRight;
64 fParent = right.fParent;
70 template<typename PointT>
71 G4KDNode<PointT>::~G4KDNode()
75 template<typename Position>
76 G4KDNode_Base* G4KDNode_Base::FindParent(const Position& x0)
78 G4KDNode_Base* aParent = 0;
79 G4KDNode_Base* next = this;
86 // works if node called "next" is valid
87 if(x0[split] > (*next)[split]) next = next->fRight;
88 else next = next->fLeft;
93 template<typename PointT>
94 G4KDNode_Base* G4KDNode_Base::Insert(PointT* point)
96 G4KDNode_Base* aParent = FindParent(*point);
97 // TODO check p == aParent->pos
100 G4KDNode_Base* newNode = new G4KDNode<PointT>(fTree, point, aParent);
102 if((*point)[aParent->fAxis] > (*aParent)[aParent->fAxis])
104 aParent->fRight = newNode;
109 aParent->fLeft = newNode;
116 template<typename PointT>
117 G4KDNode_Base* G4KDNode_Base::Insert(const PointT& point)
119 G4KDNode_Base* aParent = FindParent(point);
120 // TODO check p == aParent->pos
123 G4KDNode_Base* newNode = new G4KDNodeCopy<PointT>(fTree, point, aParent);
125 if(point[aParent->fAxis] > (*aParent)[aParent->fAxis])
127 aParent->fRight = newNode;
132 aParent->fLeft = newNode;