[688] | 1 | #include <cassert> |
---|
| 2 | #include "tree.hpp" |
---|
| 3 | #include "node.hpp" |
---|
| 4 | #include "elt.hpp" |
---|
| 5 | #include <iostream> |
---|
[694] | 6 | #include "mpi.hpp" |
---|
[688] | 7 | #include <stdlib.h> /* srand, rand */ |
---|
| 8 | #include <time.h> /* time */ |
---|
| 9 | #include <vector> |
---|
[923] | 10 | #include <list> |
---|
[688] | 11 | #include <set> |
---|
| 12 | |
---|
| 13 | #include "timer.hpp" |
---|
| 14 | #include "mpi_routing.hpp" |
---|
| 15 | |
---|
| 16 | namespace sphereRemap { |
---|
| 17 | |
---|
[951] | 18 | const int MAX_LEVEL_SIZE = 100; |
---|
[688] | 19 | |
---|
| 20 | double cputime(); |
---|
| 21 | using namespace std; |
---|
| 22 | |
---|
[923] | 23 | /* |
---|
[688] | 24 | CBasicTree::CBasicTree() : ri(0), levelSize(MAX_LEVEL_SIZE), root(NULL) |
---|
| 25 | { |
---|
| 26 | } |
---|
[923] | 27 | */ |
---|
[688] | 28 | |
---|
| 29 | void CBasicTree::routeNodes(vector<int>& route, vector<Node>& nodes, int assignLevel) |
---|
| 30 | { |
---|
| 31 | for (int i = 0; i < nodes.size(); i++) |
---|
| 32 | { |
---|
| 33 | root->routeNode(&nodes[i], assignLevel); |
---|
| 34 | route[i] = nodes[i].route; |
---|
| 35 | } |
---|
| 36 | } |
---|
| 37 | |
---|
| 38 | void CBasicTree::routeIntersections(vector<vector<int> >& routes, vector<Node>& nodes) |
---|
| 39 | { |
---|
| 40 | for (int i = 0; i < nodes.size(); i++) |
---|
| 41 | root->routeIntersection(routes[i], &nodes[i]); |
---|
| 42 | } |
---|
| 43 | |
---|
| 44 | void CBasicTree::build(vector<Node>& nodes) |
---|
| 45 | { |
---|
| 46 | newRoot(1); |
---|
| 47 | insertNodes(nodes); |
---|
| 48 | } |
---|
| 49 | |
---|
| 50 | void CBasicTree::output(ostream& flux, int level) |
---|
| 51 | { |
---|
| 52 | root->output(flux,level,0) ; |
---|
| 53 | } |
---|
| 54 | void CBasicTree::slim(int nbIts) |
---|
| 55 | { |
---|
| 56 | for (int i = 0; i < nbIts; i++) |
---|
| 57 | { |
---|
| 58 | for (int level = root->level - 1; level > 0; level--) |
---|
| 59 | { |
---|
| 60 | slim2(root, level); |
---|
| 61 | ri = 0; |
---|
| 62 | emptyPool(); |
---|
| 63 | } |
---|
| 64 | |
---|
| 65 | for (int level = 2; level < root->level; level++) |
---|
| 66 | { |
---|
| 67 | slim2(root, level); |
---|
| 68 | ri = 0; |
---|
| 69 | emptyPool(); |
---|
| 70 | } |
---|
| 71 | } |
---|
| 72 | } |
---|
| 73 | |
---|
[923] | 74 | |
---|
| 75 | |
---|
[688] | 76 | void CBasicTree::insertNode(NodePtr node) |
---|
| 77 | { |
---|
| 78 | node->tree = this; |
---|
| 79 | increaseLevelSize(0); |
---|
| 80 | push_back(node); |
---|
| 81 | |
---|
| 82 | NodePtr q; |
---|
| 83 | while (pool.size()) |
---|
| 84 | { |
---|
| 85 | q = pool.front(); |
---|
| 86 | pool.pop_front(); |
---|
| 87 | q = insert(q, root); |
---|
| 88 | if (ri) |
---|
| 89 | { |
---|
| 90 | delete q; |
---|
| 91 | ri = 0; |
---|
| 92 | } |
---|
| 93 | } |
---|
| 94 | } |
---|
| 95 | |
---|
| 96 | void CBasicTree::emptyPool(void) |
---|
| 97 | { |
---|
| 98 | while (pool.size()) |
---|
| 99 | { |
---|
| 100 | NodePtr q = pool.front(); |
---|
| 101 | pool.pop_front(); |
---|
| 102 | q = insert(q, root); |
---|
| 103 | if (ri) |
---|
| 104 | { |
---|
| 105 | delete q; |
---|
| 106 | ri = 0; |
---|
| 107 | } |
---|
| 108 | } |
---|
| 109 | } |
---|
| 110 | |
---|
| 111 | void CBasicTree::push_back(NodePtr node) |
---|
| 112 | { |
---|
| 113 | #ifdef DEBUG |
---|
| 114 | node->parent = NULL; // will be overridden later, but for mem leak check better trigger leak as soon as possible |
---|
| 115 | #endif |
---|
| 116 | pool.push_back(node); |
---|
| 117 | } |
---|
| 118 | |
---|
| 119 | void CBasicTree::push_front(NodePtr node) |
---|
| 120 | { |
---|
| 121 | #ifdef DEBUG |
---|
| 122 | node->parent = NULL; // will be overridden later, but for mem leak check better trigger leak as soon as possible |
---|
| 123 | #endif |
---|
| 124 | pool.push_front(node); |
---|
| 125 | } |
---|
| 126 | |
---|
| 127 | void CBasicTree::increaseLevelSize(int level) |
---|
| 128 | { |
---|
| 129 | levelSize[level]++; |
---|
| 130 | } |
---|
| 131 | |
---|
| 132 | void CBasicTree::decreaseLevelSize(int level) |
---|
| 133 | { |
---|
| 134 | levelSize[level]--; |
---|
| 135 | } |
---|
| 136 | |
---|
| 137 | void CBasicTree::newRoot(int level) // newroot <- root |
---|
| 138 | { |
---|
| 139 | root = new Node; |
---|
[923] | 140 | // if (level > 1) cout << " newRoot level " << level << endl; |
---|
[688] | 141 | root->level = level; |
---|
| 142 | root->parent = 0; |
---|
| 143 | root->leafCount = 0; |
---|
| 144 | root->centre = ORIGIN; |
---|
| 145 | root->radius = 0.; |
---|
| 146 | root->reinserted = false; |
---|
| 147 | root->updateCount = 0; |
---|
| 148 | root->tree = this; |
---|
| 149 | levelSize[level]++; |
---|
| 150 | } |
---|
| 151 | |
---|
| 152 | CBasicTree::~CBasicTree() |
---|
| 153 | { |
---|
| 154 | //FIXME uncomment the next line and figure out why it segfault sometimes |
---|
| 155 | //root->free_descendants(); // recursively deletes all nodes in the tree |
---|
| 156 | if (root) delete root; |
---|
| 157 | } |
---|
| 158 | |
---|
| 159 | void CTree::insertNodes(vector<Node>& nodes) |
---|
| 160 | { |
---|
| 161 | int stepSlim = MAX_NODE_SZ*MAX_NODE_SZ*2; |
---|
| 162 | const double ratio = 1.5; |
---|
| 163 | for (int i = 0; i < nodes.size(); i++) |
---|
| 164 | { |
---|
| 165 | insertNode(&nodes[i]); |
---|
| 166 | |
---|
| 167 | if (root->leafCount > stepSlim) // time for slim down |
---|
| 168 | { |
---|
| 169 | slim(); |
---|
| 170 | stepSlim = stepSlim * ratio; |
---|
| 171 | } |
---|
| 172 | } |
---|
| 173 | } |
---|
| 174 | |
---|
| 175 | |
---|
| 176 | void CSampleTree::insertNodes(vector<Node>& nodes) |
---|
| 177 | { |
---|
| 178 | bool first1 = true; |
---|
| 179 | bool first2 = true; |
---|
| 180 | int stepSlim = MAX_NODE_SZ * MAX_NODE_SZ * keepNodes / 4; |
---|
| 181 | // double ratio = 1 + (0.5 * (1 - (keepNodes - 1) / (1.0 * keepNodes))) ; |
---|
| 182 | double ratio = 1.5 ; |
---|
| 183 | int i ; |
---|
| 184 | |
---|
[923] | 185 | // cout<<"CSampleTree::insertNodes : nb node to be inserted : "<<nodes.size()<<endl ; |
---|
[688] | 186 | for (i = 0; i < nodes.size(); i++) |
---|
| 187 | { |
---|
| 188 | insertNode(&nodes[i]); |
---|
| 189 | |
---|
| 190 | if (root->leafCount > stepSlim && levelSize[assignLevel] < keepNodes-2) // time for slim down |
---|
| 191 | { |
---|
| 192 | slim(); |
---|
| 193 | stepSlim = stepSlim * ratio; |
---|
| 194 | } |
---|
| 195 | |
---|
| 196 | |
---|
| 197 | if (levelSize[assignLevel] == keepNodes-2 && first1) |
---|
| 198 | { |
---|
| 199 | slim(); |
---|
| 200 | first1 = false; |
---|
| 201 | } |
---|
| 202 | |
---|
| 203 | if (levelSize[assignLevel] == keepNodes-1 && first2) |
---|
| 204 | { |
---|
| 205 | slim(); |
---|
| 206 | first2=false ; |
---|
| 207 | } |
---|
| 208 | |
---|
[923] | 209 | if (levelSize[assignLevel] >= keepNodes) slim(); |
---|
| 210 | if (levelSize[assignLevel] > keepNodes) slim(); |
---|
| 211 | if (levelSize[assignLevel] > keepNodes) slimAssignedLevel() ; |
---|
| 212 | |
---|
| 213 | if (levelSize[assignLevel] >= keepNodes) |
---|
[688] | 214 | { |
---|
[923] | 215 | if (levelSize[assignLevel] > keepNodes) |
---|
| 216 | { |
---|
| 217 | // cout<<"assign Level : "<<assignLevel<< " levelSize[assignLevel] :"<<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<endl ; |
---|
| 218 | removeExtraNode() ; |
---|
| 219 | } |
---|
[688] | 220 | break ; |
---|
| 221 | } |
---|
| 222 | } |
---|
[923] | 223 | // cout << "SampleTree build : nb Node inserted : " << i << endl; |
---|
[688] | 224 | |
---|
| 225 | } |
---|
| 226 | |
---|
[923] | 227 | void CSampleTree::slimAssignedLevel() |
---|
| 228 | { |
---|
| 229 | for(int i=MIN_NODE_SZ;i<=MAX_NODE_SZ;i++) |
---|
| 230 | { |
---|
| 231 | int levelSizeOrigin=levelSize[assignLevel] ; |
---|
| 232 | slim2(root, assignLevel,i); |
---|
| 233 | ri = 0; |
---|
| 234 | int levelSizeBefore=levelSize[assignLevel] ; |
---|
| 235 | isActiveOkSplit=true ; |
---|
| 236 | emptyPool(); |
---|
| 237 | // cout<<"assign Level : "<<assignLevel<<" MinNodeSize :"<<i<< " levelSize[assignLevel] : "<<levelSizeOrigin<<"->"<<levelSizeBefore<<"->" <<levelSize[assignLevel]<<" keepNodes : "<<keepNodes<<" "<<"CanSplit " <<canSplit()<<endl ; |
---|
| 238 | if (levelSize[assignLevel]<=keepNodes) break ; |
---|
| 239 | } |
---|
| 240 | |
---|
[688] | 241 | } |
---|
[923] | 242 | |
---|
| 243 | void CSampleTree::removeExtraNode(void) |
---|
| 244 | { |
---|
| 245 | std::list<NodePtr> nodeList ; |
---|
| 246 | std::list<NodePtr>::iterator it1,it2, rm ; |
---|
| 247 | |
---|
| 248 | root->getNodeLevel(assignLevel,nodeList) ; |
---|
| 249 | double dist,minDist ; |
---|
| 250 | |
---|
| 251 | |
---|
| 252 | for (int n=0; n<levelSize[assignLevel]-keepNodes ; ++n) |
---|
| 253 | { |
---|
| 254 | minDist=-1 ; |
---|
| 255 | for(it1=nodeList.begin();it1!=nodeList.end();++it1) |
---|
| 256 | { |
---|
| 257 | dist=0 ; |
---|
| 258 | for(it2=nodeList.begin();it2!=nodeList.end();++it2) dist+=arcdist((*it1)->centre,(*it2)->centre) ; |
---|
| 259 | if (minDist > dist || minDist < 0.) |
---|
| 260 | { |
---|
| 261 | minDist=dist ; |
---|
| 262 | rm=it1 ; |
---|
| 263 | } |
---|
| 264 | } |
---|
| 265 | (*rm)->toDelete=true ; |
---|
| 266 | nodeList.erase(rm) ; |
---|
| 267 | |
---|
| 268 | } |
---|
| 269 | root->removeDeletedNodes(assignLevel) ; |
---|
| 270 | isActiveOkSplit=true ; |
---|
| 271 | emptyPool(); |
---|
| 272 | } |
---|
| 273 | |
---|
| 274 | } |
---|