/** The Traveling Sales Person problem solution class
 * This program includes four TSP solution methods
 * @author Arūnas Kašinskas
 * @author i5arka@vaidila.vdu.lt
 * @version 2.0 
*/
import java.awt.Dimension;

public class Tsp {


//** public sector

   	/** Maximal cities number */
   public static final int MAXCITIES = 101;   
   	/** Array of current cities x co-ordinates */
   public int xCities[] = new int[MAXCITIES];				
   	/** Array of current cities y co-ordinates */
   public int yCities[] = new int[MAXCITIES];
	/** Array of current route */
   public int route[] = new int[MAXCITIES+1];


//** private sector

   	/** Current maximal cities number */
   private int citiesLimit;
   	/** Current maximal x co-ordinate value */
   private int maxX;
   	/** Current maximal y co-ordinate value */
   private int maxY;
   	/** Current minimal x co-ordinate value */
   private int minX;
   	/** Current minimal y co-ordinate value */
   private int minY;
   	
   private int cities;							// current cities number
   private int iterations;						// number of iterations
   private double[][] d = new double[MAXCITIES][MAXCITIES];     	// distances matrix
   private boolean[] visitedCities = new boolean [MAXCITIES];		// city is visited or not 

   private int[] sortedByY = new int[MAXCITIES];
	      
//** constructors

   	/**  Constructs a TSP using users parameters. 
   	 @param minx Initial start x co-ordinate of the map
   	 @param miny Initial start y co-ordinate of the map
   	 @param width Map width
   	 @param height Map height
   	 @param citiesNr Cities limit
   	  */ 
   public Tsp(int minx, int miny, int width, int height, int citiesNr) {
   	minX = minx;
   	minY = miny;
   	maxX = minx + width;
   	maxY = miny + height;
   	citiesLimit = citiesNr;
   	cities = 0;
   	iterations = 0;
   }
   	/**  Constructs a TSP using users parameters. 
   	 @param width Map width
   	 @param height Map height
   	 @param citiesNr Cities limit
   	  */ 
   public Tsp(int width, int height, int citiesNr) {
   	this (0, 0, width, height, citiesNr);
   }
   
   	/** Default constructor. Constructs a TSP with map, which is 200 width and 200 height. City limit is 100 */ 
   public Tsp() {
	this (0, 0, 200, 200, MAXCITIES);
   }
   
//***   

//** public methods sector

/** Returns string, representing main parameters of Tsp
  * @return Returns Tsp param string
*/
     public String getTspParams(){
     	return "Minx: " + minX + " Miny: " + minY + " Maxx: " + maxX + " Cities limit: " + citiesLimit
     			+ " Map size: " + (maxX - minX) + "x" + (maxY - minY);
     }
     

/** Generates random test data. Generates random cities number and random cities co-ordinates. */
     public void randomTestData(){
        int nr;
        cities = 0;
        nr = (int)(3 + Math.random()*(citiesLimit - 3));
     	for (int i=0; i<nr; i++){
     		xCities[i] = (int)(minX + Math.random()*(maxX - minX));
     		yCities[i] = (int)(minY + Math.random()*(maxY - minY));
     		cities++;
     	}
     }

/** Changes current maximal cities number 
  * @param maxCities New maximal cities value.
  * @return Returns <I> true </I> if value was changed and <I> false </I> if not.
*/
     public boolean setCitiesLimit (int maxCities){
     	if (maxCities < MAXCITIES) {
     		citiesLimit = maxCities;
     		return true;
     	}
     	return false;
     }

/** Changes cities number 
  * @param citiesNr New cities value.
  * @return Returns <I> true </I> if value was changed and <I> false </I> if not.
*/
     public boolean setCitiesNr (int citiesNr){
     	if (citiesNr < MAXCITIES) {
     		cities = citiesNr;
     		return true;
     	}
     	return false;
     }

/** Returns the value of current cities limit
  * @return Returns the value of current cities limit
  */

