#define _CRT_SECURE_NO_DEPRECATE // to avoic VS2005 to display unnecessary warnings...
#define MAX_PROBLEM_SIZE 1000 // the largest instance size
#define CANDIDATE_LIST_SIZE 100 // try to make this smaller :O, for now, to avoid bug, I will give a large value, 100 vertices...

#include "Common.h"

struct Customer {
  float Xcoord;
  float Ycoord;
};

Customer Array[MAX_PROBLEM_SIZE];
int distance_matrix[MAX_PROBLEM_SIZE][MAX_PROBLEM_SIZE]; // 2-D matrix
int candidate_list[MAX_PROBLEM_SIZE][MAX_PROBLEM_SIZE];

int solutionMap[MAX_PROBLEM_SIZE]; // Only used by TSP_ILS at the moment, is this really necessary?
int previousSolutionMap[MAX_PROBLEM_SIZE];
bool Dont_Look_Bits[MAX_PROBLEM_SIZE];

// Configuration parameters
int PERTURBATION_STRENGTH;
int BETTER_ACCEPTANCE_CRITERIA;
int NON_IMPROVING_MOVES_TOLERANCE;

void ReadConfigurationFile(char *pFileName) {
  FILE* fPtr = fopen(pFileName,"r");
  ReadConfig(fPtr,&MAX_ITERATIONS);
  ReadConfig(fPtr,&UPDATE_RATE);
  ReadConfig(fPtr,&PERTURBATION_STRENGTH);
  ReadConfig(fPtr,&BETTER_ACCEPTANCE_CRITERIA);
  ReadConfig(fPtr,&NON_IMPROVING_MOVES_TOLERANCE);
  fclose(fPtr);
}

void ReadInstanceFile(char* pFileName) {
  // Purpose    : Read *.tspx file, build distance_matrix and candidate_list
  // Complexity : O(|CANDIDATE_LIST_SIZE|*n^2)

  FILE* fPtr = fopen(pFileName,"r");

  n = 0;
  char line[1000];

  fgets(line,1000,fPtr);
  sscanf(line,"%d",&BK_OV); // If BK_OV is unknown, it will be 0...

  while (1) {
    fgets(line,1000,fPtr);
    if (strcmp(line,"NODE_COORD_SECTION\n") == 0) break;
  }

  int cust_no = 0;
  float x=0, y=0;

  while (1) {
    fgets(line,1000,fPtr);
    if (strcmp(line,"EOF\n") == 0) break;
    sscanf(line,"%d %f %f",&cust_no,&x,&y);
    Customer cus;
    cus.Xcoord = (float)x;
    cus.Ycoord = (float)y;
    Array[cust_no-1] = cus;
  }

  n = cust_no;
  fclose(fPtr);

  solution = new int[n];
  bestSolution = new int[n];
  tempSolution = new int[n];
  taken = new bool[n];

  // Now we already got the (x,y) pairs of each city
  // Build a distance table, and round all distance to nearest integer
  for (i=0; i<n; i++) { // O(n^2)
    for (j=i+1; j<n; j++) {
      double xd = Array[j].Xcoord - Array[i].Xcoord;
      double yd = Array[j].Ycoord - Array[i].Ycoord;

      // this formula will round floating point distance to nearest integer
      // in symmetric TSP, ij and ji have similar distance
      distance_matrix[i][j] = distance_matrix[j][i] = (int) (sqrt(xd*xd + yd*yd) + 0.5);
    }
    // max long int... distance from city i to city i is undefined
    distance_matrix[i][i] = 2147483647; 
  }

  // Candidate list generation...
  for (i=0; i<n; i++) { // O(|CANDIDATE_LIST_SIZE|*n^2), for each city...
    for (j=0; j<n; j++)
      taken[j] = false;

    for (j=0; j<n && j<CANDIDATE_LIST_SIZE; j++) { // O(|CANDIDATE_LIST_SIZE|*n)
      int shortestEdge = 2147483647, shortestID = -1;
  
      for (k=0; k<n; k++) // O(n)
        if (!taken[k] && distance_matrix[i][k] < shortestEdge) {
          shortestEdge = distance_matrix[i][k];
          shortestID = k;
        }

      taken[shortestID] = true;
      candidate_list[i][j] = shortestID; // record this...
    }
  }

  // LATER...
  //// initially, all don't look bits are off...
  //for (i=0; i<n; i++)
  //  Dont_Look_Bits[i] = 0;
}

