#include <map>
#include <cmath>
#include <climits>
#include <tulip/Circle.h>
#include "ConeTreeExtended.h"

LAYOUTPLUGIN(ConeTreeExtended,"Cone Tree Extended","David Auber","01/04/2001","Stable","1","0");

using namespace std;
/*
struct Circle {
  Circle(){}
  Circle(Coord pos,double rayon):pos(pos),rayon(rayon) {}
  Circle(const Circle &c) {pos=c.pos;rayon=c.rayon;}
  Coord pos;
  double rayon; 
};

Circle treatCircle(Circle &c1,const Circle &c2) {
  Coord c12=c2.pos-c1.pos;
  double norm=c12.norm();
  double dx=c12.getX()/norm;
  double dy=c12.getY()/norm;
  Coord p1(c1.pos);
  Coord p2(c2.pos);
  p1-=Coord(dx*c1.rayon,dy*c1.rayon,0);
  p2+=Coord(dx*c2.rayon,dy*c2.rayon,0);
  if ((p1.dist(p2)/2<c1.rayon)||(p1.dist(p2)/2<c2.rayon)) {
    if (c1.rayon>c2.rayon) return c1; else return c2;
  }
  else {
    return Circle((p1+p2)/2,p1.dist(p2)/2);
  }
}

Circle circleHull(vector<Circle> & circles) {
  //compute bounding box
  float boundingBox[4];
  for (int i=0;i<4;++i) boundingBox[i]=0;
  vector<Circle>::const_iterator it=circles.begin();
  Circle c(*it);
  boundingBox[0]=c.pos.getX()-c.rayon;
  boundingBox[1]=c.pos.getY()-c.rayon;
  boundingBox[2]=c.pos.getX()+c.rayon;
  boundingBox[3]=c.pos.getY()+c.rayon;
  ++it;
  for (;it!=circles.end();++it) {
    c=*it;
    boundingBox[0]=boundingBox[0] <? (c.pos.getX()-c.rayon);
    boundingBox[1]=boundingBox[1] <? (c.pos.getY()-c.rayon);
    boundingBox[2]=boundingBox[2] >? (c.pos.getX()+c.rayon);
    boundingBox[3]=boundingBox[3] >? (c.pos.getY()+c.rayon);
  }

  Coord center((boundingBox[0]+boundingBox[2])/2,(boundingBox[1]+boundingBox[3])/2,0);
  float radius=( (boundingBox[2]-boundingBox[0])/2 ) >? ( (boundingBox[3]-boundingBox[1])/2 );
  Circle result(center,radius);

  //compute circle hull
  for (vector<Circle>::const_iterator it=circles.begin();it!=circles.end();++it) {
    result=treatCircle(result,*it);
  }
  return result;
}
*/

float sqr(float x) { return x*x;}

float minRadius(float radius1,float alpha1,float radius2,float alpha2) {
  return sqrt(sqr(radius1+radius2)/(sqr(cos(alpha1)-cos(alpha2))+sqr(sin(alpha1)-sin(alpha2)))); 
}

static int progress=0;
static bool breakAlgorithm=false;


