#include "TreeReingoldAndTilford.h"
#include <tulip/LayoutProxy.h>
#include <tulip/MethodFactory.h>

LAYOUTPLUGIN(TreeReingoldAndTilford,"Hierarchical Tree (Reingold-Tilford)","David Auber","02/03/2003","Beta","0","2");

using namespace std;

TreeReingoldAndTilford::TreeReingoldAndTilford(PropertyContext *context):
  Layout(context),
  lengthMetric(0) {
}

TreeReingoldAndTilford::~TreeReingoldAndTilford() {}

int TreeReingoldAndTilford::calcDecal(const list<LR> &arbreG,const list<LR> &arbreD) {
  list<LR>::const_iterator itG,itD;
  int decal=0;
  int iG=0,iD=0;
  itG=arbreG.begin();
  itD=arbreD.begin();
  decal = ((*itG).R-(*itD).L + 1);
  iG+= (itG->size < itD->size) ? itG->size : itD->size;
  iD+= (itG->size < itD->size) ? itG->size : itD->size;
  if (iG==(*itG).size) {
    ++itG;iG=0;
  }
  if (iD==(*itD).size) {
    ++itD;iD=0;
  }
  while ((itG!=arbreG.end()) && (itD!=arbreD.end())) {
    decal = (decal > (itG->R - itD->L+1)) ? decal : (itG->R - itD->L+1);
    int min= ((itG->size - iG) < (itD->size-iD)) ? (itG->size - iG) : (itD->size-iD);
    iG+=min;
    iD+=min;
    if (iG==(*itG).size) {
      ++itG;iG=0;
    }
    if (iD==(*itD).size) {
      ++itD;iD=0;
    }
  }
  return decal;
}

list<LR>* TreeReingoldAndTilford::mergeLRList(list<LR>*L,list<LR>*R,int decal) {
  assert (L!=NULL);assert (R!=NULL);
  //  list<LR> *newContour=new list<LR>();
  list<LR>::iterator itL,itR;
  int iL=0,iR=0;
  itL=L->begin();itR=R->begin();
  LR tmp;
  while((itL!=L->end()) && (itR!=R->end())) {
    tmp.L=(*itL).L;
    tmp.R=(*itR).R+decal;
    int min = ((itL->size-iL) < (itR->size-iR)) ? (itL->size-iL) : (itR->size-iR);
    tmp.size=min;

    if ((*itL).size==1) { //start
      (*itL)=tmp;
    } 
    else {
      if (iL==0) {
	if (iL+min>=(*itL).size) //block
	  (*itL)=tmp;
	else {
	  L->insert(itL,tmp);
	  (*itL).size-=min;
	  iL=-min;
	}
      }
      else {
	if (iL+min>=(*itL).size) { //end
	  (*itL).size-=min;
	  ++itL;
	  L->insert(itL,tmp);
	  iL=-min;
	} 
	else { //middle
	  LR tmp2=*itL;
	  (*itL).size=iL;
	  ++itL;
	  L->insert(itL,tmp);
	  tmp2.size-=iL+min;
	  L->insert(itL,tmp2);
	  --itL;
	  iL=-min;
	}
      }
    }
    
    iL+=min;
    iR+=min;
    
    if (iL>=(*itL).size) {
      ++itL;iL=0;
    }
    if (iR>=(*itR).size) {
      ++itR;iR=0;
    }
  }
  if (itL!=L->end()) {
    if (iL!=0) {
      tmp.L=(*itL).L;
      tmp.R=(*itL).R;
      tmp.size=(*itL).size-iL;
      ++itL;
    }
  }
  if (itR!=R->end()) {
    if (iR!=0) {
      tmp.L=(*itR).L+decal;
      tmp.R=(*itR).R+decal;
      tmp.size=(*itR).size-iR;
      L->push_back(tmp);
      ++itR;
    }
    for (;itR!=R->end();++itR) {
      tmp.L=(*itR).L+decal;
      tmp.R=(*itR).R+decal;
      tmp.size=(*itR).size;
      L->push_back(tmp);
    }
  }
  return L;
}

