// 
// Decompiled by Procyon v0.6.0
// 

package it.unimi.dsi.fastutil.objects;

import java.util.concurrent.RecursiveAction;
import java.io.Serializable;
import java.util.Random;
import java.util.Comparator;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.ForkJoinPool;
import java.util.Arrays;
import java.lang.reflect.Array;
import it.unimi.dsi.fastutil.BigArrays;
import it.unimi.dsi.fastutil.Hash;

public final class ObjectBigArrays
{
    public static final Object[][] EMPTY_BIG_ARRAY;
    public static final Object[][] DEFAULT_EMPTY_BIG_ARRAY;
    public static final Hash.Strategy HASH_STRATEGY;
    private static final int QUICKSORT_NO_REC = 7;
    private static final int PARALLEL_QUICKSORT_NO_FORK = 8192;
    private static final int MEDIUM = 40;
    
    private ObjectBigArrays() {
    }
    
    @Deprecated
    public static <K> K get(final K[][] array, final long index) {
        return array[BigArrays.segment(index)][BigArrays.displacement(index)];
    }
    
    @Deprecated
    public static <K> void set(final K[][] array, final long index, final K value) {
        array[BigArrays.segment(index)][BigArrays.displacement(index)] = value;
    }
    
    @Deprecated
    public static <K> void swap(final K[][] array, final long first, final long second) {
        final K t = array[BigArrays.segment(first)][BigArrays.displacement(first)];
        array[BigArrays.segment(first)][BigArrays.displacement(first)] = array[BigArrays.segment(second)][BigArrays.displacement(second)];
        array[BigArrays.segment(second)][BigArrays.displacement(second)] = t;
    }
    
    @Deprecated
    public static <K> long length(final K[][] array) {
        final int length = array.length;
        return (length == 0) ? 0L : (BigArrays.start(length - 1) + array[length - 1].length);
    }
    
    @Deprecated
    public static <K> void copy(final K[][] srcArray, final long srcPos, final K[][] destArray, final long destPos, final long length) {
        BigArrays.copy(srcArray, srcPos, destArray, destPos, length);
    }
    
    @Deprecated
    public static <K> void copyFromBig(final K[][] srcArray, final long srcPos, final K[] destArray, final int destPos, final int length) {
        BigArrays.copyFromBig(srcArray, srcPos, destArray, destPos, length);
    }
    
    @Deprecated
    public static <K> void copyToBig(final K[] srcArray, final int srcPos, final K[][] destArray, final long destPos, final long length) {
        BigArrays.copyToBig(srcArray, srcPos, destArray, destPos, length);
    }
    
    public static <K> K[][] newBigArray(final K[][] prototype, final long length) {
        return (K[][])newBigArray(prototype.getClass().getComponentType(), length);
    }
    
    public static Object[][] newBigArray(final Class<?> componentType, final long length) {
        if (length == 0L && componentType == Object[].class) {
            return ObjectBigArrays.EMPTY_BIG_ARRAY;
        }
        BigArrays.ensureLength(length);
        final int baseLength = (int)(length + 134217727L >>> 27);
        final Object[][] base = (Object[][])Array.newInstance(componentType, baseLength);
        final int residual = (int)(length & 0x7FFFFFFL);
        if (residual != 0) {
            for (int i = 0; i < baseLength - 1; ++i) {
                base[i] = (Object[])Array.newInstance(componentType.getComponentType(), 134217728);
            }
            base[baseLength - 1] = (Object[])Array.newInstance(componentType.getComponentType(), residual);
        }
        else {
            for (int i = 0; i < baseLength; ++i) {
                base[i] = (Object[])Array.newInstance(componentType.getComponentType(), 134217728);
            }
        }
        return base;
    }
    
    public static Object[][] newBigArray(final long length) {
        if (length == 0L) {
            return ObjectBigArrays.EMPTY_BIG_ARRAY;
        }
        BigArrays.ensureLength(length);
        final int baseLength = (int)(length + 134217727L >>> 27);
        final Object[][] base = new Object[baseLength][];
        final int residual = (int)(length & 0x7FFFFFFL);
        if (residual != 0) {
            for (int i = 0; i < baseLength - 1; ++i) {
                base[i] = new Object[134217728];
            }
            base[baseLength - 1] = new Object[residual];
        }
        else {
            for (int i = 0; i < baseLength; ++i) {
                base[i] = new Object[134217728];
            }
        }
        return base;
    }
    
