| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /*************************************** | ||
| 2 | Auteur : Pierre Aubert | ||
| 3 | Mail : pierre.aubert@lapp.in2p3.fr | ||
| 4 | Licence : CeCILL-C | ||
| 5 | ****************************************/ | ||
| 6 | |||
| 7 | #ifndef __PNTREE_LIGHT_NODE_H_IMPL__ | ||
| 8 | #define __PNTREE_LIGHT_NODE_H_IMPL__ | ||
| 9 | |||
| 10 | #include <string.h> | ||
| 11 | #include <math.h> | ||
| 12 | |||
| 13 | #include "pstatic_computation.h" | ||
| 14 | |||
| 15 | #include "PNTreeLightNode.h" | ||
| 16 | |||
| 17 | ///Default constructor of PNTreeLightNode | ||
| 18 | template<typename T, typename U, unsigned char N> | ||
| 19 | 670 | PNTreeLightNode<T, U, N>::PNTreeLightNode(){ | |
| 20 | 670 | initialisationPNTreeLightNode(); | |
| 21 | 670 | } | |
| 22 | |||
| 23 | ///Copy constructor of PNTreeLightNode | ||
| 24 | /** @param other : class to copy | ||
| 25 | */ | ||
| 26 | template<typename T, typename U, unsigned char N> | ||
| 27 | PNTreeLightNode<T, U, N>::PNTreeLightNode(const PNTreeLightNode<T, U, N> & other){ | ||
| 28 | copyPNTreeLightNode(other); | ||
| 29 | } | ||
| 30 | |||
| 31 | ///Destructeur of PNTreeLightNode | ||
| 32 | template<typename T, typename U, unsigned char N> | ||
| 33 | 670 | PNTreeLightNode<T, U, N>::~PNTreeLightNode(){ | |
| 34 | 670 | clear(); | |
| 35 | 670 | } | |
| 36 | |||
| 37 | ///Get the size of the child | ||
| 38 | /** @param[out] childSize : child size | ||
| 39 | * @param parentSize : parent size | ||
| 40 | */ | ||
| 41 | template<typename T, unsigned char N> | ||
| 42 | 1828 | void makeHalfSize(T childSize[N], const T parentSize[N]){ | |
| 43 |
2/2✓ Branch 0 (4→3) taken 5268 times.
✓ Branch 1 (4→5) taken 1828 times.
|
7096 | for(unsigned char i(0lu); i < N; ++i){ |
| 44 | 5268 | childSize[i] = parentSize[i]/2.f; | |
| 45 | } | ||
| 46 | 1828 | } | |
| 47 | |||
| 48 | ///Check the size of the childs of a N Tree | ||
| 49 | /** @param halfSizeChild : table of half size of the current N Tree | ||
| 50 | * @param sizeLimit : limit of the cell size | ||
| 51 | * @return true if everything is OK, false if the childs are too small | ||
| 52 | */ | ||
| 53 | template<typename T, unsigned char N> | ||
| 54 | 2492 | bool checkSizeLimitLight(const T halfSizeChild[N], T sizeLimit){ | |
| 55 |
2/2✓ Branch 0 (6→3) taken 7178 times.
✓ Branch 1 (6→7) taken 2492 times.
|
9670 | for(unsigned char i(0); i < N; ++i){ |
| 56 |
1/2✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 7178 times.
|
7178 | if(halfSizeChild[i] < sizeLimit) return false; |
| 57 | } | ||
| 58 | 2492 | return true; | |
| 59 | } | ||
| 60 | |||
| 61 | ///Add an element in the PNTreeLightNode | ||
| 62 | /** @param posData : position of the data | ||
| 63 | * @param data : pointer to the data we want to sort | ||
| 64 | * @param pos : position of the current node | ||
| 65 | * @param size : size of the current node | ||
| 66 | * @param sizeLimit : limit of the cell size | ||
| 67 | * @return true on success, false otherwise | ||
| 68 | */ | ||
| 69 | template<typename T, typename U, unsigned char N> | ||
| 70 | 2398 | bool PNTreeLightNode<T, U, N>::addElement(T * posData, U * data, const T pos[N], const T size[N], T sizeLimit){ | |
| 71 |
1/2✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 2398 times.
|
2398 | if(!checkSizeLimitLight<T, N>(size, sizeLimit)){ |
| 72 | ✗ | return false; | |
| 73 | } | ||
| 74 |
2/2✓ Branch 0 (5→6) taken 764 times.
✓ Branch 1 (5→13) taken 1634 times.
|
2398 | if(p_tableChildren == NULL){ |
| 75 |
2/2✓ Branch 0 (6→7) taken 670 times.
✓ Branch 1 (6→8) taken 94 times.
|
764 | if(p_data == NULL){ //The cell is empty |
| 76 | 670 | p_data = data; | |
| 77 | 670 | p_posData = posData; | |
| 78 | 670 | return true; | |
| 79 | }else{ //There is a data in the cell | ||
| 80 |
1/2✗ Branch 0 (9→10) not taken.
✓ Branch 1 (9→11) taken 94 times.
|
94 | if(!split(pos, size, sizeLimit)) return false; |
| 81 | 94 | return addElement(posData, data, pos, size, sizeLimit); | |
| 82 | } | ||
| 83 | }else{ //There are children | ||
| 84 | T childPos[N]; | ||
| 85 | 1634 | PNTreeLightNode<T, U, N> * child = getChildFromPos(childPos, posData, pos, size); | |
| 86 |
1/2✗ Branch 0 (14→15) not taken.
✓ Branch 1 (14→16) taken 1634 times.
|
1634 | if(child == NULL){ |
| 87 | ✗ | return false; | |
| 88 | }else{ | ||
| 89 | T childSize[N]; | ||
| 90 | 1634 | makeHalfSize<T,N>(childSize, size); | |
| 91 |
1/1✓ Branch 0 (17→18) taken 1634 times.
|
1634 | return child->addElement(posData, data, childPos, childSize, sizeLimit); |
| 92 | } | ||
| 93 | } | ||
| 94 | } | ||
| 95 | |||
| 96 | ///Saves the PNTreeLightNode into a txt file for gnuplot | ||
| 97 | /** @param fileName : name of the text file we want to write | ||
| 98 | * @param pos : position of the current node | ||
| 99 | * @param size : size of the current node | ||
| 100 | * @return true on success, false otherwise | ||
| 101 | */ | ||
| 102 | template<typename T, typename U, unsigned char N> | ||
| 103 | 2 | bool PNTreeLightNode<T, U, N>::saveGnuplotData(const std::string & fileName, T pos[N], T size[N]){ | |
| 104 |
2/3✓ Branch 0 (2→3) taken 2 times.
✗ Branch 2 (3→4) not taken.
✓ Branch 3 (3→5) taken 2 times.
|
2 | if(fileName == "") return false; |
| 105 |
1/1✓ Branch 0 (5→6) taken 2 times.
|
2 | std::ofstream fs; |
| 106 |
1/1✓ Branch 0 (6→7) taken 2 times.
|
2 | fs.open(fileName); |
| 107 |
1/2✗ Branch 0 (8→9) not taken.
✓ Branch 1 (8→10) taken 2 times.
|
2 | if(!fs.is_open()){return false;} |
| 108 |
1/1✓ Branch 0 (10→11) taken 2 times.
|
2 | bool b = saveGnuplotData(fs, 0, pos, size); |
| 109 |
1/1✓ Branch 0 (11→12) taken 2 times.
|
2 | fs.close(); |
| 110 | 2 | return b; | |
| 111 | 2 | } | |
| 112 | |||
| 113 | ///Saves the PNTreeLightNode into a txt file for gnuplot | ||
| 114 | /** @param fs : text file we want to write | ||
| 115 | * @param height : height of the quad to draw | ||
| 116 | * @param pos : position of the current node | ||
| 117 | * @param size : size of the current node | ||
| 118 | * @return true on success, false otherwise | ||
| 119 | */ | ||
| 120 | template<typename T, typename U, unsigned char N> | ||
| 121 | 670 | bool PNTreeLightNode<T, U, N>::saveGnuplotData(std::ofstream & fs, T height, T pos[N], T size[N]){ | |
| 122 | if(N == 2){ | ||
| 123 | 85 | fs << pos[0] << "\t" << pos[1] << "\t" << height << std::endl; | |
| 124 | 85 | fs << (pos[0] + size[0]) << "\t" << pos[1] << "\t" << height << std::endl; | |
| 125 | 85 | fs << (pos[0] + size[0]) << "\t" << (pos[1] + size[1]) << "\t" << height << std::endl; | |
| 126 | 85 | fs << pos[0] << "\t" << (pos[1] + size[1]) << "\t" << height << std::endl; | |
| 127 | 85 | fs << pos[0] << "\t" << pos[1] << "\t" << height << std::endl; | |
| 128 | }else if(N == 3){ | ||
| 129 | 585 | T px0(pos[0]), px1(pos[0] + size[0]); | |
| 130 | 585 | T py0(pos[1]), py1(pos[1] + size[1]); | |
| 131 | 585 | T pz0(pos[2]), pz1(pos[2] + size[2]); | |
| 132 | |||
| 133 | //lower quad | ||
| 134 | 585 | fs << px0 << "\t" << py0 << "\t" << pz0 << std::endl; | |
| 135 | 585 | fs << px1 << "\t" << py0 << "\t" << pz0 << std::endl; | |
| 136 | 585 | fs << px1 << "\t" << py1 << "\t" << pz0 << std::endl; | |
| 137 | 585 | fs << px0 << "\t" << py1 << "\t" << pz0 << std::endl; | |
| 138 | 585 | fs << px0 << "\t" << py0 << "\t" << pz0 << std::endl; | |
| 139 | 585 | fs << std::endl; | |
| 140 | //upper quad | ||
| 141 | 585 | fs << px0 << "\t" << py0 << "\t" << pz1 << std::endl; | |
| 142 | 585 | fs << px1 << "\t" << py0 << "\t" << pz1 << std::endl; | |
| 143 | 585 | fs << px1 << "\t" << py1 << "\t" << pz1 << std::endl; | |
| 144 | 585 | fs << px0 << "\t" << py1 << "\t" << pz1 << std::endl; | |
| 145 | 585 | fs << px0 << "\t" << py0 << "\t" << pz1 << std::endl; | |
| 146 | 585 | fs << std::endl; | |
| 147 | //Lines on Oz axis | ||
| 148 | 585 | fs << px0 << "\t" << py0 << "\t" << pz0 << std::endl; | |
| 149 | 585 | fs << px0 << "\t" << py0 << "\t" << pz1 << std::endl; | |
| 150 | 585 | fs << std::endl; | |
| 151 | 585 | fs << px0 << "\t" << py1 << "\t" << pz0 << std::endl; | |
| 152 | 585 | fs << px0 << "\t" << py1 << "\t" << pz1 << std::endl; | |
| 153 | 585 | fs << std::endl; | |
| 154 | 585 | fs << px1 << "\t" << py1 << "\t" << pz0 << std::endl; | |
| 155 | 585 | fs << px1 << "\t" << py1 << "\t" << pz1 << std::endl; | |
| 156 | 585 | fs << std::endl; | |
| 157 | 585 | fs << px1 << "\t" << py0 << "\t" << pz0 << std::endl; | |
| 158 | 585 | fs << px1 << "\t" << py0 << "\t" << pz1 << std::endl; | |
| 159 | } | ||
| 160 | 670 | fs << std::endl; | |
| 161 |
2/2✓ Branch 0 (117→118) taken 94 times.
✓ Branch 1 (117→127) taken 576 times.
|
670 | if(p_tableChildren != NULL){ |
| 162 | T childSize[N], posChild[N]; | ||
| 163 | 94 | makeHalfSize<T,N>(childSize, size); | |
| 164 |
2/2✓ Branch 0 (125→120) taken 668 times.
✓ Branch 1 (125→126) taken 94 times.
|
762 | for(unsigned char i(0); i < PPower<2, N>::Value; ++i){ |
| 165 |
2/2✓ Branch 0 (122→121) taken 1920 times.
✓ Branch 1 (122→123) taken 668 times.
|
2588 | for(unsigned char k(0); k < N; ++k){ |
| 166 | 1920 | posChild[k] = pos[k] + ((i >> k) & 1)*childSize[k]; | |
| 167 | } | ||
| 168 |
1/1✓ Branch 0 (123→124) taken 668 times.
|
668 | p_tableChildren[i].saveGnuplotData(fs, height + 1, posChild, childSize); |
| 169 | } | ||
| 170 | } | ||
| 171 | 670 | return true; | |
| 172 | } | ||
| 173 | |||
| 174 | ///Clear the PNTreeLightNode content | ||
| 175 | template<typename T, typename U, unsigned char N> | ||
| 176 | 1340 | void PNTreeLightNode<T, U, N>::clear(){ | |
| 177 |
2/2✓ Branch 0 (2→3) taken 94 times.
✓ Branch 1 (2→13) taken 1246 times.
|
1340 | if(p_tableChildren != NULL){ |
| 178 |
2/2✓ Branch 0 (6→4) taken 668 times.
✓ Branch 1 (6→7) taken 94 times.
|
762 | for(unsigned char i(0); i < PPower<2, N>::Value; ++i){ |
| 179 | 668 | PNTreeLightNode<T, U, N> * child = &(p_tableChildren[i]); | |
| 180 | 668 | child->clear(); | |
| 181 | } | ||
| 182 |
3/4✓ Branch 0 (7→8) taken 94 times.
✗ Branch 1 (7→12) not taken.
✓ Branch 2 (9→10) taken 668 times.
✓ Branch 3 (9→11) taken 94 times.
|
762 | delete [] p_tableChildren; |
| 183 | 94 | p_tableChildren = NULL; | |
| 184 | } | ||
| 185 | 1340 | p_data = NULL; | |
| 186 | 1340 | } | |
| 187 | |||
| 188 | ///Get the data of the last node in the N tree | ||
| 189 | /** @param posData : position of the data | ||
| 190 | * @param pos : position of the current node | ||
| 191 | * @param size : size of the current node | ||
| 192 | * @return data of the last node in the N tree | ||
| 193 | */ | ||
| 194 | template<typename T, typename U, unsigned char N> | ||
| 195 | 8 | const U * PNTreeLightNode<T, U, N>::getLastData(const T * posData, const T pos[N], const T size[N]) const{ | |
| 196 |
2/2✓ Branch 0 (2→3) taken 2 times.
✓ Branch 1 (2→6) taken 6 times.
|
8 | if(p_tableChildren == NULL){ |
| 197 |
1/2✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 2 times.
|
2 | if(p_data == NULL) return NULL; |
| 198 | 2 | else return p_data; | |
| 199 | }else{ | ||
| 200 | T childPos[N]; | ||
| 201 | 6 | const PNTreeLightNode<T, U, N> * child = getChildFromPos(childPos, posData, pos, size); | |
| 202 |
1/2✗ Branch 0 (7→8) not taken.
✓ Branch 1 (7→9) taken 6 times.
|
6 | if(child == NULL) return NULL; |
| 203 | else{ | ||
| 204 | T childSize[N]; | ||
| 205 | 6 | makeHalfSize<T,N>(childSize, size); | |
| 206 |
1/1✓ Branch 0 (10→11) taken 6 times.
|
6 | return child->getLastData(posData, pos, childSize); |
| 207 | } | ||
| 208 | } | ||
| 209 | } | ||
| 210 | |||
| 211 | ///Get the distance between two points | ||
| 212 | /** @param posA : first position | ||
| 213 | * @param posB : second position | ||
| 214 | * @return distance between posA and posB | ||
| 215 | */ | ||
| 216 | template<typename T, unsigned char N> | ||
| 217 | T getDistanceFromData(const T posA[N], const T posB[N]){ | ||
| 218 | T res = 0.0, x; | ||
| 219 | for(unsigned char i(0); i < N; ++i){ | ||
| 220 | x = posA[i] - posB[i]; | ||
| 221 | res += x*x; | ||
| 222 | } | ||
| 223 | return sqrt(res); | ||
| 224 | } | ||
| 225 | |||
| 226 | ///Get the index of the check neighbours tab | ||
| 227 | /** @param indexChild : index of the reference cell | ||
| 228 | * @param currentChildIndex : index of the current node to be checked | ||
| 229 | * @return index of the neighbours to be checked in the neighbours table | ||
| 230 | */ | ||
| 231 | template<unsigned char N> | ||
| 232 | unsigned int getNeighbourCellIndex(unsigned char indexChild[N], unsigned char currentChildIndex[N]){ | ||
| 233 | unsigned int index(0u), base(1u), tmp; | ||
| 234 | for(unsigned char i(N); i < N; ++i){ | ||
| 235 | tmp = 0u; | ||
| 236 | if(indexChild[i] > currentChildIndex[i]){ | ||
| 237 | tmp = 2u; | ||
| 238 | }else if(indexChild[i] == currentChildIndex[i]){ | ||
| 239 | tmp = 1u; | ||
| 240 | } | ||
| 241 | index += base*tmp; | ||
| 242 | base *= 3u; | ||
| 243 | } | ||
| 244 | return index; | ||
| 245 | } | ||
| 246 | |||
| 247 | ///Get the closer data from the given position posData | ||
| 248 | /** @param[out] closerData : pointer to the closer data found | ||
| 249 | * @param[out] distFromCloserData : distance from the closer data to the search position posData | ||
| 250 | * @param[out] tabIsNeighbourChecked : table of the checked neighbours (true), or unchecked neighbours (false) | ||
| 251 | * @param nbNeighbour : size of the table of neighbours | ||
| 252 | * @param posData : position used to search the closer data | ||
| 253 | * @param pos : position of the current node | ||
| 254 | * @param size : size of the current node | ||
| 255 | * @return true if the closer data has been found, false if the parent needs to keep searching | ||
| 256 | */ | ||
| 257 | template<typename T, typename U, unsigned char N> | ||
| 258 | bool PNTreeLightNode<T, U, N>::getCloserData(U*& closerData, T & distFromCloserData, bool * tabIsNeighbourChecked, unsigned int nbNeighbour, | ||
| 259 | const T * posData, const T pos[N], const T size[N]) const | ||
| 260 | { | ||
| 261 | if(p_tableChildren == NULL){ //If the node has no child | ||
| 262 | if(p_data == NULL) return false; //If the node has no data | ||
| 263 | else{ //If the node has data | ||
| 264 | if(closerData == NULL){ | ||
| 265 | closerData = p_data; | ||
| 266 | distFromCloserData = getDistanceFromData<T,N>(p_posData, posData); | ||
| 267 | return true; | ||
| 268 | }else{ | ||
| 269 | T dist = getDistanceFromData<T,N>(p_posData, posData); | ||
| 270 | if(dist < distFromCloserData){ | ||
| 271 | distFromCloserData = dist; | ||
| 272 | closerData = p_data; | ||
| 273 | } | ||
| 274 | return false; | ||
| 275 | } | ||
| 276 | } | ||
| 277 | }else{ //If the node has children | ||
| 278 | T childPos[N]; | ||
| 279 | const PNTreeLightNode<T, U, N> * child = getChildFromPos(childPos, posData, pos, size); | ||
| 280 | if(child == NULL) return false; | ||
| 281 | else{ | ||
| 282 | T childSize[N]; | ||
| 283 | makeHalfSize<T,N>(childSize, size); | ||
| 284 | bool b = child->getCloserData(closerData, distFromCloserData, tabIsNeighbourChecked, nbNeighbour, posData, childPos, childSize); | ||
| 285 | if(b) return true; | ||
| 286 | else{ | ||
| 287 | unsigned char indexChild[N], currentChildIndex[N]; | ||
| 288 | T currentChildPos[N]; | ||
| 289 | getIndexOfChildFromPos(indexChild, posData, pos, size); | ||
| 290 | unsigned char fullIndexChild(getFullIndexChild(indexChild)); | ||
| 291 | |||
| 292 | for(unsigned char i(0); i < PPower<2, N>::Value; ++i){ | ||
| 293 | if(i == fullIndexChild) continue; | ||
| 294 | for(unsigned char j(0); j < N; ++j){ | ||
| 295 | currentChildIndex[j] = (i >> j) & 1; | ||
| 296 | currentChildPos[j] = pos[j] + ((T)currentChildIndex[j])*childSize[j]; | ||
| 297 | } | ||
| 298 | unsigned int indexCurrentNeighbour(getNeighbourCellIndex<N>(indexChild, currentChildIndex)); | ||
| 299 | //If the neighbours is already checked, skip it | ||
| 300 | if(tabIsNeighbourChecked[indexCurrentNeighbour]) continue; | ||
| 301 | //If the neighbours is not check yet, check it and write it in the tabIsNeighbourChecked | ||
| 302 | tabIsNeighbourChecked[indexCurrentNeighbour] = true; | ||
| 303 | if(child->getCloserData(closerData, distFromCloserData, tabIsNeighbourChecked, nbNeighbour, | ||
| 304 | posData, currentChildPos, childSize)) | ||
| 305 | { | ||
| 306 | return true; | ||
| 307 | } | ||
| 308 | } | ||
| 309 | if(isNeighbourSearchFinised(tabIsNeighbourChecked, nbNeighbour)) return true; | ||
| 310 | return false; | ||
| 311 | } | ||
| 312 | } | ||
| 313 | } | ||
| 314 | } | ||
| 315 | |||
| 316 | ///Get the child of the PNTreeLightNode with a position | ||
| 317 | /** @param[out] childPos : position of the child | ||
| 318 | * @param posData : position of the data | ||
| 319 | * @param pos : position of the current node | ||
| 320 | * @param size : size of the current node | ||
| 321 | * @return child of the current PNTreeLightNode which contains the position (pos) | ||
| 322 | */ | ||
| 323 | template<typename T, typename U, unsigned char N> | ||
| 324 | 6 | const PNTreeLightNode<T, U, N> * PNTreeLightNode<T, U, N>::getChildFromPos(T childPos[N], const T * posData, const T pos[N], const T size[N]) const{ | |
| 325 |
1/2✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 6 times.
|
6 | if(p_tableChildren == NULL) return NULL; |
| 326 | 6 | unsigned char posChild(0), base(1); | |
| 327 | bool cond; | ||
| 328 |
2/2✓ Branch 0 (6→5) taken 15 times.
✓ Branch 1 (6→7) taken 6 times.
|
21 | for(unsigned char j(0); j < N; ++j){ |
| 329 | 15 | cond = ((posData[j] - pos[j]) > size[j]*0.5); | |
| 330 | 15 | childPos[j] = pos[j] + cond*size[j]*0.5; | |
| 331 | 15 | posChild += cond*base; | |
| 332 | 15 | base *= 2; //on poura faire du décalage de bit plus tard | |
| 333 | } | ||
| 334 |
1/2✗ Branch 0 (7→8) not taken.
✓ Branch 1 (7→9) taken 6 times.
|
6 | if(posChild >= PPower<2, N>::Value) return NULL; |
| 335 | 6 | else return &(p_tableChildren[posChild]); | |
| 336 | } | ||
| 337 | |||
| 338 | ///Get the child of the PNTreeLightNode with a position | ||
| 339 | /** @param[out] childPos : position of the child | ||
| 340 | * @param posData : position of the data | ||
| 341 | * @param pos : position of the current node | ||
| 342 | * @param size : size of the current node | ||
| 343 | * @return child of the current PNTreeLightNode which contains the position (pos) | ||
| 344 | */ | ||
| 345 | template<typename T, typename U, unsigned char N> | ||
| 346 | 1728 | PNTreeLightNode<T, U, N> * PNTreeLightNode<T, U, N>::getChildFromPos(T childPos[N], const T * posData, const T pos[N], const T size[N]){ | |
| 347 |
1/2✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 1728 times.
|
1728 | if(p_tableChildren == NULL) return NULL; |
| 348 | 1728 | unsigned char posChild(0), base(1); | |
| 349 | bool cond; | ||
| 350 |
2/2✓ Branch 0 (6→5) taken 4992 times.
✓ Branch 1 (6→7) taken 1728 times.
|
6720 | for(unsigned char j(0); j < N; ++j){ |
| 351 | 4992 | cond = ((posData[j] - pos[j]) > size[j]*0.5); | |
| 352 | 4992 | childPos[j] = pos[j] + cond*size[j]*0.5; | |
| 353 | 4992 | posChild += cond*base; | |
| 354 | 4992 | base *= 2; //on poura faire du décalage de bit plus tard | |
| 355 | } | ||
| 356 |
1/2✗ Branch 0 (7→8) not taken.
✓ Branch 1 (7→9) taken 1728 times.
|
1728 | if(posChild >= PPower<2, N>::Value) return NULL; |
| 357 | else{ | ||
| 358 | // std::cerr << "PNTreeLightNode<T, U, N>::getChildFromPos : posChild = " << ((int)posChild) << std::endl; | ||
| 359 | 1728 | return &(p_tableChildren[posChild]); | |
| 360 | } | ||
| 361 | } | ||
| 362 | |||
| 363 | ///Get the index of the child position by respect to the position pos | ||
| 364 | /** @param[out] index : vector of the position of the child | ||
| 365 | * @param posData : position used to get the child | ||
| 366 | * @param pos : position of the current node | ||
| 367 | * @param size : size of the current node | ||
| 368 | */ | ||
| 369 | template<typename T, typename U, unsigned char N> | ||
| 370 | void PNTreeLightNode<T, U, N>::getIndexOfChildFromPos(unsigned char index[N], const T * posData, const T pos[N], const T size[N]) const{ | ||
| 371 | if(p_tableChildren == NULL) return; | ||
| 372 | for(unsigned char j(0lu); j < N; ++j){ | ||
| 373 | index[j] = ((posData[j] - pos[j]) > size[j]*0.5); | ||
| 374 | } | ||
| 375 | } | ||
| 376 | |||
| 377 | ///Get the index of the child position by respect to the position pos | ||
| 378 | /** @param[out] index : vector of the position of the child | ||
| 379 | * @param posData : position used to get the child | ||
| 380 | * @param pos : position of the current node | ||
| 381 | * @param size : size of the current node | ||
| 382 | */ | ||
| 383 | template<typename T, typename U, unsigned char N> | ||
| 384 | void PNTreeLightNode<T, U, N>::getIndexOfChildFromPos(unsigned char index[N], T * posData, T pos[N], T size[N]){ | ||
| 385 | if(p_tableChildren == NULL) return; | ||
| 386 | for(unsigned char j(0); j < N; ++j){ | ||
| 387 | index[j] = ((posData[j] - pos[j]) > size[j]*0.5); | ||
| 388 | } | ||
| 389 | } | ||
| 390 | |||
| 391 | ///Get the full index position of a child | ||
| 392 | /** @param index : vector of index position of a child | ||
| 393 | * @return full index position of a child | ||
| 394 | */ | ||
| 395 | template<typename T, typename U, unsigned char N> | ||
| 396 | unsigned char PNTreeLightNode<T, U, N>::getFullIndexChild(unsigned char index[N]) const{ | ||
| 397 | unsigned char posChild(0), base(1); | ||
| 398 | for(unsigned char j(0); j < N; ++j){ | ||
| 399 | posChild += (index[j])*base; | ||
| 400 | base *= 2; //on poura faire du décalage de bit plus tard | ||
| 401 | } | ||
| 402 | return posChild; | ||
| 403 | } | ||
| 404 | |||
| 405 | ///Returns the data position | ||
| 406 | /** @return data position | ||
| 407 | */ | ||
| 408 | template<typename T, typename U, unsigned char N> | ||
| 409 | const T * PNTreeLightNode<T, U, N>::getDataPos() const{return p_posData;} | ||
| 410 | |||
| 411 | ///Returns the data position | ||
| 412 | /** @return data position | ||
| 413 | */ | ||
| 414 | template<typename T, typename U, unsigned char N> | ||
| 415 | T * PNTreeLightNode<T, U, N>::getDataPos(){return p_posData;} | ||
| 416 | |||
| 417 | ///Returns the table of children of the PNTreeLightNode | ||
| 418 | /** @return table of children of the PNTreeLightNode | ||
| 419 | */ | ||
| 420 | template<typename T, typename U, unsigned char N> | ||
| 421 | const PNTreeLightNode<T, U, N> * PNTreeLightNode<T, U, N>::getTabChildren() const{return p_tableChildren;} | ||
| 422 | |||
| 423 | ///Returns the table of children of the PNTreeLightNode | ||
| 424 | /** @return table of children of the PNTreeLightNode | ||
| 425 | */ | ||
| 426 | template<typename T, typename U, unsigned char N> | ||
| 427 | PNTreeLightNode<T, U, N> * PNTreeLightNode<T, U, N>::getTabChildren(){return p_tableChildren;} | ||
| 428 | |||
| 429 | ///Returns the child of the PNTreeLightNode | ||
| 430 | /** @param childId : id of the child we want to have | ||
| 431 | * @return pointer to the child or NULL if there is not | ||
| 432 | */ | ||
| 433 | template<typename T, typename U, unsigned char N> | ||
| 434 | const PNTreeLightNode<T, U, N> * PNTreeLightNode<T, U, N>::getChild(unsigned char childId) const{ | ||
| 435 | if(p_tableChildren == NULL || childId >= PPower<2, N>::Value) return NULL; | ||
| 436 | return &(p_tableChildren[childId]); | ||
| 437 | } | ||
| 438 | |||
| 439 | ///Returns the child of the PNTreeLightNode | ||
| 440 | /** @param childId : id of the child we want to have | ||
| 441 | * @return pointer to the child or NULL if there is not | ||
| 442 | */ | ||
| 443 | template<typename T, typename U, unsigned char N> | ||
| 444 | PNTreeLightNode<T, U, N> * PNTreeLightNode<T, U, N>::getChild(unsigned char childId){ | ||
| 445 | if(p_tableChildren == NULL || childId >= PPower<2, N>::Value) return NULL; | ||
| 446 | return &(p_tableChildren[childId]); | ||
| 447 | } | ||
| 448 | |||
| 449 | ///Copy function of PNTreeLightNode | ||
| 450 | /** @param other : class to copy | ||
| 451 | */ | ||
| 452 | template<typename T, typename U, unsigned char N> | ||
| 453 | void PNTreeLightNode<T, U, N>::copyPNTreeLightNode(const PNTreeLightNode<T, U, N> & other){ | ||
| 454 | |||
| 455 | } | ||
| 456 | |||
| 457 | ///Split the PNTreeLightNode | ||
| 458 | /** @param pos : position of the current node | ||
| 459 | * @param size : size of the current node | ||
| 460 | * @param sizeLimit : limit of the cell size | ||
| 461 | * @return true on success, false otherwise | ||
| 462 | */ | ||
| 463 | template<typename T, typename U, unsigned char N> | ||
| 464 | 94 | bool PNTreeLightNode<T, U, N>::split(const T pos[N], const T size[N], T sizeLimit){ | |
| 465 |
2/4✓ Branch 0 (2→3) taken 94 times.
✗ Branch 1 (2→4) not taken.
✗ Branch 2 (3→4) not taken.
✓ Branch 3 (3→7) taken 94 times.
|
94 | if(p_tableChildren != NULL || p_data == NULL){ |
| 466 | ✗ | std::cerr << "PNTreeLightNode<T, U, N>::split() : current node already split" << std::endl; | |
| 467 | ✗ | return false; | |
| 468 | } | ||
| 469 | // std::cerr << "PNTreeLightNode<T, U, N>::split() : begin" << std::endl; | ||
| 470 | T halfSizeChild[N]; | ||
| 471 | 94 | makeHalfSize<T, N>(halfSizeChild, size); | |
| 472 |
1/2✗ Branch 0 (9→10) not taken.
✓ Branch 1 (9→11) taken 94 times.
|
94 | if(!checkSizeLimitLight<T, N>(halfSizeChild, sizeLimit)){ |
| 473 | // std::cerr << "PNTreeLightNode<T, U, N>::split : can't split more, child sizes less than " << sizeLimit << std::endl; | ||
| 474 | ✗ | return false; | |
| 475 | } | ||
| 476 | 94 | unsigned char nbChildren(PPower<2, N>::Value); | |
| 477 |
6/18✓ Branch 0 (11→12) taken 94 times.
✗ Branch 1 (11→13) not taken.
✓ Branch 2 (14→15) taken 94 times.
✓ Branch 4 (16→17) taken 668 times.
✓ Branch 6 (18→16) taken 668 times.
✓ Branch 7 (18→19) taken 94 times.
✗ Branch 8 (19→20) not taken.
✓ Branch 9 (19→24) taken 94 times.
✗ Branch 10 (20→21) not taken.
✗ Branch 11 (20→22) not taken.
✗ Branch 12 (34→35) not taken.
✗ Branch 13 (34→38) not taken.
✗ Branch 14 (36→37) not taken.
✗ Branch 15 (36→38) not taken.
✗ Branch 16 (39→40) not taken.
✗ Branch 17 (39→44) not taken.
✗ Branch 18 (40→41) not taken.
✗ Branch 19 (40→42) not taken.
|
762 | p_tableChildren = new PNTreeLightNode<T, U, N>[nbChildren]; |
| 478 |
2/2✓ Branch 0 (26→25) taken 668 times.
✓ Branch 1 (26→27) taken 94 times.
|
762 | for(unsigned char i(0); i < nbChildren; ++i){ |
| 479 | 668 | PNTreeLightNode<T, U, N> * child = &(p_tableChildren[i]); | |
| 480 | 668 | child->p_tableChildren = NULL; | |
| 481 | 668 | child->p_data = NULL; | |
| 482 | 668 | child->p_posData = NULL; | |
| 483 | } | ||
| 484 | // std::cerr << "PNTreeLightNode<T, U, N>::split : replace child" << std::endl; | ||
| 485 | T childPos[N]; | ||
| 486 | 94 | PNTreeLightNode<T, U, N> * child = getChildFromPos(childPos, p_posData, pos, size); | |
| 487 | 94 | bool b = true;; | |
| 488 |
1/2✗ Branch 0 (28→29) not taken.
✓ Branch 1 (28→30) taken 94 times.
|
94 | if(child == NULL) return false; |
| 489 | else{ | ||
| 490 |
1/1✓ Branch 0 (30→31) taken 94 times.
|
94 | b = child->addElement(p_posData, p_data, childPos, halfSizeChild, sizeLimit); |
| 491 | } | ||
| 492 | 94 | p_data = NULL; | |
| 493 | 94 | p_posData = NULL; | |
| 494 | 94 | return b; | |
| 495 | } | ||
| 496 | |||
| 497 | ///Initialisation function of the class PNTreeLightNode | ||
| 498 | template<typename T, typename U, unsigned char N> | ||
| 499 | 670 | void PNTreeLightNode<T, U, N>::initialisationPNTreeLightNode(){ | |
| 500 | 670 | p_posData = NULL; | |
| 501 | 670 | p_data = NULL; | |
| 502 | 670 | p_tableChildren = NULL; | |
| 503 | 670 | } | |
| 504 | |||
| 505 | |||
| 506 | |||
| 507 | |||
| 508 | |||
| 509 | #endif | ||
| 510 | |||
| 511 | |||
| 512 | |||
| 513 |