| Geant4 Cross Reference |
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 //
27 // Author: Mathieu Karamitros (kara (AT) cenbg . in2p3 . fr)
28 //
29 // History:
30 // -----------
31 // 10 Oct 2011 M.Karamitros created
32 //
33 // -------------------------------------------------------------------
34
35 #include "globals.hh"
36 #include "G4KDNode.hh"
37 #include "G4KDTree.hh"
38 #include <ostream>
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
57 void InactiveNode(G4KDNode_Base* node)
58 {
59 if(node == nullptr) return;
60 // if(node->IsValid())
61 node->InactiveNode();
62 }
63
64 void Free(G4KDNode_Base*& node)
65 {
66 delete node;
67 node = nullptr;
68 }
69
70 //______________________________________________________________________
71 G4KDNode_Base::G4KDNode_Base(G4KDTree* tree,
72 G4KDNode_Base* parent):
73 fTree(tree),
74 fParent(parent)
75 {
76 fSide = 0;
77 fAxis = fParent == nullptr? 0 : fParent->fAxis +1 < fTree->fDim? fParent->fAxis+1:0;
78 }
79
80 // Copy constructor should not be used
81 G4KDNode_Base::G4KDNode_Base(const G4KDNode_Base& )
82 {
83 fSide = 0;
84 fAxis = 0;
85 }
86
87 // Assignement should not be used
88 G4KDNode_Base& G4KDNode_Base::operator=(const G4KDNode_Base& right)
89 {
90 if (this == &right) return *this;
91 fTree = right.fTree;
92 fLeft = right.fLeft;
93 fRight = right.fRight;
94 fParent = right.fParent;
95 fSide = right.fSide;
96 fAxis = right.fAxis;
97 return *this;
98 }
99
100 G4KDNode_Base::~G4KDNode_Base()
101 = default;
102
103 void G4KDNode_Base::InactiveNode()
104 {
105 fTree->NoticeNodeDeactivation();
106 }
107
108 G4int G4KDNode_Base::GetDim() const
109 {
110 if(fTree != nullptr) return (G4int)fTree->GetDim();
111 return -1;
112 }
113
114 G4int G4KDNode_Base::Insert(G4KDNode_Base* newNode)
115 {
116 G4KDNode_Base* aParent = FindParent(*newNode);
117 // TODO check p == aParent->pos
118 // Exception
119
120 newNode->fAxis = aParent->fAxis +1 < fTree->GetDim()? aParent->fAxis+1:0;
121 newNode->fParent = aParent ;
122
123 if((*newNode)[aParent->fAxis] > (*aParent)[aParent->fAxis])
124 {
125 aParent->fRight = newNode ;
126 newNode->fSide = 1 ;
127 }
128 else
129 {
130 aParent->fLeft = newNode ;
131 newNode->fSide = -1 ;
132 }
133
134 newNode->fRight = nullptr;
135 newNode->fLeft = nullptr;
136
137 return 0 ;
138 }
139
140
141 void G4KDNode_Base::PullSubTree()
142 {
143 if(fParent != nullptr)
144 {
145 if(fSide == -1)
146 {
147 fParent->fLeft = nullptr;
148 }
149 else
150 fParent->fRight = nullptr;
151 }
152 if(fLeft != nullptr) fLeft -> PullSubTree();
153 if(fRight != nullptr) fRight-> PullSubTree();
154
155 fParent = nullptr ;
156 fRight = nullptr ;
157 fLeft = nullptr ;
158 fTree = nullptr ;
159 }
160
161 void G4KDNode_Base::RetrieveNodeList(std::list<G4KDNode_Base *>& output)
162 {
163 output.push_back(this);
164
165 if(fLeft != nullptr)
166 fLeft->RetrieveNodeList(output);
167
168 if(fRight != nullptr)
169 fRight->RetrieveNodeList(output);
170 }
171
172 void G4KDNode_Base::Print(std::ostream& out, int level) const
173 {
174 // Print node level
175 out << G4endl;
176 for (G4int i=0; i<level; ++i) // Indent to level
177 {
178 out << " ";
179 }
180 out << level;
181
182 // Print children
183 if(fLeft != nullptr)
184 {
185 fLeft->Print(out, level + 1);
186 }
187 if(fRight != nullptr)
188 {
189 fRight->Print(out, level + 1);
190 }
191 }
192