Geant4 Cross Reference |
1 // 1 // 2 // ******************************************* 2 // ******************************************************************** 3 // * License and Disclaimer 3 // * License and Disclaimer * 4 // * 4 // * * 5 // * The Geant4 software is copyright of th 5 // * The Geant4 software is copyright of the Copyright Holders of * 6 // * the Geant4 Collaboration. It is provided 6 // * the Geant4 Collaboration. It is provided under the terms and * 7 // * conditions of the Geant4 Software License 7 // * conditions of the Geant4 Software License, included in the file * 8 // * LICENSE and available at http://cern.ch/ 8 // * LICENSE and available at http://cern.ch/geant4/license . These * 9 // * include a list of copyright holders. 9 // * include a list of copyright holders. * 10 // * 10 // * * 11 // * Neither the authors of this software syst 11 // * Neither the authors of this software system, nor their employing * 12 // * institutes,nor the agencies providing fin 12 // * institutes,nor the agencies providing financial support for this * 13 // * work make any representation or warran 13 // * work make any representation or warranty, express or implied, * 14 // * regarding this software system or assum 14 // * regarding this software system or assume any liability for its * 15 // * use. Please see the license in the file 15 // * use. Please see the license in the file LICENSE and URL above * 16 // * for the full disclaimer and the limitatio 16 // * for the full disclaimer and the limitation of liability. * 17 // * 17 // * * 18 // * This code implementation is the result 18 // * This code implementation is the result of the scientific and * 19 // * technical work of the GEANT4 collaboratio 19 // * technical work of the GEANT4 collaboration. * 20 // * By using, copying, modifying or distri 20 // * By using, copying, modifying or distributing the software (or * 21 // * any work based on the software) you ag 21 // * any work based on the software) you agree to acknowledge its * 22 // * use in resulting scientific publicati 22 // * use in resulting scientific publications, and indicate your * 23 // * acceptance of all terms of the Geant4 Sof 23 // * acceptance of all terms of the Geant4 Software license. * 24 // ******************************************* 24 // ******************************************************************** 25 // 25 // >> 26 // $Id: G4KDNode.cc 64057 2012-10-30 15:04:49Z gcosmo $ 26 // 27 // 27 // Author: Mathieu Karamitros (kara (AT) cenbg 28 // Author: Mathieu Karamitros (kara (AT) cenbg . in2p3 . fr) 28 // 29 // 29 // History: 30 // History: 30 // ----------- 31 // ----------- 31 // 10 Oct 2011 M.Karamitros created 32 // 10 Oct 2011 M.Karamitros created 32 // 33 // 33 // ------------------------------------------- 34 // ------------------------------------------------------------------- 34 35 35 #include "globals.hh" 36 #include "globals.hh" 36 #include "G4KDNode.hh" 37 #include "G4KDNode.hh" 37 #include "G4KDTree.hh" 38 #include "G4KDTree.hh" 38 #include <ostream> << 39 39 40 //******************************************** 40 //********************************************* 41 41 42 //____________________________________________ 42 //______________________________________________________________________ 43 // Node functions 43 // Node functions 44 44 45 //void* GetData(G4KDNode* node) << 45 void* GetData(G4KDNode* node) 46 //{ << 46 { 47 // return node->GetData() ; << 47 return node->GetData() ; 48 //} << 48 } 49 // << 49 50 //const double* GetNodePosition(G4KDNode* node << 50 const double* GetNodePosition(G4KDNode* node) 51 //{ << 51 { 52 // return node->GetPosition() ; << 52 return node->GetPosition() ; 53 //} << 53 } 54 54 55 //____________________________________________ 55 //______________________________________________________________________ 56 56 57 void InactiveNode(G4KDNode_Base* node) << 57 void InactiveNode(G4KDNode* node) 58 { 58 { 59 if(node == nullptr) return; << 59 if(!node) return ; 60 // if(node->IsValid()) << 60 node->InactiveNode() ; 61 node->InactiveNode(); << 62 } 61 } 63 62 64 void Free(G4KDNode_Base*& node) << 63 void Free(G4KDNode*& node) 65 { 64 { 66 delete node; << 65 if(node) 67 node = nullptr; << 66 delete node ; >> 67 node = 0; 68 } 68 } >> 69 //********************************************* 69 70 70 //____________________________________________ << 71 G4KDNode::G4KDNode(G4KDTree* tree, const double* position, void* data, 71 G4KDNode_Base::G4KDNode_Base(G4KDTree* tree, << 72 G4KDNode* parent, int axis) : 72 G4KDNode_Base* parent): << 73 fPosition(0), fData(data), fTree(tree), 73 fTree(tree), << 74 fLeft(0), fRight(0), fParent(parent) 74 fParent(parent) << 75 { 75 { << 76 fSide = 0; 76 fSide = 0; << 77 fAxis = axis; 77 fAxis = fParent == nullptr? 0 : fParent->fAx << 78 SetPosition(position); 78 } 79 } 79 80 80 // Copy constructor should not be used 81 // Copy constructor should not be used 81 G4KDNode_Base::G4KDNode_Base(const G4KDNode_Ba << 82 G4KDNode::G4KDNode(const G4KDNode& ): 82 { << 83 fPosition(0), fData(0), fTree(0), 83 fSide = 0; << 84 fLeft(0), fRight(0), fParent(0) 84 fAxis = 0; << 85 { >> 86 fSide = 0; >> 87 fAxis = 0; >> 88 fPosition = 0; 85 } 89 } 86 90 87 // Assignement should not be used 91 // Assignement should not be used 88 G4KDNode_Base& G4KDNode_Base::operator=(const << 92 G4KDNode& G4KDNode::operator=(const G4KDNode& right) 89 { 93 { 90 if (this == &right) return *this; << 94 if (this == &right) return *this; 91 fTree = right.fTree; << 95 fPosition = 0; 92 fLeft = right.fLeft; << 96 fData = right.fData; 93 fRight = right.fRight; << 97 fTree = right.fTree; 94 fParent = right.fParent; << 98 fLeft = right.fLeft; 95 fSide = right.fSide; << 99 fRight = right.fRight; 96 fAxis = right.fAxis; << 100 fParent = right.fParent; 97 return *this; << 101 fSide = right.fSide; >> 102 fAxis = right.fAxis; >> 103 SetPosition(right.fPosition); >> 104 return *this; 98 } 105 } 99 106 100 G4KDNode_Base::~G4KDNode_Base() << 107 G4KDNode::~G4KDNode() 101 = default; << 108 { >> 109 delete[] fPosition; >> 110 } 102 111 103 void G4KDNode_Base::InactiveNode() << 112 int G4KDNode::GetDim() 104 { 113 { 105 fTree->NoticeNodeDeactivation(); << 114 if(fTree) >> 115 return fTree->GetDim(); >> 116 else >> 117 return -1; 106 } 118 } 107 119 108 G4int G4KDNode_Base::GetDim() const << 120 void G4KDNode::InactiveNode() 109 { 121 { 110 if(fTree != nullptr) return (G4int)fTree->Ge << 122 fData = 0 ; 111 return -1; << 112 } 123 } 113 124 114 G4int G4KDNode_Base::Insert(G4KDNode_Base* new << 125 int G4KDNode::SetPosition(const double* newposition) 115 { 126 { 116 G4KDNode_Base* aParent = FindParent(*newNode << 127 if(!newposition) return -1; 117 // TODO check p == aParent->pos << 128 if(!fPosition) 118 // Exception << 129 { >> 130 fPosition = new double[fTree->fDim]; >> 131 } 119 132 120 newNode->fAxis = aParent->fAxis +1 < fTree-> << 133 memcpy(fPosition, newposition, fTree->fDim * sizeof(double)); 121 newNode->fParent = aParent ; << 122 134 123 if((*newNode)[aParent->fAxis] > (*aParent)[a << 135 return 0; 124 { << 136 } 125 aParent->fRight = newNode ; << 126 newNode->fSide = 1 ; << 127 } << 128 else << 129 { << 130 aParent->fLeft = newNode ; << 131 newNode->fSide = -1 ; << 132 } << 133 137 134 newNode->fRight = nullptr; << 138 G4KDNode* G4KDNode::FindParent(const double* x0) 135 newNode->fLeft = nullptr; << 139 { >> 140 G4KDNode* aParent = 0 ; >> 141 G4KDNode* next = this ; >> 142 int split = -1 ; >> 143 while(next) >> 144 { >> 145 split = next->fAxis ; >> 146 aParent = next ; 136 147 137 return 0 ; << 148 if(x0[split] > next->fPosition[split]) >> 149 next = next->fRight ; >> 150 else >> 151 next = next->fLeft ; >> 152 } >> 153 return aParent ; 138 } 154 } 139 155 >> 156 G4KDNode* G4KDNode::Insert(const double* p, void* data) >> 157 { >> 158 G4KDNode* aParent = FindParent(p); >> 159 // TODO check p == aParent->pos >> 160 // Exception 140 161 141 void G4KDNode_Base::PullSubTree() << 162 G4KDNode* newNode = new G4KDNode(fTree, p, data, aParent, >> 163 aParent->fAxis +1 < fTree->fDim? aParent->fAxis+1:0); >> 164 >> 165 if(p[aParent->fAxis] > aParent->fPosition[aParent->fAxis]) >> 166 { >> 167 aParent->fRight = newNode ; >> 168 newNode->fSide = 1 ; >> 169 } >> 170 else >> 171 { >> 172 aParent->fLeft = newNode ; >> 173 newNode->fSide = -1 ; >> 174 } >> 175 >> 176 return newNode ; >> 177 } >> 178 >> 179 >> 180 int G4KDNode::Insert(G4KDNode* newNode, double* p) 142 { 181 { 143 if(fParent != nullptr) << 182 G4KDNode* aParent = FindParent(p); 144 { << 183 // TODO check p == aParent->pos 145 if(fSide == -1) << 184 // Exception 146 { << 185 147 fParent->fLeft = nullptr; << 186 newNode->fAxis = aParent->fAxis +1 < fTree->fDim? aParent->fAxis+1:0; 148 } << 187 newNode->fParent = aParent ; 149 else << 188 150 fParent->fRight = nullptr; << 189 if(p[aParent->fAxis] > aParent->fPosition[aParent->fAxis]) 151 } << 190 { 152 if(fLeft != nullptr) fLeft -> PullSubTree(); << 191 aParent->fRight = newNode ; 153 if(fRight != nullptr) fRight-> PullSubTree() << 192 newNode->fSide = 1 ; >> 193 } >> 194 else >> 195 { >> 196 aParent->fLeft = newNode ; >> 197 newNode->fSide = -1 ; >> 198 } 154 199 155 fParent = nullptr ; << 200 newNode->fRight = 0; 156 fRight = nullptr ; << 201 newNode->fLeft = 0; 157 fLeft = nullptr ; << 202 158 fTree = nullptr ; << 203 return 0 ; 159 } 204 } 160 205 161 void G4KDNode_Base::RetrieveNodeList(std::list << 206 int G4KDNode::Insert(G4KDNode* newNode, const double& x, const double& y, const double& z) 162 { 207 { 163 output.push_back(this); << 208 double p[3] ; >> 209 p[0] = x; >> 210 p[1] = y ; >> 211 p[2] = z ; >> 212 return Insert(newNode, p); >> 213 } 164 214 165 if(fLeft != nullptr) << 215 int G4KDNode::Insert(G4KDNode* newNode) 166 fLeft->RetrieveNodeList(output); << 216 { >> 217 return Insert(newNode, newNode->fPosition); >> 218 } 167 219 168 if(fRight != nullptr) << 220 void G4KDNode::PullSubTree() 169 fRight->RetrieveNodeList(output); << 221 { >> 222 if(fParent) >> 223 { >> 224 if(fSide == -1) >> 225 { >> 226 fParent->fLeft = 0; >> 227 } >> 228 else >> 229 fParent->fRight = 0; >> 230 } >> 231 if(fLeft) fLeft -> PullSubTree(); >> 232 if(fRight) fRight-> PullSubTree(); >> 233 >> 234 fParent = 0 ; >> 235 fRight = 0 ; >> 236 fLeft = 0 ; >> 237 fTree = 0 ; 170 } 238 } 171 239 172 void G4KDNode_Base::Print(std::ostream& out, i << 240 void G4KDNode::RetrieveNodeList(std::list<G4KDNode*>& output) 173 { 241 { 174 // Print node level << 242 output.push_back(this); 175 out << G4endl; << 243 176 for (G4int i=0; i<level; ++i) // Ind << 244 if(fLeft) 177 { << 245 fLeft->RetrieveNodeList(output); 178 out << " "; << 179 } << 180 out << level; << 181 246 182 // Print children << 247 if(fRight) 183 if(fLeft != nullptr) << 248 fRight->RetrieveNodeList(output); 184 { << 185 fLeft->Print(out, level + 1); << 186 } << 187 if(fRight != nullptr) << 188 { << 189 fRight->Print(out, level + 1); << 190 } << 191 } 249 } 192 250