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

package it.unimi.dsi.fastutil.booleans;

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

public final class BooleanBigArrays
{
    public static final boolean[][] EMPTY_BIG_ARRAY;
    public static final boolean[][] 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 BooleanBigArrays() {
    }
    
    @Deprecated
    public static boolean get(final boolean[][] array, final long index) {
        return array[BigArrays.segment(index)][BigArrays.displacement(index)];
    }
    
    @Deprecated
    public static void set(final boolean[][] array, final long index, final boolean value) {
        array[BigArrays.segment(index)][BigArrays.displacement(index)] = value;
    }
    
    @Deprecated
    public static void swap(final boolean[][] array, final long first, final long second) {
        final boolean 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 long length(final boolean[][] array) {
        final int length = array.length;
        return (length == 0) ? 0L : (BigArrays.start(length - 1) + array[length - 1].length);
    }
    
    @Deprecated
    public static void copy(final boolean[][] srcArray, final long srcPos, final boolean[][] destArray, final long destPos, final long length) {
        BigArrays.copy(srcArray, srcPos, destArray, destPos, length);
    }
    
    @Deprecated
    public static void copyFromBig(final boolean[][] srcArray, final long srcPos, final boolean[] destArray, final int destPos, final int length) {
        BigArrays.copyFromBig(srcArray, srcPos, destArray, destPos, length);
    }
    
    @Deprecated
    public static void copyToBig(final boolean[] srcArray, final int srcPos, final boolean[][] destArray, final long destPos, final long length) {
        BigArrays.copyToBig(srcArray, srcPos, destArray, destPos, length);
    }
    
    public static boolean[][] newBigArray(final long length) {
        if (length == 0L) {
            return BooleanBigArrays.EMPTY_BIG_ARRAY;
        }
        BigArrays.ensureLength(length);
        final int baseLength = (int)(length + 134217727L >>> 27);
        final boolean[][] base = new boolean[baseLength][];
        final int residual = (int)(length & 0x7FFFFFFL);
        if (residual != 0) {
            for (int i = 0; i < baseLength - 1; ++i) {
                base[i] = new boolean[134217728];
            }
            base[baseLength - 1] = new boolean[residual];
        }
        else {
            for (int i = 0; i < baseLength; ++i) {
                base[i] = new boolean[134217728];
            }
        }
        return base;
    }
    
    @Deprecated
    public static boolean[][] wrap(final boolean[] array) {
        return BigArrays.wrap(array);
    }
    
    @Deprecated
    public static boolean[][] ensureCapacity(final boolean[][] array, final long length) {
        return ensureCapacity(array, length, length(array));
    }
    
    @Deprecated
    public static boolean[][] forceCapacity(final boolean[][] array, final long length, final long preserve) {
        return BigArrays.forceCapacity(array, length, preserve);
    }
    
    @Deprecated
    public static boolean[][] ensureCapacity(final boolean[][] array, final long length, final long preserve) {
        return (length > length(array)) ? forceCapacity(array, length, preserve) : array;
    }
    
    @Deprecated
    public static boolean[][] grow(final boolean[][] array, final long length) {
        final long oldLength = length(array);
        return (length > oldLength) ? grow(array, length, oldLength) : array;
    }
    
    @Deprecated
    public static boolean[][] grow(final boolean[][] array, final long length, final long preserve) {
        final long oldLength = length(array);
        return (length > oldLength) ? ensureCapacity(array, Math.max(oldLength + (oldLength >> 1), length), preserve) : array;
    }
    
    @Deprecated
    public static boolean[][] trim(final boolean[][] array, final long length) {
        BigArrays.ensureLength(length);
        final long oldLength = length(array);
        if (length >= oldLength) {
            return array;
        }
        final int baseLength = (int)(length + 134217727L >>> 27);
        final boolean[][] base = Arrays.copyOf(array, baseLength);
        final int residual = (int)(length & 0x7FFFFFFL);
        if (residual != 0) {
            base[baseLength - 1] = BooleanArrays.trim(base[baseLength - 1], residual);
        }
        return base;
    }
    
    @Deprecated
    public static boolean[][] setLength(final boolean[][] array, final long length) {
        return BigArrays.setLength(array, length);
    }
    
    @Deprecated
    public static boolean[][] copy(final boolean[][] array, final long offset, final long length) {
        return BigArrays.copy(array, offset, length);
    }
    
    @Deprecated
    public static boolean[][] copy(final boolean[][] array) {
        return BigArrays.copy(array);
    }
    
    @Deprecated
    public static void fill(final boolean[][] array, final boolean value) {
        int i = array.length;
        while (i-- != 0) {
            Arrays.fill(array[i], value);
        }
    }
    
    @Deprecated
    public static void fill(final boolean[][] array, final long from, final long to, final boolean value) {
        BigArrays.fill(array, from, to, value);
    }
    
    @Deprecated
    public static boolean equals(final boolean[][] a1, final boolean[][] a2) {
        return BigArrays.equals(a1, a2);
    }
    
    @Deprecated
    public static String toString(final boolean[][] a) {
        return BigArrays.toString(a);
    }
    
    @Deprecated
    public static void ensureFromTo(final boolean[][] a, final long from, final long to) {
        BigArrays.ensureFromTo(length(a), from, to);
    }
    
    @Deprecated
    public static void ensureOffsetLength(final boolean[][] a, final long offset, final long length) {
        BigArrays.ensureOffsetLength(length(a), offset, length);
    }
    
    @Deprecated
    public static void ensureSameLength(final boolean[][] a, final boolean[][] 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 void swap(final boolean[][] x, long a, long b, final long n) {
        for (int i = 0; i < n; ++i, ++a, ++b) {
            BigArrays.swap(x, a, b);
        }
    }
    
    private static long med3(final boolean[][] x, final long a, final long b, final long c, final BooleanComparator 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 void selectionSort(final boolean[][] a, final long from, final long to, final BooleanComparator 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 void quickSort(final boolean[][] x, final long from, final long to, final BooleanComparator comp) {
        final long len = to - from;
        if (len < 7L) {
            selectionSort(x, from, to, 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 boolean 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, comp);
        }
        if ((s2 = d - c) > 1L) {
            quickSort(x, n2 - s2, n2, comp);
        }
    }
    
    private static long med3(final boolean[][] x, final long a, final long b, final long c) {
        final int ab = Boolean.compare(BigArrays.get(x, a), BigArrays.get(x, b));
        final int ac = Boolean.compare(BigArrays.get(x, a), BigArrays.get(x, c));
        final int bc = Boolean.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 void selectionSort(final boolean[][] 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(a, j) && BigArrays.get(a, m)) {
                    m = j;
                }
            }
            if (m != i) {
                BigArrays.swap(a, i, m);
            }
        }
    }
    
    public static void quickSort(final boolean[][] x, final BooleanComparator comp) {
        quickSort(x, 0L, BigArrays.length(x), comp);
    }
    
    public static void quickSort(final boolean[][] x, final long from, final long to) {
        final long len = to - from;
        if (len < 7L) {
            selectionSort(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 boolean 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 = Boolean.compare(BigArrays.get(x, b), v)) <= 0) {
                if (comparison == 0) {
                    BigArrays.swap(x, a++, b);
                }
                ++b;
            }
            else {
                while (c >= b && (comparison = Boolean.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);
        }
        if ((s2 = d - c) > 1L) {
            quickSort(x, n2 - s2, n2);
        }
    }
    
    public static void quickSort(final boolean[][] x) {
        quickSort(x, 0L, BigArrays.length(x));
    }
    
    public static void parallelQuickSort(final boolean[][] x, final long from, final long to) {
        final ForkJoinPool pool = getPool();
        if (to - from < 8192L || pool.getParallelism() == 1) {
            quickSort(x, from, to);
        }
        else {
            pool.invoke((ForkJoinTask<Object>)new ForkJoinQuickSort(x, from, to));
        }
    }
    
    public static void parallelQuickSort(final boolean[][] x) {
        parallelQuickSort(x, 0L, BigArrays.length(x));
    }
    
    public static void parallelQuickSort(final boolean[][] x, final long from, final long to, final BooleanComparator comp) {
        final ForkJoinPool pool = getPool();
        if (to - from < 8192L || pool.getParallelism() == 1) {
            quickSort(x, from, to, comp);
        }
        else {
            pool.invoke((ForkJoinTask<Object>)new ForkJoinQuickSortComp(x, from, to, comp));
        }
    }
    
    public static void parallelQuickSort(final boolean[][] x, final BooleanComparator comp) {
        parallelQuickSort(x, 0L, BigArrays.length(x), comp);
    }
    
    public static boolean[][] shuffle(final boolean[][] a, final long from, final long to, final Random random) {
        return BigArrays.shuffle(a, from, to, random);
    }
    
    public static boolean[][] shuffle(final boolean[][] a, final Random random) {
        return BigArrays.shuffle(a, random);
    }
    
    static {
        EMPTY_BIG_ARRAY = new boolean[0][];
        DEFAULT_EMPTY_BIG_ARRAY = new boolean[0][];
        HASH_STRATEGY = new BigArrayHashStrategy();
    }
    
    private static final class BigArrayHashStrategy implements Hash.Strategy<boolean[][]>, Serializable
    {
        private static final long serialVersionUID = -7046029254386353129L;
        
        @Override
        public int hashCode(final boolean[][] o) {
            return Arrays.deepHashCode(o);
        }
        
        @Override
        public boolean equals(final boolean[][] a, final boolean[][] b) {
            return BooleanBigArrays.equals(a, b);
        }
    }
    
    protected static class ForkJoinQuickSort extends RecursiveAction
    {
        private static final long serialVersionUID = 1L;
        private final long from;
        private final long to;
        private final boolean[][] x;
        
        public ForkJoinQuickSort(final boolean[][] x, final long from, final long to) {
            this.from = from;
            this.to = to;
            this.x = x;
        }
        
        @Override
        protected void compute() {
            final boolean[][] x = this.x;
            final long len = this.to - this.from;
            if (len < 8192L) {
                BooleanBigArrays.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 boolean 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 = Boolean.compare(BigArrays.get(x, b), v)) <= 0) {
                    if (comparison == 0) {
                        BigArrays.swap(x, a++, b);
                    }
                    ++b;
                }
                else {
                    while (c >= b && (comparison = Boolean.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 ForkJoinQuickSort(x, this.from, this.from + s), new ForkJoinQuickSort(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 extends RecursiveAction
    {
        private static final long serialVersionUID = 1L;
        private final long from;
        private final long to;
        private final boolean[][] x;
        private final BooleanComparator comp;
        
        public ForkJoinQuickSortComp(final boolean[][] x, final long from, final long to, final BooleanComparator comp) {
            this.from = from;
            this.to = to;
            this.x = x;
            this.comp = comp;
        }
        
        @Override
        protected void compute() {
            final boolean[][] x = this.x;
            final long len = this.to - this.from;
            if (len < 8192L) {
                BooleanBigArrays.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 boolean 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(x, this.from, this.from + s, this.comp), new ForkJoinQuickSortComp(x, this.to - t, this.to, 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));
            }
        }
    }
}