     public int getCitiesLimit () {
     	return citiesLimit;
     }

/** Changes minimal x co-ordinate value
  * @param minx New minimal x co-ordinate value
  * @return Returns <I> true </I> if value was changed and <I> false </I> if not.
*/
     public boolean setMinX (int minx) {
     	if (minx < maxX) {
     		minX = minx;
     		return true;
     	}
     	return false;
     }

/** Changes minimal y co-ordinate value
  * @param miny New minimal y co-ordinate value
  * @return Returns <I> true </I> if value was changed and <I> false </I> if not.
*/
     public boolean setMinY (int miny) {
     	if (miny < maxY) {
     		minY = miny;
     		return true;
     	}
     	return false;
     }

/** Changes maximal x co-ordinate value
  * @param maxx New minimal x co-ordinate value
  * @return Returns <I> true </I> if value was changed and <I> false </I> if not.
*/
     public boolean setMaxX (int maxx) {
     	if (maxx > minX) {
     		maxX = maxx;
     		return true;
     	}
     	return false;
     }

/** Changes maximal y co-ordinate value
  * @param maxy New minimal y co-ordinate value
  * @return Returns <I> true </I> if value was changed and <I> false </I> if not.
*/
     public boolean setMaxY (int maxy) {
     	if (maxy > minY) {
     		maxY = maxy;
     		return true;
     	}
     	return false;
     }

/** Returns tsp map size
  * @return Returns dimension of tsp map size.
*/

	public Dimension getMapSize() {
		return new Dimension(maxX - minX, maxY - minY);	
	}

/** Removes the cities, which are out of map bounds 
  * @return No return value
*/
     public void removeOutOfBoundsCities(){
	
	int[] temp = new int[MAXCITIES];
	int j = 0;
     	for (int i = 0; i < cities; i ++){
     		if ((xCities[i] > maxX) || (yCities[i] > maxY) || (xCities[i] < minX) || (yCities[i] < minY)){
     			temp[j] = i;
     			j++;
     		}
     	}
     	
	for (int i = j-1; i>-1; i--){
		removeCity(temp[i]);
	}
     }

/** Removes defined city from the map 
  * @param  cityNr City number in array.
  * @return Returns <I> true </I> if city was removed and <I> false </I> if not.
  */

