/* 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];
		
			// 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];
			}
			
			try{
				
			// Construct a buffered reader object and connect it to the files "miles.dat"
			BufferedReader in = new BufferedReader(new FileReader("miles.dat"));

			int cityNumber = 0;
			
			String line, city, stateLat, longPop;			
			
			// 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();
				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
				int cityMile = 0;
				while (cityMile < 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
					while(tokenizedMileage.hasMoreTokens())
						distances[cityNumber][cityMile++] = tokenizedMileage.nextToken();

				} // end of while reading distances

				cityNumber++;
			}
			
			}
			catch (IOException e) {System.out.println("File not found.");}
			
	}
		
	public void selectCities(String attribute, int low, int high)
	{
		//Set any populations to false that are not within the parameters
		if (attribute.compareTo("population") == 0);
		{
			for(int g=0;g<numCities;g++)
			{
				if (currentCities[g] == true && cpSort[g] < low || cpSort[g] > high)
				{
					currentCities[this.index(cpSort[g], cityPop)] = false;
				}
				else if (currentCities[g] == true && cpSort[g] > low && cpSort[g] < high)
				{
					currentCities[this.index(cpSort[g], cityPop)] = true;
				}
			}
		}	
		
		//Set any latitudes to false that are not within the selection
		if (attribute.compareTo("latitude") == 0)
		{ 
			for(int y=0;y<numCities;y++)
			{
				if(currentCities[y] == true && clSort[y] < low || clSort[y] > high)
				{
					currentCities[this.index(clSort[y], cityLat)] = false;
				}
				else if(currentCities[y] == true && clSort[y] > low && clSort[y] < high)
				{
					currentCities[this.index(clSort[y], cityLat)] = true;
				}
			}
		}
		
		//Set any longitudes to false that are not within the selection
		else if (attribute.compareTo("longitude") == 0)
		{
			for(int r= 0; r<numCities; r++)
			{
				if(currentCities[r] == true && cLsort[r] < low || cLsort[r] > high)
				{
					currentCities[this.index(cLsort[r], cityLong)] = false;
				}
				else if(currentCities[r] == true && cLsort[r] > low && cLsort[r] < high)
				{
					currentCities[this.index(cLsort[r], cityLong)] = true;
				}
			}
		}
	}

	public void selectCities(String attribute, String low, String high)
	{
		//Set any names to false that are not within the parameters
		if (attribute.compareTo("name") == 0);
		{
			for(int m=0;m<numCities;m++)
			{
				
				if(currentCities[m] != true && cnSort[m].compareTo(low) < 0 || cnSort[m].compareTo(high) > 0)
				{
					currentCities[this.index(cnSort[m], cityName)] = false;
				}
				else if(currentCities[m] == true && cnSort[m].compareTo(low) > 0 && cnSort[m].compareTo(high) < 0 || cnSort[m].compareTo(high) == 0)
				{
					currentCities[this.index(cnSort[m], cityName)] = true;
					
//					if(cnSort[m+1].compareTo(low) > 0 && cnSort[m+1].compareTo(high) < 0)
//					{
//						currentCities[this.index(cnSort[m], cityName)] = true;
//					}
				
				}
			}
		}
		
		if (attribute.compareTo("state") == 0);
		{
			for(int u=0;u<numCities;u++)
			{
				
				if(csSort[u].compareTo(low) < 0 || csSort[u].compareTo(high) > 0)
				{
					currentCities[this.index(csSort[u], cityState)] = false;
				}
				else if (currentCities[u] == true && csSort[u].compareTo(low) > 0 || csSort[u].compareTo(high) < 0)
				{
					currentCities[this.index(csSort[u], cityState)] = true;
				}
				
			}
		}
	}

	//Select all cities, setting each slot of currentCities "true" by going through the for loop
	public void selectAllCities()
	{
		for (int q = 0; q < numCities; q ++)
		{
				currentCities[q] = true;
		}
	}

	//Select all cities, setting each slot of currentCities "false" by going through the for loop
	public void unselectAllCities()
	{
		for (int q = 0; q < numCities; q ++)
		{
				currentCities[q] = false;
		}
	}

	//Selecting all edges, so all cities are connected by using two for loops, setting all to "true"
	 // "q" = scanning the rows, "w" = scanning the columns
	public void selectAllEdges()
	{
		for (int q = 0; q < numCities; q++)
		{
			for (int w = 0; w < q; w++)
			{
				currentEdges[q][w] = true;
			}
		}
	}

	//Selecting all edges, so all cities are connected by using two for loops, setting all to "false"
	 // "q" = scanning the rows, "w" = scanning the columns
	public void unselectAllEdges()
	{
		for (int q = 0; q < numCities; q++)
		{
			for (int w = 0; w < numCities; w++)
			{
				currentEdges[q][w] = false;
			}
		}
	}
	
	public void printCities(String identifier)
	{
		for(int s= 0; s< numCities;s++)
		{
			if(currentCities[s] == true)
				if(identifier.compareTo("name") == 0)
					System.out.println(cityName[s]);
			
				if(identifier.compareTo("state") == 0)
					System.out.println(cityState[s]);
			
				if(identifier.compareTo("latitude") == 0)
					System.out.println(cityLat[s]);
			
				if(identifier.compareTo("longitude") == 0)
					System.out.println(cityLong[s]);
			
				if(identifier.compareTo("population") == 0)
					System.out.println(cityPop[s]);
		}
	}

	public void printCities()
	{
		for(int s= 0; s< numCities;s++)
		{
			if(currentCities[s] == true)
				System.out.println(cnSort[s]);
		}
	}
	
	public void printEdges()
	{
		int q;
		int counter = 0;
		for(q=0; q<numCities; q++)
			for(int f = 0; f<q;f++)
				if(currentEdges[q][f] == true)
				{
					System.out.print(distances[q][f] + "   ,   ");
					if(f == q-1)
					{
						System.out.println();
					}
				}
	}

	//Sort method to sort cities
	public void Sort()
	{		
		//Allot arrays
		cnSort = new String[numCities]; 
		csSort = new String[numCities];
		clSort = new int[numCities];
		cLsort = new int[numCities]; 
		cpSort = new int[numCities];
		
		//for loop to make copies
		for(int n=0; n<numCities;n++)
		{
			cnSort[n] = cityName[n];
			csSort[n] = cityState[n];
			clSort[n] = cityLat[n];
			cLsort[n] = cityLong[n];
			cpSort[n] = cityPop[n];		
		}
		
		//Sort all arrays
		Arrays.asList(cnSort); Arrays.asList(csSort);
		Arrays.sort(cnSort); Arrays.sort(csSort); 
		Arrays.sort(clSort); Arrays.sort(cLsort); Arrays.sort(cpSort);
		
		//Creating a 2D array to put the indices of the original array into the 2D array for references? Necessary?
		sortCity = new int[numCities][5];
		{
			for(int h = 0; h< numCities; h++)
			{

				sortCity[h][0] = this.index(cnSort[h], cityName);
				sortCity[h][1] = this.index(csSort[h], cityState);
				sortCity[h][2] = this.index(clSort[h], cityLat);
				sortCity[h][3] = this.index(cLsort[h], cityLong);
				sortCity[h][4] = this.index(cpSort[h], cityPop);
			}
		}
	}
	
	//Find index of string in the string arrays
	protected int index(String string, String[] stArray)
	{	
		int x;
		
		for (x=0; x< numCities; x++)
			if(string.compareTo(stArray[x]) == 0)
			{
				return x;
			}
		return -1;
	}

	//Find index of int in integer array
	protected int index(int integer, int[] intArray)
	{
		int x;
        for (x=0; x< numCities; x++)
        	{
        	if(integer == intArray[x])
        	   {
                return x;
        	   }   
        	}
		
        return -1;
	}

	public MollyListGraph makeGraph()
	{
		int arraySize = 0;
		for(int g=0; g<numCities;g++)
		{
			if(currentCities[g] == true)
			{
			arraySize++;
			}
		}
	
		MollyListGraph graph = new MollyListGraph(arraySize);
		for(int a= 0; a < numCities; a++)
		{
			if(currentCities[a] == true)
			{
				String s = cityName[a]+" "+cityState[a];
				graph.addVertex(s);			
System.out.println(s);
			}
		}

		for(int u=0; u<numCities;u++)
		{
			for(int l=0; l<u+1;l++)
			{
				if (currentEdges[u][l] == true)
					if(currentCities[u]== true && currentCities[l] == true)
						graph.addEdge(cityName[u]+" "+cityState[u], cityName[l]+" "+cityState[l]);
			}
		}
		
		return graph;
	}
	
	public void selectEdges(int lowerBound, int upperBound)
	{
		int x = lowerBound;
		int y = upperBound;
		
		for(int o=0; o<numCities;o++)
		{
			for(int e=0; e<o;e++)
			{
				if (currentEdges[o][e] && Integer.parseInt(distances[o][e]) >= x  && Integer.parseInt(distances[o][e]) <= y)
					currentEdges[o][e] = true;
				else
					currentEdges[o][e] = false;
			}
		}
		
	}
	

	
	//Main method
	public static void main(String[] args) {
		City newCity = new City();
		newCity.selectAllCities();
		newCity.selectAllEdges();
		
		MollyListGraph graph1= newCity.makeGraph();

System.out.println(graph1.numberOfVertices() + " " + graph1.numberOfEdges());

		String[] path = graph1.shortestPath("Yakima WA", "Wilmington DE");

	}
}