package APS2;


import java.util.ArrayList;
import java.util.Random;

public class TravellingSalesman {

    ArrayList nodes;

    public TravellingSalesman() {
        nodes = new ArrayList();
    }

    static class Node {
        int x;
        int y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    /**
     * To solve the traveling salesman problem (TSP) you need to find a shortest
     * tour over all nodes in the graph where each node must be visited exactly
     * once. You need to finish at the origin node.
     *
     * In this task we will consider complete undirected graphs only with
     * Euclidean distances between the nodes.
     */

    /**
     * Adds a node to a graph with coordinates x and y. Assume the nodes are
     * named by the order of insertion.
     *
     * @param x X-coordinate
     * @param y Y-coordinate
     */
    public void addNode(int x, int y){
        nodes.add(new Node(x, y));
    }

    /**
     * Returns the distance between nodes v1 and v2.
     *
     * @param v1 Identifier of the first node
     * @param v2 Identifier of the second node
     * @return Euclidean distance between the nodes
     */
    public double getDistance(int v1, int v2) {
        Node n1 = (Node) nodes.get(v1);
        Node n2 = (Node) nodes.get(v2);

        return Math.sqrt(Math.pow(n2.x - n1.x, 2) + Math.pow(n2.y - n1.y, 2));
    }
    int[] best;
    double minimum = Integer.MAX_VALUE;

    public void permute(int[] arr, int index, int start) {

        if (index >= arr.length - 1) {
            double current = 0;
            current += getDistance(start, arr[0]);
            for (int i = 0; i < arr.length-1; i++) {
                current += getDistance(arr[i], arr[i+1]);
                if (current > minimum) {
                    break;
                }

            }
            current += getDistance(arr[arr.length-1], start);
            if (current < minimum) {
                minimum = current;
                for (int i = 0; i < arr.length; i++) {
                    this.best[i] = arr[i];
                }
            }
        }
        for (int i = index; i < arr.length; i++) {
            int t = arr[index];
            arr[index] = arr[i];
            arr[i] = t;

            permute(arr, index+1, start);

            t = arr[index];
            arr[index] = arr[i];
            arr[i] = t;
        }
    }


    /**
     * Finds and returns an optimal shortest tour from the origin node and
     * returns the order of nodes to visit.
     *
     * Implementation note: Avoid exploring paths which are obviously longer
     * than the existing shortest tour.
     *
     * @param start Index of the origin node
     * @return List of nodes to visit in specific order
     */
    public int[] calculateExactShortestTour(int start){

        int[] arrayToPermute = new int[nodes.size()-1];

        for (int i = 0; i < nodes.size()-1; i++) {
            if (i < start) {
                arrayToPermute[i] = i;
            } else {
                arrayToPermute[i] = i+1;
            }
        }
        best = new int[arrayToPermute.length];
        permute(arrayToPermute, 0, start);

        int[] shortestTourArray = new int[best.length+2];
        shortestTourArray[0] = start;
        shortestTourArray[shortestTourArray.length-1] = start;

        for (int i = 1; i <= best.length; i++) {
            shortestTourArray[i] = best[i-1];
        }

        return shortestTourArray;
    }

    /**
     * Returns an optimal shortest tour and returns its distance given the
     * origin node.
     *
     * @param start Index of the origin node
     * @return Distance of the optimal shortest TSP tour
     */
    public double calculateExactShortestTourDistance(int start){
        double total = 0;
        int[] tempNodes = calculateExactShortestTour(start);
        for (int i = 0; i < tempNodes.length-1; i++) {
            total += getDistance(tempNodes[i], tempNodes[i+1]);
        }
        return total;
    }

    /**
     * Returns an approximate shortest tour and returns the order of nodes to
     * visit given the origin node.
     *
     * Implementation note: Use a greedy nearest neighbor approach to construct
     * an initial tour. Then use iterative 2-opt method to improve the
     * solution.
     *
     * @param start Index of the origin node
     * @return List of nodes to visit in specific order
     */
    public int[] calculateApproximateShortestTour(int start){
        throw new UnsupportedOperationException("You need to implement this function!");
    }

    /**
     * Returns an approximate shortest tour and returns its distance given the
     * origin node.
     *
     * @param start Index of the origin node
     * @return Distance of the approximate shortest TSP tour
     */
    public double calculateApproximateShortestTourDistance(int start){
        double total = 0;
        int tour[] = calculateApproximateShortestTour(start);
        for (int i = 0; i < tour.length-1; i++) {
            total += getDistance(tour[i], tour[i+1]);
        }
        return total;
    }

    /**
     * Constructs a Hamiltonian cycle by starting at the origin node and each
     * time adding the closest neighbor to the path.
     *
     * Implementation note: If multiple neighbors share the same distance,
     * select the one with the smallest id.
     *
     * @param start Origin node
     * @return List of nodes to visit in specific order
     */
    public int[] nearestNeighborGreedy(int start){
        throw new UnsupportedOperationException("You need to implement this function!");
    }

    /**
     * Improves the given route using 2-opt exchange.
     *
     * Implementation note: Repeat the procedure until the route is not
     * improved in the next iteration anymore.
     *
     * @param route Original route
     * @return Improved route using 2-opt exchange
     */
    private int[] twoOptExchange(int[] route) {
        throw new UnsupportedOperationException("You need to implement this function!");
    }

    /**
     * Swaps the nodes i and k of the tour and adjusts the tour accordingly.
     *
     * Implementation note: Consider the new order of some nodes due to the
     * swap!
     *
     * @param route Original tour
     * @param i Name of the first node
     * @param k Name of the second node
     * @return The newly adjusted tour
     */
    public int[] twoOptSwap(int[] route, int i, int k) {
        throw new UnsupportedOperationException("You need to implement this function!");
    }

    /**
     * Returns the total distance of the given tour i.e. the sum of distances
     * of the given path add the distance between the final and initial node.
     *
     * @param tour List of nodes in the given order
     * @return Traveled distance of the tour
     */
    public double calculateDistanceTravelled(int[] tour){
        double total = 0;
        for (int i = 0; i < tour.length-1; i++) {
            total += getDistance(tour[i], tour[i+1]);
        }
        return total + getDistance(tour[tour.length-1], tour[0]);
    }

    public static void main(String[] args) {
        TravellingSalesman ts = new TravellingSalesman();

        Random r = new Random(35164);

        for (int i = 0; i < 12; i++) {
            ts.addNode(r.nextInt(50), r.nextInt(50));
        }

        System.out.println(ts.calculateDistanceTravelled(ts.calculateExactShortestTour(0)));
        System.out.println(ts.calculateExactShortestTourDistance(0));

        ts.addNode(r.nextInt(50), r.nextInt(50));
        System.out.println(ts.calculateDistanceTravelled(ts.calculateExactShortestTour(0)));
        System.out.println(ts.calculateExactShortestTourDistance(0));

    }
}