Port of oJdk8 Arrays#parallelSort* & tests
Based on openJdk 8u40 source & iam@ stream change in
ag/872080
Bug: 27426684
Change-Id: I86e5b8a61201c73ab2e8bac069e540c9ca8dc120
diff --git a/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/ArraysTest.java b/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/ArraysTest.java
index c6bcd3d..7b0bed1 100644
--- a/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/ArraysTest.java
+++ b/harmony-tests/src/test/java/org/apache/harmony/tests/java/util/ArraysTest.java
@@ -32,6 +32,9 @@
import java.util.function.DoubleConsumer;
import java.util.function.IntConsumer;
import java.util.function.LongConsumer;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.concurrent.ForkJoinPool;
public class ArraysTest extends junit.framework.TestCase {
@@ -4549,6 +4552,946 @@
}
}
+ private void test_parallelSort$B(int size) {
+ if (size % 256 != 0) {
+ fail("test_parallelSort$B size needs to be dividable by 256");
+ }
+ int mul256Count = size / 256;
+ byte[] sortedArray = new byte[size];
+ byte curentValue = Byte.MIN_VALUE;
+ for (int counter = 0; counter < size; counter++) {
+ sortedArray[counter] = curentValue;
+ if (counter != 0 && counter % mul256Count == 0) {
+ curentValue++;
+ }
+ }
+ byte[] reversedArray = new byte[size];
+ for (int counter = 0; counter < size; counter++) {
+ reversedArray[counter] = sortedArray[size - counter - 1];
+ }
+
+ Arrays.parallelSort(reversedArray);
+ assertTrue(Arrays.equals(sortedArray, reversedArray));
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(byte[])
+ */
+ public void test_parallelSort$B() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$B(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$B(256 * 64);
+ }
+ }
+
+ private void test_parallelSort$BII(int size) {
+ int startIndex = 100;
+ int endIndex = size - 100;
+ byte[] reversedArray = new byte[size];
+ byte[] originalReversedArray = new byte[size];
+ Arrays.fill(reversedArray, 0 , startIndex, (byte)100);
+ Arrays.fill(reversedArray, endIndex, size, (byte)100);
+ for (int counter = startIndex; counter < endIndex; counter++) {
+ reversedArray[counter] = (byte) (size - counter - startIndex - 1);
+ }
+ System.arraycopy(reversedArray, 0, originalReversedArray, 0, size);
+
+ Arrays.parallelSort(reversedArray, startIndex, endIndex);
+ for (int counter = 0; counter < startIndex; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+ for (int counter = startIndex; counter < endIndex - 1; counter++)
+ assertTrue("Array not sorted within bounds",
+ reversedArray[counter] <= reversedArray[counter + 1]);
+ for (int counter = endIndex; counter < arraySize; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+
+ //exception testing
+ try {
+ Arrays.parallelSort(reversedArray, startIndex + 1, startIndex);
+ fail("IllegalArgumentException expected");
+ } catch (IllegalArgumentException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, -1, startIndex);
+ fail("ArrayIndexOutOfBoundsException expected (1)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, startIndex, reversedArray.length + 1);
+ fail("ArrayIndexOutOfBoundsException expected (2)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(byte[], int, int)
+ */
+ public void test_parallelSort$BII() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$BII(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$BII(256 * 64);
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(byte[]) & (byte[], int, int) NPE
+ */
+ public void test_parallelSort$B_NPE() {
+ byte[] byte_array_null = null;
+ try {
+ java.util.Arrays.parallelSort(byte_array_null);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ try {
+ java.util.Arrays.parallelSort(byte_array_null, (int) -1, (int) 1);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ }
+
+ private void test_parallelSort$C(int size) {
+ char[] sortedArray = new char[size];
+ for (int counter = 0; counter < size; counter++)
+ sortedArray[counter] = (char)(Short.MIN_VALUE + counter);
+ char[] reversedArray = new char[size];
+ for (int counter = 0; counter < size; counter++) {
+ reversedArray[counter] = sortedArray[size - counter - 1];
+ }
+ Arrays.parallelSort(reversedArray);
+ assertTrue(Arrays.equals(sortedArray, reversedArray));
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(char[])
+ */
+ public void test_parallelSort$C() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$C(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$C(256 * 64);
+ }
+ }
+
+ private void test_parallelSort$CII(int size) {
+ int startIndex = 100;
+ int endIndex = size - 100;
+ char[] reversedArray = new char[size];
+ char[] originalReversedArray = new char[size];
+
+ Arrays.fill(reversedArray, 0 , startIndex, (char)100);
+ Arrays.fill(reversedArray, endIndex, size, (char)100);
+ for (int counter = startIndex; counter < endIndex; counter++) {
+ reversedArray[counter] = (char)(size - counter - startIndex - 1);
+ }
+ System.arraycopy(reversedArray, 0, originalReversedArray, 0, size);
+
+ Arrays.parallelSort(reversedArray, startIndex, endIndex);
+ for (int counter = 0; counter < startIndex; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+ for (int counter = startIndex; counter < endIndex - 1; counter++)
+ assertTrue("Array not sorted within bounds",
+ reversedArray[counter] <= reversedArray[counter + 1]);
+ for (int counter = endIndex; counter < arraySize; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+
+ //exception testing
+ try {
+ Arrays.parallelSort(reversedArray, startIndex + 1, startIndex);
+ fail("IllegalArgumentException expected");
+ } catch (IllegalArgumentException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, -1, startIndex);
+ fail("ArrayIndexOutOfBoundsException expected (1)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, startIndex, reversedArray.length + 1);
+ fail("ArrayIndexOutOfBoundsException expected (2)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(char[], int, int)
+ */
+ public void test_parallelSort$CII() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$CII(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$CII(256 * 64);
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(char[]) & (char[], int, int) NPE
+ */
+ public void test_parallelSort$C_NPE() {
+ char[] char_array_null = null;
+ try {
+ java.util.Arrays.parallelSort(char_array_null);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ try {
+ java.util.Arrays.parallelSort(char_array_null, (int) -1, (int) 1);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ }
+
+ private void test_parallelSort$S(int size) {
+ short[] sortedArray = new short[size];
+ for (int counter = 0; counter < size; counter++)
+ sortedArray[counter] = (short)(Short.MIN_VALUE + counter);
+ short[] reversedArray = new short[size];
+ for (int counter = 0; counter < size; counter++) {
+ reversedArray[counter] = sortedArray[size - counter - 1];
+ }
+ Arrays.parallelSort(reversedArray);
+ assertTrue(Arrays.equals(sortedArray, reversedArray));
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(short[])
+ */
+ public void test_parallelSort$S() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$S(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$S(256 * 64);
+ }
+ }
+
+ private void test_parallelSort$SII(int size) {
+ int startIndex = 100;
+ int endIndex = size - 100;
+ short[] reversedArray = new short[size];
+ short[] originalReversedArray = new short[size];
+
+ Arrays.fill(reversedArray, 0 , startIndex, (short)100);
+ Arrays.fill(reversedArray, endIndex, size, (short)100);
+ for (int counter = startIndex; counter < endIndex; counter++) {
+ reversedArray[counter] = (short)(size - counter - startIndex - 1);
+ }
+ System.arraycopy(reversedArray, 0, originalReversedArray, 0, size);
+
+ Arrays.parallelSort(reversedArray, startIndex, endIndex);
+ for (int counter = 0; counter < startIndex; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+ for (int counter = startIndex; counter < endIndex - 1; counter++)
+ assertTrue("Array not sorted within bounds",
+ reversedArray[counter] <= reversedArray[counter + 1]);
+ for (int counter = endIndex; counter < arraySize; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+
+ //exception testing
+ try {
+ Arrays.parallelSort(reversedArray, startIndex + 1, startIndex);
+ fail("IllegalArgumentException expected");
+ } catch (IllegalArgumentException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, -1, startIndex);
+ fail("ArrayIndexOutOfBoundsException expected (1)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, startIndex, reversedArray.length + 1);
+ fail("ArrayIndexOutOfBoundsException expected (2)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(short[], int, int)
+ */
+ public void test_parallelSort$SII() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$SII(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$SII(256 * 64);
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(short[]) & (short[], int, int) NPE
+ */
+ public void test_parallelSort$S_NPE() {
+ short[] array_null = null;
+ try {
+ java.util.Arrays.parallelSort(array_null);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ try {
+ java.util.Arrays.parallelSort(array_null, (int) -1, (int) 1);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ }
+
+ private void test_parallelSort$I(int size) {
+ int[] sortedArray = new int[size];
+ for (int counter = 0; counter < size; counter++)
+ sortedArray[counter] = (int)(Integer.MIN_VALUE + counter);
+ int[] reversedArray = new int[size];
+ for (int counter = 0; counter < size; counter++) {
+ reversedArray[counter] = sortedArray[size - counter - 1];
+ }
+ Arrays.parallelSort(reversedArray);
+ assertTrue(Arrays.equals(sortedArray, reversedArray));
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(int[])
+ */
+ public void test_parallelSort$I() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$I(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$I(256 * 64);
+ }
+ }
+
+ private void test_parallelSort$III(int size) {
+ int startIndex = 100;
+ int endIndex = size - 100;
+ int[] reversedArray = new int[size];
+ int[] originalReversedArray = new int[size];
+
+ Arrays.fill(reversedArray, 0 , startIndex, (int)100);
+ Arrays.fill(reversedArray, endIndex, size, (int)100);
+ for (int counter = startIndex; counter < endIndex; counter++) {
+ reversedArray[counter] = (int)(size - counter - startIndex - 1);
+ }
+ System.arraycopy(reversedArray, 0, originalReversedArray, 0, size);
+
+ Arrays.parallelSort(reversedArray, startIndex, endIndex);
+ for (int counter = 0; counter < startIndex; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+ for (int counter = startIndex; counter < endIndex - 1; counter++)
+ assertTrue("Array not sorted within bounds",
+ reversedArray[counter] <= reversedArray[counter + 1]);
+ for (int counter = endIndex; counter < arraySize; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+
+ //exception testing
+ try {
+ Arrays.parallelSort(reversedArray, startIndex + 1, startIndex);
+ fail("IllegalArgumentException expected");
+ } catch (IllegalArgumentException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, -1, startIndex);
+ fail("ArrayIndexOutOfBoundsException expected (1)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, startIndex, reversedArray.length + 1);
+ fail("ArrayIndexOutOfBoundsException expected (2)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(int[], int, int)
+ */
+ public void test_parallelSort$III() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$III(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$III(256 * 64);
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(int[]) & (int[], int, int) NPE
+ */
+ public void test_parallelSort$I_NPE() {
+ int[] array_null = null;
+ try {
+ java.util.Arrays.parallelSort(array_null);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ try {
+ java.util.Arrays.parallelSort(array_null, (int) -1, (int) 1);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ }
+
+ private void test_parallelSort$J(int size) {
+ long[] reversedArray = new long[size];
+ for (int counter = 0; counter < size; counter++)
+ reversedArray[counter] = (long)(size - counter - 1);
+ Arrays.parallelSort(reversedArray);
+
+ for (int counter = 0; counter < size; counter++)
+ assertTrue("Resulting array not sorted",
+ reversedArray[counter] == (long) counter);
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(long[])
+ */
+ public void test_parallelSort$J() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$J(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$J(256 * 64);
+ }
+ }
+
+ private void test_parallelSort$JII(int size) {
+ int startIndex = 100;
+ int endIndex = size - 100;
+ long[] reversedArray = new long[size];
+ long[] originalReversedArray = new long[size];
+
+ Arrays.fill(reversedArray, 0 , startIndex, (long)100);
+ Arrays.fill(reversedArray, endIndex, size, (long)100);
+ for (int counter = startIndex; counter < endIndex; counter++) {
+ reversedArray[counter] = (long)(size - counter - startIndex - 1);
+ }
+ System.arraycopy(reversedArray, 0, originalReversedArray, 0, size);
+
+ Arrays.parallelSort(reversedArray, startIndex, endIndex);
+ for (int counter = 0; counter < startIndex; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+ for (int counter = startIndex; counter < endIndex - 1; counter++)
+ assertTrue("Array not sorted within bounds",
+ reversedArray[counter] <= reversedArray[counter + 1]);
+ for (int counter = endIndex; counter < arraySize; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+
+ //exception testing
+ try {
+ Arrays.parallelSort(reversedArray, startIndex + 1, startIndex);
+ fail("IllegalArgumentException expected");
+ } catch (IllegalArgumentException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, -1, startIndex);
+ fail("ArrayIndexOutOfBoundsException expected (1)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, startIndex, reversedArray.length + 1);
+ fail("ArrayIndexOutOfBoundsException expected (2)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(long[], int, int)
+ */
+ public void test_parallelSort$JII() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$JII(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$JII(256 * 64);
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(long[]) & (long[], int, int) NPE
+ */
+ public void test_parallelSort$J_NPE() {
+ long[] array_null = null;
+ try {
+ java.util.Arrays.parallelSort(array_null);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ try {
+ java.util.Arrays.parallelSort(array_null, (int) -1, (int) 1);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ }
+
+ private void test_parallelSort$D(int size) {
+ double[] sortedArray = new double[size];
+ for (int counter = 0; counter < size; counter++)
+ sortedArray[counter] = (double)(counter);
+ double[] reversedArray = new double[size];
+ for (int counter = 0; counter < size; counter++) {
+ reversedArray[counter] = sortedArray[size - counter - 1];
+ }
+ Arrays.parallelSort(reversedArray);
+ assertTrue(Arrays.equals(sortedArray, reversedArray));
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(double[])
+ */
+ public void test_parallelSort$D() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$D(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$D(256 * 64);
+ }
+ }
+
+ private void test_parallelSort$DII(int size) {
+ int startIndex = 100;
+ int endIndex = size-100;
+ double[] reversedArray = new double[size];
+ double[] originalReversedArray = new double[size];
+
+ Arrays.fill(reversedArray, 0 , startIndex, (double)100);
+ Arrays.fill(reversedArray, endIndex, size, (double)100);
+ for (int counter = startIndex; counter < endIndex; counter++) {
+ reversedArray[counter] = (double) (size - counter - startIndex - 1);
+ }
+ System.arraycopy(reversedArray, 0, originalReversedArray, 0, size);
+
+ Arrays.parallelSort(reversedArray, startIndex, endIndex);
+ for (int counter = 0; counter < startIndex; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+ for (int counter = startIndex; counter < endIndex - 1; counter++)
+ assertTrue("Array not sorted within bounds",
+ reversedArray[counter] <= reversedArray[counter + 1]);
+ for (int counter = endIndex; counter < arraySize; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+
+ //exception testing
+ try {
+ Arrays.parallelSort(reversedArray, startIndex + 1, startIndex);
+ fail("IllegalArgumentException expected");
+ } catch (IllegalArgumentException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, -1, startIndex);
+ fail("ArrayIndexOutOfBoundsException expected (1)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, startIndex, reversedArray.length + 1);
+ fail("ArrayIndexOutOfBoundsException expected (2)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(double[], int, int)
+ */
+ public void test_parallelSort$DII() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$DII(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$DII(64*256);
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(double[]) & (double[], int, int) NPE
+ */
+ public void test_parallelSort$D_NPE() {
+ double[] array_null = null;
+ try {
+ java.util.Arrays.parallelSort(array_null);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ try {
+ java.util.Arrays.parallelSort(array_null, (int) -1, (int) 1);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ }
+
+ private void test_parallelSort$F(int size) {
+ float[] sortedArray = new float[size];
+ for (int counter = 0; counter < size; counter++)
+ sortedArray[counter] = (float)(counter);
+ float[] reversedArray = new float[size];
+ for (int counter = 0; counter < size; counter++) {
+ reversedArray[counter] = sortedArray[size - counter - 1];
+ }
+ Arrays.parallelSort(reversedArray);
+ assertTrue(Arrays.equals(sortedArray, reversedArray));
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(float[])
+ */
+ public void test_parallelSort$F() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$F(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$F(256 * 64);
+ }
+ }
+
+ private void test_parallelSort$FII(int size) {
+ int startIndex = 100;
+ int endIndex = size-100;
+ float[] reversedArray = new float[size];
+ float[] originalReversedArray = new float[size];
+
+ Arrays.fill(reversedArray, 0 , startIndex, (float)100);
+ Arrays.fill(reversedArray, endIndex, size, (float)100);
+ for (int counter = startIndex; counter < endIndex; counter++) {
+ reversedArray[counter] = (float) (size - counter - startIndex - 1);
+ }
+ System.arraycopy(reversedArray, 0, originalReversedArray, 0, size);
+
+ Arrays.parallelSort(reversedArray, startIndex, endIndex);
+ for (int counter = 0; counter < startIndex; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+ for (int counter = startIndex; counter < endIndex - 1; counter++)
+ assertTrue("Array not sorted within bounds",
+ reversedArray[counter] <= reversedArray[counter + 1]);
+ for (int counter = endIndex; counter < arraySize; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+
+ //exception testing
+ try {
+ Arrays.parallelSort(reversedArray, startIndex + 1, startIndex);
+ fail("IllegalArgumentException expected");
+ } catch (IllegalArgumentException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, -1, startIndex);
+ fail("ArrayIndexOutOfBoundsException expected (1)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, startIndex, reversedArray.length + 1);
+ fail("ArrayIndexOutOfBoundsException expected (2)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(float[], int, int)
+ */
+ public void test_parallelSort$FII() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$FII(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$FII(64*256);
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(float[]) & (float[], int, int) NPE
+ */
+ public void test_parallelSort$F_NPE() {
+ float[] array_null = null;
+ try {
+ java.util.Arrays.parallelSort(array_null);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+
+ }
+ try {
+ java.util.Arrays.parallelSort(array_null, (int) -1, (int) 1);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ }
+
+ private void test_parallelSort$Ljava_lang_Comparable(int size) {
+ Comparable[] sortedArray = new Comparable[size];
+ for (int counter = 0; counter < size; counter++)
+ sortedArray[counter] = new Integer(counter);
+ Comparable[] reversedArray = new Comparable[size];
+ for (int counter = 0; counter < size; counter++) {
+ reversedArray[counter] = sortedArray[size - counter - 1];
+ }
+ Arrays.parallelSort(reversedArray);
+ assertTrue(Arrays.equals(sortedArray, reversedArray));
+
+ Arrays.fill(reversedArray, 0, reversedArray.length/2, "String");
+ Arrays.fill(reversedArray, reversedArray.length/2, reversedArray.length, new Integer(1));
+
+ try {
+ Arrays.sort(reversedArray);
+ fail("ClassCastException expected");
+ } catch (ClassCastException expected) {
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(java.lang.Comparable[])
+ */
+ public void test_parallelSort$Ljava_lang_Comparable() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$Ljava_lang_Comparable(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$Ljava_lang_Comparable(256 * 64);
+ }
+ }
+
+ private void test_parallelSort$Ljava_lang_ComparableII(int size) {
+ int startIndex = 100;
+ int endIndex = size-100;
+ Comparable[] reversedArray = new Comparable[size];
+ Comparable[] originalReversedArray = new Comparable[size];
+ Arrays.fill(reversedArray, 0 , startIndex, new Integer(100));
+ Arrays.fill(reversedArray, endIndex, size, new Integer(100));
+ for (int counter = startIndex; counter < endIndex; counter++) {
+ reversedArray[counter] = new Integer(size - counter - startIndex - 1);
+ }
+ System.arraycopy(reversedArray, 0, originalReversedArray, 0, size);
+
+ Arrays.parallelSort(reversedArray, startIndex, endIndex);
+ for (int counter = 0; counter < startIndex; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+ for (int counter = startIndex; counter < endIndex - 1; counter++)
+ assertTrue("Array not sorted within bounds",
+ (int)(Integer)reversedArray[counter] <= (int)reversedArray[counter + 1]);
+ for (int counter = endIndex; counter < arraySize; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+
+ //exception testing
+ try {
+ Arrays.parallelSort(reversedArray, startIndex + 1, startIndex);
+ fail("IllegalArgumentException expected");
+ } catch (IllegalArgumentException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, -1, startIndex);
+ fail("ArrayIndexOutOfBoundsException expected (1)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, startIndex, reversedArray.length + 1);
+ fail("ArrayIndexOutOfBoundsException expected (2)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(java.lang.Comparable[], int, int)
+ */
+ public void test_parallelSort$Ljava_lang_ComparableII() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$Ljava_lang_ComparableII(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$Ljava_lang_ComparableII(64*256);
+ }
+ }
+
+
+ /**
+ * java.util.Arrays#parallelSort(java_lang_Comparable[]) & (java_lang_Comparable[], int, int) NPE
+ */
+ public void test_parallelSort$Ljava_lang_Comparable_NPE() {
+ Comparable[] array_null = null;
+ try {
+ java.util.Arrays.parallelSort(array_null);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+
+ }
+ try {
+ java.util.Arrays.parallelSort(array_null, (int) -1, (int) 1);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ }
+
+ private void test_parallelSort$Ljava_lang_ObjectLjava_util_Comparator(int size) {
+ Object[] reversedArray = new Object[size];
+ for (int counter = 0; counter < size; counter++)
+ reversedArray[counter] = new Integer(counter);
+ Comparator comparator = new ReversedIntegerComparator();
+ Arrays.parallelSort(reversedArray, comparator);
+
+ for (int counter = 0; counter < size; counter++)
+ assertTrue("Resulting array not sorted",
+ (int)(reversedArray[counter]) == (size - counter -1 ));
+
+ Arrays.fill(reversedArray, 0, reversedArray.length/2, "String");
+ Arrays.fill(reversedArray, reversedArray.length/2, reversedArray.length, new Integer(1));
+
+ try {
+ Arrays.sort(reversedArray, comparator);
+ fail("ClassCastException expected");
+ } catch (ClassCastException expected) {
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(java.lang.Object[], java.util.Comparator)
+ */
+ public void test_parallelSort$Ljava_lang_Objectjava_util_Comparator() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$Ljava_lang_ObjectLjava_util_Comparator(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$Ljava_lang_ObjectLjava_util_Comparator(256 * 64);
+ }
+ }
+
+ private void test_parallelSort$Ljava_lang_ObjectLjava_util_ComparatorII(int size) {
+ int startIndex = 100;
+ int endIndex = size-100;
+ Integer[] reversedArray = new Integer[size];
+ Integer[] originalReversedArray = new Integer[size];
+ Arrays.fill(reversedArray, 0 , startIndex, new Integer(100));
+ Arrays.fill(reversedArray, endIndex, size, new Integer(100));
+ for (int counter = startIndex; counter < endIndex; counter++) {
+ reversedArray[counter] = new Integer(counter - startIndex);
+ }
+ System.arraycopy(reversedArray, 0, originalReversedArray, 0, size);
+
+ Comparator comparator = new ReversedIntegerComparator();
+ Arrays.parallelSort(reversedArray, startIndex, endIndex, comparator);
+ for (int counter = 0; counter < startIndex; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+ for (int counter = startIndex; counter < endIndex - 1; counter++)
+ assertTrue("Array not sorted within bounds",
+ (int)(Integer)reversedArray[counter] >= (int)reversedArray[counter + 1]);
+ for (int counter = endIndex; counter < arraySize; counter++)
+ assertTrue("Array modified outside of bounds",
+ reversedArray[counter] == originalReversedArray[counter]);
+
+ //exception testing
+ try {
+ Arrays.parallelSort(reversedArray, startIndex + 1, startIndex, comparator);
+ fail("IllegalArgumentException expected");
+ } catch (IllegalArgumentException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, -1, startIndex, comparator);
+ fail("ArrayIndexOutOfBoundsException expected (1)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+
+ try {
+ Arrays.parallelSort(reversedArray, startIndex, reversedArray.length + 1, comparator);
+ fail("ArrayIndexOutOfBoundsException expected (2)");
+ } catch (ArrayIndexOutOfBoundsException ignore) {
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(java.lang.Object[], int, int, java.util.Comparator)
+ */
+ public void test_parallelSort$Ljava_lang_ObjectLjava_util_ComparatorII() {
+ // This will result in single thread sort
+ assertTrue(256 <= Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$Ljava_lang_ObjectLjava_util_ComparatorII(256);
+ // This should trigger true parallel sort
+ if (ForkJoinPool.getCommonPoolParallelism() > 1) {
+ assertTrue(256 * 64 > Arrays.MIN_ARRAY_SORT_GRAN);
+ test_parallelSort$Ljava_lang_ObjectLjava_util_ComparatorII(64*256);
+ }
+ }
+
+ /**
+ * java.util.Arrays#parallelSort(Object[],Comparator) & (Object[], int, int, Comparator) NPE
+ */
+ public void test_parallelSort$Ljava_lang_ObjectLjava_util_Comparator_NPE() {
+ Object[] array_null = null;
+ Comparator comparator = new ReversedIntegerComparator();
+ try {
+ java.util.Arrays.parallelSort(array_null, comparator);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+
+ }
+ try {
+ java.util.Arrays.parallelSort(array_null, (int) -1, (int) 1, comparator);
+ fail("Should throw java.lang.NullPointerException");
+ } catch (NullPointerException expected) {
+ }
+ }
+
+
/**
* Tears down the fixture, for example, close a network connection. This
* method is called after a test is executed.
diff --git a/ojluni/src/main/java/java/util/Arrays.java b/ojluni/src/main/java/java/util/Arrays.java
index f39a719..3dd999d 100755
--- a/ojluni/src/main/java/java/util/Arrays.java
+++ b/ojluni/src/main/java/java/util/Arrays.java
@@ -28,6 +28,7 @@
import java.lang.reflect.*;
import java.util.function.Consumer;
+import java.util.concurrent.ForkJoinPool;
/**
* This class contains various methods for manipulating arrays (such as
@@ -56,6 +57,39 @@
*/
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<Object> {
+ @SuppressWarnings("unchecked")
+ public int compare(Object first, Object second) {
+ return ((Comparable<Object>)first).compareTo(second);
+ }
+ static final NaturalOrder INSTANCE = new NaturalOrder();
+ }
+
// Suppresses default constructor, ensuring non-instantiability.
private Arrays() {}
@@ -375,6 +409,745 @@
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.
*/
diff --git a/ojluni/src/main/java/java/util/ArraysParallelSortHelpers.java b/ojluni/src/main/java/java/util/ArraysParallelSortHelpers.java
new file mode 100644
index 0000000..8fa2262
--- /dev/null
+++ b/ojluni/src/main/java/java/util/ArraysParallelSortHelpers.java
@@ -0,0 +1,1010 @@
+/*
+ * Copyright (c) 2012, 2013, 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.util.concurrent.RecursiveAction;
+import java.util.concurrent.CountedCompleter;
+
+/**
+ * Helper utilities for the parallel sort methods in Arrays.parallelSort.
+ *
+ * For each primitive type, plus Object, we define a static class to
+ * contain the Sorter and Merger implementations for that type:
+ *
+ * Sorter classes based mainly on CilkSort
+ * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>:
+ * Basic algorithm:
+ * if array size is small, just use a sequential quicksort (via Arrays.sort)
+ * Otherwise:
+ * 1. Break array in half.
+ * 2. For each half,
+ * a. break the half in half (i.e., quarters),
+ * b. sort the quarters
+ * c. merge them together
+ * 3. merge together the two halves.
+ *
+ * One reason for splitting in quarters is that this guarantees that
+ * the final sort is in the main array, not the workspace array.
+ * (workspace and main swap roles on each subsort step.) Leaf-level
+ * sorts use the associated sequential sort.
+ *
+ * Merger classes perform merging for Sorter. They are structured
+ * such that if the underlying sort is stable (as is true for
+ * TimSort), then so is the full sort. If big enough, they split the
+ * largest of the two partitions in half, find the greatest point in
+ * smaller partition less than the beginning of the second half of
+ * larger via binary search; and then merge in parallel the two
+ * partitions. In part to ensure tasks are triggered in
+ * stability-preserving order, the current CountedCompleter design
+ * requires some little tasks to serve as place holders for triggering
+ * completion tasks. These classes (EmptyCompleter and Relay) don't
+ * need to keep track of the arrays, and are never themselves forked,
+ * so don't hold any task state.
+ *
+ * The primitive class versions (FJByte... FJDouble) are
+ * identical to each other except for type declarations.
+ *
+ * The base sequential sorts rely on non-public versions of TimSort,
+ * ComparableTimSort, and DualPivotQuicksort sort methods that accept
+ * temp workspace array slices that we will have already allocated, so
+ * avoids redundant allocation. (Except for DualPivotQuicksort byte[]
+ * sort, that does not ever use a workspace array.)
+ */
+/*package*/ class ArraysParallelSortHelpers {
+
+ /*
+ * Style note: The task classes have a lot of parameters, that are
+ * stored as task fields and copied to local variables and used in
+ * compute() methods, We pack these into as few lines as possible,
+ * and hoist consistency checks among them before main loops, to
+ * reduce distraction.
+ */
+
+ /**
+ * A placeholder task for Sorters, used for the lowest
+ * quartile task, that does not need to maintain array state.
+ */
+ static final class EmptyCompleter extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ EmptyCompleter(CountedCompleter<?> p) { super(p); }
+ public final void compute() { }
+ }
+
+ /**
+ * A trigger for secondary merge of two merges
+ */
+ static final class Relay extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final CountedCompleter<?> task;
+ Relay(CountedCompleter<?> task) {
+ super(null, 1);
+ this.task = task;
+ }
+ public final void compute() { }
+ public final void onCompletion(CountedCompleter<?> t) {
+ task.compute();
+ }
+ }
+
+ /** Object + Comparator support class */
+ static final class FJObject {
+ static final class Sorter<T> extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final T[] a, w;
+ final int base, size, wbase, gran;
+ Comparator<? super T> comparator;
+ Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size,
+ int wbase, int gran,
+ Comparator<? super T> comparator) {
+ super(par);
+ this.a = a; this.w = w; this.base = base; this.size = size;
+ this.wbase = wbase; this.gran = gran;
+ this.comparator = comparator;
+ }
+ public final void compute() {
+ CountedCompleter<?> s = this;
+ Comparator<? super T> c = this.comparator;
+ T[] a = this.a, w = this.w; // localize all params
+ int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
+ while (n > g) {
+ int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+ Relay fc = new Relay(new Merger<T>(s, w, a, wb, h,
+ wb+h, n-h, b, g, c));
+ Relay rc = new Relay(new Merger<T>(fc, a, w, b+h, q,
+ b+u, n-u, wb+h, g, c));
+ new Sorter<T>(rc, a, w, b+u, n-u, wb+u, g, c).fork();
+ new Sorter<T>(rc, a, w, b+h, q, wb+h, g, c).fork();;
+ Relay bc = new Relay(new Merger<T>(fc, a, w, b, q,
+ b+q, h-q, wb, g, c));
+ new Sorter<T>(bc, a, w, b+q, h-q, wb+q, g, c).fork();
+ s = new EmptyCompleter(bc);
+ n = q;
+ }
+ TimSort.sort(a, b, b + n, c, w, wb, n);
+ s.tryComplete();
+ }
+ }
+
+ static final class Merger<T> extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final T[] a, w; // main and workspace arrays
+ final int lbase, lsize, rbase, rsize, wbase, gran;
+ Comparator<? super T> comparator;
+ Merger(CountedCompleter<?> par, T[] a, T[] w,
+ int lbase, int lsize, int rbase,
+ int rsize, int wbase, int gran,
+ Comparator<? super T> comparator) {
+ super(par);
+ this.a = a; this.w = w;
+ this.lbase = lbase; this.lsize = lsize;
+ this.rbase = rbase; this.rsize = rsize;
+ this.wbase = wbase; this.gran = gran;
+ this.comparator = comparator;
+ }
+
+ public final void compute() {
+ Comparator<? super T> c = this.comparator;
+ T[] a = this.a, w = this.w; // localize all params
+ int lb = this.lbase, ln = this.lsize, rb = this.rbase,
+ rn = this.rsize, k = this.wbase, g = this.gran;
+ if (a == null || w == null || lb < 0 || rb < 0 || k < 0 ||
+ c == null)
+ throw new IllegalStateException(); // hoist checks
+ for (int lh, rh;;) { // split larger, find point in smaller
+ if (ln >= rn) {
+ if (ln <= g)
+ break;
+ rh = rn;
+ T split = a[(lh = ln >>> 1) + lb];
+ for (int lo = 0; lo < rh; ) {
+ int rm = (lo + rh) >>> 1;
+ if (c.compare(split, a[rm + rb]) <= 0)
+ rh = rm;
+ else
+ lo = rm + 1;
+ }
+ }
+ else {
+ if (rn <= g)
+ break;
+ lh = ln;
+ T split = a[(rh = rn >>> 1) + rb];
+ for (int lo = 0; lo < lh; ) {
+ int lm = (lo + lh) >>> 1;
+ if (c.compare(split, a[lm + lb]) <= 0)
+ lh = lm;
+ else
+ lo = lm + 1;
+ }
+ }
+ Merger<T> m = new Merger<T>(this, a, w, lb + lh, ln - lh,
+ rb + rh, rn - rh,
+ k + lh + rh, g, c);
+ rn = rh;
+ ln = lh;
+ addToPendingCount(1);
+ m.fork();
+ }
+
+ int lf = lb + ln, rf = rb + rn; // index bounds
+ while (lb < lf && rb < rf) {
+ T t, al, ar;
+ if (c.compare((al = a[lb]), (ar = a[rb])) <= 0) {
+ lb++; t = al;
+ }
+ else {
+ rb++; t = ar;
+ }
+ w[k++] = t;
+ }
+ if (rb < rf)
+ System.arraycopy(a, rb, w, k, rf - rb);
+ else if (lb < lf)
+ System.arraycopy(a, lb, w, k, lf - lb);
+
+ tryComplete();
+ }
+
+ }
+ } // FJObject
+
+ /** byte support class */
+ static final class FJByte {
+ static final class Sorter extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final byte[] a, w;
+ final int base, size, wbase, gran;
+ Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base,
+ int size, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w; this.base = base; this.size = size;
+ this.wbase = wbase; this.gran = gran;
+ }
+ public final void compute() {
+ CountedCompleter<?> s = this;
+ byte[] a = this.a, w = this.w; // localize all params
+ int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
+ while (n > g) {
+ int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+ Relay fc = new Relay(new Merger(s, w, a, wb, h,
+ wb+h, n-h, b, g));
+ Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+ b+u, n-u, wb+h, g));
+ new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+ new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+ Relay bc = new Relay(new Merger(fc, a, w, b, q,
+ b+q, h-q, wb, g));
+ new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+ s = new EmptyCompleter(bc);
+ n = q;
+ }
+ DualPivotQuicksort.sort(a, b, b + n - 1);
+ s.tryComplete();
+ }
+ }
+
+ static final class Merger extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final byte[] a, w; // main and workspace arrays
+ final int lbase, lsize, rbase, rsize, wbase, gran;
+ Merger(CountedCompleter<?> par, byte[] a, byte[] w,
+ int lbase, int lsize, int rbase,
+ int rsize, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w;
+ this.lbase = lbase; this.lsize = lsize;
+ this.rbase = rbase; this.rsize = rsize;
+ this.wbase = wbase; this.gran = gran;
+ }
+
+ public final void compute() {
+ byte[] a = this.a, w = this.w; // localize all params
+ int lb = this.lbase, ln = this.lsize, rb = this.rbase,
+ rn = this.rsize, k = this.wbase, g = this.gran;
+ if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+ throw new IllegalStateException(); // hoist checks
+ for (int lh, rh;;) { // split larger, find point in smaller
+ if (ln >= rn) {
+ if (ln <= g)
+ break;
+ rh = rn;
+ byte split = a[(lh = ln >>> 1) + lb];
+ for (int lo = 0; lo < rh; ) {
+ int rm = (lo + rh) >>> 1;
+ if (split <= a[rm + rb])
+ rh = rm;
+ else
+ lo = rm + 1;
+ }
+ }
+ else {
+ if (rn <= g)
+ break;
+ lh = ln;
+ byte split = a[(rh = rn >>> 1) + rb];
+ for (int lo = 0; lo < lh; ) {
+ int lm = (lo + lh) >>> 1;
+ if (split <= a[lm + lb])
+ lh = lm;
+ else
+ lo = lm + 1;
+ }
+ }
+ Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+ rb + rh, rn - rh,
+ k + lh + rh, g);
+ rn = rh;
+ ln = lh;
+ addToPendingCount(1);
+ m.fork();
+ }
+
+ int lf = lb + ln, rf = rb + rn; // index bounds
+ while (lb < lf && rb < rf) {
+ byte t, al, ar;
+ if ((al = a[lb]) <= (ar = a[rb])) {
+ lb++; t = al;
+ }
+ else {
+ rb++; t = ar;
+ }
+ w[k++] = t;
+ }
+ if (rb < rf)
+ System.arraycopy(a, rb, w, k, rf - rb);
+ else if (lb < lf)
+ System.arraycopy(a, lb, w, k, lf - lb);
+ tryComplete();
+ }
+ }
+ } // FJByte
+
+ /** char support class */
+ static final class FJChar {
+ static final class Sorter extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final char[] a, w;
+ final int base, size, wbase, gran;
+ Sorter(CountedCompleter<?> par, char[] a, char[] w, int base,
+ int size, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w; this.base = base; this.size = size;
+ this.wbase = wbase; this.gran = gran;
+ }
+ public final void compute() {
+ CountedCompleter<?> s = this;
+ char[] a = this.a, w = this.w; // localize all params
+ int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
+ while (n > g) {
+ int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+ Relay fc = new Relay(new Merger(s, w, a, wb, h,
+ wb+h, n-h, b, g));
+ Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+ b+u, n-u, wb+h, g));
+ new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+ new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+ Relay bc = new Relay(new Merger(fc, a, w, b, q,
+ b+q, h-q, wb, g));
+ new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+ s = new EmptyCompleter(bc);
+ n = q;
+ }
+ DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
+ s.tryComplete();
+ }
+ }
+
+ static final class Merger extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final char[] a, w; // main and workspace arrays
+ final int lbase, lsize, rbase, rsize, wbase, gran;
+ Merger(CountedCompleter<?> par, char[] a, char[] w,
+ int lbase, int lsize, int rbase,
+ int rsize, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w;
+ this.lbase = lbase; this.lsize = lsize;
+ this.rbase = rbase; this.rsize = rsize;
+ this.wbase = wbase; this.gran = gran;
+ }
+
+ public final void compute() {
+ char[] a = this.a, w = this.w; // localize all params
+ int lb = this.lbase, ln = this.lsize, rb = this.rbase,
+ rn = this.rsize, k = this.wbase, g = this.gran;
+ if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+ throw new IllegalStateException(); // hoist checks
+ for (int lh, rh;;) { // split larger, find point in smaller
+ if (ln >= rn) {
+ if (ln <= g)
+ break;
+ rh = rn;
+ char split = a[(lh = ln >>> 1) + lb];
+ for (int lo = 0; lo < rh; ) {
+ int rm = (lo + rh) >>> 1;
+ if (split <= a[rm + rb])
+ rh = rm;
+ else
+ lo = rm + 1;
+ }
+ }
+ else {
+ if (rn <= g)
+ break;
+ lh = ln;
+ char split = a[(rh = rn >>> 1) + rb];
+ for (int lo = 0; lo < lh; ) {
+ int lm = (lo + lh) >>> 1;
+ if (split <= a[lm + lb])
+ lh = lm;
+ else
+ lo = lm + 1;
+ }
+ }
+ Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+ rb + rh, rn - rh,
+ k + lh + rh, g);
+ rn = rh;
+ ln = lh;
+ addToPendingCount(1);
+ m.fork();
+ }
+
+ int lf = lb + ln, rf = rb + rn; // index bounds
+ while (lb < lf && rb < rf) {
+ char t, al, ar;
+ if ((al = a[lb]) <= (ar = a[rb])) {
+ lb++; t = al;
+ }
+ else {
+ rb++; t = ar;
+ }
+ w[k++] = t;
+ }
+ if (rb < rf)
+ System.arraycopy(a, rb, w, k, rf - rb);
+ else if (lb < lf)
+ System.arraycopy(a, lb, w, k, lf - lb);
+ tryComplete();
+ }
+ }
+ } // FJChar
+
+ /** short support class */
+ static final class FJShort {
+ static final class Sorter extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final short[] a, w;
+ final int base, size, wbase, gran;
+ Sorter(CountedCompleter<?> par, short[] a, short[] w, int base,
+ int size, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w; this.base = base; this.size = size;
+ this.wbase = wbase; this.gran = gran;
+ }
+ public final void compute() {
+ CountedCompleter<?> s = this;
+ short[] a = this.a, w = this.w; // localize all params
+ int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
+ while (n > g) {
+ int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+ Relay fc = new Relay(new Merger(s, w, a, wb, h,
+ wb+h, n-h, b, g));
+ Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+ b+u, n-u, wb+h, g));
+ new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+ new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+ Relay bc = new Relay(new Merger(fc, a, w, b, q,
+ b+q, h-q, wb, g));
+ new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+ s = new EmptyCompleter(bc);
+ n = q;
+ }
+ DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
+ s.tryComplete();
+ }
+ }
+
+ static final class Merger extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final short[] a, w; // main and workspace arrays
+ final int lbase, lsize, rbase, rsize, wbase, gran;
+ Merger(CountedCompleter<?> par, short[] a, short[] w,
+ int lbase, int lsize, int rbase,
+ int rsize, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w;
+ this.lbase = lbase; this.lsize = lsize;
+ this.rbase = rbase; this.rsize = rsize;
+ this.wbase = wbase; this.gran = gran;
+ }
+
+ public final void compute() {
+ short[] a = this.a, w = this.w; // localize all params
+ int lb = this.lbase, ln = this.lsize, rb = this.rbase,
+ rn = this.rsize, k = this.wbase, g = this.gran;
+ if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+ throw new IllegalStateException(); // hoist checks
+ for (int lh, rh;;) { // split larger, find point in smaller
+ if (ln >= rn) {
+ if (ln <= g)
+ break;
+ rh = rn;
+ short split = a[(lh = ln >>> 1) + lb];
+ for (int lo = 0; lo < rh; ) {
+ int rm = (lo + rh) >>> 1;
+ if (split <= a[rm + rb])
+ rh = rm;
+ else
+ lo = rm + 1;
+ }
+ }
+ else {
+ if (rn <= g)
+ break;
+ lh = ln;
+ short split = a[(rh = rn >>> 1) + rb];
+ for (int lo = 0; lo < lh; ) {
+ int lm = (lo + lh) >>> 1;
+ if (split <= a[lm + lb])
+ lh = lm;
+ else
+ lo = lm + 1;
+ }
+ }
+ Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+ rb + rh, rn - rh,
+ k + lh + rh, g);
+ rn = rh;
+ ln = lh;
+ addToPendingCount(1);
+ m.fork();
+ }
+
+ int lf = lb + ln, rf = rb + rn; // index bounds
+ while (lb < lf && rb < rf) {
+ short t, al, ar;
+ if ((al = a[lb]) <= (ar = a[rb])) {
+ lb++; t = al;
+ }
+ else {
+ rb++; t = ar;
+ }
+ w[k++] = t;
+ }
+ if (rb < rf)
+ System.arraycopy(a, rb, w, k, rf - rb);
+ else if (lb < lf)
+ System.arraycopy(a, lb, w, k, lf - lb);
+ tryComplete();
+ }
+ }
+ } // FJShort
+
+ /** int support class */
+ static final class FJInt {
+ static final class Sorter extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final int[] a, w;
+ final int base, size, wbase, gran;
+ Sorter(CountedCompleter<?> par, int[] a, int[] w, int base,
+ int size, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w; this.base = base; this.size = size;
+ this.wbase = wbase; this.gran = gran;
+ }
+ public final void compute() {
+ CountedCompleter<?> s = this;
+ int[] a = this.a, w = this.w; // localize all params
+ int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
+ while (n > g) {
+ int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+ Relay fc = new Relay(new Merger(s, w, a, wb, h,
+ wb+h, n-h, b, g));
+ Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+ b+u, n-u, wb+h, g));
+ new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+ new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+ Relay bc = new Relay(new Merger(fc, a, w, b, q,
+ b+q, h-q, wb, g));
+ new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+ s = new EmptyCompleter(bc);
+ n = q;
+ }
+ DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
+ s.tryComplete();
+ }
+ }
+
+ static final class Merger extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final int[] a, w; // main and workspace arrays
+ final int lbase, lsize, rbase, rsize, wbase, gran;
+ Merger(CountedCompleter<?> par, int[] a, int[] w,
+ int lbase, int lsize, int rbase,
+ int rsize, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w;
+ this.lbase = lbase; this.lsize = lsize;
+ this.rbase = rbase; this.rsize = rsize;
+ this.wbase = wbase; this.gran = gran;
+ }
+
+ public final void compute() {
+ int[] a = this.a, w = this.w; // localize all params
+ int lb = this.lbase, ln = this.lsize, rb = this.rbase,
+ rn = this.rsize, k = this.wbase, g = this.gran;
+ if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+ throw new IllegalStateException(); // hoist checks
+ for (int lh, rh;;) { // split larger, find point in smaller
+ if (ln >= rn) {
+ if (ln <= g)
+ break;
+ rh = rn;
+ int split = a[(lh = ln >>> 1) + lb];
+ for (int lo = 0; lo < rh; ) {
+ int rm = (lo + rh) >>> 1;
+ if (split <= a[rm + rb])
+ rh = rm;
+ else
+ lo = rm + 1;
+ }
+ }
+ else {
+ if (rn <= g)
+ break;
+ lh = ln;
+ int split = a[(rh = rn >>> 1) + rb];
+ for (int lo = 0; lo < lh; ) {
+ int lm = (lo + lh) >>> 1;
+ if (split <= a[lm + lb])
+ lh = lm;
+ else
+ lo = lm + 1;
+ }
+ }
+ Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+ rb + rh, rn - rh,
+ k + lh + rh, g);
+ rn = rh;
+ ln = lh;
+ addToPendingCount(1);
+ m.fork();
+ }
+
+ int lf = lb + ln, rf = rb + rn; // index bounds
+ while (lb < lf && rb < rf) {
+ int t, al, ar;
+ if ((al = a[lb]) <= (ar = a[rb])) {
+ lb++; t = al;
+ }
+ else {
+ rb++; t = ar;
+ }
+ w[k++] = t;
+ }
+ if (rb < rf)
+ System.arraycopy(a, rb, w, k, rf - rb);
+ else if (lb < lf)
+ System.arraycopy(a, lb, w, k, lf - lb);
+ tryComplete();
+ }
+ }
+ } // FJInt
+
+ /** long support class */
+ static final class FJLong {
+ static final class Sorter extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final long[] a, w;
+ final int base, size, wbase, gran;
+ Sorter(CountedCompleter<?> par, long[] a, long[] w, int base,
+ int size, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w; this.base = base; this.size = size;
+ this.wbase = wbase; this.gran = gran;
+ }
+ public final void compute() {
+ CountedCompleter<?> s = this;
+ long[] a = this.a, w = this.w; // localize all params
+ int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
+ while (n > g) {
+ int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+ Relay fc = new Relay(new Merger(s, w, a, wb, h,
+ wb+h, n-h, b, g));
+ Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+ b+u, n-u, wb+h, g));
+ new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+ new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+ Relay bc = new Relay(new Merger(fc, a, w, b, q,
+ b+q, h-q, wb, g));
+ new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+ s = new EmptyCompleter(bc);
+ n = q;
+ }
+ DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
+ s.tryComplete();
+ }
+ }
+
+ static final class Merger extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final long[] a, w; // main and workspace arrays
+ final int lbase, lsize, rbase, rsize, wbase, gran;
+ Merger(CountedCompleter<?> par, long[] a, long[] w,
+ int lbase, int lsize, int rbase,
+ int rsize, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w;
+ this.lbase = lbase; this.lsize = lsize;
+ this.rbase = rbase; this.rsize = rsize;
+ this.wbase = wbase; this.gran = gran;
+ }
+
+ public final void compute() {
+ long[] a = this.a, w = this.w; // localize all params
+ int lb = this.lbase, ln = this.lsize, rb = this.rbase,
+ rn = this.rsize, k = this.wbase, g = this.gran;
+ if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+ throw new IllegalStateException(); // hoist checks
+ for (int lh, rh;;) { // split larger, find point in smaller
+ if (ln >= rn) {
+ if (ln <= g)
+ break;
+ rh = rn;
+ long split = a[(lh = ln >>> 1) + lb];
+ for (int lo = 0; lo < rh; ) {
+ int rm = (lo + rh) >>> 1;
+ if (split <= a[rm + rb])
+ rh = rm;
+ else
+ lo = rm + 1;
+ }
+ }
+ else {
+ if (rn <= g)
+ break;
+ lh = ln;
+ long split = a[(rh = rn >>> 1) + rb];
+ for (int lo = 0; lo < lh; ) {
+ int lm = (lo + lh) >>> 1;
+ if (split <= a[lm + lb])
+ lh = lm;
+ else
+ lo = lm + 1;
+ }
+ }
+ Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+ rb + rh, rn - rh,
+ k + lh + rh, g);
+ rn = rh;
+ ln = lh;
+ addToPendingCount(1);
+ m.fork();
+ }
+
+ int lf = lb + ln, rf = rb + rn; // index bounds
+ while (lb < lf && rb < rf) {
+ long t, al, ar;
+ if ((al = a[lb]) <= (ar = a[rb])) {
+ lb++; t = al;
+ }
+ else {
+ rb++; t = ar;
+ }
+ w[k++] = t;
+ }
+ if (rb < rf)
+ System.arraycopy(a, rb, w, k, rf - rb);
+ else if (lb < lf)
+ System.arraycopy(a, lb, w, k, lf - lb);
+ tryComplete();
+ }
+ }
+ } // FJLong
+
+ /** float support class */
+ static final class FJFloat {
+ static final class Sorter extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final float[] a, w;
+ final int base, size, wbase, gran;
+ Sorter(CountedCompleter<?> par, float[] a, float[] w, int base,
+ int size, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w; this.base = base; this.size = size;
+ this.wbase = wbase; this.gran = gran;
+ }
+ public final void compute() {
+ CountedCompleter<?> s = this;
+ float[] a = this.a, w = this.w; // localize all params
+ int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
+ while (n > g) {
+ int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+ Relay fc = new Relay(new Merger(s, w, a, wb, h,
+ wb+h, n-h, b, g));
+ Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+ b+u, n-u, wb+h, g));
+ new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+ new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+ Relay bc = new Relay(new Merger(fc, a, w, b, q,
+ b+q, h-q, wb, g));
+ new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+ s = new EmptyCompleter(bc);
+ n = q;
+ }
+ DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
+ s.tryComplete();
+ }
+ }
+
+ static final class Merger extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final float[] a, w; // main and workspace arrays
+ final int lbase, lsize, rbase, rsize, wbase, gran;
+ Merger(CountedCompleter<?> par, float[] a, float[] w,
+ int lbase, int lsize, int rbase,
+ int rsize, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w;
+ this.lbase = lbase; this.lsize = lsize;
+ this.rbase = rbase; this.rsize = rsize;
+ this.wbase = wbase; this.gran = gran;
+ }
+
+ public final void compute() {
+ float[] a = this.a, w = this.w; // localize all params
+ int lb = this.lbase, ln = this.lsize, rb = this.rbase,
+ rn = this.rsize, k = this.wbase, g = this.gran;
+ if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+ throw new IllegalStateException(); // hoist checks
+ for (int lh, rh;;) { // split larger, find point in smaller
+ if (ln >= rn) {
+ if (ln <= g)
+ break;
+ rh = rn;
+ float split = a[(lh = ln >>> 1) + lb];
+ for (int lo = 0; lo < rh; ) {
+ int rm = (lo + rh) >>> 1;
+ if (split <= a[rm + rb])
+ rh = rm;
+ else
+ lo = rm + 1;
+ }
+ }
+ else {
+ if (rn <= g)
+ break;
+ lh = ln;
+ float split = a[(rh = rn >>> 1) + rb];
+ for (int lo = 0; lo < lh; ) {
+ int lm = (lo + lh) >>> 1;
+ if (split <= a[lm + lb])
+ lh = lm;
+ else
+ lo = lm + 1;
+ }
+ }
+ Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+ rb + rh, rn - rh,
+ k + lh + rh, g);
+ rn = rh;
+ ln = lh;
+ addToPendingCount(1);
+ m.fork();
+ }
+
+ int lf = lb + ln, rf = rb + rn; // index bounds
+ while (lb < lf && rb < rf) {
+ float t, al, ar;
+ if ((al = a[lb]) <= (ar = a[rb])) {
+ lb++; t = al;
+ }
+ else {
+ rb++; t = ar;
+ }
+ w[k++] = t;
+ }
+ if (rb < rf)
+ System.arraycopy(a, rb, w, k, rf - rb);
+ else if (lb < lf)
+ System.arraycopy(a, lb, w, k, lf - lb);
+ tryComplete();
+ }
+ }
+ } // FJFloat
+
+ /** double support class */
+ static final class FJDouble {
+ static final class Sorter extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final double[] a, w;
+ final int base, size, wbase, gran;
+ Sorter(CountedCompleter<?> par, double[] a, double[] w, int base,
+ int size, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w; this.base = base; this.size = size;
+ this.wbase = wbase; this.gran = gran;
+ }
+ public final void compute() {
+ CountedCompleter<?> s = this;
+ double[] a = this.a, w = this.w; // localize all params
+ int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
+ while (n > g) {
+ int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
+ Relay fc = new Relay(new Merger(s, w, a, wb, h,
+ wb+h, n-h, b, g));
+ Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
+ b+u, n-u, wb+h, g));
+ new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
+ new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
+ Relay bc = new Relay(new Merger(fc, a, w, b, q,
+ b+q, h-q, wb, g));
+ new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
+ s = new EmptyCompleter(bc);
+ n = q;
+ }
+ DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
+ s.tryComplete();
+ }
+ }
+
+ static final class Merger extends CountedCompleter<Void> {
+ static final long serialVersionUID = 2446542900576103244L;
+ final double[] a, w; // main and workspace arrays
+ final int lbase, lsize, rbase, rsize, wbase, gran;
+ Merger(CountedCompleter<?> par, double[] a, double[] w,
+ int lbase, int lsize, int rbase,
+ int rsize, int wbase, int gran) {
+ super(par);
+ this.a = a; this.w = w;
+ this.lbase = lbase; this.lsize = lsize;
+ this.rbase = rbase; this.rsize = rsize;
+ this.wbase = wbase; this.gran = gran;
+ }
+
+ public final void compute() {
+ double[] a = this.a, w = this.w; // localize all params
+ int lb = this.lbase, ln = this.lsize, rb = this.rbase,
+ rn = this.rsize, k = this.wbase, g = this.gran;
+ if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
+ throw new IllegalStateException(); // hoist checks
+ for (int lh, rh;;) { // split larger, find point in smaller
+ if (ln >= rn) {
+ if (ln <= g)
+ break;
+ rh = rn;
+ double split = a[(lh = ln >>> 1) + lb];
+ for (int lo = 0; lo < rh; ) {
+ int rm = (lo + rh) >>> 1;
+ if (split <= a[rm + rb])
+ rh = rm;
+ else
+ lo = rm + 1;
+ }
+ }
+ else {
+ if (rn <= g)
+ break;
+ lh = ln;
+ double split = a[(rh = rn >>> 1) + rb];
+ for (int lo = 0; lo < lh; ) {
+ int lm = (lo + lh) >>> 1;
+ if (split <= a[lm + lb])
+ lh = lm;
+ else
+ lo = lm + 1;
+ }
+ }
+ Merger m = new Merger(this, a, w, lb + lh, ln - lh,
+ rb + rh, rn - rh,
+ k + lh + rh, g);
+ rn = rh;
+ ln = lh;
+ addToPendingCount(1);
+ m.fork();
+ }
+
+ int lf = lb + ln, rf = rb + rn; // index bounds
+ while (lb < lf && rb < rf) {
+ double t, al, ar;
+ if ((al = a[lb]) <= (ar = a[rb])) {
+ lb++; t = al;
+ }
+ else {
+ rb++; t = ar;
+ }
+ w[k++] = t;
+ }
+ if (rb < rf)
+ System.arraycopy(a, rb, w, k, rf - rb);
+ else if (lb < lf)
+ System.arraycopy(a, lb, w, k, lf - lb);
+ tryComplete();
+ }
+ }
+ } // FJDouble
+
+}
diff --git a/openjdk_java_files.mk b/openjdk_java_files.mk
index 29bbb79..b77f2ae 100644
--- a/openjdk_java_files.mk
+++ b/openjdk_java_files.mk
@@ -649,6 +649,7 @@
ojluni/src/main/java/java/util/ArrayDeque.java \
ojluni/src/main/java/java/util/ArrayList.java \
ojluni/src/main/java/java/util/Arrays.java \
+ ojluni/src/main/java/java/util/ArraysParallelSortHelpers.java \
ojluni/src/main/java/java/util/BitSet.java \
ojluni/src/main/java/java/util/Calendar.java \
ojluni/src/main/java/java/util/Collection.java \
