/*

 * Copyright (c) 1997, 2014, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package java.util;

import java.lang.reflect.Array;

import java.util.concurrent.ForkJoinPool;

import java.util.function.BinaryOperator;

import java.util.function.DoubleBinaryOperator;

import java.util.function.IntBinaryOperator;

import java.util.function.IntFunction;

import java.util.function.IntToDoubleFunction;

import java.util.function.IntToLongFunction;

import java.util.function.IntUnaryOperator;

import java.util.function.LongBinaryOperator;

import java.util.stream.DoubleStream;

import java.util.stream.IntStream;

import java.util.stream.LongStream;

import java.util.stream.Stream;

import java.util.stream.StreamSupport;

/**

 * This class contains various methods for manipulating arrays (such as

 * sorting and searching). This class also contains a static factory

 * that allows arrays to be viewed as lists.

 *

 * <p>The methods in this class all throw a {@code NullPointerException},

 * if the specified array reference is null, except where noted.

 *

 * <p>The documentation for the methods contained in this class includes

 * be regarded as <i>implementation notes</i>, rather than parts of the

 * <i>specification</i>. Implementors should feel free to substitute other

 * algorithms, so long as the specification itself is adhered to. (For

 * example, the algorithm used by {@code sort(Object[])} does not have to be

 * a MergeSort, but it does have to be <i>stable</i>.)

 *

 * <p>This class is a member of the

 * <a href="{@docRoot}/../technotes/guides/collections/index.html">

 * Java Collections Framework</a>.

 *

 * @author Josh Bloch

 * @author Neal Gafter

 * @author John Rose

 * @since  1.2

 */

public class Arrays {

    /**

     * The minimum array length below which a parallel sorting

     * algorithm will not further partition the sorting task. Using

     * smaller sizes typically results in memory contention across

     * tasks that makes parallel speedups unlikely.

     */

    private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;

    // Suppresses default constructor, ensuring non-instantiability.

    private Arrays() {}

    /**

     * A comparator that implements the natural ordering of a group of

     * mutually comparable elements. May be used when a supplied

     * comparator is null. To simplify code-sharing within underlying

     * implementations, the compare method only declares type Object

     * for its second argument.

     *

     * Arrays class implementor's note: It is an empirical matter

     * whether ComparableTimSort offers any performance benefit over

     * TimSort used with this comparator.  If not, you are better off

     * deleting or bypassing ComparableTimSort.  There is currently no

     * empirical case for separating them for parallel sorting, so all

     * public Object parallelSort methods use the same comparator

     * based implementation.

     */

    static final class NaturalOrder implements Comparator<Object> {

        @SuppressWarnings("unchecked")

        public int compare(Object first, Object second) {

            return ((Comparable<Object>)first).compareTo(second);

        }

        static final NaturalOrder INSTANCE = new NaturalOrder();

    }

    /**

     * Checks that {@code fromIndex} and {@code toIndex} are in

     * the range and throws an exception if they aren't.

     */

    private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {

        if (fromIndex > toIndex) {

            throw new IllegalArgumentException(

                    "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");

        }

        if (fromIndex < 0) {

            throw new ArrayIndexOutOfBoundsException(fromIndex);

        }

        if (toIndex > arrayLength) {

            throw new ArrayIndexOutOfBoundsException(toIndex);

        }

    }

    /*

     * Sorting methods. Note that all public "sort" methods take the

     * same form: Performing argument checks if necessary, and then

     * expanding arguments into those required for the internal

     * implementation methods residing in other package-private

     * classes (except for legacyMergeSort, included in this class).

     */

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     */

