Algorithms-I : 5-kdtrees: implement PointSET

1 files changed, 29 insertions, 5 deletions

diff --git a/Algorithms/Part-I/5-KdTrees/PointSET.java b/Algorithms/Part-I/5-KdTrees/PointSET.java
index aabceff..f5594de 100644
--- a/Algorithms/Part-I/5-KdTrees/PointSET.java
+++ b/Algorithms/Part-I/5-KdTrees/PointSET.java
@@ -1,50 +1,74 @@
 /* vim: set expandtab tabstop=4 shiftwidth=4 : */
 
+import java.util.TreeSet;
+
 public class PointSET
 {
+    private TreeSet<Point2D> set;
     // construct an empty set of points
     public PointSET()
     {
+        set = new TreeSet<Point2D>();
     }
 
     // is the set empty?
     public boolean isEmpty()
     {
-        return true;
+        return set.isEmpty();
     }
 
     // number of points in the set
     public int size()
     {
-        return 0;
+        return set.size();
     }
 
     // add the point p to the set (if it is not already in the set)
     public void insert(Point2D p)
     {
+        set.add(p);
     }
 
     // does the set contain the point p?
     public boolean contains(Point2D p)
     {
-        return false;
+        return set.contains(p);
     }
 
     // draw all of the points to standard draw
     public void draw()
     {
+        for (Point2D p : set) p.draw();
     }
 
     // all points in the set that are inside the rectangle
     public Iterable<Point2D> range(RectHV rect)
     {
-        return null;
+        Stack<Point2D> stack = new Stack<Point2D>();
+
+        for (Point2D p : set)
+            if (rect.contains(p)) stack.push(p);
+
+        return stack;
     }
 
     // a nearest neighbor in the set to p; null if set is empty
     public Point2D nearest(Point2D p)
     {
-        return null;
+        if (set.isEmpty()) return null;
+
+        Point2D p0 = null;
+        double d = Double.MAX_VALUE;
+        for (Point2D o : set)
+        {
+            double d2 = p.distanceTo(o);
+            if (d2 < d) {
+                d = d2;
+                p0 = o;
+            }
+        }
+        return p0;
+
     }
 }