#include <cmath>
#include <tulip/MetricProxy.h>

#include "ConnectedAndTreeComponent.h"

METRICPLUGIN(ConnectedAndTreeComponent,"Connected & Tree Component","David Auber","12/06/2001","Alpha","0","1");

using namespace std;

int ConnectedAndTreeComponent::attachNumerotation(node n,
						  STL_EXT_NS::hash_map<node,bool> &visited,
						  STL_EXT_NS::hash_map<node,bool> &finished,
						  STL_EXT_NS::hash_map<node,int> &minAttach,
						  int &id, stack<node> &renum, int &curComponent)
{
  if (visited[n]) return minAttach[n];
  visited[n]=true;
  int myId=id;  
  id++;
  minAttach[n]=myId;
  renum.push(n);

  int result=myId;
  Iterator<node> *itN=superGraph->getOutNodes(n);
  for (;itN->hasNext();) {
    node tmpN=itN->next();
    if (!finished[tmpN]) {
      int tmp=attachNumerotation(tmpN,visited,finished,minAttach,id,renum,curComponent);
      if (result>tmp) result=tmp;
    }
  } delete itN;
  minAttach[n]=result;

  if (result==myId) {
    while (renum.top()!=n) {
      node tmp=renum.top();
      renum.pop();
      finished[tmp]=true;
      minAttach[tmp]=result;
      metricProxy->setNodeValue(tmp,curComponent);
    }
    finished[n]=true;
    metricProxy->setNodeValue(n,curComponent);
    curComponent++;
    renum.pop();
  }
  return result;
}


void ConnectedAndTreeComponent::treeRenum(node n,map<int,int> &histo) {
  Iterator<node> *itN=superGraph->getInOutNodes(n);
  for (;itN->hasNext();) {
    node itn=itN->next();
    if ((itn!=n) && (histo[(int)metricProxy->getNodeValue(itn)]==1)) {
      metricProxy->setNodeValue(itn,metricProxy->getNodeValue(n));
      histo[(int)metricProxy->getNodeValue(n)]+=1;
      treeRenum(itn,histo);
    }
  }delete itN;
}

ConnectedAndTreeComponent::ConnectedAndTreeComponent(PropertyContext *context):Metric(context) {}

ConnectedAndTreeComponent::~ConnectedAndTreeComponent()
{}

bool ConnectedAndTreeComponent::run()
{
  STL_EXT_NS::hash_map<node,bool> visited;
  STL_EXT_NS::hash_map<node,bool> finished;
  stack<node> renum;
  STL_EXT_NS::hash_map<node,int> cachedValues;

  int id=1;
  int curComponent=0;
  Iterator<node> *itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    if (!visited[itn]) {attachNumerotation(itn,visited,finished,cachedValues,id,renum,curComponent);}
  }delete itN;

  //build of histogram
  map<int,int> histo;
  map<int,int>::iterator itHisto;
  itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    if ((itHisto=histo.find((int)metricProxy->getNodeValue(itn)))!=histo.end()) {
      (*itHisto).second++;
    }
    else {
      histo[(int)metricProxy->getNodeValue(itn)]=1;
    }
  }delete itN;


  //histo ok
  itN=superGraph->getNodes();
  for (;itN->hasNext();)
    {
      node itn=itN->next();
      if (histo[(int)metricProxy->getNodeValue(itn)]==1)
	treeRenum(itn,histo);
    }
  delete itN;
  return true;
}