int Evaluate() {
  // Purpose    : Update Cur_OV from scratch
  // Complexity : O(n)

  int distance = 0;
  for (i=0; i<n-1; i++)
    distance += distance_matrix[solution[i]][solution[i+1]];
  distance += distance_matrix[solution[n-1]][solution[0]]; // loop back
  return distance;
}

inline int EvaluateNeighbor(int t1,int t2,int t3,int t4) {
  // Purpose    : Update Cur_OV incrementally by deleting two edges
  //              (pos1,(pos+1)%n) and (pos2,(pos2+1)%n)
  //              (t1,t2) and (t3,t4)
  //              and adding two edges
  //              (pos1,pos2) and ((pos1+1)%n,(pos2+1)%n)
  //              (t1,t3) and (t2,t4)
  //              distance_matrix[city_index1][city_index2]
  // Complexity : O(1)

  int distance = Cur_OV; // incremental calculation...
  // minus two edges
  distance -= distance_matrix[t1][t2];
  distance -= distance_matrix[t3][t4];
  // add two edges
  distance += distance_matrix[t1][t3];
  distance += distance_matrix[t2][t4];
  return distance;
}

void CreateInitialSolution() {
  // Purpose    : Array 'solution' and 'solutionMap' are initialized linearly, 
  //              Cur_OV evaluated (absolute)
  // Complexity : O(n)

  for (i=0; i<n; i++)
    solution[i] = solutionMap[i] = i;
  assert(IsValidPermutation());
  Cur_OV = Evaluate();
}

void CreateRandomSolution() {
  // Purpose    : Array 'solution' and 'solutionMap' are initialized randomly, 
  //              Cur_OV evaluated (absolute)
  // Complexity : O(n)

  for (i=0; i<n; i++)
    taken[i] = false;

  for (i=j=0; i<n; i++) {
    int nextVal = rand()%n;
    while (nextVal--) j = (j+1)%n;
    while (taken[j]) j = (j+1)%n;
    solution[i] = j;
    solutionMap[j] = i;
    taken[j] = true;
  }

  assert(IsValidPermutation());
  Cur_OV = Evaluate();
}

void CreateGreedySolution() {
  // Purpose    : Array 'solution' and 'solutionMap' are initialized randomly, 
  //              Cur_OV evaluated (absolute)
  // Complexity : O(n^2)

  int currentNode = rand()%n; // the starting node is random
  // printf("starting node: %d\n",currentNode);
  for (i=0; i<n; i++)
    taken[i] = false;

  solution[0] = currentNode;
  solutionMap[currentNode] = 0;
  taken[currentNode] = true;

  for (i=1; i<n; i++) { // O(n^2)
    int shortestEdge = 2147483647;
    vector<int> bestJ;

    for (j=0; j<n; j++) {
      if (!taken[j] && distance_matrix[currentNode][j] < shortestEdge) {
        shortestEdge = distance_matrix[currentNode][j];
        bestJ.clear();
      }

      if (!taken[j] && distance_matrix[currentNode][j] == shortestEdge)
        bestJ.push_back(j);
    }
    
    int randPos = (int) (rand()%bestJ.size()); // throw fair coin
    solution[i] = bestJ[randPos]; // the shortest edge (fair selection among ties).
    solutionMap[bestJ[randPos]] = i;
    currentNode = bestJ[randPos];
    taken[bestJ[randPos]] = true;
  }

  assert(IsValidPermutation());
  Cur_OV = Evaluate();
}