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

#include "Sugiyama.h"

LAYOUTPLUGIN(Sugiyama,"Sugiyama","David Auber","12/09/2002","Alpha","0","1");

using namespace std;

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

Sugiyama::~Sugiyama() {}

//Build the grid of node
void Sugiyama::buildGrid(SuperGraph *superGraph){
  //  cerr << "buildGrid" << endl;
  MetricProxy *dagLevel = getLocalProxy<MetricProxy>(superGraph,"DagLevel");
  Iterator<node> *itN=superGraph->getNodes();  
  for(;itN->hasNext();){
    node itn=itN->next();
    unsigned int level=(unsigned int)dagLevel->getNodeValue(itn);
    while (level>=grid.size()) grid.push_back(vector<node>());
    metricProxy->setNodeValue(itn,grid[level].size());
    grid[level].push_back(itn);
  }delete itN;
}

bool Sugiyama::assert_twoLayerCrossReduction(unsigned int freeLayer,bool sense){
  if (sense)
    return (grid.size()>freeLayer);
  else
    return (freeLayer>=0);
}

unsigned int Sugiyama::degree(SuperGraph *superGraph,node n,bool sense) {
  if (sense)
    return (superGraph->outdeg(n));
  else
    return (superGraph->indeg(n));
}

node Sugiyama::getOpposite(SuperGraph *superGraph,node n,bool sense) {
  cerr << "getOpposite" << endl;
  node result;
  if (sense)
    {Iterator<node> *itN=superGraph->getOutNodes(n);result=itN->next();delete itN;}
  else
    {Iterator<node> *itN=superGraph->getInNodes(n);result=itN->next();delete itN;}
  return result;
}

void Sugiyama::forceNoTwoLayerCross(SuperGraph *superGraph,unsigned int freeLayer,bool sense){
  STL_EXT_NS::hash_map<node,bool> freeNode(grid[freeLayer].size());
  unsigned int fixedLayer=(sense?freeLayer+1:freeLayer-1);
  unsigned posFixedLayer=0;
  for(unsigned int j=0;j<grid[freeLayer].size();++j) freeNode[grid[freeLayer][j]]=false;
  vector<node> newOrder;
  for(unsigned int j=0;j<grid[freeLayer].size();++j) {
    if (bends.find(grid[freeLayer][j])!=bends.end()) {

      if (freeNode[grid[freeLayer][j]]==false) {
	node itn=getOpposite(superGraph,grid[freeLayer][j],sense);
	if (bends.find(itn)!=bends.end()) {
	  while (grid[fixedLayer][posFixedLayer]!=itn) {
	    if (bends.find(grid[freeLayer][posFixedLayer])!=bends.end()) {
	      node itn2=getOpposite(superGraph,grid[freeLayer][posFixedLayer],sense);
	      if (bends.find(itn2)!=bends.end()) {
		newOrder.push_back(itn2);
		freeNode[itn2]=true;
	      }
	    }
	    posFixedLayer++;
	  }
	  newOrder.push_back(grid[freeLayer][j]);
	}
      }
    }
    else {
      newOrder.push_back(grid[freeLayer][j]);
    }
  }
  cerr << grid[freeLayer].size() << "," << newOrder.size() << endl;
  unsigned int j=0;
  for (vector<node>::const_iterator it=newOrder.begin();it!=newOrder.end();++it) {
    metricProxy->setNodeValue(*it,j);
    j++;
  }
}

//If sense==true fixed_layer is freeLayer+1 else freeLayer-1
void Sugiyama::twoLayerCrossReduction(SuperGraph *superGraph,unsigned int freeLayer,bool sense){
  //  cerr << "twoLayer" << endl;
  assert(assert_twoLayerCrossReduction(freeLayer,sense));
  vector<node>::const_iterator it;
  for (it=grid[freeLayer].begin();it!=grid[freeLayer].end();++it) {
    node n=*it;
    if (degree(superGraph,n,sense)>0) {
      double sum=0;
      Iterator<node>*itN;
      if (sense) 
	itN=superGraph->getOutNodes(n);
      else
	itN=superGraph->getInNodes(n);
      for(;itN->hasNext();) {
	node itn=itN->next();
	sum+=metricProxy->getNodeValue(itn);
      }delete itN;
      metricProxy->setNodeValue(n,sum/(double)degree(superGraph,n,sense));
    }
  }
  stable_sort(grid[freeLayer].begin(),grid[freeLayer].end(),lessNode);
  unsigned int j=0;
  for (it=grid[freeLayer].begin();it!=grid[freeLayer].end();++it) {
    metricProxy->setNodeValue(*it,j);
    j++;
  }
}



