package travellingSalesman;

import static java.lang.Math.atan2;
import static java.lang.Math.cos;
import static java.lang.Math.sin;
import static java.lang.Math.sqrt;
import static java.lang.Math.toRadians;

import java.util.Formatter;

/**
 * Holds information about a single city.
 * 
 * @author David Matuszek
 */
public class City {
    private String state;
    private String city;
    private static int nextNumber = 0;
    private int number;
    private double latitude;
    private double longitude;

    /**
     * Creates a City with the given information.
     * 
     * @param state The name of the state containing this city.
     * @param city The name of this city.
     * @param latitude The approximate latitude of this city.
     * @param longitude The approximate longitude of this city.
     */
    public City(String state, String city, double latitude, double longitude) {
        this.state = state;
        this.city = city;
        this.number = nextNumber++;
        this.latitude = latitude;
        this.longitude = longitude;
    }

    /**
     * Returns the name of the state containing this city.
     *  
     * @return The state name.
     */
    public String getStateName() {
        return state;
    }

    /**
     * Returns the name of this city.
     * 
     * @return The city name.
     */
    public String getCityName() {
        return city;
    }

    /**
     * Returns a unique numerical identifier for this city, in the range
     * 0 to number of cities - 1.
     * 
     * @return An ID for this city.
     */
    public int getNumber() {
        return number;
    }

    /**
     * Returns the latitude of this city.
     * 
     * @return The city latitude.
     */
    public double getLatitude() {
        return latitude;
    }

    /**
     * Returns the longitude of this city.
     * 
     * @return The city longitude.
     */
    public double getLongitude() {
        return longitude;
    }

    /**
     * Returns a printable string representing this city.
     * 
     * @return A brief description of this city.
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        Formatter f = new Formatter();
        f.format("%2d  %-25s [%7.4f, %8.4f]", number, city +
                 ", " + state, latitude, longitude);
        return f.toString();
    }
    
    /**
     * Returns the total distance for a trip of the given cities
     * in order, returning to the starting point.
     * 
     * @param cities The ordered sequence of cities to visit. 
     * @return The total distance of a round trip.
     */
    public static double roundTripDistance(City[] cities) {
        double cost = 0;
        for (int i = 0; i < cities.length; i++) {
            cost += cities[i].distanceTo(cities[(i + 1) % cities.length]);
        }
        return cost;
    }

    /**
     * Returns the distance between this city and the other city.
     * 
     * @param that The other city.
     * @return The distance between the cities.
     */
    public double distanceTo(City that) {
        return distance(this.latitude, this.longitude, that.latitude, that.longitude);
    }

    /**
     * Computes the distance between two locations on Earth.
     * 
     * @param lat1degrees Latitude, in degrees, of the first location.
     * @param long1degrees Longitude, in degrees, of the first location.
     * @param lat2degrees Latitude, in degrees, of the second location.
     * @param long2degrees Longitude, in degrees, of the second location.
     * @return The distance, in miles, between the two locations.
     */
    private static double distance(double lat1degrees, double long1degrees,
            double lat2degrees, double long2degrees) {
        final double earthRadius = 3956; // miles
        double lat1 = toRadians(lat1degrees);
        double long1 = toRadians(long1degrees);
        double lat2 = toRadians(lat2degrees);
        double long2 = toRadians(long2degrees);
        double dLat = lat2 - lat1;
        double dLong = long2 - long1;
        double sinHalfLat = sin(dLat / 2);
        double sinHalfLong = sin(dLong / 2);
        double a = square(sinHalfLat) + cos(lat1) * cos(lat2) * square(sinHalfLong);
        double c = 2 * atan2(sqrt(a), sqrt(1 - a));
        return earthRadius * c;
    }

    private static double square(double x) {
        return x * x;
    }
}