#include <iostream>
#include <fstream>
#include <sstream>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <limits>
// #include <algorithm>


/**
 * INFO704
 *
 * Comparaison entre deux méthodes pour calculer la distance minimale entre deux
 * points parmis un ensemble de points.
 *
 * 1. Algorithme naif consistant à calculer la distance entrer toutes les paires
 * de points et à retenir la plus petite.
 *
 * 2. Algorithme ``Diviser pour régner``, vu en TD)
 *
 */

using std::cout;
using std::endl;
using std::string;
using std::vector;


class Point
{
public :
  Point ( int x, int y ) : x(x), y(y) {}
  ~Point() {}

  double distance( const Point & autre ) const
    {
      double diff_x = (double)(x-autre.x);
      double diff_y = (double)(y-autre.y);
      return sqrt( diff_x*diff_x + diff_y*diff_y );
    }

  static bool cmp_x( const Point &  p, const Point & q )
    {
      return p.x < q.x;
    }

  static bool cmp_y( const Point &  p, const Point & q )
    {
      return p.y < q.y;
    }

public :
  int x;
  int y;
};


typedef vector<Point> tabPoints;

/**
 * Importe la liste des points issue de file.
 * Params :
 *  - T - ( sortie ) tableau dans lequel les points sont inscrits,
 *  - file - le fichier contenant les points.
 */
void ptsGeneFile( tabPoints & T,  const std::string file)
{
  T.clear();

  std::ifstream inputFile;
  inputFile.open(file);
  if (inputFile.is_open()){

    std::string data1, data2;
    int i,j = 0;
    while (getline(inputFile, data1, ' ') && getline(inputFile, data2)){
      std::stringstream ss1( data1 ); //create a stringstream with the input variable
      std::stringstream ss2( data2 ); //create a stringstream with the input variable
      if( ss1 >> i && ss2 >> j) //if the 'input' goes into the int...
        T.push_back( Point( i, j ) );
           //need to split the data by \t and properly convert it into an int/string/float where needed
    }

    inputFile.close();
  }
  else cout << "Problème lors de l'ouverture du fichier généré";
}


double distance_min_naive( const tabPoints & T )
{
  double dmin = std::numeric_limits<double>::max();
  int n = T.size();
  for ( int i=0; i<n-1; ++i )
    {
      for ( int j=i+1; j<n; ++j )
        {
          double d = T[i].distance( T[j] );
          if ( d < dmin )
            {
              dmin = d;
            }
        }
    }
  return dmin;
}



/**  Cette fonction de tri pourrait vous servir !
        -> trier_sous_tableau( T, debut, fin, Point::cmp_x );
    trie le sous-tableau défini entre debut et fin selon la x-coordonnée.
    Le tri se fait selon la y-coordonnée si on met à la fin : "Point::cmp_y"
**/
typedef bool (*ordrePts)( const Point &, const Point & );
void trier_sous_tableau( tabPoints &T, int debut, int fin, ordrePts cmp )
{
  sort( T.begin()+debut, T.begin()+fin+1, cmp );
}


/**  Code de la méthode Diviser-pour-régner à compléter
**/
double distance_min_dpr( const tabPoints & T )
{
  double dmin = std::numeric_limits<double>::max(); // dmin est initialisée à la valeur maximale possible





    /**  C'est ici qu'il faudrait écrire le nouvel algorithme récursif
      basé sur le principe "Diviser pour régner"
    **/






  return dmin;
}

/**  Aide indiquant comment utiliser notre fonction
**/
void usage( const char* nom )
{
  cout << "Usage : " << nom << " METHODE file\n";
  cout << "  Importe un fichier file listant un ensemble de points dans\n";
  cout << "  le plan puis détermine la distance minimum entre deux de\n";
  cout << "  ces points.\n";
  cout << "  Valeurs valides pour METHODE :\n";
  cout << "  - naive -        Double boucle en O(n^2)\n";
  cout << "  - dpr -          Méthode diviser-pour-régner \n";
  cout << "                     (algorithme à implémenter))" << endl;
  cout << "  - naive_muette - comme naive mais sans sortie\n";
  cout << "  - dpr_muette -   comme dpr mais sans sortie" << endl;
}



int main( int argc, const char* argv[] )
{
  if ( argc < 3 )
    {
      usage( argv[0] );
      exit( EXIT_FAILURE );
    }


  double (*fctDistMin)( const tabPoints& );
  if ( string( argv[1] ).compare( "naive" ) == 0 )
    {
      cout << "# [Méthode naïve]" << endl;
      fctDistMin = distance_min_naive;
    }
  else if ( string( argv[1] ).compare( "naive_muette" ) == 0 )
    {
      fctDistMin = distance_min_naive;
    }
  else if ( string( argv[1] ).compare( "dpr" ) == 0 )
    {
      cout << "# [Méthode diviser-pour-régner]" << endl;
      fctDistMin = distance_min_dpr;
    }
  else if ( string( argv[1] ).compare( "dpr_muette" ) == 0 )
    {
      fctDistMin = distance_min_dpr;
    }
  else
    {
      usage( argv[0] );
      exit( EXIT_FAILURE );
    }

  tabPoints T;

  // Importation de la liste des points du plan
  ptsGeneFile( T, argv[2] );
  // Calcul de la distance minimale
  double d=fctDistMin( T );
  if ( string( argv[1] ).compare( "naive" ) == 0 || string( argv[1] ).compare( "dpr" ) == 0 )
    {
      cout << " La distance minimale est " << d << endl;
    }

  return 0;
}