//add file header comment

import java.util.*;

//add class header comment
public class AntColonyOptimization {

	/**
	 * Finds the shortest route it can (though it might not be the absolute
	 * shortest route) from the queen ant's nest to the chamber with food based
	 * on the map of the colony in the AntWorld class, and displays this route
	 * and its length.
	 *
	 * @param args
	 */
	public static void main(String[] args) {
		int[] shortestRoute = findShortestRoute(AntWorld.antWorld.MAP,
				AntWorld.antWorld.NEST_LOCATION,
				AntWorld.antWorld.FOOD_LOCATION, AntWorld.antWorld.N_ANTS,
				AntWorld.antWorld.N_ITERATIONS,
				AntWorld.antWorld.PHEROMONE_EVAPORATION_COEFFICIENT,
				AntWorld.antWorld.PHEROMONE_STRENGTH_COEFFICIENT,
				AntWorld.antWorld.SEED);
		System.out.print("Shortest route found: ");
		printRoute(shortestRoute);
		System.out.println("Length: " + calcLengthOfRoute(shortestRoute,
				AntWorld.antWorld.MAP));
	}

	/**
	 * Repeatedly finds a new set of routes from the queen's nest to the food
	 * chamber for the number of iterations given, updates the attractiveness
	 * of the tunnels based on those routes, and keeps track of the shortest
	 * route found so far (but it might not be the absolute shortest route).
	 *
	 * @param map
	 *            distances between all pairs of chambers in which is possible
	 *            to move from one chamber to the other, if it is not possible
	 *            to move from one chamber to another then the distance for
	 *            that pair is zero
	 * @param nestLocation
	 *            the chamber of the queen's nest
	 * @param foodLocation
	 *            the chamber of the food
	 * @param nAnts
	 *            the number of ants that will find a route from the nest to
	 *            the food in each iteration of the algorithm
	 * @param nIterations
	 *            the number of times to repeat the algorithm
	 * @param pheromoneEvaporationCoefficient
	 *            the proportion of each tunnel attractiveness that is taken
	 *            away when the tunnel attractivenesses are updated
	 * @param pheromoneStrengthCoefficient
	 *            a factor used in updating the tunnel attractivenesses
	 * @param seed
	 *            a seed for the random number generator
	 * @return the sequence of chambers from the queen's nest to the food
	 *         chamber, in this case without any trailing negative ones, that
	 *         had the smallest length of all such sequences that were
	 *         considered
	 */
	public static int[] findShortestRoute(double[][] map, int nestLocation,
			int foodLocation, int nAnts, int nIterations,
			double pheromoneEvaporationCoefficient,
			double pheromoneStrengthCoefficient, int seed) {
		Random random = new Random(seed);

		return null;
	}

	/**
	 * Creates the initial tunnelAttractivenesses two-dimensional double
	 * array, with a value of 1.0 for every ordered pair of indices whose
	 * value in map was positive and 0.0 for every ordered pair of indices
	 * whose value in map was zero.
	 *
	 * @param map
	 *            distances between all pairs of chambers in which is possible
	 *            to move from one chamber to the other, if it is not possible
	 *            to move from one chamber to another then the distance for
	 *            that pair is zero
	 * @return initialTunnelAttractivenesses
	 */
	public static double[][] initializeTunnelAttractivenesses(double[][] map) {

		double [][] initializeTunnelAttractivenesses = new double [map.length][map[0].length];
		for (int i =0; i < map.length; i++){
			for(int j = 0; j < map[i].length; j++){
				if (map[i][j]>0){
					initializeTunnelAttractivenesses [i][j] = 1.0;
				}
				else {
					initializeTunnelAttractivenesses [i][j] = 0.0;
				}
			}
		}
		return initializeTunnelAttractivenesses;
	}

