#include <string>
#include <cassert>
#include <math.h> 
#include <tulip/MethodFactory.h>
#include <tulip/LayoutProxy.h>
#include <tulip/SelectionProxy.h>
#include <tulip/SubGraph.h>

#include "GeneralGraphBox.h"

LAYOUTPLUGIN(GeneralGraphBox,"General Graph Box","David Auber","23/05/2000","Alpha","0","1");

using namespace std;

GeneralGraphBox::GeneralGraphBox(PropertyContext *context):Layout(context) {}

GeneralGraphBox::~GeneralGraphBox() {}
class LessThanEdge
{
public:
  MetricProxy *metric;
  SuperGraph *sg;
  bool operator() (edge e1,edge e2){return (metric->getNodeValue(sg->source(e1)) < metric->getNodeValue(sg->source(e2)));}
};

void GeneralGraphBox::DagLevelSpanningTree(SuperGraph* superGraph,node n) {
  assert(superGraph->isAcyclic());
  stack<edge> toDelete;
  MetricProxy *barycenter=getProxy<MetricProxy>(superGraph,"Barycenter");

  Iterator<node> *itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    if (superGraph->indeg(itn)>1) {
      list<edge> tmpList;

      Iterator<edge> *itE=superGraph->getInEdges(itn);
      for (;itE->hasNext();) {
	edge ite=itE->next();
	tmpList.push_back(ite);
      }delete itE;

      LessThanEdge tmpL;
      tmpL.metric=barycenter;
      tmpL.sg=superGraph;
      tmpList.sort(tmpL);
      int toKeep=tmpList.size()/2;
      itE=superGraph->getInEdges(itn);
      for (;itE->hasNext();) {
	edge ite=itE->next();
	if (toKeep!=0) toDelete.push(ite);
	toKeep--;
      }delete itE;      
    }
  }delete itN;
  while (!toDelete.empty()) {
    superGraph->delEdge(toDelete.top());
    toDelete.pop();
  }
  assert(superGraph->isTree());
}


void GeneralGraphBox::makeAcyclic(SuperGraph* superGraph,set<edge> &reversed,list<SelfLoops> &selfLoops) {
  if (!superGraph->isAcyclic()) {
    bool cached,resultBool;
    string erreurMsg;
    SelectionProxy *spanningDag=0;
    spanningDag=getLocalProxy<SelectionProxy>(superGraph,"SpanningDag",cached,resultBool,erreurMsg);
    if (cached) resultBool=spanningDag->recompute(erreurMsg);
    if (!resultBool) cerr << erreurMsg;
    
    //sauvegarde information
    vector<edge> graphEdges(superGraph->numberOfEdges());
    int i=0;
    Iterator<edge> *itE=superGraph->getEdges();
    for (;itE->hasNext();) {
      graphEdges[i]=itE->next();
      i++;
    }delete itE;
    
    //We replace self loops by three edges an two nodes.
    for (vector<edge>::const_iterator itEdge=graphEdges.begin();itEdge!=graphEdges.end();++itEdge) {
      edge ite=*itEdge;
      if ((spanningDag->getEdgeValue(ite))==false) {
	if (superGraph->source(ite)==superGraph->target(ite)) {
	  node n1=superGraph->addNode();
	  node n2=superGraph->addNode();
	  selfLoops.push_back(SelfLoops(n1 ,
					n2 , 
					superGraph->addEdge(superGraph->source(ite),n1) , 
					superGraph->addEdge(n1,n2) , 
					superGraph->addEdge(superGraph->source(ite),n2) , 
					ite ));
	}
	else {
	  reversed.insert(ite);
	  superGraph->reverse(ite);
	}
      }
    }
    superGraph->getPropertyProxyContainer()->delLocalProxy("SpanningDag");      
    //We remove all self loops from the graph
    list<SelfLoops>::iterator itSelf;
    for (itSelf=selfLoops.begin();itSelf!=selfLoops.end();++itSelf) {
      superGraph->delEdge((*itSelf).oldEdge);
    }
  }
  assert(superGraph->isAcyclic());
}

//le faire une fois le layer assignement et le barycenter efféctué
node GeneralGraphBox::makeSimpleSource(SuperGraph* superGraph) {
  assert(superGraph->isAcyclic());
  node startNode=superGraph->addNode();
  Iterator<node> *itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    if ((superGraph->indeg(itn)==0) && (itn!=startNode)) {
      superGraph->addEdge(startNode,itn);
    }
  }delete itN;
  assert(superGraph->isAcyclic());
  return startNode;
}


