00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036 #include "globals.hh"
00037 #include "G4KDNode.hh"
00038 #include "G4KDTree.hh"
00039
00040
00041
00042
00043
00044
00045 void* GetData(G4KDNode* node)
00046 {
00047 return node->GetData() ;
00048 }
00049
00050 const double* GetNodePosition(G4KDNode* node)
00051 {
00052 return node->GetPosition() ;
00053 }
00054
00055
00056
00057 void InactiveNode(G4KDNode* node)
00058 {
00059 if(!node) return ;
00060 node->InactiveNode() ;
00061 }
00062
00063 void Free(G4KDNode*& node)
00064 {
00065 if(node)
00066 delete node ;
00067 node = 0;
00068 }
00069
00070
00071 G4KDNode::G4KDNode(G4KDTree* tree, const double* position, void* data,
00072 G4KDNode* parent, int axis) :
00073 fPosition(0), fData(data), fTree(tree),
00074 fLeft(0), fRight(0), fParent(parent)
00075 {
00076 fSide = 0;
00077 fAxis = axis;
00078 SetPosition(position);
00079 }
00080
00081
00082 G4KDNode::G4KDNode(const G4KDNode& ):
00083 fPosition(0), fData(0), fTree(0),
00084 fLeft(0), fRight(0), fParent(0)
00085 {
00086 fSide = 0;
00087 fAxis = 0;
00088 fPosition = 0;
00089 }
00090
00091
00092 G4KDNode& G4KDNode::operator=(const G4KDNode& right)
00093 {
00094 if (this == &right) return *this;
00095 fPosition = 0;
00096 fData = right.fData;
00097 fTree = right.fTree;
00098 fLeft = right.fLeft;
00099 fRight = right.fRight;
00100 fParent = right.fParent;
00101 fSide = right.fSide;
00102 fAxis = right.fAxis;
00103 SetPosition(right.fPosition);
00104 return *this;
00105 }
00106
00107 G4KDNode::~G4KDNode()
00108 {
00109 delete[] fPosition;
00110 }
00111
00112 int G4KDNode::GetDim()
00113 {
00114 if(fTree)
00115 return fTree->GetDim();
00116 else
00117 return -1;
00118 }
00119
00120 void G4KDNode::InactiveNode()
00121 {
00122 fData = 0 ;
00123 }
00124
00125 int G4KDNode::SetPosition(const double* newposition)
00126 {
00127 if(!newposition) return -1;
00128 if(!fPosition)
00129 {
00130 fPosition = new double[fTree->fDim];
00131 }
00132
00133 memcpy(fPosition, newposition, fTree->fDim * sizeof(double));
00134
00135 return 0;
00136 }
00137
00138 G4KDNode* G4KDNode::FindParent(const double* x0)
00139 {
00140 G4KDNode* aParent = 0 ;
00141 G4KDNode* next = this ;
00142 int split = -1 ;
00143 while(next)
00144 {
00145 split = next->fAxis ;
00146 aParent = next ;
00147
00148 if(x0[split] > next->fPosition[split])
00149 next = next->fRight ;
00150 else
00151 next = next->fLeft ;
00152 }
00153 return aParent ;
00154 }
00155
00156 G4KDNode* G4KDNode::Insert(const double* p, void* data)
00157 {
00158 G4KDNode* aParent = FindParent(p);
00159
00160
00161
00162 G4KDNode* newNode = new G4KDNode(fTree, p, data, aParent,
00163 aParent->fAxis +1 < fTree->fDim? aParent->fAxis+1:0);
00164
00165 if(p[aParent->fAxis] > aParent->fPosition[aParent->fAxis])
00166 {
00167 aParent->fRight = newNode ;
00168 newNode->fSide = 1 ;
00169 }
00170 else
00171 {
00172 aParent->fLeft = newNode ;
00173 newNode->fSide = -1 ;
00174 }
00175
00176 return newNode ;
00177 }
00178
00179
00180 int G4KDNode::Insert(G4KDNode* newNode, double* p)
00181 {
00182 G4KDNode* aParent = FindParent(p);
00183
00184
00185
00186 newNode->fAxis = aParent->fAxis +1 < fTree->fDim? aParent->fAxis+1:0;
00187 newNode->fParent = aParent ;
00188
00189 if(p[aParent->fAxis] > aParent->fPosition[aParent->fAxis])
00190 {
00191 aParent->fRight = newNode ;
00192 newNode->fSide = 1 ;
00193 }
00194 else
00195 {
00196 aParent->fLeft = newNode ;
00197 newNode->fSide = -1 ;
00198 }
00199
00200 newNode->fRight = 0;
00201 newNode->fLeft = 0;
00202
00203 return 0 ;
00204 }
00205
00206 int G4KDNode::Insert(G4KDNode* newNode, const double& x, const double& y, const double& z)
00207 {
00208 double p[3] ;
00209 p[0] = x;
00210 p[1] = y ;
00211 p[2] = z ;
00212 return Insert(newNode, p);
00213 }
00214
00215 int G4KDNode::Insert(G4KDNode* newNode)
00216 {
00217 return Insert(newNode, newNode->fPosition);
00218 }
00219
00220 void G4KDNode::PullSubTree()
00221 {
00222 if(fParent)
00223 {
00224 if(fSide == -1)
00225 {
00226 fParent->fLeft = 0;
00227 }
00228 else
00229 fParent->fRight = 0;
00230 }
00231 if(fLeft) fLeft -> PullSubTree();
00232 if(fRight) fRight-> PullSubTree();
00233
00234 fParent = 0 ;
00235 fRight = 0 ;
00236 fLeft = 0 ;
00237 fTree = 0 ;
00238 }
00239
00240 void G4KDNode::RetrieveNodeList(std::list<G4KDNode*>& output)
00241 {
00242 output.push_back(this);
00243
00244 if(fLeft)
00245 fLeft->RetrieveNodeList(output);
00246
00247 if(fRight)
00248 fRight->RetrieveNodeList(output);
00249 }