< prev index next >
test/jdk/java/util/Arrays/Sorting.java
Print this page
*** 1,16 ****
/*
! * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* 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,
--- 1,16 ----
/*
! * Copyright (c) 2009, 2019, 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,
*** 21,296 ****
* questions.
*/
/*
* @test
! * @bug 6880672 6896573 6899694 6976036 7013585 7018258
! * @summary Exercise Arrays.sort
* @build Sorting
* @run main Sorting -shortrun
*
* @author Vladimir Yaroslavskiy
* @author Jon Bentley
* @author Josh Bloch
*/
import java.util.Arrays;
import java.util.Random;
! import java.io.PrintStream;
public class Sorting {
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 = {
! 1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000 };
// Array lengths used in a short run
private static final int[] SHORT_RUN_LENGTHS = {
! 1, 2, 3, 21, 55, 1000, 10000 };
// 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.sort(new int[] {});
! Arrays.sort(new int[] {}, 0, 0);
try {
! Arrays.sort((int[]) null);
} catch (NullPointerException expected) {
try {
! Arrays.sort((int[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! failed("Arrays.sort(int[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! failed("Arrays.sort(int[]) shouldn't catch null array");
}
private static void testEmptyAndNullLongArray() {
! ourDescription = "Check empty and null array";
! Arrays.sort(new long[] {});
! Arrays.sort(new long[] {}, 0, 0);
try {
! Arrays.sort((long[]) null);
} catch (NullPointerException expected) {
try {
! Arrays.sort((long[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! failed("Arrays.sort(long[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! failed("Arrays.sort(long[]) shouldn't catch null array");
}
! private static void testEmptyAndNullShortArray() {
! ourDescription = "Check empty and null array";
! Arrays.sort(new short[] {});
! Arrays.sort(new short[] {}, 0, 0);
try {
! Arrays.sort((short[]) null);
} catch (NullPointerException expected) {
try {
! Arrays.sort((short[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! failed("Arrays.sort(short[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! failed("Arrays.sort(short[]) shouldn't catch null array");
}
private static void testEmptyAndNullCharArray() {
! ourDescription = "Check empty and null array";
! Arrays.sort(new char[] {});
! Arrays.sort(new char[] {}, 0, 0);
try {
! Arrays.sort((char[]) null);
} catch (NullPointerException expected) {
try {
! Arrays.sort((char[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! failed("Arrays.sort(char[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! failed("Arrays.sort(char[]) shouldn't catch null array");
}
! private static void testEmptyAndNullByteArray() {
! ourDescription = "Check empty and null array";
! Arrays.sort(new byte[] {});
! Arrays.sort(new byte[] {}, 0, 0);
try {
! Arrays.sort((byte[]) null);
} catch (NullPointerException expected) {
try {
! Arrays.sort((byte[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! failed("Arrays.sort(byte[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! failed("Arrays.sort(byte[]) shouldn't catch null array");
}
private static void testEmptyAndNullFloatArray() {
! ourDescription = "Check empty and null array";
! Arrays.sort(new float[] {});
! Arrays.sort(new float[] {}, 0, 0);
try {
! Arrays.sort((float[]) null);
} catch (NullPointerException expected) {
try {
! Arrays.sort((float[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! failed("Arrays.sort(float[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! failed("Arrays.sort(float[]) shouldn't catch null array");
}
private static void testEmptyAndNullDoubleArray() {
! ourDescription = "Check empty and null array";
! Arrays.sort(new double[] {});
! Arrays.sort(new double[] {}, 0, 0);
try {
! Arrays.sort((double[]) null);
} catch (NullPointerException expected) {
try {
! Arrays.sort((double[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! failed("Arrays.sort(double[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! failed("Arrays.sort(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.sort(a);
- 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) {
--- 21,371 ----
* questions.
*/
/*
* @test
! * @compile/module=java.base java/util/SortingHelper.java
! * @bug 6880672 6896573 6899694 6976036 7013585 7018258 8003981 8226297
* @build Sorting
* @run main Sorting -shortrun
+ * @summary Exercise Arrays.sort, Arrays.parallelSort
*
* @author Vladimir Yaroslavskiy
* @author Jon Bentley
* @author Josh Bloch
*/
+ import java.io.PrintStream;
import java.util.Arrays;
+ import java.util.Comparator;
import java.util.Random;
! import java.util.SortingHelper;
public class Sorting {
+
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 = {
! 1, 2, 3, 5, 8, 13, 21, 34, 55, 88, 100, 1000, 10000, 100000, 1000000 };
// Array lengths used in a short run
private static final int[] SHORT_RUN_LENGTHS = {
! 1, 2, 3, 21, 55, 1000, 10000, 17000 };
// Random initial values used in a long run (default)
! private static final long[] LONG_RUN_RANDOMS = { 0xBABA, 0xDEDA, 0xC0FFEE };
// Random initial values used in a short run
! private static final long[] SHORT_RUN_RANDOMS = { 0xC0FFEE };
!
! // Constants used in subarray sorting
! private static final int A380 = 0xA380;
! private static final int B747 = 0xB747;
!
! private static SortingHelper sortingHelper;
! private static String name;
public static void main(String[] args) {
boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
long start = System.currentTimeMillis();
+ // Check Dual-Pivot Quicksort
+ sortingHelper = SortingHelper.getDualPivotQuicksortHelper();
+
if (shortRun) {
! testQuicksort(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
} else {
! testQuicksort(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
! }
!
! // Check Parallel sort
! sortingHelper = SortingHelper.getParallelSortHelper();
!
! if (shortRun) {
! testQuicksort(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
! } else {
! testQuicksort(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
}
! // Check Heap sort
! sortingHelper = SortingHelper.getHeapSortHelper();
! testHeapSort(shortRun ? SHORT_RUN_RANDOMS : LONG_RUN_RANDOMS);
!
! // Check Object sort
! if (shortRun) {
! testObject(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
! } else {
! testObject(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
! }
!
! long end = System.currentTimeMillis();
! out.format("\nPASSED in %d sec.\n", (end - start) / 1000);
}
! private static void testQuicksort(int[] lengths, long[] randoms) {
testEmptyAndNullIntArray();
testEmptyAndNullLongArray();
testEmptyAndNullByteArray();
+ testEmptyAndNullCharArray();
+ testEmptyAndNullShortArray();
testEmptyAndNullFloatArray();
testEmptyAndNullDoubleArray();
for (int length : lengths) {
! testMergingSort(length);
testAndCheckRange(length);
testAndCheckSubArray(length);
}
!
! for (long random : randoms) {
for (int length : lengths) {
! testAndCheckWithInsertionSort(length, new TestRandom(random));
! testAndCheckWithCheckSum(length, new TestRandom(random));
! testAndCheckWithScrambling(length, new TestRandom(random));
! testFloatNegativeZero(length, new TestRandom(random));
! testAndCheckFloat(length, new TestRandom(random));
! testDoubleNegativeZero(length, new TestRandom(random));
! testAndCheckDouble(length, new TestRandom(random));
}
}
}
+ private static void testHeapSort(long[] randoms) {
+ for (long random : randoms) {
+ for (int length : SHORT_RUN_LENGTHS) {
+ testAndCheckWithCheckSum(length, new TestRandom(random));
+ testAndCheckWithScrambling(length, new TestRandom(random));
+ }
+ }
+ }
+
+ private static void testObject(int[] lengths, long[] randoms) {
+ for (long random : randoms) {
+ for (int length : lengths) {
+ testObject(length, new TestRandom(random));
+ testParallelObject(length, new TestRandom(random));
+ }
+ }
+ }
+
+ private static void testObject(int length, TestRandom random) {
+ name = "sorting is stable";
+ Pair[] a = build(length, random);
+ out.println("[Object Sorting] 'stable' random = " +
+ random.getSeed() + ", length = " + length);
+ Arrays.sort(a);
+ checkSorted(a);
+ checkStable(a);
+
+ a = build(length, random);
+ out.println("[Object Sorting] 'comparator' " +
+ " random = " + random.getSeed() + ", length = " + length);
+ Arrays.sort(a, pairComparator);
+ checkSorted(a);
+ checkStable(a);
+ }
+
+ private static void testParallelObject(int length, TestRandom random) {
+ name = "parallel sorting is stable";
+ Pair[] a = build(length, random);
+ out.println("[Object Sorting] 'parallel stable' random = " +
+ random.getSeed() + ", length = " + length);
+ Arrays.parallelSort(a);
+ checkSorted(a);
+ checkStable(a);
+
+ a = build(length, random);
+ out.println("[Object Sorting] 'parallel comparator'" +
+ " random = " + random.getSeed() + ", length = " + length);
+ Arrays.parallelSort(a, pairComparator);
+ checkSorted(a);
+ checkStable(a);
+ }
+
private static void testEmptyAndNullIntArray() {
! name = "Empty and null array";
! sortingHelper.sort(new int[] {});
! sortingHelper.sort(new int[] {}, 0, 0);
try {
! sortingHelper.sort((int[]) null);
} catch (NullPointerException expected) {
try {
! sortingHelper.sort((int[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! fail(sortingHelper + "(int[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! fail(sortingHelper + "(int[]) shouldn't catch null array");
}
private static void testEmptyAndNullLongArray() {
! name = "Empty and null array";
! sortingHelper.sort(new long[] {});
! sortingHelper.sort(new long[] {}, 0, 0);
try {
! sortingHelper.sort((long[]) null);
} catch (NullPointerException expected) {
try {
! sortingHelper.sort((long[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! fail(sortingHelper + "(long[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! fail(sortingHelper + "(long[]) shouldn't catch null array");
}
! private static void testEmptyAndNullByteArray() {
! name = "Empty and null array";
! sortingHelper.sort(new byte[] {});
! sortingHelper.sort(new byte[] {}, 0, 0);
try {
! sortingHelper.sort((byte[]) null);
} catch (NullPointerException expected) {
try {
! sortingHelper.sort((byte[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! fail(sortingHelper + "(byte[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! fail(sortingHelper + "(byte[]) shouldn't catch null array");
}
private static void testEmptyAndNullCharArray() {
! name = "Empty and null array";
! sortingHelper.sort(new char[] {});
! sortingHelper.sort(new char[] {}, 0, 0);
try {
! sortingHelper.sort((char[]) null);
} catch (NullPointerException expected) {
try {
! sortingHelper.sort((char[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! fail(sortingHelper + "(char[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! fail(sortingHelper + "(char[]) shouldn't catch null array");
}
! private static void testEmptyAndNullShortArray() {
! name = "Empty and null array";
! sortingHelper.sort(new short[] {});
! sortingHelper.sort(new short[] {}, 0, 0);
try {
! sortingHelper.sort((short[]) null);
} catch (NullPointerException expected) {
try {
! sortingHelper.sort((short[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! fail(sortingHelper + "(short[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! fail(sortingHelper + "(short[]) shouldn't catch null array");
}
private static void testEmptyAndNullFloatArray() {
! name = "Empty and null array";
! sortingHelper.sort(new float[] {});
! sortingHelper.sort(new float[] {}, 0, 0);
try {
! sortingHelper.sort((float[]) null);
} catch (NullPointerException expected) {
try {
! sortingHelper.sort((float[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! fail(sortingHelper + "(float[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! fail(sortingHelper + "(float[]) shouldn't catch null array");
}
private static void testEmptyAndNullDoubleArray() {
! name = "Empty and null array";
! sortingHelper.sort(new double[] {});
! sortingHelper.sort(new double[] {}, 0, 0);
try {
! sortingHelper.sort((double[]) null);
} catch (NullPointerException expected) {
try {
! sortingHelper.sort((double[]) null, 0, 0);
} catch (NullPointerException expected2) {
return;
}
! fail(sortingHelper + "(double[],fromIndex,toIndex) shouldn't " +
"catch null array");
}
! fail(sortingHelper + "(double[]) shouldn't catch null array");
}
private static void testAndCheckSubArray(int length) {
! name = "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);
int[] test = golden.clone();
for (TypeConverter converter : TypeConverter.values()) {
! out.println(getTestName() + converter +
! " length = " + length + ", m = " + m);
Object convertedTest = converter.convert(test);
sortSubArray(convertedTest, fromIndex, toIndex);
! checkSubArray(convertedTest, fromIndex, toIndex);
}
}
if (newLine) {
out.println();
}
}
private static void testAndCheckRange(int length) {
! name = "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(getTestName() + converter +
! " length = " + length + ", m = " + m);
Object convertedGolden = converter.convert(golden);
checkRange(convertedGolden, m);
}
}
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()) {
! failSort(i, "" + a[i].getKey(), "" + a[i + 1].getKey());
}
}
}
private static void checkStable(Pair[] a) {
*** 303,318 ****
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);
}
}
}
--- 378,393 ----
int value3 = a[i++].getValue();
int key4 = a[i].getKey();
int value4 = a[i++].getValue();
if (!(key1 == key2 && key2 == key3 && key3 == key4)) {
! fail("On position " + i + " keys are different " +
key1 + ", " + key2 + ", " + key3 + ", " + key4);
}
if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
! fail("Sorting is not stable at position " + i +
! ". Second values have been changed: " + value1 + ", " +
value2 + ", " + value3 + ", " + value4);
}
}
}
*** 327,387 ****
a[i++] = new Pair(key, 4);
}
return a;
}
! 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);
--- 402,464 ----
a[i++] = new Pair(key, 4);
}
return a;
}
! private static Comparator<Pair> pairComparator = new Comparator<Pair>() {
!
! @Override
! public int compare(Pair p1, Pair p2) {
! return p1.compareTo(p2);
! }
! };
!
! private static class Pair implements Comparable<Pair> {
!
! private Pair(int key, int value) {
! this.key = key;
! this.value = value;
}
int getKey() {
! return key;
}
int getValue() {
! return value;
}
+ @Override
public int compareTo(Pair pair) {
! return Integer.compare(key, pair.key);
}
@Override
public String toString() {
! return "(" + key + ", " + value + ")";
}
! private int key;
! private int value;
}
! private static void testAndCheckWithInsertionSort(int length, TestRandom random) {
if (length > 1000) {
return;
}
! name = "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(getTestName() + converter + " " +
! builder + "random = " + random.getSeed() + ", length = " +
! length + ", m = " + m);
Object convertedTest1 = converter.convert(test);
Object convertedTest2 = converter.convert(test);
sort(convertedTest1);
sortByInsertionSort(convertedTest2);
compare(convertedTest1, convertedTest2);
*** 389,434 ****
}
}
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);
--- 466,510 ----
}
}
out.println();
}
! private static void testMergingSort(int length) {
if (length < 1000) {
return;
}
! name = "Merging sort";
int[] golden = new int[length];
! final int PERIOD = 50;
! for (int m = PERIOD - 2; m <= PERIOD + 2; ++m) {
! for (MergingBuilder builder : MergingBuilder.values()) {
builder.build(golden, m);
for (TypeConverter converter : TypeConverter.values()) {
! out.println(getTestName() + converter +
! " " + builder + "length = " + length + ", m = " + m);
Object convertedGolden = converter.convert(golden);
sort(convertedGolden);
checkSorted(convertedGolden);
}
}
}
out.println();
}
! private static void testAndCheckWithCheckSum(int length, TestRandom random) {
! name = "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(getTestName() + converter +
" " + builder + "random = " + random.getSeed() +
", length = " + length + ", m = " + m);
Object convertedGolden = converter.convert(golden);
Object convertedTest = converter.convert(test);
sort(convertedTest);
*** 437,494 ****
}
}
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);
--- 513,568 ----
}
}
out.println();
}
! private static void testAndCheckWithScrambling(int length, TestRandom random) {
! name = "Sorting with scrambling";
int[] golden = new int[length];
! for (int m = 1; m < 8; ++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(getTestName() + 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, TestRandom random) {
! name = "Float sorting";
float[] golden = new float[length];
boolean newLine = false;
+ final int MAX = 13;
! 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;
}
for (FloatBuilder builder : FloatBuilder.values()) {
! out.println(getTestName() + "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);
*** 500,532 ****
}
}
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);
--- 574,636 ----
}
}
if (newLine) {
out.println();
}
+
+ for (int m = 13; m > 4; --m) {
+ int t = length / m;
+ int g = t, z = t, n = t, p = t;
+ int a = length - g - z - n - p;
+
+ for (FloatBuilder builder : FloatBuilder.values()) {
+ out.println(getTestName() + "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);
+ }
+ }
+ out.println();
}
! private static void testFloatNegativeZero(int length, TestRandom random) {
! name = "Float -0.0";
! out.println(getTestName() + "random = " + random.getSeed() + " length = " + length);
! float[] a = new float[length];
!
! for (int i = 0; i < length; ++i) {
! a[i] = random.nextBoolean() ? -0.0f : 0.0f;
! }
! sort(a);
! checkNegativeZero(a);
! out.println();
! }
!
! private static void testAndCheckDouble(int length, TestRandom random) {
! name = "Double sorting";
double[] golden = new double[length];
boolean newLine = false;
+ final int MAX = 13;
! 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;
}
for (DoubleBuilder builder : DoubleBuilder.values()) {
! out.println(getTestName() + "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);
*** 538,581 ****
}
}
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) {
--- 642,717 ----
}
}
if (newLine) {
out.println();
}
+
+ for (int m = 13; m > 4; --m) {
+ int t = length / m;
+ int g = t, z = t, n = t, p = t;
+ int a = length - g - z - n - p;
+
+ for (DoubleBuilder builder : DoubleBuilder.values()) {
+ out.println(getTestName() + "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);
+ }
+ }
+ out.println();
+ }
+
+ private static void testDoubleNegativeZero(int length, TestRandom random) {
+ name = "Double -0.0";
+ out.println(getTestName() + "random = " + random.getSeed() + " length = " + length);
+ double[] a = new double[length];
+
+ for (int i = 0; i < length; ++i) {
+ a[i] = random.nextBoolean() ? -0.0d : 0.0d;
+ }
+ sort(a);
+ checkNegativeZero(a);
+ out.println();
}
! private static void prepareSubArray(int[] a, int fromIndex, int toIndex) {
! for (int i = 0; i < fromIndex; ++i) {
! a[i] = A380;
}
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] = B747;
}
}
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) {
*** 594,693 ****
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();
--- 730,828 ----
double t = a[i];
a[i] = a[j];
a[j] = t;
}
! private 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;
}
};
abstract Object convert(int[] a);
! @Override
! public String toString() {
String name = name();
! for (int i = name.length(); i < 9; ++i) {
name += " ";
}
return name;
}
}
! private 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();
*** 709,719 ****
};
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();
--- 844,855 ----
};
abstract void build(float[] x, int a, int g, int z, int n, int p, Random random);
}
! private 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();
*** 736,1026 ****
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);
--- 872,1245 ----
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]) {
! fail("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])) {
! fail("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]) {
! failCompare(i, "" + a[i], "" + b[i]);
! }
! }
! }
!
! private static void checkNegativeZero(float[] a) {
! for (int i = 0; i < a.length - 1; ++i) {
! if (Float.floatToRawIntBits(a[i]) == 0 && Float.floatToRawIntBits(a[i + 1]) < 0) {
! fail(a[i] + " goes before " + a[i + 1] + " at " + 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]) {
! fail("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])) {
! fail("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]) {
! failCompare(i, "" + a[i], "" + b[i]);
}
}
}
! private static void checkNegativeZero(double[] a) {
! for (int i = 0; i < a.length - 1; ++i) {
! if (Double.doubleToRawLongBits(a[i]) == 0 && Double.doubleToRawLongBits(a[i + 1]) < 0) {
! fail(a[i] + " goes before " + a[i + 1] + " at " + i);
! }
! }
! }
!
! private enum SortedBuilder {
!
! STEPS {
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;
}
}
};
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 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;
}
}
},
!
! 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);
}
}
+ },
+
+ LATCH {
+ void build(int[] a, int m, Random random) {
+ int max = a.length / m;
+ max = max < 2 ? 2 : max;
+
+ for (int i = 0; i < a.length; ++i) {
+ a[i] = i % max;
+ }
+ }
};
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 enum MergingBuilder {
!
! 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;
! }
! },
!
! POINT {
! void build(int[] a, int m) {
! for (int i = 0; i < a.length; ++i) {
! a[i] = 0;
! }
! a[a.length / 2] = m;
! }
! },
!
! LINE {
! void build(int[] a, int m) {
! for (int i = 0; i < a.length; ++i) {
! a[i] = i;
! }
! reverse(a, 0, a.length - 1);
! }
! },
!
! PEARL {
! void build(int[] a, int m) {
! for (int i = 0; i < a.length; ++i) {
! a[i] = i;
! }
! reverse(a, 0, 2);
! }
! },
!
! RING {
! void build(int[] a, int m) {
! int k1 = a.length / 3;
! int k2 = a.length / 3 * 2;
! int level = a.length / 3;
!
! for (int i = 0, k = level; i < k1; ++i) {
! a[i] = k--;
! }
! for (int i = k1; i < k2; ++i) {
! a[i] = 0;
! }
! for (int i = k2, k = level; i < a.length; ++i) {
! 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 void reverse(int[] a, int lo, int hi) {
+ for (--hi; lo < hi; ) {
+ int tmp = a[lo];
+ a[lo++] = a[hi];
+ a[hi--] = tmp;
+ }
+ }
+
private static void checkWithCheckSum(Object test, Object golden) {
checkSorted(test);
checkCheckSum(test, golden);
}
! private static void fail(String message) {
! err.format("\n*** TEST FAILED *** %s.\n\n%s.\n\n", name, message);
throw new RuntimeException("Test failed - see log file for details");
}
! private static void failSort(int index, String value1, String value2) {
! fail("Array is not sorted at " + index + "-th position: " + value1 + " and " + value2);
}
! private static void failCompare(int index, String value1, String value2) {
! fail("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);
*** 1034,1111 ****
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) {
--- 1253,1320 ----
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 {
! fail("Unknown 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]) {
! failCompare(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]) {
! failCompare(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]) {
! failCompare(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]) {
! failCompare(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]) {
! failCompare(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]) {
! failCompare(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]) {
! failCompare(i, "" + a[i], "" + b[i]);
}
}
}
private static void checkSorted(Object object) {
*** 1121,1208 ****
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[]) {
--- 1330,1407 ----
checkSorted((char[]) object);
} else if (object instanceof float[]) {
checkSorted((float[]) object);
} else if (object instanceof double[]) {
checkSorted((double[]) object);
} else {
! fail("Unknown 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]) {
! failSort(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]) {
! failSort(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]) {
! failSort(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]) {
! failSort(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]) {
! failSort(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]) {
! failSort(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]) {
! failSort(i, "" + a[i], "" + a[i + 1]);
}
}
}
private static void checkCheckSum(Object test, Object golden) {
if (checkSumXor(test) != checkSumXor(golden)) {
! fail("Original and sorted arrays are not identical [xor]");
}
if (checkSumPlus(test) != checkSumPlus(golden)) {
! fail("Original and sorted arrays are not identical [plus]");
}
}
private static int checkSumXor(Object object) {
if (object instanceof int[]) {
*** 1217,1244 ****
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;
--- 1416,1432 ----
return checkSumXor((char[]) object);
} else if (object instanceof float[]) {
return checkSumXor((float[]) object);
} else if (object instanceof double[]) {
return checkSumXor((double[]) object);
} else {
! fail("Unknown type of array: " + object + " of class " +
object.getClass().getName());
return -1;
}
}
private static int checkSumXor(int[] a) {
int checkSum = 0;
for (int e : a) {
checkSum ^= e;
*** 1313,1326 ****
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;
}
}
--- 1501,1512 ----
return checkSumPlus((char[]) object);
} else if (object instanceof float[]) {
return checkSumPlus((float[]) object);
} else if (object instanceof double[]) {
return checkSumPlus((double[]) object);
} else {
! fail("Unknown type of array: " + object + " of class " +
object.getClass().getName());
return -1;
}
}
*** 1385,1403 ****
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);
--- 1571,1580 ----
*** 1409,1747 ****
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.sort((int[]) object);
} else if (object instanceof long[]) {
! Arrays.sort((long[]) object);
} else if (object instanceof short[]) {
! Arrays.sort((short[]) object);
} else if (object instanceof byte[]) {
! Arrays.sort((byte[]) object);
} else if (object instanceof char[]) {
! Arrays.sort((char[]) object);
} else if (object instanceof float[]) {
! Arrays.sort((float[]) object);
} else if (object instanceof double[]) {
! Arrays.sort((double[]) object);
! } else if (object instanceof Integer[]) {
! Arrays.sort((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.sort((int[]) object, fromIndex, toIndex);
} else if (object instanceof long[]) {
! Arrays.sort((long[]) object, fromIndex, toIndex);
} else if (object instanceof short[]) {
! Arrays.sort((short[]) object, fromIndex, toIndex);
} else if (object instanceof byte[]) {
! Arrays.sort((byte[]) object, fromIndex, toIndex);
} else if (object instanceof char[]) {
! Arrays.sort((char[]) object, fromIndex, toIndex);
} else if (object instanceof float[]) {
! Arrays.sort((float[]) object, fromIndex, toIndex);
} else if (object instanceof double[]) {
! Arrays.sort((double[]) object, fromIndex, toIndex);
! } else if (object instanceof Integer[]) {
! Arrays.sort((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) {
--- 1586,1884 ----
sortByInsertionSort((char[]) object);
} else if (object instanceof float[]) {
sortByInsertionSort((float[]) object);
} else if (object instanceof double[]) {
sortByInsertionSort((double[]) object);
} else {
! fail("Unknown 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 sort(Object object) {
if (object instanceof int[]) {
! sortingHelper.sort((int[]) object);
} else if (object instanceof long[]) {
! sortingHelper.sort((long[]) object);
} else if (object instanceof short[]) {
! sortingHelper.sort((short[]) object);
} else if (object instanceof byte[]) {
! sortingHelper.sort((byte[]) object);
} else if (object instanceof char[]) {
! sortingHelper.sort((char[]) object);
} else if (object instanceof float[]) {
! sortingHelper.sort((float[]) object);
} else if (object instanceof double[]) {
! sortingHelper.sort((double[]) object);
} else {
! fail("Unknown type of array: " + object + " of class " +
object.getClass().getName());
}
}
private static void sortSubArray(Object object, int fromIndex, int toIndex) {
if (object instanceof int[]) {
! sortingHelper.sort((int[]) object, fromIndex, toIndex);
} else if (object instanceof long[]) {
! sortingHelper.sort((long[]) object, fromIndex, toIndex);
} else if (object instanceof short[]) {
! sortingHelper.sort((short[]) object, fromIndex, toIndex);
} else if (object instanceof byte[]) {
! sortingHelper.sort((byte[]) object, fromIndex, toIndex);
} else if (object instanceof char[]) {
! sortingHelper.sort((char[]) object, fromIndex, toIndex);
} else if (object instanceof float[]) {
! sortingHelper.sort((float[]) object, fromIndex, toIndex);
} else if (object instanceof double[]) {
! sortingHelper.sort((double[]) object, fromIndex, toIndex);
} else {
! fail("Unknown type of array: " + object + " of class " +
object.getClass().getName());
}
}
! private static void checkSubArray(Object object, int fromIndex, int toIndex) {
if (object instanceof int[]) {
! checkSubArray((int[]) object, fromIndex, toIndex);
} else if (object instanceof long[]) {
! checkSubArray((long[]) object, fromIndex, toIndex);
} else if (object instanceof short[]) {
! checkSubArray((short[]) object, fromIndex, toIndex);
} else if (object instanceof byte[]) {
! checkSubArray((byte[]) object, fromIndex, toIndex);
} else if (object instanceof char[]) {
! checkSubArray((char[]) object, fromIndex, toIndex);
} else if (object instanceof float[]) {
! checkSubArray((float[]) object, fromIndex, toIndex);
} else if (object instanceof double[]) {
! checkSubArray((double[]) object, fromIndex, toIndex);
} else {
! fail("Unknown type of array: " + object + " of class " +
object.getClass().getName());
}
}
! private static void checkSubArray(int[] a, int fromIndex, int toIndex) {
! for (int i = 0; i < fromIndex; ++i) {
! if (a[i] != A380) {
! fail("Range sort changes left element on position " + i +
! ": " + a[i] + ", must be " + A380);
}
}
! for (int i = fromIndex; i < toIndex - 1; ++i) {
if (a[i] > a[i + 1]) {
! failSort(i, "" + a[i], "" + a[i + 1]);
}
}
! for (int i = toIndex; i < a.length; ++i) {
! if (a[i] != B747) {
! fail("Range sort changes right element on position " + i +
! ": " + a[i] + ", must be " + B747);
}
}
}
! private static void checkSubArray(byte[] a, int fromIndex, int toIndex) {
! for (int i = 0; i < fromIndex; ++i) {
! if (a[i] != (byte) A380) {
! fail("Range sort changes left element on position " + i +
! ": " + a[i] + ", must be " + A380);
}
}
! for (int i = fromIndex; i < toIndex - 1; ++i) {
if (a[i] > a[i + 1]) {
! failSort(i, "" + a[i], "" + a[i + 1]);
}
}
! for (int i = toIndex; i < a.length; ++i) {
! if (a[i] != (byte) B747) {
! fail("Range sort changes right element on position " + i +
! ": " + a[i] + ", must be " + B747);
}
}
}
! private static void checkSubArray(long[] a, int fromIndex, int toIndex) {
! for (int i = 0; i < fromIndex; ++i) {
! if (a[i] != (long) A380) {
! fail("Range sort changes left element on position " + i +
! ": " + a[i] + ", must be " + A380);
}
}
! for (int i = fromIndex; i < toIndex - 1; ++i) {
if (a[i] > a[i + 1]) {
! failSort(i, "" + a[i], "" + a[i + 1]);
}
}
! for (int i = toIndex; i < a.length; ++i) {
! if (a[i] != (long) B747) {
! fail("Range sort changes right element on position " + i +
! ": " + a[i] + ", must be " + B747);
}
}
}
! private static void checkSubArray(char[] a, int fromIndex, int toIndex) {
! for (int i = 0; i < fromIndex; ++i) {
! if (a[i] != (char) A380) {
! fail("Range sort changes left element on position " + i +
! ": " + a[i] + ", must be " + A380);
}
}
! for (int i = fromIndex; i < toIndex - 1; ++i) {
if (a[i] > a[i + 1]) {
! failSort(i, "" + a[i], "" + a[i + 1]);
}
}
! for (int i = toIndex; i < a.length; ++i) {
! if (a[i] != (char) B747) {
! fail("Range sort changes right element on position " + i +
! ": " + a[i] + ", must be " + B747);
}
}
}
! private static void checkSubArray(short[] a, int fromIndex, int toIndex) {
! for (int i = 0; i < fromIndex; ++i) {
! if (a[i] != (short) A380) {
! fail("Range sort changes left element on position " + i +
! ": " + a[i] + ", must be " + A380);
}
}
! for (int i = fromIndex; i < toIndex - 1; ++i) {
if (a[i] > a[i + 1]) {
! failSort(i, "" + a[i], "" + a[i + 1]);
}
}
! for (int i = toIndex; i < a.length; ++i) {
! if (a[i] != (short) B747) {
! fail("Range sort changes right element on position " + i +
! ": " + a[i] + ", must be " + B747);
}
}
}
! private static void checkSubArray(float[] a, int fromIndex, int toIndex) {
! for (int i = 0; i < fromIndex; ++i) {
! if (a[i] != (float) A380) {
! fail("Range sort changes left element on position " + i +
! ": " + a[i] + ", must be " + A380);
}
}
! for (int i = fromIndex; i < toIndex - 1; ++i) {
if (a[i] > a[i + 1]) {
! failSort(i, "" + a[i], "" + a[i + 1]);
}
}
! for (int i = toIndex; i < a.length; ++i) {
! if (a[i] != (float) B747) {
! fail("Range sort changes right element on position " + i +
! ": " + a[i] + ", must be " + B747);
}
}
}
! private static void checkSubArray(double[] a, int fromIndex, int toIndex) {
! for (int i = 0; i < fromIndex; ++i) {
! if (a[i] != (double) A380) {
! fail("Range sort changes left element on position " + i +
! ": " + a[i] + ", must be " + A380);
}
}
! for (int i = fromIndex; i < toIndex - 1; ++i) {
if (a[i] > a[i + 1]) {
! failSort(i, "" + a[i], "" + a[i + 1]);
}
}
! for (int i = toIndex; i < a.length; ++i) {
! if (a[i] != (double) B747) {
! fail("Range sort changes right element on position " + i +
! ": " + a[i] + ", must be " + B747);
}
}
}
private static void checkRange(Object object, int m) {
*** 1757,2044 ****
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.sort(a, m + 1, m);
-
- failed("Sort does not throw IllegalArgumentException " +
- " as expected: fromIndex = " + (m + 1) +
- " toIndex = " + m);
- }
- catch (IllegalArgumentException iae) {
- try {
- Arrays.sort(a, -m, a.length);
-
- failed("Sort does not throw ArrayIndexOutOfBoundsException " +
- " as expected: fromIndex = " + (-m));
- }
- catch (ArrayIndexOutOfBoundsException aoe) {
- try {
- Arrays.sort(a, 0, a.length + m);
-
- failed("Sort does not throw ArrayIndexOutOfBoundsException " +
- " as expected: toIndex = " + (a.length + m));
- }
- catch (ArrayIndexOutOfBoundsException aie) {
- return;
- }
- }
- }
- }
-
private static void checkRange(int[] a, int m) {
try {
! Arrays.sort(a, m + 1, m);
! failed("Sort does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) +
! " toIndex = " + m);
! }
! catch (IllegalArgumentException iae) {
try {
! Arrays.sort(a, -m, a.length);
! failed("Sort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! }
! catch (ArrayIndexOutOfBoundsException aoe) {
try {
! Arrays.sort(a, 0, a.length + m);
! failed("Sort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
! }
! catch (ArrayIndexOutOfBoundsException aie) {
! return;
}
}
}
}
private static void checkRange(long[] a, int m) {
try {
! Arrays.sort(a, m + 1, m);
! failed("Sort does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) +
! " toIndex = " + m);
! }
! catch (IllegalArgumentException iae) {
try {
! Arrays.sort(a, -m, a.length);
! failed("Sort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! }
! catch (ArrayIndexOutOfBoundsException aoe) {
try {
! Arrays.sort(a, 0, a.length + m);
! failed("Sort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
! }
! catch (ArrayIndexOutOfBoundsException aie) {
! return;
}
}
}
}
private static void checkRange(byte[] a, int m) {
try {
! Arrays.sort(a, m + 1, m);
! failed("Sort does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) +
! " toIndex = " + m);
! }
! catch (IllegalArgumentException iae) {
try {
! Arrays.sort(a, -m, a.length);
! failed("Sort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! }
! catch (ArrayIndexOutOfBoundsException aoe) {
try {
! Arrays.sort(a, 0, a.length + m);
! failed("Sort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
! }
! catch (ArrayIndexOutOfBoundsException aie) {
! return;
}
}
}
}
private static void checkRange(short[] a, int m) {
try {
! Arrays.sort(a, m + 1, m);
! failed("Sort does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) +
! " toIndex = " + m);
! }
! catch (IllegalArgumentException iae) {
try {
! Arrays.sort(a, -m, a.length);
! failed("Sort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! }
! catch (ArrayIndexOutOfBoundsException aoe) {
try {
! Arrays.sort(a, 0, a.length + m);
! failed("Sort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
! }
! catch (ArrayIndexOutOfBoundsException aie) {
! return;
}
}
}
}
private static void checkRange(char[] a, int m) {
try {
! Arrays.sort(a, m + 1, m);
! failed("Sort does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) +
! " toIndex = " + m);
! }
! catch (IllegalArgumentException iae) {
try {
! Arrays.sort(a, -m, a.length);
! failed("Sort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! }
! catch (ArrayIndexOutOfBoundsException aoe) {
try {
! Arrays.sort(a, 0, a.length + m);
! failed("Sort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
! }
! catch (ArrayIndexOutOfBoundsException aie) {
! return;
}
}
}
}
private static void checkRange(float[] a, int m) {
try {
! Arrays.sort(a, m + 1, m);
! failed("Sort does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) +
! " toIndex = " + m);
! }
! catch (IllegalArgumentException iae) {
try {
! Arrays.sort(a, -m, a.length);
! failed("Sort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! }
! catch (ArrayIndexOutOfBoundsException aoe) {
try {
! Arrays.sort(a, 0, a.length + m);
! failed("Sort does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
! }
! catch (ArrayIndexOutOfBoundsException aie) {
! return;
}
}
}
}
private static void checkRange(double[] a, int m) {
try {
! Arrays.sort(a, m + 1, m);
! failed("Sort does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) +
! " toIndex = " + m);
! }
! catch (IllegalArgumentException iae) {
try {
! Arrays.sort(a, -m, a.length);
! failed("Sort does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! }
! catch (ArrayIndexOutOfBoundsException aoe) {
try {
! Arrays.sort(a, 0, a.length + m);
! failed("Sort 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;
}
--- 1894,2090 ----
checkRange((char[]) object, m);
} else if (object instanceof float[]) {
checkRange((float[]) object, m);
} else if (object instanceof double[]) {
checkRange((double[]) object, m);
} else {
! fail("Unknown type of array: " + object + " of class " +
object.getClass().getName());
}
}
private static void checkRange(int[] a, int m) {
try {
! sortingHelper.sort(a, m + 1, m);
! fail(sortingHelper + "() does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
! } catch (IllegalArgumentException iae) {
try {
! sortingHelper.sort(a, -m, a.length);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! } catch (ArrayIndexOutOfBoundsException aoe) {
try {
! sortingHelper.sort(a, 0, a.length + m);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
! } catch (ArrayIndexOutOfBoundsException expected) {
}
}
}
}
private static void checkRange(long[] a, int m) {
try {
! sortingHelper.sort(a, m + 1, m);
! fail(sortingHelper + "() does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
! } catch (IllegalArgumentException iae) {
try {
! sortingHelper.sort(a, -m, a.length);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! } catch (ArrayIndexOutOfBoundsException aoe) {
try {
! sortingHelper.sort(a, 0, a.length + m);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
! } catch (ArrayIndexOutOfBoundsException expected) {
}
}
}
}
private static void checkRange(byte[] a, int m) {
try {
! sortingHelper.sort(a, m + 1, m);
! fail(sortingHelper + "() does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
! } catch (IllegalArgumentException iae) {
try {
! sortingHelper.sort(a, -m, a.length);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! } catch (ArrayIndexOutOfBoundsException aoe) {
try {
! sortingHelper.sort(a, 0, a.length + m);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
! } catch (ArrayIndexOutOfBoundsException expected) {
}
}
}
}
private static void checkRange(short[] a, int m) {
try {
! sortingHelper.sort(a, m + 1, m);
! fail(sortingHelper + "() does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
! } catch (IllegalArgumentException iae) {
try {
! sortingHelper.sort(a, -m, a.length);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! } catch (ArrayIndexOutOfBoundsException aoe) {
try {
! sortingHelper.sort(a, 0, a.length + m);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
! } catch (ArrayIndexOutOfBoundsException expected) {
}
}
}
}
private static void checkRange(char[] a, int m) {
try {
! sortingHelper.sort(a, m + 1, m);
! fail(sortingHelper + "() does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
! } catch (IllegalArgumentException iae) {
try {
! sortingHelper.sort(a, -m, a.length);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! } catch (ArrayIndexOutOfBoundsException aoe) {
try {
! sortingHelper.sort(a, 0, a.length + m);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
! } catch (ArrayIndexOutOfBoundsException expected) {
}
}
}
}
private static void checkRange(float[] a, int m) {
try {
! sortingHelper.sort(a, m + 1, m);
! fail(sortingHelper + "() does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
! } catch (IllegalArgumentException iae) {
try {
! sortingHelper.sort(a, -m, a.length);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! } catch (ArrayIndexOutOfBoundsException aoe) {
try {
! sortingHelper.sort(a, 0, a.length + m);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
! } catch (ArrayIndexOutOfBoundsException expected) {
}
}
}
}
private static void checkRange(double[] a, int m) {
try {
! sortingHelper.sort(a, m + 1, m);
! fail(sortingHelper + "() does not throw IllegalArgumentException " +
! " as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
! } catch (IllegalArgumentException iae) {
try {
! sortingHelper.sort(a, -m, a.length);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: fromIndex = " + (-m));
! } catch (ArrayIndexOutOfBoundsException aoe) {
try {
! sortingHelper.sort(a, 0, a.length + m);
! fail(sortingHelper + "() does not throw ArrayIndexOutOfBoundsException " +
" as expected: toIndex = " + (a.length + m));
! } catch (ArrayIndexOutOfBoundsException expected) {
}
}
}
}
! private static String getTestName() {
! return "[" + sortingHelper + "] '" + name + "' ";
}
! private static class TestRandom extends Random {
! private TestRandom(long seed) {
super(seed);
! this.seed = Long.toHexString(seed).toUpperCase();
}
! String getSeed() {
! return seed;
}
! private String seed;
}
}
< prev index next >