void GeneralGraphBox::makeProperDag(SuperGraph* superGraph,list<node> &addedNodes, STL_EXT_NS::hash_map<edge,edge> &replacedEdges)
{
  if (superGraph->isTree()) return;
  assert(superGraph->isAcyclic());
  //We compute the dag level metric on resulting graph.
  bool cached,resultBool;
  string erreurMsg;
  MetricProxy *dagLevel=getLocalProxy<MetricProxy>(superGraph,"DagLevel",cached,resultBool,erreurMsg);
  if (!resultBool) cerr << erreurMsg;
  //  cerr << "DagLevel ok" << endl;
  //  cerr << "nedges:" << superGraph->numberOfEdges()<< " " <<  superGraph->numberOfNodes() << endl;
  assert(resultBool);
  //we now transform the dag in a proper Dag, two linked nodes of a proper dag
  //must have a difference of one of dag level metric.
  node tmp1,tmp2;
  string tmpString;
  //sauvegarde information
  //cerr << "nedges:" << superGraph->numberOfEdges()<< " " <<  superGraph->numberOfNodes() << endl;
  vector<edge> graphEdges(superGraph->numberOfEdges());
  Iterator<edge> *itE=superGraph->getEdges();
  for (int i=0;itE->hasNext();++i) {
    graphEdges[i]=itE->next();
  }delete itE;
  IntProxy *edgeLength=getLocalProxy<IntProxy>(superGraph,"treeEdgeLength");
  for (vector<edge>::const_iterator itEdge=graphEdges.begin();itEdge!=graphEdges.end();++itEdge) {
    edge ite=*itEdge;
    int delta=(int)rint(dagLevel->getNodeValue(superGraph->target(ite))-dagLevel->getNodeValue(superGraph->source(ite)));
    if (delta>1) {
      tmp1=superGraph->addNode();
      replacedEdges[ite]=superGraph->addEdge(superGraph->source(ite),tmp1);
      addedNodes.push_back(tmp1);
      dagLevel->setNodeValue(tmp1,dagLevel->getNodeValue(superGraph->source(ite))+1);
      if (delta>2) {
	tmp2=superGraph->addNode();
	addedNodes.push_back(tmp2);
	edge e=superGraph->addEdge(tmp1,tmp2);
	edgeLength->setEdgeValue(e,delta-2);	  
	dagLevel->setNodeValue(tmp2,dagLevel->getNodeValue(superGraph->target(ite))-1);
	tmp1=tmp2;
      }
      superGraph->addEdge(tmp1,superGraph->target(ite));
    }
  }
  //  superGraph->getPropertyProxyContainer()->delLocalProxy("DagLevel");
  for (STL_EXT_NS::hash_map<edge,edge>::const_iterator it=replacedEdges.begin();it!=replacedEdges.end();++it) 
    superGraph->delEdge((*it).first);
  assert(superGraph->isAcyclic());
}