    @Deprecated
    public static <K> K[][] wrap(final K[] array) {
        return BigArrays.wrap(array);
    }
    
    @Deprecated
    public static <K> K[][] ensureCapacity(final K[][] array, final long length) {
        return ensureCapacity(array, length, length(array));
    }
    
    @Deprecated
    public static <K> K[][] forceCapacity(final K[][] array, final long length, final long preserve) {
        return BigArrays.forceCapacity(array, length, preserve);
    }
    
    @Deprecated
    public static <K> K[][] ensureCapacity(final K[][] array, final long length, final long preserve) {
        return (K[][])((length > length(array)) ? forceCapacity((Object[][])array, length, preserve) : array);
    }
    
    @Deprecated
    public static <K> K[][] grow(final K[][] array, final long length) {
        final long oldLength = length(array);
        return (length > oldLength) ? grow(array, length, oldLength) : array;
    }
    
    @Deprecated
    public static <K> K[][] grow(final K[][] array, final long length, final long preserve) {
        final long oldLength = length(array);
        return (K[][])((length > oldLength) ? ensureCapacity((Object[][])array, Math.max(oldLength + (oldLength >> 1), length), preserve) : array);
    }
    
    @Deprecated
    public static <K> K[][] trim(final K[][] array, final long length) {
        return BigArrays.trim(array, length);
    }
    
    @Deprecated
    public static <K> K[][] setLength(final K[][] array, final long length) {
        return BigArrays.setLength(array, length);
    }
    
    @Deprecated
    public static <K> K[][] copy(final K[][] array, final long offset, final long length) {
        return BigArrays.copy(array, offset, length);
    }
    
    @Deprecated
    public static <K> K[][] copy(final K[][] array) {
        return BigArrays.copy(array);
    }
    
    @Deprecated
    public static <K> void fill(final K[][] array, final K value) {
        int i = array.length;
        while (i-- != 0) {
            Arrays.fill(array[i], value);
        }
    }
    
    @Deprecated
    public static <K> void fill(final K[][] array, final long from, final long to, final K value) {
        BigArrays.fill(array, from, to, value);
    }
    
    @Deprecated
    public static <K> boolean equals(final K[][] a1, final K[][] a2) {
        return BigArrays.equals(a1, a2);
    }
    
    @Deprecated
    public static <K> String toString(final K[][] a) {
        return BigArrays.toString(a);
    }
    
    @Deprecated
    public static <K> void ensureFromTo(final K[][] a, final long from, final long to) {
        BigArrays.ensureFromTo(length(a), from, to);
    }
    
    @Deprecated
    public static <K> void ensureOffsetLength(final K[][] a, final long offset, final long length) {
        BigArrays.ensureOffsetLength(length(a), offset, length);
    }
    
    @Deprecated
    public static <K> void ensureSameLength(final K[][] a, final K[][] b) {
        if (length(a) != length(b)) {
            throw new IllegalArgumentException("Array size mismatch: " + length(a) + " != " + length(b));
        }
    }
    
    private static ForkJoinPool getPool() {
        final ForkJoinPool current = ForkJoinTask.getPool();
        return (current == null) ? ForkJoinPool.commonPool() : current;
    }
    
    private static <K> void swap(final K[][] x, long a, long b, final long n) {
        for (int i = 0; i < n; ++i, ++a, ++b) {
            BigArrays.swap(x, a, b);
        }
    }
    
    private static <K> long med3(final K[][] x, final long a, final long b, final long c, final Comparator<K> comp) {
        final int ab = comp.compare(BigArrays.get(x, a), BigArrays.get(x, b));
        final int ac = comp.compare(BigArrays.get(x, a), BigArrays.get(x, c));
        final int bc = comp.compare(BigArrays.get(x, b), BigArrays.get(x, c));
        return (ab < 0) ? ((bc < 0) ? b : ((ac < 0) ? c : a)) : ((bc > 0) ? b : ((ac > 0) ? c : a));
    }
    
    private static <K> void selectionSort(final K[][] a, final long from, final long to, final Comparator<K> comp) {
        for (long i = from; i < to - 1L; ++i) {
            long m = i;
            for (long j = i + 1L; j < to; ++j) {
                if (comp.compare(BigArrays.get(a, j), BigArrays.get(a, m)) < 0) {
                    m = j;
                }
            }
            if (m != i) {
                BigArrays.swap(a, i, m);
            }
        }
    }
    
