source: XIOS/dev/dev_olga/extern/remap/src/tree.cpp @ 1158

Last change on this file since 1158 was 1158, checked in by oabramkina, 4 years ago

Two server levels: merging with trunk r1137.
There are bugs.

File size: 5.7 KB
Line 
1#include <cassert>
2#include "tree.hpp"
3#include "node.hpp"
4#include "elt.hpp"
5#include <iostream>
6#include "mpi.hpp"
7#include <stdlib.h>     /* srand, rand */
8#include <time.h>       /* time */
9#include <vector>
10#include <list>
11#include <set>
12
13#include "timer.hpp"
14#include "mpi_routing.hpp"
15
16namespace sphereRemap {
17
18const int MAX_LEVEL_SIZE = 100;
19
20double cputime();
21using namespace std;
22
23/*
24CBasicTree::CBasicTree() : ri(0), levelSize(MAX_LEVEL_SIZE), root(NULL)
25{
26}
27*/
28
29void 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
38void 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
44void CBasicTree::build(vector<Node>& nodes)
45{
46        newRoot(1);
47        insertNodes(nodes);
48}
49
50void CBasicTree::output(ostream& flux, int level)
51{
52        root->output(flux,level,0) ;
53}
54void 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
74
75
76void 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
96void 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
111void 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
119void 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
127void CBasicTree::increaseLevelSize(int level)
128{
129        levelSize[level]++;
130}
131
132void CBasicTree::decreaseLevelSize(int level)
133{
134        levelSize[level]--;
135}
136
137void CBasicTree::newRoot(int level)  // newroot <- root
138{
139        root = new Node;
140        // if (level > 1) cout << " newRoot level " << level << endl;
141        root->level = level;
142        root->parent = 0;
143        root->leafCount = 0;
144// initialize root node on the sphere
145  root->centre.x=1 ; root->centre.y=0 ; root->centre.z=0 ; 
146        root->radius = 0.;
147        root->reinserted = false;
148        root->updateCount = 0;
149        root->tree = this;
150        levelSize[level]++;
151}
152
153CBasicTree::~CBasicTree()
154{
155        //FIXME uncomment the next line and figure out why it segfault sometimes
156        //root->free_descendants(); // recursively deletes all nodes in the tree
157        if (root) delete root;
158}
159
160void CTree::insertNodes(vector<Node>& nodes)
161{
162        int stepSlim = MAX_NODE_SZ*MAX_NODE_SZ*2;
163        const double ratio = 1.5;
164        for (int i = 0; i < nodes.size(); i++)
165        {
166                insertNode(&nodes[i]);
167
168                if (root->leafCount > stepSlim) // time for slim down
169                {
170                        slim();
171                        stepSlim = stepSlim * ratio;
172                }
173        }
174}
175
176
177void CSampleTree::insertNodes(vector<Node>& nodes)
178{
179        bool first1 = true;
180        bool first2 = true;
181        int stepSlim = MAX_NODE_SZ * MAX_NODE_SZ * keepNodes / 4;
182//      double ratio = 1 + (0.5 * (1 - (keepNodes - 1) / (1.0 * keepNodes))) ;
183        double ratio = 1.5 ;
184  int i ;
185 
186//  cout<<"CSampleTree::insertNodes  : nb node to be inserted : "<<nodes.size()<<endl ;
187  for (i = 0; i < nodes.size(); i++)
188        {
189    insertNode(&nodes[i]);
190
191                if (root->leafCount > stepSlim && levelSize[assignLevel] < keepNodes-2) // time for slim down
192                {
193                        slim();
194                        stepSlim = stepSlim * ratio;
195                }
196
197   
198    if (levelSize[assignLevel] == keepNodes-2 && first1)
199                {
200      slim();
201                        first1 = false;
202                }
203
204                if (levelSize[assignLevel] == keepNodes-1 && first2)
205                {
206      slim();
207      first2=false ;
208                }
209
210        if (levelSize[assignLevel] >= keepNodes) slim();
211        if (levelSize[assignLevel] > keepNodes) slim();
212    if (levelSize[assignLevel] > keepNodes) slimAssignedLevel() ;
213
214    if (levelSize[assignLevel] >= keepNodes) 
215                {
216      if (levelSize[assignLevel] > keepNodes)
217      {
218//        cout<<"assign Level : "<<assignLevel<< "     levelSize[assignLevel] :"<<levelSize[assignLevel]<<"   keepNodes : "<<keepNodes<<endl ;
219        removeExtraNode() ;
220      }
221      break ;
222                }
223        }
224//      cout << "SampleTree build : nb Node inserted : " << i << endl;
225
226}
227
228void CSampleTree::slimAssignedLevel()
229{
230  for(int i=MIN_NODE_SZ;i<=MAX_NODE_SZ;i++)
231  {
232    int levelSizeOrigin=levelSize[assignLevel] ;
233    slim2(root, assignLevel,i);
234    ri = 0;
235    int levelSizeBefore=levelSize[assignLevel] ;
236    isActiveOkSplit=true ;
237    emptyPool();
238//    cout<<"assign Level : "<<assignLevel<<"  MinNodeSize :"<<i<< "     levelSize[assignLevel] : "<<levelSizeOrigin<<"->"<<levelSizeBefore<<"->" <<levelSize[assignLevel]<<"   keepNodes : "<<keepNodes<<"  "<<"CanSplit " <<canSplit()<<endl ;
239    if (levelSize[assignLevel]<=keepNodes) break ;
240  }
241
242}
243
244void CSampleTree::removeExtraNode(void)
245{
246  std::list<NodePtr> nodeList ;
247  std::list<NodePtr>::iterator it1,it2, rm ;
248
249  root->getNodeLevel(assignLevel,nodeList) ;
250  double dist,minDist ;
251 
252 
253  for (int n=0; n<levelSize[assignLevel]-keepNodes ; ++n)
254  {
255    minDist=-1 ;
256    for(it1=nodeList.begin();it1!=nodeList.end();++it1)
257    {
258      dist=0 ;
259      for(it2=nodeList.begin();it2!=nodeList.end();++it2) dist+=arcdist((*it1)->centre,(*it2)->centre) ;
260      if (minDist > dist || minDist < 0.)
261      {
262        minDist=dist ;
263        rm=it1 ;
264      }
265    }
266    (*rm)->toDelete=true ;
267    nodeList.erase(rm) ;
268   
269  }
270  root->removeDeletedNodes(assignLevel) ;
271  isActiveOkSplit=true ;
272  emptyPool();
273}
274
275}
Note: See TracBrowser for help on using the repository browser.