001package algs32.kdtree; 002import stdlib.*; 003import algs12.Point2D; 004import algs13.Queue; 005//import algs35.SET; 006 007public class PointSET { 008 private final java.util.TreeSet<Point2D> set; 009 010 /* construct an empty set of points */ 011 public PointSET() { 012 set = new java.util.TreeSet<> (); 013 } 014 015 /* is the set empty? */ 016 public boolean isEmpty() { 017 return set.isEmpty (); 018 } 019 020 /* number of points in the set */ 021 public int size() { 022 return set.size (); 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 if (p == null) 028 throw new IllegalArgumentException (); 029 set.add (p); 030 } 031 032 /* does the set contain the point p? */ 033 public boolean contains(Point2D target) { 034 return set.contains (target); 035 } 036 037 /* draw all of the points to standard draw */ 038 public void draw() { 039 for (Point2D p : set) 040 p.draw (); 041 } 042 043 /* all points in the set that are inside the rectangle */ 044 public Iterable<Point2D> range(RectHV target) { 045 final Queue<Point2D> queue = new Queue<> (); 046 for (Point2D p : set) 047 if (target.contains (p)) queue.enqueue (p); 048 return queue; 049 } 050 051 052 /* a nearest neighbor in the set to p; null if set is empty */ 053 public Point2D nearest(Point2D target) { 054 Point2D champ = null; 055 double distance = Double.POSITIVE_INFINITY; 056 for (Point2D q : set) { 057 final double d = target.distanceTo (q); 058 if (d <= distance) { 059 champ = q; 060 distance = d; 061 } 062 } 063 return champ; 064 } 065 066 public String toString () { 067 StringBuilder sb = new StringBuilder (); 068 for (Point2D key : set) 069 sb.append (key + " "); 070 return sb.toString (); 071 } 072 073 /* unit testing of the methods */ 074 public static void main(String[] args) { 075 PointSET brute = new PointSET (); 076 brute.insert (new Point2D (0.04,0.02)); 077 brute.insert (new Point2D (0.83,0.19)); 078 brute.insert (new Point2D (0.81,0.26)); 079 brute.insert (new Point2D (0.95,0.13)); 080 brute.insert (new Point2D (0.02,0.65)); 081 brute.insert (new Point2D (0.70,0.94)); 082 brute.insert (new Point2D (0.41,0.89)); 083 StdOut.println (brute.size ()); 084 StdOut.println (brute); 085 } 086}