package lib280.base; import lib280.exception.InvalidArgument280Exception; public
ID: 3731925 • Letter: P
Question
package lib280.base;
import lib280.exception.InvalidArgument280Exception;
public class NDPoint280 implements Comparable<NDPoint280> {
protected Double coords[];
protected int dim;
/**
* Create a new N-dimensional point at the origin (0,0,..., 0).
*
* @param dim Dimensionality of the point.
*/
public NDPoint280(int dim) {
if( dim < 1 ) throw new IllegalArgumentException("NDPoint: dimension of point must be at least 1.");
this.dim = dim;
coords = new Double[dim];
}
/**
* Create a point from a coordinate in an array of Double. The dimensionality of
* the point is equal to the length of pt.
*
* @param pt Coordinates of the new point.
*/
public NDPoint280(Double pt[]) {
this.dim = pt.length;
if( this.dim < 1 ) throw new IllegalArgumentException("NDPoint: dimension of point must be at least 1.");
coords = new Double[this.dim];
this.copyArray(pt);
}
/**
* Create a point from a coordinate in array of double. The dimensionality of
* the point is equal to the length of pt.
*
* @param pt Coordinates of the new point.
*/
public NDPoint280(double pt[]) {
this.dim = pt.length;
if( this.dim < 1 ) throw new IllegalArgumentException("NDPoint: dimension of point must be at least 1.");
coords = new Double[this.dim];
this.copyArray(pt);
}
/**
* Use the coordinates in the given array for this point.
* @param pt New coordinates for this point.
* @precond pt must be equal to this.dim()
* @throws InvalidArgument280Exception if the length of pt is not equal to the the dimensionality of this N-dimensional point.
*/
protected void copyArray(Double pt[]) {
if( this.dim() != pt.length ) throw new InvalidArgument280Exception("Array length must equal point dimensionality ("+this.dim+")");
for(int i=0; i < this.dim; i++) {
coords[i] = pt[i];
}
}
/**
* Use the coordinates in the given array for this point.
* @param pt New coordinates for this point.
* @precond pt must be equal to this.dim()
* @throws InvalidArgument280Exception if the length of pt is not equal to the the dimensionality of this N-dimensional point.
*/
protected void copyArray(double pt[]) {
if( this.dim() != pt.length ) throw new InvalidArgument280Exception("Array length must equal point dimensionality ("+this.dim+")");
for(int i=0; i < this.dim; i++) {
coords[i] = pt[i];
}
}
/**
* Get the dimensionality of the point.
* @return The dimensionality of the point.
*/
public int dim() { return this.dim; }
/**
* Set the coordinates of this point.
*
* @param pt The point to store represented as an array of double.
* @precond Length of pt must be at least 1 and be equal to this.dim()
*/
public void setPoint(Double pt[]) {
if( this.dim != pt.length) {
this.dim = pt.length;
if( this.dim < 1 ) throw new IllegalArgumentException("NDPoint: dimension of point must be at least 1.");
coords = new Double[this.dim];
}
this.copyArray(pt);
}
/**
* Obtain the i-th coordinate of the point.
* @param i Desired coordinate of the point.
* @precond i is less than the point's dimensionality
* @return The value of the i-th coordinate of the point.
* @throws InvalidArgument280Exception if i is not a valid dimension index for this n-diensional point (i.e. if i >= n)
*/
public double idx(int i) {
if( i >= this.dim ) throw new InvalidArgument280Exception("Requested coordinate index exceeds point dimensionality.");
return coords[i];
}
@Override
public String toString() {
String out = "(" + coords[0];
for(int i=1; i < this.dim; i++) {
out += ", " + coords[i];
}
out += ")";
return out;
}
/**
* Compares the i-th coordinate of two NDPoint objects.
* @param i Index of the coordinate to compare.
* @param other The point to which to compare this point.
* @precond i is less than this point's dimensionality
* @precond this.dim() must equal other.dim()
* @return -1 if the i-th coordinate of this point is smaller than that of 'other';
* 0 if the i-th coordinate of this point and 'other' are equal; or
* 1 if the i-th coordinate of this point is greater than that of 'other'.
*/
public int compareByDim(int i, NDPoint280 other) {
if( other.dim() != this.dim ) {
throw new IllegalArgumentException("NDPoint: comparing two points of different dimension");
}
if( i >= this.dim ) {
throw new IllegalArgumentException("NDPoint: comparing dimension: " + i + ", but point only has dimension " + this.dim);
}
return coords[i].compareTo(other.coords[i]);
}
/**
* Compares this point to 'o' based on the first non-equal dimension (i.e. lexographic ordering).
* @precond this.dim() must equal o.dim()
* @param o The point to which this point is to be compared.
*/
public int compareTo(NDPoint280 o) {
if( this.dim != o.dim )
throw new IllegalArgumentException("NDPoint: comparing two points of different dimension");
for(int i=0; i < this.dim; i++) {
if( this.coords[i].compareTo(o.coords[i]) != 0 ) {
return this.coords[i].compareTo(o.coords[i]);
}
}
return 0;
}
public static void main(String args[]) {
// test first constructor, test dim()
NDPoint280 p = new NDPoint280(5);
if( p.dim() != 5) System.out.println("Newly created point should have dimension 5, but has dimension " + p.dim());
// test second constructor, test dim()
Double pt3d[] = {1.0, 2.0, 3.0};
p = new NDPoint280(pt3d);
if( p.dim() != 3) System.out.println("Newly created point should have dimension 3, but has dimension " + p.dim());
if( p.idx(0) != 1.0 || p.idx(1) != 2.0 || p.idx(2) != 3.0 )
System.out.println("Point should be (1.0, 2.0, 3.0) but it is: " + p);
// test setPoint() and idx()
Double newpt3d[] = {3.0, 2.0, 1.0};
p.setPoint(newpt3d);
if( p.idx(0) != 3.0 || p.idx(1) != 2.0 || p.idx(2) != 1.0 )
System.out.println("Point should be (3.0, 2.0, 1.0) but it is: " + p);
// test toString()
String ptAsString = p.toString();
if( ptAsString.compareTo("(3.0, 2.0, 1.0)") != 0 )
System.out.println("Sting representation of point should be "(3.0, 2.0, 1.0)" but it is: "" + ptAsString + """);
// test compareTo() when the first coordinate is different
NDPoint280 q = new NDPoint280(pt3d);
if( p.compareTo(p) != 0 )
System.out.println("The point is not equal to itself!");
if( p.compareTo(q) != 1 )
System.out.println("Point p should be greater than point q, but it isn't.");
if( q.compareTo(p) != -1 )
System.out.println("Point q should be less than point p, but it isn't.");
// test compareTo() when the third coordinate is different
Double anotherPoint[] = {1.0, 2.0, 4.0};
p.setPoint(anotherPoint);
if( p.compareTo(q) != 1 )
System.out.println("Point p should be greater than point q, but it isn't.");
if( q.compareTo(p) != -1 )
System.out.println("Point q should be less than point p, but it isn't.");
// test compareByDim()
if( p.compareByDim(1, q) != 0 )
System.out.println("Coordinate 0 of p and q should be equal but they are reportedly not.");
if( p.compareByDim(1, q) != 0 )
System.out.println("Coordinate 1 of p and q should be equal but they are reportedly not.");
if( p.compareByDim(2, q) != 1 )
System.out.println("Coordinate 2 of p should be larger than coordinate 2 of q, but it is reportedly not.");
System.out.println("Unit test complete.");
}
}
#exception
/* InvalidArgument280Exception.java
* ---------------------------------------------
* Copyright (c) 2004 University of Saskatchewan
* All Rights Reserved
* --------------------------------------------- */
package lib280.exception;
/** This exception is used when a method takes in an invalid argument. */
public class InvalidArgument280Exception extends Exception280
{
/** Create an exception with the specified message. <br>
Analysis: Time = O(1) */
public InvalidArgument280Exception(String message)
{
super(message);
}
/** Create an exception with the default message. <br>
Analysis: Time = O(1) */
public InvalidArgument280Exception()
{
super("InvalidArgument280Exception thrown!");
}
}
Implementing the k-D Tree - What You Must Do Implement a k-D tree. You must use the NDPoint280 class provided in the lib280.base package of lib280-asn6 to represent your k-dimensional points. You must design and implement both a node class (KDNode280.java) and a tree class (KDTree280.java). Other than specific instructions given in this question, the design of these classes is up to you. You may use as much or as little of lib280 as you think is appropriate. You'll be graded in the actual appropriateness of your choices here. You should aim to make the class fit into lib280 and its hierarchy of data structures, but you should not force things by extending classes inappropriately. You may use whatever private/protected methods you deem necessary A portion of the marks for this question will be awarded for the design/modularity/style of the im- plementation of your class. A portion of the marks for this question will be awarded for acceptable inline and javadoc commenting. Your ADT must support the following operations: . Construct a new (balanced) k-D tree from a set of k-dimensional points (it must work for any k > 0) . Perform a range search: given a pair of points (al'a2.. ..ak) and (b1, b2 ., bk), aiExplanation / Answer
You need to import lib280.base.NDPoint280 class from lib280.base package.See my code below and u will understand.
--------------------------------------------------------------------------------------------------------------------------------------
Here is my code for KDNode280.java class
--------------------------------------------------------------------------------------------------------------------------------------
package lib280.tree;
import lib280.base.NDPoint280;
public class KDNode280<I extends Comparable<? super I>> {
// Contents of the node.
protected NDPoint280 item;
// pointer to left child
protected KDNode280<I> left_Child = null;
// pointer to right child
protected KDNode280<I> right_Child = null;
/**
* Is the tree empty?. Analysis: Time = O(1)
*/
public boolean isEmpty() {
if (item == null)
return true;
else
return false;
}
// Form a string representation that includes level numbers.
// Analysis: Time = O(n), where n = number of items in the (sub)node
// @param i the level for the root of this (sub)node
protected String toStringByLevel(int i) {
StringBuffer blanks = new StringBuffer((i - 1) * 5);
for (int j = 0; j < i - 1; j++)
blanks.append(" ");
String result = new String();
if (!isEmpty() && (left_Child != null || right_Child != null))
result += right_Child.toStringByLevel(i + 1);
result += " " + blanks + i + ": ";
if (isEmpty())
result += "-";
else {
result += item;
if (left_Child != null || right_Child != null) {
if (left_Child != null)
result += left_Child.toStringByLevel(i + 1);
}
}
return result;
}
// String representation of the tree, level by level. <br>
// Analysis: Time = O(n), where n = number of items in the node
public String toStringByLevel() {
return toStringByLevel(1);
}
// constructs the node
// @param dimension the dimension of the node
public KDNode280(int dimension) {
NDPoint280 p = new NDPoint280(dimension);
this.item = p;
}
}
---------------------------------------------------------------------------------------------------------------------------------------
Here is my code for KDTree280.java class
---------------------------------------------------------------------------------------------------------------------------------------
package lib280.tree;
public class KDTree280<I extends Comparable<? super I>> extends LinkedSimpleTree280<I> {
// The dimension of the tree
private int dimensions;
// The KD Tree
KDTree280<I> kdTree;
// Root of kdTree
KDNode280<I> root_Node;
// Constructor of kdTree
public KDTree280(KDNode280<I>[] point_Array,int left,int right, int depth){
this.root_Node = kdtree(point_Array, left, right, depth);
}
// The constructor for the kdTree
// @param pointArray - an array of KDNode280s
// @param left - left most offset of the array
// @param right - right most offset of the array
// @param depth - current depth in the partially built tree
// @param dimension - dimension of the tree
// @return node - newly constructed node
public KDNode280<I> kdtree(KDNode280<I>[] pointArray,int left,int right, int depth){
this.dimensions = pointArray[0].item.dim();
if ((right-left) <= -1){
return null;
}
else{
int d = depth % this.dimensions;
int medianOffset = (left+right)/2;
KDNode280<I> node = new KDNode280<I>(this.dimensions);
node.item = pointArray[medianOffset].item;
node.left_Child = kdtree(pointArray, left, medianOffset-1, depth+1);//recursion
node.right_Child = kdtree(pointArray, medianOffset+1, right, depth+1);//recursion
return node;
}
}
// Search Range
// @param T subtree in which to search for elements between a and b inclusive
// @param a - lower bound of search range
// @param b - midd bound of search range
// @param depth the depth of the tree*/
public String searchRange(KDNode280<I> T,KDNode280<I> a,KDNode280<I> b, int depth){
String result = "";
if (T.left_Child == null || T.right_Child == null){
if (T.left_Child==null && T.right_Child!= null)
return result+=T.right_Child.item.toString()+ " " + T.item.toString()+ " ";
else if (T.left_Child != null && T.right_Child == null)
return result+=T.left_Child.item.toString() + " " + T.item.toString()+ " ";
else
return result+= T.item.toString()+ " ";
}
int dimension = depth % dimensions;
//System.out.println("String so far: " + result);
if (T.left_Child.item.compareByDim(dimension, a.item) <= 0){
return searchRange(T.left_Child, a, b, depth+1);// items less than a, search right
}
else if (T.left_Child.item.compareByDim(dimension, b.item) >= 0){
return searchRange(T.right_Child, a, b, depth+1);// items larger than b, search left
}
else{
// could be both trees
String L = this.searchRange(T.left_Child, a, b, depth +1);
String R = this.searchRange(T.right_Child, a, b, depth+1);
if (T.item.compareByDim(dimension, a.item) >= 0 && T.item.compareByDim(dimension, b.item) <= 0){
return result+= L + R + T.item + " ";
}
else
return result+=L+R+ " ";
}
}
@SuppressWarnings({ "rawtypes", "unchecked" })
public static void main(String args[]) { // a method to test the function
System.out.println("Input 2D points:");
KDNode280[] arr = new KDNode280[8];
Double pt02d[] = {5.0,2.0};
Double pt12d[] = {9.0,10.0};
Double pt22d[] = {11.0,1.0};
Double pt32d[] = {4.0,3.0};
Double pt42d[] = {2.0,19.0};
Double pt52d[] = {3.0,7.0};
Double pt62d[] = {1.0,5.0};
Double pt72d[] = {0.0,18.0};
for (int i = 0; i<8;i++)
arr[i] = new KDNode280(2);
arr[0].item.setPoint(pt02d);
arr[1].item.setPoint(pt12d);
arr[2].item.setPoint(pt22d);
arr[3].item.setPoint(pt32d);
arr[4].item.setPoint(pt42d);
arr[5].item.setPoint(pt52d);
arr[6].item.setPoint(pt62d);
arr[7].item.setPoint(pt72d);
for (int i = 0; i<arr.length;i++)
System.out.println(arr[i].item.toString());
KDTree280 newTree = new KDTree280(arr, 0,7,0);
System.out.println(newTree.root_Node.toStringByLevel());
System.out.println(" Input 3D points:");
KDNode280[] arr2 = new KDNode280[8];
Double p0d[] = {5.0,2.0,6.0};
Double p1d[] = {6.0,10.0,1.0};
Double p2d[] = {11.0,1.0,2.0};
Double p3d[] = {4.0,3.0,0.0};
Double p4d[] = {2.0,12.0,5.0};
Double p5d[] = {3.0,7.0,7.0};
Double p6d[] = {1.0,5.0,8.0};
Double p7d[] = {0.0,11.0,4.0};
for (int i = 0; i<8;i++)
arr2[i] = new KDNode280(3);
arr2[0].item.setPoint(p0d);
arr2[1].item.setPoint(p1d);
arr2[2].item.setPoint(p2d);
arr2[3].item.setPoint(p3d);
arr2[4].item.setPoint(p4d);
arr2[5].item.setPoint(p5d);
arr2[6].item.setPoint(p6d);
arr2[7].item.setPoint(p7d);
for (int i = 0; i<arr2.length; i++)
System.out.println(arr2[i].item.toString());
KDTree280 newTree2 = new KDTree280(arr2, 0,7,0);
System.out.println(newTree2.root_Node.toStringByLevel());
Double a1[] = {1.0,5.0,8.0};
Double b1[] = {1.0,6.0,9.0};
KDNode280 a = new KDNode280(3);
a.item.setPoint(a1);
KDNode280 b = new KDNode280(3);
b.item.setPoint(b1);
System.out.println("Looking for points between {0.0,4.0,7.0} and {1.0,6.0,9.0} Found: ");
System.out.print(newTree2.searchRange(newTree2.root_Node, a, b, 0));
System.out.println(" ");
Double a2[] = {0.0,0.0,0.0};
Double b2[] = {3.0,14.0,6.0};
a.item.setPoint(a2);
b.item.setPoint(b2);
System.out.println("Looking for points between {0.0,0.0,0.0} and {3.0,14.0,6.0} Found: ");
System.out.print(newTree2.searchRange(newTree2.root_Node, a, b, 0));
System.out.println(" ");
Double a3[] = {-5.0,-5.0,-5.0};
Double b3[] = {20.0,20.0,20.0};
a.item.setPoint(a3);
b.item.setPoint(b3);
System.out.println("Looking for points between {-5.0,-5.0,-5.0} and {20.0,20.0,20.0} Found: ");
System.out.print(newTree2.searchRange(newTree2.root_Node, a, b, 0));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.