import java.io.*;
import java.util.*;

public class KateCity {

    	//data members
		static int TotalCities = 128;
        String[] city = new String[TotalCities];
        String[] state = new String[TotalCities];
        int[] latitude = new int[TotalCities];
        int[] longitude = new int[TotalCities];
        int[] population = new int[TotalCities];
        int[][] distance = new int[TotalCities][];
        boolean[] selectedCities = new boolean[TotalCities];
        boolean[][] selectedEdges = new boolean[TotalCities][];
        
        //the temp Arrays are used to be print cities, these arrays are actually
        //sorted instead of the original arrays so that we don't loose association between
        //the original arrays
		String[] tempCity = new String[TotalCities];
		String[] tempState = new String[TotalCities];
  		int[] tempLat = new int[TotalCities];
  		int[] tempLong = new int[TotalCities];
  		int[] tempPop = new int[TotalCities];
  		
  		//the tempIndex arrays are to keep track of where cities/states/whatever is
  		//in the original arrays as opposed to the tempArrays which are sorted and include
  		//only selected Cities
  		int[] tempCityIndex = new int[TotalCities];
  		int[] tempStateIndex = new int[TotalCities];
  		int[] tempLatIndex = new int[TotalCities];
  		int[] tempLongIndex = new int[TotalCities];
  		int[] tempPopIndex = new int[TotalCities];
	
	//Default Constructor
    public KateCity() {
		try
		{
    		//Create the buffered reader for reading the file
    		BufferedReader inFile = new BufferedReader(new FileReader("miles.dat"));

    		//Dummy variables to get past the first three rows of information on the dat file
    		String dum1, dum2, dum3, dum4;
    		dum1 = inFile.readLine();
    		dum2 = inFile.readLine();
    		dum3 = inFile.readLine();
    		dum4 = inFile.readLine();
    		
    		int distToRead = 0;
    		int cityLine = 0;
    		String line, miles;
    		
    		//For loop allocates size for selectedEdges Array
    		//sets all edges to true
            for(int i = 0; i < selectedEdges.length; i++)
    		{
    			selectedEdges[i] = new boolean[i+1];			
    			for(int j = 0; j < i; j++)
    				selectedEdges[i][j] = true;
    		}
            
            //For loop allocates size for distance array
            for(int i = 0; i < distance.length; i++)
    		{
    			distance[i] = new int[i+1];			
    			for(int j = 0; j < i; j++)
    				distance[i][j] = 0;
    		}
    		
            //Goes through miles.dat and sticks info into arrays
    		while(cityLine < TotalCities)
    		{
    				line = inFile.readLine();
    				java.util.StringTokenizer st = new java.util.StringTokenizer(line, ",[,]");
    				
    				String cityName, stateName, latitudeName, longitudeName, populationName;
    				
    				//Reads in all data in the City line
    				cityName = st.nextToken();
    				stateName = st.nextToken().trim();
    				latitudeName = st.nextToken();
    				longitudeName = st.nextToken();
    				populationName = st.nextToken();
    				
    				//Stores that data into arrays
    				city[cityLine] = cityName;
    				state[cityLine] = stateName;
    				latitude[cityLine] = Integer.parseInt(latitudeName);
    				longitude[cityLine] = Integer.parseInt(longitudeName);
    				population[cityLine] = Integer.parseInt(populationName);
    				
    				//System.out.println(city[cityLine] + ", " + state[cityLine] + " [" + latitude[cityLine] +
    				//		", " + longitude[cityLine] + "] " + population[cityLine]);
    				
    				//Read the next line, as long as there are more distances to be read
    				while(distToRead < cityLine){
     					
    					miles = inFile.readLine();
    					java.util.StringTokenizer string = new java.util.StringTokenizer(miles, " ");
    	
    					while(string.hasMoreTokens())
    					{
    						distance[cityLine][distToRead] = Integer.parseInt(string.nextToken());
    						//System.out.println(distance[cityLine][distToRead]);
						
    						distToRead++;
    					}
    				}

				// Reset distToRead counter
				distToRead = 0;
				cityLine++;
    		}
    		
    			//Initialize the selectedCities Array to true
    			for(int i = 0; i < TotalCities; i++){
    				selectedCities[i] = true;
    			}
    			
		}
		catch(IOException e){}
		catch (java.util.NoSuchElementException e) {}
    }
   
