// THIS CODE IS MY OWN WORK, IT WAS WRITTEN WITHOUT CONSULTING
// A TUTOR OR CODE WRITTEN BY OTHER STUDENTS - Your Name

// Edit this file.  See Notes.txt for details.  As given, it
// only does steps 1 through 4.

import java.util.Iterator;

public class TSP
{
    // If you use BlueJ, these methods emulate some Makefile tests.
    public static void run10()   { run("tsp10.txt",    4); }
    public static void run100()  { run("tsp100.txt",  10); }
    public static void run1000() { run("tsp1000.txt", 15); }

    // Draw a single edge, in the current color.
    // Note e does not actually have to be an edge in 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, in the current color.
    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: run filename and D from command line arguments.
    public static void main(String[] args) {
        if (args.length != 2) {
            System.err.println("Expected two arguments: FILENAME D");
            System.exit(1);
        }
        run(args[0], Integer.parseInt(args[1]));
    }

    public static void run(String fileName, int D)
    {
        // Step 1: read file, compute G.
        In in = new In(fileName);
        // First line: bounding-box dimensions (width and height)
        int width = in.readInt(), height = in.readInt();
        // read the sequence of points (remainin input lines)
        Bag<Point> bp = new Bag<Point>();
        while (!in.isEmpty()) {
            double x = in.readDouble();
            double y = in.readDouble();
            bp.add(new Point(x, y));
        }
        // copy points into the points[] array, preserving
        // input order so points[0] is first, and so on.
        int V = bp.size();
        Point[] points = new Point[V];
        {
            int v=V;
            for (Point p: bp) points[--v] = p;
        }
        // System.err.println("width "+w+", height "+h+", V "+V);
        // Construct G.  For big files, this may be the slowest step!
        // Note: we limit D to at most V-1 here (maximum degree).
        GeomGraph G = new GeomGraph(points, Math.min(D, V-1));

        // Step 2: draw G, and save as G.png
        // Prepare StdDraw window. Here we leave it at its default
        // pixel size (512 by 512), but rescale axes to fit image.
        int maxwh = Math.max(width, height);
        StdDraw.setXscale(0, maxwh);
        StdDraw.setYscale(0, maxwh);
        StdDraw.show(0);        // start deferred (animation) mode
        draw(G);
        StdDraw.show(0);        // show updated image
        StdDraw.save("G.png");

        // Step 3: compute MST, plot in RED, save "MST.png", print weight.
        MST T = new MST(G);
        double wt = T.weight();
        Iterable<Edge> ET = T.edges(); // edge set of T
        StdDraw.clear();
        StdDraw.setPenColor(StdDraw.RED);
        draw(G, ET);
        StdDraw.show(0);
        StdDraw.save("MST.png");
        StdOut.println(wt);     // first required line of output

        // Step 4: quit if not connected.
        if (T.components() != 1) {
            System.err.println("G is not connected, giving up");
            System.exit(1);
        }

        // TODO: steps 5, 6, 7  (TSP1, TSP2).

        // Step 8: exit, immediately closing the StdDraw window.
        // Note we do not wait for user input here, so the window
        // will not stay visible for long.  We can review the *.png
        // files instead.
        System.exit(0);
    }
}