import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;
import java.lang.UnsupportedOperationException;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Merge;
import edu.princeton.cs.algs4.Quick;
public class Point2D {
private final int x; // x coordinate
private final int y; // y coordinate
public Point2D(int x, int y) {
this.x = x;
this.y = y;
}
// compute the square of the distance between two points
public static int distanceSquared(Point2D to, Point2D from) {
return
(to.x - from.x) * (to.x - from.x) +
(to.y - from.y) * (to.y - from.y);
}
// implement Comparable<Point2D> interface
public int compareTo(Point2D other) {
throw new UnsupportedOperationException();
}
// example of some (bogus) comparator
public static class SomeComparator implements Comparator<Point2D> {
public int compare(Point2D p, Point2D q) {
// ...
// should return NEGATIVE (or -1) if p is smaller than q
// POSITIVE (or 1) if p is larger than q
// ZERO if p is equal to q
// ...
throw new UnsupportedOperationException();
}
}
// Compare the distance of two points to an origin
public static class byDistanceSq implements Comparator<Point2D> {
// FIXME: add instance variable(s)
public byDistanceSq(Point2D origin) {
// FIXME: implement this
throw new UnsupportedOperationException();
}
public int compare(Point2D p, Point2D q) {
// FIXME: implement this
throw new UnsupportedOperationException();
}
}
public static void printPoints(Point2D[] a) {
StdOut.print("-> ");
for (int i = 0; i < a.length; i++)
StdOut.print(a[i]);
StdOut.println(".");
}
public static void main(String[] args) {
// TESTING
}
// assuming arrays are sorted (duplicates are adjacent)
// will count the number of distinct elements in linear time
// (result is undefined if array is not sorted)
public static <T> int countDistinct(T[] elements, Comparator<T> cmp) {
// Assume elements are sorted
// From Precept #1
int uniqueCount = 0;
int i = 0;
int N = elements.length;
while (i < N) {
T current = elements[i];
uniqueCount += 1;
int j = i + 1;
while (j < N) {
// (BONUS QUESTION: how can I change this to
// make an elementary check of whether the array is sorted)
// element is not equal to current
if (cmp.compare(elements[j], current) != 0)
break;
j++;
}
i = j;
}
return uniqueCount;
}
}