    //Method to find out which city is the most populated
	public String mostPopulated(){
		String largestState = "";
		
		int greatest = 0;
			
		for(int i  = 0; i < 128; i++){
			if(population[i] > greatest){
				greatest = population[i];
				largestState = state[i];
			}
		}
		return largestState;
	}
    
    //sets all indexes in selectedCities Array to true
    public void selectAllCities(){
    	for(int i = 0; i < TotalCities; i++)
    	{
    		selectedCities[i] = true;
    		//System.out.println(city[i]);
    	}
    }
    
    //sets all indexes in selectedCities Array to false
    public void unselectAllCities(){
    	for(int i = 0; i < TotalCities; i++)
    	{
    		selectedCities[i] = false;
    	}
    }
    
    //sets all indexes in selectedEdges array to true
    public void selectAllEdges(){
    	for(int i = 0; i < TotalCities; i++){
    		for(int j = 0; j < i + 1; j++){
    			selectedEdges[i][j] = true;
    		}
    	}
    }
    
    //sets all indexes in selectedEdges array to false
    public void unselectAllEdges(){
    	for(int i = 0; i < TotalCities; i++){
    		for(int j = 0; j < i + 1; j++){
    			selectedEdges[i][j] = false;
    		}
    	}
    }
    
    //Sets edges in selectedEdges array  that fall between two integers to true and all others to false
    public void selectEdges(int lowerbound, int upperbound){
    	for(int i =0; i < TotalCities; i++){
    		for(int j = 0; j < i +1; j++){
    	    	if(distance[i][j] >= lowerbound && distance[i][j] <= upperbound){
    	    		selectedEdges[i][j] = true;
// Sriram: added
if(city[i].equals("Yakima"))
	System.out.println("Yakima: Inside Select Edges:" + city[j]);

if(city[i].equals("Springfield"))
	System.out.println("Springfield: Inside Select Edges:" + city[j]);
    	    	}
    	    	else
    	    		selectedEdges[i][j] = false;
    		}
    	}
    }
    
    //Sets indexes in selectedCities array to true if city/state name falls in range of strings
    public void selectCities(String x, String y, String z){
    	if(x == "city"){
        	for(int i =0; i < TotalCities; i++){
        		if(selectedCities[i] == true){
        			
        	    	if(city[i].compareTo(y) >= 0 && city[i].compareTo(z) <= 0){
        	    		selectedCities[i] = true;
        	    	}
        	    	else
        	    	{	selectedCities[i] = false;
        	    	}
        		}
        	}
    	}
    	
    	else if(x == "state"){
        	for(int i =0; i < TotalCities; i++){
        		if(selectedCities[i] == true){
        	    	if(state[i].compareTo(y) >= 0 && state[i].compareTo(z) <= 0){
        	    		selectedCities[i] = true;
        	    	}
        	    	else
        	    		selectedCities[i] = false;
        		}
        	}
    	}
    }
    
    //Sets indexes in selectedCities array to true if latitude/longitude/population falls in range of integers
    public void selectCities(String x, int y, int z){
    	if(x == "latitude"){
        	for(int i =0; i < TotalCities; i++){
        		if(selectedCities[i] == true){
        	    	if(latitude[i] >= y && latitude[i] <= z){
        	    		selectedCities[i] = true;
        	    	}
        	    	else
        	    		selectedCities[i] = false;
        		}
        	}
    	}
    	
    	else if(x == "longitude"){
        	for(int i = 0; i < TotalCities; i++){
        		if(selectedCities[i] == true){
        	    	if(longitude[i] >= y && longitude[i] <= z){
        	    		selectedCities[i] = true;
        	    	}
        	    	else
        	    		selectedCities[i] = false;
        		}
        	}
    	}
    	
    	else if(x == "population"){
        	for(int i = 0; i < TotalCities; i++){
        		if(selectedCities[i] == true){
        	    	if(population[i] >= y && population[i] <= z){
        	    		selectedCities[i] = true;
        	    	}
        	    	else
        	    		selectedCities[i] = false;
        		}
        	}
    	}
    }
    
    //Prints selected cities -- takes in no data
    public void printCities(){
    	selectionSort("city");
    	for(int i = 0; i < numTrue("city"); i++){
    		System.out.println(city[tempCityIndex[i]]);
    	}
    }
    
