#define _CRT_SECURE_NO_DEPRECATE // to avoid VS2005 to display unnecessary warnings...

// All the necessary includes are listed here...
#include <assert.h>
#include <ctime>
#include <fstream>
#include <iostream>
#include <map>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <time.h>
#include <vector>
using namespace std;

typedef int** type_matrix;          // important for dynamic memory allocation, no need to depend on MAX_PROBLEM_SIZE
typedef int*  type_vector;
typedef bool* type_bool_vector;

// Identifier for this Instance-Config-RunID
char InstanceFile[255];
char ConfigurationFile[255];
char RunID[255];

// For temporary stuffs
char tempString[255];

// Current & Best Solution          // For permutation, assignment, valuation, bit string
int n;                              // Instance Size
type_vector solution;               // Indices are always from [0..n-1]
type_vector bestSolution;
type_vector tempSolution;           // In care we need to revert back, e.g. ILS
type_bool_vector taken;             // A helper array variable

// OV: Objective Value
int Cur_OV;                         // Current Objective Value
int Prev_OV;                        // Objective Value one iteration ago
int Neighbor_OV;                    // For neighborhood based SLS
int Best_Neighbor_OV;               // To keep track which is the best neighbor OV
int BF_OV;                          // Best Found Objective Value in this run
int BK_OV;                          // Best Known Objective Value for this instance
double gap;                         // Gap between BK_OV and BF_OV
double cur_gap;                     // Gap between BK_OV and Cur_OV

bool Is_Minimizing = true;          // Default value: true (Minimizing COP)

// Iteration Variables
int Cur_Iter;                       // Current Iteration
int Best_Iter;                      // Best Iteration
int bestToPercent[5];
int NonImprovingMoves;

// Default configuration variables
int MAX_ITERATIONS;
int UPDATE_RATE;

// Counter variables... Do not use them to store anything important.
int i,j,k,l;

void ReadConfig(FILE* file_pointer,int* parameter) {
  // Purpose    : Read 
  // Complexity : O(1)

  char line[1000],*p;
  fgets(line,1000,file_pointer);
  p = strtok(line,"\t"); // get the first item
  sscanf(p,"%d",parameter);
}

int PreProcess(int argc,char **argv) {
  // Purpose    : Prepare preliminary stuffs
  // Complexity : O(1)

  if (argc < 4) {
    printf("Use this syntax to run this program:\n");
    printf("EXE_name \"<Instance_File>\" \"<Configuration_File>\" <Run_ID>\n");
    printf("\n");
    printf("There should not be any whitespace inside each parameter!\n");
    printf("Therefore, please enclose the file paths with double quotes!\n");

    return 1; // do not continue the program
  }
  else { // from command line
    strcpy(InstanceFile,argv[1]);
    strcpy(ConfigurationFile,argv[2]);
    strcpy(RunID,argv[3]);
  }

  if (Is_Minimizing)
    BF_OV = Prev_OV = 2147483647; // 2^31-1
  else
    BF_OV = Prev_OV = -2147483647; // -2^31-1

  Best_Iter = bestToPercent[4] = bestToPercent[3] = bestToPercent[2] = bestToPercent[1] = bestToPercent[0] = -1;
  Cur_Iter = NonImprovingMoves = MAX_ITERATIONS = 0;
  UPDATE_RATE = 1;
  gap = cur_gap = 100.0; // start with 100.0%, just a default value
  srand((unsigned) time(NULL)); // record (unsigned) time(NULL), then...

  return 0;
}

inline void UpdateStatistics() {
  // Purpose    : Update some internal statistics, inline for faster processing
  // Complexity : O(n)

  if ((Is_Minimizing && Cur_OV < BF_OV) || (!Is_Minimizing && Cur_OV > BF_OV)) {
    BF_OV = Cur_OV;
    NonImprovingMoves = 0; // reset counter
    for (i=0; i<n; i++) // convention, always from 0 to n-1
      bestSolution[i] = solution[i]; // save best

    gap = abs(BF_OV - BK_OV) * 100.0 / BK_OV ; // in percentage-off
    Best_Iter = Cur_Iter; // always update until end of run...

    for (i=4; i>=0; i--) {
      if (bestToPercent[i] == -1 && gap <= i) // 1 time record
        bestToPercent[i] = Cur_Iter;
    }
  }
  else
    NonImprovingMoves++;

  cur_gap = abs(Cur_OV - BK_OV) * 100.0 / BK_OV ;
  Prev_OV = Cur_OV;

  if (Cur_Iter%UPDATE_RATE == 0)
    printf("%6d, Current = %d, Best = %d (%.2lf)\n",Cur_Iter,Cur_OV,BF_OV,gap);
}

void PrintStatistics() {
  // Purpose    : Print-out the final statistics
  // Complexity : O(1)

  printf("\nLast iteration: %d\n",Cur_Iter);
  printf("BK OV = %d\n",BK_OV);
  printf("BF OV = %d (%.2lf%c-Off BK)\n",BF_OV,gap,'%');
  printf("\n");
  for (i=0; i<n; i++)
    printf("%d-",bestSolution[i]);
  printf("\n\nIterations needed to reach OV within:\n");
  for (i=4; i>=0; i--)
    printf("  %d%c BK_OV: %d\n",i,'%',bestToPercent[i]);
}

bool IsValidPermutation() {
  // Purpose    : To check whether the current solution is a valid permutation of [0..n-1]
  // Complexity : O(n)

  for (i=0; i<n; i++)
    taken[i] = false;
  for (i=0; i<n; i++)
    taken[solution[i]] = true;
  for (i=0; i<n; i++)
    if (!taken[i])
      return false;

  return true;
}

