#include "TreeReingoldOrtho.h"

#define minDecal 1.0

LAYOUTPLUGIN(TreeReingoldOrhto,"Hierarchical Tree (Orthogonal)","David Auber","06/12/2002","Alpha","0","1")

using namespace std;

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

TreeReingoldOrhto::~TreeReingoldOrhto() {}

double TreeReingoldOrhto::calcDecal(const list<LR> &arbreG,const list<LR> &arbreD) {
  list<LR>::const_iterator itG,itD;
  double decal=0;
  double dG,dD;
  itG=arbreG.begin();
  itD=arbreD.begin();
  decal = (*itG).R-(*itD).L + minDecal;
  dG=(*itD).L;
  dD=(*itG).R;
  ++itG;++itD;
  while ((itG!=arbreG.end()) && (itD!=arbreD.end())) {
    if (decal+(*itD).L<=(*itG).R)
      decal=(*itG).R-((*itD).L)+minDecal;
    ++itG;++itD;
  }
  return decal;
}

list<LR> * TreeReingoldOrhto::mergeLRList(list<LR>*L,list<LR>*R,double decal) {
  list<LR>::iterator itL,itR;
  assert (L!=NULL);
  assert (R!=NULL);
  itL=L->begin();
  itR=R->begin();
  if (L->size()>=R->size()) {
    while((itL!=L->end()) && (itR!=R->end())){
      (*itL).R=(*itR).R+decal;
      ++itL;++itR;
    }
    return L;
  }
  else {
    while((itL!=L->end()) && (itR!=R->end())){
      (*itR).L=(*itL).L-decal;
      ++itL;++itR;
    }
    return R;
  }
}

struct LessThanNodos {
  MetricProxy *metric;
  bool operator() (node n1,node n2) {
    return (metric->getNodeValue(n1) < metric->getNodeValue(n2));
  } 
};

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

template<typename T> struct stlListIterator:public Iterator<T>{
  typename list<T>::iterator &it, itEnd;
  stlListIterator(typename list<T>::iterator &startIt, typename list<T>::iterator endIt):it(startIt),itEnd(endIt){}
  T next(){T tmp=*it;++it;return tmp;}
  bool hasNext(){return (itEnd!=it);}
};


/**
   Compute recursively by using two countours the absolute position of each node.
 */
