refactored bruteforce into a queue based solution and made it work for sPair aswell

1 files changed, 23 insertions, 31 deletions

diff --git a/src/ClosestPair/ClosestPair.cs b/src/ClosestPair/ClosestPair.cs
index e98f91d..2238275 100644
--- a/src/ClosestPair/ClosestPair.cs
+++ b/src/ClosestPair/ClosestPair.cs
@@ -68,16 +68,7 @@ namespace ClosestPair
             if (S.SortedByY.Length < 2)
                 return qPair.Distance < rPair.Distance ? qPair : rPair;
 
-            PointPair sPair = new PointPair(S.SortedByY[0], S.SortedByY[1]);
-            double min = double.MaxValue;
-            for (int i = 0; i < S.SortedByY.Length; i++)
-                for (int j = i + 1; j < S.SortedByY.Length && j <= i + 7; j++)
-                    if (S.SortedByY[i].DistanceTo(S.SortedByY[j]) < min)
-                    {
-                        min = S.SortedByY[i].DistanceTo(S.SortedByY[j]);
-                        sPair = new PointPair(S.SortedByY[i], S.SortedByY[j]);
-                    }
-
+            PointPair sPair = BruteForce(S.SortedByY, 7);
 
             if (sPair.Distance < delta)
                 return sPair;
@@ -94,31 +85,32 @@ namespace ClosestPair
             //         return (Point r0, Point r1)
         }
 
-        static PointPair BruteForce(Point[] P)
+        static PointPair BruteForce(Point[] points) 
+            => BruteForce(points, points.Length);
+
+        static PointPair BruteForce(Point[] points, int queueSize)
         {
-            double min = double.MaxValue;
-            PointPair pair = new PointPair(P[0], P[1]);
-
-            for (int i = 0; i < P.Length; i++)
-                for (int j = i + 1; j < P.Length; j++)
-                    if (P[i].DistanceTo(P[j]) < min)
-                    {
-                        min = P[i].DistanceTo(P[j]);
-                        pair = new PointPair(P[i], P[j]);
-                    }
-            return pair;
+            PointPair closestPair = new(new Point(0, 0), new Point(int.MaxValue, int.MaxValue));
+            Queue<Point> pointQueue = new();
+
+            foreach (Point point in points)
+            {
+                pointQueue.Enqueue(point);
+
+                if (pointQueue.Count < queueSize)
+                    continue;
+
+                Point current = pointQueue.Dequeue();
+
+                foreach (Point next in pointQueue)
+                    if (current.DistanceTo(next) < closestPair.Distance)
+                        closestPair = new(current, next);
+            }
+
+            return closestPair;
         }
 
-        // public void Split<T>(T[] array, int index, out T[] first, out T[] second)
-        // {
-        //     first = array.Take(index).ToArray();
-        //     second = array.Skip(index).ToArray();
-        // }
 
-        // public void SplitMidPoint<T>(T[] array, out T[] first, out T[] second)
-        // {
-        //     Split(array, array.Length / 2, out first, out second);
-        // }
     }
 }