int BondDistanceToBF() {
  // Purpose    : Check the bond distance of current solution to current BF solution
  // Complexity : O(n)

  int currentDistance = 0;
  int matchLCur[MAX_PROBLEM_SIZE];
  int matchRCur[MAX_PROBLEM_SIZE];

  for (i=0; i<n; i++) {
    matchRCur[bestSolution[i]] = bestSolution[(i + 1) % n];
    matchLCur[bestSolution[(i + 1) % n]] = bestSolution[i];
  }

  for (i=0; i<n; i++) // bestSolution.Length == solution.Length
    if (!((matchRCur[solution[i]] == solution[(i + 1) % n]) ||
          (matchLCur[solution[i]] == solution[(i + 1) % n]) ||
          (matchRCur[solution[(i + 1) % n]] == solution[i]) ||
          (matchLCur[solution[(i + 1) % n]] == solution[i])))
      currentDistance++;

  return currentDistance;
}

int HammingDistanceToBF() {
  // Purpose    : Check the Hamming distance of current solution to current BF solution
  // Complexity : O(n)

  int currentDistance = 0;

  for (i=0; i<n; i++)
    if (solution[i] != bestSolution[i])
      currentDistance++;

  return currentDistance;
}

void RestartToBF() {
  // Purpose    : Set the current solution = current BF solution
  // Complexity : O(n)

  for (i=0; i<n; i++)
    solution[i] = bestSolution[i];
}

class VizLogger { 
public:
  VizLogger(
    string ProblemName,       // 2-(TSP|QAP|etc)
    bool IsMinimizing,        // 3-(true|false)
    string InstanceFile,      // 4-(tai50b.datx|lin105.tspx|etc)
    string ConfigurationFile, //   (Ro-TS-A.cfg|Ro-TS-B.cfg|etc)
    string RunID,             //   an integer
    int InstanceSize,         // 5-an integer
    string SolverName,        // 6-(TS|ILS|SA|etc)
    string RunDescription,    // 7-any string comments
    int NumberOfEntries)      // 8-an integer
  {
    // Purpose    : Create RunLog file using standardized name and then write RunLog headers
    // Complexity : O(1)

    // Remember the creation time of this class
    start = clock();
 
    // This is the standard file name, remove directory name if any, then remove extension
    InstanceFile = InstanceFile.substr(InstanceFile.find('\\')+1,InstanceFile.length());
    InstanceFile = InstanceFile.substr(0,InstanceFile.find('.')); // remove .tspx/.datx
    ConfigurationFile = ConfigurationFile.substr(ConfigurationFile.find('\\')+1,ConfigurationFile.length());
    ConfigurationFile = ConfigurationFile.substr(0,ConfigurationFile.find('.')); // remove .cfg
    string logFile = InstanceFile + "_" + ConfigurationFile + "_" + RunID + ".RunLog";
    RunLogFile.open(logFile.c_str());
    RunLogFile.precision(3);
    RunLogFile.flags(ios::right + ios::fixed);

    RunLogFile << "2006b" << endl;                     // Line 1 - FormatVersion // RunLog latest format is 2006b, VDF latest format is 2007a!
    RunLogFile << ProblemName << endl;                 // Line 2 - ProblemName
    RunLogFile << (IsMinimizing ? 1 : 0) << endl;      // Line 3 - IsMinimizing
    RunLogFile << InstanceFile << endl;                // Line 4 - InstanceFile
    RunLogFile << InstanceSize << endl;                // Line 5 - InstanceSize
    RunLogFile << SolverName << endl;                  // Line 6 - SolverName
    RunLogFile << RunDescription << endl;              // Line 7 - RunDescription
    RunLogFile << NumberOfEntries << endl;             // Line 8 - NumberOfEntries
    RunLogFile << endl;                                // Line 9 - Dummy1
    RunLogFile.flush();
  }

  ~VizLogger() {
    // Purpose    : Close run log
    // Complexity : O(1)

    RunLogFile.close();
  }

  void LogCurrentSolution(int* Solution, bool feasible, double OV) {
    // Purpose    : Log current solution
    // Complexity : O(n)
    // Storing these values in memory first and then dump to file is another idea...
    // However, that is more complex and can be slow too...

    for (int i=0; i<n; i++)                            // Line 10 - Solution (comma separated)
      RunLogFile << Solution[i] << ",";
    RunLogFile << endl; 
    RunLogFile << (feasible ? 1 : 0) << endl;          // Line 11 - Is_Feasible
    RunLogFile << OV << endl;                          // Line 12 - Objective_Value
    RunLogFile << (double) (clock() - start)           // Line 13 - Time_Stamp
      / CLOCKS_PER_SEC << endl; 
    RunLogFile << endl;                                // Line 14 - Tag
    RunLogFile.flush();                                // quickly write to file!
  }

  void LogAlgorithmSpecific(char* line1, char* line2, char* line3) {
    // Purpose    : Log algorithm information
    // Complexity : O(1)

    RunLogFile << line1 << endl;                       // Line 15 - Tabu_Tenure/Perturb4OptDoubleBridgeation/Temperature
    RunLogFile << line2 << endl;                       // Line 16 -            /AcceptReject/Toss_Value
    RunLogFile << line3 << endl;                       // Line 17 - (empty)
    RunLogFile.flush();
  }

private:
  ofstream RunLogFile;                                 // pointer to RunLog file
  clock_t start;
};

// User just need to instantiate this...
VizLogger* LOGGER;