    public static <K> void quickSort(final K[][] x, final long from, final long to, final Comparator<K> comp) {
        final long len = to - from;
        if (len < 7L) {
            selectionSort(x, from, to, (Comparator<Object>)comp);
            return;
        }
        long m = from + len / 2L;
        if (len > 7L) {
            long l = from;
            long n = to - 1L;
            if (len > 40L) {
                final long s = len / 8L;
                l = med3(x, l, l + s, l + 2L * s, comp);
                m = med3(x, m - s, m, m + s, comp);
                n = med3(x, n - 2L * s, n - s, n, comp);
            }
            m = med3(x, l, m, n, comp);
        }
        final K v = BigArrays.get(x, m);
        long b;
        long a = b = from;
        long d;
        long c = d = to - 1L;
        while (true) {
            int comparison;
            if (b <= c && (comparison = comp.compare(BigArrays.get(x, b), v)) <= 0) {
                if (comparison == 0) {
                    BigArrays.swap(x, a++, b);
                }
                ++b;
            }
            else {
                while (c >= b && (comparison = comp.compare(BigArrays.get(x, c), v)) >= 0) {
                    if (comparison == 0) {
                        BigArrays.swap(x, c, d--);
                    }
                    --c;
                }
                if (b > c) {
                    break;
                }
                BigArrays.swap(x, b++, c--);
            }
        }
        final long n2 = to;
        long s2 = Math.min(a - from, b - a);
        swap(x, from, b - s2, s2);
        s2 = Math.min(d - c, n2 - d - 1L);
        swap(x, b, n2 - s2, s2);
        if ((s2 = b - a) > 1L) {
            quickSort(x, from, from + s2, (Comparator<Object>)comp);
        }
        if ((s2 = d - c) > 1L) {
            quickSort(x, n2 - s2, n2, (Comparator<Object>)comp);
        }
    }
    
    private static <K> long med3(final K[][] x, final long a, final long b, final long c) {
        final int ab = BigArrays.get((Comparable<K>[][])x, a).compareTo(BigArrays.get(x, b));
        final int ac = BigArrays.get((Comparable<K>[][])x, a).compareTo(BigArrays.get(x, c));
        final int bc = BigArrays.get((Comparable<K>[][])x, b).compareTo(BigArrays.get(x, c));
        return (ab < 0) ? ((bc < 0) ? b : ((ac < 0) ? c : a)) : ((bc > 0) ? b : ((ac > 0) ? c : a));
    }
    
    private static <K> void selectionSort(final K[][] a, final long from, final long to) {
        for (long i = from; i < to - 1L; ++i) {
            long m = i;
            for (long j = i + 1L; j < to; ++j) {
                if (BigArrays.get((Comparable<K>[][])a, j).compareTo(BigArrays.get(a, m)) < 0) {
                    m = j;
                }
            }
            if (m != i) {
                BigArrays.swap(a, i, m);
            }
        }
    }
    
    public static <K> void quickSort(final K[][] x, final Comparator<K> comp) {
        quickSort(x, 0L, BigArrays.length(x), comp);
    }
    
    public static <K> void quickSort(final K[][] x, final long from, final long to) {
        final long len = to - from;
        if (len < 7L) {
            selectionSort((Object[][])x, from, to);
            return;
        }
        long m = from + len / 2L;
        if (len > 7L) {
            long l = from;
            long n = to - 1L;
            if (len > 40L) {
                final long s = len / 8L;
                l = med3(x, l, l + s, l + 2L * s);
                m = med3(x, m - s, m, m + s);
                n = med3(x, n - 2L * s, n - s, n);
            }
            m = med3(x, l, m, n);
        }
        final K v = BigArrays.get(x, m);
        long b;
        long a = b = from;
        long d;
        long c = d = to - 1L;
        while (true) {
            int comparison;
            if (b <= c && (comparison = BigArrays.get((Comparable<K>[][])x, b).compareTo(v)) <= 0) {
                if (comparison == 0) {
                    BigArrays.swap(x, a++, b);
                }
                ++b;
            }
            else {
                while (c >= b && (comparison = BigArrays.get((Comparable<K>[][])x, c).compareTo(v)) >= 0) {
                    if (comparison == 0) {
                        BigArrays.swap(x, c, d--);
                    }
                    --c;
                }
                if (b > c) {
                    break;
                }
                BigArrays.swap(x, b++, c--);
            }
        }
        final long n2 = to;
        long s2 = Math.min(a - from, b - a);
        swap(x, from, b - s2, s2);
        s2 = Math.min(d - c, n2 - d - 1L);
        swap(x, b, n2 - s2, s2);
        if ((s2 = b - a) > 1L) {
            quickSort((Object[][])x, from, from + s2);
        }
        if ((s2 = d - c) > 1L) {
            quickSort((Object[][])x, n2 - s2, n2);
        }
    }
    