    //Prints selected cities - prints sorted array of city/state/latitude/longitude/population
    public void printCities(String x){
    	if(x == "city")
    	{
        	selectionSort("city");
        	for(int i = 0; i < numTrue("city"); i++){
        		System.out.println(city[tempCityIndex[i]]);
        	}
    	}
    	
    	else if(x == "state")
    	{
        	selectionSort("state");
        	for(int i = 0; i < numTrue("city"); i++){
        		System.out.println(state[tempStateIndex[i]]);
        	}
    	}
    	
    	else if(x == "latitude")
    	{
        	selectionSort("latitude");
        	for(int i = 0; i < numTrue("city"); i++){
        		System.out.println(latitude[tempLatIndex[i]]);
        	}
    	}

    	else if(x == "longitude")
    	{
        	selectionSort("longitude");
        	for(int i = 0; i < numTrue("city"); i++){
        		System.out.println(longitude[tempLongIndex[i]]);
        	}
    	}
    	
    	else if(x == "population")
    	{
        	selectionSort("population");
        	for(int i = 0; i < numTrue("city"); i++){
        		System.out.println(population[tempPopIndex[i]]);
        	}
    	}
    }
    
    //Prints all selected Edges if the cities on both ends of the edge are also selected
    public void printEdges(){
    	for(int i = 0; i < TotalCities - 1; i++){
    		for(int j = 0; j < i +1; j++){
    			
    			if(selectedEdges[i][j] == true){
    				if(selectedCities[i] == true && selectedCities[(i - j) -1] == true){
    					System.out.println(city[i] + " " + city[(i-j) - 1]);
    					
    				}
    			}
    		}
    	}

    }
    
    //swap method for selectionSort method -- takes in int array
	public static void swap(int[] data, int x, int y)
	{
		int temp = data[x];
		data[x] = data[y];
		data[y] = temp;
	}
	
	//swap method for selectionSort method -- takes in string array
	public static void swap(String[] data, int x, int y)
	{
		String temp = data[x];
		data[x] = data[y];
		data[y] = temp;
	}
	
    //Finds the number of selectedCities -- used to size my temp arrays
	public int numTrue(String type){
		int numTrue = 0;
		
		if(type == "city"){
			for(int p = 0; p < TotalCities; p++){
				if(selectedCities[p] == true)
				{
					numTrue++;
				}
			}
		}
		return numTrue;
	}
	
