/*

 * Copyright (c) 1997, 2019, 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 jdk.internal.HotSpotIntrinsicCandidate;

import jdk.internal.util.ArraysSupport;

import java.io.Serializable;

import java.lang.reflect.Array;

import java.util.concurrent.ForkJoinPool;

import java.util.function.BinaryOperator;

import java.util.function.Consumer;

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.function.UnaryOperator;

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

 * brief descriptions of the <i>implementations</i>. Such descriptions should

 * 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}/java.base/java/util/package-summary.html#CollectionsFramework">

 * Java Collections Framework</a>.

 *

 * @author Josh Bloch

 * @author Neal Gafter

 * @author John Rose

 * @since  1.2

 */

public class Arrays {

    // Suppresses default constructor, ensuring non-instantiability.

    private Arrays() {}

    /*

     * 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.

     *

     * @implNote 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 all data sets, 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, 0, a.length);

    }

    /**

     * 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.

     *

     * @implNote 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 all data sets, 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, 0, fromIndex, toIndex);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * @implNote 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 all data sets, 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, 0, a.length);

    }

    /**

     * 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.

     *

     * @implNote 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 all data sets, 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, 0, fromIndex, toIndex);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * @implNote 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 all data sets, 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);

    }

    /**

     * 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.

     *

     * @implNote 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 all data sets, 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);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * @implNote 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 all data sets, 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);

    }

    /**

     * 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.

     *

     * @implNote 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 all data sets, 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);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * @implNote 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 all data sets, 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);

    }

    /**

     * 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.

     *

     * @implNote 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 all data sets, 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);

    }

    /**

     * 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.

     *

     * @implNote 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 all data sets, 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, 0, a.length);

    }

    /**

     * 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.

     *

     * @implNote 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 all data sets, 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, 0, fromIndex, toIndex);

    }

    /**

     * 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.

     *

     * @implNote 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 all data sets, 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, 0, a.length);

    }

    /**

     * 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.

     *

     * @implNote 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 all data sets, 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, 0, fromIndex, toIndex);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * @implNote The sorting algorithm is a Dual-Pivot Quicksort by

     * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm

     * offers O(n log(n)) performance on all data sets, and is typically

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

     *

     * @param a the array to be sorted

     *

     * @since 1.8

     */

    public static void parallelSort(byte[] a) {

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

    }

    /**

     * 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 Dual-Pivot Quicksort by

     * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm

     * offers O(n log(n)) performance on all data sets, 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}

     *

     * @since 1.8

     */

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

        rangeCheck(a.length, fromIndex, toIndex);

        DualPivotQuicksort.sort(a, fromIndex, toIndex);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * @implNote The sorting algorithm is a Dual-Pivot Quicksort by

     * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm

     * offers O(n log(n)) performance on all data sets, and is typically

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

     *

     * @param a the array to be sorted

     *

     * @since 1.8

     */

    public static void parallelSort(char[] a) {

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

    }

    /**

     * 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 Dual-Pivot Quicksort by

     * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm

     * offers O(n log(n)) performance on all data sets, 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}

     *

     * @since 1.8

     */

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

        rangeCheck(a.length, fromIndex, toIndex);

        DualPivotQuicksort.sort(a, fromIndex, toIndex);

    }

    /**

     * Sorts the specified array into ascending numerical order.

     *

     * @implNote The sorting algorithm is a Dual-Pivot Quicksort by

     * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm

     * offers O(n log(n)) performance on all data sets, and is typically

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

     *

     * @param a the array to be sorted

     *

     * @since 1.8

     */

    public static void parallelSort(short[] a) {

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

    }

    /**

     * 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 Dual-Pivot Quicksort by

     * Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm

     * offers O(n log(n)) performance on all data sets, and is typically

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

     *