COS226

• Download Point2D-solution.java

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