void Sugiyama::initCross(SuperGraph *superGraph,node n, STL_EXT_NS::hash_map<node,bool> &visited,int &id) {
  if (visited[n]) return;
  id++;
  visited[n]=true;
  metricProxy->setNodeValue(n,id);
  Iterator<node> *itN=superGraph->getOutNodes(n);
  for (;itN->hasNext();){
    node itn=itN->next();
    initCross(superGraph,itn,visited,id);
  }delete itN;
}


void Sugiyama::crossReduction(SuperGraph *superGraph){
  STL_EXT_NS::hash_map<node,bool> visited(superGraph->numberOfNodes());
  int id=1;
  Iterator<node> *itN=superGraph->getNodes();
  for (;itN->hasNext();){
    node itn=itN->next();
    if (superGraph->indeg(itn)==0) initCross(superGraph,itn, visited,id);
  }delete itN;

  itN=superGraph->getNodes();
  for (;itN->hasNext();){
    node itn=itN->next();
    initCross(superGraph,itn,visited,id);
  }delete itN;


  //cerr << "crossReduc" << endl;
  unsigned int maxDepth=grid.size();
  //Iterations of the sweeping
  for (int a=0;a<4;++a) {
    //Down sweeping
    for (unsigned int i=0;i<maxDepth;++i) {
      twoLayerCrossReduction(superGraph,i,false);
      //      forceNoTwoLayerCross(superGraph,i,false);
    }
    //Up sweeping
    for (int i=maxDepth-1;i>=0;--i) {
      twoLayerCrossReduction(superGraph,i,true);
      //      forceNoTwoLayerCross(superGraph,i,true);
    }
  }
}

void Sugiyama::makeAcyclic(SuperGraph* superGraph,set<edge> &reversed,list<SelfLoops> &selfLoops) {
  //cerr << "makeAcyclic" << 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 << "Error Sugiyama::makeAcyclic =>" << erreurMsg; return;}
    
    //save 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>::const_iterator itSelf;
    for (itSelf=selfLoops.begin();itSelf!=selfLoops.end();++itSelf) {
      superGraph->delEdge((*itSelf).oldEdge);
    }
  }
  assert(superGraph->isAcyclic());
}


void Sugiyama::makeProperDag(SuperGraph* superGraph,list<node> &addedNodes, STL_EXT_NS::hash_map<edge,edge> &replacedEdges)
{
  //cerr << "makeProper" << endl;
  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 << "Error Sugiyama::makeProperDag =>" << erreurMsg << endl; return;}
  //we now transform the dag in a proper Dag, two linked nodes of a proper dag
  //must have a difference of one in dag level metric.
  node tmp1,tmp2;
  //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;
  
  for (vector<edge>::const_iterator itEdge=graphEdges.begin();itEdge!=graphEdges.end();++itEdge) {
    edge ite=*itEdge;
    double delta=dagLevel->getNodeValue(superGraph->target(ite))-dagLevel->getNodeValue(superGraph->source(ite));
    double levelStartNode=dagLevel->getNodeValue(superGraph->source(ite))+1;
    if (delta>1) {
      tmp1=superGraph->addNode();
      dagLevel->setNodeValue(tmp1,levelStartNode);
      levelStartNode++;
      //store only the first replaced edges
      replacedEdges[ite]=superGraph->addEdge(superGraph->source(ite),tmp1);
      addedNodes.push_back(tmp1);
      bends[tmp1]=pair<node,node>(superGraph->source(ite),superGraph->target(ite));
      while (delta>2) {
	tmp2=superGraph->addNode();
	dagLevel->setNodeValue(tmp2,levelStartNode);
	bends[tmp2]=pair<node,node>(superGraph->source(ite),superGraph->target(ite));
	levelStartNode++;
	addedNodes.push_back(tmp2);
	superGraph->addEdge(tmp1,tmp2);
	tmp1=tmp2;
	delta--;
      }
      superGraph->addEdge(tmp1,superGraph->target(ite));
    }
  }
  for (STL_EXT_NS::hash_map<edge,edge>::iterator it=replacedEdges.begin();it!=replacedEdges.end();++it) {
    superGraph->delEdge((*it).first);
  }
  assert(superGraph->isAcyclic());
}



