|
|
Java example source code file (ParallelSorting.java)
This example Java source code file (ParallelSorting.java) is included in the alvinalexander.com
"Java Source Code
Warehouse" project. The intent of this project is to help you "Learn
Java by Example" TM.
Learn more about this Java project at its project page.
The ParallelSorting.java Java example source code
/*
* Copyright (c) 2011, 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.
*
* 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.
*/
/* Adapted from test/java/util/Arrays/Sorting.java
*
* Where that test checks Arrays.sort against manual quicksort routines,
* this test checks parallelSort against either Arrays.sort or manual
* quicksort routines.
*/
/*
* @test
* @bug 8003981
* @run main ParallelSorting -shortrun
* @summary Exercise Arrays.parallelSort (adapted from test Sorting)
*
* @author Vladimir Yaroslavskiy
* @author Jon Bentley
* @author Josh Bloch
*/
import java.util.Arrays;
import java.util.Random;
import java.io.PrintStream;
import java.util.Comparator;
public class ParallelSorting {
private static final PrintStream out = System.out;
private static final PrintStream err = System.err;
// Array lengths used in a long run (default)
private static final int[] LONG_RUN_LENGTHS = {
1000, 10000, 100000, 1000000 };
// Array lengths used in a short run
private static final int[] SHORT_RUN_LENGTHS = {
5000, 9000, 10000, 12000 };
// Random initial values used in a long run (default)
private static final long[] LONG_RUN_RANDOMS = { 666, 0xC0FFEE, 999 };
// Random initial values used in a short run
private static final long[] SHORT_RUN_RANDOMS = { 666 };
public static void main(String[] args) {
boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
long start = System.currentTimeMillis();
if (shortRun) {
testAndCheck(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
} else {
testAndCheck(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
}
long end = System.currentTimeMillis();
out.format("PASSED in %d sec.\n", Math.round((end - start) / 1E3));
}
private static void testAndCheck(int[] lengths, long[] randoms) {
testEmptyAndNullIntArray();
testEmptyAndNullLongArray();
testEmptyAndNullShortArray();
testEmptyAndNullCharArray();
testEmptyAndNullByteArray();
testEmptyAndNullFloatArray();
testEmptyAndNullDoubleArray();
for (int length : lengths) {
testMergeSort(length);
testAndCheckRange(length);
testAndCheckSubArray(length);
}
for (long seed : randoms) {
for (int length : lengths) {
testAndCheckWithInsertionSort(length, new MyRandom(seed));
testAndCheckWithCheckSum(length, new MyRandom(seed));
testAndCheckWithScrambling(length, new MyRandom(seed));
testAndCheckFloat(length, new MyRandom(seed));
testAndCheckDouble(length, new MyRandom(seed));
testStable(length, new MyRandom(seed));
}
}
}
private static void testEmptyAndNullIntArray() {
ourDescription = "Check empty and null array";
Arrays.parallelSort(new int[]{});
Arrays.parallelSort(new int[]{}, 0, 0);
try {
Arrays.parallelSort((int[]) null);
} catch (NullPointerException expected) {
try {
Arrays.parallelSort((int[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
failed("Arrays.parallelSort(int[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
failed("Arrays.parallelSort(int[]) shouldn't catch null array");
}
private static void testEmptyAndNullLongArray() {
ourDescription = "Check empty and null array";
Arrays.parallelSort(new long[]{});
Arrays.parallelSort(new long[]{}, 0, 0);
try {
Arrays.parallelSort((long[]) null);
} catch (NullPointerException expected) {
try {
Arrays.parallelSort((long[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
failed("Arrays.parallelSort(long[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
failed("Arrays.parallelSort(long[]) shouldn't catch null array");
}
private static void testEmptyAndNullShortArray() {
ourDescription = "Check empty and null array";
Arrays.parallelSort(new short[]{});
Arrays.parallelSort(new short[]{}, 0, 0);
try {
Arrays.parallelSort((short[]) null);
} catch (NullPointerException expected) {
try {
Arrays.parallelSort((short[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
failed("Arrays.parallelSort(short[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
failed("Arrays.parallelSort(short[]) shouldn't catch null array");
}
private static void testEmptyAndNullCharArray() {
ourDescription = "Check empty and null array";
Arrays.parallelSort(new char[]{});
Arrays.parallelSort(new char[]{}, 0, 0);
try {
Arrays.parallelSort((char[]) null);
} catch (NullPointerException expected) {
try {
Arrays.parallelSort((char[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
failed("Arrays.parallelSort(char[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
failed("Arrays.parallelSort(char[]) shouldn't catch null array");
}
private static void testEmptyAndNullByteArray() {
ourDescription = "Check empty and null array";
Arrays.parallelSort(new byte[]{});
Arrays.parallelSort(new byte[]{}, 0, 0);
try {
Arrays.parallelSort((byte[]) null);
} catch (NullPointerException expected) {
try {
Arrays.parallelSort((byte[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
failed("Arrays.parallelSort(byte[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
failed("Arrays.parallelSort(byte[]) shouldn't catch null array");
}
private static void testEmptyAndNullFloatArray() {
ourDescription = "Check empty and null array";
Arrays.parallelSort(new float[]{});
Arrays.parallelSort(new float[]{}, 0, 0);
try {
Arrays.parallelSort((float[]) null);
} catch (NullPointerException expected) {
try {
Arrays.parallelSort((float[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
failed("Arrays.parallelSort(float[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
failed("Arrays.parallelSort(float[]) shouldn't catch null array");
}
private static void testEmptyAndNullDoubleArray() {
ourDescription = "Check empty and null array";
Arrays.parallelSort(new double[]{});
Arrays.parallelSort(new double[]{}, 0, 0);
try {
Arrays.parallelSort((double[]) null);
} catch (NullPointerException expected) {
try {
Arrays.parallelSort((double[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
failed("Arrays.parallelSort(double[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
failed("Arrays.parallelSort(double[]) shouldn't catch null array");
}
private static void testAndCheckSubArray(int length) {
ourDescription = "Check sorting of subarray";
int[] golden = new int[length];
boolean newLine = false;
for (int m = 1; m < length / 2; m *= 2) {
newLine = true;
int fromIndex = m;
int toIndex = length - m;
prepareSubArray(golden, fromIndex, toIndex, m);
int[] test = golden.clone();
for (TypeConverter converter : TypeConverter.values()) {
out.println("Test 'subarray': " + converter +
" length = " + length + ", m = " + m);
Object convertedGolden = converter.convert(golden);
Object convertedTest = converter.convert(test);
sortSubArray(convertedTest, fromIndex, toIndex);
checkSubArray(convertedTest, fromIndex, toIndex, m);
}
}
if (newLine) {
out.println();
}
}
private static void testAndCheckRange(int length) {
ourDescription = "Check range check";
int[] golden = new int[length];
for (int m = 1; m < 2 * length; m *= 2) {
for (int i = 1; i <= length; i++) {
golden[i - 1] = i % m + m % i;
}
for (TypeConverter converter : TypeConverter.values()) {
out.println("Test 'range': " + converter +
", length = " + length + ", m = " + m);
Object convertedGolden = converter.convert(golden);
checkRange(convertedGolden, m);
}
}
out.println();
}
private static void testStable(int length, MyRandom random) {
ourDescription = "Check if sorting is stable";
Pair[] a = build(length, random);
out.println("Test 'stable': " + "random = " + random.getSeed() +
", length = " + length);
Arrays.parallelSort(a);
checkSorted(a);
checkStable(a);
out.println();
a = build(length, random);
out.println("Test 'stable' comparator: " + "random = " + random.getSeed() +
", length = " + length);
Arrays.parallelSort(a, pairCmp);
checkSorted(a);
checkStable(a);
out.println();
}
private static void checkSorted(Pair[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i].getKey() > a[i + 1].getKey()) {
failedSort(i, "" + a[i].getKey(), "" + a[i + 1].getKey());
}
}
}
private static void checkStable(Pair[] a) {
for (int i = 0; i < a.length / 4; ) {
int key1 = a[i].getKey();
int value1 = a[i++].getValue();
int key2 = a[i].getKey();
int value2 = a[i++].getValue();
int key3 = a[i].getKey();
int value3 = a[i++].getValue();
int key4 = a[i].getKey();
int value4 = a[i++].getValue();
if (!(key1 == key2 && key2 == key3 && key3 == key4)) {
failed("On position " + i + " keys are different " +
key1 + ", " + key2 + ", " + key3 + ", " + key4);
}
if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
failed("Sorting is not stable at position " + i +
". Second values have been changed: " + value1 + ", " +
value2 + ", " + value3 + ", " + value4);
}
}
}
private static Pair[] build(int length, Random random) {
Pair[] a = new Pair[length * 4];
for (int i = 0; i < a.length; ) {
int key = random.nextInt();
a[i++] = new Pair(key, 1);
a[i++] = new Pair(key, 2);
a[i++] = new Pair(key, 3);
a[i++] = new Pair(key, 4);
}
return a;
}
private static Comparator<Pair> pairCmp = new Comparator() {
public int compare(Pair p1, Pair p2) {
return p1.compareTo(p2);
}
};
private static final class Pair implements Comparable<Pair> {
Pair(int key, int value) {
myKey = key;
myValue = value;
}
int getKey() {
return myKey;
}
int getValue() {
return myValue;
}
public int compareTo(Pair pair) {
if (myKey < pair.myKey) {
return -1;
}
if (myKey > pair.myKey) {
return 1;
}
return 0;
}
@Override
public String toString() {
return "(" + myKey + ", " + myValue + ")";
}
private int myKey;
private int myValue;
}
private static void testAndCheckWithInsertionSort(int length, MyRandom random) {
if (length > 1000) {
return;
}
ourDescription = "Check sorting with insertion sort";
int[] golden = new int[length];
for (int m = 1; m < 2 * length; m *= 2) {
for (UnsortedBuilder builder : UnsortedBuilder.values()) {
builder.build(golden, m, random);
int[] test = golden.clone();
for (TypeConverter converter : TypeConverter.values()) {
out.println("Test 'insertion sort': " + converter +
" " + builder + "random = " + random.getSeed() +
", length = " + length + ", m = " + m);
Object convertedGolden = converter.convert(golden);
Object convertedTest1 = converter.convert(test);
Object convertedTest2 = converter.convert(test);
sort(convertedTest1);
sortByInsertionSort(convertedTest2);
compare(convertedTest1, convertedTest2);
}
}
}
out.println();
}
private static void testMergeSort(int length) {
if (length < 1000) {
return;
}
ourDescription = "Check merge sorting";
int[] golden = new int[length];
int period = 67; // java.util.DualPivotQuicksort.MAX_RUN_COUNT
for (int m = period - 2; m <= period + 2; m++) {
for (MergeBuilder builder : MergeBuilder.values()) {
builder.build(golden, m);
int[] test = golden.clone();
for (TypeConverter converter : TypeConverter.values()) {
out.println("Test 'merge sort': " + converter + " " +
builder + "length = " + length + ", m = " + m);
Object convertedGolden = converter.convert(golden);
sort(convertedGolden);
checkSorted(convertedGolden);
}
}
}
out.println();
}
private static void testAndCheckWithCheckSum(int length, MyRandom random) {
ourDescription = "Check sorting with check sum";
int[] golden = new int[length];
for (int m = 1; m < 2 * length; m *= 2) {
for (UnsortedBuilder builder : UnsortedBuilder.values()) {
builder.build(golden, m, random);
int[] test = golden.clone();
for (TypeConverter converter : TypeConverter.values()) {
out.println("Test 'check sum': " + converter +
" " + builder + "random = " + random.getSeed() +
", length = " + length + ", m = " + m);
Object convertedGolden = converter.convert(golden);
Object convertedTest = converter.convert(test);
sort(convertedTest);
checkWithCheckSum(convertedTest, convertedGolden);
}
}
}
out.println();
}
private static void testAndCheckWithScrambling(int length, MyRandom random) {
ourDescription = "Check sorting with scrambling";
int[] golden = new int[length];
for (int m = 1; m <= 7; m++) {
if (m > length) {
break;
}
for (SortedBuilder builder : SortedBuilder.values()) {
builder.build(golden, m);
int[] test = golden.clone();
scramble(test, random);
for (TypeConverter converter : TypeConverter.values()) {
out.println("Test 'scrambling': " + converter +
" " + builder + "random = " + random.getSeed() +
", length = " + length + ", m = " + m);
Object convertedGolden = converter.convert(golden);
Object convertedTest = converter.convert(test);
sort(convertedTest);
compare(convertedTest, convertedGolden);
}
}
}
out.println();
}
private static void testAndCheckFloat(int length, MyRandom random) {
ourDescription = "Check float sorting";
float[] golden = new float[length];
final int MAX = 10;
boolean newLine = false;
for (int a = 0; a <= MAX; a++) {
for (int g = 0; g <= MAX; g++) {
for (int z = 0; z <= MAX; z++) {
for (int n = 0; n <= MAX; n++) {
for (int p = 0; p <= MAX; p++) {
if (a + g + z + n + p > length) {
continue;
}
if (a + g + z + n + p < length) {
continue;
}
for (FloatBuilder builder : FloatBuilder.values()) {
out.println("Test 'float': random = " + random.getSeed() +
", length = " + length + ", a = " + a + ", g = " +
g + ", z = " + z + ", n = " + n + ", p = " + p);
builder.build(golden, a, g, z, n, p, random);
float[] test = golden.clone();
scramble(test, random);
sort(test);
compare(test, golden, a, n, g);
}
newLine = true;
}
}
}
}
}
if (newLine) {
out.println();
}
}
private static void testAndCheckDouble(int length, MyRandom random) {
ourDescription = "Check double sorting";
double[] golden = new double[length];
final int MAX = 10;
boolean newLine = false;
for (int a = 0; a <= MAX; a++) {
for (int g = 0; g <= MAX; g++) {
for (int z = 0; z <= MAX; z++) {
for (int n = 0; n <= MAX; n++) {
for (int p = 0; p <= MAX; p++) {
if (a + g + z + n + p > length) {
continue;
}
if (a + g + z + n + p < length) {
continue;
}
for (DoubleBuilder builder : DoubleBuilder.values()) {
out.println("Test 'double': random = " + random.getSeed() +
", length = " + length + ", a = " + a + ", g = " +
g + ", z = " + z + ", n = " + n + ", p = " + p);
builder.build(golden, a, g, z, n, p, random);
double[] test = golden.clone();
scramble(test, random);
sort(test);
compare(test, golden, a, n, g);
}
newLine = true;
}
}
}
}
}
if (newLine) {
out.println();
}
}
private static void prepareSubArray(int[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
a[i] = 0xDEDA;
}
int middle = (fromIndex + toIndex) >>> 1;
int k = 0;
for (int i = fromIndex; i < middle; i++) {
a[i] = k++;
}
for (int i = middle; i < toIndex; i++) {
a[i] = k--;
}
for (int i = toIndex; i < a.length; i++) {
a[i] = 0xBABA;
}
}
private static void scramble(int[] a, Random random) {
for (int i = 0; i < a.length * 7; i++) {
swap(a, random.nextInt(a.length), random.nextInt(a.length));
}
}
private static void scramble(float[] a, Random random) {
for (int i = 0; i < a.length * 7; i++) {
swap(a, random.nextInt(a.length), random.nextInt(a.length));
}
}
private static void scramble(double[] a, Random random) {
for (int i = 0; i < a.length * 7; i++) {
swap(a, random.nextInt(a.length), random.nextInt(a.length));
}
}
private static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void swap(float[] a, int i, int j) {
float t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void swap(double[] a, int i, int j) {
double t = a[i];
a[i] = a[j];
a[j] = t;
}
private static enum TypeConverter {
INT {
Object convert(int[] a) {
return a.clone();
}
},
LONG {
Object convert(int[] a) {
long[] b = new long[a.length];
for (int i = 0; i < a.length; i++) {
b[i] = (long) a[i];
}
return b;
}
},
BYTE {
Object convert(int[] a) {
byte[] b = new byte[a.length];
for (int i = 0; i < a.length; i++) {
b[i] = (byte) a[i];
}
return b;
}
},
SHORT {
Object convert(int[] a) {
short[] b = new short[a.length];
for (int i = 0; i < a.length; i++) {
b[i] = (short) a[i];
}
return b;
}
},
CHAR {
Object convert(int[] a) {
char[] b = new char[a.length];
for (int i = 0; i < a.length; i++) {
b[i] = (char) a[i];
}
return b;
}
},
FLOAT {
Object convert(int[] a) {
float[] b = new float[a.length];
for (int i = 0; i < a.length; i++) {
b[i] = (float) a[i];
}
return b;
}
},
DOUBLE {
Object convert(int[] a) {
double[] b = new double[a.length];
for (int i = 0; i < a.length; i++) {
b[i] = (double) a[i];
}
return b;
}
},
INTEGER {
Object convert(int[] a) {
Integer[] b = new Integer[a.length];
for (int i = 0; i < a.length; i++) {
b[i] = new Integer(a[i]);
}
return b;
}
};
abstract Object convert(int[] a);
@Override public String toString() {
String name = name();
for (int i = name.length(); i < 9; i++) {
name += " ";
}
return name;
}
}
private static enum FloatBuilder {
SIMPLE {
void build(float[] x, int a, int g, int z, int n, int p, Random random) {
int fromIndex = 0;
float negativeValue = -random.nextFloat();
float positiveValue = random.nextFloat();
writeValue(x, negativeValue, fromIndex, n);
fromIndex += n;
writeValue(x, -0.0f, fromIndex, g);
fromIndex += g;
writeValue(x, 0.0f, fromIndex, z);
fromIndex += z;
writeValue(x, positiveValue, fromIndex, p);
fromIndex += p;
writeValue(x, Float.NaN, fromIndex, a);
}
};
abstract void build(float[] x, int a, int g, int z, int n, int p, Random random);
}
private static enum DoubleBuilder {
SIMPLE {
void build(double[] x, int a, int g, int z, int n, int p, Random random) {
int fromIndex = 0;
double negativeValue = -random.nextFloat();
double positiveValue = random.nextFloat();
writeValue(x, negativeValue, fromIndex, n);
fromIndex += n;
writeValue(x, -0.0d, fromIndex, g);
fromIndex += g;
writeValue(x, 0.0d, fromIndex, z);
fromIndex += z;
writeValue(x, positiveValue, fromIndex, p);
fromIndex += p;
writeValue(x, Double.NaN, fromIndex, a);
}
};
abstract void build(double[] x, int a, int g, int z, int n, int p, Random random);
}
private static void writeValue(float[] a, float value, int fromIndex, int count) {
for (int i = fromIndex; i < fromIndex + count; i++) {
a[i] = value;
}
}
private static void compare(float[] a, float[] b, int numNaN, int numNeg, int numNegZero) {
for (int i = a.length - numNaN; i < a.length; i++) {
if (a[i] == a[i]) {
failed("On position " + i + " must be NaN instead of " + a[i]);
}
}
final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
for (int i = numNeg; i < numNeg + numNegZero; i++) {
if (NEGATIVE_ZERO != Float.floatToIntBits(a[i])) {
failed("On position " + i + " must be -0.0 instead of " + a[i]);
}
}
for (int i = 0; i < a.length - numNaN; i++) {
if (a[i] != b[i]) {
failedCompare(i, "" + a[i], "" + b[i]);
}
}
}
private static void writeValue(double[] a, double value, int fromIndex, int count) {
for (int i = fromIndex; i < fromIndex + count; i++) {
a[i] = value;
}
}
private static void compare(double[] a, double[] b, int numNaN, int numNeg, int numNegZero) {
for (int i = a.length - numNaN; i < a.length; i++) {
if (a[i] == a[i]) {
failed("On position " + i + " must be NaN instead of " + a[i]);
}
}
final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
for (int i = numNeg; i < numNeg + numNegZero; i++) {
if (NEGATIVE_ZERO != Double.doubleToLongBits(a[i])) {
failed("On position " + i + " must be -0.0 instead of " + a[i]);
}
}
for (int i = 0; i < a.length - numNaN; i++) {
if (a[i] != b[i]) {
failedCompare(i, "" + a[i], "" + b[i]);
}
}
}
private static enum SortedBuilder {
REPEATED {
void build(int[] a, int m) {
int period = a.length / m;
int i = 0;
int k = 0;
while (true) {
for (int t = 1; t <= period; t++) {
if (i >= a.length) {
return;
}
a[i++] = k;
}
if (i >= a.length) {
return;
}
k++;
}
}
},
ORGAN_PIPES {
void build(int[] a, int m) {
int i = 0;
int k = m;
while (true) {
for (int t = 1; t <= m; t++) {
if (i >= a.length) {
return;
}
a[i++] = k;
}
}
}
};
abstract void build(int[] a, int m);
@Override public String toString() {
String name = name();
for (int i = name.length(); i < 12; i++) {
name += " ";
}
return name;
}
}
private static enum MergeBuilder {
ASCENDING {
void build(int[] a, int m) {
int period = a.length / m;
int v = 1, i = 0;
for (int k = 0; k < m; k++) {
v = 1;
for (int p = 0; p < period; p++) {
a[i++] = v++;
}
}
for (int j = i; j < a.length - 1; j++) {
a[j] = v++;
}
a[a.length - 1] = 0;
}
},
DESCENDING {
void build(int[] a, int m) {
int period = a.length / m;
int v = -1, i = 0;
for (int k = 0; k < m; k++) {
v = -1;
for (int p = 0; p < period; p++) {
a[i++] = v--;
}
}
for (int j = i; j < a.length - 1; j++) {
a[j] = v--;
}
a[a.length - 1] = 0;
}
};
abstract void build(int[] a, int m);
@Override public String toString() {
String name = name();
for (int i = name.length(); i < 12; i++) {
name += " ";
}
return name;
}
}
private static enum UnsortedBuilder {
RANDOM {
void build(int[] a, int m, Random random) {
for (int i = 0; i < a.length; i++) {
a[i] = random.nextInt();
}
}
},
ASCENDING {
void build(int[] a, int m, Random random) {
for (int i = 0; i < a.length; i++) {
a[i] = m + i;
}
}
},
DESCENDING {
void build(int[] a, int m, Random random) {
for (int i = 0; i < a.length; i++) {
a[i] = a.length - m - i;
}
}
},
ALL_EQUAL {
void build(int[] a, int m, Random random) {
for (int i = 0; i < a.length; i++) {
a[i] = m;
}
}
},
SAW {
void build(int[] a, int m, Random random) {
int incCount = 1;
int decCount = a.length;
int i = 0;
int period = m--;
while (true) {
for (int k = 1; k <= period; k++) {
if (i >= a.length) {
return;
}
a[i++] = incCount++;
}
period += m;
for (int k = 1; k <= period; k++) {
if (i >= a.length) {
return;
}
a[i++] = decCount--;
}
period += m;
}
}
},
REPEATED {
void build(int[] a, int m, Random random) {
for (int i = 0; i < a.length; i++) {
a[i] = i % m;
}
}
},
DUPLICATED {
void build(int[] a, int m, Random random) {
for (int i = 0; i < a.length; i++) {
a[i] = random.nextInt(m);
}
}
},
ORGAN_PIPES {
void build(int[] a, int m, Random random) {
int middle = a.length / (m + 1);
for (int i = 0; i < middle; i++) {
a[i] = i;
}
for (int i = middle; i < a.length; i++) {
a[i] = a.length - i - 1;
}
}
},
STAGGER {
void build(int[] a, int m, Random random) {
for (int i = 0; i < a.length; i++) {
a[i] = (i * m + i) % a.length;
}
}
},
PLATEAU {
void build(int[] a, int m, Random random) {
for (int i = 0; i < a.length; i++) {
a[i] = Math.min(i, m);
}
}
},
SHUFFLE {
void build(int[] a, int m, Random random) {
int x = 0, y = 0;
for (int i = 0; i < a.length; i++) {
a[i] = random.nextBoolean() ? (x += 2) : (y += 2);
}
}
};
abstract void build(int[] a, int m, Random random);
@Override public String toString() {
String name = name();
for (int i = name.length(); i < 12; i++) {
name += " ";
}
return name;
}
}
private static void checkWithCheckSum(Object test, Object golden) {
checkSorted(test);
checkCheckSum(test, golden);
}
private static void failed(String message) {
err.format("\n*** TEST FAILED - %s.\n\n%s.\n\n", ourDescription, message);
throw new RuntimeException("Test failed - see log file for details");
}
private static void failedSort(int index, String value1, String value2) {
failed("Array is not sorted at " + index + "-th position: " +
value1 + " and " + value2);
}
private static void failedCompare(int index, String value1, String value2) {
failed("On position " + index + " must be " + value2 + " instead of " + value1);
}
private static void compare(Object test, Object golden) {
if (test instanceof int[]) {
compare((int[]) test, (int[]) golden);
} else if (test instanceof long[]) {
compare((long[]) test, (long[]) golden);
} else if (test instanceof short[]) {
compare((short[]) test, (short[]) golden);
} else if (test instanceof byte[]) {
compare((byte[]) test, (byte[]) golden);
} else if (test instanceof char[]) {
compare((char[]) test, (char[]) golden);
} else if (test instanceof float[]) {
compare((float[]) test, (float[]) golden);
} else if (test instanceof double[]) {
compare((double[]) test, (double[]) golden);
} else if (test instanceof Integer[]) {
compare((Integer[]) test, (Integer[]) golden);
} else {
failed("Unknow type of array: " + test + " of class " +
test.getClass().getName());
}
}
private static void compare(int[] a, int[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) {
failedCompare(i, "" + a[i], "" + b[i]);
}
}
}
private static void compare(long[] a, long[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) {
failedCompare(i, "" + a[i], "" + b[i]);
}
}
}
private static void compare(short[] a, short[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) {
failedCompare(i, "" + a[i], "" + b[i]);
}
}
}
private static void compare(byte[] a, byte[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) {
failedCompare(i, "" + a[i], "" + b[i]);
}
}
}
private static void compare(char[] a, char[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) {
failedCompare(i, "" + a[i], "" + b[i]);
}
}
}
private static void compare(float[] a, float[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) {
failedCompare(i, "" + a[i], "" + b[i]);
}
}
}
private static void compare(double[] a, double[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) {
failedCompare(i, "" + a[i], "" + b[i]);
}
}
}
private static void compare(Integer[] a, Integer[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i].compareTo(b[i]) != 0) {
failedCompare(i, "" + a[i], "" + b[i]);
}
}
}
private static void checkSorted(Object object) {
if (object instanceof int[]) {
checkSorted((int[]) object);
} else if (object instanceof long[]) {
checkSorted((long[]) object);
} else if (object instanceof short[]) {
checkSorted((short[]) object);
} else if (object instanceof byte[]) {
checkSorted((byte[]) object);
} else if (object instanceof char[]) {
checkSorted((char[]) object);
} else if (object instanceof float[]) {
checkSorted((float[]) object);
} else if (object instanceof double[]) {
checkSorted((double[]) object);
} else if (object instanceof Integer[]) {
checkSorted((Integer[]) object);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
}
}
private static void checkSorted(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
}
private static void checkSorted(long[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
}
private static void checkSorted(short[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
}
private static void checkSorted(byte[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
}
private static void checkSorted(char[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
}
private static void checkSorted(float[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
}
private static void checkSorted(double[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
}
private static void checkSorted(Integer[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i].intValue() > a[i + 1].intValue()) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
}
private static void checkCheckSum(Object test, Object golden) {
if (checkSumXor(test) != checkSumXor(golden)) {
failed("Original and sorted arrays are not identical [xor]");
}
if (checkSumPlus(test) != checkSumPlus(golden)) {
failed("Original and sorted arrays are not identical [plus]");
}
}
private static int checkSumXor(Object object) {
if (object instanceof int[]) {
return checkSumXor((int[]) object);
} else if (object instanceof long[]) {
return checkSumXor((long[]) object);
} else if (object instanceof short[]) {
return checkSumXor((short[]) object);
} else if (object instanceof byte[]) {
return checkSumXor((byte[]) object);
} else if (object instanceof char[]) {
return checkSumXor((char[]) object);
} else if (object instanceof float[]) {
return checkSumXor((float[]) object);
} else if (object instanceof double[]) {
return checkSumXor((double[]) object);
} else if (object instanceof Integer[]) {
return checkSumXor((Integer[]) object);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
return -1;
}
}
private static int checkSumXor(Integer[] a) {
int checkSum = 0;
for (Integer e : a) {
checkSum ^= e.intValue();
}
return checkSum;
}
private static int checkSumXor(int[] a) {
int checkSum = 0;
for (int e : a) {
checkSum ^= e;
}
return checkSum;
}
private static int checkSumXor(long[] a) {
long checkSum = 0;
for (long e : a) {
checkSum ^= e;
}
return (int) checkSum;
}
private static int checkSumXor(short[] a) {
short checkSum = 0;
for (short e : a) {
checkSum ^= e;
}
return (int) checkSum;
}
private static int checkSumXor(byte[] a) {
byte checkSum = 0;
for (byte e : a) {
checkSum ^= e;
}
return (int) checkSum;
}
private static int checkSumXor(char[] a) {
char checkSum = 0;
for (char e : a) {
checkSum ^= e;
}
return (int) checkSum;
}
private static int checkSumXor(float[] a) {
int checkSum = 0;
for (float e : a) {
checkSum ^= (int) e;
}
return checkSum;
}
private static int checkSumXor(double[] a) {
int checkSum = 0;
for (double e : a) {
checkSum ^= (int) e;
}
return checkSum;
}
private static int checkSumPlus(Object object) {
if (object instanceof int[]) {
return checkSumPlus((int[]) object);
} else if (object instanceof long[]) {
return checkSumPlus((long[]) object);
} else if (object instanceof short[]) {
return checkSumPlus((short[]) object);
} else if (object instanceof byte[]) {
return checkSumPlus((byte[]) object);
} else if (object instanceof char[]) {
return checkSumPlus((char[]) object);
} else if (object instanceof float[]) {
return checkSumPlus((float[]) object);
} else if (object instanceof double[]) {
return checkSumPlus((double[]) object);
} else if (object instanceof Integer[]) {
return checkSumPlus((Integer[]) object);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
return -1;
}
}
private static int checkSumPlus(int[] a) {
int checkSum = 0;
for (int e : a) {
checkSum += e;
}
return checkSum;
}
private static int checkSumPlus(long[] a) {
long checkSum = 0;
for (long e : a) {
checkSum += e;
}
return (int) checkSum;
}
private static int checkSumPlus(short[] a) {
short checkSum = 0;
for (short e : a) {
checkSum += e;
}
return (int) checkSum;
}
private static int checkSumPlus(byte[] a) {
byte checkSum = 0;
for (byte e : a) {
checkSum += e;
}
return (int) checkSum;
}
private static int checkSumPlus(char[] a) {
char checkSum = 0;
for (char e : a) {
checkSum += e;
}
return (int) checkSum;
}
private static int checkSumPlus(float[] a) {
int checkSum = 0;
for (float e : a) {
checkSum += (int) e;
}
return checkSum;
}
private static int checkSumPlus(double[] a) {
int checkSum = 0;
for (double e : a) {
checkSum += (int) e;
}
return checkSum;
}
private static int checkSumPlus(Integer[] a) {
int checkSum = 0;
for (Integer e : a) {
checkSum += e.intValue();
}
return checkSum;
}
private static void sortByInsertionSort(Object object) {
if (object instanceof int[]) {
sortByInsertionSort((int[]) object);
} else if (object instanceof long[]) {
sortByInsertionSort((long[]) object);
} else if (object instanceof short[]) {
sortByInsertionSort((short[]) object);
} else if (object instanceof byte[]) {
sortByInsertionSort((byte[]) object);
} else if (object instanceof char[]) {
sortByInsertionSort((char[]) object);
} else if (object instanceof float[]) {
sortByInsertionSort((float[]) object);
} else if (object instanceof double[]) {
sortByInsertionSort((double[]) object);
} else if (object instanceof Integer[]) {
sortByInsertionSort((Integer[]) object);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
}
}
private static void sortByInsertionSort(int[] a) {
for (int j, i = 1; i < a.length; i++) {
int ai = a[i];
for (j = i - 1; j >= 0 && ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
}
private static void sortByInsertionSort(long[] a) {
for (int j, i = 1; i < a.length; i++) {
long ai = a[i];
for (j = i - 1; j >= 0 && ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
}
private static void sortByInsertionSort(short[] a) {
for (int j, i = 1; i < a.length; i++) {
short ai = a[i];
for (j = i - 1; j >= 0 && ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
}
private static void sortByInsertionSort(byte[] a) {
for (int j, i = 1; i < a.length; i++) {
byte ai = a[i];
for (j = i - 1; j >= 0 && ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
}
private static void sortByInsertionSort(char[] a) {
for (int j, i = 1; i < a.length; i++) {
char ai = a[i];
for (j = i - 1; j >= 0 && ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
}
private static void sortByInsertionSort(float[] a) {
for (int j, i = 1; i < a.length; i++) {
float ai = a[i];
for (j = i - 1; j >= 0 && ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
}
private static void sortByInsertionSort(double[] a) {
for (int j, i = 1; i < a.length; i++) {
double ai = a[i];
for (j = i - 1; j >= 0 && ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
}
private static void sortByInsertionSort(Integer[] a) {
for (int j, i = 1; i < a.length; i++) {
Integer ai = a[i];
for (j = i - 1; j >= 0 && ai < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = ai;
}
}
private static void sort(Object object) {
if (object instanceof int[]) {
Arrays.parallelSort((int[]) object);
} else if (object instanceof long[]) {
Arrays.parallelSort((long[]) object);
} else if (object instanceof short[]) {
Arrays.parallelSort((short[]) object);
} else if (object instanceof byte[]) {
Arrays.parallelSort((byte[]) object);
} else if (object instanceof char[]) {
Arrays.parallelSort((char[]) object);
} else if (object instanceof float[]) {
Arrays.parallelSort((float[]) object);
} else if (object instanceof double[]) {
Arrays.parallelSort((double[]) object);
} else if (object instanceof Integer[]) {
Arrays.parallelSort((Integer[]) object);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
}
}
private static void sortSubArray(Object object, int fromIndex, int toIndex) {
if (object instanceof int[]) {
Arrays.parallelSort((int[]) object, fromIndex, toIndex);
} else if (object instanceof long[]) {
Arrays.parallelSort((long[]) object, fromIndex, toIndex);
} else if (object instanceof short[]) {
Arrays.parallelSort((short[]) object, fromIndex, toIndex);
} else if (object instanceof byte[]) {
Arrays.parallelSort((byte[]) object, fromIndex, toIndex);
} else if (object instanceof char[]) {
Arrays.parallelSort((char[]) object, fromIndex, toIndex);
} else if (object instanceof float[]) {
Arrays.parallelSort((float[]) object, fromIndex, toIndex);
} else if (object instanceof double[]) {
Arrays.parallelSort((double[]) object, fromIndex, toIndex);
} else if (object instanceof Integer[]) {
Arrays.parallelSort((Integer[]) object, fromIndex, toIndex);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
}
}
private static void checkSubArray(Object object, int fromIndex, int toIndex, int m) {
if (object instanceof int[]) {
checkSubArray((int[]) object, fromIndex, toIndex, m);
} else if (object instanceof long[]) {
checkSubArray((long[]) object, fromIndex, toIndex, m);
} else if (object instanceof short[]) {
checkSubArray((short[]) object, fromIndex, toIndex, m);
} else if (object instanceof byte[]) {
checkSubArray((byte[]) object, fromIndex, toIndex, m);
} else if (object instanceof char[]) {
checkSubArray((char[]) object, fromIndex, toIndex, m);
} else if (object instanceof float[]) {
checkSubArray((float[]) object, fromIndex, toIndex, m);
} else if (object instanceof double[]) {
checkSubArray((double[]) object, fromIndex, toIndex, m);
} else if (object instanceof Integer[]) {
checkSubArray((Integer[]) object, fromIndex, toIndex, m);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
}
}
private static void checkSubArray(Integer[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
if (a[i].intValue() != 0xDEDA) {
failed("Range sort changes left element on position " + i +
": " + a[i] + ", must be " + 0xDEDA);
}
}
for (int i = fromIndex; i < toIndex - 1; i++) {
if (a[i].intValue() > a[i + 1].intValue()) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
for (int i = toIndex; i < a.length; i++) {
if (a[i].intValue() != 0xBABA) {
failed("Range sort changes right element on position " + i +
": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
if (a[i] != 0xDEDA) {
failed("Range sort changes left element on position " + i +
": " + a[i] + ", must be " + 0xDEDA);
}
}
for (int i = fromIndex; i < toIndex - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
for (int i = toIndex; i < a.length; i++) {
if (a[i] != 0xBABA) {
failed("Range sort changes right element on position " + i +
": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(byte[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
if (a[i] != (byte) 0xDEDA) {
failed("Range sort changes left element on position " + i +
": " + a[i] + ", must be " + 0xDEDA);
}
}
for (int i = fromIndex; i < toIndex - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
for (int i = toIndex; i < a.length; i++) {
if (a[i] != (byte) 0xBABA) {
failed("Range sort changes right element on position " + i +
": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(long[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
if (a[i] != (long) 0xDEDA) {
failed("Range sort changes left element on position " + i +
": " + a[i] + ", must be " + 0xDEDA);
}
}
for (int i = fromIndex; i < toIndex - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
for (int i = toIndex; i < a.length; i++) {
if (a[i] != (long) 0xBABA) {
failed("Range sort changes right element on position " + i +
": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(char[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
if (a[i] != (char) 0xDEDA) {
failed("Range sort changes left element on position " + i +
": " + a[i] + ", must be " + 0xDEDA);
}
}
for (int i = fromIndex; i < toIndex - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
for (int i = toIndex; i < a.length; i++) {
if (a[i] != (char) 0xBABA) {
failed("Range sort changes right element on position " + i +
": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(short[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
if (a[i] != (short) 0xDEDA) {
failed("Range sort changes left element on position " + i +
": " + a[i] + ", must be " + 0xDEDA);
}
}
for (int i = fromIndex; i < toIndex - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
for (int i = toIndex; i < a.length; i++) {
if (a[i] != (short) 0xBABA) {
failed("Range sort changes right element on position " + i +
": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(float[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
if (a[i] != (float) 0xDEDA) {
failed("Range sort changes left element on position " + i +
": " + a[i] + ", must be " + 0xDEDA);
}
}
for (int i = fromIndex; i < toIndex - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
for (int i = toIndex; i < a.length; i++) {
if (a[i] != (float) 0xBABA) {
failed("Range sort changes right element on position " + i +
": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkSubArray(double[] a, int fromIndex, int toIndex, int m) {
for (int i = 0; i < fromIndex; i++) {
if (a[i] != (double) 0xDEDA) {
failed("Range sort changes left element on position " + i +
": " + a[i] + ", must be " + 0xDEDA);
}
}
for (int i = fromIndex; i < toIndex - 1; i++) {
if (a[i] > a[i + 1]) {
failedSort(i, "" + a[i], "" + a[i + 1]);
}
}
for (int i = toIndex; i < a.length; i++) {
if (a[i] != (double) 0xBABA) {
failed("Range sort changes right element on position " + i +
": " + a[i] + ", must be " + 0xBABA);
}
}
}
private static void checkRange(Object object, int m) {
if (object instanceof int[]) {
checkRange((int[]) object, m);
} else if (object instanceof long[]) {
checkRange((long[]) object, m);
} else if (object instanceof short[]) {
checkRange((short[]) object, m);
} else if (object instanceof byte[]) {
checkRange((byte[]) object, m);
} else if (object instanceof char[]) {
checkRange((char[]) object, m);
} else if (object instanceof float[]) {
checkRange((float[]) object, m);
} else if (object instanceof double[]) {
checkRange((double[]) object, m);
} else if (object instanceof Integer[]) {
checkRange((Integer[]) object, m);
} else {
failed("Unknow type of array: " + object + " of class " +
object.getClass().getName());
}
}
private static void checkRange(Integer[] a, int m) {
try {
Arrays.parallelSort(a, m + 1, m);
failed("ParallelSort does not throw IllegalArgumentException " +
" as expected: fromIndex = " + (m + 1) +
" toIndex = " + m);
}
catch (IllegalArgumentException iae) {
try {
Arrays.parallelSort(a, -m, a.length);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
}
catch (ArrayIndexOutOfBoundsException aoe) {
try {
Arrays.parallelSort(a, 0, a.length + m);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
}
catch (ArrayIndexOutOfBoundsException aie) {
return;
}
}
}
}
private static void checkRange(int[] a, int m) {
try {
Arrays.parallelSort(a, m + 1, m);
failed("ParallelSort does not throw IllegalArgumentException " +
" as expected: fromIndex = " + (m + 1) +
" toIndex = " + m);
}
catch (IllegalArgumentException iae) {
try {
Arrays.parallelSort(a, -m, a.length);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
}
catch (ArrayIndexOutOfBoundsException aoe) {
try {
Arrays.parallelSort(a, 0, a.length + m);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
}
catch (ArrayIndexOutOfBoundsException aie) {
return;
}
}
}
}
private static void checkRange(long[] a, int m) {
try {
Arrays.parallelSort(a, m + 1, m);
failed("ParallelSort does not throw IllegalArgumentException " +
" as expected: fromIndex = " + (m + 1) +
" toIndex = " + m);
}
catch (IllegalArgumentException iae) {
try {
Arrays.parallelSort(a, -m, a.length);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
}
catch (ArrayIndexOutOfBoundsException aoe) {
try {
Arrays.parallelSort(a, 0, a.length + m);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
}
catch (ArrayIndexOutOfBoundsException aie) {
return;
}
}
}
}
private static void checkRange(byte[] a, int m) {
try {
Arrays.parallelSort(a, m + 1, m);
failed("ParallelSort does not throw IllegalArgumentException " +
" as expected: fromIndex = " + (m + 1) +
" toIndex = " + m);
}
catch (IllegalArgumentException iae) {
try {
Arrays.parallelSort(a, -m, a.length);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
}
catch (ArrayIndexOutOfBoundsException aoe) {
try {
Arrays.parallelSort(a, 0, a.length + m);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
}
catch (ArrayIndexOutOfBoundsException aie) {
return;
}
}
}
}
private static void checkRange(short[] a, int m) {
try {
Arrays.parallelSort(a, m + 1, m);
failed("ParallelSort does not throw IllegalArgumentException " +
" as expected: fromIndex = " + (m + 1) +
" toIndex = " + m);
}
catch (IllegalArgumentException iae) {
try {
Arrays.parallelSort(a, -m, a.length);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
}
catch (ArrayIndexOutOfBoundsException aoe) {
try {
Arrays.parallelSort(a, 0, a.length + m);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
}
catch (ArrayIndexOutOfBoundsException aie) {
return;
}
}
}
}
private static void checkRange(char[] a, int m) {
try {
Arrays.parallelSort(a, m + 1, m);
failed("ParallelSort does not throw IllegalArgumentException " +
" as expected: fromIndex = " + (m + 1) +
" toIndex = " + m);
}
catch (IllegalArgumentException iae) {
try {
Arrays.parallelSort(a, -m, a.length);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
}
catch (ArrayIndexOutOfBoundsException aoe) {
try {
Arrays.parallelSort(a, 0, a.length + m);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
}
catch (ArrayIndexOutOfBoundsException aie) {
return;
}
}
}
}
private static void checkRange(float[] a, int m) {
try {
Arrays.parallelSort(a, m + 1, m);
failed("ParallelSort does not throw IllegalArgumentException " +
" as expected: fromIndex = " + (m + 1) +
" toIndex = " + m);
}
catch (IllegalArgumentException iae) {
try {
Arrays.parallelSort(a, -m, a.length);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
}
catch (ArrayIndexOutOfBoundsException aoe) {
try {
Arrays.parallelSort(a, 0, a.length + m);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
}
catch (ArrayIndexOutOfBoundsException aie) {
return;
}
}
}
}
private static void checkRange(double[] a, int m) {
try {
Arrays.parallelSort(a, m + 1, m);
failed("ParallelSort does not throw IllegalArgumentException " +
" as expected: fromIndex = " + (m + 1) +
" toIndex = " + m);
}
catch (IllegalArgumentException iae) {
try {
Arrays.parallelSort(a, -m, a.length);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
}
catch (ArrayIndexOutOfBoundsException aoe) {
try {
Arrays.parallelSort(a, 0, a.length + m);
failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
}
catch (ArrayIndexOutOfBoundsException aie) {
return;
}
}
}
}
private static void outArray(Object[] a) {
for (int i = 0; i < a.length; i++) {
out.print(a[i] + " ");
}
out.println();
}
private static void outArray(int[] a) {
for (int i = 0; i < a.length; i++) {
out.print(a[i] + " ");
}
out.println();
}
private static void outArray(float[] a) {
for (int i = 0; i < a.length; i++) {
out.print(a[i] + " ");
}
out.println();
}
private static void outArray(double[] a) {
for (int i = 0; i < a.length; i++) {
out.print(a[i] + " ");
}
out.println();
}
private static class MyRandom extends Random {
MyRandom(long seed) {
super(seed);
mySeed = seed;
}
long getSeed() {
return mySeed;
}
private long mySeed;
}
private static String ourDescription;
}
Other Java examples (source code examples)
Here is a short list of links related to this Java ParallelSorting.java source code file:
|
The search page
Other Java source code examples at this package level
Click here to learn more about this project
