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 implements Comparable<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
    //lexicographic order (natural order)
    public int compareTo(Point2D other) {
        // first object: this (instance)
        // second object: other (parameter)
        // -> comparison this < other

        if (this.x < other.x) return -1;
        else if (this.x == other.x) {
            return this.y - other.y;
        }
        else
            return 1;
    }

    // compare two points according to y coordinate
    public static class byYCoordinat 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
            // ...
            if (p.y < q.y) return -1;
            if (p.y > q.y) return  1;

            // otherwise points have equal y coordinate
            return 0;         
        }
    }

    // Compare the distance of two points to an origin
    public static class byDistanceSq implements Comparator<Point2D> {
        private final Point2D origin; // origin point that
                                      // distance is measured to
        
        public byDistanceSq(Point2D origin) {
            this.origin = origin;
        }
        public int compare(Point2D p, Point2D q) {
            Integer dist_p = distanceSquared(origin, p);
            Integer dist_q = distanceSquared(origin, q);

            // WAY 1
            return dist_p - dist_q;

            // WAY 2
            //if (dist_p < dist_q) return -1;
            //if (dist_p > dist_q) return  1;
            //return 0;
            //
            //// WAY 3
            //return dist_p.compareTo(dist_q);
        }
    }

    public String toString() {
        return "(" + this.x + ", " + this.y + ")";
    }
    

    public static void printPoints(Point2D[] a) {
        StdOut.print("-> ");
        for (int i = 0; i < a.length; i++)
            StdOut.print(a[i]);
        StdOut.println(".");
    }

    public final static Comparator<Point2D> BY_Y_AXIS =
        new byYCoordinate();

    public static <T> boolean isSorted(T[] a, Comparator<T> cmp) {
        for(int i = 0; i < a.length - 1; i++) {
            if (cmp.compare(a[i], a[i+1]) > 0)
                return false;
        }
        return true;
    }

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

        assert (p1.compareTo(p6) < 0);
        
        Point2D[] arr = { p1, p2, p3, p4, p5, p6, p7, p8 };
        printPoints(arr);
        StdOut.println(isSorted(arr, BY_Y_AXIS));

        
        Arrays.sort(arr, BY_Y_AXIS);
        printPoints(arr);
        StdOut.println(isSorted(arr, BY_Y_AXIS));
        
        Arrays.sort(arr);
        printPoints(arr);
        
        Comparator<Point2D> dist_p8_cmp =
            new byDistanceSq(p8);

        StdOut.println("before: "+ isSorted(arr, dist_p8_cmp));
        
        Arrays.sort(arr, dist_p8_cmp);
        printPoints(arr);
        StdOut.println("after: " + isSorted(arr, dist_p8_cmp));
        StdOut.println("after (y-axis): " + isSorted(arr, BY_Y_AXIS));
        Arrays.sort(arr, BY_Y_AXIS);
        printPoints(arr);
    }














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