/* Programmer: Sriram Pemmaraju. Oct 24th, 2007

*/
import java.util.StringTokenizer;
import java.util.Arrays;
import java.io.*;

public class City{

		// Arrays to keep track of info. related to each city
		private String[] cityName;
		private String[] cityState;
		private int[] cityLat;
		private int[] cityLong;
		private int[] cityPop;

		// 2-D array to keep track of pairwise distances between cities
		private int[][] distances;

		// boolean 1-D array to keep track of selected cities
		private boolean[] currentCities;

		// boolean 2-D array to keep track of selected edges
		private boolean[][] currentEdges;

		// number of cities
		private static int numCities = 128;
		
		public City() {
			//Allotting the space for each 1-D array
			cityName = new String[numCities];
			cityState = new String[numCities];
			cityLat = new int[numCities];
			cityLong = new int[numCities];
			cityPop = new int[numCities];
			currentCities = new boolean[numCities];

			// Select all cities initially 
			for(int i = 0; i < numCities; i++)
				currentCities[i] = true;
		
			// Allocate space for each 2-D array. These arrays have 0 elements in row 0,
			// 1 element in row 1, 2 elements in row 2, etc.
			distances = new int[numCities][];
			currentEdges = new boolean[numCities][];

			for(int i = 0; i < numCities; i++)
			{
				distances[i] = new int[i];
				currentEdges[i] = new boolean[i];

				// Select all edges initially
				for(int j = 0; j < i; j++)
					currentEdges[i][j] = true;
			}
			
			try{
				
				// Construct a buffered reader object and connect it to the files "miles.dat"
				BufferedReader in = new BufferedReader(new FileReader("miles.dat"));

				// A counter that keeps track of the index of the current city being read
				int cityNumber = 0;
			
				// While-loop for reading in data from "miles.dat." At the beginning of the while-loop 
				// the expectation is that we'll be reading a line containing the city name. Instead,
				// if we encounter a line that starts with "*" then we skip to the next line
				while(cityNumber < numCities)
				{
					// Read in a line
					String line = in.readLine();
				
					// Skip the rest of the loop if line starts with a "*"
					if(line.charAt(0) == '*')
						continue;
		
					// Otherwise tokenize the line
					StringTokenizer tokenizedLine= new StringTokenizer(line, ",[]");
				
					//Putting actual data into correct position in the array
					cityName[cityNumber] = tokenizedLine.nextToken();
					cityState[cityNumber]= (tokenizedLine.nextToken()).trim(); // trim() gets rid of leading/trailing blanks
					cityLat[cityNumber] = Integer.parseInt(tokenizedLine.nextToken());
					cityLong[cityNumber] = Integer.parseInt(tokenizedLine.nextToken());
					cityPop[cityNumber] = Integer.parseInt(tokenizedLine.nextToken());

					//while loop to put distances in the array; this may need to read several lines
					int mileNumber = 0;
					while (mileNumber < cityNumber)
					{
						// Read a mileage line and tokenize it
						String mileage = in.readLine();
						StringTokenizer tokenizedMileage = new StringTokenizer(mileage, " ");
					
						// Read all the mileage data in this line into row cityNumber; increment 
						// mileNumber after each read
						while(tokenizedMileage.hasMoreTokens())
						{
							distances[cityNumber][cityNumber-mileNumber-1] = Integer.parseInt(tokenizedMileage.nextToken());
							//distances[cityNumber][mileNumber] = Integer.parseInt(tokenizedMileage.nextToken());
							mileNumber++;
						}

					} // end of while reading distances

					cityNumber++;
				} // end of while reading cities
			
			} // end of try
			catch (IOException e) {System.out.println("File not found.");}
			
	} // end of City() constructor

	// Constructs a String array of all distinct state names of selected cities 
	String[] getStates()
	{
		String[] states = new String[numCities];
		int count = 0;
		for(int i = 0; i < numCities; i++)
			states[count++] = cityState[i];

		// Sort the states array
		Arrays.sort(states);

		// Get rid of duplicates and create a new String array with
		// only distinct states
		String[] distinctStates = new String[count];
		int distinctCount = 0;
		String previousState = null;
		for(int i = 0; i < count; i++)
			if(!states[i].equals(previousState))
			{
				distinctStates[distinctCount++] = states[i];
				previousState = states[i];
			}
		

		// Resize the distinctStates array so that it has exactly the right size
		String[] newDistinctStates = new String[distinctCount];
		for(int i = 0; i < distinctCount; i++)
			newDistinctStates[i] = distinctStates[i];

		return newDistinctStates;
	}