    public static void sort(int[] a) {

        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);

    }

    /**

     * Sorts the specified range of the array into ascending order. The range

     * to be sorted extends from the index {@code fromIndex}, inclusive, to

     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     * @param fromIndex the index of the first element, inclusive, to be sorted

     * @param toIndex the index of the last element, exclusive, to be sorted

     *

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

     */

    public static void sort(int[] a, int fromIndex, int toIndex) {

        rangeCheck(a.length, fromIndex, toIndex);

        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     */

    public static void sort(long[] a) {

        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);

    }

    /**

     * Sorts the specified range of the array into ascending order. The range

     * to be sorted extends from the index {@code fromIndex}, inclusive, to

     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     * @param fromIndex the index of the first element, inclusive, to be sorted

     * @param toIndex the index of the last element, exclusive, to be sorted

     *

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

     */

    public static void sort(long[] a, int fromIndex, int toIndex) {

        rangeCheck(a.length, fromIndex, toIndex);

        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     */

    public static void sort(short[] a) {

        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);

    }

    /**

     * Sorts the specified range of the array into ascending order. The range

     * to be sorted extends from the index {@code fromIndex}, inclusive, to

     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     * @param fromIndex the index of the first element, inclusive, to be sorted

     * @param toIndex the index of the last element, exclusive, to be sorted

     *

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

     */

    public static void sort(short[] a, int fromIndex, int toIndex) {

        rangeCheck(a.length, fromIndex, toIndex);

        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     */

    public static void sort(char[] a) {

        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);

    }

    /**

     * Sorts the specified range of the array into ascending order. The range

     * to be sorted extends from the index {@code fromIndex}, inclusive, to

     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     * @param fromIndex the index of the first element, inclusive, to be sorted

     * @param toIndex the index of the last element, exclusive, to be sorted

     *

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

     */

    public static void sort(char[] a, int fromIndex, int toIndex) {

        rangeCheck(a.length, fromIndex, toIndex);

        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     */

    public static void sort(byte[] a) {

        DualPivotQuicksort.sort(a, 0, a.length - 1);

    }

    /**

     * Sorts the specified range of the array into ascending order. The range

     * to be sorted extends from the index {@code fromIndex}, inclusive, to

     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     * @param fromIndex the index of the first element, inclusive, to be sorted

     * @param toIndex the index of the last element, exclusive, to be sorted

     *

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

     */

    public static void sort(byte[] a, int fromIndex, int toIndex) {

        rangeCheck(a.length, fromIndex, toIndex);

        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * <p>The {@code <} relation does not provide a total order on all float

     * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}

     * value compares neither less than, greater than, nor equal to any value,

     * even itself. This method uses the total order imposed by the method

     * {@link Float#compareTo}: {@code -0.0f} is treated as less than value

     * {@code 0.0f} and {@code Float.NaN} is considered greater than any

     * other value and all {@code Float.NaN} values are considered equal.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     */

    public static void sort(float[] a) {

        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);

    }

    /**

     * Sorts the specified range of the array into ascending order. The range

     * to be sorted extends from the index {@code fromIndex}, inclusive, to

     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     *

     * <p>The {@code <} relation does not provide a total order on all float

     * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}

     * value compares neither less than, greater than, nor equal to any value,

     * even itself. This method uses the total order imposed by the method

     * {@link Float#compareTo}: {@code -0.0f} is treated as less than value

     * {@code 0.0f} and {@code Float.NaN} is considered greater than any

     * other value and all {@code Float.NaN} values are considered equal.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     * @param fromIndex the index of the first element, inclusive, to be sorted

     * @param toIndex the index of the last element, exclusive, to be sorted

     *

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

     */

    public static void sort(float[] a, int fromIndex, int toIndex) {

        rangeCheck(a.length, fromIndex, toIndex);

        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * <p>The {@code <} relation does not provide a total order on all double

     * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}

     * value compares neither less than, greater than, nor equal to any value,

     * even itself. This method uses the total order imposed by the method

     * {@link Double#compareTo}: {@code -0.0d} is treated as less than value

     * {@code 0.0d} and {@code Double.NaN} is considered greater than any

     * other value and all {@code Double.NaN} values are considered equal.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     */

    public static void sort(double[] a) {

        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);

    }

    /**

     * Sorts the specified range of the array into ascending order. The range

     * to be sorted extends from the index {@code fromIndex}, inclusive, to

     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},

     * the range to be sorted is empty.

     *

     * <p>The {@code <} relation does not provide a total order on all double

     * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}

     * value compares neither less than, greater than, nor equal to any value,

     * even itself. This method uses the total order imposed by the method

     * {@link Double#compareTo}: {@code -0.0d} is treated as less than value

     * {@code 0.0d} and {@code Double.NaN} is considered greater than any

     * other value and all {@code Double.NaN} values are considered equal.

     *

     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort

     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm

     * offers O(n log(n)) performance on many data sets that cause other

     * quicksorts to degrade to quadratic performance, and is typically

     * faster than traditional (one-pivot) Quicksort implementations.

     *

     * @param a the array to be sorted

     * @param fromIndex the index of the first element, inclusive, to be sorted

     * @param toIndex the index of the last element, exclusive, to be sorted

     *

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException

     *     if {@code fromIndex < 0} or {@code toIndex > a.length}

     */

    public static void sort(double[] a, int fromIndex, int toIndex) {

        rangeCheck(a.length, fromIndex, toIndex);

        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * @implNote The sorting algorithm is a parallel sort-merge that breaks the

     * array into sub-arrays that are themselves sorted and then merged. When

     * the sub-array length reaches a minimum granularity, the sub-array is

     * sorted using the appropriate {@link Arrays#sort(byte[]) Arrays.sort}

     * method. If the length of the specified array is less than the minimum

     * granularity, then it is sorted using the appropriate {@link

     * Arrays#sort(byte[]) Arrays.sort} method. The algorithm requires a

     * working space no greater than the size of the original array. The

     * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to

     * execute any parallel tasks.

     *

     * @param a the array to be sorted

     *

     * @since 1.8

     */

    public static void parallelSort(byte[] a) {

        int n = a.length, p, g;

        if (n <= MIN_ARRAY_SORT_GRAN ||

            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)

            DualPivotQuicksort.sort(a, 0, n - 1);

        else

            new ArraysParallelSortHelpers.FJByte.Sorter

                (null, a, new byte[n], 0, n, 0,

                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?

                 MIN_ARRAY_SORT_GRAN : g).invoke();

    }

    /**

     * Sorts the specified range of the array into ascending numerical order.

     * The range to be sorted extends from the index {@code fromIndex},

     * inclusive, to the index {@code toIndex}, exclusive. If

     * {@code fromIndex == toIndex}, the range to be sorted is empty.

     *

     * @implNote The sorting algorithm is a parallel sort-merge that breaks the

     * array into sub-arrays that are themselves sorted and then merged. When

     * the sub-array length reaches a minimum granularity, the sub-array is

     * sorted using the appropriate {@link Arrays#sort(byte[]) Arrays.sort}

     * method. If the length of the specified array is less than the minimum

     * granularity, then it is sorted using the appropriate {@link

     * Arrays#sort(byte[]) Arrays.sort} method. The algorithm requires a working

     * space no greater than the size of the specified range of the original

     * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is

     * used to execute any parallel tasks.

     *

     * @param a the array to be sorted

     * @param fromIndex the index of the first element, inclusive, to be sorted

     * @param toIndex the index of the last element, exclusive, to be sorted

     *

     * @throws IllegalArgumentException if {@code fromIndex > toIndex}

     * @throws ArrayIndexOutOfBoundsException