double ConeTreeExtended::treePlace3D(node n, 
				     STL_EXT_NS::hash_map<node,double> *posRelX, 
				     STL_EXT_NS::hash_map<node,double> *posRelY) {
  if (breakAlgorithm) return 0;
  progress++;
  if (progress%100==0) breakAlgorithm=!pluginProgress->progress(progress,2*superGraph->numberOfNodes());
  (*posRelX)[n]=0;
  (*posRelY)[n]=0;
  if (superGraph->outdeg(n)==0) {return 1.0;}

  if (superGraph->outdeg(n)==1) {
    Iterator<node> *itN=superGraph->getOutNodes(n);
    node itn=itN->next();
    delete itN;
    return treePlace3D(itn,posRelX,posRelY);
  }

  double sumRadius=0;
  double maxRadius=0;
  double newRadius;
  double minRadiusResult;

  std::vector<double> subCircleRadius(superGraph->outdeg(n));
  Iterator<node> *itN=superGraph->getOutNodes(n);
  for (int i=0;itN->hasNext();++i)  {
    node itn = itN->next();
    subCircleRadius[i] = treePlace3D(itn,posRelX,posRelY);
    sumRadius += 2*subCircleRadius[i];
    maxRadius = (maxRadius > subCircleRadius[i]) ? maxRadius : subCircleRadius[i];
  }delete itN;
  
  double radius=sumRadius/(2*M_PI);

  //  treat angles
  vector<double> vangles(subCircleRadius.size());
  double angle=0;
  vangles[0]=0;
  for (int i=1;i<subCircleRadius.size();++i) {
    angle+=(subCircleRadius[i-1]+subCircleRadius[i])/radius;
    vangles[i]=angle;
  }

  // compute new radius
  newRadius=0;
  for (int i=0;i<subCircleRadius.size()-1;++i) {
    //if (subCircleRadius[i]>1)
      for (int j=i+1;j<subCircleRadius.size();++j) {
         minRadiusResult = minRadius(subCircleRadius[i],vangles[i],subCircleRadius[j],vangles[j]);
         newRadius = (newRadius > minRadiusResult) ? newRadius : minRadiusResult;
      }
  }
  if (newRadius==0) newRadius=radius;
  //compute Circle Hull
  vector<tlp::geo::Circle<float> > circles(subCircleRadius.size());
  for (int i=0;i<subCircleRadius.size();++i) {
    tlp::geo::Vector<float,2> point;
    circles[i][0]=newRadius*cos(vangles[i]);
    circles[i][1]=newRadius*sin(vangles[i]);
    circles[i].radius=subCircleRadius[i];
    //    circles[i]=tlp::geo::Circle(Coord(newRadius*cos(vangles[i]),newRadius*sin(vangles[i]),0),subCircleRadius[i]);
  }
  tlp::geo::Circle<float> circleH=tlp::geo::enclosingCircle(circles);

  //Place relative position
  itN=superGraph->getOutNodes(n);
  for (int i=0;i<subCircleRadius.size();++i) {
    node itn = itN->next();
    (*posRelX)[itn]=newRadius*cos(vangles[i])-circleH[0];
    (*posRelY)[itn]=newRadius*sin(vangles[i])-circleH[1];
  }delete itN;
  return circleH.radius;
}

void ConeTreeExtended::calcLayout(node n, STL_EXT_NS::hash_map<node,double> *px, STL_EXT_NS::hash_map<node,double> *py,
			double x, double y, int level) {
  if (breakAlgorithm) return;
  progress++;
  if (progress%100==0) breakAlgorithm=!pluginProgress->progress(progress,2*superGraph->numberOfNodes());
  layoutProxy->setNodeValue(n,Coord(x+(*px)[n],level,y+(*py)[n]));
  Iterator<node> *it=superGraph->getOutNodes(n);
  for (;it->hasNext();) {
    node itn;
    itn=it->next();
    calcLayout(itn,px,py,x+(*px)[n],y+(*py)[n] , level+2);
  }delete it;
}

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

ConeTreeExtended::~ConeTreeExtended() {}

bool ConeTreeExtended::run() {
  breakAlgorithm=false;
  progress=0;
  breakAlgorithm=!pluginProgress->progress(0,2*superGraph->numberOfNodes());
  layoutProxy->setAllEdgeValue(vector<Coord>(0));
  STL_EXT_NS::hash_map<node,double> posX;
  STL_EXT_NS::hash_map<node,double> posY;
  getLocalProxy<SizesProxy>(superGraph,"viewSize")->setAllNodeValue(Size(1,1,1));
  getLocalProxy<SizesProxy>(superGraph,"viewSize")->setAllEdgeValue(Size(0.125,0.125,0.5));
  node startNode;
  Iterator<node> *itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    if (superGraph->indeg(itn)==0) {
      startNode=itn;
      break;
    }
  }delete itN;
    
  treePlace3D(startNode,&posX,&posY);
  calcLayout(startNode,&posX,&posY,0,0,0);
  if (!breakAlgorithm)
    return true;
  else
    return false;
}

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

void ConeTreeExtended::reset() {}