// This is a slow GeomGraph like hw4, but rewritten to easily subclass
// in GeomGraphQuad.  This includes command-line testing from 'main'.

// The vertex ids (0 to V-1) index the points[] array, so each vertex
// corresponds to a point in the plane.  Whenever we add an edge, its
// weight is their Euclidean distance.  Note the constructor does not
// add any edges, this is done later by the other methods.  Duplicate
// edges are possible, and edge lists are not sorted.

import java.util.Iterator;

public class GeomGraph extends EdgeWeightedGraph
{
    // Return degree of vertex v, counting duplicate edges.
    // (This method ought to be in EdgeWeigtedGraph.)
    public int degree(int v) { return ((Bag<Edge>)adj(v)).size(); }

    // Our array of Point objects, given in the constructor.
    // The vertex ids (0 to V-1) are indices into this array.
    private final Point[] points;

    // We maintain array rad[] (radius), with this invariant:
    // if v!=w and distance(v,w)<rad[v], then we have already added
    // edge {v,w} (it may have been added as (v,w) or as (w,v)).
    // Note v may also have some edges not guaranteed by rad[v].
    // We use rad[] to avoid adding some duplicate edges.
    private final double[] rad;
    private void incRad(int v, double r) { rad[v]=Math.max(rad[v], r); }

    // Construct a GeomGraph with vertices, but no edges yet.
    public GeomGraph(Point[] pts) {
        super(pts.length);      // one vertex per point
        points = pts;
        rad = new double[V()];  // all 0.0
    }

    // Return the point of vertex v.
    public Point point(int v) { return points[v]; }

    // Return the geometric distance between two points (vertex ids).
    // This does not depend on the possible presence of edge (v,w).
    public double distance(int v, int w) {
        return points[v].distanceTo(points[w]);
    }

    // Return bounding box for this GeomGraph.
    Rectangle bbox() {
        Rectangle rec = new Rectangle(points[0]);
        for (Point p: points)
            rec = rec.add(p);
        return rec;
    }

    // Return an iterator for vertex ids, in order of increasing
    // distance from an arbitrary point p.
    public Iterator<Integer> closest(Point p) {
        // O(V lg V) time to create and sort.
        // This could be O(V) time to create using IndexMinPQ,
        // but it would need some rewriting to achieve that.
        /*
        IndexMinPQ pq = new IndexMinPQ<Double>(V());
        for (int w=0; w<V; ++w) pq.insert(w, p.distanceTo(point(w)));
        return pq.iterator();
        */
        int V = V();
        double[] dist = new double[V];
        for (int w=0; w<V; ++w) dist[w] = p.distanceTo(point(w));
        return new IndirectSort(dist).iterator();
    }
    // Return an iterator for vertex ids, in order of increasing
    // distance from the point of vertex v.
    public Iterator<Integer> closest(int v) { return closest(point(v)); }

    // Connect v to the D closest points.
    public void addEdges(int v, int D) { addEdges(v, D, closest(v)); }
    private void addEdges(int v, int D, Iterator<Integer> closest) {
        int vEdges = 0;
        while (closest.hasNext() && vEdges < D) {
            int w = closest.next();
            if (w==v) continue; // skip self-loop
            ++vEdges;
            double dist = distance(v, w);
            if (dist >= rad[w]) // not already added at w?
                addEdge(new Edge(v, w, dist));
        }
        // Set rad[v] to the next distance, if any.
        if (closest.hasNext())
            incRad(v, distance(v, closest.next()));
        else
            incRad(v, Double.POSITIVE_INFINITY);
    }

    // Connect v to all points at distance less than delta.
    public void addEdges(int v, double delta) { addEdges(v,delta,closest(v)); }
    private void addEdges(int v, double delta, Iterator<Integer> closest) {
        while (closest.hasNext()) {
            int w = closest.next();
            if (w==v) continue; // skip self-loop
            double dist = distance(v, w);
            if (dist >= delta) { // done
                incRad(v, dist);
                return;
            }
            if (dist >= rad[w]) // not already added at w?
                addEdge(new Edge(v, w, dist));
        }
        incRad(v, Double.POSITIVE_INFINITY);
    }

    // Connect each point to its D closest neighbors.
    public void addEdges(int D) {
        int V = V();
        for (int v=0; v<V; ++v) addEdges(v, D);
    }

    // Connect all pairs of points at distance less than delta.
    public void addEdges(double delta) {
        int V = V();
        for (int v=0; v<V; ++v) addEdges(v, delta);
    }

    // Create a new GeomGraph with same type as this, no edges.
    // This is a factory method, subclasses should override it.
    public GeomGraph create(Point[] pts) { return new GeomGraph(pts); }

    // Create a new GeomGraph with create(pts), initializing pts
    // and edges as specified by the command line arguments, args.
    // Various diagnostic output messages are printed to out.
    //
    // The first argument should be a filename (like "tsp10.txt"), and
    // the second should be numeric (like "20" or "50.0").  If it
    // includes ".", then it is parsed as a double delta, and we add
    // edges with addEdges(delta).  Otherwise it is parsed as an int
    // D, and we add edges with addEdges(D).   Either way, we print
    // some summary information and timing to StdOut.
    //
    // Examples:
    //   tsp1000.txt 50.0
    //   circuit1290.txt 20
    //
    // Remark: this is also a factory method, but it may suffice for
    // subclasses to just override create(pts), which is used here.
    public GeomGraph create(String[] args, Out out)
    {
        Stopwatch all = new Stopwatch();
        if (out==null) out = new Out(); // same as StdOut
        out.printf("Reading %s ... ", args[0]);
        Stopwatch sw = new Stopwatch();
        In in = new In(args[0]);
        int width = in.readInt(), height = in.readInt(); // forget
        Point[] pts = readPoints(in); // read all the point data
        in.close();
        out.printf("%d points in %.3f secs%n", pts.length, sw.elapsedTime());
        out.printf("Creating G (no edges yet) ... ");
        sw = new Stopwatch();
        GeomGraph G = create(pts);
        out.printf("done in %.3f secs%n", sw.elapsedTime());
        if (args[1].indexOf(".") >= 0) {
            double delta = Double.parseDouble(args[1]);
            out.printf("Calling addEdges(delta=%f) ... ", delta);
            sw = new Stopwatch();
            G.addEdges(delta);
        } else {
            int D = Integer.parseInt(args[1]);
            out.printf("Calling addEdges(D=%d) ... ", D);
            sw = new Stopwatch();
            G.addEdges(D);
        }
        out.printf("%d edges in %.3f secs%n", G.E(), sw.elapsedTime());
        out.printf("%.3f seconds overall%n%n", all.elapsedTime());
        return G;
    }

    // Return array of Point objects read from some input.
    // We assume the first line (width and height) is already read.
    static Point[] readPoints(In in)
    {
        // First line? Assume this is already read.
        // int width = in.readInt(), height = in.readInt();
        // Read the remaining sequence of points.
        Bag<Point> bp = new Bag<Point>();
        while (!in.isEmpty()) {
            double x = in.readDouble();
            double y = in.readDouble();
            bp.add(new Point(x, y));
        }
        // Now copy the points into the points[] array, preserving
        // their input order: points[0] is the first input point,
        // points[1] is the second, and so on.
        int v = bp.size();
        Point[] points = new Point[v];
        for (Point p: bp) points[--v] = p;
        return points;
    }

    public static void main(String[] args) {
        // An empty graph just serves as a factory.
        GeomGraph factory = new GeomGraph(new Point[0]);
        GeomGraph G = factory.create(args, null);
    }
}