bool GeneralGraphBox::run()
{
  //=======================================================================
  // Build a clone of this graph
  SelectionProxy *tmpSel=getLocalProxy<SelectionProxy>(superGraph,"TmpSel");
  layoutProxy->setAllEdgeValue(vector<Coord>(0));
  tmpSel->setAllNodeValue(true);
  tmpSel->setAllEdgeValue(true);
  SubGraph *tmpSubGraph=superGraph->addView("tmpView",tmpSel);
  SuperGraph *mySGraph=tmpSubGraph->getAssociatedSuperGraph();
  superGraph->getPropertyProxyContainer()->delLocalProxy("TmpSel");

  //========================================================================
  //if the graph is not acyclic we reverse edges to make it acyclic
  list<SelfLoops> listSelfLoops;
  set<edge> reversedEdges;
  makeAcyclic(mySGraph,reversedEdges,listSelfLoops);

  //We add a node and edges to force the dag to have only one source.
  node startNode=makeSimpleSource(mySGraph);

  //We transform the dag in a proper dag
  list<node> properAddedNodes;
  STL_EXT_NS::hash_map<edge,edge> replacedEdges;
  IntProxy *edgeLength=getLocalProxy<IntProxy>(mySGraph,"treeEdgeLength");
  edgeLength->setAllEdgeValue(1);
  makeProperDag(mySGraph,properAddedNodes,replacedEdges);

  bool cached,resultBool;
  string erreurMsg;

  //we compute metric for cross reduction
  *getLocalProxy<MetricProxy>(mySGraph,"treeOrder")=*getLocalProxy<MetricProxy>(mySGraph,"Barycenter",cached,resultBool,erreurMsg);
  cerr << "Barycenter result = " << resultBool << " --> " << erreurMsg;
  //We extract a spanning tree from the proper dag.
  DagLevelSpanningTree(mySGraph,startNode);

  //We draw the tree using a tree drawing algorithm
  LayoutProxy *tmpLayout=getLocalProxy<LayoutProxy>(mySGraph,"Hierarchical Tree (R-T Extended)",cached,resultBool,erreurMsg);
  
  //  return true;
  //  MetricProxy *barycenter = getLocalProxy<MetricProxy>(mySGraph,"Barycenter",cached,resultBool,erreurMsg);
  //  MetricProxy *dagLevel = getLocalProxy<MetricProxy>(superGraph,"DagLevel",cached,resultBool,erreurMsg);
  //  cerr << "End Tree Walker box" << endl;
  Iterator<node> *itN=superGraph->getNodes();
  for (;itN->hasNext();)
    {
     node itn=itN->next();
     layoutProxy->setNodeValue(itn,tmpLayout->getNodeValue(itn));
     //layoutProxy->setNodeValue(itn,Coord(barycenter->getNodeValue(itn),dagLevel->getNodeValue(itn),0));
    }
  delete itN;
  
  //  cerr << "we compute bends on splitted edges" << endl;
  for (STL_EXT_NS::hash_map<edge,edge>::const_iterator it=replacedEdges.begin();it!=replacedEdges.end();++it)
    {
      edge toUpdate=(*it).first;
      edge start=(*it).second;
      edge end=start;
      Coord p1,p2;
      //we take the first and last point of the replaced edges
      while (superGraph->target(end)!=superGraph->target(toUpdate))
	{
	  Iterator<edge> *itE=mySGraph->getOutEdges(superGraph->target(end));end=itE->next();delete itE;
	}
      node firstN=superGraph->target(start);
      node endN=superGraph->source(end);
      LineType::RealType edgeLine;
      if (reversedEdges.find(toUpdate)!=reversedEdges.end())
	{
	  p1=tmpLayout->getNodeValue(endN);
	  p2=tmpLayout->getNodeValue(firstN);
	}
      else
	{	  
	  p1=tmpLayout->getNodeValue(firstN);
	  p2=tmpLayout->getNodeValue(endN);
	}
      if (p1==p2) edgeLine.push_back(p1); else
	{edgeLine.push_back(p1); edgeLine.push_back(p2);}
      layoutProxy->setEdgeValue(toUpdate,edgeLine);
    }

  //cerr << "We compute self loops" << endl;
  while (!listSelfLoops.empty())
    {
      SelfLoops tmp=listSelfLoops.back();
      listSelfLoops.pop_back();
      LineType::RealType tmpLCoord;
      LineType::RealType &edge1=tmpLayout->getEdgeValue(tmp.e1);
      LineType::RealType &edge2=tmpLayout->getEdgeValue(tmp.e2);
      LineType::RealType &edge3=tmpLayout->getEdgeValue(tmp.e3);
      LineType::RealType::iterator it;
      for (it=edge1.begin();it!=edge1.end();++it)
	tmpLCoord.push_back(*it);
      tmpLCoord.push_back(tmpLayout->getNodeValue(tmp.ghostNode1));
      for (it=edge2.begin();it!=edge2.end();++it)
	tmpLCoord.push_back(*it);
      tmpLCoord.push_back(tmpLayout->getNodeValue(tmp.ghostNode2));
      for (it=edge3.begin();it!=edge3.end();++it)
	tmpLCoord.push_back(*it);
      layoutProxy->setEdgeValue(tmp.oldEdge,tmpLCoord);
      mySGraph->delAllNode(tmp.ghostNode1);
      mySGraph->delAllNode(tmp.ghostNode2);
    }

  //  cerr << "we clean every added nodes and edges" << endl;
  mySGraph->getPropertyProxyContainer()->delLocalProxy("treeEdgeLength");
  mySGraph->getPropertyProxyContainer()->delLocalProxy("treeOrder");
  mySGraph->getPropertyProxyContainer()->delLocalProxy("Hierarchical Tree (R-T Extended)");
  mySGraph->getPropertyProxyContainer()->delLocalProxy("viewSize");
  for (set<edge>::const_iterator it=reversedEdges.begin();it!=reversedEdges.end();++it) {
    superGraph->reverse(*it);
  }
  mySGraph->delAllNode(startNode);
  while(!properAddedNodes.empty()) {
    mySGraph->delAllNode(properAddedNodes.back());
    properAddedNodes.pop_back();
  }
  superGraph->delView(tmpSubGraph);
  return true;
}