Skip to content

Instantly share code, notes, and snippets.

@Chayemor

Chayemor/KdTree.java

Created August 5, 2020 15:14
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Chayemor/632a6bd1110401dc5cf82d72497104e6 to your computer and use it in GitHub Desktop.
Save Chayemor/632a6bd1110401dc5cf82d72497104e6 to your computer and use it in GitHub Desktop.
Download ZIP
Kd-Trees - Coursera Algorithms Part 1
Raw
KdTree.java
/******************************************************************************
*
* Name: Johanna Mesa Ramos
* Coursera User ID: c02b4bb527298de170192d644483baeb
* Last modified: 08/2020
* Course: Algorithms, Part I https://www.coursera.org/learn/algorithms-part1
*
******************************************************************************/
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.RectHV;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class KdTree {
private static class Node {
private final Point2D point;
private Node left, right;
private final boolean useX;
public Node(Point2D p, Node lt, Node r, boolean alternate) {
point = p;
left = lt;
right = r;
useX = alternate;
}
}
private Node root = null;
private int size = 0;
private void checkNull(Object obj) {
if (obj == null)
throw new IllegalArgumentException("Parameter can't be null");
}
public boolean isEmpty() {
return root == null;
}
public int size() {
return size;
}
public void insert(Point2D p) {
checkNull(p);
if (root == null) {
root = new Node(p, null, null, true);
++size;
}
else if (!contains(p)) {
++size;
insert(root, p);
}
}
private void insert(Node parent, Point2D p) {
Comparator<Point2D> comparator = parent.useX ? Point2D.X_ORDER : Point2D.Y_ORDER;
if (comparator.compare(parent.point, p) > 0) {
if (parent.left == null)
parent.left = new Node(p, null, null, !parent.useX);
else
insert(parent.left, p);
}
else {
if (parent.right == null)
parent.right = new Node(p, null, null, !parent.useX);
else
insert(parent.right, p);
}
}
public boolean contains(Point2D p) {
checkNull(p);
return contains(root, p);
}
private boolean contains(Node parent, Point2D p) {
if (parent == null)
return false;
Comparator<Point2D> comparator = parent.useX ? Point2D.X_ORDER : Point2D.Y_ORDER;
if (parent.point.equals(p)) return true;
if (comparator.compare(parent.point, p) > 0) {
return contains(parent.left, p);
}
else {
return contains(parent.right, p);
}
}
public void draw() {
draw(root, new RectHV(0, 0, 1, 1)); // The root corresponds to the unit square
}
private void draw(Node n, RectHV rect) {
if (n == null)
return;
StdDraw.setPenRadius(0.01);
StdDraw.setPenColor(StdDraw.BLACK);
n.point.draw();
StdDraw.setPenRadius();
if (n.useX) { // vertical
StdDraw.setPenColor(StdDraw.RED);
StdDraw.line(n.point.x(), rect.ymin(), n.point.x(), rect.ymax());
draw(n.left, new RectHV(rect.xmin(), rect.ymin(), n.point.x(), rect.ymax()));
draw(n.right, new RectHV(n.point.x(), rect.ymin(), rect.xmax(), rect.ymax()));
}
else { // horizontal
StdDraw.setPenColor(StdDraw.BLUE);
StdDraw.line(rect.xmin(), n.point.y(), rect.xmax(), n.point.y());
draw(n.left, new RectHV(rect.xmin(), rect.ymin(), rect.xmax(), n.point.y()));
draw(n.right, new RectHV(rect.xmin(), n.point.y(), rect.xmax(), rect.ymax()));
}
}
public Iterable<Point2D> range(RectHV rect) {
checkNull(rect);
List<Point2D> points = new ArrayList<>();
range(root, rect, points);
return points;
}
/*
* Instead of checking whether the query rectangle intersects the rectangle corresponding to a node,
* it suffices to check only whether the query rectangle intersects the splitting line segment:
* if it does, then recursively search both subtrees;
* otherwise, recursively search the one subtree where points intersecting the query rectangle could be.
* */
private void range(Node current, RectHV rect, List<Point2D> points) {
if (current == null)
return;
if (rect.contains(current.point))
points.add(current.point);
if (current.useX) { // vertical
if (current.point.x() >= rect.xmin() && current.point.x() <= rect.xmax()) {
range(current.left, rect, points);
range(current.right, rect, points);
}
else if (current.point.x() <= rect.xmin()) {
range(current.right, rect, points);
}
else if (current.point.x() >= rect.xmax()) {
range(current.left, rect, points);
}
}
else { // horizontal
if (current.point.y() >= rect.ymin() && current.point.y() <= rect.ymax()) {
range(current.left, rect, points);
range(current.right, rect, points);
}
else if (current.point.y() <= rect.ymin()) {
range(current.right, rect, points);
}
else if (current.point.y() >= rect.ymax()) {
range(current.left, rect, points);
}
}
}
public Point2D nearest(Point2D p) {
return nearest(root, root, p, Double.POSITIVE_INFINITY, new RectHV(0, 0, 1, 1));
}
private Point2D nearest(Node current, Node currentMin, Point2D p, double minDistance,
RectHV nodeRect) {
if (current == null)
return currentMin == null ? null : currentMin.point;
double distance = p.distanceSquaredTo(current.point);
if (distance < minDistance) {
currentMin = current;
minDistance = distance;
}
if (nodeRect.distanceSquaredTo(p) > minDistance)
return currentMin == null ? null : currentMin.point;
RectHV leftRect, rightRect;
if (current.useX) {
leftRect = new RectHV(nodeRect.xmin(), nodeRect.ymin(), current.point.x(),
nodeRect.ymax());
rightRect = new RectHV(current.point.x(), nodeRect.ymin(), nodeRect.xmax(),
nodeRect.ymax());
}
else {
leftRect = new RectHV(nodeRect.xmin(), nodeRect.ymin(), nodeRect.xmax(),
current.point.y());
rightRect = new RectHV(nodeRect.xmin(), current.point.y(), nodeRect.xmax(),
nodeRect.ymax());
}
Point2D rightNearest = nearest(current.right, currentMin, p, minDistance, rightRect);
Point2D leftNearest = nearest(current.left, currentMin, p, minDistance, leftRect);
return p.distanceSquaredTo(rightNearest) < p.distanceSquaredTo(leftNearest)
? rightNearest
: leftNearest;
}
public static void main(String[] args) {
// initialize the two data structures with point from file
String filename = args[0];
In in = new In(filename);
KdTree kdtree = new KdTree();
while (!in.isEmpty()) {
double x = in.readDouble();
double y = in.readDouble();
Point2D p = new Point2D(x, y);
kdtree.insert(p);
}
kdtree.insert(new Point2D(0.372, 0.497));
kdtree.insert(new Point2D(0.564, 0.413));
kdtree.insert(new Point2D(0.226, 0.577));
kdtree.insert(new Point2D(0.144, 0.179));
kdtree.insert(new Point2D(0.083, 0.51));
kdtree.insert(new Point2D(0.32, 0.708));
kdtree.insert(new Point2D(0.417, 0.362));
kdtree.insert(new Point2D(0.862, 0.825));
kdtree.insert(new Point2D(0.785, 0.725));
kdtree.insert(new Point2D(0.499, 0.208));
Point2D queryPoint = new Point2D(0.017, 0.678);
Point2D nearest = kdtree.nearest(queryPoint);
StdOut.println(nearest);
StdOut.println(nearest.distanceSquaredTo(queryPoint));
}
}
Raw
KdTreeVisualizer.java
/******************************************************************************
* Compilation: javac KdTreeVisualizer.java
* Execution: java KdTreeVisualizer
* Dependencies: KdTree.java
*
* Add the points that the user clicks in the standard draw window
* to a kd-tree and draw the resulting kd-tree.
*
******************************************************************************/
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.RectHV;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;
public class KdTreeVisualizer {
public static void main(String[] args) {
RectHV rect = new RectHV(0.0, 0.0, 1.0, 1.0);
StdDraw.enableDoubleBuffering();
KdTree kdtree = new KdTree();
while (true) {
if (StdDraw.isMousePressed()) {
double x = StdDraw.mouseX();
double y = StdDraw.mouseY();
StdOut.printf("%8.6f %8.6f\n", x, y);
Point2D p = new Point2D(x, y);
if (rect.contains(p)) {
StdOut.printf("%8.6f %8.6f\n", x, y);
kdtree.insert(p);
StdDraw.clear();
kdtree.draw();
StdDraw.show();
}
}
StdDraw.pause(100);
}
}
}
Raw
NearestNeighborVisualizer.java
/******************************************************************************
* Compilation: javac NearestNeighborVisualizer.java
* Execution: java NearestNeighborVisualizer input.txt
* Dependencies: PointSET.java KdTree.java
*
* Read points from a file (specified as a command-line argument) and
* draw to standard draw. Highlight the closest point to the mouse.
*
* The nearest neighbor according to the brute-force algorithm is drawn
* in red; the nearest neighbor using the kd-tree algorithm is drawn in blue.
*
******************************************************************************/
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.StdDraw;
public class NearestNeighborVisualizer {
public static void main(String[] args) {
// initialize the two data structures with point from file
String filename = args[0];
In in = new In(filename);
PointSET brute = new PointSET();
KdTree kdtree = new KdTree();
while (!in.isEmpty()) {
double x = in.readDouble();
double y = in.readDouble();
Point2D p = new Point2D(x, y);
kdtree.insert(p);
brute.insert(p);
}
// process nearest neighbor queries
StdDraw.enableDoubleBuffering();
while (true) {
// the location (x, y) of the mouse
double x = StdDraw.mouseX();
double y = StdDraw.mouseY();
Point2D query = new Point2D(x, y);
// draw all of the points
StdDraw.clear();
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius(0.01);
brute.draw();
// draw in red the nearest neighbor (using brute-force algorithm)
StdDraw.setPenRadius(0.03);
StdDraw.setPenColor(StdDraw.RED);
brute.nearest(query).draw();
StdDraw.setPenRadius(0.02);
// draw in blue the nearest neighbor (using kd-tree algorithm)
StdDraw.setPenColor(StdDraw.BLUE);
kdtree.nearest(query).draw();
StdDraw.show();
StdDraw.pause(40);
}
}
}
Raw
PointSET.java
/******************************************************************************
*
* Name: Johanna Mesa Ramos
* Coursera User ID: c02b4bb527298de170192d644483baeb
* Last modified: 08/2020
* Course: Algorithms, Part I https://www.coursera.org/learn/algorithms-part1
*
******************************************************************************/
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.RectHV;
import edu.princeton.cs.algs4.StdDraw;
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;
public class PointSET {
private final TreeSet<Point2D> tree;
public PointSET() {
tree = new TreeSet<>();
}
private void checkNull(Object obj) {
if (obj == null)
throw new IllegalArgumentException("Parameter can't be null");
}
public boolean isEmpty() {
return tree.isEmpty();
}
public int size() {
return tree.size();
}
public void insert(Point2D p) {
checkNull(p);
tree.add(p);
}
public boolean contains(Point2D p) {
checkNull(p);
return tree.contains(p);
}
public void draw() {
StdDraw.setPenRadius(0.015);
StdDraw.setPenColor(StdDraw.BLUE);
for (Point2D p : tree)
p.draw();
StdDraw.show();
}
public Iterable<Point2D> range(RectHV rect) {
checkNull(rect);
List<Point2D> points = new ArrayList<>();
for (Point2D p : tree) {
if (rect.contains(p))
points.add(p);
}
return points;
}
public Point2D nearest(Point2D p) {
checkNull(p);
Point2D neighbour = null;
double minDistance = Double.POSITIVE_INFINITY;
for (Point2D candidate : tree) {
double distance = p.distanceSquaredTo(candidate);
if (distance < minDistance) {
neighbour = candidate;
minDistance = distance;
}
}
return neighbour;
}
}
Raw
Z - Results
ASSESSMENT SUMMARY
Compilation: PASSED
API: PASSED
Spotbugs: PASSED
PMD: FAILED (1 warning)
Checkstyle: FAILED (0 errors, 2 warnings)
Correctness: 32/35 tests passed
Memory: 16/16 tests passed
Timing: 34/42 tests passed
Aggregate score: 91.05%
[Compilation: 5%, API: 5%, Spotbugs: 0%, PMD: 0%, Checkstyle: 0%, Correctness: 60%, Memory: 10%, Timing: 20%]
ASSESSMENT DETAILS
The following files were submitted:
----------------------------------
13K Aug 5 14:02 KdTree.java
1.7K Aug 5 14:02 PointSET.java
********************************************************************************
* COMPILING
********************************************************************************
% javac PointSET.java
*-----------------------------------------------------------
% javac KdTree.java
*-----------------------------------------------------------
================================================================
Checking the APIs of your programs.
*-----------------------------------------------------------
PointSET:
KdTree:
================================================================
********************************************************************************
* CHECKING STYLE AND COMMON BUG PATTERNS
********************************************************************************
% spotbugs *.class
*-----------------------------------------------------------
================================================================
% pmd .
*-----------------------------------------------------------
KdTree.java:212: Avoid unused private methods, such as 'optNearest(Node,Node,Point2D,double,RectHV)'. [UnusedPrivateMethod]
PMD ends with 1 warning.
================================================================
% checkstyle *.java
*-----------------------------------------------------------
[WARN] KdTree.java:320:11: '//' or '/*' is not followed by whitespace. [WhitespaceAfter]
Checkstyle ends with 0 errors and 1 warning.
% custom checkstyle checks for PointSET.java
*-----------------------------------------------------------
[WARN] PointSET.java:41:30: The numeric literal '0.015' appears to be unnecessary. [NumericLiteral]
Checkstyle ends with 0 errors and 1 warning.
% custom checkstyle checks for KdTree.java
*-----------------------------------------------------------
================================================================
********************************************************************************
* TESTING CORRECTNESS
********************************************************************************
Testing correctness of PointSET
*-----------------------------------------------------------
Running 8 total tests.
A point in an m-by-m grid means that it is of the form (i/m, j/m),
where i and j are integers between 0 and m
Test 1: insert n random points; check size() and isEmpty() after each insertion
(size may be less than n because of duplicates)
* 5 random points in a 1-by-1 grid
* 50 random points in a 8-by-8 grid
* 100 random points in a 16-by-16 grid
* 1000 random points in a 128-by-128 grid
* 5000 random points in a 1024-by-1024 grid
* 50000 random points in a 65536-by-65536 grid
==> passed
Test 2: insert n random points; check contains() with random query points
* 1 random points in a 1-by-1 grid
* 10 random points in a 4-by-4 grid
* 20 random points in a 8-by-8 grid
* 10000 random points in a 128-by-128 grid
* 100000 random points in a 1024-by-1024 grid
* 100000 random points in a 65536-by-65536 grid
==> passed
Test 3: insert random points; check nearest() with random query points
* 10 random points in a 4-by-4 grid
* 15 random points in a 8-by-8 grid
* 20 random points in a 16-by-16 grid
* 100 random points in a 32-by-32 grid
* 10000 random points in a 65536-by-65536 grid
==> passed
Test 4: insert random points; check range() with random query rectangles
* 2 random points and random rectangles in a 2-by-2 grid
* 10 random points and random rectangles in a 4-by-4 grid
* 20 random points and random rectangles in a 8-by-8 grid
* 100 random points and random rectangles in a 16-by-16 grid
* 1000 random points and random rectangles in a 64-by-64 grid
* 10000 random points and random rectangles in a 128-by-128 grid
==> passed
Test 5: call methods before inserting any points
* size() and isEmpty()
* contains()
* nearest()
* range()
==> passed
Test 6: call methods with null argument
* insert()
* contains()
* range()
* nearest()
==> passed
Test 7: check intermixed sequence of calls to insert(), isEmpty(),
size(), contains(), range(), and nearest() with
probabilities (p1, p2, p3, p4, p5, p6, p7), respectively
* 10000 calls with random points in a 1-by-1 grid
and probabilities (0.3, 0.1, 0.1, 0.1, 0.2, 0.2)
* 10000 calls with random points in a 16-by-16 grid
and probabilities (0.3, 0.1, 0.1, 0.1, 0.2, 0.2)
* 10000 calls with random points in a 128-by-128 grid
and probabilities (0.3, 0.1, 0.1, 0.1, 0.2, 0.2)
* 10000 calls with random points in a 1024-by-1024 grid
and probabilities (0.3, 0.1, 0.1, 0.1, 0.2, 0.2)
* 10000 calls with random points in a 8192-by-8192 grid
and probabilities (0.3, 0.1, 0.1, 0.1, 0.2, 0.2)
* 10000 calls with random points in a 65536-by-65536 grid
and probabilities (0.3, 0.1, 0.1, 0.1, 0.2, 0.2)
==> passed
Test 8: check that two PointSET objects can be created at the same time
==> passed
Total: 8/8 tests passed!
================================================================
Testing correctness of KdTree
*-----------------------------------------------------------
Running 27 total tests.
In the tests below, we consider three classes of points and rectangles.
* Non-degenerate points: no two points (or rectangles) share either an
x-coordinate or a y-coordinate
* Distinct points: no two points (or rectangles) share both an
x-coordinate and a y-coordinate
* General points: no restrictions on the x-coordinates or y-coordinates
of the points (or rectangles)
A point in an m-by-m grid means that it is of the form (i/m, j/m),
where i and j are integers between 0 and m (inclusive).
Test 1a: insert points from file; check size() and isEmpty() after each insertion
* input0.txt
* input1.txt
* input5.txt
* input10.txt
==> passed
Test 1b: insert non-degenerate points; check size() and isEmpty() after each insertion
* 1 random non-degenerate points in a 1-by-1 grid
* 5 random non-degenerate points in a 8-by-8 grid
* 10 random non-degenerate points in a 16-by-16 grid
* 50 random non-degenerate points in a 128-by-128 grid
* 500 random non-degenerate points in a 1024-by-1024 grid
* 50000 random non-degenerate points in a 65536-by-65536 grid
==> passed
Test 1c: insert distinct points; check size() and isEmpty() after each insertion
* 1 random distinct points in a 1-by-1 grid
* 10 random distinct points in a 8-by-8 grid
* 20 random distinct points in a 16-by-16 grid
* 10000 random distinct points in a 128-by-128 grid
* 100000 random distinct points in a 1024-by-1024 grid
* 100000 random distinct points in a 65536-by-65536 grid
==> passed
Test 1d: insert general points; check size() and isEmpty() after each insertion
* 5 random general points in a 1-by-1 grid
* 10 random general points in a 4-by-4 grid
* 50 random general points in a 8-by-8 grid
* 100000 random general points in a 16-by-16 grid
* 100000 random general points in a 128-by-128 grid
* 100000 random general points in a 1024-by-1024 grid
==> passed
Test 2a: insert points from file; check contains() with random query points
* input0.txt
* input1.txt
* input5.txt
* input10.txt
==> passed
Test 2b: insert non-degenerate points; check contains() with random query points
* 1 random non-degenerate points in a 1-by-1 grid
* 5 random non-degenerate points in a 8-by-8 grid
* 10 random non-degenerate points in a 16-by-16 grid
* 20 random non-degenerate points in a 32-by-32 grid
* 500 random non-degenerate points in a 1024-by-1024 grid
* 10000 random non-degenerate points in a 65536-by-65536 grid
==> passed
Test 2c: insert distinct points; check contains() with random query points
* 1 random distinct points in a 1-by-1 grid
* 10 random distinct points in a 4-by-4 grid
* 20 random distinct points in a 8-by-8 grid
* 10000 random distinct points in a 128-by-128 grid
* 100000 random distinct points in a 1024-by-1024 grid
* 100000 random distinct points in a 65536-by-65536 grid
==> passed
Test 2d: insert general points; check contains() with random query points
* 10000 random general points in a 1-by-1 grid
* 10000 random general points in a 16-by-16 grid
* 10000 random general points in a 128-by-128 grid
* 10000 random general points in a 1024-by-1024 grid
==> passed
Test 3a: insert points from file; check range() with random query rectangles
* input0.txt
* input1.txt
* input5.txt
* input10.txt
==> passed
Test 3b: insert non-degenerate points; check range() with random query rectangles
* 1 random non-degenerate points and random rectangles in a 2-by-2 grid
* 5 random non-degenerate points and random rectangles in a 8-by-8 grid
* 10 random non-degenerate points and random rectangles in a 16-by-16 grid
* 20 random non-degenerate points and random rectangles in a 32-by-32 grid
* 500 random non-degenerate points and random rectangles in a 1024-by-1024 grid
* 10000 random non-degenerate points and random rectangles in a 65536-by-65536 grid
==> passed
Test 3c: insert distinct points; check range() with random query rectangles
* 2 random distinct points and random rectangles in a 2-by-2 grid
* 10 random distinct points and random rectangles in a 4-by-4 grid
* 20 random distinct points and random rectangles in a 8-by-8 grid
* 100 random distinct points and random rectangles in a 16-by-16 grid
* 1000 random distinct points and random rectangles in a 64-by-64 grid
* 10000 random distinct points and random rectangles in a 128-by-128 grid
==> passed
Test 3d: insert general points; check range() with random query rectangles
* 5000 random general points and random rectangles in a 2-by-2 grid
* 5000 random general points and random rectangles in a 16-by-16 grid
* 5000 random general points and random rectangles in a 128-by-128 grid
* 5000 random general points and random rectangles in a 1024-by-1024 grid
==> passed
Test 3e: insert random points; check range() with tiny rectangles
enclosing each point
* 5 tiny rectangles and 5 general points in a 2-by-2 grid
* 10 tiny rectangles and 10 general points in a 4-by-4 grid
* 20 tiny rectangles and 20 general points in a 8-by-8 grid
* 5000 tiny rectangles and 5000 general points in a 128-by-128 grid
* 5000 tiny rectangles and 5000 general points in a 1024-by-1024 grid
* 5000 tiny rectangles and 5000 general points in a 65536-by-65536 grid
==> passed
Test 4a: insert points from file; check range() with random query rectangles
and check traversal of kd-tree
* input5.txt
* input10.txt
==> passed
Test 4b: insert non-degenerate points; check range() with random query rectangles
and check traversal of kd-tree
* 3 random non-degenerate points and 1000 random rectangles in a 4-by-4 grid
* 6 random non-degenerate points and 1000 random rectangles in a 8-by-8 grid
* 10 random non-degenerate points and 1000 random rectangles in a 16-by-16 grid
* 20 random non-degenerate points and 1000 random rectangles in a 32-by-32 grid
* 30 random non-degenerate points and 1000 random rectangles in a 64-by-64 grid
==> passed
Test 5a: insert points from file; check nearest() with random query points
* input0.txt
* input1.txt
* input5.txt
* input10.txt
==> passed
Test 5b: insert non-degenerate points; check nearest() with random query points
* 5 random non-degenerate points in a 8-by-8 grid
* 10 random non-degenerate points in a 16-by-16 grid
* 20 random non-degenerate points in a 32-by-32 grid
* 30 random non-degenerate points in a 64-by-64 grid
* 10000 random non-degenerate points in a 65536-by-65536 grid
==> passed
Test 5c: insert distinct points; check nearest() with random query points
* 10 random distinct points in a 4-by-4 grid
* 15 random distinct points in a 8-by-8 grid
* 20 random distinct points in a 16-by-16 grid
* 100 random distinct points in a 32-by-32 grid
* 10000 random distinct points in a 65536-by-65536 grid
==> passed
Test 5d: insert general points; check nearest() with random query points
* 10000 random general points in a 16-by-16 grid
* 10000 random general points in a 128-by-128 grid
* 10000 random general points in a 1024-by-1024 grid
==> passed
Test 6a: insert points from file; check nearest() with random query points
and check traversal of kd-tree
* input5.txt
- student nearest() = (0.4, 0.7)
- reference nearest() = (0.4, 0.7)
- performs incorrect traversal of kd-tree during call to nearest()
- query point = (0.42, 0.59)
- sequence of points inserted:
A 0.7 0.2
B 0.5 0.4
C 0.2 0.3
D 0.4 0.7
E 0.9 0.6
- student sequence of kd-tree nodes involved in calls to Point2D methods:
A E B D C
- reference sequence of kd-tree nodes involved in calls to Point2D methods:
A B D
- failed on trial 1 of 1000
* input10.txt
- student nearest() = (0.083, 0.51)
- reference nearest() = (0.083, 0.51)
- performs incorrect traversal of kd-tree during call to nearest()
- query point = (0.05, 0.4)
- sequence of points inserted:
A 0.372 0.497
B 0.564 0.413
C 0.226 0.577
D 0.144 0.179
E 0.083 0.51
F 0.32 0.708
G 0.417 0.362
H 0.862 0.825
I 0.785 0.725
J 0.499 0.208
- student sequence of kd-tree nodes involved in calls to Point2D methods:
A B H I G J C F D E
- reference sequence of kd-tree nodes involved in calls to Point2D methods:
A C D E
- failed on trial 1 of 1000
==> FAILED
Test 6b: insert non-degenerate points; check nearest() with random query points
and check traversal of kd-tree
* 5 random non-degenerate points in a 8-by-8 grid
- student nearest() = (0.125, 0.5)
- reference nearest() = (0.125, 0.5)
- performs incorrect traversal of kd-tree during call to nearest()
- query point = (0.0, 0.25)
- sequence of points inserted:
A 0.625 0.875
B 0.125 0.5
C 0.25 0.125
D 0.75 0.75
E 0.375 0.375
- student sequence of kd-tree nodes involved in calls to Point2D methods:
A D B C E
- reference sequence of kd-tree nodes involved in calls to Point2D methods:
A B C E
- failed on trial 1 of 1000
* 10 random non-degenerate points in a 16-by-16 grid
- student nearest() = (0.75, 0.0)
- reference nearest() = (0.75, 0.0)
- performs incorrect traversal of kd-tree during call to nearest()
- query point = (0.8125, 0.0625)
- sequence of points inserted:
A 0.75 0.0
B 1.0 0.25
C 0.125 0.75
D 0.0625 0.375
E 0.375 0.5625
F 0.9375 0.5
G 0.3125 0.3125
H 0.5625 0.125
I 0.0 1.0
J 0.625 0.9375
- student sequence of kd-tree nodes involved in calls to Point2D methods:
A B F C I D E G H
- reference sequence of kd-tree nodes involved in calls to Point2D methods:
A B C D E G H
- failed on trial 1 of 1000
* 20 random non-degenerate points in a 32-by-32 grid
- student nearest() = (0.1875, 0.875)
- reference nearest() = (0.1875, 0.875)
- performs incorrect traversal of kd-tree during call to nearest()
- query point = (0.0625, 0.8125)
- sequence of points inserted:
A 0.84375 0.25
B 0.65625 0.78125
C 0.15625 0.34375
D 0.59375 0.375
E 0.0 0.46875
F 0.5625 0.4375
G 1.0 0.40625
H 0.125 0.5625
I 0.03125 0.5
J 0.8125 0.125
K 0.375 0.03125
L 0.90625 0.75
M 0.3125 0.96875
N 0.625 0.0
O 0.1875 0.875
P 0.71875 0.6875
Q 0.96875 0.84375
R 0.5 0.28125
S 0.09375 0.1875
T 0.28125 0.59375
- student sequence of kd-tree nodes involved in calls to Point2D methods:
A G L Q B M O C D F P T J K R N E H I S
- reference sequence of kd-tree nodes involved in calls to Point2D methods:
A B M O C E H I D F T
- failed on trial 1 of 1000
* 30 random non-degenerate points in a 64-by-64 grid
- student nearest() = (0.46875, 0.75)
- reference nearest() = (0.46875, 0.75)
- performs incorrect traversal of kd-tree during call to nearest()
- number of student entries = 27
- number of reference entries = 11
- entry 1 of the two sequences are not equal
- student entry 1 = (0.6875, 0.59375)
- reference entry 1 = (0.625, 0.96875)
- failed on trial 1 of 1000
* 50 random non-degenerate points in a 128-by-128 grid
- student nearest() = (0.515625, 0.7421875)
- reference nearest() = (0.515625, 0.7421875)
- performs incorrect traversal of kd-tree during call to nearest()
- number of student entries = 32
- number of reference entries = 13
- entry 6 of the two sequences are not equal
- student entry 6 = (0.890625, 0.9140625)
- reference entry 6 = (0.7265625, 0.7578125)
- failed on trial 1 of 1000
* 1000 random non-degenerate points in a 2048-by-2048 grid
- student nearest() = (0.42724609375, 0.693359375)
- reference nearest() = (0.42724609375, 0.693359375)
- performs incorrect traversal of kd-tree during call to nearest()
- number of student entries = 214
- number of reference entries = 29
- entry 1 of the two sequences are not equal
- student entry 1 = (0.88330078125, 0.169921875)
- reference entry 1 = (0.681640625, 0.0126953125)
- failed on trial 1 of 1000
==> FAILED
Test 7: check with no points
* size() and isEmpty()
* contains()
* nearest()
* range()
==> passed
Test 8: check that the specified exception is thrown with null arguments
* argument to insert() is null
* argument to contains() is null
* argument to range() is null
* argument to nearest() is null
- throws wrong exception when calling nearest() with a null argument
- throws a java.lang.NullPointerException
- should throw a java.lang.IllegalArgumentException
==> FAILED
Test 9a: check intermixed sequence of calls to insert(), isEmpty(),
size(), contains(), range(), and nearest() with probabilities
(p1, p2, p3, p4, p5, p6), respectively
* 20000 calls with non-degenerate points in a 1-by-1 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with non-degenerate points in a 16-by-16 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with non-degenerate points in a 128-by-128 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with non-degenerate points in a 1024-by-1024 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with non-degenerate points in a 8192-by-8192 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with non-degenerate points in a 65536-by-65536 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
==> passed
Test 9b: check intermixed sequence of calls to insert(), isEmpty(),
size(), contains(), range(), and nearest() with probabilities
(p1, p2, p3, p4, p5, p6), respectively
* 20000 calls with distinct points in a 1-by-1 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with distinct points in a 16-by-16 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with distinct points in a 128-by-128 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with distinct points in a 1024-by-1024 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with distinct points in a 8192-by-8192 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with distinct points in a 65536-by-65536 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
==> passed
Test 9c: check intermixed sequence of calls to insert(), isEmpty(),
size(), contains(), range(), and nearest() with probabilities
(p1, p2, p3, p4, p5, p6), respectively
* 20000 calls with general points in a 1-by-1 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with general points in a 16-by-16 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with general points in a 128-by-128 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with general points in a 1024-by-1024 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with general points in a 8192-by-8192 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
* 20000 calls with general points in a 65536-by-65536 grid
and probabilities (0.3, 0.05, 0.05, 0.2, 0.2, 0.2)
==> passed
Test 10: insert n random points into two different KdTree objects;
check that repeated calls to size(), contains(), range(),
and nearest() with the same arguments yield same results
* 10 random general points in a 4-by-4 grid
* 20 random general points in a 8-by-8 grid
* 100 random general points in a 128-by-128 grid
* 1000 random general points in a 65536-by-65536 grid
==> passed
Total: 24/27 tests passed!
================================================================
********************************************************************************
* MEMORY
********************************************************************************
Analyzing memory of Point2D
*-----------------------------------------------------------
Memory of Point2D object = 32 bytes
================================================================
Analyzing memory of RectHV
*-----------------------------------------------------------
Memory of RectHV object = 48 bytes
================================================================
Analyzing memory of PointSET
*-----------------------------------------------------------
Running 8 total tests.
Memory usage of a PointSET with n points (including Point2D and RectHV objects).
Maximum allowed memory is 96n + 200 bytes.
n student (bytes) reference (bytes)
--------------------------------------------------------------
=> passed 1 240 264
=> passed 2 336 360
=> passed 5 624 648
=> passed 10 1104 1128
=> passed 25 2544 2568
=> passed 100 9744 9768
=> passed 400 38544 38568
=> passed 800 76944 76968
==> 8/8 tests passed
Total: 8/8 tests passed!
Estimated student memory (bytes) = 96.00 n + 144.00 (R^2 = 1.000)
Estimated reference memory (bytes) = 96.00 n + 168.00 (R^2 = 1.000)
================================================================
Analyzing memory of KdTree
*-----------------------------------------------------------
Running 8 total tests.
Memory usage of a KdTree with n points (including Point2D and RectHV objects).
Maximum allowed memory is 312n + 192 bytes.
n student (bytes) reference (bytes)
--------------------------------------------------------------
=> passed 1 112 160
=> passed 2 192 288
=> passed 5 432 672
=> passed 10 832 1312
=> passed 25 2032 3232
=> passed 100 8032 12832
=> passed 400 32032 51232
=> passed 800 64032 102432
==> 8/8 tests passed
Total: 8/8 tests passed!
Estimated student memory (bytes) = 80.00 n + 32.00 (R^2 = 1.000)
Estimated reference memory (bytes) = 128.00 n + 32.00 (R^2 = 1.000)
================================================================
********************************************************************************
* TIMING
********************************************************************************
Timing PointSET
*-----------------------------------------------------------
Running 14 total tests.
Inserting n points into a PointSET
n ops per second
----------------------------------------
=> passed 160000 1585101
=> passed 320000 1755217
=> passed 640000 1555990
=> passed 1280000 1254311
==> 4/4 tests passed
Performing contains() queries after inserting n points into a PointSET
n ops per second
----------------------------------------
=> passed 160000 913453
=> passed 320000 862735
=> passed 640000 878851
=> passed 1280000 653374
==> 4/4 tests passed
Performing range() queries after inserting n points into a PointSET
n ops per second
----------------------------------------
=> passed 10000 4396
=> passed 20000 1663
=> passed 40000 699
==> 3/3 tests passed
Performing nearest() queries after inserting n points into a PointSET
n ops per second
----------------------------------------
=> passed 10000 4581
=> passed 20000 1643
=> passed 40000 771
==> 3/3 tests passed
Total: 14/14 tests passed!
================================================================
Timing KdTree
*-----------------------------------------------------------
Running 28 total tests.
Test 1a-d: Insert n points into a 2d tree. The table gives the average number of calls
to methods in RectHV and Point per call to insert().
Point2D
n ops per second RectHV() x() y() equals()
----------------------------------------------------------------------------------------------------------------
=> passed 160000 1361763 0.0 88.6 84.6 21.6
=> passed 320000 1336789 0.0 90.2 86.2 22.0
=> passed 640000 952865 0.0 96.2 92.2 23.5
=> passed 1280000 808592 0.0 104.6 100.6 25.6
==> 4/4 tests passed
Test 2a-h: Perform contains() queries after inserting n points into a 2d tree. The table gives
the average number of calls to methods in RectHV and Point per call to contains().
Point2D
n ops per second x() y() equals()
-----------------------------------------------------------------------------------------------
=> passed 10000 1105654 37.0 35.0 18.0
=> passed 20000 677628 39.3 37.3 19.2
=> passed 40000 1041149 43.6 41.6 21.3
=> passed 80000 606688 44.0 42.0 21.5
=> passed 160000 907622 46.5 44.5 22.7
=> passed 320000 679954 50.1 48.1 24.5
=> passed 640000 533510 51.4 49.4 25.2
=> passed 1280000 666286 54.4 52.4 26.7
==> 8/8 tests passed
Test 3a-h: Perform range() queries after inserting n points into a 2d tree. The table gives
the average number of calls to methods in RectHV and Point per call to range().
n ops per second intersects() contains() x() y()
---------------------------------------------------------------------------------------------------------------
=> passed 10000 553695 0.0 31.1 93.4 54.1
=> passed 20000 580060 0.0 32.6 97.6 61.4
=> passed 40000 523977 0.0 39.3 119.4 67.7
=> passed 80000 450019 0.0 40.7 122.6 71.3
=> passed 160000 382854 0.0 42.5 130.0 82.0
=> passed 320000 323128 0.0 40.2 121.8 72.4
=> passed 640000 262136 0.0 43.3 130.0 80.1
=> passed 1280000 206895 0.0 47.0 143.1 77.6
==> 8/8 tests passed
Test 4a-h: Perform nearest() queries after inserting n points into a 2d tree. The table gives
the average number of calls to methods in RectHV and Point per call to nearest().
Point2D RectHV
n ops per second distanceSquaredTo() distanceSquaredTo() x() y()
------------------------------------------------------------------------------------------------------------------------
=> FAILED 10000 26908 (0.9x) 1557.3 (2.6x) 633.6 (2.1x) 2029.7 (2.5x) 2003.9 (2.5x)
=> FAILED 20000 21776 (0.7x) 2165.6 (3.6x) 877.4 (2.9x) 2830.1 (3.5x) 2790.5 (3.5x)
=> FAILED 40000 15177 (0.5x) 2985.3 (5.0x) 1207.9 (4.0x) 3920.2 (4.9x) 3738.1 (4.7x)
=> FAILED 80000 9192 (0.3x) 5146.0 (8.6x) 2088.4 (7.0x) 6566.5 (8.2x) 6380.8 (8.0x)
=> FAILED 160000 5973 (0.2x) 7129.3 (11.9x) 2886.8 (9.6x) 9272.2 (11.6x) 8960.7 (11.2x)
=> FAILED 320000 4102 (0.2x) 9642.5 (16.1x) 3887.5 (13.0x) 12467.0 (15.6x) 12172.3 (15.2x)
=> FAILED 640000 3541 (0.2x) 10356.0 (17.3x) 4174.3 (13.9x) 13379.4 (16.7x) 12889.7 (16.1x)
=> FAILED 1280000 2410 (0.1x) 16778.3 (28.0x) 6762.2 (22.5x) 22171.9 (27.7x) 21116.2 (26.4x)
==> 0/8 tests passed
Total: 20/28 tests passed!
================================================================
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment