#include "Problem.h"
#include "Solution.h"
#include "orOptTSP.h"
#include "Control.h"
#include "Random.h"
#include "farthestInsertion.h"

#include <fstream.h>
#include <iostream.h>
#include <math.h>
using namespace std;

int main( int argc, char** argv ) {


  Control control( argc, argv );


  Random* rnd =  new Random((unsigned) control.getSeed());;
  Problem *problem = new Problem( control );
  int n = problem->numberOfCustomers;

  while( control.triesLeft() ) {

    control.beginTry();    
    
    Solution currentSolution(rnd, control, problem );
    Solution bestSolution(rnd, control, problem );

    farthestInsertion(currentSolution);

    control.setCurrentCost( currentSolution.computeExpectedCost());

    double best = currentSolution.expectedCost;
    bestSolution.copySolution(currentSolution);

    while ( control.timeLeft() ) {

      orOptTSP(rnd,control, currentSolution);
      
      //cout << "local search= " << currentSolution.expectedCost << endl;//////////


      control.setCurrentCost( currentSolution.computeExpectedCost());
         
      if (currentSolution.expectedCost < best) { 
	bestSolution.copySolution(currentSolution);
	best = currentSolution.expectedCost; 
      }
      else 
	currentSolution.copySolution(bestSolution); 

      double best_perturbed = INT_MAX;
      
      Solution PbestSolution(rnd, control, problem ); 
      int count = 0;
      
      while ( count < n ){ 
	currentSolution.copySolution( bestSolution);
	currentSolution.perturbTSP(); 
	currentSolution.computeExpectedCost();
	control.setCurrentCost( currentSolution.expectedCost); 
	if (currentSolution.expectedCost < best) {
	  bestSolution.copySolution(currentSolution);
	  best = currentSolution.expectedCost; 
	  break;
	}
	else if (currentSolution.expectedCost - best < n/10)
	  break;	

	if (best_perturbed > currentSolution.expectedCost - best) {
	  PbestSolution.copySolution( currentSolution);
	  best_perturbed = currentSolution.expectedCost - best;
	}
	count ++;
      }      
      if (count == n) 
	currentSolution.copySolution( PbestSolution);
      
      control.setCurrentCost( currentSolution.computeExpectedCost());

    }
    
    bestSolution.copySolution(currentSolution); 
    
    control.endTry();
    bestSolution.printOn(control.getOutputStream());
  }
  
}