package ru.ifmo;

public class DeductiveSort {
    private static final NonDominatedSortingFactory INSTANCE = (maximumPoints, maximumDimension) ->
            new NonDominatedSorting(maximumPoints, maximumDimension) {
        private int[] indices = new int[maximumPoints];
        private boolean[] dominated = new boolean[maximumPoints];

        @Override
        public String getName() {
            return "Deductive Sort";
        }

        @Override
        protected void closeImpl() throws Exception {
            indices = new int[maximumPoints];
            dominated = new boolean[maximumDimension];
        }

        private int compare(double[] a, double[] b) {
            int d = a.length;
            boolean hasLess = false, hasGreater = false;
            for (int i = 0; i < d; ++i) {
                hasLess |= a[i] < b[i];
                hasGreater |= a[i] > b[i];
                if (hasLess && hasGreater) {
                    return 0;
                }
            }
            return hasLess ? -1 : hasGreater ? 1 : 0;
        }

        @Override
        protected void sortChecked(double[][] points, int[] ranks, int maximalMeaningfulRank) {
            int n = points.length;
            for (int i = 0; i < n; ++i) {
                indices[i] = i;
                dominated[i] = false;
            }
            int from = 0;
            for (int rank = 0; from < n; ++rank) {
                for (int i = from; i < n; ++i) {
                    dominated[indices[i]] = false;
                }
                int curr = from;
                int last = n;
                while (curr < last) {
                    int currI = indices[curr];
                    if (dominated[currI]) {
                        throw new AssertionError();
                    }
                    double[] currP = points[currI];
                    int next = curr + 1;
                    while (next < last) {
                        int nextI = indices[next];
                        if (dominated[nextI]) {
                            throw new AssertionError();
                        }
                        double[] nextP = points[nextI];
                        int comparison = compare(currP, nextP);
                        if (comparison < 0) {
                            dominated[nextI] = true;
                            int tmp = indices[--last];
                            indices[last] = indices[next];
                            indices[next] = tmp;
                        } else if (comparison > 0) {
                            dominated[currI] = true;
                            int tmp = indices[--last];
                            indices[last] = indices[curr];
                            indices[curr] = tmp;
                            break;
                        } else {
                            ++next;
                        }
                    }
                    if (!dominated[currI]) {
                        ranks[currI] = rank;
                        ++curr;
                    }
                }
                from = last;
            }
        }
    };

    public static NonDominatedSortingFactory getInstance() {
        return INSTANCE;
    }
}

@@ -270,74 +270,8 @@
 ts%5D;
-%0A        private boolean%5B%5D dominated = new boolean%5BmaximumPoints%5D;
 %0A%0A  
@@ -467,84 +467,11 @@
  = n
-ew int%5BmaximumPoints%5D;%0A            dominated = new boolean%5BmaximumDimension%5D
+ull
 ;%0A  
@@ -1144,46 +1144,8 @@
  i;%0A
-                dominated%5Bi%5D = false;%0A
     
@@ -1235,126 +1235,8 @@
 ) %7B%0A
-                for (int i = from; i %3C n; ++i) %7B%0A                    dominated%5Bindices%5Bi%5D%5D = false;%0A                %7D%0A
     
@@ -1383,126 +1383,8 @@
 r%5D;%0A
-                    if (dominated%5BcurrI%5D) %7B%0A                        throw new AssertionError();%0A                    %7D%0A
     
@@ -1472,16 +1472,70 @@
 rr + 1;%0A
+                    boolean currentDominated = false;%0A
         
@@ -1623,138 +1623,8 @@
 t%5D;%0A
-                        if (dominated%5BnextI%5D) %7B%0A                            throw new AssertionError();%0A                        %7D%0A
     
@@ -1789,61 +1789,8 @@
 ) %7B%0A
-                            dominated%5BnextI%5D = true;%0A
     
@@ -2029,25 +2029,32 @@
         
-d
+currentD
 ominated
 %5BcurrI%5D 
@@ -2045,23 +2045,16 @@
 ominated
-%5BcurrI%5D
  = true;
@@ -2398,17 +2398,24 @@
 f (!
-d
+currentD
 ominated
 %5Bcur
@@ -2410,23 +2410,16 @@
 ominated
-%5BcurrI%5D
 ) %7B%0A    

Improve Deductive Sort a little bit.