/*************************************************************************
 *  Compilation:  javac DrawRoute.java
 *  Execution:    java DrawRoute < input.txt
 *  Dependencies: StdDraw.java StdIn.java
 *  
 *
 *************************************************************************/

import java.awt.Font;
import java.awt.Color;

public class DrawRoute { 

    public static int find(City[] cities, String city) {
	// do a binary search on the cities for city

	int lo = 0;
	int hi = cities.length - 1;

	while (lo <= hi) {
	    int mid = (lo + hi) / 2;
	    if (cities[mid].name.equals(city))
		return mid;
	    else if (cities[mid].name.compareTo(city) < 0)
		lo = mid + 1;
	    else 
		hi = mid - 1;
	}
	return -1; // not found
    }

    public static double distFrom(double lat1, double lng1, double lat2, double lng2) {
	double earthRadius = 3959;
	double dLat = Math.toRadians(lat2-lat1);
	double dLng = Math.toRadians(lng2-lng1);
	double a = 
	    Math.sin(dLat/2) * Math.sin(dLat/2) +
	    Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) *
	    Math.sin(dLng/2) * Math.sin(dLng/2);
	double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
	double dist = earthRadius * c;

	return dist;
    }

    public static double bearing(double lat1, double lng1, double lat2, double lng2) {
	double deltaLong = Math.toRadians(lng2 - lng1);

	lat1 = Math.toRadians(lat1);
	lat2 = Math.toRadians(lat2);

	double y = Math.sin(deltaLong) * Math.cos(lat2);
	double x = Math.cos(lat1) * Math.sin(lat2) - Math.sin(lat1) * Math.cos(lat2) * Math.cos(deltaLong);
	double result = Math.atan2(y, x);
	// return (result + 360.0) % 360.0;
	return result;
    }

    public static double destLat(double lat, double lng, double bearing, double d) {
	double earthRadius = 3959;

	lat = Math.toRadians(lat);
	lng = Math.toRadians(lng);

	return Math.asin(Math.sin(lat) * Math.cos(d/earthRadius) +
			 Math.cos(lat) * Math.sin(d/earthRadius) * Math.cos(bearing));
    }

    public static double destLng(double lat, double lng, double bearing, double d, double lat2) {
	double earthRadius = 3959;

	lat = Math.toRadians(lat);
	lng = Math.toRadians(lng);


	return lng + Math.atan2(Math.sin(bearing) * Math.sin(d/earthRadius) * Math.cos(lat),
				Math.cos(d/earthRadius) - Math.sin(lat) * Math.sin(lat2));
    }

    private static double[] pointRadialDistance(double lat1, double lon1, 
						double radianBearing, double radialDistance) {

	double rlat1 = Math.toRadians(lat1);
	double rlon1 = Math.toRadians(lon1);
	double rRadianBearing = Math.toRadians(radianBearing);
	double rRadialDistance = radialDistance / 3968; // miles
	
	double lat = Math.asin(Math.sin(rlat1)*Math.cos(rRadialDistance)+Math.cos(rlat1)
			       *Math.sin(rRadialDistance)*Math.cos(rRadianBearing));
	double lon;

	if(Math.cos(lat) == 0 || Math.abs(Math.cos(lat)) < 0.00001) {  // Endpoint a pole
	    lon= Math.toDegrees(rlon1);      
	}
	else {
	    lon = Math.toDegrees(((rlon1-Math.asin(Math.sin(rRadianBearing)*Math.sin(rRadialDistance)/Math.cos(rlat1))
				   +Math.PI) % (2*Math.PI)) - Math.PI);
	}


	return (new double[]{Math.toDegrees(lat), lon});
    }

    public static void main(String[] args) {

	Mercator mm = new Mercator();
	double mpm = 1609.344;  // meters per mile

	boolean DEBUG = false;
	boolean DEBUG2 = false;
	boolean FLAT = true;
	Draw canvasA = new Draw();	

	canvasA.setCanvasSize(1024,768);
	canvasA.setXscale(0,4300);
	canvasA.setYscale(0,2000);

	if (args.length > 0) {
	    if (args[0].equals("-h")) {
		System.out.println("Usage: java -jar DrawNetwork [-b <file.jpg>] < <inputRoute>");
		System.out.println("\t-b use background jpg image <file.jpg>");
		System.exit(0);
	    } else if (args[0].equals("-b")) 

		if (args.length > 1) {
		    canvasA.picture(2100,1000,args[1]);
		    canvasA.show();
		}
		else {
		    System.out.println("Please specify background file.");
		    System.exit(0);
		}
	}

	int numCities = StdIn.readInt();  // the number of cities
	City[] cities = new City[numCities];
	boolean[] parity = new boolean[numCities];  // make sure each city connected to another city 
	                                            // also has its own list of connections
	int[] numConns = new int[numCities];  // make sure the number of connections to a city
	                                      // is the same as the number of connections from it
	int[] checkSum = new int[numCities];  // keep track of number of connections to a city

	int[] connDists = new int[numCities]; // calculate the total distance of the cities immediately 
	                                      // connected to each city
	int[] checkDists = new int[numCities]; // check that the reverse connection distances sum to the same

	for (int i = 0; i < numCities; i++) {
	    String name = StdIn.readString();
	    double lat = StdIn.readDouble();
	    double lng = StdIn.readDouble();

	    if (DEBUG) 
		System.out.println(name + " " + lat + " " + lng);

	    cities[i] = new City(name,lat,lng);
	}

	    
	for (int i = 0; i < numCities; i++) {

	    double x;  // the x coordinate for cities[i]
	    double y;  // the y coordinate for cities[i]
		
	    if (FLAT) {

		// reference point
		//		double LNG = 123; // largest longitude
		//		double LAT = 25;  // smallest latitude (largest is 48)

// 		double xDiff = LNG - cities[i].lng;
// 		double yDiff = cities[i].lat - LAT;

// 		double hyp = Math.sqrt((xDiff * xDiff) + (yDiff * yDiff));

// 		if (yDiff <= 8)
// 		    x = (62.7 * xDiff + 80) * 1.4;
// 		else if (yDiff <= 16)
// 		    x = (60 * xDiff + 80) * 1.4;
// 		else
// 		    x = (57 * xDiff + 80) * 1.4;

// 		y = (69 * yDiff +  30) * 1.2;


		double [] mmTest = mm.merc(cities[i].lng,cities[i].lat);  

		double lat = cities[i].lat;
		double lng = cities[i].lng;
	      
		if (lat > 45)  // Ref: Seattle
		    x = 8990 - (mmTest[0]/mpm) * 1.03;
		else if (lat > 44)  // Ref: Burlington
		    x = 9650 - (mmTest[0]/mpm) * 1.13;
		else if (lat > 42) // Ref: Boston
		    x = 9590 - (mmTest[0]/mpm) * 1.124;
		else if (lat > 40) // Ref: Chicago
		    x = 9630 - (mmTest[0]/mpm) * 1.124;
		else if (lat > 35) // 
		    x = 10110 - (mmTest[0]/mpm) * 1.198;
		else if (lat > 30)
		    x = 10490 - (mmTest[0]/mpm) * 1.253;
		else if (lat > 27)
		    x = 10940 - (mmTest[0]/mpm) * 1.32;
		else 
		    x = 11040 - (mmTest[0]/mpm) * 1.32;

		if (lng > 120) // Ref: San-Francisco
		    y = (mmTest[1]/mpm * .70) - 875;
		else if (lng > 115) // Los-Angeles
		    y = (mmTest[1]/mpm * .76) - 1100;
		else if (lng > 110) // Phoenix
		    y = (mmTest[1]/mpm * .76) - 1190;
		else if (lng > 100) // Albuquerque
		    y = (mmTest[1]/mpm * .855) - 1485;
		else if (lng >  90) // Dallas
		    y = (mmTest[1]/mpm * .82) - 1385;
		else if (lng >  86) // Chicago
		    y = (mmTest[1]/mpm * .825) - 1400;
		else if (lng >  85) // Chattanooga
		    y = (mmTest[1]/mpm * .825) - 1370;
		else if (lng >  82) // Atlanta
		    y = (mmTest[1]/mpm * .795) - 1290;
		else if (lng >  80) // Charlotte
		    y = (mmTest[1]/mpm * .790) - 1250;
		else if (lng >  75) // Buffalo
		    y = (mmTest[1]/mpm * .805) - 1270;
		else if (lng >  70) // New York
		    y = (mmTest[1]/mpm * .795) - 1190;
		else
		    y = (mmTest[1]/mpm * .795) - 1180;
		
 		if (DEBUG) 
 		    System.out.println("City " + cities[i].name +
 				       " x/y " + x + "," + y);

	    }
	    else { // the earth is round

		// reference point
		double LNG = 87.65;
		double LAT = 39.75;
		
		double dist = distFrom(cities[i].lat,cities[i].lng,LAT,LNG);
		
		// initial bearing
		
		double theta = bearing(LAT,LNG,cities[i].lat,cities[i].lng);
		
		double lngAdj;
		double latAdj;
		double xAdj;
		double deltaX;
		if (cities[i].lng < LNG && cities[i].lat < LAT) { // Southeast
		    xAdj = 1.60;
		    deltaX = 1750;
		    theta = theta * .95;
		    lngAdj = (cities[i].lng)/(LNG);
		    latAdj = (cities[i].lat)/(LAT);
		}
		else if (cities[i].lng < LNG && cities[i].lat > LAT) { // Northeast
		    xAdj = 1.60;
		    deltaX = 1700;
		    theta = theta * 0.98;
		    lngAdj = (cities[i].lng)/(LNG);
		    latAdj = (LAT*.95)/(cities[i].lat);
		}
		else if (cities[i].lng > LNG && cities[i].lat < LAT) { // Southwest
		    xAdj = 1.45;
		    deltaX = 1850;
		    theta = theta * 1.05;
		    lngAdj = (LNG*.9)/(cities[i].lng);
		    latAdj = (cities[i].lat)/(LAT*.9);
		}
		else { // Northwest
		    xAdj = 1.60;
		    deltaX = 1800;
		    theta = theta * 1.01;
		    lngAdj = (LNG)/(cities[i].lng);
		    latAdj = (LAT*.85)/(cities[i].lat);
		}
		
		x = (-Math.sin(theta) * dist + deltaX) * xAdj;
		y = ((Math.cos(theta) * dist * lngAdj * latAdj) + 650) * 1.6;
	    }

	    Circle c = new Circle(canvasA);

	    c.setRadius(3);
	    c.setLocation(x,y);
	    c.draw();

	    if (cities[i].name.equals("Atlanta") || 
		cities[i].name.equals("Albuquerque") || 
		cities[i].name.equals("Boston") ||
		cities[i].name.equals("Salt-Lake-City") ||
		cities[i].name.equals("Chicago") ||
		cities[i].name.equals("Denver") ||
		cities[i].name.equals("Miami") ||
		cities[i].name.equals("Minneapolis") ||
		cities[i].name.equals("Dallas") ||
		cities[i].name.equals("Houston") ||
		cities[i].name.equals("Tampa") ||
		cities[i].name.equals("Los-Angeles") ||
		cities[i].name.equals("Seattle") ||
		cities[i].name.equals("Philadelphia") ||
		cities[i].name.equals("Phoenix") ||
		cities[i].name.equals("Portland") ||
		cities[i].name.equals("San-Francisco") ||
		cities[i].name.equals("Washington-DC") ||
		cities[i].name.equals("New-York")) {
		Text c1 = new Text(canvasA);
		c1.setText(cities[i].name);
		c1.setFont(new Font("SansSerif", Font.PLAIN, 9));
		c1.setLocation(x,y);
		c1.draw();
	    }

	    cities[i].x = x;
	    cities[i].y = y;

	    if (DEBUG)
		System.out.println(cities[i].name + ":" + x + "," + y);
	}

	// read the road informations
	Connection[][] map = new Connection[numCities][];

	int countConnections = 0;

	String prevToken = "";

	while (! StdIn.isEmpty()) {
	    // assume it is a city name
	    String nextToken = StdIn.readString();

	    if (nextToken.compareTo(prevToken) <= 0) {
		System.out.println(prevToken + " " + nextToken + " out of order");
	    }
	    else prevToken = nextToken;

	    if (nextToken.equals("Route:")) break;

	    int conns = StdIn.readInt(); // read the number of connections
	    
	    int indexOf = find(cities,nextToken); // find the index of the city

	    numConns[indexOf] = conns;
	    parity[indexOf] = true;

	    if (DEBUG2) {
		System.out.println("Setting up connection for " + nextToken + "/cities " + indexOf);
	    }
	   

	    map[indexOf] = new Connection[conns]; // set the array 

	    for (int i = 0; i < conns; i++) {
		String cityName = StdIn.readString();

		if (DEBUG2)
		    System.out.println("found " + cityName);

		int distance = StdIn.readInt();
		String roadName = StdIn.readString();

		int secondIndex = find(cities,cityName);

		if (secondIndex == -1) {
		    System.out.println("Can't find " + cityName);
		    continue;
		}

		connDists[indexOf] += distance;  // add to the current distance of connections 
		                                 // coming out of cities[indexOf]

		checkSum[secondIndex]++;

		if (DEBUG2) 
		    System.out.println(cityName + " " + roadName + " " + distance);

		map[indexOf][i] = new Connection(cityName,roadName,distance);

		Line l = new Line(canvasA);
		l.setColor(Color.LIGHT_GRAY);
		l.setLocation(cities[indexOf].x,cities[indexOf].y);
		l.setLocation2(cities[secondIndex].x,cities[secondIndex].y);
		l.draw();
		
	    }
	}

	for (int i = 0; i < numCities; i++) {
	    if (! parity[i]) 
		System.out.println("Missing connections for " + cities[i].name);

	    if (checkSum[i] != numConns[i]) 
		System.out.println("Wrong connection count for " + cities[i].name);
	}

	for (int i = 0; i < numCities; i++) {
	    for (int j = 0; j < map[i].length; j++) {
		int revIndex = find(cities,map[i][j].name); // find the index of city at map[i][j]
		checkDists[revIndex] += map[i][j].distance;
	    }
	}

	for (int i = 0; i < numCities; i++) {
	    if (checkDists[i] != connDists[i]) 
		System.out.println("Connection distances different for " + cities[i].name +
				   "(f:" + connDists[i] + ",to:" + checkDists[i] + ")");
	}


	// now read the route:

	if (! StdIn.isEmpty()) {

	    int total = StdIn.readInt();
	
	    boolean first = true;  // first time printing the route, print both cities
	    
	    Text c = new Text(canvasA);

	    c.setLocation(3000,1800);
	    c.setFont(new Font("SansSerif", Font.PLAIN, 16));
	    c.setText("Total Distance: " + total);
	    c.draw();
	    
	    c.setFont(new Font("SansSerif", Font.PLAIN, 9));
	    
	    while (! StdIn.isEmpty()) {
		String city1 = StdIn.readString();
		String city2 = StdIn.readString();
		String road = StdIn.readString();
		
		int index1 = find(cities,city1);
		int index2 = find(cities,city2);
		
		if (index1 == -1) {
		    System.out.println("Can't find " + city1);
		    System.exit(0);
		}
		
		if (index2 == -1) {
		    System.out.println("Can't find " + city2);
		    System.exit(0);
		}
		
		c.setColor(Color.BLACK);
		
		if (first) {
		    c.setText(city1);
		    c.setLocation(cities[index1].x,cities[index1].y);
		    c.draw();
		}
		
		c.setFont(new Font("SansSerif", Font.PLAIN, 7));
		c.setText(road);
		c.setLocation((cities[index2].x + cities[index1].x)/2,
			      (cities[index2].y + cities[index1].y)/2);
		c.draw();
		c.setFont(new Font("SansSerif", Font.PLAIN, 9));
		
		c.setText(city2);
		c.setLocation(cities[index2].x,cities[index2].y);
		c.draw();
		
		Line line = new Line(canvasA);
		line.setColor(Color.RED);
		line.setLocation(cities[index1].x,cities[index1].y);
		line.setLocation2(cities[index2].x,cities[index2].y);
		line.draw();
	    }
	}
    }
}