package ru.ifmo.nds.util;

import java.util.concurrent.ThreadLocalRandom;

public final class DoubleArraySorter {
    private final double[] scratch;
    private final ThreadLocalRandom random = ThreadLocalRandom.current();

    private double[][] points = null;
    private int[] indices = null;
    private int coordinate = -1;
    private int maxCoordinate = -1;
    private int[] resolver = null;

    public DoubleArraySorter(int maximumPoints) {
        this.scratch = new double[maximumPoints];
    }

    private void sortImplInside(int from, int until) {
        double pivot = scratch[random.nextInt(from, until)];
        int l = from, r = until - 1;
        while (l <= r) {
            while (scratch[l] < pivot) ++l;
            while (scratch[r] > pivot) --r;
            if (l <= r) {
                ArrayHelper.swap(indices, l, r);
                ArrayHelper.swap(scratch, l++, r--);
            }
        }
        if (from + 1 <= r) sortImplInside(from, r + 1);
        if (l + 1 < until) sortImplInside(l, until);
    }

    private void sortImpl(int from, int until) {
        for (int i = from; i < until; ++i) {
            scratch[i] = points[indices[i]][coordinate];
        }
        sortImplInside(from, until);
    }

    private void lexSortImpl(int from, int until, int coordinate) {
        this.coordinate = coordinate;
        sortImpl(from, until);

        int last = from;
        double lastX = scratch[from];
        for (int i = from + 1; i < until; ++i) {
            double currX = scratch[i];
            if (currX != lastX) {
                if (last + 1 < i && coordinate + 1 < maxCoordinate) {
                    lexSortImpl(last, i, coordinate + 1);
                }
                last = i;
                lastX = currX;
            }
        }
        if (last + 1 < until && coordinate + 1 < maxCoordinate) {
            lexSortImpl(last, until, coordinate + 1);
        }
    }

    public void sort(double[][] points, int[] indices, int from, int until, int whichCoordinate) {
        if (until - from > scratch.length) {
            throw new IllegalArgumentException("The maximum array length to be sorted is " + scratch.length
                    + ", but you requested from = " + from + " until = " + until + " which is " + (until - from));
        }
        this.points = points;
        this.indices = indices;
        this.coordinate = whichCoordinate;

        sortImpl(from, until);

        this.points = null;
        this.indices = null;
        this.coordinate = -1;
    }

    public void lexicographicalSort(double[][] points, int[] indices, int from, int until, int maxCoordinate) {
        if (until - from > scratch.length) {
            throw new IllegalArgumentException("The maximum array length to be sorted is " + scratch.length
                    + ", but you requested from = " + from + " until = " + until + " which is " + (until - from));
        }
        this.points = points;
        this.indices = indices;
        this.maxCoordinate = maxCoordinate;

        lexSortImpl(from, until, 0);

        this.points = null;
        this.indices = null;
        this.maxCoordinate = -1;
    }

    private void sortByResolver(int from, int until) {
        int pivot = resolver[indices[random.nextInt(from, until)]];
        int l = from, r = until - 1;
        while (l <= r) {
            while (resolver[indices[l]] < pivot) ++l;
            while (resolver[indices[r]] > pivot) --r;
            if (l <= r) {
                ArrayHelper.swap(indices, l++, r--);
            }
        }
        if (from + 1 <= r) sortByResolver(from, r + 1);
        if (l + 1 < until) sortByResolver(l, until);
    }

    private void sortWhileResolvingEqualImpl(int from, int until) {
        sortImpl(from, until);

        int last = from;
        double lastX = points[indices[from]][coordinate];
        for (int i = from + 1; i < until; ++i) {
            double currX = points[indices[i]][coordinate];
            if (currX != lastX) {
                if (last + 1 < i) {
                    sortByResolver(last, i);
                }
                last = i;
                lastX = currX;
            }
        }
        if (last + 1 < until) {
            sortByResolver(last, until);
        }
    }

    public void sortWhileResolvingEqual(double[][] points, int[] indices, int from, int until, int coordinate, int[] resolver) {
        if (until - from > scratch.length) {
            throw new IllegalArgumentException("The maximum array length to be sorted is " + scratch.length
                    + ", but you requested from = " + from + " until = " + until + " which is " + (until - from));
        }
        this.points = points;
        this.indices = indices;
        this.coordinate = coordinate;
        this.resolver = resolver;

        sortWhileResolvingEqualImpl(from, until);

        this.points = null;
        this.indices = null;
        this.coordinate = -1;
        this.resolver = null;
    }

    public static int retainUniquePoints(double[][] sourcePoints, int[] sortedIndices, double[][] targetPoints, int[] reindex) {
        int n = sourcePoints.length, newN = 1;
        int lastII = sortedIndices[0];
        targetPoints[0] = sourcePoints[lastII];
        reindex[lastII] = 0;
        for (int i = 1; i < n; ++i) {
            int currII = sortedIndices[i];
            if (!ArrayHelper.equal(sourcePoints[lastII], sourcePoints[currII])) {
                // Copying the point to the internal array.
                targetPoints[newN] = sourcePoints[currII];
                lastII = currII;
                ++newN;
            }
            reindex[currII] = newN - 1;
        }
        return newN;
    }
}

@@ -1371,32 +1371,82 @@
 (from, until);%0A%0A
+        if (coordinate + 1 %3C maxCoordinate) %7B%0A    
         int last
@@ -1446,32 +1446,36 @@
 nt last = from;%0A
+    
         double l
@@ -1496,32 +1496,36 @@
 %5Bfrom%5D;%0A        
+   
+ 
 for (int i = fro
@@ -1553,32 +1553,36 @@
 ) %7B%0A            
+    
 double currX = s
@@ -1596,32 +1596,36 @@
 i%5D;%0A            
+ 
+   
 if (currX != las
@@ -1638,32 +1638,36 @@
                 
+  
+  
 if (last + 1 %3C i
@@ -1670,46 +1670,16 @@
  %3C i
- && coordinate + 1 %3C maxCoordinate
 ) %7B%0A
+    
     
@@ -1740,34 +1740,41 @@
                 
-%7D%0A
+    %7D%0A   
                 
@@ -1765,32 +1765,33 @@
                 
+ 
 last = i;%0A      
@@ -1776,32 +1776,36 @@
       last = i;%0A
+    
                 
@@ -1827,36 +1827,48 @@
             
-%7D%0A    
     %7D%0A
+            %7D%0A    
         if (
@@ -1887,46 +1887,16 @@
 ntil
- && coordinate + 1 %3C maxCoordinate
 ) %7B%0A
+    
     
@@ -1937,32 +1937,46 @@
 oordinate + 1);%0A
+            %7D%0A
         %7D%0A    %7D%0A

Move guard outside the loop in DAS.lexSortImpl. Rename