package ru.ifmo.nds.fnds;

import ru.ifmo.nds.NonDominatedSorting;
import ru.ifmo.nds.util.ArrayHelper;
import ru.ifmo.nds.util.DoubleArraySorter;

public class LinearMemory extends NonDominatedSorting {
    private int[] ranks;
    private double[][] points;

    public LinearMemory(int maximumPoints, int maximumDimension) {
        super(maximumPoints, maximumDimension);
        ranks = new int[maximumPoints];
        points = new double[maximumPoints][];
    }

    @Override
    public String getName() {
        return "Fast Non-Dominated Sorting (with linear memory)";
    }

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

    private boolean strictlyDominatesAssumingNotSame(int goodIndex, int weakIndex, int dim) {
        double[] goodPoint = points[goodIndex];
        double[] weakPoint = points[weakIndex];
        // Comparison in 0 makes no sense, as due to goodIndex < weakIndex the points are <= in this coordinate.
        for (int i = dim - 1; i > 0; --i) {
            if (goodPoint[i] > weakPoint[i]) {
                return false;
            }
        }
        return true;
    }

    private void doSorting(int n, int dim, int maximalMeaningfulRank) {
        ranks[0] = 0;
        for (int i = 1; i < n; ++i) {
            int myRank = 0;
            for (int j = i - 1; myRank <= maximalMeaningfulRank && j >= 0; --j) {
                int thatRank = ranks[j];
                if (myRank <= thatRank && strictlyDominatesAssumingNotSame(j, i, dim)) {
                    myRank = thatRank + 1;
                }
            }
            ranks[i] = myRank;
        }
    }

    @Override
    protected void sortChecked(double[][] points, int[] ranks, int maximalMeaningfulRank) {
        int n = points.length;
        int dim = points[0].length;
        ArrayHelper.fillIdentity(indices, n);
        sorter.lexicographicalSort(points, indices, 0, n, dim);
        int newN = DoubleArraySorter.retainUniquePoints(points, indices, this.points, ranks);
        doSorting(newN, dim, maximalMeaningfulRank);
        for (int i = 0; i < n; ++i) {
            ranks[i] = this.ranks[ranks[i]];
            this.points[i] = null;
        }
    }
}

@@ -97,16 +97,57 @@
 Helper;%0A
+import ru.ifmo.nds.util.DominanceHelper;%0A
 import r
@@ -723,484 +723,8 @@
  %7D%0A%0A
-    private boolean strictlyDominatesAssumingNotSame(int goodIndex, int weakIndex, int dim) %7B%0A        double%5B%5D goodPoint = points%5BgoodIndex%5D;%0A        double%5B%5D weakPoint = points%5BweakIndex%5D;%0A        // Comparison in 0 makes no sense, as due to goodIndex %3C weakIndex the points are %3C= in this coordinate.%0A        for (int i = dim - 1; i %3E 0; --i) %7B%0A            if (goodPoint%5Bi%5D %3E weakPoint%5Bi%5D) %7B%0A                return false;%0A            %7D%0A        %7D%0A        return true;%0A    %7D%0A%0A
     
@@ -809,24 +809,54 @@
 nks%5B0%5D = 0;%0A
+        int maxObj = dim - 1;%0A
         for 
@@ -925,62 +925,64 @@
     
-for (int j = i - 1; myRank %3C= maximalMeaningfulRank &&
+double%5B%5D pi = points%5Bi%5D;%0A            for (int j = i - 1;
  j %3E
@@ -1076,16 +1076,32 @@
 Rank && 
+DominanceHelper.
 strictly
@@ -1129,17 +1129,29 @@
 ame(
-j
+points%5Bj%5D
 , 
+p
 i, 
-dim
+maxObj
 )) %7B
@@ -1190,24 +1190,135 @@
 atRank + 1;%0A
+                    if (myRank %3E maximalMeaningfulRank) %7B%0A                        break;%0A                    %7D%0A
             

Update LinearMemory to use DominanceHelper.