#include <cmath>
#include <stdio.h>
#include "StrahlerAllMetric.h"
#include <tulip/StringProxy.h>

METRICPLUGIN(StrahlerAllMetric,"StrahlerAllGeneral","David Auber","06/04/2000","Alpha","0","1");

using namespace std;

namespace std {
  struct couple
  {
    int p,r;
    bool operator ==(const couple&d)
    {
      if ((p==d.p) && (r==d.r)) return true;
      return false;
    }
  };

  template <> struct equal_to<couple>
  {
    bool operator()(const couple &c,const couple &d)
    {
      if ((c.r==d.r) && (c.p==d.p)) return true;
      return false;
    }
  };

  template <> struct less<couple>
  {
    bool operator()(const couple &c,const couple &d)
    {
      if (c.r<d.r) return true;
      if (c.r>d.r) return false;
      if (c.p<d.p) return true;
      if (c.p>d.p) return false;
      return false;
    }
  };
};

static int returnEdge=0;
static int crossEdge=0;
static int descentEdge=0;
static int normalEdge=0;

int max(int i1,int i2)
{
  if (i1>i2) return i1; else return i2;
}

int min(int i1,int i2)
{
  if (i1<i2) return i1; else return i2;
}
struct StackEval
{
  StackEval(int f,int u):freeS(f),usedS(u){}
  int freeS,usedS;
};

struct GreaterStackEval
{
  bool operator()(const StackEval e1,const StackEval e2)
  {
    return (e1.freeS>e2.freeS);
  }
};

Strahler StrahlerAllMetric::topSortStrahler(node n, int &curPref,
					    STL_EXT_NS::hash_map<node,int> &tofree,
					    STL_EXT_NS::hash_map<node,int> &prefix,
					    STL_EXT_NS::hash_map<node,bool> &visited,
					    STL_EXT_NS::hash_map<node,bool> &finished,
					    STL_EXT_NS::hash_map<node,Strahler> &cachedValues)
{
  visited[n]=true;
  Strahler result;
  prefix[n]=curPref;
  curPref++;
  if (superGraph->outdeg(n)==0) {finished[n]=true;return(result);}
  list<int> strahlerResult;
  //  cerr << ".";
  list<StackEval> tmpEval;
  //Construction des ensembles pour evaluer le strahler
  Iterator<node> *itN=superGraph->getOutNodes(n);
  for (;itN->hasNext();)
    {
      node tmpN=itN->next();
      if (!visited[tmpN])
	{
	  normalEdge++;
	  //Arc Normal
	  tofree[n]=0;
	  Strahler tmpValue=topSortStrahler(tmpN,curPref,tofree,prefix,visited,finished,cachedValues);
	  //Data for strahler evaluation on the spanning Dag.
	  strahlerResult.push_front(tmpValue.strahler);
	  //Counting current used stacks.
	  //old result.usedStack+=tmpValue.usedStack;
	  //old result.usedStack-=tofree[n];
	  tmpEval.push_back(StackEval(tmpValue.stacks-tmpValue.usedStack+tofree[n],tmpValue.usedStack-tofree[n]));
	  //Looking if we need more stacks to evaluate this node.
	  //old	freeStacks=max(freeStacks,tmpValue.stacks-tmpValue.usedStack+tofree[n]);
	}
      else
	{
	  if (finished[tmpN])
	    {
	      if(prefix[tmpN]<prefix[n])
		{
		  crossEdge++;
		  //		  cerr << "Cross Edge" << endl;
		  //Arc Croisée
		  Strahler tmpValue=cachedValues[tmpN];
		  //Data for strahler evaluation on the spanning Dag.
		  strahlerResult.push_front(tmpValue.strahler);
		  //Looking if we need more stacks to evaluate this node.
		  tmpEval.push_back(StackEval(tmpValue.stacks,0));
		  //old freeStacks=max(freeStacks,tmpValue.stacks);
		}
	      else
		{
		  descentEdge++;
		  //		  cerr << "Descent Edge" << endl;
		  //Arc descent
		  Strahler tmpValue=cachedValues[tmpN];
		  //Data for strahler evaluation on the spanning Dag.
		  strahlerResult.push_front(tmpValue.strahler);
		}
	    }
	  else 
	    {
	      returnEdge++;
	      if(tmpN==n)
		{
		  //		  cerr<< "SelfLoop" << endl;
		  tmpEval.push_back(StackEval(1,0));
		  //old freeStacks=max(freeStacks,1);
		}
	      else
		{
		  //New nested cycle.
		  tofree[tmpN]++;
		  tmpEval.push_back(StackEval(0,1));
		  //result.usedStack++;
		}
	      //	      cerr << "Return edge"<< endl;
	      //Arc retour
	      //Register needed tp store the result of the recursive call
	      strahlerResult.push_front(1);
	    }
	}
    }
  delete itN;

  //compute the minimal nested cycles
  GreaterStackEval gSE;
  tmpEval.sort(gSE);
  result.stacks=0;
  result.usedStack=0;
  for (list<StackEval>::iterator it=tmpEval.begin();it!=tmpEval.end();++it)
    {
      result.usedStack+=it->usedS;
      result.stacks=max(result.stacks,it->freeS+it->usedS);//tmpValue.stacks-tmpValue.usedStack+tofree[n]);
      result.stacks-=it->usedS;
    }
  result.stacks=result.stacks+result.usedStack;
  //evaluation du strahler simple
  int tmpDbl;
  int additional=0;
  int available=0;
  strahlerResult.sort();
  while (!strahlerResult.empty())
    {
      tmpDbl=strahlerResult.back();
      strahlerResult.pop_back();
      if (tmpDbl>available)
	{
	  additional+=tmpDbl - available;
	  available=tmpDbl - 1;
	}
      else
	available -=1;
    }

  result.strahler=additional;
  strahlerResult.clear();
  finished [n]=true;
  cachedValues[n]=result;
  return result;
}

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

StrahlerAllMetric::~StrahlerAllMetric()
{}

bool StrahlerAllMetric::run()
{
  STL_EXT_NS::hash_map<node,bool> visited;
  STL_EXT_NS::hash_map<node,bool> finished;
  STL_EXT_NS::hash_map<node,int> prefix;
  STL_EXT_NS::hash_map<node,int> tofree;
  STL_EXT_NS::hash_map<node,Strahler> cachedValues;
  int curPref=0;
  Iterator<node> *it=superGraph->getNodes();
  for (int i=0;it->hasNext();++i)
    {
      if (!pluginProgress->progress(i,superGraph->numberOfNodes())) break;
      visited.clear();
      finished.clear();
      prefix.clear();
      tofree.clear();
      cachedValues.clear();
      curPref=0;
      node itn=it->next();
      tofree[itn]=0;
      topSortStrahler(itn,curPref,tofree,prefix,visited,finished,cachedValues);
      metricProxy->setNodeValue(itn,sqrt((double)cachedValues[itn].strahler*(double)cachedValues[itn].strahler
					 +(double)cachedValues[itn].stacks*(double)cachedValues[itn].stacks));
    }
  delete it;

  return pluginProgress->progress(100,100);
}

bool StrahlerAllMetric::check(string &erreurMsg)
{
  erreurMsg="";
  return true;
}

void StrahlerAllMetric::reset(){}