	// Selects all cities
	void selectAllCities()
	{
		for(int i = 0; i < numCities; i++)
			currentCities[i] = true;
	}

	// Unselects all cities
	void unselectAllCities()
	{
		for(int i = 0; i < numCities; i++)
			currentCities[i] = false;
	}
		

       // Select cities: This version of the method allows us to select cities by name or by state name
        // This method only selects from among those cities that have already been selected
        void selectCities(String attribute, String lowerBound, String upperBound)
        {
                if(attribute.equals("name"))
                {
                        // Scan all cities and unselect those select cities whose latitude is out of bounds
                        for(int i = 0; i < numCities; i++)
                                if((currentCities[i])&&((cityName[i].compareTo(lowerBound) < 0) || (cityName[i].compareTo(upperBound) > 0)))
                                        currentCities[i] = false;
                }

                if(attribute.equals("state"))
                {
                        // Scan all cities and unselect those select cities whose latitude is out of bounds
                        for(int i = 0; i < numCities; i++)
                                if((currentCities[i])&&((cityState[i].compareTo(lowerBound) < 0) || (cityState[i].compareTo(upperBound) > 0)))
                                        currentCities[i] = false;
                }


        }



	// Select cities: This version of the method allows us to select cities by latitude or longitude
	// This method only selects from among those cities that have already been selected
	void selectCities(String attribute, int lowerBound, int upperBound)
	{
		if(attribute.equals("latitude"))
		{
			// Scan all cities and unselect those select cities whose latitude is out of bounds
			for(int i = 0; i < numCities; i++)
				if((currentCities[i])&&((cityLat[i] < lowerBound) || (cityLat[i] > upperBound)))
					currentCities[i] = false;
		}

                if(attribute.equals("longitude"))
                {
                        // Scan all cities and unselect those select cities whose latitude is out of bounds
                        for(int i = 0; i < numCities; i++)
                                if((currentCities[i])&&((cityLong[i] < lowerBound) || (cityLong[i] > upperBound)))
                                        currentCities[i] = false;
                }

                if(attribute.equals("population"))
                {
                        // Scan all cities and unselect those select cities whose latitude is out of bounds
                        for(int i = 0; i < numCities; i++)
                                if((currentCities[i])&&((cityPop[i] < lowerBound) || (cityPop[i] > upperBound)))
                                        currentCities[i] = false;
                }


	}

	// Selects edges whose distance lies in-between the specified lower and upper bounds,
	// inclusive of the bounds. This function pays no attention to past edge selections
	void selectEdges(int lowerBound, int upperBound)
	{
		for(int i = 0; i < numCities; i++)
			for(int j = 0; j < i; j++)
				if((distances[i][j] >= lowerBound) && (distances[i][j] <= upperBound))
					currentEdges[i][j] = true;
				else
					currentEdges[i][j] = false;
	}


	// Constructs and returns a graph whose vertices are the set of selected cities and whose
	// edges are selected edges that connected pairs of selected cities
	myListGraph makeGraph()
	{
		
		// Create an empty graph
		myListGraph g = new myListGraph();

		// Add all selected cities to it
		for(int i = 0; i < numCities; i++)
			if(currentCities[i])
				g.addVertex(cityName[i]+" "+cityState[i]);
			
		
		// Add all selected edges between pairs of selected cities
		for(int i = 0; i < numCities; i++)
			for(int j = 0; j < i; j++)
				if((currentEdges[i][j])	&& (currentCities[i]) && (currentCities[j]))
					g.addEdge(cityName[i]+" "+cityState[i], cityName[j]+" "+cityState[j]);

		// return the constructed graph
		return g;
	}

	// Prints the selected cities
	void printCities()
	{
		// Scan the list of all cities and print out those that are selected
		for(int i = 0; i < numCities; i++)
			if(currentCities[i])
				System.out.println(cityName[i]+" "+cityState[i]);
	}

