package ru.ifmo.nds.util;

import java.util.concurrent.ThreadLocalRandom;

public final class ArrayHelper {
    private ArrayHelper() {}

    public static void swap(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    public static void swap(double[] array, int a, int b) {
        double tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    public static boolean equal(double[] a, double[] b) {
        int al = a.length;
        if (al != b.length) {
            return false;
        }
        for (int i = 0; i < al; ++i) {
            if (a[i] != b[i]) {
                return false;
            }
        }
        return true;
    }

    public static void fillIdentity(int[] array, int n) {
        for (int i = 0; i < n; ++i) {
            array[i] = i;
        }
    }

    public static double destructiveMedian(double[] array, int from, int until) {
        ThreadLocalRandom random = ThreadLocalRandom.current();
        int count = 0;
        int index = (from + until) >>> 1;
        while (from + 1 < until) {
            double pivot = array[++count > 20 ? random.nextInt(from, until) : (from + until) >>> 1];
            int pivotFirst = from, greaterFirst = until - 1;
            for (int i = from; i <= greaterFirst; ++i) {
                double value = array[i];
                if (value == pivot) {
                    continue;
                }
                if (value < pivot) {
                    array[i] = array[pivotFirst];
                    array[pivotFirst++] = value;
                } else {
                    double notGreater = array[greaterFirst];
                    while (notGreater > pivot) {
                        notGreater = array[--greaterFirst];
                    }
                    if (notGreater == pivot) {
                        array[i] = notGreater;
                    } else {
                        array[i] = array[pivotFirst];
                        array[pivotFirst++] = notGreater;
                    }
                    array[greaterFirst--] = value;
                }
            }
            --pivotFirst;
            ++greaterFirst;
            if (index <= pivotFirst) {
                until = pivotFirst + 1;
            } else if (index >= greaterFirst) {
                from = greaterFirst;
            } else {
                break;
            }
        }
        return array[index];
    }

    public static int transplant(double[] source, int[] indices, int fromIndex, int untilIndex, double[] target, int targetFrom) {
        for (int i = fromIndex; i < untilIndex; ++i) {
            target[targetFrom++] = source[indices[i]];
        }
        return targetFrom;
    }

    public static double max(double[] array, int from, int until) {
        if (from >= until) {
            return Double.NEGATIVE_INFINITY;
        } else {
            double rv = array[from];
            for (int i = from + 1; i < until; ++i) {
                double v = array[i];
                if (rv < v) {
                    rv = v;
                }
            }
            return rv;
        }
    }

    public static double min(double[] array, int from, int until) {
        if (from >= until) {
            return Double.POSITIVE_INFINITY;
        } else {
            double rv = array[from];
            for (int i = from + 1; i < until; ++i) {
                double v = array[i];
                if (rv > v) {
                    rv = v;
                }
            }
            return rv;
        }
    }
}

@@ -1163,9 +1163,9 @@
 t %3E 
-2
+3
 0 ? 
@@ -1237,633 +1237,180 @@
 int 
-pivotFirst = from, greaterFirst = until - 1;%0A            for (int i = from; i %3C= greaterFirst; ++i) %7B%0A                double value = array%5Bi%5D;%0A                if (value == pivot) %7B%0A                    continue;%0A                %7D%0A                if (value %3C pivot) %7B%0A                    
+l = from, r = until - 1;%0A            while (l %3C= r) %7B%0A                while (
 array%5B
-i%5D = array%5BpivotFirst%5D;%0A                    array%5BpivotFirst++%5D = value;%0A                %7D else %7B%0A                    double notGreater = array%5BgreaterFirst%5D;%0A                    while (notGreater %3E pivot) %7B%0A                        notGreater = array%5B--greaterFirst%5D;%0A                    %7D%0A                    if (notGreater == pivot
+l%5D %3C pivot) ++l;%0A                while (array%5Br%5D %3E pivot) --r;%0A                if (l %3C= r
 ) %7B%0A
@@ -1433,334 +1433,62 @@
     
-    array%5Bi%5D = notGreater;%0A                    %7D else %7B%0A                        array%5Bi%5D = array%5BpivotFirst%5D;%0A                        array%5BpivotFirst++%5D = notGreater;%0A                    %7D%0A                    array%5BgreaterFirst--%5D = value;%0A                %7D%0A            %7D%0A            --pivotFirst;%0A            ++greaterFirst;
+swap(array, l++, r--);%0A                %7D%0A            %7D
 %0A   
@@ -1509,26 +1509,17 @@
 ndex %3C= 
-pivotFirst
+r
 ) %7B%0A    
@@ -1542,18 +1542,9 @@
 l = 
-pivotFirst
+r
  + 1
@@ -1572,29 +1572,18 @@
 if (
+l %3C= 
 index
- %3E= greaterFirst
 ) %7B%0A
@@ -1609,20 +1609,9 @@
 m = 
-greaterFirst
+l
 ;%0A  

Revert destructiveMedian to its previous implementation.