     public boolean removeCity(int cityNr){

     	if (cityNr < cities) {
     	   while (cityNr < cities-1) {
			
		if (cityNr < MAXCITIES - 1) {
			xCities[cityNr] = xCities[cityNr+1];
			yCities[cityNr] = yCities[cityNr+1];
			cityNr++;
		    } else {
		    	xCities[cityNr] = 0;
     			yCities[cityNr] = 0;
     			cityNr++;
     		    }
		}
		cities--;
		return true;
	}
	return false;
     }

// **************

/** Adds a city to the map 
  * @param x New city x co-ordinate
  * @param y New city y co-ordinate
  * @return Returns <I> true </I> if city was added and <I> false </I> if not.
*/
     public boolean addCity(int x, int y) {
     	if (cities < citiesLimit) {
     	   if ((x <= maxX) && (y <= maxY) && (x >= minX) && (y >= minY)){
           	xCities[cities] = x;
           	yCities[cities] = y;
	        cities++;
	        return true;
           }
        }
        System.err.println("Can not add new city");
        return false;
     } 

/** Returns current number of added cities 
  * @return Returns current number of added cities 
  */
     public int getCitiesNr(){
     	return cities;
     }

/** Returns current iterations number 
  * @return Returns number of iterations, needed to calculate TSP distance and route
*/
     public int getIterationsNumber(){
     	return iterations;
     }

/** Clears all cities from the map */
     public void clearCities(){
     	cities = 0;
     	iterations = 0;
     }
    
/** Calculates the traveling sales person distance using Nearest Neighbour calculation method
  * @return Returns TSP distance.
*/
     public double nearestNeighbour() {
     	initCalc();
     	return nearest_n(0);
     }

/** Calculates the traveling sales person distance using Repeatetive Nearest Neighbour calculation method
  * @return Returns TSP distance.
  */
     public double repeatetiveNearestNeighbour(){
    	
    	double min_dist = Double.MAX_VALUE;
    	double nn_dist;
        int rep_route[] = new int[MAXCITIES+1];		// a copy of route used for rnn method    	
    	
    	initCalc();
    	for (int i = 0; i<cities; i++){
    		// clear visited cities values
    		for (int k=0; k<cities; k++)
    			visitedCities[k] = false;

    		// get the distance and route starting from the city i	
		nn_dist = nearest_n(i);
		if (nn_dist < min_dist){
			min_dist = nn_dist;
			for (int j=0; j<cities+1; j++)
				rep_route[j] = route[j];
		}
    	}
	for (int j=0; j<cities+1; j++)
		route[j] = rep_route[j];
	
	return min_dist;
     }

/** Calculates the traveling sales person distance using Random Two Optimals Exchange calculation method 
  * @return Returns TSP distance.
  */
    public double randomTwoOptimals() {
    	initCalc();
    	return two_optimals(1);
    }
    
/** Calculates the traveling sales person distance using Nearest Neighbour initial value Two Optimals Exchange calculation 
  * @return Returns TSP distance.
  */
    public double nnTwoOptimals() {
    	initCalc();
    	return two_optimals(0);
    }

// two optimals exchange algorythm
    private double two_optimals(int which){

	int[] ptr= new int[MAXCITIES];
	int ahead, i1, i2, index, j1, j2, last, limit, n1, n2, next, s1=0, s2=0, t1=0, t2=0;
	
	double max, max1, tweight=0;
	int n = cities;
	if (which == 0){
		tweight = nearest_n(0);	
	} else {
		for (int i=0; i < n; i++){
			route[i] = i;
			iterations++;					
			if (i != n-1){
				tweight = tweight + d[i+1][i];
			}
		}
		route[n] = 0;
		tweight = tweight + d[0][n-1];
		iterations++;		
	}

	n1 = n - 1;
	n2 = n1 - 1;
	
	// ptr yra masyvas, kuris parodo i kuri miesta vaziuoja sekanciame zingsnyje   
	for (int i = 0; i < n1; i++)
		ptr[route[i]] = route[i+1];
	ptr[route[n1]] = route[0];
	
	//lygina visas ne galimas poras (poros negali tureti bendru virsuniu)
	do {
		max = 0;
		i1 = 0; 
		for (int i=0; i < n2; i++) {
			limit = (i == 0) ? n1:n;
			i2 = ptr[i1];
			j1 = ptr[i2];
			for (int j = i + 2; j < limit; j++) {
				iterations++;		
				j2 = ptr[j1];
				max1 = d[i1][i2] + d[j1][j2] - (d[i1][j1] + d[i2][j2]);
				
				// Jei surasta pora, kurios virsunes sukeitus vietomis
				// gaunamas trumpesnis atstumas, tai virsunes reikia isaugoti
				
				if (max1 > max) {
					s1 = i1;
					s2 = i2;
					t1 = j1;
					t2 = j2;
					max = max1;
				}
				j1 = j2;
			}
			i1 = i2;
		}

	// Jei turime geresni marsruta , reikia pakeisti informacija.
		if (max > 0) {

		//  Sukeicia virsunes
			ptr[s1] = t1;
			next = s2;
			last = t2;

			do {	ahead = ptr[next];
				ptr[next] = last;
				last = next;
				next = ahead;
			} while (next != t2);
		//  Sumazina marsruto ilgi
			tweight = tweight - max;
		}
	} while (max != 0);

	// Pakeicia marsruta.
	index = 0;
	for (int i=0; i < n; i++) {
		route[i] = index;
		index = ptr[index];
	}     
        return tweight;	
    }

// nearest neighbour method      
     private double nearest_n (int start){      
      	
      	int next_c = 0, i, n; 
      	double mindist, distance = 0;
      	i = start;
        for(n = 0; n < cities; n++){
             mindist = Double.MAX_VALUE; // let it be, primary minimal distance
             for(int j = 0; j < cities; j++){
	        iterations++;
        	if(n != cities-1){  // to the start city we return in the last step
        	   if ((mindist > d[i][j])&&(i != j) && (visitedCities[j] != true) && (j != start)){
           		mindist = d[i][j];
           	 	next_c = j;
              	   }
          	} else {
              	   mindist = d[i][start]; 
              	   next_c = start;
          	}
             }     	
           	  	 	
	     visitedCities[i] = true;
             distance = distance + mindist;
             route[n] = i;		// add visited city to a route array
             i = next_c; 		// city to which we go
      	} 

	// return to the start city
	visitedCities[i] = true;
      	route[n] = i;
      	return distance;
     }

// init the matrix of distances values      
     private void initDistances(){
       	for (int i=0; i<cities; i++){
       	  for (int j=0; j<cities; j++){
       		if (i == j){
       		  d[i][j] = 0;
       		} else {
       		  d[i][j] = (Math.sqrt((double)((xCities[i]-xCities[j])*(xCities[i]-xCities[j]) + (yCities[i]-yCities[j])*(yCities[i]-yCities[j]))));
       		}
       	  }
       	  visitedCities[i] = false;		// at the begining all cities are not visited
       	  iterations = 0;			// at the beginning number of iterationss is zero
       	}
     }

// method used to initialize calculations 
     private void initCalc() {
     	initDistances();
     }
     
} ///~