#include <string>
#include <math.h> 

#include <tulip/MethodFactory.h>
#include <tulip/LayoutProxy.h>
#include <tulip/SelectionProxy.h>
#include <tulip/SubGraph.h>
#include <tulip/PropertyProxy.h>

#include "GEM.h"
// An implementation of the GEM layout algorithm, based on
// code by Arne Frick placed in the public domain.  See the
// GEM.h file for further details.

using namespace std;

#define MMIN(x,y)   ((x < y) ? (x) : (y))
#define MMAX(x,y)   ((x < y) ? (y) : (x))
#define MABS(v)     ((v > 0) ? (v) : (-(v)))

LAYOUTPLUGIN(GEM,"GEM (Frick)","David Duke","23/07/2001","Alpha","0","1")

GEM::GEM(PropertyContext *context) : Layout(context) 
{
    i_maxtemp      = IMAXTEMPDEF;
    a_maxtemp      = AMAXTEMPDEF;
    o_maxtemp      = OMAXTEMPDEF;
    i_starttemp    = ISTARTTEMPDEF;
    a_starttemp    = ASTARTTEMPDEF;
    o_starttemp    = OSTARTTEMPDEF;
    i_finaltemp    = IFINALTEMPDEF;
    a_finaltemp    = AFINALTEMPDEF;
    o_finaltemp    = OFINALTEMPDEF;
    i_maxiter      = IMAXITERDEF;
    a_maxiter      = AMAXITERDEF;
    o_maxiter      = OMAXITERDEF;
    i_gravity      = IGRAVITYDEF;
    i_oscillation  = IOSCILLATIONDEF;
    i_rotation     = IROTATIONDEF;
    i_shake        = ISHAKEDEF;
    a_gravity      = AGRAVITYDEF;
    a_oscillation  = AOSCILLATIONDEF;
    a_rotation     = AROTATIONDEF;
    a_shake        = ASHAKEDEF;
    o_gravity      = OGRAVITYDEF;
    o_oscillation  = OOSCILLATIONDEF;
    o_rotation     = OROTATIONDEF;
    o_shake        = OSHAKEDEF;
        
    Map = NULL;
        Q   = NULL;
}

GEM::~GEM()
{}


int GEM::select() 
{
  int    u, n, v;

  if (Iteration == 0) 
    {
      if (Map) delete [] Map;
      Map = new int[NodeCount];
      for (int i = 0; i < NodeCount; i++)
	Map[i] = i;
    }
  n = NodeCount - (Iteration % NodeCount);
  v = rand () % n;  // was 1 + rand() % n due to numbering in GEM
  if (v == NodeCount) v--;
  if (n == NodeCount) n--;
  u = Map[v]; Map[v] = Map[n]; Map[n] = u;
  return u;
}

int GEM::bfs(int root) 
{
  vector<int>::iterator nodeSet;
  int v, ui;

  if (root >= 0) 
    {
      if (Q) delete Q;
      Q = new queue<int>();
      if (!GemProp[root].mark) 
	for (int vi = 0; vi < NodeCount; vi++)
	  GemProp[vi].in = 0;
      else
	GemProp[root].mark = true;
      Q->push(root);
      GemProp[root].in = 1;
    }
  if (Q->size() == 0)
    return -1;          // null
  v = Q->front();
  Q->pop();
  nodeSet = Adjacent[v].begin();
  while (nodeSet < Adjacent[v].end()) 
    {
      ui = *nodeSet++;
      if (GemProp[ui].in != 0) 
	{
	  Q->push(ui);
	  GemProp[ui].in = GemProp[v].in + 1;
	}
    }
  return v;
}

int GEM::graph_center() {
  int  c, u, v, w;    // nodes
  int  h;

  c = -1;           // for a contented compiler.
  u = -1;

  h = NodeCount + 1;
  for (w = 0; w < NodeCount; w++) {
    v = this->bfs(w);
    while (v >= 0 && GemProp[v].in < h) {
      u = v;
      v = this->bfs(-1);  // null
    }
    if (GemProp[u].in < h) {
      h = GemProp[u].in;
      c = w;
    }
  }
  return c;
}

void GEM::vertexdata_init(const float starttemp) {
  GEMparam *gemP;

  Temperature = 0;
  Center.x = 0;
  Center.y = 0;

  for (int v = 0; v < NodeCount; v++) {
    gemP = GemProp + v;
    gemP->heat = starttemp * ELEN;
    Temperature += (long)(gemP->heat * gemP->heat);
    gemP->imp.x = gemP->imp.y = 0;
    gemP->dir  = 0;
    gemP->mass = 1 + gemP->mass / 3;
    Center.x += gemP->pos.x;
    Center.y += gemP->pos.y;
  }
}


