package simulatedAnnealing;

import java.util.*;

class TSP {
  final static int TRANSPORT = 0;
  private static final int NORMALIZE =1000;

  public static double calcCost(int operation,City []cities,int []order, SegmentInfo segment) {
    if (operation == TRANSPORT)
      return (calcTransportCost(cities,order,segment));
    else
      return (calcReverseCost(cities,order,segment));
  }

  public static double calcTransportCost(City []cities,int []order,
                                         SegmentInfo segment) {
    double cost = 0;

    segment.followingNewPlace = (1 + segment.newPlace) % cities.length;
    segment.precedingStart = (segment.start - 1 +cities.length) % cities.length;
    segment.followingEnd = (1 + segment.end) % cities.length;
    City []citiesInvolved = new City[6];
    citiesInvolved[0] = new City(cities[order[segment.start]]);
    citiesInvolved[1] = new City(cities[order[segment.end]]);
    citiesInvolved[2] = new City(cities[order[segment.newPlace]]);
    citiesInvolved[3] = new City(cities[order[segment.followingNewPlace]]);
    citiesInvolved[4] = new City(cities[order[segment.precedingStart]]);
    citiesInvolved[5] = new City(cities[order[segment.followingEnd]]);
    cost -= City.distance(citiesInvolved[1],citiesInvolved[5]);
    cost -= City.distance(citiesInvolved[0],citiesInvolved[4]);
    cost -= City.distance(citiesInvolved[2],citiesInvolved[3]);
    cost += City.distance(citiesInvolved[0],citiesInvolved[2]);
    cost += City.distance(citiesInvolved[1],citiesInvolved[3]);
    cost += City.distance(citiesInvolved[4],citiesInvolved[5]);

    return cost;
  }

  public static void operate(int operation,int[] order,int citiesNum,
		       SegmentInfo segment) {
    if (operation == TRANSPORT)
      transport(order,citiesNum,segment);
    else
      reverse(order,citiesNum,segment);
  }

  public static void transport(int[] order,int citiesNum,SegmentInfo segment){
    int []newOrder = new int[citiesNum];
    int segmentLength = (segment.end - segment.start +1+citiesNum) % citiesNum;
    int length1 = (segment.precedingStart - segment.followingNewPlace +
		   1+citiesNum) % citiesNum;
    int length2 = (segment.newPlace - segment.followingEnd + 1 + citiesNum) %
                   citiesNum;
    int index = 0;
    for (int i=0; i<segmentLength; i++) {
      int j = (i+segment.start) % citiesNum;
      newOrder[index++] = order[j];
    }
    for (int i=0; i<length1; i++) {
      int j = (i+segment.followingNewPlace) % citiesNum;
      newOrder[index++] = order[j];
    }
    for (int i=0; i<length2; i++) {
      int j = (i+segment.followingEnd) % citiesNum;
      newOrder[index++] = order[j];
    }
    for (int i=0; i<citiesNum; i++)
      order[i] = newOrder[i];
  }

  public static boolean metropolis(double cost, double temprature) {
    Random random = new Random(111);
    return ((cost < 0.0) || (random.nextDouble() < Math.exp(-cost/(NORMALIZE*temprature))));
  }

 public static double calcReverseCost(City []cities,int []order,SegmentInfo segment) {
    double cost = 0.0;

    segment.precedingStart = (segment.start + cities.length - 1) % cities.length;
    segment.followingEnd = (segment.end + 1) % cities.length;
    City []citiesInvolved = new City[4];
    citiesInvolved[0] = new City(cities[order[segment.start]]);
    citiesInvolved[1] = new City(cities[order[segment.end]]);
    citiesInvolved[2] = new City(cities[order[segment.precedingStart]]);
    citiesInvolved[3] = new City(cities[order[segment.followingEnd]]);
    cost -= City.distance(citiesInvolved[0],citiesInvolved[2]);
    cost -= City.distance(citiesInvolved[1],citiesInvolved[3]);
    cost += City.distance(citiesInvolved[0],citiesInvolved[3]);
    cost += City.distance(citiesInvolved[1],citiesInvolved[2]);
    return cost;
  }

  public static void reverse(int[] order,int citiesNum,SegmentInfo segment){
   int citiesToSwap = ((segment.end - segment.start + 1 + citiesNum)
			% citiesNum) /2;

    for (int i=0; i<citiesToSwap; i++) {
      int k = (segment.start + i) % citiesNum;
      int l = (segment.end + citiesNum - i) % citiesNum;
      int tmp = order[k];
      order[k] = order[l];
      order[l] = tmp;
    }
  }

  public static double calcPathLength(City cities[],int order[]) {
    double pathLength = 0.0;

    for (int i=0; i<cities.length-1; i++) {
      int curr = order[i];
      int next = order[i+1];
      pathLength += City.distance(cities[curr], cities[next]);
    }
    int curr = order[cities.length-1];
    int next = order[0];
    pathLength += City.distance(cities[curr], cities[next]);
    return pathLength;
  }

  public static Path randomPath(City []cities) {
    Path path = new Path(cities.length);
    path.order = Permutator.randomPermutation(cities.length);
    for (int j=0;j<cities.length;j++)
      path.order[j]--;
    path.length = calcPathLength(cities,path.order);

    return path;
  }
}