/*

 * Copyright (c) 1997, 2011, 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.*;

/**

 * 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

 * briefs description 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}/../technotes/guides/collections/index.html">

 * 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 of primitive type arrays.

     */

    /**

     * 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);

    }

    /**

     * 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);

    }

    /**

     * 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);

    }

    /**

     * 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);

    }

    /**

     * 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);

    }

    /**

     * 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);

    }

    /**

     * 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);

    }

    /**

     * 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);

    }

    /**

     * 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);

    }

    /**

     * 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);

    }

    /**

     * 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);

    }

    /**

     * 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);

    }

    /**

     * 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);

    }

    /*

     * Sorting of complex type arrays.

     */

    /**

     * Old merge sort implementation can be selected (for

     * compatibility with broken comparators) using a system property.

     * Cannot be a static boolean in the enclosing class due to

     * circular dependencies. To be removed in a future release.

     */

    static final class LegacyMergeSort {

        private static final boolean userRequested =

            java.security.AccessController.doPrivileged(

                new sun.security.action.GetBooleanAction(

                    "java.util.Arrays.useLegacyMergeSort")).booleanValue();

    }

    /*

     * If this platform has an optimizing VM, check whether ComparableTimSort

     * offers any performance benefit over TimSort in conjunction with a

     * comparator that returns:

     *    {@code ((Comparable)first).compareTo(Second)}.

     * If not, you are better off deleting ComparableTimSort to

     * eliminate the code duplication.  In other words, the commented

     * out code below is the preferable implementation for sorting

     * arrays of Comparables if it offers sufficient performance.

     */

//    /**

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

//     * mutually comparable elements.  Using this comparator saves us

//     * from duplicating most of the code in this file (one version for

//     * Comparables, one for explicit Comparators).

//     */

//    private static final Comparator<Object> NATURAL_ORDER =

//            new Comparator<Object>() {

//        @SuppressWarnings("unchecked")

//        public int compare(Object first, Object second) {

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

//        }

//    };

//

//    public static void sort(Object[] a) {

//        sort(a, 0, a.length, NATURAL_ORDER);

//    }

//

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

//        sort(a, fromIndex, toIndex, NATURAL_ORDER);

//    }

    /**

     * Sorts the specified array of objects into ascending order, according

     * to the {@linkplain Comparable natural ordering} of its elements.

     * All elements in the array must implement the {@link Comparable}

     * interface.  Furthermore, all elements in the array must be

     * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must

     * not throw a {@code ClassCastException} for any elements {@code e1}

     * and {@code e2} in the array).

     *

     * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will

     * not be reordered as a result of the sort.

     *

     * <p>Implementation note: This implementation is a stable, adaptive,

     * iterative mergesort that requires far fewer than n lg(n) comparisons

     * when the input array is partially sorted, while offering the

     * performance of a traditional mergesort when the input array is

     * randomly ordered.  If the input array is nearly sorted, the

     * implementation requires approximately n comparisons.  Temporary

     * storage requirements vary from a small constant for nearly sorted

     * input arrays to n/2 object references for randomly ordered input

     * arrays.

     *

     * <p>The implementation takes equal advantage of ascending and

     * descending order in its input array, and can take advantage of

     * ascending and descending order in different parts of the the same

     * input array.  It is well-suited to merging two or more sorted arrays:

     * simply concatenate the arrays and sort the resulting array.

     *

     * <p>The implementation was adapted from Tim Peters's list sort for Python

     * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">

     * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic

     * Sorting and Information Theoretic Complexity", in Proceedings of the

     * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,

     * January 1993.

     *

     * @param a the array to be sorted

     * @throws ClassCastException if the array contains elements that are not

     *         <i>mutually comparable</i> (for example, strings and integers)

     * @throws IllegalArgumentException (optional) if the natural

     *         ordering of the array elements is found to violate the

     *         {@link Comparable} contract

     */

    public static void sort(Object[] a) {

        if (LegacyMergeSort.userRequested)

            legacyMergeSort(a);

        else

            ComparableTimSort.sort(a);

    }

    /** To be removed in a future release. */

    private static void legacyMergeSort(Object[] a) {

        Object[] aux = a.clone();

        mergeSort(aux, a, 0, a.length, 0);

    }

    /**

     * Sorts the specified range of the specified array of objects into

     * ascending order, according to the

     * {@linkplain Comparable natural ordering} of its

     * elements.  The range to be sorted extends from index

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

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

     * elements in this range must implement the {@link Comparable}

     * interface.  Furthermore, all elements in this range must be <i>mutually

     * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a

     * {@code ClassCastException} for any elements {@code e1} and

     * {@code e2} in the array).

     *

     * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will

     * not be reordered as a result of the sort.