jdk-sandbox: comparison test/jdk/java/util/Arrays/Sorting.java

equal deleted inserted replaced

-:d6d8fdc95ed2
+:8910b995a2ee
 /*
-* Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
+* 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.
 * questions.
 */
 /*
 * @test
-* @bug 6880672 6896573 6899694 6976036 7013585 7018258
+* @compile/module=java.base java/util/SortingHelper.java
-* @summary Exercise Arrays.sort
+* @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.util.Arrays;
+import java.io.PrintStream;
+import java.util.Comparator;
 import java.util.Random;
-import java.io.PrintStream;
+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, 100, 1000, 10000, 100000, 1000000 };
+1, 3, 8, 21, 55, 100, 1_000, 10_000, 100_000 };
 // Array lengths used in a short run
 private static final int[] SHORT_RUN_LENGTHS = {
-1, 2, 3, 21, 55, 1000, 10000 };
+1, 8, 55, 100, 10_000 };
 // Random initial values used in a long run (default)
-private static final long[] LONG_RUN_RANDOMS = { 666, 0xC0FFEE, 999 };
+private static final TestRandom[] LONG_RUN_RANDOMS = {
+TestRandom.BABA, TestRandom.DEDA, TestRandom.C0FFEE };
 // Random initial values used in a short run
-private static final long[] SHORT_RUN_RANDOMS = { 666 };
+private static final TestRandom[] SHORT_RUN_RANDOMS = {
+TestRandom.C0FFEE };
+// Constants used in subarray sorting
+private static final int A380 = 0xA380;
+private static final int B747 = 0xB747;
+private final SortingHelper sortingHelper;
+private final TestRandom[] randoms;
+private final int[] lengths;
+private Object[] gold;
+private Object[] test;
 public static void main(String[] args) {
+long start = System.currentTimeMillis();
 boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
-long start = System.currentTimeMillis();
+int[] lengths = shortRun ? SHORT_RUN_LENGTHS : LONG_RUN_LENGTHS;
-if (shortRun) {
+TestRandom[] randoms = shortRun ? SHORT_RUN_RANDOMS : LONG_RUN_RANDOMS;
-testAndCheck(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
-} else {
+new Sorting(SortingHelper.DUAL_PIVOT_QUICKSORT, randoms, lengths).testCore();
-testAndCheck(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
+new Sorting(SortingHelper.PARALLEL_SORT, randoms, lengths).testCore();
-}
+new Sorting(SortingHelper.HEAP_SORT, randoms, lengths).testBasic();
+new Sorting(SortingHelper.ARRAYS_SORT, randoms, lengths).testAll();
+new Sorting(SortingHelper.ARRAYS_PARALLEL_SORT, randoms, lengths).testAll();
 long end = System.currentTimeMillis();
+out.format("PASSED in %d sec.\n", (end - start) / 1000);
-out.format("PASSED in %d sec.\n", Math.round((end - start) / 1E3));
+}
-}
+private Sorting(SortingHelper sortingHelper, TestRandom[] randoms, int[] lengths) {
-private static void testAndCheck(int[] lengths, long[] randoms) {
+this.sortingHelper = sortingHelper;
+this.randoms = randoms;
+this.lengths = lengths;
+}
+private void testBasic() {
+testEmptyArray();
+for (int length : lengths) {
+createData(length);
+testBasic(length);
+}
+}
+private void testBasic(int length) {
+for (TestRandom random : randoms) {
+testWithInsertionSort(length, random);
+testWithCheckSum(length, random);
+testWithScrambling(length, random);
+}
+}
+private void testCore() {
+for (int length : lengths) {
+createData(length);
+testCore(length);
+}
+}
+private void testCore(int length) {
+testBasic(length);
+for (TestRandom random : randoms) {
+testMergingSort(length, random);
+testSubArray(length, random);
+testNegativeZero(length, random);
+testFloatingPointSorting(length, random);
+}
+}
+private void testAll() {
+for (int length : lengths) {
+createData(length);
+testAll(length);
+}
+}
+private void testAll(int length) {
+testCore(length);
+for (TestRandom random : randoms) {
+testRange(length, random);
+testStability(length, random);
+}
+}
+private void testEmptyArray() {
 testEmptyAndNullIntArray();
 testEmptyAndNullLongArray();
+testEmptyAndNullByteArray();
+testEmptyAndNullCharArray();
 testEmptyAndNullShortArray();
-testEmptyAndNullCharArray();
-testEmptyAndNullByteArray();
 testEmptyAndNullFloatArray();
 testEmptyAndNullDoubleArray();
+}
-for (int length : lengths) {
-testMergeSort(length);
+private void testStability(int length, TestRandom random) {
-testAndCheckRange(length);
+printTestName("Test stability", random, length);
-testAndCheckSubArray(length);
-}
+Pair[] a = build(length, random);
-for (long seed : randoms) {
+sortingHelper.sort(a);
-for (int length : lengths) {
+checkSorted(a);
-testAndCheckWithInsertionSort(length, new MyRandom(seed));
+checkStable(a);
-testAndCheckWithCheckSum(length, new MyRandom(seed));
-testAndCheckWithScrambling(length, new MyRandom(seed));
+a = build(length, random);
-testAndCheckFloat(length, new MyRandom(seed));
+sortingHelper.sort(a, pairComparator);
-testAndCheckDouble(length, new MyRandom(seed));
+checkSorted(a);
-testStable(length, new MyRandom(seed));
+checkStable(a);
-}
-}
+out.println();
 }
-private static void testEmptyAndNullIntArray() {
+private void testEmptyAndNullIntArray() {
-ourDescription = "Check empty and null array";
+sortingHelper.sort(new int[] {});
-Arrays.sort(new int[] {});
+sortingHelper.sort(new int[] {}, 0, 0);
-Arrays.sort(new int[] {}, 0, 0);
 try {
-Arrays.sort((int[]) null);
+sortingHelper.sort(null);
 } catch (NullPointerException expected) {
 try {
-Arrays.sort((int[]) null, 0, 0);
+sortingHelper.sort(null, 0, 0);
 } catch (NullPointerException expected2) {
 return;
 }
-failed("Arrays.sort(int[],fromIndex,toIndex) shouldn't " +
+fail(sortingHelper + "(int[],fromIndex,toIndex) shouldn't " +
 "catch null array");
 }
-failed("Arrays.sort(int[]) shouldn't catch null array");
+fail(sortingHelper + "(int[]) shouldn't catch null array");
 }
-private static void testEmptyAndNullLongArray() {
+private void testEmptyAndNullLongArray() {
-ourDescription = "Check empty and null array";
+sortingHelper.sort(new long[] {});
-Arrays.sort(new long[] {});
+sortingHelper.sort(new long[] {}, 0, 0);
-Arrays.sort(new long[] {}, 0, 0);
 try {
-Arrays.sort((long[]) null);
+sortingHelper.sort(null);
 } catch (NullPointerException expected) {
 try {
-Arrays.sort((long[]) null, 0, 0);
+sortingHelper.sort(null, 0, 0);
 } catch (NullPointerException expected2) {
 return;
 }
-failed("Arrays.sort(long[],fromIndex,toIndex) shouldn't " +
+fail(sortingHelper + "(long[],fromIndex,toIndex) shouldn't " +
 "catch null array");
 }
-failed("Arrays.sort(long[]) shouldn't catch null array");
+fail(sortingHelper + "(long[]) shouldn't catch null array");
 }
-private static void testEmptyAndNullShortArray() {
+private void testEmptyAndNullByteArray() {
-ourDescription = "Check empty and null array";
+sortingHelper.sort(new byte[] {});
-Arrays.sort(new short[] {});
+sortingHelper.sort(new byte[] {}, 0, 0);
-Arrays.sort(new short[] {}, 0, 0);
 try {
-Arrays.sort((short[]) null);
+sortingHelper.sort(null);
 } catch (NullPointerException expected) {
 try {
-Arrays.sort((short[]) null, 0, 0);
+sortingHelper.sort(null, 0, 0);
 } catch (NullPointerException expected2) {
 return;
 }
-failed("Arrays.sort(short[],fromIndex,toIndex) shouldn't " +
+fail(sortingHelper + "(byte[],fromIndex,toIndex) shouldn't " +
 "catch null array");
 }
-failed("Arrays.sort(short[]) shouldn't catch null array");
+fail(sortingHelper + "(byte[]) shouldn't catch null array");
 }
-private static void testEmptyAndNullCharArray() {
+private void testEmptyAndNullCharArray() {
-ourDescription = "Check empty and null array";
+sortingHelper.sort(new char[] {});
-Arrays.sort(new char[] {});
+sortingHelper.sort(new char[] {}, 0, 0);
-Arrays.sort(new char[] {}, 0, 0);
 try {
-Arrays.sort((char[]) null);
+sortingHelper.sort(null);
 } catch (NullPointerException expected) {
 try {
-Arrays.sort((char[]) null, 0, 0);
+sortingHelper.sort(null, 0, 0);
 } catch (NullPointerException expected2) {
 return;
 }
-failed("Arrays.sort(char[],fromIndex,toIndex) shouldn't " +
+fail(sortingHelper + "(char[],fromIndex,toIndex) shouldn't " +
 "catch null array");
 }
-failed("Arrays.sort(char[]) shouldn't catch null array");
+fail(sortingHelper + "(char[]) shouldn't catch null array");
 }
-private static void testEmptyAndNullByteArray() {
+private void testEmptyAndNullShortArray() {
-ourDescription = "Check empty and null array";
+sortingHelper.sort(new short[] {});
-Arrays.sort(new byte[] {});
+sortingHelper.sort(new short[] {}, 0, 0);
-Arrays.sort(new byte[] {}, 0, 0);
 try {
-Arrays.sort((byte[]) null);
+sortingHelper.sort(null);
 } catch (NullPointerException expected) {
 try {
-Arrays.sort((byte[]) null, 0, 0);
+sortingHelper.sort(null, 0, 0);
 } catch (NullPointerException expected2) {
 return;
 }
-failed("Arrays.sort(byte[],fromIndex,toIndex) shouldn't " +
+fail(sortingHelper + "(short[],fromIndex,toIndex) shouldn't " +
 "catch null array");
 }
-failed("Arrays.sort(byte[]) shouldn't catch null array");
+fail(sortingHelper + "(short[]) shouldn't catch null array");
 }
-private static void testEmptyAndNullFloatArray() {
+private void testEmptyAndNullFloatArray() {
-ourDescription = "Check empty and null array";
+sortingHelper.sort(new float[] {});
-Arrays.sort(new float[] {});
+sortingHelper.sort(new float[] {}, 0, 0);
-Arrays.sort(new float[] {}, 0, 0);
 try {
-Arrays.sort((float[]) null);
+sortingHelper.sort(null);
 } catch (NullPointerException expected) {
 try {
-Arrays.sort((float[]) null, 0, 0);
+sortingHelper.sort(null, 0, 0);
 } catch (NullPointerException expected2) {
 return;
 }
-failed("Arrays.sort(float[],fromIndex,toIndex) shouldn't " +
+fail(sortingHelper + "(float[],fromIndex,toIndex) shouldn't " +
 "catch null array");
 }
-failed("Arrays.sort(float[]) shouldn't catch null array");
+fail(sortingHelper + "(float[]) shouldn't catch null array");
 }
-private static void testEmptyAndNullDoubleArray() {
+private void testEmptyAndNullDoubleArray() {
-ourDescription = "Check empty and null array";
+sortingHelper.sort(new double[] {});
-Arrays.sort(new double[] {});
+sortingHelper.sort(new double[] {}, 0, 0);
-Arrays.sort(new double[] {}, 0, 0);
 try {
-Arrays.sort((double[]) null);
+sortingHelper.sort(null);
 } catch (NullPointerException expected) {
 try {
-Arrays.sort((double[]) null, 0, 0);
+sortingHelper.sort(null, 0, 0);
 } catch (NullPointerException expected2) {
 return;
 }
-failed("Arrays.sort(double[],fromIndex,toIndex) shouldn't " +
+fail(sortingHelper + "(double[],fromIndex,toIndex) shouldn't " +
 "catch null array");
 }
-failed("Arrays.sort(double[]) shouldn't catch null array");
+fail(sortingHelper + "(double[]) shouldn't catch null array");
 }
-private static void testAndCheckSubArray(int length) {
+private void testSubArray(int length, TestRandom random) {
-ourDescription = "Check sorting of subarray";
+if (length < 4) {
-int[] golden = new int[length];
+return;
-boolean newLine = false;
+}
+for (int m = 1; m < length / 2; m <<= 1) {
-for (int m = 1; m < length / 2; m *= 2) {
-newLine = true;
 int fromIndex = m;
 int toIndex = length - m;
-prepareSubArray(golden, fromIndex, toIndex, m);
+prepareSubArray((int[]) gold[0], fromIndex, toIndex);
-int[] test = golden.clone();
+convertData(length);
-for (TypeConverter converter : TypeConverter.values()) {
+for (int i = 0; i < test.length; i++) {
-out.println("Test 'subarray': " + converter +
+printTestName("Test subarray", random, length,
-" length = " + length + ", m = " + m);
+", m = " + m + ", " + getType(i));
-Object convertedGolden = converter.convert(golden);
+sortingHelper.sort(test[i], fromIndex, toIndex);
-Object convertedTest = converter.convert(test);
+checkSubArray(test[i], fromIndex, toIndex);
-sortSubArray(convertedTest, fromIndex, toIndex);
+}
-checkSubArray(convertedTest, fromIndex, toIndex, m);
+}
-}
+out.println();
 }
-if (newLine) {
-out.println();
+private void testRange(int length, TestRandom random) {
-}
+if (length < 2) {
-}
+return;
+}
-private static void testAndCheckRange(int length) {
+for (int m = 1; m < length; m <<= 1) {
-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;
+((int[]) gold[0]) [i - 1] = i % m + m % i;
 }
-for (TypeConverter converter : TypeConverter.values()) {
+convertData(length);
-out.println("Test 'range': " + converter +
-", length = " + length + ", m = " + m);
+for (int i = 0; i < test.length; i++) {
-Object convertedGolden = converter.convert(golden);
+printTestName("Test range check", random, length,
-checkRange(convertedGolden, m);
+", m = " + m + ", " + getType(i));
+checkRange(test[i], m);
 }
 }
 out.println();
 }
-private static void testStable(int length, MyRandom random) {
+private void checkSorted(Pair[] a) {
-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());
+fail("Array is not sorted at " + i + "-th position: " +
-}
+a[i].getKey() + " and " + a[i + 1].getKey());
 }
 }
+}
-private static void checkStable(Pair[] a) {
+private 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 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 " +
+fail("Keys are different " + key1 + ", " + key2 + ", " +
-key1 + ", " + key2 + ", " + key3 + ", " + key4);
+key3 + ", " + key4 + " at position " + i);
 }
 if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
-failed("Sorting is not stable at position " + i +
+fail("Sorting is not stable at position " + i +
-". Second values have been changed: " +  value1 + ", " +
+". Second values have been changed: " + value1 + ", " +
 value2 + ", " + value3 + ", " + value4);
 }
 }
 }
-private static Pair[] build(int length, Random random) {
+private 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, 4);
 }
 return a;
 }
-private static final class Pair implements Comparable<Pair> {
+private void testWithInsertionSort(int length, TestRandom random) {
-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";
+for (int m = 1; m <= length; m <<= 1) {
-int[] golden = new int[length];
-for (int m = 1; m < 2 * length; m *= 2) {
 for (UnsortedBuilder builder : UnsortedBuilder.values()) {
-builder.build(golden, m, random);
+builder.build((int[]) gold[0], m, random);
-int[] test = golden.clone();
+convertData(length);
-for (TypeConverter converter : TypeConverter.values()) {
+for (int i = 0; i < test.length; i++) {
-out.println("Test 'insertion sort': " + converter +
+printTestName("Test with insertion sort", random, length,
-" " + builder + "random = " + random.getSeed() +
+", m = " + m + ", " + getType(i) + " " + builder);
-", length = " + length + ", m = " + m);
+sortingHelper.sort(test[i]);
-Object convertedGolden = converter.convert(golden);
+sortByInsertionSort(gold[i]);
-Object convertedTest1 = converter.convert(test);
+compare(test[i], gold[i]);
-Object convertedTest2 = converter.convert(test);
-sort(convertedTest1);
-sortByInsertionSort(convertedTest2);
-compare(convertedTest1, convertedTest2);
 }
 }
 }
 out.println();
 }
-private static void testMergeSort(int length) {
+private void testMergingSort(int length, TestRandom random) {
-if (length < 1000) {
+if (length < (4 << 10)) { // DualPivotQuicksort.MIN_TRY_MERGE_SIZE
 return;
 }
-ourDescription = "Check merge sorting";
+final int PERIOD = 50;
-int[] golden = new int[length];
-int period = 67; // java.util.DualPivotQuicksort.MAX_RUN_COUNT
+for (int m = PERIOD - 2; m <= PERIOD + 2; m++) {
+for (MergingBuilder builder : MergingBuilder.values()) {
-for (int m = period - 2; m <= period + 2; m++) {
+builder.build((int[]) gold[0], m);
-for (MergeBuilder builder : MergeBuilder.values()) {
+convertData(length);
-builder.build(golden, m);
-int[] test = golden.clone();
+for (int i = 0; i < test.length; i++) {
+printTestName("Test merging sort", random, length,
-for (TypeConverter converter : TypeConverter.values()) {
+", m = " + m + ", " +  getType(i) + " " + builder);
-out.println("Test 'merge sort': " + converter + " " +
+sortingHelper.sort(test[i]);
-builder + "length = " + length + ", m = " + m);
+checkSorted(test[i]);
-Object convertedGolden = converter.convert(golden);
-sort(convertedGolden);
-checkSorted(convertedGolden);
 }
 }
 }
 out.println();
 }
-private static void testAndCheckWithCheckSum(int length, MyRandom random) {
+private void testWithCheckSum(int length, TestRandom random) {
-ourDescription = "Check sorting with check sum";
+for (int m = 1; m <= length; m <<= 1) {
-int[] golden = new int[length];
-for (int m = 1; m < 2 * length; m *= 2) {
 for (UnsortedBuilder builder : UnsortedBuilder.values()) {
-builder.build(golden, m, random);
+builder.build((int[]) gold[0], m, random);
-int[] test = golden.clone();
+convertData(length);
-for (TypeConverter converter : TypeConverter.values()) {
+for (int i = 0; i < test.length; i++) {
-out.println("Test 'check sum': " + converter +
+printTestName("Test with check sum", random, length,
-" " + builder + "random = " + random.getSeed() +
+", m = " + m + ", " + getType(i) + " " + builder);
-", length = " + length + ", m = " + m);
+sortingHelper.sort(test[i]);
-Object convertedGolden = converter.convert(golden);
+checkWithCheckSum(test[i], gold[i]);
-Object convertedTest = converter.convert(test);
-sort(convertedTest);
-checkWithCheckSum(convertedTest, convertedGolden);
 }
 }
 }
 out.println();
 }
-private static void testAndCheckWithScrambling(int length, MyRandom random) {
+private void testWithScrambling(int length, TestRandom random) {
-ourDescription = "Check sorting with scrambling";
+for (int m = 1; m <= length; m <<= 1) {
-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);
+builder.build((int[]) gold[0], m);
-int[] test = golden.clone();
+convertData(length);
-scramble(test, random);
+for (int i = 0; i < test.length; i++) {
-for (TypeConverter converter : TypeConverter.values()) {
+printTestName("Test with scrambling", random, length,
-out.println("Test 'scrambling': " + converter +
+", m = " + m + ", " + getType(i) + " " + builder);
-" " + builder + "random = " + random.getSeed() +
+scramble(test[i], random);
-", length = " + length + ", m = " + m);
+sortingHelper.sort(test[i]);
-Object convertedGolden = converter.convert(golden);
+compare(test[i], gold[i]);
-Object convertedTest = converter.convert(test);
-sort(convertedTest);
-compare(convertedTest, convertedGolden);
 }
 }
 }
 out.println();
 }
-private static void testAndCheckFloat(int length, MyRandom random) {
+private void testNegativeZero(int length, TestRandom random) {
-ourDescription = "Check float sorting";
+for (int i = 5; i < test.length; i++) {
-float[] golden = new float[length];
+printTestName("Test negative zero -0.0", random, length, " " + getType(i));
-final int MAX = 10;
-boolean newLine = false;
+NegativeZeroBuilder builder = NegativeZeroBuilder.values() [i - 5];
+builder.build(test[i], random);
-for (int a = 0; a <= MAX; a++) {
-for (int g = 0; g <= MAX; g++) {
+sortingHelper.sort(test[i]);
-for (int z = 0; z <= MAX; z++) {
+checkNegativeZero(test[i]);
-for (int n = 0; n <= MAX; n++) {
+}
-for (int p = 0; p <= MAX; p++) {
+out.println();
-if (a + g + z + n + p > length) {
+}
+private void testFloatingPointSorting(int length, TestRandom random) {
+if (length < 2) {
+return;
+}
+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;
 }
-if (a + g + z + n + p < length) {
+for (int i = 5; i < test.length; i++) {
-continue;
+printTestName("Test float-pointing sorting", random, length,
+", a = " + a + ", g = " + g + ", z = " + z +
+", n = " + n + ", p = " + p + ", " + getType(i));
+FloatingPointBuilder builder = FloatingPointBuilder.values()[i - 5];
+builder.build(gold[i], a, g, z, n, p, random);
+copy(test[i], gold[i]);
+scramble(test[i], random);
+sortingHelper.sort(test[i]);
+compare(test[i], gold[i], a, n, g);
 }
-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();
+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;
-private static void testAndCheckDouble(int length, MyRandom random) {
-ourDescription = "Check double sorting";
+for (int i = 5; i < test.length; i++) {
-double[] golden = new double[length];
+printTestName("Test float-pointing sorting", random, length,
-final int MAX = 10;
+", a = " + a + ", g = " + g + ", z = " + z +
-boolean newLine = false;
+", n = " + n + ", p = " + p + ", " + getType(i));
+FloatingPointBuilder builder = FloatingPointBuilder.values() [i - 5];
-for (int a = 0; a <= MAX; a++) {
+builder.build(gold[i], a, g, z, n, p, random);
-for (int g = 0; g <= MAX; g++) {
+copy(test[i], gold[i]);
-for (int z = 0; z <= MAX; z++) {
+scramble(test[i], random);
-for (int n = 0; n <= MAX; n++) {
+sortingHelper.sort(test[i]);
-for (int p = 0; p <= MAX; p++) {
+compare(test[i], gold[i], a, n, g);
-if (a + g + z + n + p > length) {
+}
-continue;
+}
-}
+out.println();
-if (a + g + z + n + p < length) {
+}
-continue;
-}
+private void prepareSubArray(int[] a, int fromIndex, int toIndex) {
-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;
+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] = 0xBABA;
+a[i] = B747;
 }
 }
-private static void scramble(int[] a, Random random) {
+private void scramble(Object a, Random random) {
+if (a instanceof int[]) {
+scramble((int[]) a, random);
+} else if (a instanceof long[]) {
+scramble((long[]) a, random);
+} else if (a instanceof byte[]) {
+scramble((byte[]) a, random);
+} else if (a instanceof char[]) {
+scramble((char[]) a, random);
+} else if (a instanceof short[]) {
+scramble((short[]) a, random);
+} else if (a instanceof float[]) {
+scramble((float[]) a, random);
+} else if (a instanceof double[]) {
+scramble((double[]) a, random);
+} else {
+fail("Unknown type of array: " + a.getClass().getName());
+}
+}
+private 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) {
+private void scramble(long[] 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) {
+private void scramble(byte[] 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) {
+private void scramble(char[] a, Random random) {
-int t = a[i];
+for (int i = 0; i < a.length * 7; i++) {
-a[i] = a[j];
+swap(a, random.nextInt(a.length), random.nextInt(a.length));
-a[j] = t;
+}
 }
-private static void swap(float[] a, int i, int j) {
+private void scramble(short[] a, Random random) {
-float t = a[i];
+for (int i = 0; i < a.length * 7; i++) {
-a[i] = a[j];
+swap(a, random.nextInt(a.length), random.nextInt(a.length));
-a[j] = t;
+}
 }
-private static void swap(double[] a, int i, int j) {
+private void scramble(float[] a, Random random) {
-double t = a[i];
+for (int i = 0; i < a.length * 7; i++) {
-a[i] = a[j];
+swap(a, random.nextInt(a.length), random.nextInt(a.length));
-a[j] = t;
+}
 }
-private static enum TypeConverter {
+private void scramble(double[] a, Random random) {
-INT {
+for (int i = 0; i < a.length * 7; i++) {
-Object convert(int[] a) {
+swap(a, random.nextInt(a.length), random.nextInt(a.length));
-return a.clone();
+}
 }
-},
-LONG {
+private void swap(int[] a, int i, int j) {
-Object convert(int[] a) {
+int t = a[i]; a[i] = a[j]; a[j] = t;
-long[] b = new long[a.length];
+}
-for (int i = 0; i < a.length; i++) {
+private void swap(long[] a, int i, int j) {
-b[i] = (long) a[i];
+long t = a[i]; a[i] = a[j]; a[j] = t;
 }
-return b;
-}
+private void swap(byte[] a, int i, int j) {
-},
+byte t = a[i]; a[i] = a[j]; a[j] = t;
-BYTE {
+}
-Object convert(int[] a) {
-byte[] b = new byte[a.length];
+private void swap(char[] a, int i, int j) {
+char t = a[i]; a[i] = a[j]; a[j] = t;
-for (int i = 0; i < a.length; i++) {
+}
-b[i] = (byte) a[i];
-}
+private void swap(short[] a, int i, int j) {
-return b;
+short t = a[i]; a[i] = a[j]; a[j] = t;
 }
-},
-SHORT {
+private void swap(float[] a, int i, int j) {
-Object convert(int[] a) {
+float t = a[i]; a[i] = a[j]; a[j] = t;
-short[] b = new short[a.length];
+}
-for (int i = 0; i < a.length; i++) {
+private void swap(double[] a, int i, int j) {
-b[i] = (short) a[i];
+double t = a[i]; a[i] = a[j]; a[j] = t;
 }
-return b;
-}
+private void checkWithCheckSum(Object test, Object gold) {
-},
+checkSorted(test);
-CHAR {
+checkCheckSum(test, gold);
-Object convert(int[] a) {
+}
-char[] b = new char[a.length];
+private void fail(String message) {
-for (int i = 0; i < a.length; i++) {
+err.format("\n*** TEST FAILED ***\n\n%s\n\n", message);
-b[i] = (char) a[i];
+throw new RuntimeException("Test failed");
 }
-return b;
-}
+private void checkNegativeZero(Object a) {
-},
+if (a instanceof float[]) {
-FLOAT {
+checkNegativeZero((float[]) a);
-Object convert(int[] a) {
+} else if (a instanceof double[]) {
-float[] b = new float[a.length];
+checkNegativeZero((double[]) a);
+} else {
-for (int i = 0; i < a.length; i++) {
+fail("Unknown type of array: " + a.getClass().getName());
-b[i] = (float) a[i];
+}
 }
-return b;
-}
+private void checkNegativeZero(float[] a) {
-},
+for (int i = 0; i < a.length - 1; i++) {
-DOUBLE {
+if (Float.floatToRawIntBits(a[i]) == 0 && Float.floatToRawIntBits(a[i + 1]) < 0) {
-Object convert(int[] a) {
+fail(a[i] + " before " + a[i + 1] + " at position " + i);
-double[] b = new double[a.length];
+}
+}
-for (int i = 0; i < a.length; i++) {
+}
-b[i] = (double) a[i];
-}
+private void checkNegativeZero(double[] a) {
-return b;
+for (int i = 0; i < a.length - 1; i++) {
-}
+if (Double.doubleToRawLongBits(a[i]) == 0 && Double.doubleToRawLongBits(a[i + 1]) < 0) {
-},
+fail(a[i] + " before " + a[i + 1] + " at position " + i);
-INTEGER {
+}
-Object convert(int[] a) {
+}
-Integer[] b = new Integer[a.length];
+}
-for (int i = 0; i < a.length; i++) {
+private void compare(Object a, Object b, int numNaN, int numNeg, int numNegZero) {
-b[i] = new Integer(a[i]);
+if (a instanceof float[]) {
-}
+compare((float[]) a, (float[]) b, numNaN, numNeg, numNegZero);
-return b;
+} else if (a instanceof double[]) {
-}
+compare((double[]) a, (double[]) b, numNaN, numNeg, numNegZero);
-};
+} else {
+fail("Unknown type of array: " + a.getClass().getName());
-abstract Object convert(int[] a);
+}
+}
-@Override public String toString() {
-String name = name();
+private void compare(float[] a, float[] b, int numNaN, int numNeg, int numNegZero) {
-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]);
+fail("There must be NaN instead of " + a[i] + " at position " + 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]);
+fail("There must be -0.0 instead of " + a[i] + " at position " + i);
 }
 }
 for (int i = 0; i < a.length - numNaN; i++) {
 if (a[i] != b[i]) {
-failedCompare(i, "" + a[i], "" + b[i]);
+fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
 }
 }
 }
-private static void writeValue(double[] a, double value, int fromIndex, int count) {
+private void compare(double[] a, double[] b, int numNaN, int numNeg, int numNegZero) {
-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]);
+fail("There must be NaN instead of " + a[i] + " at position " + 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]);
+fail("There must be -0.0 instead of " + a[i] + " at position " + i);
 }
 }
 for (int i = 0; i < a.length - numNaN; i++) {
 if (a[i] != b[i]) {
-failedCompare(i, "" + a[i], "" + b[i]);
+fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
 }
 }
+}
+private void compare(Object a, Object b) {
+if (a instanceof int[]) {
+compare((int[]) a, (int[]) b);
+} else if (a instanceof long[]) {
+compare((long[]) a, (long[]) b);
+} else if (a instanceof byte[]) {
+compare((byte[]) a, (byte[]) b);
+} else if (a instanceof char[]) {
+compare((char[]) a, (char[]) b);
+} else if (a instanceof short[]) {
+compare((short[]) a, (short[]) b);
+} else if (a instanceof float[]) {
+compare((float[]) a, (float[]) b);
+} else if (a instanceof double[]) {
+compare((double[]) a, (double[]) b);
+} else {
+fail("Unknown type of array: " + a.getClass().getName());
+}
+}
+private void compare(int[] a, int[] b) {
+for (int i = 0; i < a.length; i++) {
+if (a[i] != b[i]) {
+fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
+}
+}
+}
+private void compare(long[] a, long[] b) {
+for (int i = 0; i < a.length; i++) {
+if (a[i] != b[i]) {
+fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
+}
+}
+}
+private void compare(byte[] a, byte[] b) {
+for (int i = 0; i < a.length; i++) {
+if (a[i] != b[i]) {
+fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
+}
+}
+}
+private void compare(char[] a, char[] b) {
+for (int i = 0; i < a.length; i++) {
+if (a[i] != b[i]) {
+fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
+}
+}
+}
+private void compare(short[] a, short[] b) {
+for (int i = 0; i < a.length; i++) {
+if (a[i] != b[i]) {
+fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
+}
+}
+}
+private void compare(float[] a, float[] b) {
+for (int i = 0; i < a.length; i++) {
+if (a[i] != b[i]) {
+fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
+}
+}
+}
+private void compare(double[] a, double[] b) {
+for (int i = 0; i < a.length; i++) {
+if (a[i] != b[i]) {
+fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
+}
+}
+}
+private String getType(int i) {
+Object a = test[i];
+if (a instanceof int[]) {
+return "INT   ";
+}
+if (a instanceof long[]) {
+return "LONG  ";
+}
+if (a instanceof byte[]) {
+return "BYTE  ";
+}
+if (a instanceof char[]) {
+return "CHAR  ";
+}
+if (a instanceof short[]) {
+return "SHORT ";
+}
+if (a instanceof float[]) {
+return "FLOAT ";
+}
+if (a instanceof double[]) {
+return "DOUBLE";
+}
+fail("Unknown type of array: " + a.getClass().getName());
+return null;
+}
+private void checkSorted(Object a) {
+if (a instanceof int[]) {
+checkSorted((int[]) a);
+} else if (a instanceof long[]) {
+checkSorted((long[]) a);
+} else if (a instanceof byte[]) {
+checkSorted((byte[]) a);
+} else if (a instanceof char[]) {
+checkSorted((char[]) a);
+} else if (a instanceof short[]) {
+checkSorted((short[]) a);
+} else if (a instanceof float[]) {
+checkSorted((float[]) a);
+} else if (a instanceof double[]) {
+checkSorted((double[]) a);
+} else {
+fail("Unknown type of array: " + a.getClass().getName());
+}
+}
+private void checkSorted(int[] a) {
+for (int i = 0; i < a.length - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+}
+private void checkSorted(long[] a) {
+for (int i = 0; i < a.length - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+}
+private void checkSorted(byte[] a) {
+for (int i = 0; i < a.length - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+}
+private void checkSorted(char[] a) {
+for (int i = 0; i < a.length - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+}
+private void checkSorted(short[] a) {
+for (int i = 0; i < a.length - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+}
+private void checkSorted(float[] a) {
+for (int i = 0; i < a.length - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+}
+private void checkSorted(double[] a) {
+for (int i = 0; i < a.length - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+}
+private void checkCheckSum(Object test, Object gold) {
+if (checkSumXor(test) != checkSumXor(gold)) {
+fail("Original and sorted arrays are not identical [^]");
+}
+if (checkSumPlus(test) != checkSumPlus(gold)) {
+fail("Original and sorted arrays are not identical [+]");
+}
+}
+private int checkSumXor(Object a) {
+if (a instanceof int[]) {
+return checkSumXor((int[]) a);
+}
+if (a instanceof long[]) {
+return checkSumXor((long[]) a);
+}
+if (a instanceof byte[]) {
+return checkSumXor((byte[]) a);
+}
+if (a instanceof char[]) {
+return checkSumXor((char[]) a);
+}
+if (a instanceof short[]) {
+return checkSumXor((short[]) a);
+}
+if (a instanceof float[]) {
+return checkSumXor((float[]) a);
+}
+if (a instanceof double[]) {
+return checkSumXor((double[]) a);
+}
+fail("Unknown type of array: " + a.getClass().getName());
+return -1;
+}
+private int checkSumXor(int[] a) {
+int checkSum = 0;
+for (int e : a) {
+checkSum ^= e;
+}
+return checkSum;
+}
+private int checkSumXor(long[] a) {
+long checkSum = 0;
+for (long e : a) {
+checkSum ^= e;
+}
+return (int) checkSum;
+}
+private int checkSumXor(byte[] a) {
+byte checkSum = 0;
+for (byte e : a) {
+checkSum ^= e;
+}
+return (int) checkSum;
+}
+private int checkSumXor(char[] a) {
+char checkSum = 0;
+for (char e : a) {
+checkSum ^= e;
+}
+return (int) checkSum;
+}
+private int checkSumXor(short[] a) {
+short checkSum = 0;
+for (short e : a) {
+checkSum ^= e;
+}
+return (int) checkSum;
+}
+private int checkSumXor(float[] a) {
+int checkSum = 0;
+for (float e : a) {
+checkSum ^= (int) e;
+}
+return checkSum;
+}
+private int checkSumXor(double[] a) {
+int checkSum = 0;
+for (double e : a) {
+checkSum ^= (int) e;
+}
+return checkSum;
+}
+private int checkSumPlus(Object a) {
+if (a instanceof int[]) {
+return checkSumPlus((int[]) a);
+}
+if (a instanceof long[]) {
+return checkSumPlus((long[]) a);
+}
+if (a instanceof byte[]) {
+return checkSumPlus((byte[]) a);
+}
+if (a instanceof char[]) {
+return checkSumPlus((char[]) a);
+}
+if (a instanceof short[]) {
+return checkSumPlus((short[]) a);
+}
+if (a instanceof float[]) {
+return checkSumPlus((float[]) a);
+}
+if (a instanceof double[]) {
+return checkSumPlus((double[]) a);
+}
+fail("Unknown type of array: " + a.getClass().getName());
+return -1;
+}
+private int checkSumPlus(int[] a) {
+int checkSum = 0;
+for (int e : a) {
+checkSum += e;
+}
+return checkSum;
+}
+private int checkSumPlus(long[] a) {
+long checkSum = 0;
+for (long e : a) {
+checkSum += e;
+}
+return (int) checkSum;
+}
+private int checkSumPlus(byte[] a) {
+byte checkSum = 0;
+for (byte e : a) {
+checkSum += e;
+}
+return (int) checkSum;
+}
+private int checkSumPlus(char[] a) {
+char checkSum = 0;
+for (char e : a) {
+checkSum += e;
+}
+return (int) checkSum;
+}
+private int checkSumPlus(short[] a) {
+short checkSum = 0;
+for (short e : a) {
+checkSum += e;
+}
+return (int) checkSum;
+}
+private int checkSumPlus(float[] a) {
+int checkSum = 0;
+for (float e : a) {
+checkSum += (int) e;
+}
+return checkSum;
+}
+private int checkSumPlus(double[] a) {
+int checkSum = 0;
+for (double e : a) {
+checkSum += (int) e;
+}
+return checkSum;
+}
+private void sortByInsertionSort(Object a) {
+if (a instanceof int[]) {
+sortByInsertionSort((int[]) a);
+} else if (a instanceof long[]) {
+sortByInsertionSort((long[]) a);
+} else if (a instanceof byte[]) {
+sortByInsertionSort((byte[]) a);
+} else if (a instanceof char[]) {
+sortByInsertionSort((char[]) a);
+} else if (a instanceof short[]) {
+sortByInsertionSort((short[]) a);
+} else if (a instanceof float[]) {
+sortByInsertionSort((float[]) a);
+} else if (a instanceof double[]) {
+sortByInsertionSort((double[]) a);
+} else {
+fail("Unknown type of array: " + a.getClass().getName());
+}
+}
+private 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 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 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 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 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 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 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 void checkSubArray(Object a, int fromIndex, int toIndex) {
+if (a instanceof int[]) {
+checkSubArray((int[]) a, fromIndex, toIndex);
+} else if (a instanceof long[]) {
+checkSubArray((long[]) a, fromIndex, toIndex);
+} else if (a instanceof byte[]) {
+checkSubArray((byte[]) a, fromIndex, toIndex);
+} else if (a instanceof char[]) {
+checkSubArray((char[]) a, fromIndex, toIndex);
+} else if (a instanceof short[]) {
+checkSubArray((short[]) a, fromIndex, toIndex);
+} else if (a instanceof float[]) {
+checkSubArray((float[]) a, fromIndex, toIndex);
+} else if (a instanceof double[]) {
+checkSubArray((double[]) a, fromIndex, toIndex);
+} else {
+fail("Unknown type of array: " + a.getClass().getName());
+}
+}
+private 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 at position " + i + hex(a[i], A380));
+}
+}
+for (int i = fromIndex; i < toIndex - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+for (int i = toIndex; i < a.length; i++) {
+if (a[i] != B747) {
+fail("Range sort changes right element at position " + i + hex(a[i], B747));
+}
+}
+}
+private 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 at position " + i + hex(a[i], A380));
+}
+}
+for (int i = fromIndex; i < toIndex - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+for (int i = toIndex; i < a.length; i++) {
+if (a[i] != (long) B747) {
+fail("Range sort changes right element at position " + i + hex(a[i], B747));
+}
+}
+}
+private 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 at position " + i + hex(a[i], A380));
+}
+}
+for (int i = fromIndex; i < toIndex - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+for (int i = toIndex; i < a.length; i++) {
+if (a[i] != (byte) B747) {
+fail("Range sort changes right element at position " + i + hex(a[i], B747));
+}
+}
+}
+private 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 at position " + i + hex(a[i], A380));
+}
+}
+for (int i = fromIndex; i < toIndex - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+for (int i = toIndex; i < a.length; i++) {
+if (a[i] != (char) B747) {
+fail("Range sort changes right element at position " + i + hex(a[i], B747));
+}
+}
+}
+private 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 at position " + i + hex(a[i], A380));
+}
+}
+for (int i = fromIndex; i < toIndex - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+for (int i = toIndex; i < a.length; i++) {
+if (a[i] != (short) B747) {
+fail("Range sort changes right element at position " + i + hex(a[i], B747));
+}
+}
+}
+private 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 at position " + i + hex((long) a[i], A380));
+}
+}
+for (int i = fromIndex; i < toIndex - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+for (int i = toIndex; i < a.length; i++) {
+if (a[i] != (float) B747) {
+fail("Range sort changes right element at position " + i + hex((long) a[i], B747));
+}
+}
+}
+private 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 at position " + i + hex((long) a[i], A380));
+}
+}
+for (int i = fromIndex; i < toIndex - 1; i++) {
+if (a[i] > a[i + 1]) {
+fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
+}
+}
+for (int i = toIndex; i < a.length; i++) {
+if (a[i] != (double) B747) {
+fail("Range sort changes right element at position " + i + hex((long) a[i], B747));
+}
+}
+}
+private void checkRange(Object a, int m) {
+if (a instanceof int[]) {
+checkRange((int[]) a, m);
+} else if (a instanceof long[]) {
+checkRange((long[]) a, m);
+} else if (a instanceof byte[]) {
+checkRange((byte[]) a, m);
+} else if (a instanceof char[]) {
+checkRange((char[]) a, m);
+} else if (a instanceof short[]) {
+checkRange((short[]) a, m);
+} else if (a instanceof float[]) {
+checkRange((float[]) a, m);
+} else if (a instanceof double[]) {
+checkRange((double[]) a, m);
+} else {
+fail("Unknown type of array: " + a.getClass().getName());
+}
+}
+private 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 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 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 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 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 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 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 void copy(Object dst, Object src) {
+if (src instanceof float[]) {
+copy((float[]) dst, (float[]) src);
+} else if (src instanceof double[]) {
+copy((double[]) dst, (double[]) src);
+} else {
+fail("Unknown type of array: " + src.getClass().getName());
+}
+}
+private void copy(float[] dst, float[] src) {
+System.arraycopy(src, 0, dst, 0, src.length);
+}
+private void copy(double[] dst, double[] src) {
+System.arraycopy(src, 0, dst, 0, src.length);
+}
+private void printTestName(String test, TestRandom random, int length) {
+printTestName(test, random, length, "");
+}
+private void createData(int length) {
+gold = new Object[] {
+new int[length], new long[length],
+new byte[length], new char[length], new short[length],
+new float[length], new double[length]
+};
+test = new Object[] {
+new int[length], new long[length],
+new byte[length], new char[length], new short[length],
+new float[length], new double[length]
+};
+}
+private void convertData(int length) {
+for (int i = 1; i < gold.length; i++) {
+TypeConverter converter = TypeConverter.values()[i - 1];
+converter.convert((int[])gold[0], gold[i]);
+}
+for (int i = 0; i < gold.length; i++) {
+System.arraycopy(gold[i], 0, test[i], 0, length);
+}
+}
+private String hex(long a, int b) {
+return ": " + Long.toHexString(a) + ", must be " + Integer.toHexString(b);
+}
+private void printTestName(String test, TestRandom random, int length, String message) {
+out.println( "[" + sortingHelper + "] '" + test +
+"' length = " + length + ", random = " + random + message);
+}
+private static enum TypeConverter {
+LONG {
+void convert(int[] src, Object dst) {
+long[] b = (long[]) dst;
+for (int i = 0; i < src.length; i++) {
+b[i] = (long) src[i];
+}
+}
+},
+BYTE {
+void convert(int[] src, Object dst) {
+byte[] b = (byte[]) dst;
+for (int i = 0; i < src.length; i++) {
+b[i] = (byte) src[i];
+}
+}
+},
+CHAR {
+void convert(int[] src, Object dst) {
+char[] b = (char[]) dst;
+for (int i = 0; i < src.length; i++) {
+b[i] = (char) src[i];
+}
+}
+},
+SHORT {
+void convert(int[] src, Object dst) {
+short[] b = (short[]) dst;
+for (int i = 0; i < src.length; i++) {
+b[i] = (short) src[i];
+}
+}
+},
+FLOAT {
+void convert(int[] src, Object dst) {
+float[] b = (float[]) dst;
+for (int i = 0; i < src.length; i++) {
+b[i] = (float) src[i];
+}
+}
+},
+DOUBLE {
+void convert(int[] src, Object dst) {
+double[] b = (double[]) dst;
+for (int i = 0; i < src.length; i++) {
+b[i] = (double) src[i];
+}
+}
+};
+abstract void convert(int[] src, Object dst);
 }
 private static enum SortedBuilder {
-REPEATED {
+STEPS {
 void build(int[] a, int m) {
-int period = a.length / m;
+for (int i = 0; i < m; i++) {
-int i = 0;
+a[i] = 0;
-int k = 0;
+}
-while (true) {
+for (int i = m; i < a.length; i++) {
-for (int t = 1; t <= period; t++) {
+a[i] = 1;
-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 {
+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;
 }
 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();
+private static enum MergingBuilder {
+ASCENDING {
-for (int i = name.length(); i < 12; i++) {
+void build(int[] a, int m) {
-name += " ";
+int period = a.length / m;
-}
+int v = 1, i = 0;
-return name;
-}
+for (int k = 0; k < m; k++) {
-}
+v = 1;
-private static void checkWithCheckSum(Object test, Object golden) {
+for (int p = 0; p < period; p++) {
-checkSorted(test);
+a[i++] = v++;
-checkCheckSum(test, golden);
+}
 }
-private static void failed(String message) {
+for (int j = i; j < a.length - 1; j++) {
-err.format("\n*** TEST FAILED - %s.\n\n%s.\n\n", ourDescription, message);
+a[j] = v++;
-throw new RuntimeException("Test failed - see log file for details");
+}
-}
+a[a.length - 1] = 0;
-private static void failedSort(int index, String value1, String value2) {
+}
-failed("Array is not sorted at " + index + "-th position: " +
+},
-value1 + " and " + value2);
-}
+DESCENDING {
+void build(int[] a, int m) {
-private static void failedCompare(int index, String value1, String value2) {
+int period = a.length / m;
-failed("On position " + index + " must be " + value2 + " instead of " + value1);
+int v = -1, i = 0;
-}
+for (int k = 0; k < m; k++) {
-private static void compare(Object test, Object golden) {
+v = -1;
-if (test instanceof int[]) {
-compare((int[]) test, (int[]) golden);
+for (int p = 0; p < period; p++) {
-} else if (test instanceof long[]) {
+a[i++] = v--;
-compare((long[]) test, (long[]) golden);
+}
-} else if (test instanceof short[]) {
+}
-compare((short[]) test, (short[]) golden);
-} else if (test instanceof byte[]) {
+for (int j = i; j < a.length - 1; j++) {
-compare((byte[]) test, (byte[]) golden);
+a[j] = v--;
-} else if (test instanceof char[]) {
+}
-compare((char[]) test, (char[]) golden);
-} else if (test instanceof float[]) {
+a[a.length - 1] = 0;
-compare((float[]) test, (float[]) golden);
+}
-} else if (test instanceof double[]) {
+},
-compare((double[]) test, (double[]) golden);
-} else if (test instanceof Integer[]) {
+POINT {
-compare((Integer[]) test, (Integer[]) golden);
+void build(int[] a, int m) {
-} else {
+for (int i = 0; i < a.length; i++) {
-failed("Unknow type of array: " + test + " of class " +
+a[i] = 0;
-test.getClass().getName());
+}
-}
+a[a.length / 2] = m;
 }
+},
-private static void compare(int[] a, int[] b) {
-for (int i = 0; i < a.length; i++) {
+LINE {
-if (a[i] != b[i]) {
+void build(int[] a, int m) {
-failedCompare(i, "" + a[i], "" + b[i]);
+for (int i = 0; i < a.length; i++) {
-}
+a[i] = i;
 }
-}
+reverse(a, 0, a.length - 1);
+}
-private static void compare(long[] a, long[] b) {
+},
-for (int i = 0; i < a.length; i++) {
-if (a[i] != b[i]) {
+PEARL {
-failedCompare(i, "" + a[i], "" + b[i]);
+void build(int[] a, int m) {
-}
+for (int i = 0; i < a.length; i++) {
-}
+a[i] = i;
 }
+reverse(a, 0, 2);
-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]);
+RING {
-}
+void build(int[] a, int m) {
-}
+int k1 = a.length / 3;
-}
+int k2 = a.length / 3 * 2;
+int level = a.length / 3;
-private static void compare(byte[] a, byte[] b) {
-for (int i = 0; i < a.length; i++) {
+for (int i = 0, k = level; i < k1; i++) {
-if (a[i] != b[i]) {
+a[i] = k--;
-failedCompare(i, "" + a[i], "" + b[i]);
+}
-}
-}
+for (int i = k1; i < k2; i++) {
-}
+a[i] = 0;
+}
-private static void compare(char[] a, char[] b) {
-for (int i = 0; i < a.length; i++) {
+for (int i = k2, k = level; i < a.length; i++) {
-if (a[i] != b[i]) {
+a[i] = k--;
-failedCompare(i, "" + a[i], "" + b[i]);
+}
 }
-}
+};
-}
+abstract void build(int[] a, int m);
-private static void compare(float[] a, float[] b) {
-for (int i = 0; i < a.length; i++) {
+private static void reverse(int[] a, int lo, int hi) {
-if (a[i] != b[i]) {
+for (--hi; lo < hi; ) {
-failedCompare(i, "" + a[i], "" + b[i]);
+int tmp = a[lo];
-}
+a[lo++] = a[hi];
-}
+a[hi--] = tmp;
 }
+}
-private static void compare(double[] a, double[] b) {
+}
-for (int i = 0; i < a.length; i++) {
-if (a[i] != b[i]) {
+private static enum NegativeZeroBuilder {
-failedCompare(i, "" + a[i], "" + b[i]);
+FLOAT {
-}
+void build(Object o, Random random) {
-}
+float[] a = (float[]) o;
-}
+for (int i = 0; i < a.length; i++) {
-private static void compare(Integer[] a, Integer[] b) {
+a[i] = random.nextBoolean() ? -0.0f : 0.0f;
-for (int i = 0; i < a.length; i++) {
+}
-if (a[i].compareTo(b[i]) != 0) {
+}
-failedCompare(i, "" + a[i], "" + b[i]);
+},
-}
-}
+DOUBLE {
-}
+void build(Object o, Random random) {
+double[] a = (double[]) o;
-private static void checkSorted(Object object) {
-if (object instanceof int[]) {
+for (int i = 0; i < a.length; i++) {
-checkSorted((int[]) object);
+a[i] = random.nextBoolean() ? -0.0d : 0.0d;
-} else if (object instanceof long[]) {
+}
-checkSorted((long[]) object);
+}
-} else if (object instanceof short[]) {
+};
-checkSorted((short[]) object);
-} else if (object instanceof byte[]) {
+abstract void build(Object o, Random random);
-checkSorted((byte[]) object);
+}
-} else if (object instanceof char[]) {
-checkSorted((char[]) object);
+private static enum FloatingPointBuilder {
-} else if (object instanceof float[]) {
+FLOAT {
-checkSorted((float[]) object);
+void build(Object o, int a, int g, int z, int n, int p, Random random) {
-} else if (object instanceof double[]) {
+float negativeValue = -random.nextFloat();
-checkSorted((double[]) object);
+float positiveValue =  random.nextFloat();
-} else if (object instanceof Integer[]) {
+float[] x = (float[]) o;
-checkSorted((Integer[]) object);
+int fromIndex = 0;
-} else {
-failed("Unknow type of array: " + object + " of class " +
+writeValue(x, negativeValue, fromIndex, n);
-object.getClass().getName());
+fromIndex += n;
-}
-}
+writeValue(x, -0.0f, fromIndex, g);
+fromIndex += g;
-private static void checkSorted(int[] a) {
-for (int i = 0; i < a.length - 1; i++) {
+writeValue(x, 0.0f, fromIndex, z);
-if (a[i] > a[i + 1]) {
+fromIndex += z;
-failedSort(i, "" + a[i], "" + a[i + 1]);
-}
+writeValue(x, positiveValue, fromIndex, p);
-}
+fromIndex += p;
-}
+writeValue(x, Float.NaN, fromIndex, a);
-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]);
+DOUBLE {
-}
+void build(Object o, int a, int g, int z, int n, int p, Random random) {
-}
+double negativeValue = -random.nextFloat();
-}
+double positiveValue =  random.nextFloat();
+double[] x = (double[]) o;
-private static void checkSorted(short[] a) {
+int fromIndex = 0;
-for (int i = 0; i < a.length - 1; i++) {
-if (a[i] > a[i + 1]) {
+writeValue(x, negativeValue, fromIndex, n);
-failedSort(i, "" + a[i], "" + a[i + 1]);
+fromIndex += n;
-}
-}
+writeValue(x, -0.0d, fromIndex, g);
-}
+fromIndex += g;
-private static void checkSorted(byte[] a) {
+writeValue(x, 0.0d, fromIndex, z);
-for (int i = 0; i < a.length - 1; i++) {
+fromIndex += z;
-if (a[i] > a[i + 1]) {
-failedSort(i, "" + a[i], "" + a[i + 1]);
+writeValue(x, positiveValue, fromIndex, p);
-}
+fromIndex += p;
-}
-}
+writeValue(x, Double.NaN, fromIndex, a);
+}
-private static void checkSorted(char[] a) {
+};
-for (int i = 0; i < a.length - 1; i++) {
-if (a[i] > a[i + 1]) {
+abstract void build(Object o, int a, int g, int z, int n, int p, Random random);
-failedSort(i, "" + a[i], "" + a[i + 1]);
-}
+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 checkSorted(float[] a) {
+}
-for (int i = 0; i < a.length - 1; i++) {
-if (a[i] > a[i + 1]) {
+private static void writeValue(double[] a, double value, int fromIndex, int count) {
-failedSort(i, "" + a[i], "" + a[i + 1]);
+for (int i = fromIndex; i < fromIndex + count; i++) {
-}
+a[i] = value;
 }
 }
+}
-private static void checkSorted(double[] a) {
-for (int i = 0; i < a.length - 1; i++) {
+private static Comparator<Pair> pairComparator = new Comparator<Pair>() {
-if (a[i] > a[i + 1]) {
-failedSort(i, "" + a[i], "" + a[i + 1]);
+@Override
-}
+public int compare(Pair p1, Pair p2) {
-}
+return p1.compareTo(p2);
 }
+};
-private static void checkSorted(Integer[] a) {
-for (int i = 0; i < a.length - 1; i++) {
+private static class Pair implements Comparable<Pair> {
-if (a[i].intValue() > a[i + 1].intValue()) {
-failedSort(i, "" + a[i], "" + a[i + 1]);
+private Pair(int key, int value) {
-}
+this.key = key;
-}
+this.value = value;
 }
-private static void checkCheckSum(Object test, Object golden) {
+int getKey() {
-if (checkSumXor(test) != checkSumXor(golden)) {
+return key;
-failed("Original and sorted arrays are not identical [xor]");
+}
-}
-if (checkSumPlus(test) != checkSumPlus(golden)) {
+int getValue() {
-failed("Original and sorted arrays are not identical [plus]");
+return value;
 }
-}
+@Override
-private static int checkSumXor(Object object) {
+public int compareTo(Pair pair) {
-if (object instanceof int[]) {
+return Integer.compare(key, pair.key);
-return checkSumXor((int[]) object);
+}
-} else if (object instanceof long[]) {
-return checkSumXor((long[]) object);
+@Override
-} else if (object instanceof short[]) {
+public String toString() {
-return checkSumXor((short[]) object);
+return "(" + key + ", " + value + ")";
-} else if (object instanceof byte[]) {
+}
-return checkSumXor((byte[]) object);
-} else if (object instanceof char[]) {
+private int key;
-return checkSumXor((char[]) object);
+private int value;
-} else if (object instanceof float[]) {
+}
-return checkSumXor((float[]) object);
-} else if (object instanceof double[]) {
+private static class TestRandom extends Random {
-return checkSumXor((double[]) object);
-} else if (object instanceof Integer[]) {
+private static final TestRandom BABA = new TestRandom(0xBABA);
-return checkSumXor((Integer[]) object);
+private static final TestRandom DEDA = new TestRandom(0xDEDA);
-} else {
+private static final TestRandom C0FFEE = new TestRandom(0xC0FFEE);
-failed("Unknow type of array: " + object + " of class " +
-object.getClass().getName());
+private TestRandom(long seed) {
-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.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) {
-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.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;
+this.seed = Long.toHexString(seed).toUpperCase();
 }
-long getSeed() {
+@Override
-return mySeed;
+public String toString() {
-}
+return seed;
+}
-private long mySeed;
-}
+private String seed;
+}
-private static String ourDescription;
 }

changeset 59042	8910b995a2ee
parent 47216	71c04702a3d5