// GeomGraphQuad is just like GeomGraph, except that it uses a
// QuadTree to more quickly iterate over closest points.

import java.util.Iterator;

public class GeomGraphQuad extends GeomGraph
{
    // A QuadTree, mapping points to vertex ids (index in points[]).
    private QuadTree qt;

    // Construct with points and quadtree, but no edges yet.
    public GeomGraphQuad(Point[] points) {
        super(points);             // a vertex per point
        qt = new QuadTree(points); // does random insertion order
    }

    // Override this method, all efficiency gains are here:
    public Iterator<Integer> closest(Point p) { return qt.closestValues(p); }

    // Override these two methods, to use GeomGraphQuad in our tests.
    public GeomGraph create(Point[] pts) { return new GeomGraphQuad(pts); }
    public static void main(String[] args) {
        // An empty graph just serves as a factory.
        GeomGraph factory = new GeomGraphQuad(new Point[0]);
        GeomGraph G = factory.create(args, null);
    }
}