Ticket #97: tree.cpp

File tree.cpp, 3.9 KB (added by ssenesi, 5 years ago)
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 <set>
11
12#include "timer.hpp"
13#include "mpi_routing.hpp"
14
15namespace sphereRemap {
16
17static const int MAX_LEVEL_SIZE = 100;
18
19double cputime();
20using namespace std;
21
22CBasicTree::CBasicTree() : ri(0), levelSize(MAX_LEVEL_SIZE), root(NULL)
23{
24}
25
26void CBasicTree::routeNodes(vector<int>& route, vector<Node>& nodes, int assignLevel)
27{
28        for (int i = 0; i < nodes.size(); i++)
29        {
30                root->routeNode(&nodes[i], assignLevel);
31                route[i] = nodes[i].route;
32        }
33}
34
35void CBasicTree::routeIntersections(vector<vector<int> >& routes, vector<Node>& nodes)
36{
37        for (int i = 0; i < nodes.size(); i++)
38                root->routeIntersection(routes[i], &nodes[i]);
39}
40
41void CBasicTree::build(vector<Node>& nodes)
42{
43        newRoot(1);
44        insertNodes(nodes);
45}
46
47void CBasicTree::output(ostream& flux, int level)
48{
49        root->output(flux,level,0) ;
50}
51void CBasicTree::slim(int nbIts)
52{
53        //if (!isSampleTree)
54        for (int i = 0; i < nbIts; i++)
55        {
56                for (int level = root->level - 1; level > 0; level--)
57                {
58                        slim2(root, level);
59                        ri = 0;
60                        emptyPool();
61
62                }
63
64                for (int level = 2; level < root->level; level++)
65                {
66                        slim2(root, level);
67                        ri = 0;
68                        emptyPool();
69                }
70        }
71}
72
73void CBasicTree::insertNode(NodePtr node)
74{
75        node->tree = this;
76        increaseLevelSize(0);
77        push_back(node);
78
79        NodePtr q;
80        while (pool.size())
81        {
82                q = pool.front();
83                pool.pop_front();
84                q = insert(q, root);
85                if (ri)
86                {
87                        delete q;
88                        ri = 0;
89                }
90        }
91}
92
93void CBasicTree::emptyPool(void)
94{
95        while (pool.size())
96        {
97                NodePtr q = pool.front();
98                pool.pop_front();
99                q = insert(q, root);
100                if (ri)
101                {
102                        delete q;
103                        ri = 0;
104                }
105        }
106}
107
108void CBasicTree::push_back(NodePtr node)
109{
110#ifdef DEBUG
111        node->parent = NULL; // will be overridden later, but for mem leak check better trigger leak as soon as possible
112#endif
113        pool.push_back(node);
114}
115
116void CBasicTree::push_front(NodePtr node)
117{
118#ifdef DEBUG
119        node->parent = NULL; // will be overridden later, but for mem leak check better trigger leak as soon as possible
120#endif
121        pool.push_front(node);
122}
123
124void CBasicTree::increaseLevelSize(int level)
125{
126        levelSize[level]++;
127}
128
129void CBasicTree::decreaseLevelSize(int level)
130{
131        levelSize[level]--;
132}
133
134void CBasicTree::newRoot(int level)  // newroot <- root
135{
136        root = new Node;
137        //      if (level > 1) cout << " newRoot level " << level << endl;
138        root->level = level;
139        root->parent = 0;
140        root->leafCount = 0;
141        root->centre = ORIGIN;
142        root->radius = 0.;
143        root->reinserted = false;
144        root->updateCount = 0;
145        root->tree = this;
146        levelSize[level]++;
147}
148
149CBasicTree::~CBasicTree()
150{
151        //FIXME uncomment the next line and figure out why it segfault sometimes
152        //root->free_descendants(); // recursively deletes all nodes in the tree
153        if (root) delete root;
154}
155
156void CTree::insertNodes(vector<Node>& nodes)
157{
158        int stepSlim = MAX_NODE_SZ*MAX_NODE_SZ*2;
159        const double ratio = 1.5;
160        for (int i = 0; i < nodes.size(); i++)
161        {
162                insertNode(&nodes[i]);
163
164                if (root->leafCount > stepSlim) // time for slim down
165                {
166                        slim();
167                        stepSlim = stepSlim * ratio;
168                }
169        }
170}
171
172
173void CSampleTree::insertNodes(vector<Node>& nodes)
174{
175        bool first1 = true;
176        bool first2 = true;
177        int stepSlim = MAX_NODE_SZ * MAX_NODE_SZ * keepNodes / 4;
178//      double ratio = 1 + (0.5 * (1 - (keepNodes - 1) / (1.0 * keepNodes))) ;
179        double ratio = 1.5 ;
180  int i ;
181 
182  for (i = 0; i < nodes.size(); i++)
183        {
184    insertNode(&nodes[i]);
185
186                if (root->leafCount > stepSlim && levelSize[assignLevel] < keepNodes-2) // time for slim down
187                {
188                        slim();
189                        stepSlim = stepSlim * ratio;
190                }
191
192   
193    if (levelSize[assignLevel] == keepNodes-2 && first1)
194                {
195      slim();
196                        first1 = false;
197                }
198
199                if (levelSize[assignLevel] == keepNodes-1 && first2)
200                {
201      slim();
202      first2=false ;
203                }
204
205        if (levelSize[assignLevel] > keepNodes)
206                {
207      slim();
208                }
209    if (levelSize[assignLevel] >= keepNodes)
210                {
211      break ;
212                }
213        }
214
215}
216
217}