/* * Copyright (C) 2014 The Android Open Source Project * 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.*; 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. * *

The methods in this class all throw a {@code NullPointerException}, * if the specified array reference is null, except where noted. * *

The documentation for the methods contained in this class includes * briefs description of the implementations. Such descriptions should * be regarded as implementation notes, rather than parts of the * specification. 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 stable.) * *

This class is a member of the * * Java Collections Framework. * * @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. * @hide */ public static final int MIN_ARRAY_SORT_GRAN = 1 << 13; /** * 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 { @SuppressWarnings("unchecked") public int compare(Object first, Object second) { return ((Comparable)first).compareTo(second); } static final NaturalOrder INSTANCE = new NaturalOrder(); } // Suppresses default constructor, ensuring non-instantiability. private Arrays() {} /* * Sorting of primitive type arrays. */ /** * Sorts the specified array into ascending numerical order. * *

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 * 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); int n = toIndex - fromIndex, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); else new ArraysParallelSortHelpers.FJByte.Sorter (null, a, new byte[n], fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke(); } /** * 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(char[]) 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(char[]) 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(char[] a) { int n = a.length, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJChar.Sorter (null, a, new char[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(char[]) 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(char[]) 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 * 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); int n = toIndex - fromIndex, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJChar.Sorter (null, a, new char[n], fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke(); } /** * 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(short[]) 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(short[]) 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(short[] a) { int n = a.length, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJShort.Sorter (null, a, new short[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(short[]) 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(short[]) 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 * if {@code fromIndex < 0} or {@code toIndex > a.length} * * @since 1.8 */ public static void parallelSort(short[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); int n = toIndex - fromIndex, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJShort.Sorter (null, a, new short[n], fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke(); } /** * 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(int[]) 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(int[]) 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(int[] a) { int n = a.length, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJInt.Sorter (null, a, new int[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(int[]) 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(int[]) 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 * if {@code fromIndex < 0} or {@code toIndex > a.length} * * @since 1.8 */ public static void parallelSort(int[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); int n = toIndex - fromIndex, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJInt.Sorter (null, a, new int[n], fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke(); } /** * 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(long[]) 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(long[]) 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(long[] a) { int n = a.length, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJLong.Sorter (null, a, new long[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(long[]) 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(long[]) 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 * if {@code fromIndex < 0} or {@code toIndex > a.length} * * @since 1.8 */ public static void parallelSort(long[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); int n = toIndex - fromIndex, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJLong.Sorter (null, a, new long[n], fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke(); } /** * Sorts the specified array into ascending numerical order. * *

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 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(float[]) 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(float[]) 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(float[] a) { int n = a.length, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJFloat.Sorter (null, a, new float[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. * *

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 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(float[]) 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(float[]) 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 * if {@code fromIndex < 0} or {@code toIndex > a.length} * * @since 1.8 */ public static void parallelSort(float[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); int n = toIndex - fromIndex, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJFloat.Sorter (null, a, new float[n], fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke(); } /** * Sorts the specified array into ascending numerical order. * *

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 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(double[]) 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(double[]) 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(double[] a) { int n = a.length, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJDouble.Sorter (null, a, new double[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. * *

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 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(double[]) 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(double[]) 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 * if {@code fromIndex < 0} or {@code toIndex > a.length} * * @since 1.8 */ public static void parallelSort(double[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); int n = toIndex - fromIndex, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); else new ArraysParallelSortHelpers.FJDouble.Sorter (null, a, new double[n], fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g).invoke(); } /** * 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 * mutually comparable (that is, {@code e1.compareTo(e2)} must * not throw a {@code ClassCastException} for any elements {@code e1} * and {@code e2} in the array). * *

This sort is guaranteed to be stable: equal elements will * not be reordered as a result of the sort. * * @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(Object[]) 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(Object[]) 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 the class of the objects to be sorted * @param a the array to be sorted * * @throws ClassCastException if the array contains elements that are not * mutually comparable (for example, strings and integers) * @throws IllegalArgumentException (optional) if the natural * ordering of the array elements is found to violate the * {@link Comparable} contract * * @since 1.8 */ @SuppressWarnings("unchecked") public static > void parallelSort(T[] a) { int n = a.length, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) TimSort.sort(a, 0, n, NaturalOrder.INSTANCE, null, 0, 0); else new ArraysParallelSortHelpers.FJObject.Sorter (null, a, (T[])Array.newInstance(a.getClass().getComponentType(), n), 0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke(); } /** * 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 mutually * comparable (that is, {@code e1.compareTo(e2)} must not throw a * {@code ClassCastException} for any elements {@code e1} and * {@code e2} in the array). * *

This sort is guaranteed to be stable: equal elements will * not be reordered as a result of the sort. * * @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(Object[]) 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(Object[]) 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 the class of the objects to be sorted * @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} or * (optional) if the natural ordering of the array elements is * found to violate the {@link Comparable} contract * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or * {@code toIndex > a.length} * @throws ClassCastException if the array contains elements that are * not mutually comparable (for example, strings and * integers). * * @since 1.8 */ @SuppressWarnings("unchecked") public static > void parallelSort(T[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); int n = toIndex - fromIndex, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) TimSort.sort(a, fromIndex, toIndex, NaturalOrder.INSTANCE, null, 0, 0); else new ArraysParallelSortHelpers.FJObject.Sorter (null, a, (T[])Array.newInstance(a.getClass().getComponentType(), n), fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke(); } /** * Sorts the specified array of objects according to the order induced by * the specified comparator. All elements in the array must be * mutually comparable by the specified comparator (that is, * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} * for any elements {@code e1} and {@code e2} in the array). * *

This sort is guaranteed to be stable: equal elements will * not be reordered as a result of the sort. * * @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(Object[]) 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(Object[]) 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 the class of the objects to be sorted * @param a the array to be sorted * @param cmp the comparator to determine the order of the array. A * {@code null} value indicates that the elements' * {@linkplain Comparable natural ordering} should be used. * @throws ClassCastException if the array contains elements that are * not mutually comparable using the specified comparator * @throws IllegalArgumentException (optional) if the comparator is * found to violate the {@link java.util.Comparator} contract * * @since 1.8 */ @SuppressWarnings("unchecked") public static void parallelSort(T[] a, Comparator cmp) { if (cmp == null) cmp = NaturalOrder.INSTANCE; int n = a.length, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) TimSort.sort(a, 0, n, cmp, null, 0, 0); else new ArraysParallelSortHelpers.FJObject.Sorter (null, a, (T[])Array.newInstance(a.getClass().getComponentType(), n), 0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g, cmp).invoke(); } /** * Sorts the specified range of the specified array of objects according * to the order induced by the specified comparator. 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 the range must be * mutually comparable by the specified comparator (that is, * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} * for any elements {@code e1} and {@code e2} in the range). * *

This sort is guaranteed to be stable: equal elements will * not be reordered as a result of the sort. * * @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(Object[]) 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(Object[]) 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 the class of the objects to be sorted * @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 * @param cmp the comparator to determine the order of the array. A * {@code null} value indicates that the elements' * {@linkplain Comparable natural ordering} should be used. * @throws IllegalArgumentException if {@code fromIndex > toIndex} or * (optional) if the natural ordering of the array elements is * found to violate the {@link Comparable} contract * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or * {@code toIndex > a.length} * @throws ClassCastException if the array contains elements that are * not mutually comparable (for example, strings and * integers). * * @since 1.8 */ @SuppressWarnings("unchecked") public static void parallelSort(T[] a, int fromIndex, int toIndex, Comparator cmp) { rangeCheck(a.length, fromIndex, toIndex); if (cmp == null) cmp = NaturalOrder.INSTANCE; int n = toIndex - fromIndex, p, g; if (n <= MIN_ARRAY_SORT_GRAN || (p = ForkJoinPool.getCommonPoolParallelism()) == 1) TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0); else new ArraysParallelSortHelpers.FJObject.Sorter (null, a, (T[])Array.newInstance(a.getClass().getComponentType(), n), fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? MIN_ARRAY_SORT_GRAN : g, cmp).invoke(); } /* * 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 { // Android-changed: Never use circular merge sort. private static final boolean userRequested = false; } /* * 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 NATURAL_ORDER = // new Comparator() { // @SuppressWarnings("unchecked") // public int compare(Object first, Object second) { // return ((Comparable)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 * mutually comparable (that is, {@code e1.compareTo(e2)} must * not throw a {@code ClassCastException} for any elements {@code e1} * and {@code e2} in the array). * *

This sort is guaranteed to be stable: equal elements will * not be reordered as a result of the sort. * *

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

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

The implementation was adapted from Tim Peters's list sort for Python * ( * TimSort). 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 * mutually comparable (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, 0, a.length, null, 0, 0); } /** 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 mutually * comparable (that is, {@code e1.compareTo(e2)} must not throw a * {@code ClassCastException} for any elements {@code e1} and * {@code e2} in the array). * *

This sort is guaranteed to be stable: equal elements will * not be reordered as a result of the sort. * *

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

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

The implementation was adapted from Tim Peters's list sort for Python * ( * TimSort). 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 * @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} or * (optional) if the natural ordering of the array elements is * found to violate the {@link Comparable} contract * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or * {@code toIndex > a.length} * @throws ClassCastException if the array contains elements that are * not mutually comparable (for example, strings and * integers). */ public static void sort(Object[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); if (LegacyMergeSort.userRequested) legacyMergeSort(a, fromIndex, toIndex); else ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0); } /** To be removed in a future release. */ private static void legacyMergeSort(Object[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); Object[] aux = copyOfRange(a, fromIndex, toIndex); mergeSort(aux, a, fromIndex, toIndex, -fromIndex); } /** * Tuning parameter: list size at or below which insertion sort will be * used in preference to mergesort. * To be removed in a future release. */ private static final int INSERTIONSORT_THRESHOLD = 7; /** * Src is the source array that starts at index 0 * Dest is the (possibly larger) array destination with a possible offset * low is the index in dest to start sorting * high is the end index in dest to end sorting * off is the offset to generate corresponding low, high in src * To be removed in a future release. */ private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off) { int length = high - low; // Insertion sort on smallest arrays if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; ilow && ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--) swap(dest, j, j-1); return; } // Recursively sort halves of dest into src int destLow = low; int destHigh = high; low += off; high += off; int mid = (low + high) >>> 1; mergeSort(dest, src, low, mid, -off); mergeSort(dest, src, mid, high, -off); // If list is already sorted, just copy from src to dest. This is an // optimization that results in faster sorts for nearly ordered lists. if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) { System.arraycopy(src, low, dest, destLow, length); return; } // Merge sorted halves (now in src) into dest for(int i = destLow, p = low, q = mid; i < destHigh; i++) { if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0) dest[i] = src[p++]; else dest[i] = src[q++]; } } /** * Swaps x[a] with x[b]. */ private static void swap(Object[] x, int a, int b) { Object t = x[a]; x[a] = x[b]; x[b] = t; } /** * Sorts the specified array of objects according to the order induced by * the specified comparator. All elements in the array must be * mutually comparable by the specified comparator (that is, * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} * for any elements {@code e1} and {@code e2} in the array). * *

This sort is guaranteed to be stable: equal elements will * not be reordered as a result of the sort. * *

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

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

The implementation was adapted from Tim Peters's list sort for Python * ( * TimSort). 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 * @param c the comparator to determine the order of the array. A * {@code null} value indicates that the elements' * {@linkplain Comparable natural ordering} should be used. * @throws ClassCastException if the array contains elements that are * not mutually comparable using the specified comparator * @throws IllegalArgumentException (optional) if the comparator is * found to violate the {@link Comparator} contract */ public static void sort(T[] a, Comparator c) { if (c == null) { sort(a); } else { if (LegacyMergeSort.userRequested) legacyMergeSort(a, c); else TimSort.sort(a, 0, a.length, c, null, 0, 0); } } /** To be removed in a future release. */ private static void legacyMergeSort(T[] a, Comparator c) { T[] aux = a.clone(); if (c==null) mergeSort(aux, a, 0, a.length, 0); else mergeSort(aux, a, 0, a.length, 0, c); } /** * Sorts the specified range of the specified array of objects according * to the order induced by the specified comparator. 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 the range must be * mutually comparable by the specified comparator (that is, * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} * for any elements {@code e1} and {@code e2} in the range). * *

This sort is guaranteed to be stable: equal elements will * not be reordered as a result of the sort. * *

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

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

The implementation was adapted from Tim Peters's list sort for Python * ( * TimSort). 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 * @param fromIndex the index of the first element (inclusive) to be * sorted * @param toIndex the index of the last element (exclusive) to be sorted * @param c the comparator to determine the order of the array. A * {@code null} value indicates that the elements' * {@linkplain Comparable natural ordering} should be used. * @throws ClassCastException if the array contains elements that are not * mutually comparable using the specified comparator. * @throws IllegalArgumentException if {@code fromIndex > toIndex} or * (optional) if the comparator is found to violate the * {@link Comparator} contract * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or * {@code toIndex > a.length} */ public static void sort(T[] a, int fromIndex, int toIndex, Comparator c) { if (c == null) { sort(a, fromIndex, toIndex); } else { rangeCheck(a.length, fromIndex, toIndex); if (LegacyMergeSort.userRequested) legacyMergeSort(a, fromIndex, toIndex, c); else TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0); } } /** To be removed in a future release. */ private static void legacyMergeSort(T[] a, int fromIndex, int toIndex, Comparator c) { rangeCheck(a.length, fromIndex, toIndex); T[] aux = copyOfRange(a, fromIndex, toIndex); if (c==null) mergeSort(aux, a, fromIndex, toIndex, -fromIndex); else mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c); } /** * Src is the source array that starts at index 0 * Dest is the (possibly larger) array destination with a possible offset * low is the index in dest to start sorting * high is the end index in dest to end sorting * off is the offset into src corresponding to low in dest * To be removed in a future release. */ private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off, Comparator c) { int length = high - low; // Insertion sort on smallest arrays if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; ilow && c.compare(dest[j-1], dest[j])>0; j--) swap(dest, j, j-1); return; } // Recursively sort halves of dest into src int destLow = low; int destHigh = high; low += off; high += off; int mid = (low + high) >>> 1; mergeSort(dest, src, low, mid, -off, c); mergeSort(dest, src, mid, high, -off, c); // If list is already sorted, just copy from src to dest. This is an // optimization that results in faster sorts for nearly ordered lists. if (c.compare(src[mid-1], src[mid]) <= 0) { System.arraycopy(src, low, dest, destLow, length); return; } // Merge sorted halves (now in src) into dest for(int i = destLow, p = low, q = mid; i < destHigh; i++) { if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0) dest[i] = src[p++]; else dest[i] = src[q++]; } } /** * Checks that {@code fromIndex} and {@code toIndex} are in * the range and throws an appropriate exception, if they aren't. */ private static void rangeCheck(int length, int fromIndex, int toIndex) { if (fromIndex > toIndex) { throw new IllegalArgumentException( "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); } if (fromIndex < 0) { throw new ArrayIndexOutOfBoundsException(fromIndex); } if (toIndex > length) { throw new ArrayIndexOutOfBoundsException(toIndex); } } // Parallel prefix /** * Cumulates, in parallel, each element of the given array in place, * using the supplied function. For example if the array initially * holds {@code [2, 1, 0, 3]} and the operation performs addition, * then upon return the array holds {@code [2, 3, 3, 6]}. * Parallel prefix computation is usually more efficient than * sequential loops for large arrays. * * @param the class of the objects in the array * @param array the array, which is modified in-place by this method * @param op a side-effect-free, associative function to perform the * cumulation * @throws NullPointerException if the specified array or function is null * @since 1.8 */ public static void parallelPrefix(T[] array, BinaryOperator op) { Objects.requireNonNull(op); if (array.length > 0) new ArrayPrefixHelpers.CumulateTask<> (null, op, array, 0, array.length).invoke(); } /** * Performs {@link #parallelPrefix(Object[], BinaryOperator)} * for the given subrange of the array. * * @param the class of the objects in the array * @param array the array * @param fromIndex the index of the first element, inclusive * @param toIndex the index of the last element, exclusive * @param op a side-effect-free, associative function to perform the * cumulation * @throws IllegalArgumentException if {@code fromIndex > toIndex} * @throws ArrayIndexOutOfBoundsException * if {@code fromIndex < 0} or {@code toIndex > array.length} * @throws NullPointerException if the specified array or function is null * @since 1.8 */ public static void parallelPrefix(T[] array, int fromIndex, int toIndex, BinaryOperator op) { Objects.requireNonNull(op); rangeCheck(array.length, fromIndex, toIndex); if (fromIndex < toIndex) new ArrayPrefixHelpers.CumulateTask<> (null, op, array, fromIndex, toIndex).invoke(); } /** * Cumulates, in parallel, each element of the given array in place, * using the supplied function. For example if the array initially * holds {@code [2, 1, 0, 3]} and the operation performs addition, * then upon return the array holds {@code [2, 3, 3, 6]}. * Parallel prefix computation is usually more efficient than * sequential loops for large arrays. * * @param array the array, which is modified in-place by this method * @param op a side-effect-free, associative function to perform the * cumulation * @throws NullPointerException if the specified array or function is null * @since 1.8 */ public static void parallelPrefix(long[] array, LongBinaryOperator op) { Objects.requireNonNull(op); if (array.length > 0) new ArrayPrefixHelpers.LongCumulateTask (null, op, array, 0, array.length).invoke(); } /** * Performs {@link #parallelPrefix(long[], LongBinaryOperator)} * for the given subrange of the array. * * @param array the array * @param fromIndex the index of the first element, inclusive * @param toIndex the index of the last element, exclusive * @param op a side-effect-free, associative function to perform the * cumulation * @throws IllegalArgumentException if {@code fromIndex > toIndex} * @throws ArrayIndexOutOfBoundsException * if {@code fromIndex < 0} or {@code toIndex > array.length} * @throws NullPointerException if the specified array or function is null * @since 1.8 */ public static void parallelPrefix(long[] array, int fromIndex, int toIndex, LongBinaryOperator op) { Objects.requireNonNull(op); rangeCheck(array.length, fromIndex, toIndex); if (fromIndex < toIndex) new ArrayPrefixHelpers.LongCumulateTask (null, op, array, fromIndex, toIndex).invoke(); } /** * Cumulates, in parallel, each element of the given array in place, * using the supplied function. For example if the array initially * holds {@code [2.0, 1.0, 0.0, 3.0]} and the operation performs addition, * then upon return the array holds {@code [2.0, 3.0, 3.0, 6.0]}. * Parallel prefix computation is usually more efficient than * sequential loops for large arrays. * *

Because floating-point operations may not be strictly associative, * the returned result may not be identical to the value that would be * obtained if the operation was performed sequentially. * * @param array the array, which is modified in-place by this method * @param op a side-effect-free function to perform the cumulation * @throws NullPointerException if the specified array or function is null * @since 1.8 */ public static void parallelPrefix(double[] array, DoubleBinaryOperator op) { Objects.requireNonNull(op); if (array.length > 0) new ArrayPrefixHelpers.DoubleCumulateTask (null, op, array, 0, array.length).invoke(); } /** * Performs {@link #parallelPrefix(double[], DoubleBinaryOperator)} * for the given subrange of the array. * * @param array the array * @param fromIndex the index of the first element, inclusive * @param toIndex the index of the last element, exclusive * @param op a side-effect-free, associative function to perform the * cumulation * @throws IllegalArgumentException if {@code fromIndex > toIndex} * @throws ArrayIndexOutOfBoundsException * if {@code fromIndex < 0} or {@code toIndex > array.length} * @throws NullPointerException if the specified array or function is null * @since 1.8 */ public static void parallelPrefix(double[] array, int fromIndex, int toIndex, DoubleBinaryOperator op) { Objects.requireNonNull(op); rangeCheck(array.length, fromIndex, toIndex); if (fromIndex < toIndex) new ArrayPrefixHelpers.DoubleCumulateTask (null, op, array, fromIndex, toIndex).invoke(); } /** * Cumulates, in parallel, each element of the given array in place, * using the supplied function. For example if the array initially * holds {@code [2, 1, 0, 3]} and the operation performs addition, * then upon return the array holds {@code [2, 3, 3, 6]}. * Parallel prefix computation is usually more efficient than * sequential loops for large arrays. * * @param array the array, which is modified in-place by this method * @param op a side-effect-free, associative function to perform the * cumulation * @throws NullPointerException if the specified array or function is null * @since 1.8 */ public static void parallelPrefix(int[] array, IntBinaryOperator op) { Objects.requireNonNull(op); if (array.length > 0) new ArrayPrefixHelpers.IntCumulateTask (null, op, array, 0, array.length).invoke(); } /** * Performs {@link #parallelPrefix(int[], IntBinaryOperator)} * for the given subrange of the array. * * @param array the array * @param fromIndex the index of the first element, inclusive * @param toIndex the index of the last element, exclusive * @param op a side-effect-free, associative function to perform the * cumulation * @throws IllegalArgumentException if {@code fromIndex > toIndex} * @throws ArrayIndexOutOfBoundsException * if {@code fromIndex < 0} or {@code toIndex > array.length} * @throws NullPointerException if the specified array or function is null * @since 1.8 */ public static void parallelPrefix(int[] array, int fromIndex, int toIndex, IntBinaryOperator op) { Objects.requireNonNull(op); rangeCheck(array.length, fromIndex, toIndex); if (fromIndex < toIndex) new ArrayPrefixHelpers.IntCumulateTask (null, op, array, fromIndex, toIndex).invoke(); } // Searching /** * Searches the specified array of longs for the specified value using the * binary search algorithm. The array must be sorted (as * by the {@link #sort(long[])} method) prior to making this call. If it * is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. */ public static int binarySearch(long[] a, long key) { return binarySearch0(a, 0, a.length, key); } /** * Searches a range of * the specified array of longs for the specified value using the * binary search algorithm. * The range must be sorted (as * by the {@link #sort(long[], int, int)} method) * prior to making this call. If it * is not sorted, the results are undefined. If the range contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched * @param fromIndex the index of the first element (inclusive) to be * searched * @param toIndex the index of the last element (exclusive) to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array * within the specified range; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element in the range greater than the key, * or toIndex if all * elements in the range are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws IllegalArgumentException * if {@code fromIndex > toIndex} * @throws ArrayIndexOutOfBoundsException * if {@code fromIndex < 0 or toIndex > a.length} * @since 1.6 */ public static int binarySearch(long[] a, int fromIndex, int toIndex, long key) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); } // Like public version, but without range checks. private static int binarySearch0(long[] a, int fromIndex, int toIndex, long key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; long midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array of ints for the specified value using the * binary search algorithm. The array must be sorted (as * by the {@link #sort(int[])} method) prior to making this call. If it * is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. */ public static int binarySearch(int[] a, int key) { return binarySearch0(a, 0, a.length, key); } /** * Searches a range of * the specified array of ints for the specified value using the * binary search algorithm. * The range must be sorted (as * by the {@link #sort(int[], int, int)} method) * prior to making this call. If it * is not sorted, the results are undefined. If the range contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched * @param fromIndex the index of the first element (inclusive) to be * searched * @param toIndex the index of the last element (exclusive) to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array * within the specified range; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element in the range greater than the key, * or toIndex if all * elements in the range are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws IllegalArgumentException * if {@code fromIndex > toIndex} * @throws ArrayIndexOutOfBoundsException * if {@code fromIndex < 0 or toIndex > a.length} * @since 1.6 */ public static int binarySearch(int[] a, int fromIndex, int toIndex, int key) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); } // Like public version, but without range checks. private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; int midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array of shorts for the specified value using * the binary search algorithm. The array must be sorted * (as by the {@link #sort(short[])} method) prior to making this call. If * it is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. */ public static int binarySearch(short[] a, short key) { return binarySearch0(a, 0, a.length, key); } /** * Searches a range of * the specified array of shorts for the specified value using * the binary search algorithm. * The range must be sorted * (as by the {@link #sort(short[], int, int)} method) * prior to making this call. If * it is not sorted, the results are undefined. If the range contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched * @param fromIndex the index of the first element (inclusive) to be * searched * @param toIndex the index of the last element (exclusive) to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array * within the specified range; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element in the range greater than the key, * or toIndex if all * elements in the range are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws IllegalArgumentException * if {@code fromIndex > toIndex} * @throws ArrayIndexOutOfBoundsException * if {@code fromIndex < 0 or toIndex > a.length} * @since 1.6 */ public static int binarySearch(short[] a, int fromIndex, int toIndex, short key) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); } // Like public version, but without range checks. private static int binarySearch0(short[] a, int fromIndex, int toIndex, short key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; short midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array of chars for the specified value using the * binary search algorithm. The array must be sorted (as * by the {@link #sort(char[])} method) prior to making this call. If it * is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. */ public static int binarySearch(char[] a, char key) { return binarySearch0(a, 0, a.length, key); } /** * Searches a range of * the specified array of chars for the specified value using the * binary search algorithm. * The range must be sorted (as * by the {@link #sort(char[], int, int)} method) * prior to making this call. If it * is not sorted, the results are undefined. If the range contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched * @param fromIndex the index of the first element (inclusive) to be * searched * @param toIndex the index of the last element (exclusive) to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array * within the specified range; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element in the range greater than the key, * or toIndex if all * elements in the range are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws IllegalArgumentException * if {@code fromIndex > toIndex} * @throws ArrayIndexOutOfBoundsException * if {@code fromIndex < 0 or toIndex > a.length} * @since 1.6 */ public static int binarySearch(char[] a, int fromIndex, int toIndex, char key) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); } // Like public version, but without range checks. private static int binarySearch0(char[] a, int fromIndex, int toIndex, char key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; char midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array of bytes for the specified value using the * binary search algorithm. The array must be sorted (as * by the {@link #sort(byte[])} method) prior to making this call. If it * is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. */ public static int binarySearch(byte[] a, byte key) { return binarySearch0(a, 0, a.length, key); } /** * Searches a range of * the specified array of bytes for the specified value using the * binary search algorithm. * The range must be sorted (as * by the {@link #sort(byte[], int, int)} method) * prior to making this call. If it * is not sorted, the results are undefined. If the range contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched * @param fromIndex the index of the first element (inclusive) to be * searched * @param toIndex the index of the last element (exclusive) to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array * within the specified range; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element in the range greater than the key, * or toIndex if all * elements in the range are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws IllegalArgumentException * if {@code fromIndex > toIndex} * @throws ArrayIndexOutOfBoundsException * if {@code fromIndex < 0 or toIndex > a.length} * @since 1.6 */ public static int binarySearch(byte[] a, int fromIndex, int toIndex, byte key) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); } // Like public version, but without range checks. private static int binarySearch0(byte[] a, int fromIndex, int toIndex, byte key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; byte midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array of doubles for the specified value using * the binary search algorithm. The array must be sorted * (as by the {@link #sort(double[])} method) prior to making this call. * If it is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. This method considers all NaN values to be * equivalent and equal. * * @param a the array to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. */ public static int binarySearch(double[] a, double key) { return binarySearch0(a, 0, a.length, key); } /** * Searches a range of * the specified array of doubles for the specified value using * the binary search algorithm. * The range must be sorted * (as by the {@link #sort(double[], int, int)} method) * prior to making this call. * If it is not sorted, the results are undefined. If the range contains * multiple elements with the specified value, there is no guarantee which * one will be found. This method considers all NaN values to be * equivalent and equal. * * @param a the array to be searched * @param fromIndex the index of the first element (inclusive) to be * searched * @param toIndex the index of the last element (exclusive) to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array * within the specified range; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element in the range greater than the key, * or toIndex if all * elements in the range are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws IllegalArgumentException * if {@code fromIndex > toIndex} * @throws ArrayIndexOutOfBoundsException * if {@code fromIndex < 0 or toIndex > a.length} * @since 1.6 */ public static int binarySearch(double[] a, int fromIndex, int toIndex, double key) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); } // Like public version, but without range checks. private static int binarySearch0(double[] a, int fromIndex, int toIndex, double key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; double midVal = a[mid]; if (midVal < key) low = mid + 1; // Neither val is NaN, thisVal is smaller else if (midVal > key) high = mid - 1; // Neither val is NaN, thisVal is larger else { long midBits = Double.doubleToLongBits(midVal); long keyBits = Double.doubleToLongBits(key); if (midBits == keyBits) // Values are equal return mid; // Key found else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN) low = mid + 1; else // (0.0, -0.0) or (NaN, !NaN) high = mid - 1; } } return -(low + 1); // key not found. } /** * Searches the specified array of floats for the specified value using * the binary search algorithm. The array must be sorted * (as by the {@link #sort(float[])} method) prior to making this call. If * it is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. This method considers all NaN values to be * equivalent and equal. * * @param a the array to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. */ public static int binarySearch(float[] a, float key) { return binarySearch0(a, 0, a.length, key); } /** * Searches a range of * the specified array of floats for the specified value using * the binary search algorithm. * The range must be sorted * (as by the {@link #sort(float[], int, int)} method) * prior to making this call. If * it is not sorted, the results are undefined. If the range contains * multiple elements with the specified value, there is no guarantee which * one will be found. This method considers all NaN values to be * equivalent and equal. * * @param a the array to be searched * @param fromIndex the index of the first element (inclusive) to be * searched * @param toIndex the index of the last element (exclusive) to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array * within the specified range; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element in the range greater than the key, * or toIndex if all * elements in the range are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws IllegalArgumentException * if {@code fromIndex > toIndex} * @throws ArrayIndexOutOfBoundsException * if {@code fromIndex < 0 or toIndex > a.length} * @since 1.6 */ public static int binarySearch(float[] a, int fromIndex, int toIndex, float key) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); } // Like public version, but without range checks. private static int binarySearch0(float[] a, int fromIndex, int toIndex, float key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; float midVal = a[mid]; if (midVal < key) low = mid + 1; // Neither val is NaN, thisVal is smaller else if (midVal > key) high = mid - 1; // Neither val is NaN, thisVal is larger else { int midBits = Float.floatToIntBits(midVal); int keyBits = Float.floatToIntBits(key); if (midBits == keyBits) // Values are equal return mid; // Key found else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN) low = mid + 1; else // (0.0, -0.0) or (NaN, !NaN) high = mid - 1; } } return -(low + 1); // key not found. } /** * Searches the specified array for the specified object using the binary * search algorithm. The array must be sorted into ascending order * according to the * {@linkplain Comparable natural ordering} * of its elements (as by the * {@link #sort(Object[])} method) prior to making this call. * If it is not sorted, the results are undefined. * (If the array contains elements that are not mutually comparable (for * example, strings and integers), it cannot be sorted according * to the natural ordering of its elements, hence results are undefined.) * If the array contains multiple * elements equal to the specified object, there is no guarantee which * one will be found. * * @param a the array to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws ClassCastException if the search key is not comparable to the * elements of the array. */ public static int binarySearch(Object[] a, Object key) { return binarySearch0(a, 0, a.length, key); } /** * Searches a range of * the specified array for the specified object using the binary * search algorithm. * The range must be sorted into ascending order * according to the * {@linkplain Comparable natural ordering} * of its elements (as by the * {@link #sort(Object[], int, int)} method) prior to making this * call. If it is not sorted, the results are undefined. * (If the range contains elements that are not mutually comparable (for * example, strings and integers), it cannot be sorted according * to the natural ordering of its elements, hence results are undefined.) * If the range contains multiple * elements equal to the specified object, there is no guarantee which * one will be found. * * @param a the array to be searched * @param fromIndex the index of the first element (inclusive) to be * searched * @param toIndex the index of the last element (exclusive) to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array * within the specified range; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element in the range greater than the key, * or toIndex if all * elements in the range are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws ClassCastException if the search key is not comparable to the * elements of the array within the specified range. * @throws IllegalArgumentException * if {@code fromIndex > toIndex} * @throws ArrayIndexOutOfBoundsException * if {@code fromIndex < 0 or toIndex > a.length} * @since 1.6 */ public static int binarySearch(Object[] a, int fromIndex, int toIndex, Object key) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); } // Like public version, but without range checks. private static int binarySearch0(Object[] a, int fromIndex, int toIndex, Object key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; Comparable midVal = (Comparable)a[mid]; int cmp = midVal.compareTo(key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array for the specified object using the binary * search algorithm. The array must be sorted into ascending order * according to the specified comparator (as by the * {@link #sort(Object[], Comparator) sort(T[], Comparator)} * method) prior to making this call. If it is * not sorted, the results are undefined. * If the array contains multiple * elements equal to the specified object, there is no guarantee which one * will be found. * * @param a the array to be searched * @param key the value to be searched for * @param c the comparator by which the array is ordered. A * null value indicates that the elements' * {@linkplain Comparable natural ordering} should be used. * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws ClassCastException if the array contains elements that are not * mutually comparable using the specified comparator, * or the search key is not comparable to the * elements of the array using this comparator. */ public static int binarySearch(T[] a, T key, Comparator c) { return binarySearch0(a, 0, a.length, key, c); } /** * Searches a range of * the specified array for the specified object using the binary * search algorithm. * The range must be sorted into ascending order * according to the specified comparator (as by the * {@link #sort(Object[], int, int, Comparator) * sort(T[], int, int, Comparator)} * method) prior to making this call. * If it is not sorted, the results are undefined. * If the range contains multiple elements equal to the specified object, * there is no guarantee which one will be found. * * @param a the array to be searched * @param fromIndex the index of the first element (inclusive) to be * searched * @param toIndex the index of the last element (exclusive) to be searched * @param key the value to be searched for * @param c the comparator by which the array is ordered. A * null value indicates that the elements' * {@linkplain Comparable natural ordering} should be used. * @return index of the search key, if it is contained in the array * within the specified range; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element in the range greater than the key, * or toIndex if all * elements in the range are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws ClassCastException if the range contains elements that are not * mutually comparable using the specified comparator, * or the search key is not comparable to the * elements in the range using this comparator. * @throws IllegalArgumentException * if {@code fromIndex > toIndex} * @throws ArrayIndexOutOfBoundsException * if {@code fromIndex < 0 or toIndex > a.length} * @since 1.6 */ public static int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator c) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key, c); } // Like public version, but without range checks. private static int binarySearch0(T[] a, int fromIndex, int toIndex, T key, Comparator c) { if (c == null) { return binarySearch0(a, fromIndex, toIndex, key); } int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; T midVal = a[mid]; int cmp = c.compare(midVal, key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } // Equality Testing /** * Returns true if the two specified arrays of longs are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * @param a one array to be tested for equality * @param a2 the other array to be tested for equality * @return true if the two arrays are equal */ public static boolean equals(long[] a, long[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of ints are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * @param a one array to be tested for equality * @param a2 the other array to be tested for equality * @return true if the two arrays are equal */ public static boolean equals(int[] a, int[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of shorts are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * @param a one array to be tested for equality * @param a2 the other array to be tested for equality * @return true if the two arrays are equal */ public static boolean equals(short[] a, short a2[]) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of chars are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * @param a one array to be tested for equality * @param a2 the other array to be tested for equality * @return true if the two arrays are equal */ public static boolean equals(char[] a, char[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of bytes are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * @param a one array to be tested for equality * @param a2 the other array to be tested for equality * @return true if the two arrays are equal */ public static boolean equals(byte[] a, byte[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of booleans are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * @param a one array to be tested for equality * @param a2 the other array to be tested for equality * @return true if the two arrays are equal */ public static boolean equals(boolean[] a, boolean[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of doubles are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * Two doubles d1 and d2 are considered equal if: *

    new Double(d1).equals(new Double(d2))
* (Unlike the == operator, this method considers * NaN equals to itself, and 0.0d unequal to -0.0d.) * * @param a one array to be tested for equality * @param a2 the other array to be tested for equality * @return true if the two arrays are equal * @see Double#equals(Object) */ public static boolean equals(double[] a, double[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of floats are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * Two floats f1 and f2 are considered equal if: *

    new Float(f1).equals(new Float(f2))
* (Unlike the == operator, this method considers * NaN equals to itself, and 0.0f unequal to -0.0f.) * * @param a one array to be tested for equality * @param a2 the other array to be tested for equality * @return true if the two arrays are equal * @see Float#equals(Object) */ public static boolean equals(float[] a, float[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of Objects are * equal to one another. The two arrays are considered equal if * both arrays contain the same number of elements, and all corresponding * pairs of elements in the two arrays are equal. Two objects e1 * and e2 are considered equal if (e1==null ? e2==null * : e1.equals(e2)). In other words, the two arrays are equal if * they contain the same elements in the same order. Also, two array * references are considered equal if both are null.

* * @param a one array to be tested for equality * @param a2 the other array to be tested for equality * @return true if the two arrays are equal */ public static boolean equals(Object[] a, Object[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; ifromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value * @param toIndex the index of the last element (exclusive) to be * filled with the specified value * @param val the value to be stored in all elements of the array * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(long[] a, int fromIndex, int toIndex, long val) { rangeCheck(a.length, fromIndex, toIndex); for (int i = fromIndex; i < toIndex; i++) a[i] = val; } /** * Assigns the specified int value to each element of the specified array * of ints. * * @param a the array to be filled * @param val the value to be stored in all elements of the array */ public static void fill(int[] a, int val) { for (int i = 0, len = a.length; i < len; i++) a[i] = val; } /** * Assigns the specified int value to each element of the specified * range of the specified array of ints. The range to be filled * extends from index fromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value * @param toIndex the index of the last element (exclusive) to be * filled with the specified value * @param val the value to be stored in all elements of the array * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(int[] a, int fromIndex, int toIndex, int val) { rangeCheck(a.length, fromIndex, toIndex); for (int i = fromIndex; i < toIndex; i++) a[i] = val; } /** * Assigns the specified short value to each element of the specified array * of shorts. * * @param a the array to be filled * @param val the value to be stored in all elements of the array */ public static void fill(short[] a, short val) { for (int i = 0, len = a.length; i < len; i++) a[i] = val; } /** * Assigns the specified short value to each element of the specified * range of the specified array of shorts. The range to be filled * extends from index fromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value * @param toIndex the index of the last element (exclusive) to be * filled with the specified value * @param val the value to be stored in all elements of the array * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(short[] a, int fromIndex, int toIndex, short val) { rangeCheck(a.length, fromIndex, toIndex); for (int i = fromIndex; i < toIndex; i++) a[i] = val; } /** * Assigns the specified char value to each element of the specified array * of chars. * * @param a the array to be filled * @param val the value to be stored in all elements of the array */ public static void fill(char[] a, char val) { for (int i = 0, len = a.length; i < len; i++) a[i] = val; } /** * Assigns the specified char value to each element of the specified * range of the specified array of chars. The range to be filled * extends from index fromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value * @param toIndex the index of the last element (exclusive) to be * filled with the specified value * @param val the value to be stored in all elements of the array * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(char[] a, int fromIndex, int toIndex, char val) { rangeCheck(a.length, fromIndex, toIndex); for (int i = fromIndex; i < toIndex; i++) a[i] = val; } /** * Assigns the specified byte value to each element of the specified array * of bytes. * * @param a the array to be filled * @param val the value to be stored in all elements of the array */ public static void fill(byte[] a, byte val) { for (int i = 0, len = a.length; i < len; i++) a[i] = val; } /** * Assigns the specified byte value to each element of the specified * range of the specified array of bytes. The range to be filled * extends from index fromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value * @param toIndex the index of the last element (exclusive) to be * filled with the specified value * @param val the value to be stored in all elements of the array * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(byte[] a, int fromIndex, int toIndex, byte val) { rangeCheck(a.length, fromIndex, toIndex); for (int i = fromIndex; i < toIndex; i++) a[i] = val; } /** * Assigns the specified boolean value to each element of the specified * array of booleans. * * @param a the array to be filled * @param val the value to be stored in all elements of the array */ public static void fill(boolean[] a, boolean val) { for (int i = 0, len = a.length; i < len; i++) a[i] = val; } /** * Assigns the specified boolean value to each element of the specified * range of the specified array of booleans. The range to be filled * extends from index fromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value * @param toIndex the index of the last element (exclusive) to be * filled with the specified value * @param val the value to be stored in all elements of the array * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(boolean[] a, int fromIndex, int toIndex, boolean val) { rangeCheck(a.length, fromIndex, toIndex); for (int i = fromIndex; i < toIndex; i++) a[i] = val; } /** * Assigns the specified double value to each element of the specified * array of doubles. * * @param a the array to be filled * @param val the value to be stored in all elements of the array */ public static void fill(double[] a, double val) { for (int i = 0, len = a.length; i < len; i++) a[i] = val; } /** * Assigns the specified double value to each element of the specified * range of the specified array of doubles. The range to be filled * extends from index fromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value * @param toIndex the index of the last element (exclusive) to be * filled with the specified value * @param val the value to be stored in all elements of the array * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(double[] a, int fromIndex, int toIndex,double val){ rangeCheck(a.length, fromIndex, toIndex); for (int i = fromIndex; i < toIndex; i++) a[i] = val; } /** * Assigns the specified float value to each element of the specified array * of floats. * * @param a the array to be filled * @param val the value to be stored in all elements of the array */ public static void fill(float[] a, float val) { for (int i = 0, len = a.length; i < len; i++) a[i] = val; } /** * Assigns the specified float value to each element of the specified * range of the specified array of floats. The range to be filled * extends from index fromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value * @param toIndex the index of the last element (exclusive) to be * filled with the specified value * @param val the value to be stored in all elements of the array * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(float[] a, int fromIndex, int toIndex, float val) { rangeCheck(a.length, fromIndex, toIndex); for (int i = fromIndex; i < toIndex; i++) a[i] = val; } /** * Assigns the specified Object reference to each element of the specified * array of Objects. * * @param a the array to be filled * @param val the value to be stored in all elements of the array * @throws ArrayStoreException if the specified value is not of a * runtime type that can be stored in the specified array */ public static void fill(Object[] a, Object val) { for (int i = 0, len = a.length; i < len; i++) a[i] = val; } /** * Assigns the specified Object reference to each element of the specified * range of the specified array of Objects. The range to be filled * extends from index fromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value * @param toIndex the index of the last element (exclusive) to be * filled with the specified value * @param val the value to be stored in all elements of the array * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length * @throws ArrayStoreException if the specified value is not of a * runtime type that can be stored in the specified array */ public static void fill(Object[] a, int fromIndex, int toIndex, Object val) { rangeCheck(a.length, fromIndex, toIndex); for (int i = fromIndex; i < toIndex; i++) a[i] = val; } // Cloning /** * Copies the specified array, truncating or padding with nulls (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain null. * Such indices will exist if and only if the specified length * is greater than that of the original array. * The resulting array is of exactly the same class as the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with nulls * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass()); } /** * Copies the specified array, truncating or padding with nulls (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain null. * Such indices will exist if and only if the specified length * is greater than that of the original array. * The resulting array is of the class newType. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @param newType the class of the copy to be returned * @return a copy of the original array, truncated or padded with nulls * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @throws ArrayStoreException if an element copied from * original is not of a runtime type that can be stored in * an array of class newType * @since 1.6 */ public static T[] copyOf(U[] original, int newLength, Class newType) { T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with zeros (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain (byte)0. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with zeros * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static byte[] copyOf(byte[] original, int newLength) { byte[] copy = new byte[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with zeros (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain (short)0. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with zeros * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static short[] copyOf(short[] original, int newLength) { short[] copy = new short[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with zeros (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain 0. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with zeros * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static int[] copyOf(int[] original, int newLength) { int[] copy = new int[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with zeros (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain 0L. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with zeros * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static long[] copyOf(long[] original, int newLength) { long[] copy = new long[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with null characters (if necessary) * so the copy has the specified length. For all indices that are valid * in both the original array and the copy, the two arrays will contain * identical values. For any indices that are valid in the copy but not * the original, the copy will contain '\\u000'. Such indices * will exist if and only if the specified length is greater than that of * the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with null characters * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static char[] copyOf(char[] original, int newLength) { char[] copy = new char[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with zeros (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain 0f. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with zeros * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static float[] copyOf(float[] original, int newLength) { float[] copy = new float[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with zeros (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain 0d. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with zeros * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static double[] copyOf(double[] original, int newLength) { double[] copy = new double[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with false (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain false. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with false elements * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static boolean[] copyOf(boolean[] original, int newLength) { boolean[] copy = new boolean[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * null is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. *

* The resulting array is of exactly the same class as the original array. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with nulls to obtain the required length * @throws ArrayIndexOutOfBoundsException if {@code from < 0} * or {@code from > original.length} * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static T[] copyOfRange(T[] original, int from, int to) { return copyOfRange(original, from, to, (Class) original.getClass()); } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * null is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * The resulting array is of the class newType. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @param newType the class of the copy to be returned * @return a new array containing the specified range from the original array, * truncated or padded with nulls to obtain the required length * @throws ArrayIndexOutOfBoundsException if {@code from < 0} * or {@code from > original.length} * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @throws ArrayStoreException if an element copied from * original is not of a runtime type that can be stored in * an array of class newType. * @since 1.6 */ public static T[] copyOfRange(U[] original, int from, int to, Class newType) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * (byte)0 is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with zeros to obtain the required length * @throws ArrayIndexOutOfBoundsException if {@code from < 0} * or {@code from > original.length} * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static byte[] copyOfRange(byte[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); byte[] copy = new byte[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * (short)0 is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with zeros to obtain the required length * @throws ArrayIndexOutOfBoundsException if {@code from < 0} * or {@code from > original.length} * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static short[] copyOfRange(short[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); short[] copy = new short[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * 0 is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with zeros to obtain the required length * @throws ArrayIndexOutOfBoundsException if {@code from < 0} * or {@code from > original.length} * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static int[] copyOfRange(int[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); int[] copy = new int[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * 0L is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with zeros to obtain the required length * @throws ArrayIndexOutOfBoundsException if {@code from < 0} * or {@code from > original.length} * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static long[] copyOfRange(long[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); long[] copy = new long[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * '\\u000' is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with null characters to obtain the required length * @throws ArrayIndexOutOfBoundsException if {@code from < 0} * or {@code from > original.length} * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static char[] copyOfRange(char[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); char[] copy = new char[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * 0f is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with zeros to obtain the required length * @throws ArrayIndexOutOfBoundsException if {@code from < 0} * or {@code from > original.length} * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static float[] copyOfRange(float[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); float[] copy = new float[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * 0d is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with zeros to obtain the required length * @throws ArrayIndexOutOfBoundsException if {@code from < 0} * or {@code from > original.length} * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static double[] copyOfRange(double[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); double[] copy = new double[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * false is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with false elements to obtain the required length * @throws ArrayIndexOutOfBoundsException if {@code from < 0} * or {@code from > original.length} * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static boolean[] copyOfRange(boolean[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); boolean[] copy = new boolean[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } // Misc /** * Returns a fixed-size list backed by the specified array. (Changes to * the returned list "write through" to the array.) This method acts * as bridge between array-based and collection-based APIs, in * combination with {@link Collection#toArray}. The returned list is * serializable and implements {@link RandomAccess}. * *

This method also provides a convenient way to create a fixed-size * list initialized to contain several elements: *

     *     List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
     * 
* * @param a the array by which the list will be backed * @return a list view of the specified array */ @SafeVarargs public static List asList(T... a) { return new ArrayList<>(a); } /** * @serial include */ private static class ArrayList extends AbstractList implements RandomAccess, java.io.Serializable { private static final long serialVersionUID = -2764017481108945198L; private final E[] a; ArrayList(E[] array) { a = Objects.requireNonNull(array); } @Override public int size() { return a.length; } @Override public Object[] toArray() { return a.clone(); } @Override @SuppressWarnings("unchecked") public T[] toArray(T[] a) { int size = size(); if (a.length < size) return Arrays.copyOf(this.a, size, (Class) a.getClass()); System.arraycopy(this.a, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } @Override public E get(int index) { return a[index]; } @Override public E set(int index, E element) { E oldValue = a[index]; a[index] = element; return oldValue; } @Override public int indexOf(Object o) { if (o==null) { for (int i=0; i action) { Objects.requireNonNull(action); for (E e : a) { action.accept(e); } } @Override public void replaceAll(UnaryOperator operator) { Objects.requireNonNull(operator); E[] a = this.a; for (int i = 0; i < a.length; i++) { a[i] = operator.apply(a[i]); } } @Override public Spliterator spliterator() { return Spliterators.spliterator(a, Spliterator.ORDERED); } } /** * Returns a hash code based on the contents of the specified array. * For any two long arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Long} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(long a[]) { if (a == null) return 0; int result = 1; for (long element : a) { int elementHash = (int)(element ^ (element >>> 32)); result = 31 * result + elementHash; } return result; } /** * Returns a hash code based on the contents of the specified array. * For any two non-null int arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Integer} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(int a[]) { if (a == null) return 0; int result = 1; for (int element : a) result = 31 * result + element; return result; } /** * Returns a hash code based on the contents of the specified array. * For any two short arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Short} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(short a[]) { if (a == null) return 0; int result = 1; for (short element : a) result = 31 * result + element; return result; } /** * Returns a hash code based on the contents of the specified array. * For any two char arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Character} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(char a[]) { if (a == null) return 0; int result = 1; for (char element : a) result = 31 * result + element; return result; } /** * Returns a hash code based on the contents of the specified array. * For any two byte arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Byte} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(byte a[]) { if (a == null) return 0; int result = 1; for (byte element : a) result = 31 * result + element; return result; } /** * Returns a hash code based on the contents of the specified array. * For any two boolean arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Boolean} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(boolean a[]) { if (a == null) return 0; int result = 1; for (boolean element : a) result = 31 * result + (element ? 1231 : 1237); return result; } /** * Returns a hash code based on the contents of the specified array. * For any two float arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Float} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(float a[]) { if (a == null) return 0; int result = 1; for (float element : a) result = 31 * result + Float.floatToIntBits(element); return result; } /** * Returns a hash code based on the contents of the specified array. * For any two double arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Double} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(double a[]) { if (a == null) return 0; int result = 1; for (double element : a) { long bits = Double.doubleToLongBits(element); result = 31 * result + (int)(bits ^ (bits >>> 32)); } return result; } /** * Returns a hash code based on the contents of the specified array. If * the array contains other arrays as elements, the hash code is based on * their identities rather than their contents. It is therefore * acceptable to invoke this method on an array that contains itself as an * element, either directly or indirectly through one or more levels of * arrays. * *

For any two arrays a and b such that * Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is equal to the value that would * be returned by Arrays.asList(a).hashCode(), unless a * is null, in which case 0 is returned. * * @param a the array whose content-based hash code to compute * @return a content-based hash code for a * @see #deepHashCode(Object[]) * @since 1.5 */ public static int hashCode(Object a[]) { if (a == null) return 0; int result = 1; for (Object element : a) result = 31 * result + (element == null ? 0 : element.hashCode()); return result; } /** * Returns a hash code based on the "deep contents" of the specified * array. If the array contains other arrays as elements, the * hash code is based on their contents and so on, ad infinitum. * It is therefore unacceptable to invoke this method on an array that * contains itself as an element, either directly or indirectly through * one or more levels of arrays. The behavior of such an invocation is * undefined. * *

For any two arrays a and b such that * Arrays.deepEquals(a, b), it is also the case that * Arrays.deepHashCode(a) == Arrays.deepHashCode(b). * *

The computation of the value returned by this method is similar to * that of the value returned by {@link List#hashCode()} on a list * containing the same elements as a in the same order, with one * difference: If an element e of a is itself an array, * its hash code is computed not by calling e.hashCode(), but as * by calling the appropriate overloading of Arrays.hashCode(e) * if e is an array of a primitive type, or as by calling * Arrays.deepHashCode(e) recursively if e is an array * of a reference type. If a is null, this method * returns 0. * * @param a the array whose deep-content-based hash code to compute * @return a deep-content-based hash code for a * @see #hashCode(Object[]) * @since 1.5 */ public static int deepHashCode(Object a[]) { if (a == null) return 0; int result = 1; for (Object element : a) { int elementHash = 0; if (element != null) { Class cl = element.getClass().getComponentType(); if (cl == null) elementHash = element.hashCode(); else if (element instanceof Object[]) elementHash = deepHashCode((Object[]) element); else if (cl == byte.class) elementHash = hashCode((byte[]) element); else if (cl == short.class) elementHash = hashCode((short[]) element); else if (cl == int.class) elementHash = hashCode((int[]) element); else if (cl == long.class) elementHash = hashCode((long[]) element); else if (cl == char.class) elementHash = hashCode((char[]) element); else if (cl == float.class) elementHash = hashCode((float[]) element); else if (cl == double.class) elementHash = hashCode((double[]) element); else if (cl == boolean.class) elementHash = hashCode((boolean[]) element); else elementHash = element.hashCode(); } result = 31 * result + elementHash; } return result; } /** * Returns true if the two specified arrays are deeply * equal to one another. Unlike the {@link #equals(Object[],Object[])} * method, this method is appropriate for use with nested arrays of * arbitrary depth. * *

Two array references are considered deeply equal if both * are null, or if they refer to arrays that contain the same * number of elements and all corresponding pairs of elements in the two * arrays are deeply equal. * *

Two possibly null elements e1 and e2 are * deeply equal if any of the following conditions hold: *

    *
  • e1 and e2 are both arrays of object reference * types, and Arrays.deepEquals(e1, e2) would return true *
  • e1 and e2 are arrays of the same primitive * type, and the appropriate overloading of * Arrays.equals(e1, e2) would return true. *
  • e1 == e2 *
  • e1.equals(e2) would return true. *
* Note that this definition permits null elements at any depth. * *

If either of the specified arrays contain themselves as elements * either directly or indirectly through one or more levels of arrays, * the behavior of this method is undefined. * * @param a1 one array to be tested for equality * @param a2 the other array to be tested for equality * @return true if the two arrays are equal * @see #equals(Object[],Object[]) * @see Objects#deepEquals(Object, Object) * @since 1.5 */ public static boolean deepEquals(Object[] a1, Object[] a2) { if (a1 == a2) return true; if (a1 == null || a2==null) return false; int length = a1.length; if (a2.length != length) return false; for (int i = 0; i < length; i++) { Object e1 = a1[i]; Object e2 = a2[i]; if (e1 == e2) continue; if (e1 == null || e2 == null) return false; // Figure out whether the two elements are equal boolean eq = deepEquals0(e1, e2); if (!eq) return false; } return true; } static boolean deepEquals0(Object e1, Object e2) { Class cl1 = e1.getClass().getComponentType(); Class cl2 = e2.getClass().getComponentType(); if (cl1 != cl2) { return false; } if (e1 instanceof Object[]) return deepEquals ((Object[]) e1, (Object[]) e2); else if (cl1 == byte.class) return equals((byte[]) e1, (byte[]) e2); else if (cl1 == short.class) return equals((short[]) e1, (short[]) e2); else if (cl1 == int.class) return equals((int[]) e1, (int[]) e2); else if (cl1 == long.class) return equals((long[]) e1, (long[]) e2); else if (cl1 == char.class) return equals((char[]) e1, (char[]) e2); else if (cl1 == float.class) return equals((float[]) e1, (float[]) e2); else if (cl1 == double.class) return equals((double[]) e1, (double[]) e2); else if (cl1 == boolean.class) return equals((boolean[]) e1, (boolean[]) e2); else return e1.equals(e2); } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(long). Returns "null" if a * is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(long[] a) { if (a == null) return "null"; int iMax = a.length - 1; if (iMax == -1) return "[]"; StringBuilder b = new StringBuilder(); b.append('['); for (int i = 0; ; i++) { b.append(a[i]); if (i == iMax) return b.append(']').toString(); b.append(", "); } } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(int). Returns "null" if a is * null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(int[] a) { if (a == null) return "null"; int iMax = a.length - 1; if (iMax == -1) return "[]"; StringBuilder b = new StringBuilder(); b.append('['); for (int i = 0; ; i++) { b.append(a[i]); if (i == iMax) return b.append(']').toString(); b.append(", "); } } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(short). Returns "null" if a * is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(short[] a) { if (a == null) return "null"; int iMax = a.length - 1; if (iMax == -1) return "[]"; StringBuilder b = new StringBuilder(); b.append('['); for (int i = 0; ; i++) { b.append(a[i]); if (i == iMax) return b.append(']').toString(); b.append(", "); } } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(char). Returns "null" if a * is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(char[] a) { if (a == null) return "null"; int iMax = a.length - 1; if (iMax == -1) return "[]"; StringBuilder b = new StringBuilder(); b.append('['); for (int i = 0; ; i++) { b.append(a[i]); if (i == iMax) return b.append(']').toString(); b.append(", "); } } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements * are separated by the characters ", " (a comma followed * by a space). Elements are converted to strings as by * String.valueOf(byte). Returns "null" if * a is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(byte[] a) { if (a == null) return "null"; int iMax = a.length - 1; if (iMax == -1) return "[]"; StringBuilder b = new StringBuilder(); b.append('['); for (int i = 0; ; i++) { b.append(a[i]); if (i == iMax) return b.append(']').toString(); b.append(", "); } } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(boolean). Returns "null" if * a is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(boolean[] a) { if (a == null) return "null"; int iMax = a.length - 1; if (iMax == -1) return "[]"; StringBuilder b = new StringBuilder(); b.append('['); for (int i = 0; ; i++) { b.append(a[i]); if (i == iMax) return b.append(']').toString(); b.append(", "); } } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(float). Returns "null" if a * is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(float[] a) { if (a == null) return "null"; int iMax = a.length - 1; if (iMax == -1) return "[]"; StringBuilder b = new StringBuilder(); b.append('['); for (int i = 0; ; i++) { b.append(a[i]); if (i == iMax) return b.append(']').toString(); b.append(", "); } } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(double). Returns "null" if a * is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(double[] a) { if (a == null) return "null"; int iMax = a.length - 1; if (iMax == -1) return "[]"; StringBuilder b = new StringBuilder(); b.append('['); for (int i = 0; ; i++) { b.append(a[i]); if (i == iMax) return b.append(']').toString(); b.append(", "); } } /** * Returns a string representation of the contents of the specified array. * If the array contains other arrays as elements, they are converted to * strings by the {@link Object#toString} method inherited from * Object, which describes their identities rather than * their contents. * *

The value returned by this method is equal to the value that would * be returned by Arrays.asList(a).toString(), unless a * is null, in which case "null" is returned. * * @param a the array whose string representation to return * @return a string representation of a * @see #deepToString(Object[]) * @since 1.5 */ public static String toString(Object[] a) { if (a == null) return "null"; int iMax = a.length - 1; if (iMax == -1) return "[]"; StringBuilder b = new StringBuilder(); b.append('['); for (int i = 0; ; i++) { b.append(String.valueOf(a[i])); if (i == iMax) return b.append(']').toString(); b.append(", "); } } /** * Returns a string representation of the "deep contents" of the specified * array. If the array contains other arrays as elements, the string * representation contains their contents and so on. This method is * designed for converting multidimensional arrays to strings. * *

The string representation consists of a list of the array's * elements, enclosed in square brackets ("[]"). Adjacent * elements are separated by the characters ", " (a comma * followed by a space). Elements are converted to strings as by * String.valueOf(Object), unless they are themselves * arrays. * *

If an element e is an array of a primitive type, it is * converted to a string as by invoking the appropriate overloading of * Arrays.toString(e). If an element e is an array of a * reference type, it is converted to a string as by invoking * this method recursively. * *

To avoid infinite recursion, if the specified array contains itself * as an element, or contains an indirect reference to itself through one * or more levels of arrays, the self-reference is converted to the string * "[...]". For example, an array containing only a reference * to itself would be rendered as "[[...]]". * *

This method returns "null" if the specified array * is null. * * @param a the array whose string representation to return * @return a string representation of a * @see #toString(Object[]) * @since 1.5 */ public static String deepToString(Object[] a) { if (a == null) return "null"; int bufLen = 20 * a.length; if (a.length != 0 && bufLen <= 0) bufLen = Integer.MAX_VALUE; StringBuilder buf = new StringBuilder(bufLen); deepToString(a, buf, new HashSet()); return buf.toString(); } private static void deepToString(Object[] a, StringBuilder buf, Set dejaVu) { if (a == null) { buf.append("null"); return; } int iMax = a.length - 1; if (iMax == -1) { buf.append("[]"); return; } dejaVu.add(a); buf.append('['); for (int i = 0; ; i++) { Object element = a[i]; if (element == null) { buf.append("null"); } else { Class eClass = element.getClass(); if (eClass.isArray()) { if (eClass == byte[].class) buf.append(toString((byte[]) element)); else if (eClass == short[].class) buf.append(toString((short[]) element)); else if (eClass == int[].class) buf.append(toString((int[]) element)); else if (eClass == long[].class) buf.append(toString((long[]) element)); else if (eClass == char[].class) buf.append(toString((char[]) element)); else if (eClass == float[].class) buf.append(toString((float[]) element)); else if (eClass == double[].class) buf.append(toString((double[]) element)); else if (eClass == boolean[].class) buf.append(toString((boolean[]) element)); else { // element is an array of object references if (dejaVu.contains(element)) buf.append("[...]"); else deepToString((Object[])element, buf, dejaVu); } } else { // element is non-null and not an array buf.append(element.toString()); } } if (i == iMax) break; buf.append(", "); } buf.append(']'); dejaVu.remove(a); } /** * Set all elements of the specified array, using the provided * generator function to compute each element. * *

If the generator function throws an exception, it is relayed to * the caller and the array is left in an indeterminate state. * * @param type of elements of the array * @param array array to be initialized * @param generator a function accepting an index and producing the desired * value for that position * @throws NullPointerException if the generator is null * @since 1.8 */ public static void setAll(T[] array, IntFunction generator) { Objects.requireNonNull(generator); for (int i = 0; i < array.length; i++) array[i] = generator.apply(i); } /** * Set all elements of the specified array, in parallel, using the * provided generator function to compute each element. * *

If the generator function throws an exception, an unchecked exception * is thrown from {@code parallelSetAll} and the array is left in an * indeterminate state. * * @param type of elements of the array * @param array array to be initialized * @param generator a function accepting an index and producing the desired * value for that position * @throws NullPointerException if the generator is null * @since 1.8 */ public static void parallelSetAll(T[] array, IntFunction generator) { Objects.requireNonNull(generator); IntStream.range(0, array.length).parallel().forEach(i -> { array[i] = generator.apply(i); }); } /** * Set all elements of the specified array, using the provided * generator function to compute each element. * *

If the generator function throws an exception, it is relayed to * the caller and the array is left in an indeterminate state. * * @param array array to be initialized * @param generator a function accepting an index and producing the desired * value for that position * @throws NullPointerException if the generator is null * @since 1.8 */ public static void setAll(int[] array, IntUnaryOperator generator) { Objects.requireNonNull(generator); for (int i = 0; i < array.length; i++) array[i] = generator.applyAsInt(i); } /** * Set all elements of the specified array, in parallel, using the * provided generator function to compute each element. * *

If the generator function throws an exception, an unchecked exception * is thrown from {@code parallelSetAll} and the array is left in an * indeterminate state. * * @param array array to be initialized * @param generator a function accepting an index and producing the desired * value for that position * @throws NullPointerException if the generator is null * @since 1.8 */ public static void parallelSetAll(int[] array, IntUnaryOperator generator) { Objects.requireNonNull(generator); IntStream.range(0, array.length).parallel().forEach(i -> { array[i] = generator.applyAsInt(i); }); } /** * Set all elements of the specified array, using the provided * generator function to compute each element. * *

If the generator function throws an exception, it is relayed to * the caller and the array is left in an indeterminate state. * * @param array array to be initialized * @param generator a function accepting an index and producing the desired * value for that position * @throws NullPointerException if the generator is null * @since 1.8 */ public static void setAll(long[] array, IntToLongFunction generator) { Objects.requireNonNull(generator); for (int i = 0; i < array.length; i++) array[i] = generator.applyAsLong(i); } /** * Set all elements of the specified array, in parallel, using the * provided generator function to compute each element. * *

If the generator function throws an exception, an unchecked exception * is thrown from {@code parallelSetAll} and the array is left in an * indeterminate state. * * @param array array to be initialized * @param generator a function accepting an index and producing the desired * value for that position * @throws NullPointerException if the generator is null * @since 1.8 */ public static void parallelSetAll(long[] array, IntToLongFunction generator) { Objects.requireNonNull(generator); IntStream.range(0, array.length).parallel().forEach(i -> { array[i] = generator.applyAsLong(i); }); } /** * Set all elements of the specified array, using the provided * generator function to compute each element. * *

If the generator function throws an exception, it is relayed to * the caller and the array is left in an indeterminate state. * * @param array array to be initialized * @param generator a function accepting an index and producing the desired * value for that position * @throws NullPointerException if the generator is null * @since 1.8 */ public static void setAll(double[] array, IntToDoubleFunction generator) { Objects.requireNonNull(generator); for (int i = 0; i < array.length; i++) array[i] = generator.applyAsDouble(i); } /** * Set all elements of the specified array, in parallel, using the * provided generator function to compute each element. * *

If the generator function throws an exception, an unchecked exception * is thrown from {@code parallelSetAll} and the array is left in an * indeterminate state. * * @param array array to be initialized * @param generator a function accepting an index and producing the desired * value for that position * @throws NullPointerException if the generator is null * @since 1.8 */ public static void parallelSetAll(double[] array, IntToDoubleFunction generator) { Objects.requireNonNull(generator); IntStream.range(0, array.length).parallel().forEach(i -> { array[i] = generator.applyAsDouble(i); }); } /** * Checks that the range described by {@code offset} and {@code count} doesn't exceed * {@code arrayLength}. * * Android changed. * @hide */ public static void checkOffsetAndCount(int arrayLength, int offset, int count) { if ((offset | count) < 0 || offset > arrayLength || arrayLength - offset < count) { throw new ArrayIndexOutOfBoundsException(arrayLength, offset, count); } } /** * Returns a {@link Spliterator} covering all of the specified array. * *

The spliterator reports {@link Spliterator#SIZED}, * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and * {@link Spliterator#IMMUTABLE}. * * @param type of elements * @param array the array, assumed to be unmodified during use * @return a spliterator for the array elements * @since 1.8 */ public static Spliterator spliterator(T[] array) { return Spliterators.spliterator(array, Spliterator.ORDERED | Spliterator.IMMUTABLE); } /** * Returns a {@link Spliterator} covering the specified range of the * specified array. * *

The spliterator reports {@link Spliterator#SIZED}, * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and * {@link Spliterator#IMMUTABLE}. * * @param type of elements * @param array the array, assumed to be unmodified during use * @param startInclusive the first index to cover, inclusive * @param endExclusive index immediately past the last index to cover * @return a spliterator for the array elements * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is * negative, {@code endExclusive} is less than * {@code startInclusive}, or {@code endExclusive} is greater than * the array size * @since 1.8 */ public static Spliterator spliterator(T[] array, int startInclusive, int endExclusive) { return Spliterators.spliterator(array, startInclusive, endExclusive, Spliterator.ORDERED | Spliterator.IMMUTABLE); } /** * Returns a {@link Spliterator.OfInt} covering all of the specified array. * *

The spliterator reports {@link Spliterator#SIZED}, * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and * {@link Spliterator#IMMUTABLE}. * * @param array the array, assumed to be unmodified during use * @return a spliterator for the array elements * @since 1.8 */ public static Spliterator.OfInt spliterator(int[] array) { return Spliterators.spliterator(array, Spliterator.ORDERED | Spliterator.IMMUTABLE); } /** * Returns a {@link Spliterator.OfInt} covering the specified range of the * specified array. * *

The spliterator reports {@link Spliterator#SIZED}, * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and * {@link Spliterator#IMMUTABLE}. * * @param array the array, assumed to be unmodified during use * @param startInclusive the first index to cover, inclusive * @param endExclusive index immediately past the last index to cover * @return a spliterator for the array elements * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is * negative, {@code endExclusive} is less than * {@code startInclusive}, or {@code endExclusive} is greater than * the array size * @since 1.8 */ public static Spliterator.OfInt spliterator(int[] array, int startInclusive, int endExclusive) { return Spliterators.spliterator(array, startInclusive, endExclusive, Spliterator.ORDERED | Spliterator.IMMUTABLE); } /** * Returns a {@link Spliterator.OfLong} covering all of the specified array. * *

The spliterator reports {@link Spliterator#SIZED}, * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and * {@link Spliterator#IMMUTABLE}. * * @param array the array, assumed to be unmodified during use * @return the spliterator for the array elements * @since 1.8 */ public static Spliterator.OfLong spliterator(long[] array) { return Spliterators.spliterator(array, Spliterator.ORDERED | Spliterator.IMMUTABLE); } /** * Returns a {@link Spliterator.OfLong} covering the specified range of the * specified array. * *

The spliterator reports {@link Spliterator#SIZED}, * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and * {@link Spliterator#IMMUTABLE}. * * @param array the array, assumed to be unmodified during use * @param startInclusive the first index to cover, inclusive * @param endExclusive index immediately past the last index to cover * @return a spliterator for the array elements * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is * negative, {@code endExclusive} is less than * {@code startInclusive}, or {@code endExclusive} is greater than * the array size * @since 1.8 */ public static Spliterator.OfLong spliterator(long[] array, int startInclusive, int endExclusive) { return Spliterators.spliterator(array, startInclusive, endExclusive, Spliterator.ORDERED | Spliterator.IMMUTABLE); } /** * Returns a {@link Spliterator.OfDouble} covering all of the specified * array. * *

The spliterator reports {@link Spliterator#SIZED}, * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and * {@link Spliterator#IMMUTABLE}. * * @param array the array, assumed to be unmodified during use * @return a spliterator for the array elements * @since 1.8 */ public static Spliterator.OfDouble spliterator(double[] array) { return Spliterators.spliterator(array, Spliterator.ORDERED | Spliterator.IMMUTABLE); } /** * Returns a {@link Spliterator.OfDouble} covering the specified range of * the specified array. * *

The spliterator reports {@link Spliterator#SIZED}, * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and * {@link Spliterator#IMMUTABLE}. * * @param array the array, assumed to be unmodified during use * @param startInclusive the first index to cover, inclusive * @param endExclusive index immediately past the last index to cover * @return a spliterator for the array elements * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is * negative, {@code endExclusive} is less than * {@code startInclusive}, or {@code endExclusive} is greater than * the array size * @since 1.8 */ public static Spliterator.OfDouble spliterator(double[] array, int startInclusive, int endExclusive) { return Spliterators.spliterator(array, startInclusive, endExclusive, Spliterator.ORDERED | Spliterator.IMMUTABLE); } /** * Returns a sequential {@link Stream} with the specified array as its * source. * * @param The type of the array elements * @param array The array, assumed to be unmodified during use * @return a {@code Stream} for the array * @since 1.8 */ public static Stream stream(T[] array) { return stream(array, 0, array.length); } /** * Returns a sequential {@link Stream} with the specified range of the * specified array as its source. * * @param the type of the array elements * @param array the array, assumed to be unmodified during use * @param startInclusive the first index to cover, inclusive * @param endExclusive index immediately past the last index to cover * @return a {@code Stream} for the array range * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is * negative, {@code endExclusive} is less than * {@code startInclusive}, or {@code endExclusive} is greater than * the array size * @since 1.8 */ public static Stream stream(T[] array, int startInclusive, int endExclusive) { return StreamSupport.stream(spliterator(array, startInclusive, endExclusive), false); } /** * Returns a sequential {@link IntStream} with the specified array as its * source. * * @param array the array, assumed to be unmodified during use * @return an {@code IntStream} for the array * @since 1.8 */ public static IntStream stream(int[] array) { return stream(array, 0, array.length); } /** * Returns a sequential {@link IntStream} with the specified range of the * specified array as its source. * * @param array the array, assumed to be unmodified during use * @param startInclusive the first index to cover, inclusive * @param endExclusive index immediately past the last index to cover * @return an {@code IntStream} for the array range * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is * negative, {@code endExclusive} is less than * {@code startInclusive}, or {@code endExclusive} is greater than * the array size * @since 1.8 */ public static IntStream stream(int[] array, int startInclusive, int endExclusive) { return StreamSupport.intStream(spliterator(array, startInclusive, endExclusive), false); } /** * Returns a sequential {@link LongStream} with the specified array as its * source. * * @param array the array, assumed to be unmodified during use * @return a {@code LongStream} for the array * @since 1.8 */ public static LongStream stream(long[] array) { return stream(array, 0, array.length); } /** * Returns a sequential {@link LongStream} with the specified range of the * specified array as its source. * * @param array the array, assumed to be unmodified during use * @param startInclusive the first index to cover, inclusive * @param endExclusive index immediately past the last index to cover * @return a {@code LongStream} for the array range * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is * negative, {@code endExclusive} is less than * {@code startInclusive}, or {@code endExclusive} is greater than * the array size * @since 1.8 */ public static LongStream stream(long[] array, int startInclusive, int endExclusive) { return StreamSupport.longStream(spliterator(array, startInclusive, endExclusive), false); } /** * Returns a sequential {@link DoubleStream} with the specified array as its * source. * * @param array the array, assumed to be unmodified during use * @return a {@code DoubleStream} for the array * @since 1.8 */ public static DoubleStream stream(double[] array) { return stream(array, 0, array.length); } /** * Returns a sequential {@link DoubleStream} with the specified range of the * specified array as its source. * * @param array the array, assumed to be unmodified during use * @param startInclusive the first index to cover, inclusive * @param endExclusive index immediately past the last index to cover * @return a {@code DoubleStream} for the array range * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is * negative, {@code endExclusive} is less than * {@code startInclusive}, or {@code endExclusive} is greater than * the array size * @since 1.8 */ public static DoubleStream stream(double[] array, int startInclusive, int endExclusive) { return StreamSupport.doubleStream(spliterator(array, startInclusive, endExclusive), false); } }