#include <stdio.h>
#include <math.h>
#include <sstream>
#include <qinputdialog.h>
#include <tulip/TlpTools.h>
#include <tulip/SuperGraph.h>
#include <tulip/SelectionProxy.h>
#include <tulip/SubGraph.h>
#include <fstream>

#include "ConvolutionClustering.h"
#include "ConvolutionClusteringSetup.h"

CLUSTERINGPLUGIN(ConvolutionClustering,"Convolution","David Auber","14/08/2001","Alpha","0","1");

using namespace std;
  /** =========================
      | Convolution clustering|
      =========================
      
  */
//================================================================================
  ConvolutionClustering::ConvolutionClustering(ClusterContext context):Clustering(context) {}
//================================================================================
ConvolutionClustering::~ConvolutionClustering(){}
//================================================================================
//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 ConvolutionClustering::setParameters(int histosize,int threshold,int width) {
  this->histosize=histosize;
  this->threshold=threshold;
  this->width=width;
}
//================================================================================
void ConvolutionClustering::getParameters(int &histosize,int &threshold,int &width) {
  histosize=this->histosize;
  threshold=this->threshold;
  width=this->width;
}
//================================================================================
list<int> ConvolutionClustering::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 ConvolutionClustering::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()));
  //===============================================================================
  //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> *ConvolutionClustering::getHistogram() {
  //building of the histogram of values
  cerr << "ConvolutionClustering::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;
    }
  */


  for (int pos=0;pos<histosize;++pos) smoothHistogram[pos]=0;
  map<int,int>::iterator itMap;
  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 << "ConvolutionClustering::getHistogram() end" << endl;
}
//================================================================================
bool ConvolutionClustering::run()
{
  //  int width=10;
  //  int height=1;
  //  double threshold=2;
  //  width = QInputDialog::getInteger( QString("Please enter the width of the convolution"),QString("Width :"), 10, 10, 1000000, 10, &ok );
  //  int height = QInputDialog::getInteger( QString("Please enter the height of the convolution"),QString("Height"), 1, 1, 1000000, 10, &ok );
  //  threshold = QInputDialog::getInteger( QString("Please enter the threshold"),QString("threshold"), 2, 2 , 1000000, 10, &ok );
 
  histosize=128;

  string tmp1,tmp2;

  metric=getProxy<MetricProxy>(superGraph,"viewMetric");
  autoSetParameter();
  getHistogram();
  ConvolutionClusteringSetup *mysetup=new ConvolutionClusteringSetup(this);
  bool setupResult=mysetup->exec();
  delete mysetup;
  if (setupResult==QDialog::Rejected) return false;

  /**
     Compute the scale factor on x and y the shifting to obtain a good dicretisation of the Real values.
     The histogram must be in the range [0..histosize]
     The amplitude must be in the range {0..10]
  */
  /*
   cerr << "histogram of values :" << histogramOfValues.size() << endl;
   cerr << "************************************************" << endl;
   ofstream osHist("histogramOfValues.txt");
   int i=0;
   for (map<int,int>::iterator it=histogramOfValues.begin();it!=histogramOfValues.end();++it) {
     while(it->first>i) {
       osHist <<  i << " , 0" << endl;
       i++;
     }       
     osHist <<  it->first << " , " << it->second << endl;
     i++;
   }
   while(i<histosize) {
     osHist <<  i << " , 0" << endl;
     i++;
   }       
   cerr << endl << "************************************************" << endl;
  */

  //Cut the resultHistogram in part depending of the threshold of sensibility
  /*
    cerr << "************************************************" << endl;
    cerr << "Histogram smooth" << endl;
    ofstream osHistSmooth("smoothhistogramOfValues.txt");
    for (int i=0;i<histosize;++i)
    {
    osHistSmooth << i << " , " << smoothHistogram[i] << endl;
    }
    cerr << endl << "************************************************" << endl;
  */

  vector<int> temporaryRanges;
  bool state=false; //indicate if we are above the threshold or not;
  /*
  temporaryRanges.push_back(-1);
  for (int i=0;i<histosize;++i) {
    if (!state) {
      if (smoothHistogram[i]>=threshold) {
	temporaryRanges.push_back(i);
	state=true;
      }
    }
    else {
      if (smoothHistogram[i]<threshold) {
	temporaryRanges.push_back(i);
	state=false;
      }
    }
  }
  temporaryRanges.push_back(histosize);
  */
  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;



  //build the empty graphs 
  char str[100];
  vector<SuperGraph *> newGraphs(ranges.size()-1);
  for (unsigned int i=0; i< ranges.size()-1;++i) {
    sprintf(str,"Cluster_%05i",i);
    newGraphs[i]=TlpTools::newSubGraph(superGraph,string(str));
  }
  cerr << "Empty graphs built" << endl;

  //Fill the graphs with nodes
  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);
    newGraphs[tmp]->addNode(itn);
  }delete itN;  
  cerr << "nodes added" << endl;

  //Fill the graphs with edges
  for (unsigned int i=0; i< ranges.size()-1; ++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 ConvolutionClustering::check(string &erreurMsg)
{
  erreurMsg="";
  return true;
}
//================================================================================
void ConvolutionClustering::reset()
{
}
//================================================================================