list<LR> * TreeReingoldAndTilford::TreePlace(node n ,IntProxy *p) {
  if (superGraph->outdeg(n)==0) {
    list<LR> *result=new list<LR>();
    LR tmpLR;
    tmpLR.L=0;
    tmpLR.R=0;
    tmpLR.size=1;
    (*p).setNodeValue(n,0);
    result->push_front(tmpLR);
    return (result);
  }
  else {
    Iterator<edge> *it=superGraph->getOutEdges(n);
    edge ite=it->next();
    node itn=superGraph->target(ite);
    list<LR> *leftTree,*rightTree;
    list<int> childPos;
    leftTree=TreePlace(itn,p);
    childPos.push_back((*(leftTree->begin())).L);
    if (lengthMetric!=0) {
      int tmp=lengthMetric->getEdgeValue(ite);
      if (tmp>1) 
	(*leftTree->begin()).size+=tmp-1;
    }
    for (;it->hasNext();) {
      ite=it->next();
      itn=superGraph->target(ite);
      rightTree=TreePlace(itn,p);
      if (lengthMetric!=0) {
	int tmp=lengthMetric->getEdgeValue(ite);
	if (tmp>1) 
	  (*rightTree->begin()).size+=tmp-1;
      }
      int decal=calcDecal(*leftTree,*rightTree);
      int tmpL=(*(rightTree->begin())).L;
      mergeLRList(leftTree,rightTree,decal);
      delete rightTree;
      childPos.push_back(tmpL+decal);
    }delete it;
    
    int posFather=(int)rint((((*(leftTree->begin())).L+(*(leftTree->begin())).R)/2));
    LR tmpLR;
    tmpLR.L=posFather;
    tmpLR.R=posFather;
    tmpLR.size=1;
    leftTree->push_front(tmpLR);
    
    list<int>::const_iterator itI=childPos.begin();
    Iterator<node> *itN=superGraph->getOutNodes(n);
    for (;itN->hasNext();){
      itn=itN->next();
      (*p).setNodeValue(itn,*itI-posFather);
      ++itI;
    }delete itN;
    
    (*p).setNodeValue(n,0);
    childPos.clear();
    return(leftTree);
  }
}

void TreeReingoldAndTilford::calcLayout(node n,IntProxy *p,int x, int y) {
  layoutProxy->setNodeValue(n,Coord(x+(*p).getNodeValue(n),y,0));
  if (lengthMetric!=0) {
    Iterator<edge> *it=superGraph->getOutEdges(n);
    for (;it->hasNext();){
      edge ite=it->next();
      node itn=superGraph->target(ite);
      calcLayout(itn,p,x+(*p).getNodeValue(n),y+(2*lengthMetric->getEdgeValue(ite)));
    }delete it;
  }
  else {
    Iterator<node> *it=superGraph->getOutNodes(n);
    for (;it->hasNext();){
      node itn=it->next();
      calcLayout(itn,p,x+(*p).getNodeValue(n),y+2);
    }delete it;
  }
}

bool TreeReingoldAndTilford::run() {
  IntProxy *posRelative=getLocalProxy<IntProxy>(superGraph,"posRel");
  layoutProxy->setAllEdgeValue(vector<Coord>(0));
  getLocalProxy<SizesProxy>(superGraph,"viewSize")->setAllNodeValue(Size(1,1,1));
  getLocalProxy<SizesProxy>(superGraph,"viewSize")->setAllEdgeValue(Size(0.125,0.125,0.5));
  Iterator<node> *it=superGraph->getNodes();
  node startNode=it->next();
  for (;it->hasNext();) {
    node itn=it->next();
    if (superGraph->indeg(itn)==0){
      startNode=itn;
      break;
    }
  }delete it;

  if (superGraph->getPropertyProxyContainer()->existProxy("treeEdgeLength"))
    lengthMetric=getProxy<IntProxy>(superGraph,"treeEdgeLength");
  
  list<LR> *tmpList=TreePlace(startNode,posRelative);
  delete tmpList;
  calcLayout(startNode,posRelative,0,0);
  superGraph->getPropertyProxyContainer()->delLocalProxy("posRel");
  return true;
}

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

void TreeReingoldAndTilford::reset(){}