// Do not edit, except possibly for extra credit.

// Extra Credit TODO: make the GeomGraph(points,D) constructor faster!
// Possibly adapt "grid of squares" idea from share/0321/geom/.
// If you do this, let me know, otherwise I won't notice it.

// Given an array points[] of Point objects, we have two GeomGraph
// constructors.  In either case, the weight of an edge is always the
// Euclidean distance between its endpoints.  The constructors may
// construct duplicate edges in the adjacency lists (e.g. some edge
// may be added from both ends).
//
//  1. new GeomGraph(points, D), where D is an int:
//     Add edges from each vertex to its D closest neighbors.
//
//  2. new GeomGraph(points, delta), where delta is double:
//     Add edges from each vertex to neighbors at distance < delta.

public class GeomGraph extends EdgeWeightedGraph
{
    // Our array of Point objects, given in the constructor.
    final private Point[] points;

    // Add edges from v to its D closest neighbors, O(V) time.
    private void addEdges(int v, int D)
    {
        Point p = points[v];
        int V = points.length;
        // Compute all edges from v.
        Edge[] all = new Edge[V];
        for (int w=0; w<V; ++w)
            all[w] = new Edge(v, w, p.distanceTo(points[w]));
        // Sort them by weight.
        java.util.Arrays.sort(all);
        // Add first D edges, skipping self-loop all[0].
        for (int i=1; i<=D; ++i)
            addEdge(all[i]);
    }

    // Add edges from v to neighbors w with w>v, and
    // distance less than delta, in O(V) time.
    private void addEdges(int v, double delta)
    {
        Point p = points[v];
        int V = points.length;
        // Compute all edges from v.
        // We skip w<v, since such an edge is found from w.
        for (int w=v+1; w<V; ++w) {
            double dist = p.distanceTo(points[w]);
            if (dist < delta)
                addEdge(new Edge(v, w, dist));
        }
    }

    // Return corresponding Point from the points[] array.
    public Point point(int v) { return points[v]; }

    // Return degree of vertex v (length of adjacency list)
    public int degree(int v) { return ((Bag<Edge>)adj(v)).size(); }

    // Two constructors.

    // Connect each v to its D closest neighbors.  O(V^2) time.
    public GeomGraph(Point[] points, int D)
    {
        super(points.length);
        this.points = points;
        int V = V();
        for (int v=0; v<V; ++v)
            addEdges(v, D);
    }

    // Connect each v to neighbors at distance < delta.  O(V^2) time.
    public GeomGraph(Point[] points, double delta)
    {
        super(points.length);
        this.points = points;
        int V = V();
        for (int v=0; v<V; ++v)
            addEdges(v, delta);
    }
}