BruteCollinearPoints.java

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MergeX;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Vector;


public class BruteCollinearPoints {

    /**
     * ArrayList are best to manipulate and store the line segments. HashSets (for uniqueness) are not permitted as per assignments
     * Vectors will enable us to augment the presegment every time we can merge two presegments and they are generics.
     */
    private ArrayList<LineSegment> lineSegments;
    private ArrayList<ArrayList<Point>> segments;

    // CONSTRUCTOR finds all line segments containing 4 points
    public BruteCollinearPoints(Point[] points) {

        // get those out of the way
        checkNull(points);
        checkDuplicates(points);

        lineSegments = new ArrayList<>();
        segments = new ArrayList<>();
        ArrayList<ArrayList<Point>> segmentsCopy;

        int n = points.length;

        Point[] copySortedPoints = copySort(points); // TO AVOID MUTATING THE ARRAY

        /* We compare 4 adjacent points at a time in the array, by comparing their slopes to point[i]
         * a quadruple nested for loop will find all the combinations of N choose 4 in a quadratic (N^4)
         * amortized constant time for adds  which is acceptable as per requirement */
        for (int i = 0; i < n; i++) {
            //we maintain a min and max index to avoid writing duplicate segments
            int min = n - 1;
            int max = 0;
            int mid1 = 0;
            int mid2 = 0;
            double slope1;
            double slope2;
            double slope3;

            // we iterate over N choose 4 possible combinations
            for (int j = i + 1; j < n; j++) {
                slope1 = copySortedPoints[i].slopeTo(copySortedPoints[j]);
                for (int k = j + 1; k < n; k++) {
                    slope2 = copySortedPoints[i].slopeTo(copySortedPoints[k]);
                    /** If the first 2 slopes are not equals then the 4 points cannot be collinear
                     * and its not worth computing a third slope */
                    if (slope1 == slope2) {
                        // we calculate a third slope
                        for (int p = k + 1; p < n; p++) {
                            slope3 = copySortedPoints[i].slopeTo(copySortedPoints[p]);
                            // we test for collinear points
                            if (slope3 == slope1) {
                                // we update our min and max indices for this points[i]
                                min = Math.min(i, min);
                                max = Math.max(p, max);
                                mid1 = j;
                                mid2 = k;
                            }
                        }
                    }
                }

                /** If all three slopes are equal we have 4 collinear points. We add a new segment.
                 * An intermediary structure useful to filter duplicate points */
                if (min < max) {
                    Point p1 = copySortedPoints[min];
                    Point p2 = copySortedPoints[mid1];
                    Point p3 = copySortedPoints[mid2];
                    Point p4 = copySortedPoints[max];

                    ArrayList<Point> collinearPoints = new ArrayList<>();
                    collinearPoints.add(p1);
                    collinearPoints.add(p2);
                    collinearPoints.add(p3);
                    collinearPoints.add(p4);

                    // we make a copy of preSegments to avoid concurrent Modification Exception
                    segmentsCopy = copySortSegments(segments);

                    if (!segments.isEmpty()) {
                        /* We traverse preSegments and compare the slopes and merge with the first vector
                         * that has similar slope and at least one point in common */
                        int sum = 0;
                        for (ArrayList<Point> segment : segmentsCopy) {
                            // we check wether exists a presegment that we can merge the newly found collinearPoints with
                            sum += merge(collinearPoints, segment);
                        }
                        // if none is found we write a new presegment
                        if (sum < 1) segments.add(collinearPoints);
                    } else {
                        segments.add(collinearPoints);
                    }
                }
            }
        }
        createSegments();
    }

    private void createSegments() {
        // for each preSegment we extract the min and max
        for (ArrayList<Point> segment : segments) {
            Point[] p = new Point[segment.size()]; // to avoid casting and mutating the array
            MergeX.sort(segment.toArray(p));
            Point minPoint = p[0];
            Point maxPoint = p[segment.size() - 1];
            LineSegment s = new LineSegment(minPoint, maxPoint);
            lineSegments.add(s);
        }
    }


