001package algs32.kdtree;
002import algs12.Point2D;
003import algs13.Queue;
004import stdlib.*;
005
006/* a set of points implemented as kd-tree */
007public class KdTree {
008
009  private static class Node {
010    // TODO
011  }
012  private Node root;
013
014  /* construct an empty set of points */
015  public KdTree() {
016    // TODO -- maybe nothing to do here... in which case you can remove this and use the default constructor
017  }
018
019  /* is the set empty? */
020  public boolean isEmpty() {
021    // TODO
022    return false;
023  }
024
025  /* add the point p to the set (if it is not already in the set) */
026  public void insert(Point2D p) {
027    // TODO
028  }
029
030  /* does the set contain the point p? */
031  public boolean contains(Point2D target) {
032    // TODO
033    return false;
034  }
035
036  /* all points in the set that are inside the target rectangle */
037  public Iterable<Point2D> range(RectHV target) {
038    // TODO
039    return new Queue<>();
040  }
041
042  /* a nearest neighbor to target point; null if empty */
043  public Point2D nearest(Point2D target) {
044    // TODO
045    return new Point2D (0, 0);
046  }
047
048  /* draw all of the points to standard draw */
049  /* for x-node, use red line to draw the division between left/right */
050  /* for y-node, use blue line to draw the division between top/bottom */
051  /* see the writeup for examples */
052  public void draw() {
053    // TODO
054  }
055  
056
057
058  /* some test code */
059  public void toGraphviz() { GraphvizBuilder.nodesToFile (root); }
060  private static void insert5Points (KdTree kdtree, double xoffset, double yoffset) {
061    kdtree.insert (new Point2D (0.7 + xoffset, 0.2 + yoffset));
062    kdtree.insert (new Point2D (0.5 + xoffset, 0.4 + yoffset));
063    kdtree.insert (new Point2D (0.2 + xoffset, 0.3 + yoffset));
064    kdtree.insert (new Point2D (0.4 + xoffset, 0.7 + yoffset));
065    kdtree.insert (new Point2D (0.9 + xoffset, 0.6 + yoffset));
066  }
067  public static void main (String[] args) {
068    KdTree kdtree = new KdTree ();
069    insert5Points (kdtree, 0.0, 0.0); // after this there should be 5 points
070    insert5Points (kdtree, 0.0, 0.0); // after doing it twice there should still be 5
071    insert5Points (kdtree, 0.1, 0.0); // this should add 5 more points
072    insert5Points (kdtree, 0.0, 0.1); // this should add 5 more points
073
074
075    //        kdtree.insert (new Point2D(0.15, 0.18));
076    //        kdtree.insert (new Point2D(0.86, 0.26));
077    //        kdtree.insert (new Point2D(0.70, 0.11));
078    //        kdtree.insert (new Point2D(0.16, 0.01));
079    //        kdtree.insert (new Point2D(0.62, 0.95));
080    //        kdtree.insert (new Point2D(0.98, 0.04));
081    //        kdtree.insert (new Point2D(0.87, 0.79));
082    //        kdtree.insert (new Point2D(0.83, 0.21));
083
084    //        Point2D mid = new Point2D (0.5, 0.5);
085    //        Point2D less = new Point2D (0.5, 0.4);
086    //        Point2D more = new Point2D (0.5, 0.6);
087    //        kdtree.insert (mid);
088    //        kdtree.insert (less);
089    //        kdtree.insert (more);
090    //        StdOut.println (kdtree.contains (less));
091    //        StdOut.println (kdtree.contains (more));
092    //        StdOut.println (kdtree.range (new RectHV (0.5, 0.4, 0.5, 0.6)));
093    //        StdOut.println (kdtree.nearest (less));
094    //        StdOut.println (kdtree.nearest (more));
095
096    StdOut.println (kdtree);
097        kdtree.toGraphviz ();
098    kdtree.draw ();
099  }
100}