list<LR> * TreeReingoldOrhto::TreePlace(node n, STL_EXT_NS::hash_map<node,double> *p) {
  list<edge> tmp;
  list<edge>::iterator tmpIt;
  LessThanEdgos lessEdge;
  if (superGraph->outdeg(n)==0){
    list<LR> *result=new list<LR>();
    LR tmpLR;
    tmpLR.L=-sizesProxy->getNodeValue(n).getH()/2;
    tmpLR.R=+sizesProxy->getNodeValue(n).getH()/2;
    (*p)[n]=0;
    result->push_front(tmpLR);
    return (result);
  }
  else
    {
      Iterator<edge> *it;
      if (superGraph->getPropertyProxyContainer()->existProxy("TreeReingoldOrhtoOrder")) {
	Iterator<edge> *it2=superGraph->getOutEdges(n);
	for (;it2->hasNext();) { tmp.push_back(it2->next());
	}delete it2;
	lessEdge.metric=getProxy<MetricProxy>(superGraph,"TreeReingoldOrhtoOrder");
	lessEdge.sg=superGraph;
	tmp.sort(lessEdge);
	tmpIt=tmp.begin();
	it=new stlListIterator<edge>(tmpIt,tmp.end());
      }
      else
	it=superGraph->getOutEdges(n);
      
      edge ite=it->next();
      node itn=superGraph->target(ite);
      
      list<LR> *leftTree,*rightTree;
      list<double> childPos;
      leftTree=TreePlace(itn,p);
      childPos.push_back( ( (*(leftTree->begin())).L + (*(leftTree->begin())).R )/2);
      if (superGraph->getPropertyProxyContainer()->existProxy("TreeWalkerEdgeLength")) {
	double tmpLength;
	IntProxy *lengthMetric=getProxy<IntProxy>(superGraph,"TreeWalkerEdgeLength");
	if ((tmpLength=lengthMetric->getEdgeValue(ite))>1) {
	  LR tmpLR;
	  tmpLR.L=leftTree->front().L;
	  tmpLR.R=leftTree->front().R;
	  while (tmpLength>1) {
	    leftTree->push_front(tmpLR);
	    tmpLength--;
	  }
	}
      }
      for (;it->hasNext();){
	ite=it->next();
	itn=superGraph->target(ite);
	rightTree=TreePlace(itn,p);
	if (superGraph->getPropertyProxyContainer()->existProxy("TreeWalkerEdgeLength")) {
	  double tmpLength;
	  IntProxy *lengthMetric=getProxy<IntProxy>(superGraph,"TreeWalkerEdgeLength");
	  if ((tmpLength=lengthMetric->getEdgeValue(ite))>1) {
	    LR tmpLR;
	    tmpLR.L=rightTree->front().L;
	    tmpLR.R=rightTree->front().R;
	    while (tmpLength>1) {
	      rightTree->push_front(tmpLR);
	      tmpLength--;
	    }
	  }
	}
	double decal=calcDecal(*leftTree,*rightTree);
	double tmpL= ((*(rightTree->begin())).L + (*(rightTree->begin())).R )/2;
	if (mergeLRList(leftTree,rightTree,decal)==leftTree) {
	  childPos.push_back(tmpL+decal);
	  delete rightTree;
	}
	else {
	  list<double>::iterator itI=childPos.begin();
	  for(;itI!=childPos.end();++itI) (*itI)-=decal;
	  childPos.push_back(tmpL);
	  delete leftTree;
	  leftTree=rightTree;
	}
      }delete it;
      double posFather=((((*(leftTree->begin())).L+(*(leftTree->begin())).R)/2));
      LR tmpLR;
      tmpLR.L=posFather-sizesProxy->getNodeValue(n).getH()/2;
      tmpLR.R=posFather+sizesProxy->getNodeValue(n).getH()/2;
      leftTree->push_front(tmpLR);

      list<double>::const_iterator itI=childPos.begin();
      if (superGraph->getPropertyProxyContainer()->existProxy("TreeReingoldOrhtoOrder")) {
	tmpIt=tmp.begin();
	it=new stlListIterator<edge>(tmpIt,tmp.end());
      }
      else
	it=superGraph->getOutEdges(n);
      
      for (;it->hasNext();) {
	ite=it->next();
	itn=superGraph->target(ite);
	(*p)[itn]=*itI-posFather;
	++itI;
      }delete it;
      childPos.clear();
      (*p)[n]=0;
      return(leftTree);
    }
}

/** 
    Compute the size of each layer, the algorithm take the maximum of each node in each level.
    Store the result in maxSize.
*/
void TreeReingoldOrhto::TreeLevelSizing(node n,map<int,double> &maxSize,int level,map<node,int> &levels)
{
  levels[n]=level;
  if (maxSize.find(level)!=maxSize.end()) {
    if (maxSize[level]<sizesProxy->getNodeValue(n).getW()) {
      maxSize[level]=sizesProxy->getNodeValue(n).getW();
    }
  }
  else
    maxSize[level]=sizesProxy->getNodeValue(n).getW();

  if (superGraph->getPropertyProxyContainer()->existProxy("TreeWalkerEdgeLength")) {
    IntProxy *lengthMetric=getProxy<IntProxy>(superGraph,"TreeWalkerEdgeLength");
    Iterator<edge> *it=superGraph->getOutEdges(n);
    for (;it->hasNext();) {
      edge ite=it->next();
      node itn=superGraph->target(ite);
      TreeLevelSizing(itn,maxSize,level+(lengthMetric->getEdgeValue(ite)),levels);
    }delete it;
  }
  else {
    Iterator<node> *itN=superGraph->getOutNodes(n);
    for (;itN->hasNext();) {
      node itn=itN->next();
      TreeLevelSizing(itn,maxSize,level+1,levels);
    }delete itN;
  }
}

