/* 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());
							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

	// Select cities: At this time the only possible attributes are "latitude" and "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;
                }


	}

	// 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();

		// Select edges in the range 0 through 200 miles and make a graph
		newCity.selectEdges(0, 200);
		myListGraph g = newCity.makeGraph();

		// Print some basic info. about this graph
		System.out.println("Vertices = " + g.numberOfVertices() + " " + "Edges = " + g.numberOfEdges());

		String[][] connComps = g.connectedComponents();
		System.out.println("No. connected components = " + connComps.length);

		// Print out the connected components
		for(int i = 0; i < connComps.length; i++)
		{
			System.out.println("Connected Component " + (i+1) + " has " + connComps[i].length + " vertices.");
			for(int j = 0; j < connComps[i].length; j++)
				System.out.print(connComps[i][j]+" ");

			System.out.println(" ");
		}

		// Compute shortest path between Yakima, WA and Wilmington, DE
		String[] 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(" ");
		}

		// Select cities in the upper midwest
		newCity.selectCities("latitude", 4000, 5000);
		newCity.selectCities("longitude", 8500, 10000);

		// Print these out
		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]++;

		for(int i = 0; i < popDist.length; i++)
			System.out.println("["+(20000*i)+","+(20000*(i+1))+"] "+popDist[i]);
			
	}
}