Skip to content

Instantly share code, notes, and snippets.

@gfx

gfx/jdk7.Arrays.java.diff

Last active March 12, 2016 07:59
Show Gist options
  • Save gfx/5f5a8aaa964d4a4c2645 to your computer and use it in GitHub Desktop.
Save gfx/5f5a8aaa964d4a4c2645 to your computer and use it in GitHub Desktop.
Download ZIP
Diff $openjdk/Arrays.java $android_n_preview/Arrays.java
Raw
jdk7.Arrays.java.diff
# diff for
# http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/default/src/share/classes/java/util/Arrays.java
# https://android.googlesource.com/platform/libcore/+/android-n-preview-1/ojluni/src/main/java/java/util/Arrays.java
diff --git a/jdk7.Arrays.java b/libcore/ojluni/src/main/java/java/util/Arrays.java
old mode 100644
new mode 100755
index fd408e2..c04d6cf
--- a/jdk7.Array.java
+++ b/libcore/ojluni/src/main/java/java/util/Arrays.java
@@ -1,4 +1,5 @@
/*
+ * Copyright (C) 2014 The Android Open Source Project
* Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
@@ -26,6 +27,7 @@
package java.util;
import java.lang.reflect.*;
+import java.util.function.Consumer;
/**
* This class contains various methods for manipulating arrays (such as
@@ -73,7 +75,7 @@ private Arrays() {}
* @param a the array to be sorted
*/
public static void sort(int[] a) {
- DualPivotQuicksort.sort(a);
+ DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
/**
@@ -98,7 +100,7 @@ public static void sort(int[] a) {
*/
public static void sort(int[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
- DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+ DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
/**
@@ -113,7 +115,7 @@ public static void sort(int[] a, int fromIndex, int toIndex) {
* @param a the array to be sorted
*/
public static void sort(long[] a) {
- DualPivotQuicksort.sort(a);
+ DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
/**
@@ -138,7 +140,7 @@ public static void sort(long[] a) {
*/
public static void sort(long[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
- DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+ DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
/**
@@ -153,7 +155,7 @@ public static void sort(long[] a, int fromIndex, int toIndex) {
* @param a the array to be sorted
*/
public static void sort(short[] a) {
- DualPivotQuicksort.sort(a);
+ DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
/**
@@ -178,7 +180,7 @@ public static void sort(short[] a) {
*/
public static void sort(short[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
- DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+ DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
/**
@@ -193,7 +195,7 @@ public static void sort(short[] a, int fromIndex, int toIndex) {
* @param a the array to be sorted
*/
public static void sort(char[] a) {
- DualPivotQuicksort.sort(a);
+ DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
/**
@@ -218,7 +220,7 @@ public static void sort(char[] a) {
*/
public static void sort(char[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
- DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+ DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
/**
@@ -233,7 +235,7 @@ public static void sort(char[] a, int fromIndex, int toIndex) {
* @param a the array to be sorted
*/
public static void sort(byte[] a) {
- DualPivotQuicksort.sort(a);
+ DualPivotQuicksort.sort(a, 0, a.length - 1);
}
/**
@@ -281,7 +283,7 @@ public static void sort(byte[] a, int fromIndex, int toIndex) {
* @param a the array to be sorted
*/
public static void sort(float[] a) {
- DualPivotQuicksort.sort(a);
+ DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
/**
@@ -314,7 +316,7 @@ public static void sort(float[] a) {
*/
public static void sort(float[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
- DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+ DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
/**
@@ -337,7 +339,7 @@ public static void sort(float[] a, int fromIndex, int toIndex) {
* @param a the array to be sorted
*/
public static void sort(double[] a) {
- DualPivotQuicksort.sort(a);
+ DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
/**
@@ -370,7 +372,7 @@ public static void sort(double[] a) {
*/
public static void sort(double[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
- DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+ DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}
/*
@@ -384,10 +386,8 @@ public static void sort(double[] a, int fromIndex, int toIndex) {
* circular dependencies. To be removed in a future release.
*/
static final class LegacyMergeSort {
- private static final boolean userRequested =
- java.security.AccessController.doPrivileged(
- new sun.security.action.GetBooleanAction(
- "java.util.Arrays.useLegacyMergeSort")).booleanValue();
+ // Android-changed: Never use circular merge sort.
+ private static final boolean userRequested = false;
}
/*
@@ -469,7 +469,7 @@ public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
- ComparableTimSort.sort(a);
+ ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
/** To be removed in a future release. */
@@ -531,10 +531,11 @@ private static void legacyMergeSort(Object[] a) {
* 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);
+ ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
}
/** To be removed in a future release. */
@@ -653,10 +654,14 @@ private static void swap(Object[] x, int a, int b) {
* found to violate the {@link Comparator} contract
*/
public static <T> void sort(T[] a, Comparator<? super T> c) {
- if (LegacyMergeSort.userRequested)
- legacyMergeSort(a, c);
- else
- TimSort.sort(a, 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. */
@@ -721,10 +726,15 @@ private static void swap(Object[] x, int a, int b) {
*/
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
- if (LegacyMergeSort.userRequested)
- legacyMergeSort(a, fromIndex, toIndex, c);
- else
- TimSort.sort(a, fromIndex, toIndex, 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. */
@@ -3179,27 +3189,31 @@ public static int deepHashCode(Object a[]) {
for (Object element : a) {
int elementHash = 0;
- if (element instanceof Object[])
- elementHash = deepHashCode((Object[]) element);
- else if (element instanceof byte[])
- elementHash = hashCode((byte[]) element);
- else if (element instanceof short[])
- elementHash = hashCode((short[]) element);
- else if (element instanceof int[])
- elementHash = hashCode((int[]) element);
- else if (element instanceof long[])
- elementHash = hashCode((long[]) element);
- else if (element instanceof char[])
- elementHash = hashCode((char[]) element);
- else if (element instanceof float[])
- elementHash = hashCode((float[]) element);
- else if (element instanceof double[])
- elementHash = hashCode((double[]) element);
- else if (element instanceof boolean[])
- elementHash = hashCode((boolean[]) element);
- else if (element != null)
- elementHash = element.hashCode();
-
+ 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;
}
@@ -3256,7 +3270,7 @@ public static boolean deepEquals(Object[] a1, Object[] a2) {
if (e1 == e2)
continue;
- if (e1 == null)
+ if (e1 == null || e2 == null)
return false;
// Figure out whether the two elements are equal
@@ -3269,29 +3283,32 @@ public static boolean deepEquals(Object[] a1, Object[] a2) {
}
static boolean deepEquals0(Object e1, Object e2) {
- assert e1 != null;
- boolean eq;
- if (e1 instanceof Object[] && e2 instanceof Object[])
- eq = deepEquals ((Object[]) e1, (Object[]) e2);
- else if (e1 instanceof byte[] && e2 instanceof byte[])
- eq = equals((byte[]) e1, (byte[]) e2);
- else if (e1 instanceof short[] && e2 instanceof short[])
- eq = equals((short[]) e1, (short[]) e2);
- else if (e1 instanceof int[] && e2 instanceof int[])
- eq = equals((int[]) e1, (int[]) e2);
- else if (e1 instanceof long[] && e2 instanceof long[])
- eq = equals((long[]) e1, (long[]) e2);
- else if (e1 instanceof char[] && e2 instanceof char[])
- eq = equals((char[]) e1, (char[]) e2);
- else if (e1 instanceof float[] && e2 instanceof float[])
- eq = equals((float[]) e1, (float[]) e2);
- else if (e1 instanceof double[] && e2 instanceof double[])
- eq = equals((double[]) e1, (double[]) e2);
- else if (e1 instanceof boolean[] && e2 instanceof boolean[])
- eq = equals((boolean[]) e1, (boolean[]) 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
- eq = e1.equals(e2);
- return eq;
+ return e1.equals(e2);
}
/**
@@ -3670,4 +3687,18 @@ else if (eClass == boolean[].class)
buf.append(']');
dejaVu.remove(a);
}
+
+ /**
+ * 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);
+ }
+ }
}
Raw
jdk8.Arrays.java.diff
# diff for
# http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/default/src/share/classes/java/util/Arrays.java
# https://android.googlesource.com/platform/libcore/+/android-n-preview-1/ojluni/src/main/java/java/util/Arrays.java
diff --git a/jdk8.Arrays.java b/libcore/ojluni/src/main/java/java/util/Arrays.java
old mode 100644
new mode 100755
index c620c81..c04d6cf
--- a/jdk8.Arrays.java
+++ b/libcore/ojluni/src/main/java/java/util/Arrays.java
@@ -1,5 +1,6 @@
/*
- * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (C) 2014 The Android Open Source Project
+ * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -25,21 +26,8 @@
package java.util;
-import java.lang.reflect.Array;
-import java.util.concurrent.ForkJoinPool;
-import java.util.function.BinaryOperator;
-import java.util.function.DoubleBinaryOperator;
-import java.util.function.IntBinaryOperator;
-import java.util.function.IntFunction;
-import java.util.function.IntToDoubleFunction;
-import java.util.function.IntToLongFunction;
-import java.util.function.IntUnaryOperator;
-import java.util.function.LongBinaryOperator;
-import java.util.stream.DoubleStream;
-import java.util.stream.IntStream;
-import java.util.stream.LongStream;
-import java.util.stream.Stream;
-import java.util.stream.StreamSupport;
+import java.lang.reflect.*;
+import java.util.function.Consumer;
/**
* This class contains various methods for manipulating arrays (such as
@@ -68,63 +56,11 @@
*/
public class Arrays {
- /**
- * The minimum array length below which a parallel sorting
- * algorithm will not further partition the sorting task. Using
- * smaller sizes typically results in memory contention across
- * tasks that makes parallel speedups unlikely.
- */
- private static final int MIN_ARRAY_SORT_GRAN = 1 << 13;
-
// Suppresses default constructor, ensuring non-instantiability.
private Arrays() {}
- /**
- * A comparator that implements the natural ordering of a group of
- * mutually comparable elements. May be used when a supplied
- * comparator is null. To simplify code-sharing within underlying
- * implementations, the compare method only declares type Object
- * for its second argument.
- *
- * Arrays class implementor's note: It is an empirical matter
- * whether ComparableTimSort offers any performance benefit over
- * TimSort used with this comparator. If not, you are better off
- * deleting or bypassing ComparableTimSort. There is currently no
- * empirical case for separating them for parallel sorting, so all
- * public Object parallelSort methods use the same comparator
- * based implementation.
- */
- static final class NaturalOrder implements Comparator<Object> {
- @SuppressWarnings("unchecked")
- public int compare(Object first, Object second) {
- return ((Comparable<Object>)first).compareTo(second);
- }
- static final NaturalOrder INSTANCE = new NaturalOrder();
- }
-
- /**
- * Checks that {@code fromIndex} and {@code toIndex} are in
- * the range and throws an exception if they aren't.
- */
- private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
- if (fromIndex > toIndex) {
- throw new IllegalArgumentException(
- "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
- }
- if (fromIndex < 0) {
- throw new ArrayIndexOutOfBoundsException(fromIndex);
- }
- if (toIndex > arrayLength) {
- throw new ArrayIndexOutOfBoundsException(toIndex);
- }
- }
-
/*
- * Sorting methods. Note that all public "sort" methods take the
- * same form: Performing argument checks if necessary, and then
- * expanding arguments into those required for the internal
- * implementation methods residing in other package-private
- * classes (except for legacyMergeSort, included in this class).
+ * Sorting of primitive type arrays.
*/
/**
@@ -439,745 +375,6 @@ public static void sort(double[] a, int fromIndex, int 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.
- *
- * <p>The {@code <} relation does not provide a total order on all float
- * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
- * value compares neither less than, greater than, nor equal to any value,
- * even itself. This method uses the total order imposed by the method
- * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
- * {@code 0.0f} and {@code Float.NaN} is considered greater than any
- * other value and all {@code Float.NaN} values are considered equal.
- *
- * @implNote The sorting algorithm is a 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.
- *
- * <p>The {@code <} relation does not provide a total order on all float
- * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
- * value compares neither less than, greater than, nor equal to any value,
- * even itself. This method uses the total order imposed by the method
- * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
- * {@code 0.0f} and {@code Float.NaN} is considered greater than any
- * other value and all {@code Float.NaN} values are considered equal.
- *
- * @implNote The sorting algorithm is a 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.
- *
- * <p>The {@code <} relation does not provide a total order on all double
- * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
- * value compares neither less than, greater than, nor equal to any value,
- * even itself. This method uses the total order imposed by the method
- * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
- * {@code 0.0d} and {@code Double.NaN} is considered greater than any
- * other value and all {@code Double.NaN} values are considered equal.
- *
- * @implNote The sorting algorithm is a 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.
- *
- * <p>The {@code <} relation does not provide a total order on all double
- * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
- * value compares neither less than, greater than, nor equal to any value,
- * even itself. This method uses the total order imposed by the method
- * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
- * {@code 0.0d} and {@code Double.NaN} is considered greater than any
- * other value and all {@code Double.NaN} values are considered equal.
- *
- * @implNote The sorting algorithm is a 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
- * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
- * not throw a {@code ClassCastException} for any elements {@code e1}
- * and {@code e2} in the array).
- *
- * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
- * not be reordered as a result of the sort.
- *
- * @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 <T> 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
- * <i>mutually comparable</i> (for example, strings and integers)
- * @throws IllegalArgumentException (optional) if the natural
- * ordering of the array elements is found to violate the
- * {@link Comparable} contract
- *
- * @since 1.8
- */
- @SuppressWarnings("unchecked")
- public static <T extends Comparable<? super T>> 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<T>
- (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 <i>mutually
- * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a
- * {@code ClassCastException} for any elements {@code e1} and
- * {@code e2} in the array).
- *
- * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
- * not be reordered as a result of the sort.
- *
- * @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 <T> 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 <i>mutually comparable</i> (for example, strings and
- * integers).
- *
- * @since 1.8
- */
- @SuppressWarnings("unchecked")
- public static <T extends Comparable<? super T>>
- 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<T>
- (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
- * <i>mutually comparable</i> 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).
- *
- * <p>This sort is guaranteed to be <i>stable</i>: 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 <T> 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 <i>mutually comparable</i> 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 <T> void parallelSort(T[] a, Comparator<? super T> 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<T>
- (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
- * <i>mutually comparable</i> 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).
- *
- * <p>This sort is guaranteed to be <i>stable</i>: 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 <T> 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 <i>mutually comparable</i> (for example, strings and
- * integers).
- *
- * @since 1.8
- */
- @SuppressWarnings("unchecked")
- public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,
- Comparator<? super T> 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<T>
- (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.
*/
@@ -1189,12 +386,43 @@ void parallelSort(T[] a, int fromIndex, int toIndex) {
* circular dependencies. To be removed in a future release.
*/
static final class LegacyMergeSort {
- private static final boolean userRequested =
- java.security.AccessController.doPrivileged(
- new sun.security.action.GetBooleanAction(
- "java.util.Arrays.useLegacyMergeSort")).booleanValue();
+ // 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<Object> NATURAL_ORDER =
+// new Comparator<Object>() {
+// @SuppressWarnings("unchecked")
+// public int compare(Object first, Object second) {
+// return ((Comparable<Object>)first).compareTo(second);
+// }
+// };
+//
+// public static void sort(Object[] a) {
+// sort(a, 0, a.length, NATURAL_ORDER);
+// }
+//
+// public static void sort(Object[] a, int fromIndex, int toIndex) {
+// sort(a, fromIndex, toIndex, NATURAL_ORDER);
+// }
+
/**
* Sorts the specified array of objects into ascending order, according
* to the {@linkplain Comparable natural ordering} of its elements.
@@ -1225,7 +453,7 @@ void parallelSort(T[] a, int fromIndex, int toIndex) {
*
* <p>The implementation was adapted from Tim Peters's list sort for Python
* (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
- * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic
+ * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
* Sorting and Information Theoretic Complexity", in Proceedings of the
* Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
* January 1993.
@@ -1284,7 +512,7 @@ private static void legacyMergeSort(Object[] a) {
*
* <p>The implementation was adapted from Tim Peters's list sort for Python
* (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
- * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic
+ * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
* Sorting and Information Theoretic Complexity", in Proceedings of the
* Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
* January 1993.
@@ -1313,6 +541,7 @@ public static void sort(Object[] a, int fromIndex, int toIndex) {
/** 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);
}
@@ -1332,7 +561,6 @@ private static void legacyMergeSort(Object[] a,
* off is the offset to generate corresponding low, high in src
* To be removed in a future release.
*/
- @SuppressWarnings({"unchecked", "rawtypes"})
private static void mergeSort(Object[] src,
Object[] dest,
int low,
@@ -1411,12 +639,11 @@ private static void swap(Object[] x, int a, int b) {
*
* <p>The implementation was adapted from Tim Peters's list sort for Python
* (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
- * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic
+ * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
* Sorting and Information Theoretic Complexity", in Proceedings of the
* Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
* January 1993.
*
- * @param <T> the class of the objects to be sorted
* @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'
@@ -1427,12 +654,14 @@ private static void swap(Object[] x, int a, int b) {
* found to violate the {@link Comparator} contract
*/
public static <T> void sort(T[] a, Comparator<? super T> c) {
- if (c == null)
- c = NaturalOrder.INSTANCE;
- if (LegacyMergeSort.userRequested)
- legacyMergeSort(a, c);
- else
- TimSort.sort(a, 0, a.length, c, null, 0, 0);
+ 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. */
@@ -1475,12 +704,11 @@ private static void swap(Object[] x, int a, int b) {
*
* <p>The implementation was adapted from Tim Peters's list sort for Python
* (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
- * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic
+ * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
* Sorting and Information Theoretic Complexity", in Proceedings of the
* Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
* January 1993.
*
- * @param <T> 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
@@ -1498,18 +726,21 @@ private static void swap(Object[] x, int a, int b) {
*/
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
- if (c == null)
- c = NaturalOrder.INSTANCE;
- rangeCheck(a.length, fromIndex, toIndex);
- if (LegacyMergeSort.userRequested)
- legacyMergeSort(a, fromIndex, toIndex, c);
- else
- TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
+ 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 <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
+ rangeCheck(a.length, fromIndex, toIndex);
T[] aux = copyOfRange(a, fromIndex, toIndex);
if (c==null)
mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
@@ -1525,7 +756,6 @@ private static void swap(Object[] x, int a, int b) {
* off is the offset into src corresponding to low in dest
* To be removed in a future release.
*/
- @SuppressWarnings({"rawtypes", "unchecked"})
private static void mergeSort(Object[] src,
Object[] dest,
int low, int high, int off,
@@ -1565,191 +795,21 @@ private static void mergeSort(Object[] src,
}
}
- // 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 <T> 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
+ * Checks that {@code fromIndex} and {@code toIndex} are in
+ * the range and throws an appropriate exception, if they aren't.
*/
- public static <T> void parallelPrefix(T[] array, BinaryOperator<T> 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 <T> 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 <T> void parallelPrefix(T[] array, int fromIndex,
- int toIndex, BinaryOperator<T> 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.
- *
- * <p> 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();
+ 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);
+ }
}
// Searching
@@ -2427,9 +1487,7 @@ private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
while (low <= high) {
int mid = (low + high) >>> 1;
- @SuppressWarnings("rawtypes")
Comparable midVal = (Comparable)a[mid];
- @SuppressWarnings("unchecked")
int cmp = midVal.compareTo(key);
if (cmp < 0)
@@ -2453,7 +1511,6 @@ else if (cmp > 0)
* elements equal to the specified object, there is no guarantee which one
* will be found.
*
- * @param <T> the class of the objects in the array
* @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
@@ -2489,7 +1546,6 @@ else if (cmp > 0)
* If the range contains multiple elements equal to the specified object,
* there is no guarantee which one will be found.
*
- * @param <T> the class of the objects in the array
* @param a the array to be searched
* @param fromIndex the index of the first element (inclusive) to be
* searched
@@ -3161,7 +2217,6 @@ public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
* is greater than that of the original array.
* The resulting array is of exactly the same class as the original array.
*
- * @param <T> the class of the objects in the 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
@@ -3170,7 +2225,6 @@ public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
* @throws NullPointerException if <tt>original</tt> is null
* @since 1.6
*/
- @SuppressWarnings("unchecked")
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
@@ -3185,8 +2239,6 @@ public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
* is greater than that of the original array.
* The resulting array is of the class <tt>newType</tt>.
*
- * @param <U> the class of the objects in the original array
- * @param <T> the class of the objects in the returned array
* @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
@@ -3200,7 +2252,6 @@ public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
* @since 1.6
*/
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
- @SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
@@ -3417,7 +2468,6 @@ public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
* <p>
* The resulting array is of exactly the same class as the original array.
*
- * @param <T> the class of the objects in the 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.
@@ -3430,9 +2480,8 @@ public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
* @throws NullPointerException if <tt>original</tt> is null
* @since 1.6
*/
- @SuppressWarnings("unchecked")
public static <T> T[] copyOfRange(T[] original, int from, int to) {
- return copyOfRange(original, from, to, (Class<? extends T[]>) original.getClass());
+ return copyOfRange(original, from, to, (Class<T[]>) original.getClass());
}
/**
@@ -3450,8 +2499,6 @@ public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
* of the returned array will be <tt>to - from</tt>.
* The resulting array is of the class <tt>newType</tt>.
*
- * @param <U> the class of the objects in the original array
- * @param <T> the class of the objects in the returned 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.
@@ -3472,7 +2519,6 @@ public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
int newLength = to - from;
if (newLength < 0)
throw new IllegalArgumentException(from + " > " + to);
- @SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
@@ -3784,12 +2830,10 @@ public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
* List&lt;String&gt; stooges = Arrays.asList("Larry", "Moe", "Curly");
* </pre>
*
- * @param <T> the class of the objects in the array
* @param a the array by which the list will be backed
* @return a list view of the specified array
*/
@SafeVarargs
- @SuppressWarnings("varargs")
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
@@ -3804,21 +2848,19 @@ public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
private final E[] a;
ArrayList(E[] array) {
- a = Objects.requireNonNull(array);
+ if (array==null)
+ throw new NullPointerException();
+ a = array;
}
- @Override
public int size() {
return a.length;
}
- @Override
public Object[] toArray() {
return a.clone();
}
- @Override
- @SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
int size = size();
if (a.length < size)
@@ -3830,19 +2872,16 @@ public int size() {
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<a.length; i++)
@@ -3856,15 +2895,9 @@ public int indexOf(Object o) {
return -1;
}
- @Override
public boolean contains(Object o) {
return indexOf(o) != -1;
}
-
- @Override
- public Spliterator<E> spliterator() {
- return Spliterators.spliterator(a, Spliterator.ORDERED);
- }
}
/**
@@ -4156,27 +3189,31 @@ public static int deepHashCode(Object a[]) {
for (Object element : a) {
int elementHash = 0;
- if (element instanceof Object[])
- elementHash = deepHashCode((Object[]) element);
- else if (element instanceof byte[])
- elementHash = hashCode((byte[]) element);
- else if (element instanceof short[])
- elementHash = hashCode((short[]) element);
- else if (element instanceof int[])
- elementHash = hashCode((int[]) element);
- else if (element instanceof long[])
- elementHash = hashCode((long[]) element);
- else if (element instanceof char[])
- elementHash = hashCode((char[]) element);
- else if (element instanceof float[])
- elementHash = hashCode((float[]) element);
- else if (element instanceof double[])
- elementHash = hashCode((double[]) element);
- else if (element instanceof boolean[])
- elementHash = hashCode((boolean[]) element);
- else if (element != null)
- elementHash = element.hashCode();
-
+ 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;
}
@@ -4233,7 +3270,7 @@ public static boolean deepEquals(Object[] a1, Object[] a2) {
if (e1 == e2)
continue;
- if (e1 == null)
+ if (e1 == null || e2 == null)
return false;
// Figure out whether the two elements are equal
@@ -4246,29 +3283,32 @@ public static boolean deepEquals(Object[] a1, Object[] a2) {
}
static boolean deepEquals0(Object e1, Object e2) {
- assert e1 != null;
- boolean eq;
- if (e1 instanceof Object[] && e2 instanceof Object[])
- eq = deepEquals ((Object[]) e1, (Object[]) e2);
- else if (e1 instanceof byte[] && e2 instanceof byte[])
- eq = equals((byte[]) e1, (byte[]) e2);
- else if (e1 instanceof short[] && e2 instanceof short[])
- eq = equals((short[]) e1, (short[]) e2);
- else if (e1 instanceof int[] && e2 instanceof int[])
- eq = equals((int[]) e1, (int[]) e2);
- else if (e1 instanceof long[] && e2 instanceof long[])
- eq = equals((long[]) e1, (long[]) e2);
- else if (e1 instanceof char[] && e2 instanceof char[])
- eq = equals((char[]) e1, (char[]) e2);
- else if (e1 instanceof float[] && e2 instanceof float[])
- eq = equals((float[]) e1, (float[]) e2);
- else if (e1 instanceof double[] && e2 instanceof double[])
- eq = equals((double[]) e1, (double[]) e2);
- else if (e1 instanceof boolean[] && e2 instanceof boolean[])
- eq = equals((boolean[]) e1, (boolean[]) 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
- eq = e1.equals(e2);
- return eq;
+ return e1.equals(e2);
}
/**
@@ -4611,7 +3651,7 @@ private static void deepToString(Object[] a, StringBuilder buf,
if (element == null) {
buf.append("null");
} else {
- Class<?> eClass = element.getClass();
+ Class eClass = element.getClass();
if (eClass.isArray()) {
if (eClass == byte[].class)
@@ -4648,439 +3688,17 @@ else if (eClass == boolean[].class)
dejaVu.remove(a);
}
-
/**
- * Set all elements of the specified array, using the provided
- * generator function to compute each element.
+ * Checks that the range described by {@code offset} and {@code count} doesn't exceed
+ * {@code arrayLength}.
*
- * <p>If the generator function throws an exception, it is relayed to
- * the caller and the array is left in an indeterminate state.
- *
- * @param <T> 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
+ * Android changed.
+ * @hide
*/
- public static <T> void setAll(T[] array, IntFunction<? extends T> 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.
- *
- * <p>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 <T> 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 <T> void parallelSetAll(T[] array, IntFunction<? extends T> 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.
- *
- * <p>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.
- *
- * <p>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.
- *
- * <p>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.
- *
- * <p>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.
- *
- * <p>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.
- *
- * <p>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); });
- }
-
- /**
- * Returns a {@link Spliterator} covering all of the specified array.
- *
- * <p>The spliterator reports {@link Spliterator#SIZED},
- * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
- * {@link Spliterator#IMMUTABLE}.
- *
- * @param <T> 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 <T> Spliterator<T> spliterator(T[] array) {
- return Spliterators.spliterator(array,
- Spliterator.ORDERED | Spliterator.IMMUTABLE);
- }
-
- /**
- * Returns a {@link Spliterator} covering the specified range of the
- * specified array.
- *
- * <p>The spliterator reports {@link Spliterator#SIZED},
- * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
- * {@link Spliterator#IMMUTABLE}.
- *
- * @param <T> 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 <T> Spliterator<T> 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.
- *
- * <p>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.
- *
- * <p>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.
- *
- * <p>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.
- *
- * <p>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.
- *
- * <p>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.
- *
- * <p>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 <T> 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 <T> Stream<T> 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 <T> 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 <T> Stream<T> 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);
+ 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);
+ }
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment