package ru.ifmo.nds;

import ru.ifmo.nds.util.ArrayHelper;
import static ru.ifmo.nds.util.DominanceHelper.*;

public class CornerSort {
    private CornerSort() {}

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

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

        @Override
        protected void closeImpl() {
            indices = null;
        }

        private int findBestPoint(double[][] points, int dim, int from, int until, int objective) {
            int best = from;
            double[] bestPoint = points[indices[best]];
            for (int i = from + 1; i < until; ++i) {
                double[] currPoint = points[indices[i]];
                if (bestPoint[objective] > currPoint[objective] ||
                        bestPoint[objective] == currPoint[objective] && strictlyDominates(currPoint, bestPoint, dim)) {
                    bestPoint = currPoint;
                    best = i;
                }
            }
            return best;
        }

        private int moveDominatedToTail(double[][] points, int dim, int index, int until) {
            double[] bestPoint = points[indices[index]];
            ++index;
            while (index < until) {
                if (strictlyDominates(bestPoint, points[indices[index]], dim)) {
                    ArrayHelper.swap(indices, --until, index);
                } else {
                    ++index;
                }
            }
            return until;
        }

        // Note: We have a local "objective" variable.
        // This is not the same as the original version, where "objective" is shared between ranks.
        // However, this does not influence the worst case and shall not influence the average case.

        private int peelCurrentRank(double[][] points, int[] ranks, int dim, int from, int until, int rank) {
            int curr = from;
            int last = until;
            int objective = 0;
            int d = points[0].length;

            while (curr < last) {
                int best = findBestPoint(points, dim, curr, last, objective);
                ArrayHelper.swap(indices, best, curr);
                ranks[indices[curr]] = rank;

                last = moveDominatedToTail(points, dim, curr, last);
                curr = ++from;
                objective = (objective + 1) % d;
            }

            return last;
        }

        private void fillNonMeaningfulRanks(int[] ranks, int from, int until, int maximalMeaningfulRank) {
            for (int i = from; i < until; ++i) {
                ranks[indices[i]] = maximalMeaningfulRank + 1;
            }
        }

        @Override
        protected void sortChecked(double[][] points, int[] ranks, int maximalMeaningfulRank) {
            int n = points.length;
            int dim = points[0].length;
            ArrayHelper.fillIdentity(indices, n);
            int firstNotYetProcessed = 0;
            for (int rank = 0; firstNotYetProcessed < n && rank <= maximalMeaningfulRank; ++rank) {
                firstNotYetProcessed = peelCurrentRank(points, ranks, dim, firstNotYetProcessed, n, rank);
            }
            fillNonMeaningfulRanks(ranks, firstNotYetProcessed, n, maximalMeaningfulRank);
        }
    };

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

@@ -888,20 +888,28 @@
         
-if (
+double bv = 
 bestPoin
@@ -924,10 +924,14 @@
 ive%5D
- %3E
+, cv =
  cur
@@ -951,11 +951,9 @@
 ive%5D
- %7C%7C
+;
 %0A   
@@ -969,60 +969,31 @@
     
-        bestPoint%5Bobjective%5D == currPoint%5Bobjective%5D
+if (bv %3E cv %7C%7C bv == cv
  && 
@@ -1379,32 +1379,73 @@
 ndex %3C until) %7B%0A
+                int ii = indices%5Bindex%5D;%0A
                 
@@ -1485,29 +1485,17 @@
 points%5Bi
-ndices%5Bindex%5D
+i
 %5D, dim))
@@ -1521,49 +1521,119 @@
     
-ArrayHelper.swap(
+int last = 
 indices
-, 
+%5B
 --until
-, index)
+%5D;%0A                    indices%5Buntil%5D = ii;%0A                    indices%5Bindex%5D = last
 ;%0A  
@@ -2213,46 +2213,8 @@
 = 0;
-%0A            int d = points%5B0%5D.length;
 %0A%0A  
@@ -2343,82 +2343,193 @@
     
-ArrayHelper.swap(
+int bestIdx = 
 indices
-, 
+%5B
 best
-, curr);%0A                ranks%5Bindices%5Bcurr%5D
+%5D;%0A                int currIdx = indices%5Bcurr%5D;%0A                indices%5Bbest%5D = currIdx;%0A                indices%5Bcurr%5D = bestIdx;%0A                ranks%5BbestIdx
 %5D = 
@@ -2682,16 +2682,18 @@
 + 1) %25 d
+im
 ;%0A      
@@ -2836,32 +2836,86 @@
 aningfulRank) %7B%0A
+            int nextRank = maximalMeaningfulRank + 1;%0A
             for 
@@ -2987,33 +2987,16 @@
 %5D = 
-maximalMeaningfulRank + 1
+nextRank
 ;%0A  

Add few non-asymptotic improvements to Corner Sort.