Collinear Points

BruteCollinearPoints.java

package week3.assignment;

import edu.princeton.cs.algs4.Queue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.stream.Collectors;


public class BruteCollinearPoints {
    private final Point[] points;

    public BruteCollinearPoints(Point[] points) {
        if (points == null) {
            throw new IllegalArgumentException();
        }
        if (points.length < 2) {
            throw new IllegalArgumentException();
        }
        for (Point point : points) {
            if (point == null) {
                throw new IllegalArgumentException();
            }
        }
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
                if (points[i].compareTo(points[j]) == 0) {
                    throw new IllegalArgumentException(
                            "Two points are equal.");
                }
            }
        }
        this.points = Arrays.copyOf(points, points.length);
    }

    // the number of line segments
    public int numberOfSegments() {
        return segments().length;
    }

    public LineSegment[] segments() {
        if (points.length < 2) {
            throw new IllegalArgumentException();
        }
        Point[][] tmpPoints = new Point[points.length][4];
        int i = 0;
        for (Point p1 : points) {
            for (Point p2 : points) {
                for (Point p3 : points) {
                    for (Point p4 : points) {
                        if (p1.slopeTo(p2) == p2.slopeTo(p3) && p2.slopeTo(p3) == p3.slopeTo(p4) &&
                                p4.compareTo(p3) > 0 && p3.compareTo(p2) > 0 && p2.compareTo(p1) > 0) {
                            tmpPoints[i++] = new Point[]{p1, p2, p3, p4};
                        }
                    }
                }

            }
        }

        ExtendedQueue<Double> slopes = new ExtendedQueue<>();
        for (Point[] item : tmpPoints) {
            if (item != null && item.length > 0) {
                if (item[0] == null || item[1] == null) {
                    continue;
                }
                if (!slopes.contains(item[0].slopeTo(item[1]))) {
                    slopes.enqueue(item[0].slopeTo(item[1]));
                }
            }
        }
        ArrayList<ArrayList<Point>> pointsByslope = new ArrayList<>();
        int w = 0;
        for (double slope : slopes) {
            ArrayList<Point> elems = new ArrayList<>();
            pointsByslope.add(elems);

            for (Point[] pointSet : tmpPoints) {
                for (int j = 0; j < pointSet.length; j++) {
                    for (int k = j + 1; k < pointSet.length; k++) {
                        if (pointSet[j] == null || pointSet[k] == null) {
                            continue;
                        }
                        if (pointSet[j].slopeTo(pointSet[k]) == slope) {
                            if (!pointsByslope.get(w).contains(pointSet[j])) {
                                elems.add((pointSet[j]));
                            }
                            if (!pointsByslope.get(w).contains(pointSet[k])) {
                                elems.add((pointSet[k]));
                            }
                        }
                    }
                }
            }
            w++;
        }
        LineSegment[] resultArray = new LineSegment[pointsByslope.size()];
        int z = 0;
        for (ArrayList<Point> points : pointsByslope) {
            Point[] pts = points.toArray(new Point[points.size()]);
            Arrays.sort(pts);
            resultArray[z++] = new LineSegment(pts[0], pts[points.size() - 1]);
        }

        return resultArray;
    }

    private static class ExtendedQueue<T> extends Queue<T> {

        public void toArray(T[] result) {
            Iterator<T> it = this.iterator();
            int i = 0;
            while (it.hasNext()) {
                T next = it.next();
                result[i++] = next;
            }
        }

        public boolean contains(T target) {
            for (T t : this) {
                if (t.equals(target)) {
                    return true;
                }
            }
            return false;
        }

        public T get(int pos) {
            int i = 0;
            Iterator<T> it = this.iterator();
            while (it.hasNext()) {
                T next = it.next();
                if (i == pos) {
                    return next;
                }
                i++;
            }
            throw new NoSuchElementException();
        }
    }


    public static void main(String[] args) {
//        Files.readAllLines(Path.of(ClassLoader.getSystemClassLoader().getResource("points.txt").getPath()));
        Point[] points = {
                new Point(10_000, 0),
                new Point(0, 10_000),
                new Point(3_000, 7_000),
                new Point(7_000, 3_000),
                new Point(20_000, 21_000),
                new Point(3_000, 4_000),
                new Point(14_000, 15_000),
                new Point(6_000, 7_000),
        };
        Point[] points2 = {
                new Point(19_000, 10_000),
                new Point(18_000, 10_000),
                new Point(32_000, 10_000),
                new Point(21_000, 10_000),
                new Point(1234, 5678),
                new Point(14_000, 10_000),
        };
        var b = new BruteCollinearPoints(points);
        var b2 = new BruteCollinearPoints(points2);

        LineSegment[] segments = b.segments();
        LineSegment[] segments2 = b2.segments();
        assert Arrays.stream(segments).map(LineSegment::toString).collect(Collectors.joining(", ")).equals("(10000, 0) -> (0, 10000), (3000, 4000) -> (20000, 21000)");
        assert Arrays.stream(segments2).map(LineSegment::toString).collect(Collectors.joining(", ")).equals("(14000, 10000) -> (32000, 10000)");
        // draw the points
//        StdDraw.enableDoubleBuffering();
//        StdDraw.setXscale(0, 32768);
//        StdDraw.setYscale(0, 32768);
//        for (Point p : points) {
//            p.draw();
//        }
//        for (LineSegment segment : segments) {
//            StdOut.println(segment);
//            segment.draw();
//        }
//        StdDraw.show();
    }
}

