Problem. (Brute-force Implementation) Write a mutable data type BrutePointST that implements the above API using red-black BST (edu.princeton.cs.algs4.RedBlackBST). Corner cases. Throw a java.lang.NullPointerException if any argument is null. Performance requirements. Your implementation should support put(), get() and contains() in time proportional to the logarithm of the number of points in the set in the worst case; it should support points(), range(), and nearest() in time proportional to the number of points in the symbol table.

$ java BrutePointST 0.661633 0.287141 0.65 0.68 0.28 0.29 5 < data/input10K.txt st.empty()? false st.size() = 10000 First 5 values: 3380 1585 8903 4168 5971 7265 st.contains((0.661633, 0.287141))? true st.range([0.65, 0.68] x [0.28, 0.29]): (0.663908, 0.285337) (0.661633, 0.287141) (0.671793, 0.288608) st.nearest ((0.661633, 0.287141)) = (0.663908, 0.285337) st.nearest ((0.661633, 0.287141), 5): (0.663908, 0.285337) (0.658329, 0.290039) (0.671793, 0.288608) (0.65471, 0.276885) (0.668229, 0.276482)

import edu.princeton.cs.algs4.MinPQ; import edu.princeton.cs.algs4.Point2D; import edu.princeton.cs.algs4.Queue; import edu.princeton.cs.algs4.RectHV; import edu.princeton.cs.algs4.RedBlackBST; import edu.princeton.cs.algs4.StdIn; import edu.princeton.cs.algs4.StdOut;

public class BrutePointST implements PointST { ... // Construct an empty symbol table of points. public BrutePointST() { ... }

// Is the symbol table empty? public boolean isEmpty() { ... }

// Number of points in the symbol table. public int size() { ... }

// Associate the value val with point p. public void put(Point2D p, Value val) { ... }

// Value associated with point p. public Value get(Point2D p) { ... }

// Does the symbol table contain the point p? public boolean contains(Point2D p) { ... }

// All points in the symbol table. public Iterable points() { ... }

// All points in the symbol table that are inside the rectangle rect. public Iterable range(RectHV rect) { ... }

// A nearest neighbor to point p; null if the symbol table is empty. public Point2D nearest(Point2D p) { ... }

// k points that are closest to point p. public Iterable nearest(Point2D p, int k) { ... }

// Test client. [DO NOT EDIT] public static void main(String[] args) { BrutePointST st = new BrutePointST(); double qx = Double.parseDouble(args[0]); double qy = Double.parseDouble(args[1]); double rx1 = Double.parseDouble(args[2]); double rx2 = Double.parseDouble(args[3]); double ry1 = Double.parseDouble(args[4]); double ry2 = Double.parseDouble(args[5]); int k = Integer.parseInt(args[6]); Point2D query = new Point2D(qx, qy); RectHV rect = new RectHV(rx1, ry1, rx2, ry2); int i = 0; while (!StdIn.isEmpty()) { double x = StdIn.readDouble(); double y = StdIn.readDouble(); Point2D p = new Point2D(x, y); st.put(p, i++); } StdOut.println("st.empty()? " + st.isEmpty()); StdOut.println("st.size() = " + st.size()); StdOut.println("First " + k + " values:"); i = 0; for (Point2D p : st.points()) { StdOut.println(" " + st.get(p)); if (i++ == k) { break; } } StdOut.println("st.contains(" + query + ")? " + st.contains(query)); StdOut.println("st.range(" + rect + "):"); for (Point2D p : st.range(rect)) { StdOut.println(" " + p); } StdOut.println("st.nearest(" + query + ") = " + st.nearest(query)); StdOut.println("st.nearest(" + query + ", " + k + "):"); for (Point2D p : st.nearest(query, k)) { StdOut.println(" " + p); } } }