Algorithms-I : 3-Collinear: speed and sub segments fixed

2 files changed, 62 insertions, 79 deletions

diff --git a/Algorithms/Part-I/3-Collinear/Fast.java b/Algorithms/Part-I/3-Collinear/Fast.java
index 07130a6..60b0d25 100644
--- a/Algorithms/Part-I/3-Collinear/Fast.java
+++ b/Algorithms/Part-I/3-Collinear/Fast.java
@@ -3,112 +3,100 @@
 import java.util.List;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.HashMap;
+import java.util.HashSet;
 
 public class Fast
 {
-
-    private static class Segment
+    private int N;
+    private Point ref;
+    private Point[] pts;
+    // reused each iteration
+    private Point[] work;
+    private List<Point[]> segments;
+    // for each slope, the last point must be unique,
+    // the longest segment is the first to arise
+    // multiple segment for 1 slope is possible
+    private HashMap<Double, HashSet<Point>> slopes;
+
+    private void addSegment(double sl, int start, int end)
     {
-        private Point[] pts;
-
-        public Segment(Point ref, Point[] origin, int start, int n)
+        // if this solpe is not in the hash yet,
+        // or the last point is not in the set yet
+        HashSet slopePoints = slopes.get(sl);
+        Point last = work[end - 1];
+        if ((slopePoints == null) || !slopePoints.contains(last))
         {
-            this.pts = new Point[n];
-            int i = 0;
-            int j = start;
-            boolean inserted = false;
-            while (i < (n - 1))
+            Point[] segment = new Point[end - start + 1];
+            segment[0] = ref;
+            for (int k = start, l = 1; k < end; k++, l++)
+                segment[l] = work[k];
+            segments.add(segment);
+            if (slopePoints == null)
             {
-                if (!inserted && (ref.compareTo(origin[j]) < 0))
-                {
-                    pts[i++] = ref;
-                    pts[i] = origin[j++];
-                    inserted = true;
-                }
-                else
-                    pts[i] = origin[j++];
-                i++;
+                slopePoints = new  HashSet<Point>();
+                slopePoints.add(last);
+                slopes.put(sl, slopePoints);
+            } else
+            {
+                slopePoints.add(last);
             }
-            if (!inserted)
-                pts[n - 1] = ref;
-            else
-                pts[n - 1] = origin[start + n - 2];
-        }
-
-        public boolean equals(Object other)
-        {
-            if (other == this) return true;
-            if (other == null) return false;
-            if (other.getClass() != this.getClass()) return false;
-            Segment s = (Segment) other;
-            if ((pts[0].compareTo(s.pts[0]) == 0)
-                    || (pts[pts.length - 1].compareTo(s.pts[s.pts.length - 1]) == 0))
-                    return true;
-            return false;
-        }
-
-        public void draw()
-        {
-            pts[0].drawTo(pts[pts.length-1]);
-        }
-
-        public void print()
-        {
-            String out = "";
-            for (Point p : pts)
-                out += p+" -> ";
-            StdOut.println(out.substring(0, (out.length() - 4)));
         }
     }
 
-    private static List<Segment> solve(Point[] pts, int N)
+    private void solve(Point[] origin, int len)
     {
-        List<Segment> segments = new ArrayList<Segment>();
-        for (int i = 0; i < N - 1; i++)
-        {
-            int n = N - i - 1;
-            Point ref = pts[i];
-            Point[] others = new Point[n];
+        this.N = len;
+        this.pts = origin;
+        work = new Point[N - 1];
+        segments = new ArrayList<Point[]>();
+        slopes = new HashMap<Double, HashSet<Point>>();
 
-            for (int j = 0, k = i + 1; j < n; j++, k++)
-                others[j] = pts[k];
+        for (int i = 1, n = N - 1; i < N - 3; i++, n--)
+        {
+            // reference [i-1] and copy [i;N[ to [0;n[
+            ref = pts[i - 1];
+            for (int k = 0, j = i; k < n; k++, j++)
+                work[k] = pts[j];
 
-            Arrays.sort(others, ref.SLOPE_ORDER);
+            // sort [0;n[
+            Arrays.sort(work, 0, n, ref.SLOPE_ORDER);
 
+            // search for sequences >2 in [0;n[
             int start = -1;
             double slope = Double.NEGATIVE_INFINITY;
             for (int j = 0; j < n; j++)
             {
-                double sl = ref.slopeTo(others[j]);
+                double sl = ref.slopeTo(work[j]);
                 if (sl == Double.NEGATIVE_INFINITY)
                     continue;
 
-                if (slope != sl)
+                if (sl != slope)
                 {
                     if ((start != -1) && ((j - start) > 2))
-                    {
-                        Segment seg = new Segment(ref, others,
-                                start, (j - start + 1));
-                        if (!segments.contains(seg))
-                            segments.add(seg);
-                    }
+                        addSegment(slope, start, j);
                     slope = sl;
                     start = j;
                 }
 
             }
             if ((n -  start) > 2)
-            {
-                Segment seg = new Segment(ref, others, start, (n - start + 1));
-                if (!segments.contains(seg))
-                    segments.add(seg);
-            }
+                addSegment(slope, start, n);
+        }
+        for (Point[] seg : segments)
+        {
+            seg[0].drawTo(seg[seg.length-1]);
+            String out = "";
+            for (Point p : seg)
+                out += p+" -> ";
+            StdOut.println(out.substring(0, (out.length() - 4)));
         }
-        return segments;
     }
 
     public static void main(String[] args)
     {
+        // Stopwatch w = new Stopwatch();
+
         In in = new In(args[0]);
         int n = in.readInt();
 
@@ -124,13 +112,7 @@ public class Fast
         }
         Arrays.sort(pts);
 
-        // Stopwatch w = new Stopwatch();
-
-        for (Segment sol : solve(pts, n))
-        {
-            sol.draw();
-            sol.print();
-        }
+        new Fast().solve(pts, n);
 
         // StdOut.printf("Time: %f\n\n", w.elapsedTime());
         StdDraw.show(0);
diff --git a/Algorithms/Part-I/3-Collinear/Point.java b/Algorithms/Part-I/3-Collinear/Point.java
index bd5bbe7..1dddb53 100644
--- a/Algorithms/Part-I/3-Collinear/Point.java
+++ b/Algorithms/Part-I/3-Collinear/Point.java
@@ -67,6 +67,7 @@ public class Point implements Comparable<Point> {
     // is this point lexicographically smaller than that one?
     // comparing y-coordinates and breaking ties by x-coordinates
     public int compareTo(Point that) {
+        if (this == that) return 0;
         if (this.y < that.y) return -1;
         if (this.y > that.y) return  1;
         if (this.x < that.x) return -1;