package bruthforth_tsp;

//========================= TSPComputation ================================

import popcorn.*;
import java.io.Serializable;

public class TSPComputation implements Runnable, Minimizer {

   // number of random pahts to be tried by each computation-packet
   private static final int NUMBER_OF_ITERATIONS = 500;

   ComputationObserver observer;

   int n; // number of cities
   double[][] map; // the distances map
   int[] path; // the current best path
   double min; // the total distance of the current best path
   int packetSent,packetArrived;

   public TSPComputation(double[][] map, ComputationObserver observer) {
       this.observer=observer;
       this.map=map;
       n=map.length;
       path=Permutator.randomPermutation(n);
       min=totalDistance();
   }

   public void start() {
      new Thread(this).start();
   }

   public void run() {
      observer.updateStatus(min,packetSent,packetArrived);
      observer.updateDisplay(path);
      for (;;) {
         ComputationPacket packet =
            new RandomTravelingSalesmanPacket(map,NUMBER_OF_ITERATIONS,this);
         packet.go();
         packetSent++;
         synchronized(this) {
            if (packetSent>packetArrived+10) {
                try {
                    wait();
                } catch (InterruptedException e) {}
            }
         }
      }
      //Computation.collectAll();
   }

   public synchronized void updateMinimum(Object argument, double value) {
      packetArrived++;
      notify();
      int[] newPath = (int[]) argument;
      if (value<min) {
         min=value;
         path=newPath;
         observer.updateDisplay(path);
      }
      observer.updateStatus(min,packetArrived,packetSent);
   }

   double totalDistance() {
       double sum=0.0;
       for (int i=0; i<n; i++) {
           sum+=map[path[i]-1][path[(i+1)%n]-1];
       }
       return sum;
  }
}

//-------------------------------- Minimizer ----------------------------------------------

/**
 * Minimizer interface is ment for object that seek the minimal value or minarg, from a
 * sequence of values.
 */
interface Minimizer {
   /**
    * Update the minimal value and minarg according to a new argument.
    */
   public void updateMinimum(Object argument, double value);
}

//------------------------- RandomTravelingSalesmanPacket ---------------------------------

/**
 * A RandomTravelingSalesmanPacket runs over a random set of permutations, in trying to solve
 * a TravelingSalesman problem.
 */
class RandomTravelingSalesmanPacket extends ComputationPacket {

   private Minimizer resultHandler;

   /**
    * Contructs a RandomTravelingSalesmanPacket for checking the minimal path over a set of
    * random paths.
    * @param distance The distances matrix (distance[i][j] is the distance from city i to j).
    * @param numberOfIterations The number of random paths to be try.
    */
   public RandomTravelingSalesmanPacket(double[][] distance, int numberOfIterations,
                                        Minimizer resultHandler) {
      super(new TravelingSalesmanComputelet(distance,numberOfIterations));
      this.resultHandler=resultHandler;
   }

   public void completed() {
      PathLenghtPair p = (PathLenghtPair) getResult();
      resultHandler.updateMinimum(p.first, ((Double)p.second).doubleValue());
   }
}

//------------------------- TravelingSalesmanComputelet -----------------------------

/**
 * A TravelingSalesmanComputelet runs over a random set of permutations, in trying to solve
 * a TravelingSalesman problem.
 */
class TravelingSalesmanComputelet implements Computelet, Serializable {

   private double[][] distance;
   private int iterations; // total number of iterations.
   private int n; // number of cities

   /**
    * Constructs a TravelingSalesmanComputelet for checking the minimal path, over
    * a set of random paths.
    * @param distance The distances matrix (distance[i][j] is the distance from city i to j).
    * @param numberOfIterations The number of random paths to be try.
    * Assumption: <em>distance</em> is a square matrix.
    */
   public TravelingSalesmanComputelet(double[][] distance, int numberOfIterations) {
      this.distance=distance;
      n=distance.length;
      iterations=numberOfIterations;

      // temp - make sure that the class PathLenghtPair comes as well
      new PathLenghtPair(new int[4],new Double(3.4));
      new Permutator(1);
   }

   public Object compute() {
      double min=Double.POSITIVE_INFINITY; // the minimal distance so far
      int[] bestPath=null; // the best path (permutation on the cities)
      for (int i=0; i<iterations; i++) {
         int[] randomPath = Permutator.randomPermutation(n);
         if (totalDistance(randomPath)<min) {
            min=totalDistance(randomPath);
            bestPath=randomPath;
         }
      }
      return new PathLenghtPair(bestPath, new Double(min));
   }

   private double totalDistance(int[] path) {
      double sum=0.0;
      for (int i=1; i<n; i++)
         sum+=distance[path[i-1]-1][path[i]-1];
      sum+=distance[path[n-1]-1][path[0]-1];
      return sum;
   }
}

//-------------------------------------- PathLenghtPair ----------------------------------------------

class PathLenghtPair implements Serializable {

   public int[] first;
   public Double second;

   public PathLenghtPair(int[] first, Double second) {
      this.first=first;
      this.second=second;
   }
}