/**
   Set final position of each node by using absolute position stored in p and the size of each level
   stored in maxLevelSize.
*/
void TreeReingoldOrhto::calcLayout(node n, STL_EXT_NS::hash_map<node,double> *p,double x, double y, int level ,map<int,double> &maxLevelSize)
{
  Coord tmpCoord;
  tmpCoord.set(-y-maxLevelSize[level]/2,x+(*p)[n],0);
  layoutProxy->setNodeValue(n,tmpCoord);
  if (superGraph->getPropertyProxyContainer()->existProxy("TreeWalkerEdgeLength")) {
    IntProxy *lengthMetric=getProxy<IntProxy>(superGraph,"TreeWalkerEdgeLength");
    Iterator<edge> *it=superGraph->getOutEdges(n);
    for (;it->hasNext();){
      edge ite=it->next();
      node itn=superGraph->target(ite);
      double decalY=y;
      int decalLevel=level;
      int tmp=lengthMetric->getEdgeValue(ite);
      while(tmp>0) {
	decalY+=maxLevelSize[decalLevel]+minDecal;
	decalLevel++;
	tmp--;
      }
      calcLayout(itn,p,x+(*p)[n],decalY , decalLevel, maxLevelSize);
    }delete it;
  }
  else {
    Iterator<node> *it=superGraph->getOutNodes(n);
    for (;it->hasNext();){
      node itn=it->next();
      calcLayout(itn,p, x+(*p)[n], y+maxLevelSize[level]+minDecal , level+1, maxLevelSize);
    }delete it;
    
  }
}

bool TreeReingoldOrhto::run() {
  STL_EXT_NS::hash_map<node,double> posRelative;
  list<LR> *tmpList;
  node startNode;
  layoutProxy->setAllEdgeValue(vector<Coord>(0));
  sizesProxy=getProxy<SizesProxy>(superGraph,"viewSize");
  Iterator<node> *it=superGraph->getNodes();
  IntProxy *lengthMetric=getProxy<IntProxy>(superGraph,"TreeWalkerEdgeLength");
  lengthMetric->setAllEdgeValue(2);
  node itn;
  startNode=it->next();
  for (;it->hasNext();){      
    itn=it->next();
    if (superGraph->indeg(itn)==0)
      {startNode=itn;break;}
  }delete it;
  map<int,double> maxSizeLevel;
  map<node,int> levels;
  TreeLevelSizing(startNode,maxSizeLevel,0,levels);
  delete TreePlace (startNode,&posRelative);
  //  delete tmpList;
  calcLayout(startNode,&posRelative,0,0,0,maxSizeLevel);


  //Edge bends
  //compute layer value

  map<int,double>::reverse_iterator itos= maxSizeLevel.rbegin();
  vector<double> levelCoord(itos->first+1);
  for (int i=0; i<itos->first;++i) {
    levelCoord[i]=0;
  }
  for (map<int,double>::iterator itas= maxSizeLevel.begin();itas!=maxSizeLevel.end();++itas) {
    levelCoord[itas->first]=itas->second;
  }

  for (int i=1; i<itos->first;++i) {
    levelCoord[i]+=levelCoord[i-1]+minDecal;
  }
  Iterator<edge> *itE=superGraph->getEdges();
  for (;itE->hasNext();) {
    edge ite=itE->next();
    LineType::RealType tmp=layoutProxy->getEdgeValue(ite);
    double y=levelCoord[levels[superGraph->target(ite)]-1];
    tmp.push_back(Coord(-y,layoutProxy->getNodeValue(superGraph->source(ite)).getY(), 0));
    tmp.push_back(Coord(-y,layoutProxy->getNodeValue(superGraph->target(ite)).getY(), 0));
    layoutProxy->setEdgeValue(ite,tmp);
  }delete itE;

  return true;
}

bool TreeReingoldOrhto::check(string &erreurMsg) {
  if (superGraph->isTree())
    {erreurMsg="";return true;}
  else
    {erreurMsg="The Graph must be a Tree";return false;}
}

void TreeReingoldOrhto::reset() {}