	/**
	 * Probabilistically chooses the next chamber a particular ant should
	 * travel to based on the attractiveness of the tunnels from the ant's
	 * current location to the other chambers. To do this, it: 1. Finds the sum
	 * of the attractiveness of all the tunnels from the ant's location to
	 * all other chambers. 2. Calculates a threshold by multiplying a randomly
	 * generated double between 0.0 and 1.0 by the sum of the attractivenesses.
	 * 3. Starting from chamber 0, again sums the attractiveness of all the
	 * tunnels from the ant's location to all other chambers until the sum
	 * is greater than the threshold. The chamber in which the
     * tunnel attractiveness from the ant's location to that chamber caused the
     * sum to equal or exceed the threshold is the chamber that the ant will
     * travel to next.
	 *
	 * @param location
	 *            the current chamber of an ant
	 * @param tunnelAttractivenesses
	 *            the attractiveness of the tunnel between every ordered
	 *            pair of chambers
	 * @param random
	 *            a random number generator
	 * @return the chosen chamber that the ant will travel to
	 */
	public static int chooseTunnel(int location,
			double[][] tunnelAttractivenesses, Random random) {
		double totalAttractiveness = 0;
		double sumAttractiveness = 0;
		double threshold;
		int destination = 0;
		int count = 0;
		for (int i = location; i < tunnelAttractivenesses[location].length - 1; i++){
			totalAttractiveness += tunnelAttractivenesses[location][i];
		}
		threshold = random.nextDouble() * totalAttractiveness;
		while(sumAttractiveness < threshold){
			sumAttractiveness += tunnelAttractivenesses[location][count];
			destination = count;
			count ++;
		}
			return destination;
	}

	/**
	 * Finds a new set of routes from the queen's nest chamber to the food
	 * chamber. To do this, it: 1. Creates the antRoutes two-dimensional int
	 * array. The length of each row is the total number of chambers. 2. For
	 * every ant (i.e. row), initializes its first chamber in antRoutes to be
	 * the queen's nest chamber, and initializes all other values in antRoutes
	 * to negative one. 3. As long as is necessary, repeatedly computes for all
	 * ants (i.e., rows) in order whether or not the ant has already reached
	 * the food. If an ant has not already reached the food, a tunnel is
	 * chosen and antRoutes is updated. All ants that have not already reached
	 * the food chamber are moved for the nth time before any ant is moved for
	 * the (n + 1)th time.
	 *
	 * @param tunnelAttractivenesses
	 *            the attractiveness of the tunnel between every ordered
	 *            pair of chambers
	 * @param nestLocation
	 *            the chamber of the queen's nest
	 * @param foodLocation
	 *            the chamber of the food
	 * @param nAnts
	 *            the number of ants that will find a route from the nest to
	 *            the food in each iteration of the algorithm
	 * @param random
	 *            a random number generator
	 * @return antRoutes
	 */
	public static int[][] findAntRoutes(double[][] tunnelAttractivenesses,
			int nestLocation, int foodLocation, int nAnts, Random random) {
		int chamberIndex = 0;
		int [][] antRoutes =  new int [nAnts][tunnelAttractivenesses[0].length];
		for (int i = 0; i < antRoutes.length; i++){
			for(int j = 0; j < antRoutes[i].length; j++){
				if(j==0){
					antRoutes[i][j] = nestLocation;
				}
				else {
					antRoutes[i][j] = -1;
				}
			}
		}
		//TODO while ()
		return null;
	}

	/**
	 * Calculates the length of a route according to the distances in the map.
	 *
	 * @param route
	 *            a sequence of chambers from the queen's chamber to the food
	 *            chamber, followed by some number of negative ones
	 * @param map
	 *            distances between all pairs of chambers in which is possible
	 *            to move from one chamber to the other, if it is not possible
	 *            to move from one chamber to another then the distance for
	 *            that pair is zero
	 * @return the length of the route
	 */
	public static double calcLengthOfRoute(int[] route, double[][] map) {
		int length = 0;
		route = trimRoute(route);
		for (int i = 0; i < route.length - 1; i++) {
				length += map[route[i]][route[i + 1]];
		}
		return length;
	}

