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// ********************************************************************
27// Author: Mathieu Karamitros (kara (AT) cenbg . in2p3 . fr)
31// 10 Oct 2011 M.Karamitros created
33// -------------------------------------------------------------------
35//______________________________________________________________________
36template<typename PointT>
37 G4KDNode<PointT>::G4KDNode(G4KDTree* tree,
39 G4KDNode_Base* parent) :
40 G4KDNode_Base(tree, parent)
46// Copy constructor should not be used
47template<typename PointT>
48 G4KDNode<PointT>::G4KDNode(const G4KDNode<PointT>& right) :
49 G4KDNode_Base(right), fPoint(0)
54// Assignement should not be used
55template<typename PointT>
56 G4KDNode<PointT>& G4KDNode<PointT>::operator=(const G4KDNode<PointT>& right)
58 if(this == &right) return *this;
59 fPoint = right.fPoint;
62 fRight = right.fRight;
63 fParent = right.fParent;
69template<typename PointT>
70 G4KDNode<PointT>::~G4KDNode()
74template<typename Position>
75 G4KDNode_Base* G4KDNode_Base::FindParent(const Position& x0)
77 G4KDNode_Base* aParent = 0;
78 G4KDNode_Base* next = this;
85 // works if node called "next" is valid
86 if(x0[split] > (*next)[split]) next = next->fRight;
87 else next = next->fLeft;
92template<typename PointT>
93 G4KDNode_Base* G4KDNode_Base::Insert(PointT* point)
95 G4KDNode_Base* aParent = FindParent(*point);
96 // TODO check p == aParent->pos
99 G4KDNode_Base* newNode = new G4KDNode<PointT>(fTree, point, aParent);
101 if((*point)[aParent->fAxis] > (*aParent)[aParent->fAxis])
103 aParent->fRight = newNode;
108 aParent->fLeft = newNode;
115template<typename PointT>
116 G4KDNode_Base* G4KDNode_Base::Insert(const PointT& point)
118 G4KDNode_Base* aParent = FindParent(point);
119 // TODO check p == aParent->pos
122 G4KDNode_Base* newNode = new G4KDNodeCopy<PointT>(fTree, point, aParent);
124 if(point[aParent->fAxis] > (*aParent)[aParent->fAxis])
126 aParent->fRight = newNode;
131 aParent->fLeft = newNode;