#include <stdio.h>
#include <math.h>
#include <fstream>
#include <sstream>
#include <qinputdialog.h>

#include <tulip/TlpTools.h>
#include <tulip/SuperGraph.h>
#include <tulip/SelectionProxy.h>
#include <tulip/SubGraph.h>

#include "GeometricClustering.h"
//#include "ConvolutionClusteringSetup.h"

CLUSTERINGPLUGIN(GeometricClustering,"Geometric","David Auber","14/08/2001","Alpha","0","1");

using namespace std;
  /** =========================
      | Convolution clustering|
      =========================
      
  */
//================================================================================
  GeometricClustering::GeometricClustering(ClusterContext context):Clustering(context) {}
//================================================================================
GeometricClustering::~GeometricClustering()
{}

//================================================================================
//convolution function, build a triangular function center in 0 with a width width and a 
double g(int k,double width,double amplitude) {
  double slope=amplitude/width; 
  if ((k<=-width) || (k>=width)) 
    return 0;
  else {
    if (k<0)
      return ((double)k*slope+amplitude); //partie croissante du signal triangulaire
    else
      return ((double)-k*slope+amplitude); //partie décroissante du signal triangulaire
  }
}
//================================================================================

int getInterval(int d,vector<int> &ranges) {
  for (unsigned int i=0;i<ranges.size()-1;++i) {
    if ((d>=ranges[i]) && (d<ranges[i+1])) return i;
  }
  return ranges.size()-2;
}
//================================================================================
void GeometricClustering::setParameters(int histosize,int threshold,int width) {
  this->histosize=histosize;
  this->threshold=threshold;
  this->width=width;
}
//================================================================================
void GeometricClustering::getParameters(int &histosize,int &threshold,int &width) {
  histosize=this->histosize;
  threshold=this->threshold;
  width=this->width;
}
//================================================================================
list<int> GeometricClustering::getLocalMinimum() {
  vector<double> &discretHisto=*getHistogram();
  list <int> localMinimum;
  localMinimum.push_back(0);
  bool slopeSens; //false descent
  if (discretHisto[0]>discretHisto[1]) slopeSens=false; else slopeSens=true;
  for (unsigned int i=1;i<discretHisto.size();++i) {
    bool newSlopeSens;
    if (discretHisto[i-1]>discretHisto[i]) newSlopeSens=false; else newSlopeSens=true;
    if (newSlopeSens!=slopeSens) {
      //new Local minimum
      if (slopeSens==false) {
	int local = localMinimum.back();
	if (i-local<width/2){
	  localMinimum.pop_back();
	  localMinimum.push_back((i+local)/2);
	}
	else
	  localMinimum.push_back(i);
      }
      slopeSens=newSlopeSens;
    }
  }
  return localMinimum;
}
//================================================================================
void GeometricClustering::autoSetParameter() {
  map<double,int> histo;
  Iterator<node> *itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    double tmp=metric->getNodeValue(itn);
    if (histo.find(tmp)==histo.end()) {
      histo[tmp]=1;
    }
    else {
      histo[tmp]+=1;
    }
  }delete itN;

  if (histo.empty()) return;

  //===============================================================================
  //Find good step for discretization
  //We take the minimum interval between to bar in the continue histogram
  double deltaXMin=-1;
  double deltaXMax=0;
  double deltaSum=0;
  map<double,int>::iterator itMap=histo.begin();
  double lastValue=(*itMap).first;
  ++itMap;
  for (;itMap!=histo.end();++itMap) {    
    deltaSum+=itMap->first-lastValue;
    if (itMap->first-lastValue>deltaXMax) deltaXMax=itMap->first-lastValue;
    if (itMap->first-lastValue<deltaXMin ||  deltaXMin<0 ) deltaXMin=itMap->first-lastValue;
    lastValue=(*itMap).first;
  }
  histosize=(int)((metric->getNodeMax()-metric->getNodeMin())/deltaXMin);
  if (histosize>32768) histosize=32768;
  if (histosize<64) histosize=64;
  //===============================================================================
  //Find good with for the convolution function
  //We take the maximum width of the biggest hole

  //width=(int)(deltaXMax*histosize/(metric->getNodeMax()-metric->getNodeMin()));
  //width=(int)(deltaXMin*histosize/(metric->getNodeMax()-metric->getNodeMin()));
  deltaSum/=histo.size();
  width=(int)(deltaSum*histosize/(metric->getNodeMax()-metric->getNodeMin()))*32;
  //===============================================================================
  //Find good threshold
  //make the average of all local minimum
  vector<double> &discretHisto=*getHistogram();
  list <double> localMinimum;
  double sum=0;
  int nbElement=1;
  bool slopeSens;
  if (discretHisto[0]>discretHisto[1]) slopeSens=false; else slopeSens=true;
  for (unsigned int i=1;i<discretHisto.size();++i) {
    bool newSlopeSens;
    if (discretHisto[i-1]>discretHisto[i]) newSlopeSens=false; else newSlopeSens=true;
    if (newSlopeSens!=slopeSens) {
      //new Local minimum
      localMinimum.push_back(discretHisto[i]);
      nbElement++;
      sum+=(discretHisto[i]+discretHisto[i-1])/ 2;
    }
    slopeSens=newSlopeSens;
  }
  threshold=(int)(sum/nbElement);
}
//================================================================================
vector <double> *GeometricClustering::getHistogram() {
  //building of the histogram of values
  cerr << "GeometricClustering::getHistogram() start" << endl;
  histogramOfValues.clear();
  Iterator<node> *itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    int tmp=(int)( (metric->getNodeValue(itn) - metric->getNodeMin() ) * (double)histosize / (metric->getNodeMax()-metric->getNodeMin())) ;
    if (histogramOfValues.find(tmp)==histogramOfValues.end()) {
      histogramOfValues[tmp]=1;
    }
    else {
      histogramOfValues[tmp]+=1;
    }
  }delete itN;
  //Apply the convolution on the histogram of values
  //Convolution parameter, this version work only with integer
  smoothHistogram.clear();
  smoothHistogram.resize(histosize);
  /*
    for (int pos=0;pos<histosize;++pos) {
    double result=0;
    for (int i=-width;i<=width;++i) {
    if (histogramOfValues.find(pos+i)!=histogramOfValues.end())
    result+=histogramOfValues[pos+i]*g(i,width,1);
    }
    smoothHistogram[pos]=result;
    }
  */
  map<int,int>::iterator itMap;
  for (int pos=0;pos<histosize;++pos) smoothHistogram[pos]=0;
  for (itMap=histogramOfValues.begin();itMap!=histogramOfValues.end();++itMap) {
    double value=itMap->second;
    int index=itMap->first;
    for (int i=-width;i<=width;++i) {
      if ((index+i)>=0 && (index+i)<histosize)
	smoothHistogram[index+i]+=value*g(i,width,1);
    }
  }
  return &smoothHistogram;
  cerr << "GeometricClustering::getHistogram() end" << endl;
}