    public static <K> void quickSort(final K[][] x) {
        quickSort(x, 0L, BigArrays.length(x));
    }
    
    public static <K> void parallelQuickSort(final K[][] x, final long from, final long to) {
        final ForkJoinPool pool = getPool();
        if (to - from < 8192L || pool.getParallelism() == 1) {
            quickSort((Object[][])x, from, to);
        }
        else {
            pool.invoke(new ForkJoinQuickSort(x, from, to));
        }
    }
    
    public static <K> void parallelQuickSort(final K[][] x) {
        parallelQuickSort(x, 0L, BigArrays.length(x));
    }
    
    public static <K> void parallelQuickSort(final K[][] x, final long from, final long to, final Comparator<K> comp) {
        final ForkJoinPool pool = getPool();
        if (to - from < 8192L || pool.getParallelism() == 1) {
            quickSort(x, from, to, (Comparator<Object>)comp);
        }
        else {
            pool.invoke(new ForkJoinQuickSortComp(x, from, to, (Comparator<Object>)comp));
        }
    }
    
    public static <K> void parallelQuickSort(final K[][] x, final Comparator<K> comp) {
        parallelQuickSort(x, 0L, BigArrays.length(x), comp);
    }
    
    public static <K> long binarySearch(final K[][] a, long from, long to, final K key) {
        --to;
        while (from <= to) {
            final long mid = from + to >>> 1;
            final K midVal = BigArrays.get(a, mid);
            final int cmp = ((Comparable)midVal).compareTo(key);
            if (cmp < 0) {
                from = mid + 1L;
            }
            else {
                if (cmp <= 0) {
                    return mid;
                }
                to = mid - 1L;
            }
        }
        return -(from + 1L);
    }
    
    public static <K> long binarySearch(final K[][] a, final Object key) {
        return binarySearch(a, 0L, BigArrays.length(a), key);
    }
    
    public static <K> long binarySearch(final K[][] a, long from, long to, final K key, final Comparator<K> c) {
        --to;
        while (from <= to) {
            final long mid = from + to >>> 1;
            final K midVal = BigArrays.get(a, mid);
            final int cmp = c.compare(midVal, key);
            if (cmp < 0) {
                from = mid + 1L;
            }
            else {
                if (cmp <= 0) {
                    return mid;
                }
                to = mid - 1L;
            }
        }
        return -(from + 1L);
    }
    
    public static <K> long binarySearch(final K[][] a, final K key, final Comparator<K> c) {
        return binarySearch(a, 0L, BigArrays.length(a), key, c);
    }
    
    public static <K> K[][] shuffle(final K[][] a, final long from, final long to, final Random random) {
        return BigArrays.shuffle(a, from, to, random);
    }
    
    public static <K> K[][] shuffle(final K[][] a, final Random random) {
        return BigArrays.shuffle(a, random);
    }
    
    static {
        EMPTY_BIG_ARRAY = new Object[0][];
        DEFAULT_EMPTY_BIG_ARRAY = new Object[0][];
        HASH_STRATEGY = new BigArrayHashStrategy();
    }
    
    private static final class BigArrayHashStrategy<K> implements Hash.Strategy<K[][]>, Serializable
    {
        private static final long serialVersionUID = -7046029254386353129L;
        
        @Override
        public int hashCode(final K[][] o) {
            return Arrays.deepHashCode(o);
        }
        
        @Override
        public boolean equals(final K[][] a, final K[][] b) {
            return ObjectBigArrays.equals(a, b);
        }
    }
    
    protected static class ForkJoinQuickSort<K> extends RecursiveAction
    {
        private static final long serialVersionUID = 1L;
        private final long from;
        private final long to;
        private final K[][] x;
        
        public ForkJoinQuickSort(final K[][] x, final long from, final long to) {
            this.from = from;
            this.to = to;
            this.x = x;
        }
        