void Sugiyama::minimize(SuperGraph* superGraph, STL_EXT_NS::hash_map<node,double> &xcoord,double maxX,bool bary) {

  for (unsigned int i=0;i<grid.size();++i)
    for (unsigned int j=0;j<grid[i].size();++j) {

      double leftx,rightx;
      if (j>0) leftx=xcoord[grid[i][j-1]]; else 
	{
	  if (xcoord[grid[i][j]]>0) leftx=0; else leftx=xcoord[grid[i][j]]-1;
	}
      if (j+1 < grid[i].size()) rightx=xcoord[grid[i][j+1]]; else
	{
	  if (xcoord[grid[i][j]]<maxX*2) rightx=maxX*2; else rightx=xcoord[grid[i][j]]+1;
	}
      double sum=0;

      //      if (bends.find(grid[i][j])!=bends.end()) {
      //	sum=(xcoord[bends[grid[i][j]].first]+xcoord[bends[grid[i][j]].second])/2;
      //      }
      //      else {
      if (superGraph->deg(grid[i][j])>0) {
	double max=-10000;
	double min=10000;
	Iterator<node> *itN=superGraph->getInOutNodes(grid[i][j]);
	for (;itN->hasNext();) {
	  node itn=itN->next();
	  sum+=xcoord[itn];
	  if (xcoord[itn]>max) max=xcoord[itn];
	  if (xcoord[itn]<min) min=xcoord[itn];
	}delete itN;
	if (bary)
	  sum/=(double)superGraph->deg(grid[i][j]);
	else
	  sum=(max+min) /2.0;
      } 
      else {
	//	cerr << "." << flush;
	sum=(leftx+rightx) / 2;
      }
      //}
      //cerr << "old:" << xcoord[grid[i][j]] << " leftx:" << leftx << " rightx:" << rightx << " sum:" << sum;
      sum=rint(sum);
      double sum2=xcoord[grid[i][j]];
      if (rightx-leftx > 2) {
	if ((sum<rightx-1) && (sum>leftx+1))
	  sum2=sum;
	else
	  {
	    if (rightx<sum && (rightx-1>leftx+1)) sum2=rightx-1;
	    if (sum<leftx && (leftx+1<rightx-1)) sum2=leftx+1; 
	  }
      }
      //      cerr << " sum2:" << sum2 << endl;
      xcoord[grid[i][j]]=sum2;
    }
}

void Sugiyama::forceAlignBends(SuperGraph* superGraph, STL_EXT_NS::hash_map<node,double> &xcoord,bool sense) {
  for (unsigned int i=0;i<grid.size();++i) {
    if (sense) {
      for (unsigned int j=0;j<grid[i].size();++j) {
	if (bends.find(grid[i][j])!=bends.end()) {
	  double newpos;
	  node itn;
	  Iterator<node> *itN=superGraph->getInNodes(grid[i][j]);
	  for (;itN->hasNext();) {
	    itn=itN->next();
	    newpos=xcoord[itn];
	  }delete itN;
	  if (bends.find(itn)!=bends.end()) {
	    if (newpos>xcoord[grid[i][j]]) {
	      double delta=newpos - xcoord[grid[i][j]];
	      for (unsigned int k=j;k<grid[i].size();++k){
		xcoord[grid[i][k]]+=delta;
		if (k+1<grid[i].size()) {
		  double tmp=xcoord[grid[i][k+1]]-xcoord[grid[i][k]];
		  if (tmp<1)  delta=1-tmp; else delta=0;
		}
	      }
	    }
	  }
	}
      }
    }
    else {
      for (int j=(int)grid[i].size()-1;j>=0;--j) {
	if (bends.find(grid[i][j])!=bends.end()) {
	  double newpos;
	  node itn;
	  Iterator<node> *itN=superGraph->getInNodes(grid[i][j]);
	  for (;itN->hasNext();) {
	    itn=itN->next();
	    newpos=xcoord[itn];
	  }delete itN;
	  if (bends.find(itn)!=bends.end()) {
	    if (newpos<xcoord[grid[i][j]]) {
	      double delta=newpos-xcoord[grid[i][j]];
	      for (int k=j;k>=0;--k){
		xcoord[grid[i][k]]+=delta;
		if (k-1>0) {
		  double tmp=xcoord[grid[i][k]]-xcoord[grid[i][k-1]];
		  if (tmp<1) delta=tmp-1; else delta=0;
		}
	      }
	    }
	  }
	}
      }
    }
  }
}

