import java.io.File;
import java.io.IOException;
import java.util.Comparator;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Scanner;
import javax.swing.JTextArea;
import javax.swing.JScrollPane;
import javax.swing.JOptionPane;

public class SpanningTree {
    HashMap<String,Integer> cityMap;
    ArrayList<String> cities;
    
    class Edge {
        int vertex1;
        int vertex2;
        double distance;
        
        public Edge(int vertex1,int vertex2,double distance) {
            this.vertex1 = vertex1;
            this.vertex2 = vertex2;
            this.distance = distance;
        } // end constructor
        
        public String toString() {
            return cities.get(vertex1) + " to " +
                    cities.get(vertex2) + " is " +
                    distance + " miles.\n";
        } // end toString
        
    } // end Edge
    
    class CompareWeights implements Comparator<Edge> {
        public int compare(Edge x, Edge y) {
            return (int)(x.distance - y.distance);
        } // end compare
    } // end CompareWeights
    
    void insertCity(String city) {
        if( !cityMap.containsKey(city) ) {
            cityMap.put(city,cities.size());
            cities.add(city);
        } // end if
    } // end insertCity
    
    public SpanningTree() throws IOException {
        Scanner in = new Scanner(new File("cities.data"));
        in.useDelimiter("[:\n]+");
        cityMap = new HashMap<String,Integer>();
        cities = new ArrayList<String>();
        ArrayList<Edge> edgeList = new ArrayList<Edge>();
        while( in.hasNext() ) {
            String city1 = in.next();
            insertCity(city1);
            String city2 = in.next();
            insertCity(city2);
            double distance = in.nextDouble();
            edgeList.add(new Edge(cityMap.get(city1),cityMap.get(city2),distance));
        } // end while
        BinaryHeap<Edge> edges = new BinaryHeap<Edge>(edgeList,new CompareWeights());
        String out = "The list of cities is:\n";
        for( String city : cities ) out += city + "\n";
        out += "\n\n";
        DisjointSets vertexSets = new DisjointSets(cities.size());
        ArrayList<Edge> treeEdges = new ArrayList<Edge>(cities.size());
        // Kruskal's Algorithm
        while( treeEdges.size() < cities.size()-1 ) {
            Edge minEdge = edges.removeMin();
            int vertex1Set = vertexSets.get(minEdge.vertex1);
            int vertex2Set = vertexSets.get(minEdge.vertex2);
            if( vertex1Set != vertex2Set ) {
                vertexSets.union(vertex1Set,vertex2Set);
                treeEdges.add(minEdge);
            } // end if
        } // end while
        out += "A spanning tree for the cities is:\n";
        for( Edge edge : treeEdges)  out += edge;
        JTextArea outArea = new JTextArea(out,30,40);
        JOptionPane.showMessageDialog(null,new JScrollPane(outArea));
    } // end constructor
    
    public static void main(String[] args) throws IOException {
        new SpanningTree();
        System.exit(0);
    } // end main
    
}