        @Override
        protected void compute() {
            final K[][] x = this.x;
            final long len = this.to - this.from;
            if (len < 8192L) {
                ObjectBigArrays.quickSort(x, this.from, this.to);
                return;
            }
            long m = this.from + len / 2L;
            long l = this.from;
            long n = this.to - 1L;
            long s = len / 8L;
            l = med3(x, l, l + s, l + 2L * s);
            m = med3(x, m - s, m, m + s);
            n = med3(x, n - 2L * s, n - s, n);
            m = med3(x, l, m, n);
            final K v = BigArrays.get(x, m);
            long b;
            long a = b = this.from;
            long d;
            long c = d = this.to - 1L;
            while (true) {
                int comparison;
                if (b <= c && (comparison = BigArrays.get((Comparable<K>[][])x, b).compareTo(v)) <= 0) {
                    if (comparison == 0) {
                        BigArrays.swap(x, a++, b);
                    }
                    ++b;
                }
                else {
                    while (c >= b && (comparison = BigArrays.get((Comparable<K>[][])x, c).compareTo(v)) >= 0) {
                        if (comparison == 0) {
                            BigArrays.swap(x, c, d--);
                        }
                        --c;
                    }
                    if (b > c) {
                        break;
                    }
                    BigArrays.swap(x, b++, c--);
                }
            }
            s = Math.min(a - this.from, b - a);
            swap(x, this.from, b - s, s);
            s = Math.min(d - c, this.to - d - 1L);
            swap(x, b, this.to - s, s);
            s = b - a;
            final long t = d - c;
            if (s > 1L && t > 1L) {
                ForkJoinTask.invokeAll(new ForkJoinQuickSort<Object>((Object[][])x, this.from, this.from + s), new ForkJoinQuickSort<Object>((Object[][])x, this.to - t, this.to));
            }
            else if (s > 1L) {
                ForkJoinTask.invokeAll(new ForkJoinQuickSort(x, this.from, this.from + s));
            }
            else {
                ForkJoinTask.invokeAll(new ForkJoinQuickSort(x, this.to - t, this.to));
            }
        }
    }
    
    protected static class ForkJoinQuickSortComp<K> extends RecursiveAction
    {
        private static final long serialVersionUID = 1L;
        private final long from;
        private final long to;
        private final K[][] x;
        private final Comparator<K> comp;
        
        public ForkJoinQuickSortComp(final K[][] x, final long from, final long to, final Comparator<K> comp) {
            this.from = from;
            this.to = to;
            this.x = x;
            this.comp = comp;
        }
        
        @Override
        protected void compute() {
            final K[][] x = this.x;
            final long len = this.to - this.from;
            if (len < 8192L) {
                ObjectBigArrays.quickSort(x, this.from, this.to, this.comp);
                return;
            }
            long m = this.from + len / 2L;
            long l = this.from;
            long n = this.to - 1L;
            long s = len / 8L;
            l = med3(x, l, l + s, l + 2L * s, this.comp);
            m = med3(x, m - s, m, m + s, this.comp);
            n = med3(x, n - 2L * s, n - s, n, this.comp);
            m = med3(x, l, m, n, this.comp);
            final K v = BigArrays.get(x, m);
            long b;
            long a = b = this.from;
            long d;
            long c = d = this.to - 1L;
            while (true) {
                int comparison;
                if (b <= c && (comparison = this.comp.compare(BigArrays.get(x, b), v)) <= 0) {
                    if (comparison == 0) {
                        BigArrays.swap(x, a++, b);
                    }
                    ++b;
                }
                else {
                    while (c >= b && (comparison = this.comp.compare(BigArrays.get(x, c), v)) >= 0) {
                        if (comparison == 0) {
                            BigArrays.swap(x, c, d--);
                        }
                        --c;
                    }
                    if (b > c) {
                        break;
                    }
                    BigArrays.swap(x, b++, c--);
                }
            }
            s = Math.min(a - this.from, b - a);
            swap(x, this.from, b - s, s);
            s = Math.min(d - c, this.to - d - 1L);
            swap(x, b, this.to - s, s);
            s = b - a;
            final long t = d - c;
            if (s > 1L && t > 1L) {
                ForkJoinTask.invokeAll(new ForkJoinQuickSortComp<Object>((Object[][])x, this.from, this.from + s, (Comparator<?>)this.comp), new ForkJoinQuickSortComp<Object>((Object[][])x, this.to - t, this.to, (Comparator<?>)this.comp));
            }
            else if (s > 1L) {
                ForkJoinTask.invokeAll(new ForkJoinQuickSortComp(x, this.from, this.from + s, this.comp));
            }
            else {
                ForkJoinTask.invokeAll(new ForkJoinQuickSortComp(x, this.to - t, this.to, this.comp));
            }
        }
    }
}