void GeometricClustering::buildResult(STL_EXT_NS::hash_map< node, vector<int> > &result) {
  autoSetParameter();
  getHistogram();
  vector<int> temporaryRanges;
  list<int> localMinimum=getLocalMinimum();
  while (!localMinimum.empty()) {
    temporaryRanges.push_back(localMinimum.front());
    localMinimum.pop_front();
  }
  temporaryRanges.push_back(histosize);

  cerr << "Number Of temporary intervals :" << temporaryRanges.size() << endl;
  for (unsigned int i=0;i<temporaryRanges.size();++i) {
    cerr << temporaryRanges[i] << ",";
  }
  cerr << endl;
  //Ensure that there is elements inside each intervals.
  vector<int> ranges;
  ranges.push_back(0);
  unsigned int curRanges=0;
  map<int,int>::iterator itMap;
  itMap=histogramOfValues.begin();
  while (temporaryRanges[curRanges]<histosize) {
    cerr << "curRanges=" << curRanges << " tmp[]=" << temporaryRanges[curRanges] << " itmap=" << (*itMap).first << endl;
    while ((temporaryRanges[curRanges]<=(*itMap).first)) {cerr << "a"; ++curRanges;}
    while (((*itMap).first<=temporaryRanges[curRanges]) && (itMap!=histogramOfValues.end())) {cerr << "b";++itMap;}
    if (itMap==histogramOfValues.end()) {
      ranges.push_back(histosize);
      break;
    }
    else
      ranges.push_back(temporaryRanges[curRanges]);
  }
  cerr << "Number Of intervals :" << ranges.size() << endl;
  for (unsigned int i=0;i<ranges.size();++i) {
    cerr << ranges[i] << ",";
  }
  cerr << endl;

  Iterator<node> *itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    int tmp=getInterval((int)( (metric->getNodeValue(itn) - metric->getNodeMin() ) * (double)histosize / (metric->getNodeMax()-metric->getNodeMin())),ranges);
    result[itn].push_back(tmp);
  }delete itN;
}

