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 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 Queue class represents a first-in-first-out (FIFO)

* queue of generic items.

* It supports the usual enqueue and dequeue

* operations, along with methods for peeking at the top item,

* testing if the queue is empty, and iterating through

* the items in FIFO order.

*

* All queue operations except iteration are constant time.

*

* For additional documentation, see Section 1.3 of

* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

*/

public class Queue implements Iterable {

private int N; // number of elements on queue

private Node first; // beginning of queue

private Node last; // end of queue

// helper linked list class

private static class Node {

public Node() { }

public T item;

public Node 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 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 boolean check(Queue that) {

int N = that.N;

Queue.Node first = that.first;

Queue.Node 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 x = first; x != null; x = x.next) {

numberOfNodes++;

}

if (numberOfNodes != N) return false;

// check internal consistency of instance variable last

Queue.Node 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 iterator() {

return new ListIterator();

}

// an iterator, doesn't implement remove() since it's optional

private class ListIterator implements Iterator {

private Node 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 prev, Node 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 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 {

public static final Comparator X_ORDER = new XOrder();

public static final Comparator Y_ORDER = new YOrder();

public static final Comparator R_ORDER = new ROrder();

public final Comparator POLAR_ORDER = new PolarOrder();

public final Comparator ATAN2_ORDER = new Atan2Order();

public final Comparator 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 {

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 {

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 {

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 {

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 {

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 {

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);

// }

}

}