    private int merge(ArrayList<Point> src, ArrayList<Point> dest) {
        int found = 0;
        // precondition preSeq size and null test
        assert src.size() == 4;
        assert dest.size() >= 4;

        double srcSlope = src.get(0).slopeTo(src.get(src.size() - 1));
        double destSlope = dest.get(0).slopeTo(dest.get(dest.size() - 1));

        // a copy to avoid mutating the array
        ArrayList<Point> destCopy = copySort(dest);

        if (srcSlope == destSlope) {
            for (Point srcPoint : src) {
                if (found == 0) {
                    for (Point desPoint : destCopy) {
                        // we check if they have one point in common
                        if (srcPoint.compareTo(desPoint) == 0) {
                            // we add all the points to dest in place mutation
                            dest.addAll(src);
                            Collections.sort(dest);
                            // we exit as soon as we find an adequat segment to add it to
                            found = 1;
                            break;
                        }
                    }
                }
            }
        }
        return found;
    }


    // Brute sample client - to delete when submitting
    public static void main(String[] args) {
        // read the n points from a file
        In in = new In(args[0]);
        int n = in.readInt();
        Point[] points = new Point[n];
        for (int i = 0; i < n; i++) {
            int x = in.readInt();
            int y = in.readInt();
            points[i] = new Point(x, y);
        }

        // draw the points
        StdDraw.enableDoubleBuffering();
        StdDraw.setXscale(0, 32768);
        StdDraw.setYscale(0, 32768);

        StdDraw.setPenRadius(0.01);
        StdDraw.setPenColor();
        for (Point p : points) {
            p.draw();
        }

        StdDraw.show();

        // print and draw the line segments
        BruteCollinearPoints collinear = new BruteCollinearPoints(points);
        LineSegment[] lineSegments = collinear.segments();

        for (LineSegment segment : lineSegments) {
            if (null != segment) {
                StdOut.println(segment);
                segment.draw();
            }
        }
        StdDraw.show();
    }

    private ArrayList<Point> copySort(ArrayList<Point> segment) {
        ArrayList<Point> copy = new ArrayList<>();
        copy.addAll(segment);
        Collections.sort(copy);
        return copy;
    }


    private ArrayList<ArrayList<Point>> copySortSegments(ArrayList<ArrayList<Point>> segments) {
        ArrayList<ArrayList<Point>> copySortedPreSegments = new ArrayList<>();

        for (ArrayList<Point> segment : segments) {
            Collections.sort(segment);
            copySortedPreSegments.add(segment);
        }
        return copySortedPreSegments;
    }

    // natural order sort of points
    private Point[] copySort(Point[] points) {
        int n = points.length;
        Point[] copySortedPoints = new Point[n];
        System.arraycopy(points, 0, copySortedPoints, 0, n);
        Arrays.sort(copySortedPoints);
        return copySortedPoints;
    }

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

    // the line segments
    public LineSegment[] segments() {
        int l = numberOfSegments();
        LineSegment[] lineSegmentsRes = new LineSegment[l];
        for (int i = 0; i < l; i++) {
            lineSegmentsRes[i] = lineSegments.get(i);
        }
        return lineSegmentsRes;
    }


    // thanks susutou
    private void checkNull(Point[] points) {
        if (null == points) throw new IllegalArgumentException(
                "in BruteForceCollinear the Point array cannot be null.");
        else {
            for (Point p : points) {
                if (null == p) {
                    throw new IllegalArgumentException(
                            "in BruteCollinearPoints.points one of the points is null.");
                }
            }
        }
    }

    // thanks susutou
    private void checkDuplicates(Point[] points) {
        int n = points.length;
        if (n > 0) {
            Point[] pointsCopy = new Point[n];
            System.arraycopy(points, 0, pointsCopy, 0, n);
            Arrays.sort(pointsCopy);
            // only one pass in this combinatorial search since array is already sorted
            for (int i = 0; i < n - 1; i++)
                //if (pointsCopy[i].compareTo(pointsCopy[i + 1]) == 0)
                if (pointsCopy[i].compareTo(pointsCopy[i + 1]) == 0)
                    throw new IllegalArgumentException(
                            pointsCopy[i + 1] + "is a duplicate point !");
        }
    }
}