//================================================================================
bool GeometricClustering::run()
{
  histosize=128;
  string tmp1,tmp2;

  LayoutProxy *layout=getProxy<LayoutProxy>(superGraph,"viewLayout");

  STL_EXT_NS::hash_map< node, vector<int> > tmpResult;
  metric=getProxy<MetricProxy>(superGraph,"tmpMetric1");
  Iterator<node>*itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    metric->setNodeValue(itn,layout->getNodeValue(itn).getX());
  }delete itN;
  buildResult(tmpResult);
  metric=getProxy<MetricProxy>(superGraph,"tmpMetric2");
  itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    metric->setNodeValue(itn,layout->getNodeValue(itn).getY());
  }delete itN;
  buildResult(tmpResult);
  metric=getProxy<MetricProxy>(superGraph,"tmpMetric3");
  itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    metric->setNodeValue(itn,layout->getNodeValue(itn).getZ());
  }delete itN;
  buildResult(tmpResult);

  map< vector<int> , vector<node> > subgraphs;
  itN=superGraph->getNodes();
  for (;itN->hasNext();) {
    node itn=itN->next();
    for (int k=0;k<3;++k)  cerr << tmpResult[itn][k] << " " ;
    cerr << endl;
    subgraphs[tmpResult[itn]].push_back(itn);
  }delete itN;


  map< vector<int> , vector<node> >::iterator itsub;
  char str[100];
  vector<SuperGraph *> newGraphs(subgraphs.size());
  int i;
  for (i=0,itsub=subgraphs.begin();itsub!=subgraphs.end();++itsub,++i) {
    sprintf(str,"Cluster_%05i",i);
    newGraphs[i]=TlpTools::newSubGraph(superGraph,string(str));
    vector<node>::iterator itnode;
    for (itnode=(*itsub).second.begin();itnode!=(*itsub).second.end();++itnode) {
      newGraphs[i]->addNode(*itnode);
    }
  }

  //Fill the graphs with edges
  for (unsigned int i=0; i< newGraphs.size(); ++i) {
    Iterator<edge> *itE=superGraph->getEdges();
    for(;itE->hasNext();) {
      edge ite=itE->next();
      if (newGraphs[i]->isElement(superGraph->source(ite)) && newGraphs[i]->isElement(superGraph->target(ite)) ) newGraphs[i]->addEdge(ite);
    }delete itE;
  }
  cerr << "edges added" << endl;

  return true;
}
//================================================================================
bool GeometricClustering::check(string &erreurMsg)
{
  erreurMsg="";
  return true;
}
//================================================================================
void GeometricClustering::reset()
{
}
//================================================================================