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;
// "Example of Comparable and Comparator"
// don't forget to rename "Point2D-solution.java" -> "Point2D.java"
// "implements Comparable<TTTTT>" means:
// - the object can be compared to objects of type TTTTT
// - it has a "public int compareTo(TTTTT other)" method
// in its API
public class Point2D implements Comparable<Point2D> {
private final int x; // x coordinate
private final int y; // y coordinate
public static Comparator<Point2D> myYaxisComparator = new BY_Y_AXIS();
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
// a = this b = other
public int compareTo(Point2D other) {
// lexicographical order
// A = (x1, y1) < B = (x2, y2)
//
// --- if (x1 < x2) {
// --- // A < B
// --- return -1;
// --- } else {
// --- if (x1 == x2) {
// --- if (y1 < y2) {
// --- return -1;
// --- } else if (y1 == y2)
// --- // A == B (x1 == x2, y1 == y2)
// --- return 0;
// --- else // x1 == x2 and y1 > y2
// --- return 1; // A > B
// --- } else { // x1 > x2
// --- return 1;
// --- }
// --- }
if (this.x < other.x) return -1;
else if (this.x == other.x) {
return this.y - other.y;
} else
// this.x > other.x
return 1;
}
public String toString() {
return "(" + this.x + ", " + this.y + ")";
}
// example of some (bogus) comparator
public static class BY_Y_AXIS 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
// ...
// order according to Y-axis
if (p.y < q.y) return -1;
else if (p.y > q.y) return 1;
else
// p.y == q.y
return 0;
}
}
// Compare the distance of two points to an origin
public static class byDistanceSq implements Comparator<Point2D> {
// FIXME: add instance variable(s)
private Point2D origin_of_comparator;
// ================================================================
// ====> BEWARE THE CONSTRUCTOR <=====
public byDistanceSq(Point2D origin) {
origin_of_comparator = origin;
}
// ================================================================
public int compare(Point2D p, Point2D q) {
// distanceSquared(Point2D to, Point2D from)
int dist_p = Point2D.distanceSquared(this.origin_of_comparator, p);
int dist_q = Point2D.distanceSquared(this.origin_of_comparator, q);
if (dist_p < dist_q) return -1;
else if (dist_p > dist_q) return 1;
else return 0;
}
}
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
Point2D p1 = new Point2D(0, 7);
Point2D p2 = new Point2D(2, 1);
Point2D p3 = new Point2D(1, 0);
Point2D p4 = new Point2D(0, 1);
Point2D p5 = new Point2D(0, 1);
Point2D p6 = new Point2D(1, 1);
Point2D p7 = new Point2D(1, 3);
Point2D p8 = new Point2D(10, 10);
Point2D[] array = { p1, p2, p3, p4, p5, p6, p7, p8 };
printPoints(array);
StdOut.println("Sorting by natural (lexicographic) order");
Arrays.sort(array);
printPoints(array);
StdOut.println("Sorting according to BY_Y_AXIS");
Comparator<Point2D> mycomparator = new BY_Y_AXIS(); // instance
Arrays.sort(array, mycomparator);
printPoints(array);
Arrays.sort(array, Point2D.myYaxisComparator);
printPoints(array);
StdOut.println("Sorting according to point (9,9)");
Comparator<Point2D> ninenine_comparator =
new byDistanceSq(new Point2D(9,9));
Arrays.sort(array, ninenine_comparator);
printPoints(array);
StdOut.println("Sorting according to point (1,1)");
Comparator<Point2D> oneone_comparator =
new byDistanceSq(new Point2D(1,1));
Arrays.sort(array, oneone_comparator);
printPoints(array);
}
// 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;
}
}