void Sugiyama::coordAssign(SuperGraph* superGraph,LayoutProxy *layout){
  // cerr << "coordAssign" << endl;
  unsigned int i,j;
  unsigned int maxX=0;
  STL_EXT_NS::hash_map<node,double> xcoord;
  STL_EXT_NS::hash_map<node,double> xcoord2;
  bool bary=false;
  int maxiter=5;

  for (i=0;i<grid.size();++i) {
    if (maxX<grid[i].size()) maxX=grid[i].size();
    for (j=0;j<grid[i].size();++j) {
      xcoord[grid[i][j]]=j;
    }
  }

  for (int iter=0;iter<maxiter;++iter) {
    if (iter<maxiter/4) bary=true; else bary=false;
    minimize(superGraph,xcoord,maxX,bary);
  }


  for (i=0;i<grid.size();++i) {
    for (j=0;j<grid[i].size();++j) {
      xcoord2[grid[i][j]]=(double)maxX*2.0-grid[i].size()+j;
    }
  }

  for (int iter=0;iter<maxiter;++iter) {
    if (iter<maxiter/4) bary=true; else bary=false;
    minimize(superGraph,xcoord2,maxX,bary);
  }

  for (i=0;i<grid.size();++i) {
    for (j=0;j<grid[i].size();++j) 
      xcoord2[grid[i][j]]=(xcoord[grid[i][j]]+xcoord2[grid[i][j]])/2;
  }
  forceAlignBends(superGraph,xcoord2,true);
  forceAlignBends(superGraph,xcoord2,false);

  for (i=0;i<grid.size();++i) {
    for (j=0;j<grid[i].size();++j) 
      layout->setNodeValue(grid[i][j],Coord(xcoord2[grid[i][j]],i,0));
  }
}

bool Sugiyama::run()
{
  //=======================================================================
  // Build a clone of this graph
  SelectionProxy *tmpSel=getLocalProxy<SelectionProxy>(superGraph,"TmpSel");
  tmpSel->setAllNodeValue(true);
  tmpSel->setAllEdgeValue(true);
  SubGraph *tmpSubGraph=superGraph->addView("tmpView",tmpSel);
  SuperGraph *mySGraph=tmpSubGraph->getAssociatedSuperGraph();
  superGraph->getPropertyProxyContainer()->delLocalProxy("TmpSel");
  metricProxy=getLocalProxy<MetricProxy>(superGraph,"tmpMetric");
  lessNode.metric=metricProxy;
  //========================================================================
  //if the graph is not acyclic we reverse edges to make it acyclic
  list<SelfLoops> listSelfLoops;
  set<edge> reversedEdges;
  makeAcyclic(mySGraph,reversedEdges,listSelfLoops);

  //We transform the dag in a proper dag
  list<node> properAddedNodes;
  STL_EXT_NS::hash_map<edge,edge> replacedEdges;
  makeProperDag(mySGraph,properAddedNodes,replacedEdges);

  //buildTheGrid
  buildGrid(mySGraph);
  //reduce crossings
  crossReduction(mySGraph);

  LayoutProxy *tmpLayout=getLocalProxy<LayoutProxy>(mySGraph,"tmplayout");
  //coordinatesAssignement
  coordAssign(mySGraph,tmpLayout);
  //


  //Restore the graph
  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("viewSize");
  getLocalProxy<SizesProxy>(superGraph,"viewSize")->setAllNodeValue(Size(0.5,0.5,0.5));
  for (set<edge>::const_iterator it=reversedEdges.begin();it!=reversedEdges.end();++it) {
    superGraph->reverse(*it);
  }
  for (list<node>::const_iterator it=properAddedNodes.begin();it!=properAddedNodes.end();++it)
    mySGraph->delAllNode(*it);
  superGraph->delView(tmpSubGraph);
  return true;
}