No COMPILER ERRORS package algs32.kdtree; import algs12.Point2D; import algs13.Q
ID: 3881869 • Letter: N
Question
No COMPILER ERRORS
package algs32.kdtree;
import algs12.Point2D;
import algs13.Queue;
import stdlib.*;
/* a set of points implemented as kd-tree */
public class KdTree {
private static class Node {
// TODO
}
private Node root;
/* construct an empty set of points */
public KdTree() {
// TODO -- maybe nothing to do here... in which case you can remove this and use the default constructor
}
/* is the set empty? */
public boolean isEmpty() {
// TODO
return false;
}
/* add the point p to the set (if it is not already in the set) */
public void insert(Point2D p) {
// TODO
}
/* does the set contain the point p? */
public boolean contains(Point2D target) {
// TODO
return false;
}
/* all points in the set that are inside the target rectangle */
public Iterable<Point2D> range(RectHV target) {
// TODO
return new Queue<>();
}
/* a nearest neighbor to target point; null if empty */
public Point2D nearest(Point2D target) {
// TODO
return new Point2D (0, 0);
}
/* draw all of the points to standard draw */
/* for x-node, use red line to draw the division between left/right */
/* for y-node, use blue line to draw the division between top/bottom */
/* see the writeup for examples */
public void draw() {
// TODO
}
/* some test code */
public void toGraphviz() { GraphvizBuilder.nodesToFile (root); }
private static void insert5Points (KdTree kdtree, double xoffset, double yoffset) {
kdtree.insert (new Point2D (0.7 + xoffset, 0.2 + yoffset));
kdtree.insert (new Point2D (0.5 + xoffset, 0.4 + yoffset));
kdtree.insert (new Point2D (0.2 + xoffset, 0.3 + yoffset));
kdtree.insert (new Point2D (0.4 + xoffset, 0.7 + yoffset));
kdtree.insert (new Point2D (0.9 + xoffset, 0.6 + yoffset));
}
public static void main (String[] args) {
KdTree kdtree = new KdTree ();
insert5Points (kdtree, 0.0, 0.0); // after this there should be 5 points
insert5Points (kdtree, 0.0, 0.0); // after doing it twice there should still be 5
insert5Points (kdtree, 0.1, 0.0); // this should add 5 more points
insert5Points (kdtree, 0.0, 0.1); // this should add 5 more points
// kdtree.insert (new Point2D(0.15, 0.18));
// kdtree.insert (new Point2D(0.86, 0.26));
// kdtree.insert (new Point2D(0.70, 0.11));
// kdtree.insert (new Point2D(0.16, 0.01));
// kdtree.insert (new Point2D(0.62, 0.95));
// kdtree.insert (new Point2D(0.98, 0.04));
// kdtree.insert (new Point2D(0.87, 0.79));
// kdtree.insert (new Point2D(0.83, 0.21));
// Point2D mid = new Point2D (0.5, 0.5);
// Point2D less = new Point2D (0.5, 0.4);
// Point2D more = new Point2D (0.5, 0.6);
// kdtree.insert (mid);
// kdtree.insert (less);
// kdtree.insert (more);
// StdOut.println (kdtree.contains (less));
// StdOut.println (kdtree.contains (more));
// StdOut.println (kdtree.range (new RectHV (0.5, 0.4, 0.5, 0.6)));
// StdOut.println (kdtree.nearest (less));
// StdOut.println (kdtree.nearest (more));
StdOut.println (kdtree);
kdtree.toGraphviz ();
kdtree.draw ();
}
}
Queue.java
package algs13;
import stdlib.*;
import java.util.Iterator;
import java.util.NoSuchElementException;
/* ***********************************************************************
* Compilation: javac Queue.java
* Execution: java Queue < input.txt
* Data files: http://algs4.cs.princeton.edu/13stacks/tobe.txt
*
* A generic queue, implemented using a linked list.
*
* % java Queue < tobe.txt
* to be or not to be (2 left on queue)
*
*************************************************************************/
/**
* The <tt>Queue</tt> class represents a first-in-first-out (FIFO)
* queue of generic items.
* It supports the usual <em>enqueue</em> and <em>dequeue</em>
* operations, along with methods for peeking at the top item,
* testing if the queue is empty, and iterating through
* the items in FIFO order.
* <p>
* All queue operations except iteration are constant time.
* <p>
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*/
public class Queue<T> implements Iterable<T> {
private int N; // number of elements on queue
private Node<T> first; // beginning of queue
private Node<T> last; // end of queue
// helper linked list class
private static class Node<T> {
public Node() { }
public T item;
public Node<T> next;
}
/**
* Create an empty queue.
*/
public Queue() {
first = null;
last = null;
N = 0;
}
/**
* Is the queue empty?
*/
public boolean isEmpty() {
return first == null;
}
/**
* Return the number of items in the queue.
*/
public int size() {
return N;
}
/**
* Return the item least recently added to the queue.
* @throws java.util.NoSuchElementException if queue is empty.
*/
public T peek() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
return first.item;
}
/**
* Add the item to the queue.
*/
public void enqueue(T item) {
Node<T> oldlast = last;
last = new Node<>();
last.item = item;
last.next = null;
if (isEmpty()) first = last;
else oldlast.next = last;
N++;
}
/**
* Remove and return the item on the queue least recently added.
* @throws java.util.NoSuchElementException if queue is empty.
*/
public T dequeue() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
T item = first.item;
first = first.next;
N--;
if (isEmpty()) last = null;
return item;
}
/**
* Return string representation.
*/
public String toString() {
StringBuilder s = new StringBuilder();
for (T item : this)
s.append(item + " ");
return s.toString();
}
// check internal invariants
private static <T> boolean check(Queue<T> that) {
int N = that.N;
Queue.Node<T> first = that.first;
Queue.Node<T> last = that.last;
if (N == 0) {
if (first != null) return false;
if (last != null) return false;
}
else if (N == 1) {
if (first == null || last == null) return false;
if (first != last) return false;
if (first.next != null) return false;
}
else {
if (first == last) return false;
if (first.next == null) return false;
if (last.next != null) return false;
// check internal consistency of instance variable N
int numberOfNodes = 0;
for (Queue.Node<T> x = first; x != null; x = x.next) {
numberOfNodes++;
}
if (numberOfNodes != N) return false;
// check internal consistency of instance variable last
Queue.Node<T> lastNode = first;
while (lastNode.next != null) {
lastNode = lastNode.next;
}
if (last != lastNode) return false;
}
return true;
}
/**
* Return an iterator that iterates over the items on the queue in FIFO order.
*/
public Iterator<T> iterator() {
return new ListIterator();
}
// an iterator, doesn't implement remove() since it's optional
private class ListIterator implements Iterator<T> {
private Node<T> current = first;
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public T next() {
if (!hasNext()) throw new NoSuchElementException();
T item = current.item;
current = current.next;
return item;
}
}
public void toGraphviz(String filename) {
GraphvizBuilder gb = new GraphvizBuilder ();
toGraphviz (gb, null, first);
gb.toFile (filename, "rankdir="LR"");
}
private void toGraphviz (GraphvizBuilder gb, Node<T> prev, Node<T> n) {
if (n == null) { gb.addNullEdge (prev); return; }
gb.addLabeledNode (n, n.item.toString ());
if (prev != null) gb.addEdge (prev, n);
toGraphviz (gb, n, n.next);
}
/**
* A test client.
*/
public static void main(String[] args) {
StdIn.fromString ("to be or not to - be - - that - - - is");
Queue<String> q = new Queue<>();
int count = 0;
q.toGraphviz ("queue" + count + ".png"); count++;
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) q.enqueue(item);
else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");
q.toGraphviz ("queue" + count + ".png"); count++;
}
StdOut.println("(" + q.size() + " left on queue)");
}
}
Point2D.java
// Exercise 2.5.25 (Solution published at http://algs4.cs.princeton.edu/)
package algs12;
import stdlib.*;
//import java.util.Arrays;
import java.util.Comparator;
/* ***********************************************************************
* Compilation: javac Point2D.java
*
* Immutable point data type for points in the plane.
*
*************************************************************************/
public class Point2D implements Comparable<Point2D> {
public static final Comparator<Point2D> X_ORDER = new XOrder();
public static final Comparator<Point2D> Y_ORDER = new YOrder();
public static final Comparator<Point2D> R_ORDER = new ROrder();
public final Comparator<Point2D> POLAR_ORDER = new PolarOrder();
public final Comparator<Point2D> ATAN2_ORDER = new Atan2Order();
public final Comparator<Point2D> DISTANCE_TO_ORDER = new DistanceToOrder();
private final double x; // x coordinate
private final double y; // y coordinate
// create a new point (x, y)
public Point2D(double x, double y) {
this.x = x;
this.y = y;
}
// return the x-coorindate of this point
public double x() { return x; }
// return the y-coorindate of this point
public double y() { return y; }
// return the radius of this point in polar coordinates
public double r() { return Math.sqrt(x*x + y*y); }
// return the angle of this point in polar coordinates
// (between -pi/2 and pi/2)
public double theta() { return Math.atan2(y, x); }
// return the polar angle between this point and that point (between -pi and pi);
// (0 if two points are equal)
private double angleTo(Point2D that) {
double dx = that.x - this.x;
double dy = that.y - this.y;
return Math.atan2(dy, dx);
}
// is a->b->c a counter-clockwise turn?
// -1 if clockwise, +1 if counter-clockwise, 0 if collinear
public static int ccw(Point2D a, Point2D b, Point2D c) {
double area2 = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
if (area2 < 0) return -1;
else if (area2 > 0) return +1;
else return 0;
}
// twice signed area of a-b-c
public static double area2(Point2D a, Point2D b, Point2D c) {
return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}
// return Euclidean distance between this point and that point
public double distanceTo(Point2D that) {
double dx = this.x - that.x;
double dy = this.y - that.y;
return Math.sqrt(dx*dx + dy*dy);
}
// return square of Euclidean distance between this point and that point
public double distanceSquaredTo(Point2D that) {
double dx = this.x - that.x;
double dy = this.y - that.y;
return dx*dx + dy*dy;
}
// compare by y-coordinate, breaking ties by x-coordinate
public int compareTo(Point2D that) {
if (this.y < that.y) return -1;
if (this.y > that.y) return +1;
if (this.x < that.x) return -1;
if (this.x > that.x) return +1;
return 0;
}
// compare points according to their x-coordinate
private static class XOrder implements Comparator<Point2D> {
public int compare(Point2D p, Point2D q) {
if (p.x < q.x) return -1;
if (p.x > q.x) return +1;
return 0;
}
}
// compare points according to their y-coordinate
private static class YOrder implements Comparator<Point2D> {
public int compare(Point2D p, Point2D q) {
if (p.y < q.y) return -1;
if (p.y > q.y) return +1;
return 0;
}
}
// compare points according to their polar radius
private static class ROrder implements Comparator<Point2D> {
public int compare(Point2D p, Point2D q) {
double delta = (p.x*p.x + p.y*p.y) - (q.x*q.x + q.y*q.y);
if (delta < 0) return -1;
if (delta > 0) return +1;
return 0;
}
}
// compare other points relative to atan2 angle (bewteen -pi/2 and pi/2) they make with this Point
private class Atan2Order implements Comparator<Point2D> {
public int compare(Point2D q1, Point2D q2) {
double angle1 = angleTo(q1);
double angle2 = angleTo(q2);
if (angle1 < angle2) return -1;
else if (angle1 > angle2) return +1;
else return 0;
}
}
// compare other points relative to polar angle (between 0 and 2pi) they make with this Point
private class PolarOrder implements Comparator<Point2D> {
public int compare(Point2D q1, Point2D q2) {
Trace.draw ();
double dx1 = q1.x - x;
double dy1 = q1.y - y;
double dx2 = q2.x - x;
double dy2 = q2.y - y;
if (dy1 >= 0 && dy2 < 0) return -1; // q1 above; q2 below
else if (dy2 >= 0 && dy1 < 0) return +1; // q1 below; q2 above
else if (dy1 == 0 && dy2 == 0) { // 3-collinear and horizontal
if (dx1 >= 0 && dx2 < 0) return -1;
else if (dx2 >= 0 && dx1 < 0) return +1;
else return 0;
}
else return -ccw(Point2D.this, q1, q2); // both above or below
// Note: ccw() recomputes dx1, dy1, dx2, and dy2
}
}
// compare points according to their distance to this point
private class DistanceToOrder implements Comparator<Point2D> {
public int compare(Point2D p, Point2D q) {
double dist1 = distanceSquaredTo(p);
double dist2 = distanceSquaredTo(q);
if (dist1 < dist2) return -1;
else if (dist1 > dist2) return +1;
else return 0;
}
}
// does this point equal y?
public boolean equals(Object other) {
if (other == this) return true;
if (other == null) return false;
if (other.getClass() != this.getClass()) return false;
Point2D that = (Point2D) other;
// Don't use == here if x or y could be NaN or -0
if (Double.compare(this.x,that.x) != 0) return false;
if (Double.compare(this.y,that.y) != 0) return false;
return true;
}
// must override hashcode if you override equals
// See Item 9 of Effective Java (2e) by Joshua Block
private volatile int hashCode;
public int hashCode() {
int result = hashCode;
if (result == 0) {
result = 17;
result = 31*result + Double.hashCode(x);
result = 31*result + Double.hashCode(y);
hashCode = result;
}
return result;
}
// convert to string
public String toString() {
return "(" + x + "," + y + ")";
}
// plot using StdDraw
public void draw() {
StdDraw.point(x, y);
}
// draw line from this point p to q using StdDraw
public void drawTo(Point2D that) {
StdDraw.line(this.x, this.y, that.x, that.y);
}
public static void main(String[] args) {
Trace.run ();
Point2D origin = new Point2D (0, 0);
Point2D a = new Point2D (1, -1);
Point2D b = new Point2D (-1, 1);
StdOut.println (origin.POLAR_ORDER.compare (a, b));
// args = new String[] { "20", "20", "100" };
//
// int x0 = Integer.parseInt(args[0]);
// int y0 = Integer.parseInt(args[1]);
// int N = Integer.parseInt(args[2]);
//
// StdDraw.setCanvasSize(800, 800);
// StdDraw.setXscale(0, 100);
// StdDraw.setYscale(0, 100);
// StdDraw.setPenRadius(.005);
// Point2D[] points = new Point2D[N];
// for (int i = 0; i < N; i++) {
// int x = StdRandom.uniform(100);
// int y = StdRandom.uniform(100);
// points[i] = new Point2D(x, y);
// points[i].draw();
// }
//
// // draw p = (x0, x1) in red
// Point2D p = new Point2D(x0, y0);
// StdDraw.setPenColor(StdDraw.RED);
// StdDraw.setPenRadius(.02);
// p.draw();
//
//
// // draw line segments from p to each point, one at a time, in polar order
// StdDraw.setPenRadius();
// StdDraw.setPenColor(StdDraw.BLUE);
// Arrays.sort(points, p.POLAR_ORDER);
// for (int i = 0; i < N; i++) {
// p.drawTo(points[i]);
// StdDraw.show(100);
// }
}
}
Explanation / Answer
Below is your code: -
/* a set of points implemented as kd-tree */
public class KdTree {
private static class Node {
private Point2D p;
private RectHV rect;
private Node lb;
private Node rt;
private Node(Point2D point, RectHV rectangle) {
p = point;
rect = rectangle;
}
}
private Node root;
private int size;
/* construct an empty set of points */
public KdTree() {
// TODO -- maybe nothing to do here... in which case you can remove this
// and use the default constructor
size = 0;
}
/* is the set empty? */
public boolean isEmpty() {
// TODO
return size == 0;
}
public int size() {
return size;
}
/* add the point p to the set (if it is not already in the set) */
public void insert(Point2D p) {
// TODO
if (p == null) {
throw new java.lang.NullPointerException();
}
root = insert(root, p, true, null, 0);
}
private Node insert(Node x, Point2D p, boolean leftRight, Node parent, int c) {
if (x == null) {
RectHV rect;
if (parent == null) {
rect = new RectHV(0.0, 0.0, 1.0, 1.0);
} else {
rect = subdivide(parent.rect, parent.p, c, !leftRight);
}
size++;
return new Node(p, rect);
}
Comparator<Point2D> comparator;
if (leftRight) {
comparator = Point2D.X_ORDER;
} else {
comparator = Point2D.Y_ORDER;
}
int cmp = comparator.compare(p, x.p);
if (cmp < 0) {
x.lb = insert(x.lb, p, !leftRight, x, cmp);
} else if (cmp > 0 || !x.p.equals(p)) {
x.rt = insert(x.rt, p, !leftRight, x, cmp);
}
return x;
}
private RectHV subdivide(RectHV rect, Point2D p, int cmp, boolean leftRight) {
if (leftRight) {
if (cmp < 0) {
return new RectHV(rect.xmin(), rect.ymin(), p.x(), rect.ymax());
} else {
return new RectHV(p.x(), rect.ymin(), rect.xmax(), rect.ymax());
}
} else {
if (cmp < 0) {
return new RectHV(rect.xmin(), rect.ymin(), rect.xmax(), p.y());
} else {
return new RectHV(rect.xmin(), p.y(), rect.xmax(), rect.ymax());
}
}
}
/* does the set contain the point p? */
public boolean contains(Point2D target) {
// TODO
if (target == null) {
throw new java.lang.NullPointerException();
}
return contains(root, target, true);
}
private boolean contains(Node x, Point2D p, boolean leftRight) {
if (x == null) {
return false;
}
if (x.p.equals(p)) {
return true;
}
Comparator<Point2D> comparator;
if (leftRight) {
comparator = Point2D.X_ORDER;
} else {
comparator = Point2D.Y_ORDER;
}
int cmp = comparator.compare(p, x.p);
if (cmp < 0) {
return contains(x.lb, p, !leftRight);
} else {
return contains(x.rt, p, !leftRight);
}
}
/* all points in the set that are inside the target rectangle */
public Iterable<Point2D> range(RectHV target) {
// TODO
if (target == null) {
throw new java.lang.NullPointerException();
}
Stack<Point2D> inside = new Stack<Point2D>();
if (root != null) {
range(root, target, inside);
}
return inside;
}
private void range(Node x, RectHV rect, Stack<Point2D> inside) {
if (rect.contains(x.p)) {
inside.push(x.p);
}
if (x.lb != null && x.lb.rect.intersects(rect)) {
range(x.lb, rect, inside);
}
if (x.rt != null && x.rt.rect.intersects(rect)) {
range(x.rt, rect, inside);
}
}
/* a nearest neighbor to target point; null if empty */
public Point2D nearest(Point2D target) {
// TODO
if (target == null) {
throw new java.lang.NullPointerException();
}
if (root == null) {
return null;
}
return findNearest(root, target, root.p);
}
private Point2D findNearest(Node x, Point2D query, Point2D nearest) {
if (x == null) {
return nearest;
}
double d2n = query.distanceSquaredTo(nearest);
double d2r = x.rect.distanceSquaredTo(query);
// Is the nearest point closer than this node's rectangle? If so, this
// node can't contain anything nearer, so return
if (d2n < d2r) {
return nearest;
}
double d2p = query.distanceSquaredTo(x.p);
// Is this node nearer than the current nearest? If so, update
if (d2p < d2n) {
nearest = x.p;
}
// No children? Return current nearest
if (x.lb == null && x.rt == null) {
return nearest;
}
// Only left/bottom child? Recurse to it
if (x.rt == null) {
return findNearest(x.lb, query, nearest);
}
// Only right/top child? Recurse to it
if (x.lb == null) {
return findNearest(x.rt, query, nearest);
}
// Try both children, the one containing the query point first
if (x.lb.rect.contains(query)) {
nearest = findNearest(x.lb, query, nearest);
nearest = findNearest(x.rt, query, nearest);
} else {
nearest = findNearest(x.rt, query, nearest);
nearest = findNearest(x.lb, query, nearest);
}
return nearest;
}
/* draw all of the points to standard draw */
/* for x-node, use red line to draw the division between left/right */
/* for y-node, use blue line to draw the division between top/bottom */
/* see the writeup for examples */
private static class NodeSplit {
private Node node;
private boolean leftRight;
private NodeSplit(Node n, boolean lr) {
node = n;
leftRight = lr;
}
}
public void draw() {
// TODO
if (root == null) {
return;
}
Stack<NodeSplit> nodes = new Stack<NodeSplit>();
nodes.push(new NodeSplit(root, true));
while (!nodes.isEmpty()) {
NodeSplit ns = nodes.pop();
StdDraw.setPenRadius(.01);
StdDraw.setPenColor(StdDraw.BLACK);
ns.node.p.draw();
RectHV r = ns.node.rect;
StdDraw.setPenRadius();
if (ns.leftRight) {
StdDraw.setPenColor(StdDraw.RED);
StdDraw.line(ns.node.p.x(), r.ymin(), ns.node.p.x(), r.ymax());
} else {
StdDraw.setPenColor(StdDraw.BLUE);
StdDraw.line(r.xmin(), ns.node.p.y(), r.xmax(), ns.node.p.y());
}
if (ns.node.lb != null) {
nodes.push(new NodeSplit(ns.node.lb, !ns.leftRight));
}
if (ns.node.rt != null) {
nodes.push(new NodeSplit(ns.node.rt, !ns.leftRight));
}
}
}
/* some test code */
public void toGraphviz() {
GraphvizBuilder.nodesToFile(root);
}
private static void insert5Points(KdTree kdtree, double xoffset, double yoffset) {
kdtree.insert(new Point2D(0.7 + xoffset, 0.2 + yoffset));
kdtree.insert(new Point2D(0.5 + xoffset, 0.4 + yoffset));
kdtree.insert(new Point2D(0.2 + xoffset, 0.3 + yoffset));
kdtree.insert(new Point2D(0.4 + xoffset, 0.7 + yoffset));
kdtree.insert(new Point2D(0.9 + xoffset, 0.6 + yoffset));
}
public static void main(String[] args) {
KdTree kdtree = new KdTree();
insert5Points(kdtree, 0.0, 0.0); // after this there should be 5 points
insert5Points(kdtree, 0.0, 0.0); // after doing it twice there should
// still be 5
insert5Points(kdtree, 0.1, 0.0); // this should add 5 more points
insert5Points(kdtree, 0.0, 0.1); // this should add 5 more points
// kdtree.insert (new Point2D(0.15, 0.18));
// kdtree.insert (new Point2D(0.86, 0.26));
// kdtree.insert (new Point2D(0.70, 0.11));
// kdtree.insert (new Point2D(0.16, 0.01));
// kdtree.insert (new Point2D(0.62, 0.95));
// kdtree.insert (new Point2D(0.98, 0.04));
// kdtree.insert (new Point2D(0.87, 0.79));
// kdtree.insert (new Point2D(0.83, 0.21));
// Point2D mid = new Point2D (0.5, 0.5);
// Point2D less = new Point2D (0.5, 0.4);
// Point2D more = new Point2D (0.5, 0.6);
// kdtree.insert (mid);
// kdtree.insert (less);
// kdtree.insert (more);
// StdOut.println (kdtree.contains (less));
// StdOut.println (kdtree.contains (more));
// StdOut.println (kdtree.range (new RectHV (0.5, 0.4, 0.5, 0.6)));
// StdOut.println (kdtree.nearest (less));
// StdOut.println (kdtree.nearest (more));
StdOut.println(kdtree);
kdtree.toGraphviz();
kdtree.draw();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.