/**
 * This program was designed to solve the traveling salesman problem with the
 * use of a stack and minimum scanning tree. The program will be given a list
 * of cities that are so far from each other and it must calculate the shortest
 * path to visit all cities once.
 * Author: Clint Foster
 * Date: 4/29/2017
 */
package assignment6;

import java.io.File;
import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;
import java.util.ArrayList;
import java.text.NumberFormat;
import java.text.DecimalFormat;

/**
 *
 * @author CFoster
 */
public class Assignment6 {
    int CITI = 12;
    double tourCost = 0;
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
       Assignment6 test = new Assignment6();
       File input = new File("src/assignment6/tsp12.txt");
       System.out.println("The best tourCost for 12 cities is: " + test.findPath(test.populateMatrix(input)));
       System.out.println("\n");

       Assignment6 test2 = new Assignment6();
       test2.setCityAmount(13);
       File input2 = new File("src/assignment6/tsp13.txt");
       System.out.println("The best tourCost for 13 cities is: " + test2.findPath(test2.populateMatrix(input2)));
       System.out.println("\n");

       Assignment6 test3 = new Assignment6();
       test3.setCityAmount(14);
       File input3 = new File("src/assignment6/tsp14.txt");
       System.out.println("The best tourCost for 14 cities is: " + test3.findPath(test3.populateMatrix(input3)));
       System.out.println("\n");

       Assignment6 test4 = new Assignment6();
       test4.setCityAmount(15);
       File input4 = new File("src/assignment6/tsp15.txt");
       System.out.println("The best tourCost for 15 cities is: " + test4.findPath(test4.populateMatrix(input4)));
       System.out.println("\n");

       Assignment6 test5 = new Assignment6();
       test5.setCityAmount(16);
       File input5 = new File("src/assignment6/tsp16.txt");
       System.out.println("The best tourCost for 16cities is: " + test5.findPath(test5.populateMatrix(input5)));
       System.out.println("\n");

       Assignment6 test6 = new Assignment6();
       test6.setCityAmount(19);
       File input6 = new File("src/assignment6/tsp19.txt");
       System.out.println("The best tourCost for 19 cities is: " + test6.findPath(test6.populateMatrix(input6)));
       System.out.println("\n");

       Assignment6 test7 = new Assignment6();
       test7.setCityAmount(29);
       File input7 = new File("src/assignment6/tsp29.txt");
       System.out.println("The best tourCost for 29 cities is: " + test7.findPath(test7.populateMatrix(input7)));
    }

    /**
     *
     * @param amount
     */
    public void setCityAmount(int amount){
        this.CITI = amount;
    }

    /**
     * This method takes in an input file and creates a matrix of integer values.
     * It then outputs this matrix.
     * @param input The file to be used in calculating the matrix
     * @return The matrix of values
     */
    public int[][] populateMatrix(File input) {
        int [][]adjacency = new int[CITI][CITI];
        int value;

        try {
            Scanner inf = new Scanner(input);
            for (int i = 0; i < CITI && inf.hasNext(); i++) {
                for (int j = i; j < CITI && inf.hasNext(); j++) {
                    if (i == j) {
                        adjacency[i][j] = 0;
                    } else {
                        value = inf.nextInt();
                        adjacency[i][j] = value;
                        adjacency[j][i] = value;
                    }
                }
            }
            inf.close();
        } catch (IOException e) {
        }

        return adjacency;
    }

    /**
     * This method takes in the matrix of values and uses them to find the
     * shortest path. It also outputs that path and the time taken to find it.
     * @param adjacency The matrix of values needed for city to city travel
     * @return The total time used to travel the entire path
     */
    public double findPath(int[][] adjacency){
        Stack<Integer> pathStack = new Stack();
        ArrayList<Integer> visitedCities = new ArrayList<>(CITI);
        Boolean minFlag = true;
        int closestCity = 0;
        int currentCity = 0;
        int minDistance = 0;
        double tourCost = 0.0;
        long startTime = System.nanoTime();
        long endTime = System.nanoTime();
        float duration;

        visitedCities.add(0);
        pathStack.push(0);
        minFlag = false;
        System.out.println("Starting City: " + pathStack.peek());

        while(pathStack.empty() != true){
            currentCity = pathStack.peek();
            minDistance = Integer.MAX_VALUE;
            for(int i = 0; i < CITI; i++){
                if(adjacency[currentCity][i] != 0 && !visitedCities.contains(i)){
                    if(adjacency[currentCity][i] < minDistance){
                        minDistance = adjacency[currentCity][i];
                        closestCity = i;
                        minFlag = true;
                    }
                }
            }
            if(minFlag){
                tourCost = tourCost + (double)adjacency[currentCity][closestCity];
                visitedCities.add(closestCity);
                pathStack.push(closestCity);
                System.out.println("Closest City: " + closestCity);
                minFlag = false;
                continue;
            }
            pathStack.pop();
        }
        endTime = System.nanoTime();
        NumberFormat nf = new DecimalFormat("#0.00");
        duration = (endTime - startTime)/1000000;
        System.out.println("The execution time for this file is: " + nf.format(duration) + " millisecond(s)");
        return tourCost;
    }
}