// Test client for GeomGraph.
// Reads a list of points from StdIn, and doubles delta until
// the GeomGraph is connected, and then finds MST.
// Also, draws result of each step using StdDraw.

public class Driver
{
    // Return count of connected components in G.
    static int components(EdgeWeightedGraph G) {
        int V = G.V();
        UF uf = new UF(V);
        for (int v=0; v<V; ++v)
            for (Edge e: G.adj(v))
                uf.union(v, e.other(v));
        return uf.count();
    }

    // Draw a single edge from G.
    static void draw(GeomGraph G, Edge e) {
        int v = e.either(), w = e.other(v);
        Point p = G.point(v), q = G.point(w);
        p.drawTo(q);
    }

    // Draw a list of edges from G.
    static void draw(GeomGraph G, Iterable<Edge> edges) {
        for (Edge e: edges) draw(G, e);
    }

    // Draw all vertices and edges of G.
    static void draw(GeomGraph G) {
        int V = G.V();
        for (int u=0; u<V; ++u) {
            Point p = G.point(u);
            p.draw();
            draw(G, G.adj(u));
        }
    }

    // Test client: read list of points from StdIn, and then try
    // constructing a GeomGraph G with increasing values of delta,
    // until G is connected.  Finally compute the MST.
    public static void main(String[] args)
    {
        // First read bounding-box dimensions (width and height)
        int w = StdIn.readInt();
        int h = StdIn.readInt();
        int maxwh = Math.max(w, h);
        // read the sequence of points
        Bag<Point> in = new Bag<Point>();
        while (!StdIn.isEmpty()) {
            double x = StdIn.readDouble();
            double y = StdIn.readDouble();
            in.add(new Point(x, y));
        }
        // copy all points to points[] array.
        int V = in.size(), v=V;
        Point[] points = new Point[V];
        for (Point p: in) points[--v] = p; // preserve input order

        StdOut.println("width is "+w+", height is "+h+", V is "+V);

        // Prepare StdDraw window for drawing.
        // We leave it at its default size, 512 by 512.
        StdDraw.setXscale(0, maxwh);
        StdDraw.setYscale(0, maxwh);
        StdDraw.show(0);        // deferred (animation) mode

        // Initial delta makes O(V) squares, a good initial
        // guess for a "random cloud" kind of point set.
        double delta = maxwh/(2*Math.sqrt(V));
        GeomGraph G = null;
        while (true) {
            StdOut.print("Trying delta=" + delta + " ... ");
            G = new GeomGraph(points, delta);
            int E = G.E(), p = G.pairs(), cc = components(G);
            StdOut.println(p+" pairs, "+E+" edges, "+cc+" components");
            StdOut.print("Drawing G ... ");
            draw(G);
            StdDraw.show(0);
            StdOut.println("done");
            if (cc == 1) break;
            // More than one component, try again with larger delta.
            delta = 2*delta;
        }
        StdOut.print("Computing MST ... ");
        KruskalMST T = new KruskalMST(G);
        StdOut.println("weight " + T.weight());
        // Draw the MST in red
        StdOut.print("Drawing T ... ");
        StdDraw.setPenColor(StdDraw.RED);
        draw(G, T.edges());
        StdDraw.show(0);
        StdOut.println("done");
    }
}