	//Sort method
	public void selectionSort(String x)
	{
		int i, j, min;
		int count = 0;
  		
		if(x == "city"){
			
			//initialize tempIndex
			for(int l = 0; l < numTrue("city"); l++){
				tempCityIndex[l] = l;
			}
			
			//Copy selected Cities into tempCity Array to be sorted
			String[] tempCity = new String[numTrue("city")];
  			for(int k = 0; k < TotalCities; k++){
  				if(selectedCities[k] == true){
  	  				tempCity[count] = city[k];
  	  				tempCityIndex[count] = k;
  	  				count++;
  				}
  			}
  			
  			//Sort the tempCity array
  	  		for (i = 0; i < numTrue("city"); i++)
  	  		{
  				// Select the minimum element from the remaining
  				// and swap into position i
  	    			min = i;

  	    			for (j = i+1; j < numTrue("city"); j++)
  	    				if(tempCity[j] != null){
  	    					if (tempCity[j].compareTo(tempCity[min])  < 0){
  	  	          				min = j;
  	    					}			
  	    				}
  	    			
  	    			//Whenever a swap is made to sort the tempCity array, a swap must be made 
  	    			//to keep track of where the original city is in the City array
  	    			swap(tempCity, i, min);
  	    			//System.out.println(tempCity[i]);
  	    			swap(tempCityIndex, i, min);
  	    			//System.out.println(tempCityIndex[i]);
  	  		}
  		}
  		
		if(x == "state"){
			
			//initialize tempIndex
			for(int l = 0; l < numTrue("city"); l++){
				tempStateIndex[l] = l;
			}
			
			String[] tempState = new String[numTrue("city")];
  			for(int k = 0; k < TotalCities; k++){
  				if(selectedCities[k] == true){
  	  				tempState[count] = state[k];
  	  				tempStateIndex[count] = k;
  	  				count++;
  				}
  			}
  			
  	  		for (i = 0; i < numTrue("city"); i++)
  	  		{
  				// Select the minimum element from the remaining
  				// and swap into position i
  	    			min = i;

  	    			for (j = i+1; j < numTrue("city"); j++)
  	    				if(tempState[j] != null){
  	    					if (tempState[j].compareTo(tempState[min])  < 0){
  	  	          				min = j;
  	    					}			
  	    				}
  	    			swap(tempState, i, min);
  	    			swap(tempStateIndex, i, min);
  	  		}
  		}
		
		if(x == "latitude"){
			
			//initialize tempIndex
			for(int l = 0; l < numTrue("city"); l++){
				tempLatIndex[l] = l;
			}
			
			int[] tempLat = new int[numTrue("city")];
  			for(int k = 0; k < TotalCities; k++){
  				if(selectedCities[k] == true){
  	  				tempLat[count] = latitude[k];
  	  				tempLatIndex[count] = k;
  	  				count++;
  				}
  			}
  			
  	  		for (i = 0; i < numTrue("city"); i++)
  	  		{
  				// Select the minimum element from the remaining
  				// and swap into position i
  	    			min = i;

  	    			for (j = i+1; j < numTrue("city"); j++)
  	    					if (tempLat[j] < tempLat[min]){
  	  	          				min = j;
  	    				}
  	    			swap(tempLat, i, min);
  	    			swap(tempLatIndex, i, min);
  	  		}
  		}
  		
		if(x == "longitude"){
			
			//initialize tempIndex
			for(int l = 0; l < numTrue("city"); l++){
				tempLongIndex[l] = l;
			}
			
			int[] tempLong = new int[numTrue("city")];
  			for(int k = 0; k < TotalCities; k++){
  				if(selectedCities[k] == true){
  	  				tempLong[count] = longitude[k];
  	  				tempLongIndex[count] = k;
  	  				count++;
  				}
  			}
  			
  	  		for (i = 0; i < numTrue("city"); i++)
  	  		{
  				// Select the minimum element from the remaining
  				// and swap into position i
  	    			min = i;

  	    			for (j = i+1; j < numTrue("city"); j++)
  	    					if (tempLong[j] < tempLong[min]){
  	  	          				min = j;
  	    				}
  	    			swap(tempLong, i, min);
  	    			swap(tempLongIndex, i, min);
  	  		}
  		}
  		
		if(x == "population"){
			
			//initialize tempIndex
			for(int l = 0; l < numTrue("city"); l++){
				tempPopIndex[l] = l;
			}
			
			int[] tempLong = new int[numTrue("city")];
  			for(int k = 0; k < TotalCities; k++){
  				if(selectedCities[k] == true){
  	  				tempPop[count] = population[k];
  	  				tempPopIndex[count] = k;
  	  				count++;
  				}
  			}
  			
  	  		for (i = 0; i < numTrue("city"); i++)
  	  		{
  				// Select the minimum element from the remaining
  				// and swap into position i
  	    			min = i;

  	    			for (j = i+1; j < numTrue("city"); j++)
  	    					if (tempPop[j] < tempPop[min]){
  	  	          				min = j;
  	    				}
  	    			swap(tempPop, i, min);
  	    			swap(tempPopIndex, i, min);
  	  		}
  		}
  		
	}
	
	//Creates graph from selectedCities and selecteEdges
	public KateListGraph makeGraph(){
		
		int count = numTrue("City");
		
		KateListGraph a = new KateListGraph(count);
		
		for(int j = 0; j < TotalCities; j++){
			if(selectedCities[j] == true){
				
			a.addVertex(city[j] + " " + state[j]);
			}
		}
		
		for(int k = 0; k < TotalCities; k++){
			for(int l = 0; l < k +1; l++){
				if(selectedEdges[k][l] == true){
					if(selectedCities[k] == true && selectedCities[l] == true)
					a.addEdge(city[k] + " " + state[k], city[l] + " " + state[l]);
				}
			}
		}
		return a;
	}
    
    public static void main(String args[]){
    	KateCity test = new KateCity();
    	
    	test.selectAllCities();
    	//test.printCities();
    	
    	
    	//test.selectCities("city", "Ravenna", "RedBluff");
    	//test.selectCities("state", "VA", "VB");
    	
    	//test.printCities("state");


    	
    	//test.selectCities("latitude", 4110, 9999);
    	//test.selectCities("longitude", 7202, 13000);
    	//test.selectCities("population", 0, 875538);
    	//test.printCities("latitude");
    	
    	//test.makeGraph();
    	
    	//test.printEdges();
    	//test.selectEdges(966,966);
    	//test.printEdges();
    	
    }
    
}