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

#include "GeneralGraph.h"

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

using namespace std;

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

GeneralGraph::~GeneralGraph() {}

void GeneralGraph::DagLevelSpanningTree(SuperGraph* superGraph,node n) {
  assert(superGraph->isAcyclic());
  stack<edge> toDelete;
  Iterator<node> *itN=superGraph->getNodes();
  for (;itN->hasNext();) {
      node itn=itN->next();
      if (superGraph->indeg(itn)>1) {
	int tmpI=superGraph->indeg(itn)-1;
	Iterator<edge> *itE=superGraph->getInEdges(itn);
	  for (;tmpI>0;--tmpI) toDelete.push(itE->next());
	  delete itE;
	}
    }
  delete itN;
  while (!toDelete.empty()) {
    superGraph->delEdge(toDelete.top());
    toDelete.pop();
  }
  assert(superGraph->isTree());
}

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

void GeneralGraph::dfsOrderedSpanningTree(SuperGraph *sg,node n, STL_EXT_NS::hash_map<node,bool> &flag)
{
  flag[n]=true;
  LessThanEdgos lessEdge;
  lessEdge.metric=getLocalProxy<MetricProxy>(sg,"TreeWalkerBoxOrder");
  lessEdge.sg=sg;
  Iterator<edge> *itE=sg->getOutEdges(n);
  list<edge> tmpVect;
  for (;itE->hasNext();) {
    edge ite=itE->next();
    tmpVect.push_back(ite);
  } delete itE;
  tmpVect.sort(lessEdge);
  
  list<edge>::iterator it;
  for (it=tmpVect.begin();it!=tmpVect.end();++it) {
    if (flag.find(sg->target(*it))!=flag.end())	{
      sg->delEdge(*it);
    }
    else {
      dfsOrderedSpanningTree(sg,sg->target(*it),flag);
    }
  }
}

void GeneralGraph::orderedSpanningTree(SuperGraph* superGraph,node n)
{
  MetricProxy *order=getLocalProxy<MetricProxy>(superGraph,"treeOrder");
  assert(superGraph->isAcyclic());
  set<edge> toDelete;
  Iterator<node> *itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    edge toKeep;
    double minVal=1000000;
    double maxVal=0;
    if (superGraph->indeg(itn)>1) {
      Iterator<edge> *itE=superGraph->getInEdges(itn);
      for (;itE->hasNext();) {
	edge ite=itE->next();
	if ((superGraph->indeg(n)%2)==0) {
	  if (order->getNodeValue(superGraph->source(ite))<minVal) {
	    minVal=order->getNodeValue(superGraph->source(ite));
	    toKeep=ite;
	  }
	}
	else {
	  if (order->getNodeValue(superGraph->source(ite))>maxVal) {
	    maxVal=order->getNodeValue(superGraph->source(ite));
	    toKeep=ite;
	  }
	}
	toDelete.insert(ite);
      }delete itE;
      toDelete.erase(toKeep);
    }
  }
  delete itN;
  set<edge>::iterator it;
  for (it=toDelete.begin();it!=toDelete.end();++it) {
    superGraph->delEdge(*it);
  }
  assert(superGraph->isTree());
}

void GeneralGraph::makeAcyclic(SuperGraph* superGraph,set<edge> &reversed,list<SelfLoops> &selfLoops)
{
  //cerr << superGraph << endl;
  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;
    assert(resultBool);
    //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);
    }
  }
  //  cerr << superGraph << endl;
  assert(superGraph->isAcyclic());
}

node GeneralGraph::makeSimpleSource(SuperGraph* superGraph) {
  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;
  return startNode;
}

void GeneralGraph::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());
  int i=0;
  Iterator<edge> *itE=superGraph->getEdges();
  for (;itE->hasNext();) {
    //graphEdges[i].push_back(itE->next());
    graphEdges[i]=itE->next();
    i++;
  }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);
      if (delta>2) {
	tmp2=superGraph->addNode();
	addedNodes.push_back(tmp2);
	edge e=superGraph->addEdge(tmp1,tmp2);
	edgeLength->setEdgeValue(e,delta-2);	  
	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 GeneralGraph::run()
{
  SizesProxy *sizesproxy=getLocalProxy<SizesProxy>(superGraph,"viewSize");
  sizesproxy->setAllNodeValue(Size(1,1,1));
  sizesproxy->setAllEdgeValue(Size(0.125,0.125,0.5));
  layoutProxy->setAllEdgeValue(vector<Coord>(0));
  //=======================================================================
  // Build a clone of this graph
  SelectionProxy *tmpSel=getLocalProxy<SelectionProxy>(superGraph,"TmpSel");
  tmpSel->setAllNodeValue(true);
  tmpSel->setAllEdgeValue(true);
  /*
  tmpSel->setAllNodeValue(false);
  tmpSel->setAllEdgeValue(false);
  Iterator<node> *iteN=superGraph->getNodes();
  Iterator<edge> *iteE=superGraph->getEdges();
  for (;iteN->hasNext();) tmpSel->setNodeValue(iteN->next(),true);
  delete iteN;
  for (;iteE->hasNext();) tmpSel->setEdgeValue(iteE->next(),true);
  delete iteE;
  */
  SubGraph *tmpSubGraph=superGraph->addView("tmpView",tmpSel);
  SuperGraph *mySGraph=tmpSubGraph->getAssociatedSuperGraph();
  //  cerr << "First nedges:" << mySGraph->numberOfEdges()<< " " <<  mySGraph->numberOfNodes() << endl;
  superGraph->getPropertyProxyContainer()->delLocalProxy("TmpSel");

  SizesProxy *sizesproxy2=getLocalProxy<SizesProxy>(mySGraph,"viewSize");
  sizesproxy2->setAllNodeValue(Size(0.1,0.1,0.1));
  Iterator<node> *itNN=superGraph->getNodes();
  for (;itNN->hasNext();) {
    node itn=itNN->next();
    sizesproxy2->setNodeValue(itn,Size(1,1,1));
  }delete itNN;
  
  bool cached,result;
  string errStr;


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

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

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

  //we compute metric for cross reduction
  *getLocalProxy<MetricProxy>(mySGraph,"treeOrder")=*getLocalProxy<MetricProxy>(mySGraph,"Barycenter",cached,result,errStr);
  assert(result);
  //We extract a spanning tree from the proper dag.
  //orderedSpanningTree(mySGraph,startNode);
  //  DagLevelSpanningTree(mySGraph,startNode);
  STL_EXT_NS::hash_map<node,bool> flagTmp;
  dfsOrderedSpanningTree(mySGraph,startNode,flagTmp);
  flagTmp.clear();

  //We draw the tree using a tree drawing algorithm
  bool resultBool;
  string erreurMsg;
  assert(mySGraph->isTree());
  LayoutProxy *tmpLayout=getLocalProxy<LayoutProxy>(mySGraph,"Hierarchical Tree (R-T Extended)",cached,resultBool,erreurMsg);
  //  cerr << "End Tree Walker box" << endl;
  assert(resultBool);
  Iterator<node> *itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    layoutProxy->setNodeValue(itn,tmpLayout->getNodeValue(itn));
  }
  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.front();
      listSelfLoops.pop_front();
      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);
  for (list<node>::const_iterator it=properAddedNodes.begin();it!=properAddedNodes.end();++it)
    mySGraph->delAllNode(*it);
  
  superGraph->delView(tmpSubGraph);
  return true;
}