	// Gets the populations of selected cities in an int array
	int[] getPopulations()
	{

		// First count the number of selected cities
		int count = 0;
		for(int i = 0; i < numCities; i++)
			if(currentCities[i])
				count++;

		// Use this count to define an array of the correct size to hold the
		// populations
		int[] popArray = new int[count];

		// Fill this array with the populations of the selected cities
		count = 0;
		for(int i = 0; i < numCities; i++)
			if(currentCities[i])
			popArray[count++] = cityPop[i];

		return popArray;
	}
	
	// A simple getIndex method to help test the constructor
	int getIndex(String city, String state)
	{
			
		int location;
		for(location = 0; location < numCities; location++)
			if((cityName[location].equals(city)) && (cityState[location].equals(state)))
				return location;

		return -1;

	}


	// Print information about a city, given a city index
	void printCityInfo(int index)
	{
		System.out.println(cityName[index] + " " + cityState[index] + " " + cityLat[index] + " " + cityLong[index] + " " + cityPop[index]);
	}
	

	// Print distance information between a given pair of cities
	void printDistanceInfo(int i, int j)
	{
		if(i < j)
			System.out.println(distances[j][i]);
		else
			System.out.println(distances[i][j]);
	}

	//Main method
	public static void main(String[] args) {
		City newCity = new City();
		myListGraph g;
		String[] path;

		System.out.println("---------------------------------------------------------------------------------------");
		System.out.println("EXPERIMENT 1");
		// Select edges in the range 0 through 200 miles and make a graph
		int upperBound = 200;
		while(true)
		{
			newCity.selectEdges(0, upperBound);
			g = newCity.makeGraph();
			System.out.println("Constructed a graph with all cities and edges only at most " + upperBound + " miles long.");
			System.out.println("Vertices = " + g.numberOfVertices() + " " + "Edges = " + g.numberOfEdges());
			
			// Compute shortest path between Yakima, WA and Wilmington, DE
                	path = g.shortestPath("Yakima WA", "Wilmington DE");
                	if(path == null)
                        	System.out.println("There is no path from Yakima, WA to Wilmington, DE");
                	else
                	{
                        	System.out.println("The shortest path from Yakima, WA to Wilmington, DE is");
                        	for(int i = 0; i < path.length; i++)
                                	System.out.print(path[i]+" ");
                        	System.out.println(" ");
				break;
                	}
			upperBound = upperBound + 50;

		}
	

		System.out.println("---------------------------------------------------------------------------------------");
		System.out.println("EXPERIMENT 2");
		// Select cities in the upper midwest
		newCity.selectCities("latitude", 4000, 5000);
		newCity.selectCities("longitude", 8500, 10000);

		// Print these out
		System.out.println("Cities in the upper mid-west are:");
		newCity.printCities();

		int[] popArray = newCity.getPopulations();
		
		int max = 0;
		for(int i = 0; i < popArray.length; i++)
			if(popArray[i]/20000 > max)
				max = popArray[i]/20000;

		int[] popDist = new int[max+1];
		for(int i = 0; i < popArray.length; i++)
			popDist[popArray[i]/20000]++;

		System.out.println("The population distribution of these cities is:");
		for(int i = 0; i < popDist.length; i++)
			System.out.println("["+(20000*i)+","+(20000*(i+1))+"] "+popDist[i]);
			
		System.out.println("---------------------------------------------------------------------------------------");
		System.out.println("EXPERIMENT 3");

		newCity.selectAllCities();
		String[] states = newCity.getStates();
		
		System.out.println("Here are all the states:");
		for(int i = 0; i < states.length; i++)
			System.out.print(states[i]+" ");
		System.out.println(" ");

		// Scan through the states and select all the cities in that state
		System.out.println("Here are their populations:");
		long maxPopulation = 0;
		String maxPopState = null;
		for(int i = 0; i < states.length; i++)
		{
			newCity.selectAllCities();
			newCity.selectCities("state", states[i], states[i]);
			popArray = newCity.getPopulations();
			long popSum = 0;
			for(int j = 0; j < popArray.length; j++)
				popSum = popSum + popArray[j];

			System.out.println(states[i] + " " + popSum);
			if(popSum > maxPopulation)
			{
				maxPopulation = popSum;
				maxPopState = states[i];
			}
		}
		System.out.println("The most populous state is " + maxPopState + " with a population of " + maxPopulation);

	}
}