//Greg Wessels
//Homework 9
//A03

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.StringTokenizer;


public class MST {

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

			// 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
	int[] mst(int s)
	{
		int totalDistance = 0;
		boolean[] beenThere = new boolean[numCities];
		for(int i = 0; i<numCities; i++)
		{
			beenThere[i] = false;
		}
		beenThere[s] = true;
		int temporary = 0;
		int smallestWeight = 0; 

		// Make an int[] representing the tree
		int[] tree = new int[numCities];
		for(int i = 0; i < numCities; i++)
			tree[i] = -1;

		tree[s] = s;

		for(int k = 1; k <= numVertices-1; k++)
		{
			smallestWeight = 9000;
			bestVertex = -1;
			parentOfBestVertex = -1;		
		
			// index i scans tree vertices
			for(int i = 0; i<numCities; i++)
				{
					 smallestWeight = 9000;
					
					// Checking if i is a tree vertex or not
					if(beenThere[i] == true)
						{
							// index i scans non-tree vertices
							for(int j = 0; j < numCities ; j++)
								{
								if( beenThere[j] == false)
								{
									if (distances[i][j] < smallestWeight )
										{
										smallestWeight = distances[i][j];
										bestVertex = j;
										parentOfBestVertex = i;			
											//System.out.println(smallestWeight + "   *   ");
											//temporary = j;
												
										}
								}
							} // end of for-j
							//totalDistance = totalDistance + smallestWeight;
							//beenThere[temporary] = true;
						}
				} // end for-i

			// Found the best non-tree vertex to add to the set of tree vertices
			beenThere[bestVertex] = true;
			tree[bestVertex] = parentOfBestVertex;
		}
		return tree;
	}

public static void main(String[] args) {
	
	MST m = new MST();
	m.mst(0);
	System.out.println("The total weight is "+m.mst(0));
	
	
}
}