GEM::Vector GEM::i_impulse(int v) {
  vector<int>::iterator nodeSet;

  Vector i, d, p;
  long int n;
  int u;
  GEMparam *gemP, *gemQ;

  gemP = GemProp + v;
  p = gemP->pos;

  n  = (long)(i_shake * ELEN);
  i.x = rand () % (2 * n + 1) - n;
  i.y = rand () % (2 * n + 1) - n;
  i.x += (long)((Center.x / NodeCount - p.x) * gemP->mass * i_gravity);
  i.y += (long)((Center.y / NodeCount - p.y) * gemP->mass * i_gravity);

  for (int u = 0; u < NodeCount; u++) {
    gemQ = GemProp + u;
    if (gemQ->in > 0) {
      d.x = p.x - gemQ->pos.x;
      d.y = p.y - gemQ->pos.y;
      n = d.x * d.x + d.y * d.y;
      if (n) {
	i.x += d.x * ELENSQR / n;
	i.y += d.y * ELENSQR / n;
      }
    }
  }
  nodeSet = Adjacent[v].begin();
  while (nodeSet < Adjacent[v].end()) {
    u = *nodeSet++;
    gemQ = GemProp + u;
    if (gemQ->in > 0) {
      d.x = p.x - gemQ->pos.x;
      d.y = p.y - gemQ->pos.y;
      n = (long)((d.x * d.x + d.y * d.y) / gemP->mass);
      n = MMIN(n, MAXATTRACT);  //   1048576L
      i.x -= (long)(d.x * n / ELENSQR);
      i.y -= (long)(d.y * n / ELENSQR);
    }
  }    
  return i;
}

void GEM::insert() {
  vector<int>::iterator nodeSet2;
  GEMparam *gemP, *gemQ;
  int startNode;
  int     u, v, w;
  int        d;

  this->vertexdata_init(i_starttemp);

  Oscillation = i_oscillation;
  Rotation    = i_rotation;
  Maxtemp     = (long)(i_maxtemp * ELEN);

  v = this->graph_center();

  for (int ui = 0; ui < NodeCount; ui++)
    GemProp[ui].in = 0;
  GemProp[v].in = -1;

  startNode = -1;
  for (int i = 0; i < NodeCount; i++) {
    if (!pluginProgress->progress(i,NodeCount)) return;
    d = 0;
    for (int j = 0; j < NodeCount; j++)
      if (GemProp[j].in < d) {
	d = GemProp[j].in;
	v = j;
      }
    GemProp[v].in = 1;

    nodeSet2 = Adjacent[v].begin();
    while (nodeSet2 < Adjacent[v].end()) {
      u = *nodeSet2++;
      if (GemProp[u].in <= 0)
	GemProp[u].in--;
    }
    gemP = GemProp + v;
    gemP->pos.x = gemP->pos.y = 0;

    if (startNode >= 0) {
      d = 0;
      gemP = GemProp + v;
      nodeSet2 = Adjacent[v].begin();
      while (nodeSet2 < Adjacent[v].end()) {
	w = *nodeSet2++;
	gemQ = GemProp + w;
	if (gemQ->in > 0) {
	  gemP->pos.x += gemQ->pos.x;
	  gemP->pos.y += gemQ->pos.y;
	  d++;
	}
      }
      if (d > 1) {
	gemP->pos.x /= d;
	gemP->pos.y /= d;
      }
      d = 0;
      while ((d++ < i_maxiter) && (gemP->heat > i_finaltemp * ELEN)) 
	this->displace( v, this->i_impulse(v));
    }
    else
      startNode = i;
  }
}

void GEM::displace(int v, Vector imp) {
  long int t, n;
  GEMparam *gemP;

  if (imp.x != 0 || imp.y != 0) {
    n = MMAX( labs(imp.x), labs(imp.y)) / 16384L;
    if (n > 1) {
      imp.x /= n;
      imp.y /= n;
    }
    gemP = GemProp + v;
    t  = (long)(gemP->heat);
    n  = (long)sqrt((long double)(imp.x*imp.x + imp.y*imp.y));
    imp.x = imp.x * t / n;
    imp.y = imp.y * t / n;
    gemP->pos.x += imp.x;
    gemP->pos.y += imp.y;
    Center.x += imp.x;
    Center.y += imp.y;

    n = t * (long)sqrt((long double) (gemP->imp.x*gemP->imp.x + 
				      gemP->imp.y*gemP->imp.y));
    if (n) {
      Temperature -= t * t;
      t += (long)(t * Oscillation * 
		  (imp.x * gemP->imp.x + imp.y * gemP->imp.y) / n);
      t = MMIN(t, Maxtemp);
      gemP->dir += Rotation * 
	(imp.x * gemP->imp.y - imp.y * gemP->imp.x) / n;
      t -= (long)(t * MABS(gemP->dir) / NodeCount);
      t = MMAX(t, 2L);
      Temperature += t * t;
      gemP->heat = t;
    }
    gemP->imp = imp;
  }
}