	/**
	 * Changes the attractiveness of tunnels based on the length of any routes
	 * they were used in, and then proportionately decreases the attractiveness
	 * of all of the tunnels. To do this, it: 1. For every tunnel taken in
	 * every route in antRoutes, the pheromoneStrengthCoefficient / the length
	 * of the route is added to the attractiveness of that tunnel. 2. The
	 * attractiveness of all tunnels is multiplied by 1.0 - the
	 * pheromoneEvaporationCoefficient.
	 *
	 * @param antRoutes
	 *            a set of routes from the nest to the food for a number of
	 *            ants. The first dimension corresponds to ants and the second
	 *            dimension corresponds to time. For each ant, the values over
	 *            time correspond to the chambers the ant visited. The length
	 *            of the second dimension is the total number of chambers in
	 *            the world, and the values over time after an ant has reached
	 *            the food are -1.
	 * @param tunnelAttractivenesses
	 *            the attractiveness of the tunnel between every ordered
	 *            pair of chambers
	 * @param pheromoneEvaporationCoefficient
	 *            the proportion of each tunnel attractiveness that is taken
	 *            away when the tunnel attractivenesses are updated
	 * @param pheromoneStrengthCoefficient
	 *            a factor used in updating the tunnel attractivenesses
	 * @param map
	 *            distances between all pairs of chambers in which is possible
	 *            to move from one chamber to the other, if it is not possible
	 *            to move from one chamber to another then the distance for
	 *            that pair is zero
	 */
	public static void updateTunnelAttractivenesses(int[][] antRoutes,
			double[][] tunnelAttractivenesses,
			double pheromoneEvaporationCoefficient,
			double pheromoneStrengthCoefficient, double[][] map) {

		for (int i = 0; i < antRoutes.length; i++){
			for(int j = 0; j < antRoutes[i].length; j++){
				//TODO finish this
			}
		}
	}

	/**
	 * Finds if there is a shorter route than currentShortestRoute of the
	 * routes in antRoutes using to the distances in the map to determine their
	 * length. If there is more than one route tieing for shortest, it will
	 * return the first one, starting from currentShortestRoute and
	 * continuing in increasing order through the indexes of antRoutes.
	 *
	 * @param currentShortestRoute
	 *            the sequence of chambers from the queen's nest to the food
	 *            chamber, followed by some number of negative ones, that has
	 *            the smallest length of any such sequence considered so far.
	 *            This parameter may be passed null, in which case the
	 *            currentShortestRoute is not to be considered.
	 * @param antRoutes
	 *            a set of routes from the nest to the food for a number of
	 *            ants. The first dimension corresponds to ants and the second
	 *            dimension corresponds to time. For each ant, the values over
	 *            time correspond to the chambers the ant visited. The length
	 *            of the second dimension is the total number of chambers in
	 *            the world, and the values over time after an ant has reached
	 *            the food are -1.
	 * @param map
	 *            distances between all pairs of chambers in which is possible
	 *            to move from one chamber to the other, if it is not possible
	 *            to move from one chamber to another then the distance for
	 *            that pair is zero
	 * @return the sequence of chambers from the queen's nest to the food
	 *         chamber, followed by some number of negative ones, that has the
	 *         smallest length of such sequences amongst the
	 *         currentShortestRoute and the routes in antRoutes
	 */
	public static int[] findShorterRoute(int[] currentShortestRoute,
			int[][] antRoutes, double[][] map) {
		double routeLength = 0.0;
		double shortestCurrent = calcLengthOfRoute(currentShortestRoute, map);
		for (int i = 0; i < antRoutes[0].length; i++){
			routeLength = calcLengthOfRoute(antRoutes[i], map);
			if (routeLength < shortestCurrent){
				currentShortestRoute = antRoutes[i];
			}
		}
		return currentShortestRoute;
	}

	/**
	 * Makes a new array representing the same sequence of chambers as in route
	 * but without any trailing negative ones.
	 *
	 * @param route
	 *            a sequence of chambers from the queen's nest to the food
	 *            chamber, followed by some number of negative ones
	 * @return a sequence of chambers from the queen's nest to the food
	 *         chamber
	 */
	public static int[] trimRoute(int[] route) {
		int count = 0;
		while (route[count] != -1){
			count ++;
		}
		int [] trimmedRoute = Arrays.copyOf(route, count-1);

		return trimmedRoute;
	}

	/**
	 * Displays the route horizontally on the screen separated by spaces.
	 *
	 * @param route
	 *            a sequence of chambers from the queen's nest to the food
	 *            chamber
	 */
	public static void printRoute(int[] route) {

		for (int i = 0; i <= route.length; i++){
		System.out.print(route[i] + " ");
	}
		System.out.println();
	}
}