COS226

• Download Point2D.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;


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