void GEM::a_round() {
  vector<int>::iterator nodeSet;
  int u, v;
  Vector imp, d, pos;
  long int    n;
  GEMparam *gemP, *gemQ;

  for (int i = 0; i < NodeCount; i ++) {
    v = this->select();
    gemP = GemProp + v;

    pos = gemP->pos;

    n = (long)(a_shake * ELEN);
    imp.x = rand () % (2 * n + 1) - n;
    imp.y = rand () % (2 * n + 1) - n;
    imp.x += (long)((Center.x / NodeCount - pos.x) * gemP->mass *
		    a_gravity);
    imp.y += (long)((Center.y / NodeCount - pos.y) * gemP->mass *
		    a_gravity);

    for (int j = 0; j < NodeCount; j++) {
      gemQ = GemProp + j;
      d.x = pos.x - gemQ->pos.x;
      d.y = pos.y - gemQ->pos.y;
      n  = d.x * d.x + d.y * d.y;
      if (n) {
	imp.x += d.x * ELENSQR / n;
	imp.y += d.y * ELENSQR / n;
      }
    }
    nodeSet = Adjacent[v].begin();
    while (nodeSet < Adjacent[v].end()) {
      u  = *nodeSet++;
      gemQ = GemProp + u;
      d.x = pos.x - gemQ->pos.x;
      d.y = pos.y - gemQ->pos.y;
      n  = (long)((d.x * d.x + d.y * d.y) / gemP->mass);
      n  = MMIN(n, MAXATTRACT);  // 1048576L  (N2)
      imp.x -= d.x * n / ELENSQR;
      imp.y -= d.y * n / ELENSQR;
    }
    this->displace(v, imp);
    Iteration++;
  }
}

void GEM::arrange() {
    long int stop_temperature;
    unsigned long stop_iteration;

    this->vertexdata_init(a_starttemp);

    Oscillation      = a_oscillation;
    Rotation         = a_rotation;
    Maxtemp          = (long)(a_maxtemp * ELEN);
    stop_temperature = (long)(a_finaltemp * a_finaltemp * ELENSQR * NodeCount);
    stop_iteration   = a_maxiter * NodeCount * NodeCount;
    Iteration        = 0;
    
    while (Temperature > stop_temperature && Iteration < stop_iteration) {
      if (!pluginProgress->progress(Iteration,stop_iteration/2)) return;
      this->a_round();
    }
}


bool GEM::run() {
  node n;
  GEMparam p;
  Iterator<node> *nodes;
  Iterator<node> *neighbors;

  NodeCount = superGraph->numberOfNodes();
  layoutProxy->setAllEdgeValue(vector<Coord>(0));
  GemProp  = new GEMparam[NodeCount];
  Invmap   = new node[NodeCount];
  Adjacent = new vector<int>[NodeCount];
    
  STL_EXT_NS::hash_map<node, int, STL_EXT_NS::hash<node> > nodeNumbers(NodeCount);
    
  nodes = superGraph->getNodes();
  for (int i = 0; nodes->hasNext(); i++) {
    n = nodes->next();
    GemProp[i] = GEMparam(superGraph->deg(n));
    Invmap[i]  = n;
    nodeNumbers[n] = i;
  } delete nodes;

  for (int i = 0; i < NodeCount; i++) {
    neighbors   = superGraph->getInOutNodes(Invmap[i]);
    while (neighbors->hasNext()) {
      n = neighbors->next();
      Adjacent[i].push_back( nodeNumbers[n] );
    } delete neighbors;
  }
     
  if (i_finaltemp < i_starttemp)
    this->insert();
  if (pluginProgress->progress(100,100)) 
    if (a_finaltemp < a_starttemp)
      this->arrange();
  if (pluginProgress->progress(100,100)) 
    for (int i = 0; i < NodeCount; i++) {
      p = GemProp[ i ];
      layoutProxy->setNodeValue(
				Invmap[i],
				Coord( p.pos.x, p.pos.y, 0 ) );
    }       
  delete [] GemProp;
  delete [] Invmap;
  delete [] Adjacent;
  if (Map) delete [] Map;
  if (Q) delete Q;
  
  return pluginProgress->progress(100,100);
}


bool GEM::check(string &erreurMsg) {
    return(true);
}

void GEM::reset()
{}