LineSegment.java

package week3.assignment;

public class LineSegment {
    private final Point p;   // one endpoint of this line segment
    private final Point q;   // the other endpoint of this line segment

    /**
     * Initializes a new line segment.
     *
     * @param  p one endpoint
     * @param  q the other endpoint
     * @throws NullPointerException if either <tt>p</tt> or <tt>q</tt>
     *         is <tt>null</tt>
     */
    public LineSegment(Point p, Point q) {
        if (p == null || q == null) {
            throw new IllegalArgumentException("argument to LineSegment constructor is null");
        }
        if (p.equals(q)) {
            throw new IllegalArgumentException("both arguments to LineSegment constructor are the same point: " + p);
        }
        this.p = p;
        this.q = q;
    }


    /**
     * Draws this line segment to standard draw.
     */
    public void draw() {
        p.drawTo(q);
    }

    /**
     * Returns a string representation of this line segment
     * This method is provide for debugging;
     * your program should not rely on the format of the string representation.
     *
     * @return a string representation of this line segment
     */
    public String toString() {
        return p + " -> " + q;
    }

    /**
     * Throws an exception if called. The hashCode() method is not supported because
     * hashing has not yet been introduced in this course. Moreover, hashing does not
     * typically lead to good *worst-case* performance guarantees, as required on this
     * assignment.
     *
     * @throws UnsupportedOperationException if called
     */
    public int hashCode() {
        throw new UnsupportedOperationException("hashCode() is not supported");
    }
}

Point.java

package week3.assignment;

import edu.princeton.cs.algs4.StdDraw;

import java.util.Comparator;

public class Point implements Comparable<Point> {
    private final int x;
    private final int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    /*
     The compareTo() method should compare points by their y-coordinates,
      breaking ties by their x-coordinates. Formally, the invoking point (x0, y0) is less than the argument point
      (x1, y1) if and only if either y0 < y1 or if y0 = y1 and x0 < x1.
     */

    @Override
    public int compareTo(Point that) {
        if (this.y < that.y || this.y == that.y && this.x < that.x)
            return -1;
        else if (this.y > that.y || this.y == that.y && this.x > that.x)
            return 1;
        return 0;
    }

    public void draw() {
        /* DO NOT MODIFY */
        StdDraw.point(x, y);
    }

    public void drawTo(Point that) {
        /* DO NOT MODIFY */
        StdDraw.line(this.x, this.y, that.x, that.y);
    }

    public String toString() {
        /* DO NOT MODIFY */
        return "(" + x + ", " + y + ")";
    }

    /**
     * Returns the slope between this point and the specified point.
     * Formally, if the two points are (x0, y0) and (x1, y1), then the slope
     * is (y1 - y0) / (x1 - x0). For completeness, the slope is defined to be
     * +0.0 if the line segment connecting the two points is horizontal;
     * Double.POSITIVE_INFINITY if the line segment is vertical;
     * and Double.NEGATIVE_INFINITY if (x0, y0) and (x1, y1) are equal.
     *
     * @param that the other point
     * @return the slope between this point and the specified point
     */
    public double slopeTo(Point that) {
        if (this.x == that.x && this.y == that.y)
            return Double.NEGATIVE_INFINITY;
        else if (this.x != that.x && this.y == that.y)
            return +0.0;
        else if (this.x == that.x && this.y != that.y)
            return Double.POSITIVE_INFINITY;
        return (double) (that.y - this.y) / (that.x - this.x);
    }

    /**
     * Compares two points by the slope they make with this point.
     * The slope is defined as in the slopeTo() method.
     *
     * @return the Comparator that defines this ordering on points
     */
    public Comparator<Point> slopeOrder() {
        return new BySlope(this);
    }

    private static class BySlope implements Comparator<Point> {
        private final Point thisPoint;

        public BySlope(Point point) {
            thisPoint = point;
        }

        /*
         * The slopeOrder() method should return a comparator that compares
         * its two argument points by the slopes they make with the invoking
         * point (x0, y0). Formally, the point (x1, y1) is less than the point
         * (x2, y2) if and only if the slope (y1 − y0) / (x1 − x0) is less than
         * the slope (y2 − y0) / (x2 − x0).
         * Treat horizontal, vertical, and degenerate line segments as in the slopeTo() method.
         */
        @Override
        public int compare(Point p, Point q) {
            double slope0with1 = thisPoint.slopeTo(p);
            double slope0with2 = thisPoint.slopeTo(q);
            return Double.compare(slope0with1, slope0with2);
        }
    }
}