source: XIOS/dev/branch_yushan_merged/extern/remap/src/tree.cpp @ 1172

#include <cassert>
#include "tree.hpp"
#include "node.hpp"
#include "elt.hpp"
#include <iostream>
#include "mpi.hpp"
#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */
#include <vector>
#include <list>
#include <set>

#include "timer.hpp"
#include "mpi_routing.hpp"

namespace sphereRemap {

const int MAX_LEVEL_SIZE = 100;

double cputime();
using namespace std;

/*
CBasicTree::CBasicTree() : ri(0), levelSize(MAX_LEVEL_SIZE), root(NULL)
{
}
*/

void CBasicTree::routeNodes(vector<int>& route, vector<Node>& nodes, int assignLevel)
{
  for (int i = 0; i < nodes.size(); i++)
  {
    root->routeNode(&nodes[i], assignLevel);
    route[i] = nodes[i].route;
  }
}

void CBasicTree::routeIntersections(vector<vector<int> >& routes, vector<Node>& nodes)
{
  for (int i = 0; i < nodes.size(); i++)
    root->routeIntersection(routes[i], &nodes[i]);
}

void CBasicTree::build(vector<Node>& nodes)
{
  newRoot(1);
  insertNodes(nodes);
}

void CBasicTree::output(ostream& flux, int level)
{
  root->output(flux,level,0) ;
}
void CBasicTree::slim(int nbIts)
{
  for (int i = 0; i < nbIts; i++)
  {
    for (int level = root->level - 1; level > 0; level--)
    {
      slim2(root, level);
      ri = 0;
      emptyPool();
    }

    for (int level = 2; level < root->level; level++)
    {
      slim2(root, level);
      ri = 0;
      emptyPool();
    }
  }
}



void CBasicTree::insertNode(NodePtr node)
{
  node->tree = this;
  increaseLevelSize(0);
  push_back(node);

  NodePtr q;
  while (pool.size())
  {
    q = pool.front();
    pool.pop_front();
    q = insert(q, root);
    if (ri)
    {
      delete q;
      ri = 0;
    }
  }
}

void CBasicTree::emptyPool(void)
{
  while (pool.size())
  {
    NodePtr q = pool.front();
    pool.pop_front();
    q = insert(q, root);
    if (ri)
    {
      delete q;
      ri = 0;
    }
  }
}

void CBasicTree::push_back(NodePtr node)
{
#ifdef DEBUG
        node->parent = NULL; // will be overridden later, but for mem leak check better trigger leak as soon as possible
#endif
        pool.push_back(node);
}

void CBasicTree::push_front(NodePtr node)
{
#ifdef DEBUG
        node->parent = NULL; // will be overridden later, but for mem leak check better trigger leak as soon as possible
#endif
        pool.push_front(node);
}

void CBasicTree::increaseLevelSize(int level)
{
        levelSize[level]++;
}

void CBasicTree::decreaseLevelSize(int level)
{
        levelSize[level]--;
}

void CBasicTree::newRoot(int level)  // newroot <- root
{
        root = new Node;
        // if (level > 1) cout << " newRoot level " << level << endl;
        root->level = level;
        root->parent = 0;
        root->leafCount = 0;
        // initialize root node on the sphere
        root->centre.x=1 ; 
        root->centre.y=0 ; 
        root->centre.z=0 ; 
        root->radius = 0.;
        root->reinserted = false;
        root->updateCount = 0;
        root->tree = this;
        levelSize[level]++;
}

CBasicTree::~CBasicTree()
{
        //FIXME uncomment the next line and figure out why it segfault sometimes
        //root->free_descendants(); // recursively deletes all nodes in the tree
        if (root) delete root;
}

void CTree::insertNodes(vector<Node>& nodes)
{
        int stepSlim = MAX_NODE_SZ*MAX_NODE_SZ*2;
        const double ratio = 1.5;
        for (int i = 0; i < nodes.size(); i++)
        {
                insertNode(&nodes[i]);

                if (root->leafCount > stepSlim) // time for slim down
                {
                        slim();
                        stepSlim = stepSlim * ratio;
                }
        }
}


void CSampleTree::insertNodes(vector<Node>& nodes)
{
        bool first1 = true;
        bool first2 = true;
        int stepSlim = MAX_NODE_SZ * MAX_NODE_SZ * keepNodes / 4;
//      double ratio = 1 + (0.5 * (1 - (keepNodes - 1) / (1.0 * keepNodes))) ;
        double ratio = 1.5 ;
  int i ;
  
//  cout<<"CSampleTree::insertNodes  : nb node to be inserted : "<<nodes.size()<<endl ;
  for (i = 0; i < nodes.size(); i++)
        {
    insertNode(&nodes[i]);

                if (root->leafCount > stepSlim && levelSize[assignLevel] < keepNodes-2) // time for slim down
                {
                        slim();
                        stepSlim = stepSlim * ratio;
                }

    
    if (levelSize[assignLevel] == keepNodes-2 && first1)
                {
      slim();
                        first1 = false;
                }

                if (levelSize[assignLevel] == keepNodes-1 && first2)
                {
      slim();
      first2=false ;
                }

        if (levelSize[assignLevel] >= keepNodes) slim();
        if (levelSize[assignLevel] > keepNodes) slim();
    if (levelSize[assignLevel] > keepNodes) slimAssignedLevel() ;

    if (levelSize[assignLevel] >= keepNodes) 
                {
      if (levelSize[assignLevel] > keepNodes)
      {
//        cout<<"assign Level : "<<assignLevel<< "     levelSize[assignLevel] :"<<levelSize[assignLevel]<<"   keepNodes : "<<keepNodes<<endl ;
        removeExtraNode() ;
      }
      break ;
                }
        }
//      cout << "SampleTree build : nb Node inserted : " << i << endl;

}

void CSampleTree::slimAssignedLevel()
{
  for(int i=MIN_NODE_SZ;i<=MAX_NODE_SZ;i++)
  {
    int levelSizeOrigin=levelSize[assignLevel] ;
    slim2(root, assignLevel,i);
    ri = 0;
    int levelSizeBefore=levelSize[assignLevel] ;
    isActiveOkSplit=true ;
    emptyPool();
//    cout<<"assign Level : "<<assignLevel<<"  MinNodeSize :"<<i<< "     levelSize[assignLevel] : "<<levelSizeOrigin<<"->"<<levelSizeBefore<<"->" <<levelSize[assignLevel]<<"   keepNodes : "<<keepNodes<<"  "<<"CanSplit " <<canSplit()<<endl ;
    if (levelSize[assignLevel]<=keepNodes) break ;
  }

}

void CSampleTree::removeExtraNode(void)
{
  std::list<NodePtr> nodeList ;
  std::list<NodePtr>::iterator it1,it2, rm ;

  root->getNodeLevel(assignLevel,nodeList) ;
  double dist,minDist ;
 
  
  for (int n=0; n<levelSize[assignLevel]-keepNodes ; ++n)
  {
    minDist=-1 ;
    for(it1=nodeList.begin();it1!=nodeList.end();++it1)
    {
      dist=0 ;
      for(it2=nodeList.begin();it2!=nodeList.end();++it2) dist+=arcdist((*it1)->centre,(*it2)->centre) ;
      if (minDist > dist || minDist < 0.)
      {
        minDist=dist ;
        rm=it1 ;
      }
    }
    (*rm)->toDelete=true ;
    nodeList.erase(rm) ;
    
  }
  root->removeDeletedNodes(assignLevel) ;
  isActiveOkSplit=true ;
  emptyPool();
}

}