1 /*
2 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /*
25 * @test
26 * @bug 6880672 6896573 6899694 6976036 7013585 7018258
27 * @summary Exercise Arrays.sort
28 * @build Sorting
29 * @run main Sorting -shortrun
30 *
31 * @author Vladimir Yaroslavskiy
32 * @author Jon Bentley
33 * @author Josh Bloch
34 */
35
36 import java.util.Arrays;
37 import java.util.Random;
38 import java.io.PrintStream;
39
40 public class Sorting {
41 private static final PrintStream out = System.out;
42 private static final PrintStream err = System.err;
43
44 // Array lengths used in a long run (default)
45 private static final int[] LONG_RUN_LENGTHS = {
46 1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000 };
47
48 // Array lengths used in a short run
49 private static final int[] SHORT_RUN_LENGTHS = {
50 1, 2, 3, 21, 55, 1000, 10000 };
51
52 // Random initial values used in a long run (default)
53 private static final long[] LONG_RUN_RANDOMS = { 666, 0xC0FFEE, 999 };
54
55 // Random initial values used in a short run
56 private static final long[] SHORT_RUN_RANDOMS = { 666 };
57
58 public static void main(String[] args) {
59 boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
60 long start = System.currentTimeMillis();
61
62 if (shortRun) {
63 testAndCheck(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
64 } else {
65 testAndCheck(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
66 }
67 long end = System.currentTimeMillis();
68
69 out.format("PASSED in %d sec.\n", Math.round((end - start) / 1E3));
70 }
71
72 private static void testAndCheck(int[] lengths, long[] randoms) {
73 testEmptyAndNullIntArray();
74 testEmptyAndNullLongArray();
75 testEmptyAndNullShortArray();
76 testEmptyAndNullCharArray();
77 testEmptyAndNullByteArray();
78 testEmptyAndNullFloatArray();
79 testEmptyAndNullDoubleArray();
80
81 for (int length : lengths) {
82 testMergeSort(length);
83 testAndCheckRange(length);
84 testAndCheckSubArray(length);
85 }
86 for (long seed : randoms) {
87 for (int length : lengths) {
88 testAndCheckWithInsertionSort(length, new MyRandom(seed));
89 testAndCheckWithCheckSum(length, new MyRandom(seed));
90 testAndCheckWithScrambling(length, new MyRandom(seed));
91 testAndCheckFloat(length, new MyRandom(seed));
92 testAndCheckDouble(length, new MyRandom(seed));
93 testStable(length, new MyRandom(seed));
94 }
95 }
96 }
97
98 private static void testEmptyAndNullIntArray() {
99 ourDescription = "Check empty and null array";
100 Arrays.sort(new int[] {});
101 Arrays.sort(new int[] {}, 0, 0);
102
266 for (TypeConverter converter : TypeConverter.values()) {
267 out.println("Test 'range': " + converter +
268 ", length = " + length + ", m = " + m);
269 Object convertedGolden = converter.convert(golden);
270 checkRange(convertedGolden, m);
271 }
272 }
273 out.println();
274 }
275
276 private static void testStable(int length, MyRandom random) {
277 ourDescription = "Check if sorting is stable";
278 Pair[] a = build(length, random);
279
280 out.println("Test 'stable': " + "random = " + random.getSeed() +
281 ", length = " + length);
282 Arrays.sort(a);
283 checkSorted(a);
284 checkStable(a);
285 out.println();
286 }
287
288 private static void checkSorted(Pair[] a) {
289 for (int i = 0; i < a.length - 1; i++) {
290 if (a[i].getKey() > a[i + 1].getKey()) {
291 failedSort(i, "" + a[i].getKey(), "" + a[i + 1].getKey());
292 }
293 }
294 }
295
296 private static void checkStable(Pair[] a) {
297 for (int i = 0; i < a.length / 4; ) {
298 int key1 = a[i].getKey();
299 int value1 = a[i++].getValue();
300 int key2 = a[i].getKey();
301 int value2 = a[i++].getValue();
302 int key3 = a[i].getKey();
303 int value3 = a[i++].getValue();
304 int key4 = a[i].getKey();
305 int value4 = a[i++].getValue();
312 failed("Sorting is not stable at position " + i +
313 ". Second values have been changed: " + value1 + ", " +
314 value2 + ", " + value3 + ", " + value4);
315 }
316 }
317 }
318
319 private static Pair[] build(int length, Random random) {
320 Pair[] a = new Pair[length * 4];
321
322 for (int i = 0; i < a.length; ) {
323 int key = random.nextInt();
324 a[i++] = new Pair(key, 1);
325 a[i++] = new Pair(key, 2);
326 a[i++] = new Pair(key, 3);
327 a[i++] = new Pair(key, 4);
328 }
329 return a;
330 }
331
332 private static final class Pair implements Comparable<Pair> {
333 Pair(int key, int value) {
334 myKey = key;
335 myValue = value;
336 }
337
338 int getKey() {
339 return myKey;
340 }
341
342 int getValue() {
343 return myValue;
344 }
345
346 public int compareTo(Pair pair) {
347 if (myKey < pair.myKey) {
348 return -1;
349 }
350 if (myKey > pair.myKey) {
351 return 1;
374 for (UnsortedBuilder builder : UnsortedBuilder.values()) {
375 builder.build(golden, m, random);
376 int[] test = golden.clone();
377
378 for (TypeConverter converter : TypeConverter.values()) {
379 out.println("Test 'insertion sort': " + converter +
380 " " + builder + "random = " + random.getSeed() +
381 ", length = " + length + ", m = " + m);
382 Object convertedGolden = converter.convert(golden);
383 Object convertedTest1 = converter.convert(test);
384 Object convertedTest2 = converter.convert(test);
385 sort(convertedTest1);
386 sortByInsertionSort(convertedTest2);
387 compare(convertedTest1, convertedTest2);
388 }
389 }
390 }
391 out.println();
392 }
393
394 private static void testMergeSort(int length) {
395 if (length < 1000) {
396 return;
397 }
398 ourDescription = "Check merge sorting";
399 int[] golden = new int[length];
400 int period = 67; // java.util.DualPivotQuicksort.MAX_RUN_COUNT
401
402 for (int m = period - 2; m <= period + 2; m++) {
403 for (MergeBuilder builder : MergeBuilder.values()) {
404 builder.build(golden, m);
405 int[] test = golden.clone();
406
407 for (TypeConverter converter : TypeConverter.values()) {
408 out.println("Test 'merge sort': " + converter + " " +
409 builder + "length = " + length + ", m = " + m);
410 Object convertedGolden = converter.convert(golden);
411 sort(convertedGolden);
412 checkSorted(convertedGolden);
413 }
414 }
415 }
416 out.println();
417 }
418
419 private static void testAndCheckWithCheckSum(int length, MyRandom random) {
420 ourDescription = "Check sorting with check sum";
421 int[] golden = new int[length];
422
423 for (int m = 1; m < 2 * length; m *= 2) {
424 for (UnsortedBuilder builder : UnsortedBuilder.values()) {
425 builder.build(golden, m, random);
426 int[] test = golden.clone();
427
428 for (TypeConverter converter : TypeConverter.values()) {
452 int[] test = golden.clone();
453 scramble(test, random);
454
455 for (TypeConverter converter : TypeConverter.values()) {
456 out.println("Test 'scrambling': " + converter +
457 " " + builder + "random = " + random.getSeed() +
458 ", length = " + length + ", m = " + m);
459 Object convertedGolden = converter.convert(golden);
460 Object convertedTest = converter.convert(test);
461 sort(convertedTest);
462 compare(convertedTest, convertedGolden);
463 }
464 }
465 }
466 out.println();
467 }
468
469 private static void testAndCheckFloat(int length, MyRandom random) {
470 ourDescription = "Check float sorting";
471 float[] golden = new float[length];
472 final int MAX = 10;
473 boolean newLine = false;
474
475 for (int a = 0; a <= MAX; a++) {
476 for (int g = 0; g <= MAX; g++) {
477 for (int z = 0; z <= MAX; z++) {
478 for (int n = 0; n <= MAX; n++) {
479 for (int p = 0; p <= MAX; p++) {
480 if (a + g + z + n + p > length) {
481 continue;
482 }
483 if (a + g + z + n + p < length) {
484 continue;
485 }
486 for (FloatBuilder builder : FloatBuilder.values()) {
487 out.println("Test 'float': random = " + random.getSeed() +
488 ", length = " + length + ", a = " + a + ", g = " +
489 g + ", z = " + z + ", n = " + n + ", p = " + p);
490 builder.build(golden, a, g, z, n, p, random);
491 float[] test = golden.clone();
492 scramble(test, random);
493 sort(test);
494 compare(test, golden, a, n, g);
495 }
496 newLine = true;
497 }
498 }
499 }
500 }
501 }
502 if (newLine) {
503 out.println();
527 g + ", z = " + z + ", n = " + n + ", p = " + p);
528 builder.build(golden, a, g, z, n, p, random);
529 double[] test = golden.clone();
530 scramble(test, random);
531 sort(test);
532 compare(test, golden, a, n, g);
533 }
534 newLine = true;
535 }
536 }
537 }
538 }
539 }
540 if (newLine) {
541 out.println();
542 }
543 }
544
545 private static void prepareSubArray(int[] a, int fromIndex, int toIndex, int m) {
546 for (int i = 0; i < fromIndex; i++) {
547 a[i] = 0xDEDA;
548 }
549 int middle = (fromIndex + toIndex) >>> 1;
550 int k = 0;
551
552 for (int i = fromIndex; i < middle; i++) {
553 a[i] = k++;
554 }
555 for (int i = middle; i < toIndex; i++) {
556 a[i] = k--;
557 }
558 for (int i = toIndex; i < a.length; i++) {
559 a[i] = 0xBABA;
560 }
561 }
562
563 private static void scramble(int[] a, Random random) {
564 for (int i = 0; i < a.length * 7; i++) {
565 swap(a, random.nextInt(a.length), random.nextInt(a.length));
566 }
567 }
568
569 private static void scramble(float[] a, Random random) {
570 for (int i = 0; i < a.length * 7; i++) {
571 swap(a, random.nextInt(a.length), random.nextInt(a.length));
572 }
573 }
574
575 private static void scramble(double[] a, Random random) {
576 for (int i = 0; i < a.length * 7; i++) {
577 swap(a, random.nextInt(a.length), random.nextInt(a.length));
578 }
579 }
650 b[i] = (float) a[i];
651 }
652 return b;
653 }
654 },
655 DOUBLE {
656 Object convert(int[] a) {
657 double[] b = new double[a.length];
658
659 for (int i = 0; i < a.length; i++) {
660 b[i] = (double) a[i];
661 }
662 return b;
663 }
664 },
665 INTEGER {
666 Object convert(int[] a) {
667 Integer[] b = new Integer[a.length];
668
669 for (int i = 0; i < a.length; i++) {
670 b[i] = new Integer(a[i]);
671 }
672 return b;
673 }
674 };
675
676 abstract Object convert(int[] a);
677
678 @Override public String toString() {
679 String name = name();
680
681 for (int i = name.length(); i < 9; i++) {
682 name += " ";
683 }
684 return name;
685 }
686 }
687
688 private static enum FloatBuilder {
689 SIMPLE {
690 void build(float[] x, int a, int g, int z, int n, int p, Random random) {
691 int fromIndex = 0;
692 float negativeValue = -random.nextFloat();
693 float positiveValue = random.nextFloat();
694
695 writeValue(x, negativeValue, fromIndex, n);
696 fromIndex += n;
697
698 writeValue(x, -0.0f, fromIndex, g);
811 }
812 },
813 ORGAN_PIPES {
814 void build(int[] a, int m) {
815 int i = 0;
816 int k = m;
817
818 while (true) {
819 for (int t = 1; t <= m; t++) {
820 if (i >= a.length) {
821 return;
822 }
823 a[i++] = k;
824 }
825 }
826 }
827 };
828
829 abstract void build(int[] a, int m);
830
831 @Override public String toString() {
832 String name = name();
833
834 for (int i = name.length(); i < 12; i++) {
835 name += " ";
836 }
837 return name;
838 }
839 }
840
841 private static enum MergeBuilder {
842 ASCENDING {
843 void build(int[] a, int m) {
844 int period = a.length / m;
845 int v = 1, i = 0;
846
847 for (int k = 0; k < m; k++) {
848 v = 1;
849 for (int p = 0; p < period; p++) {
850 a[i++] = v++;
851 }
852 }
853 for (int j = i; j < a.length - 1; j++) {
854 a[j] = v++;
855 }
856 a[a.length - 1] = 0;
857 }
858 },
859 DESCENDING {
860 void build(int[] a, int m) {
861 int period = a.length / m;
862 int v = -1, i = 0;
863
864 for (int k = 0; k < m; k++) {
865 v = -1;
866 for (int p = 0; p < period; p++) {
867 a[i++] = v--;
868 }
869 }
870 for (int j = i; j < a.length - 1; j++) {
871 a[j] = v--;
872 }
873 a[a.length - 1] = 0;
874 }
875 };
876
877 abstract void build(int[] a, int m);
878
879 @Override public String toString() {
880 String name = name();
881
882 for (int i = name.length(); i < 12; i++) {
883 name += " ";
884 }
885 return name;
886 }
887 }
888
889 private static enum UnsortedBuilder {
890 RANDOM {
891 void build(int[] a, int m, Random random) {
892 for (int i = 0; i < a.length; i++) {
893 a[i] = random.nextInt();
894 }
895 }
896 },
897 ASCENDING {
898 void build(int[] a, int m, Random random) {
899 for (int i = 0; i < a.length; i++) {
900 a[i] = m + i;
901 }
902 }
903 },
904 DESCENDING {
905 void build(int[] a, int m, Random random) {
906 for (int i = 0; i < a.length; i++) {
907 a[i] = a.length - m - i;
908 }
975 }
976 },
977 PLATEAU {
978 void build(int[] a, int m, Random random) {
979 for (int i = 0; i < a.length; i++) {
980 a[i] = Math.min(i, m);
981 }
982 }
983 },
984 SHUFFLE {
985 void build(int[] a, int m, Random random) {
986 int x = 0, y = 0;
987 for (int i = 0; i < a.length; i++) {
988 a[i] = random.nextBoolean() ? (x += 2) : (y += 2);
989 }
990 }
991 };
992
993 abstract void build(int[] a, int m, Random random);
994
995 @Override public String toString() {
996 String name = name();
997
998 for (int i = name.length(); i < 12; i++) {
999 name += " ";
1000 }
1001 return name;
1002 }
1003 }
1004
1005 private static void checkWithCheckSum(Object test, Object golden) {
1006 checkSorted(test);
1007 checkCheckSum(test, golden);
1008 }
1009
1010 private static void failed(String message) {
1011 err.format("\n*** TEST FAILED - %s.\n\n%s.\n\n", ourDescription, message);
1012 throw new RuntimeException("Test failed - see log file for details");
1013 }
1014
1015 private static void failedSort(int index, String value1, String value2) {
1022 }
1023
1024 private static void compare(Object test, Object golden) {
1025 if (test instanceof int[]) {
1026 compare((int[]) test, (int[]) golden);
1027 } else if (test instanceof long[]) {
1028 compare((long[]) test, (long[]) golden);
1029 } else if (test instanceof short[]) {
1030 compare((short[]) test, (short[]) golden);
1031 } else if (test instanceof byte[]) {
1032 compare((byte[]) test, (byte[]) golden);
1033 } else if (test instanceof char[]) {
1034 compare((char[]) test, (char[]) golden);
1035 } else if (test instanceof float[]) {
1036 compare((float[]) test, (float[]) golden);
1037 } else if (test instanceof double[]) {
1038 compare((double[]) test, (double[]) golden);
1039 } else if (test instanceof Integer[]) {
1040 compare((Integer[]) test, (Integer[]) golden);
1041 } else {
1042 failed("Unknow type of array: " + test + " of class " +
1043 test.getClass().getName());
1044 }
1045 }
1046
1047 private static void compare(int[] a, int[] b) {
1048 for (int i = 0; i < a.length; i++) {
1049 if (a[i] != b[i]) {
1050 failedCompare(i, "" + a[i], "" + b[i]);
1051 }
1052 }
1053 }
1054
1055 private static void compare(long[] a, long[] b) {
1056 for (int i = 0; i < a.length; i++) {
1057 if (a[i] != b[i]) {
1058 failedCompare(i, "" + a[i], "" + b[i]);
1059 }
1060 }
1061 }
1062
1109 }
1110
1111 private static void checkSorted(Object object) {
1112 if (object instanceof int[]) {
1113 checkSorted((int[]) object);
1114 } else if (object instanceof long[]) {
1115 checkSorted((long[]) object);
1116 } else if (object instanceof short[]) {
1117 checkSorted((short[]) object);
1118 } else if (object instanceof byte[]) {
1119 checkSorted((byte[]) object);
1120 } else if (object instanceof char[]) {
1121 checkSorted((char[]) object);
1122 } else if (object instanceof float[]) {
1123 checkSorted((float[]) object);
1124 } else if (object instanceof double[]) {
1125 checkSorted((double[]) object);
1126 } else if (object instanceof Integer[]) {
1127 checkSorted((Integer[]) object);
1128 } else {
1129 failed("Unknow type of array: " + object + " of class " +
1130 object.getClass().getName());
1131 }
1132 }
1133
1134 private static void checkSorted(int[] a) {
1135 for (int i = 0; i < a.length - 1; i++) {
1136 if (a[i] > a[i + 1]) {
1137 failedSort(i, "" + a[i], "" + a[i + 1]);
1138 }
1139 }
1140 }
1141
1142 private static void checkSorted(long[] a) {
1143 for (int i = 0; i < a.length - 1; i++) {
1144 if (a[i] > a[i + 1]) {
1145 failedSort(i, "" + a[i], "" + a[i + 1]);
1146 }
1147 }
1148 }
1149
1205 }
1206
1207 private static int checkSumXor(Object object) {
1208 if (object instanceof int[]) {
1209 return checkSumXor((int[]) object);
1210 } else if (object instanceof long[]) {
1211 return checkSumXor((long[]) object);
1212 } else if (object instanceof short[]) {
1213 return checkSumXor((short[]) object);
1214 } else if (object instanceof byte[]) {
1215 return checkSumXor((byte[]) object);
1216 } else if (object instanceof char[]) {
1217 return checkSumXor((char[]) object);
1218 } else if (object instanceof float[]) {
1219 return checkSumXor((float[]) object);
1220 } else if (object instanceof double[]) {
1221 return checkSumXor((double[]) object);
1222 } else if (object instanceof Integer[]) {
1223 return checkSumXor((Integer[]) object);
1224 } else {
1225 failed("Unknow type of array: " + object + " of class " +
1226 object.getClass().getName());
1227 return -1;
1228 }
1229 }
1230
1231 private static int checkSumXor(Integer[] a) {
1232 int checkSum = 0;
1233
1234 for (Integer e : a) {
1235 checkSum ^= e.intValue();
1236 }
1237 return checkSum;
1238 }
1239
1240 private static int checkSumXor(int[] a) {
1241 int checkSum = 0;
1242
1243 for (int e : a) {
1244 checkSum ^= e;
1245 }
1301 }
1302
1303 private static int checkSumPlus(Object object) {
1304 if (object instanceof int[]) {
1305 return checkSumPlus((int[]) object);
1306 } else if (object instanceof long[]) {
1307 return checkSumPlus((long[]) object);
1308 } else if (object instanceof short[]) {
1309 return checkSumPlus((short[]) object);
1310 } else if (object instanceof byte[]) {
1311 return checkSumPlus((byte[]) object);
1312 } else if (object instanceof char[]) {
1313 return checkSumPlus((char[]) object);
1314 } else if (object instanceof float[]) {
1315 return checkSumPlus((float[]) object);
1316 } else if (object instanceof double[]) {
1317 return checkSumPlus((double[]) object);
1318 } else if (object instanceof Integer[]) {
1319 return checkSumPlus((Integer[]) object);
1320 } else {
1321 failed("Unknow type of array: " + object + " of class " +
1322 object.getClass().getName());
1323 return -1;
1324 }
1325 }
1326
1327 private static int checkSumPlus(int[] a) {
1328 int checkSum = 0;
1329
1330 for (int e : a) {
1331 checkSum += e;
1332 }
1333 return checkSum;
1334 }
1335
1336 private static int checkSumPlus(long[] a) {
1337 long checkSum = 0;
1338
1339 for (long e : a) {
1340 checkSum += e;
1341 }
1397 }
1398
1399 private static void sortByInsertionSort(Object object) {
1400 if (object instanceof int[]) {
1401 sortByInsertionSort((int[]) object);
1402 } else if (object instanceof long[]) {
1403 sortByInsertionSort((long[]) object);
1404 } else if (object instanceof short[]) {
1405 sortByInsertionSort((short[]) object);
1406 } else if (object instanceof byte[]) {
1407 sortByInsertionSort((byte[]) object);
1408 } else if (object instanceof char[]) {
1409 sortByInsertionSort((char[]) object);
1410 } else if (object instanceof float[]) {
1411 sortByInsertionSort((float[]) object);
1412 } else if (object instanceof double[]) {
1413 sortByInsertionSort((double[]) object);
1414 } else if (object instanceof Integer[]) {
1415 sortByInsertionSort((Integer[]) object);
1416 } else {
1417 failed("Unknow type of array: " + object + " of class " +
1418 object.getClass().getName());
1419 }
1420 }
1421
1422 private static void sortByInsertionSort(int[] a) {
1423 for (int j, i = 1; i < a.length; i++) {
1424 int ai = a[i];
1425 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1426 a[j + 1] = a[j];
1427 }
1428 a[j + 1] = ai;
1429 }
1430 }
1431
1432 private static void sortByInsertionSort(long[] a) {
1433 for (int j, i = 1; i < a.length; i++) {
1434 long ai = a[i];
1435 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1436 a[j + 1] = a[j];
1437 }
1500 }
1501
1502 private static void sort(Object object) {
1503 if (object instanceof int[]) {
1504 Arrays.sort((int[]) object);
1505 } else if (object instanceof long[]) {
1506 Arrays.sort((long[]) object);
1507 } else if (object instanceof short[]) {
1508 Arrays.sort((short[]) object);
1509 } else if (object instanceof byte[]) {
1510 Arrays.sort((byte[]) object);
1511 } else if (object instanceof char[]) {
1512 Arrays.sort((char[]) object);
1513 } else if (object instanceof float[]) {
1514 Arrays.sort((float[]) object);
1515 } else if (object instanceof double[]) {
1516 Arrays.sort((double[]) object);
1517 } else if (object instanceof Integer[]) {
1518 Arrays.sort((Integer[]) object);
1519 } else {
1520 failed("Unknow type of array: " + object + " of class " +
1521 object.getClass().getName());
1522 }
1523 }
1524
1525 private static void sortSubArray(Object object, int fromIndex, int toIndex) {
1526 if (object instanceof int[]) {
1527 Arrays.sort((int[]) object, fromIndex, toIndex);
1528 } else if (object instanceof long[]) {
1529 Arrays.sort((long[]) object, fromIndex, toIndex);
1530 } else if (object instanceof short[]) {
1531 Arrays.sort((short[]) object, fromIndex, toIndex);
1532 } else if (object instanceof byte[]) {
1533 Arrays.sort((byte[]) object, fromIndex, toIndex);
1534 } else if (object instanceof char[]) {
1535 Arrays.sort((char[]) object, fromIndex, toIndex);
1536 } else if (object instanceof float[]) {
1537 Arrays.sort((float[]) object, fromIndex, toIndex);
1538 } else if (object instanceof double[]) {
1539 Arrays.sort((double[]) object, fromIndex, toIndex);
1540 } else if (object instanceof Integer[]) {
1541 Arrays.sort((Integer[]) object, fromIndex, toIndex);
1542 } else {
1543 failed("Unknow type of array: " + object + " of class " +
1544 object.getClass().getName());
1545 }
1546 }
1547
1548 private static void checkSubArray(Object object, int fromIndex, int toIndex, int m) {
1549 if (object instanceof int[]) {
1550 checkSubArray((int[]) object, fromIndex, toIndex, m);
1551 } else if (object instanceof long[]) {
1552 checkSubArray((long[]) object, fromIndex, toIndex, m);
1553 } else if (object instanceof short[]) {
1554 checkSubArray((short[]) object, fromIndex, toIndex, m);
1555 } else if (object instanceof byte[]) {
1556 checkSubArray((byte[]) object, fromIndex, toIndex, m);
1557 } else if (object instanceof char[]) {
1558 checkSubArray((char[]) object, fromIndex, toIndex, m);
1559 } else if (object instanceof float[]) {
1560 checkSubArray((float[]) object, fromIndex, toIndex, m);
1561 } else if (object instanceof double[]) {
1562 checkSubArray((double[]) object, fromIndex, toIndex, m);
1563 } else if (object instanceof Integer[]) {
1564 checkSubArray((Integer[]) object, fromIndex, toIndex, m);
1565 } else {
1566 failed("Unknow type of array: " + object + " of class " +
1567 object.getClass().getName());
1568 }
1569 }
1570
1571 private static void checkSubArray(Integer[] a, int fromIndex, int toIndex, int m) {
1572 for (int i = 0; i < fromIndex; i++) {
1573 if (a[i].intValue() != 0xDEDA) {
1574 failed("Range sort changes left element on position " + i +
1575 ": " + a[i] + ", must be " + 0xDEDA);
1576 }
1577 }
1578
1579 for (int i = fromIndex; i < toIndex - 1; i++) {
1580 if (a[i].intValue() > a[i + 1].intValue()) {
1581 failedSort(i, "" + a[i], "" + a[i + 1]);
1582 }
1583 }
1584
1585 for (int i = toIndex; i < a.length; i++) {
1586 if (a[i].intValue() != 0xBABA) {
1587 failed("Range sort changes right element on position " + i +
1588 ": " + a[i] + ", must be " + 0xBABA);
1589 }
1590 }
1591 }
1592
1593 private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) {
1594 for (int i = 0; i < fromIndex; i++) {
1595 if (a[i] != 0xDEDA) {
1596 failed("Range sort changes left element on position " + i +
1597 ": " + a[i] + ", must be " + 0xDEDA);
1598 }
1599 }
1600
1601 for (int i = fromIndex; i < toIndex - 1; i++) {
1602 if (a[i] > a[i + 1]) {
1603 failedSort(i, "" + a[i], "" + a[i + 1]);
1604 }
1605 }
1606
1607 for (int i = toIndex; i < a.length; i++) {
1608 if (a[i] != 0xBABA) {
1609 failed("Range sort changes right element on position " + i +
1610 ": " + a[i] + ", must be " + 0xBABA);
1611 }
1612 }
1613 }
1614
1615 private static void checkSubArray(byte[] a, int fromIndex, int toIndex, int m) {
1616 for (int i = 0; i < fromIndex; i++) {
1617 if (a[i] != (byte) 0xDEDA) {
1618 failed("Range sort changes left element on position " + i +
1619 ": " + a[i] + ", must be " + 0xDEDA);
1620 }
1621 }
1622
1623 for (int i = fromIndex; i < toIndex - 1; i++) {
1624 if (a[i] > a[i + 1]) {
1625 failedSort(i, "" + a[i], "" + a[i + 1]);
1626 }
1627 }
1628
1629 for (int i = toIndex; i < a.length; i++) {
1630 if (a[i] != (byte) 0xBABA) {
1631 failed("Range sort changes right element on position " + i +
1632 ": " + a[i] + ", must be " + 0xBABA);
1633 }
1634 }
1635 }
1636
1637 private static void checkSubArray(long[] a, int fromIndex, int toIndex, int m) {
1638 for (int i = 0; i < fromIndex; i++) {
1639 if (a[i] != (long) 0xDEDA) {
1640 failed("Range sort changes left element on position " + i +
1641 ": " + a[i] + ", must be " + 0xDEDA);
1642 }
1643 }
1644
1645 for (int i = fromIndex; i < toIndex - 1; i++) {
1646 if (a[i] > a[i + 1]) {
1647 failedSort(i, "" + a[i], "" + a[i + 1]);
1648 }
1649 }
1650
1651 for (int i = toIndex; i < a.length; i++) {
1652 if (a[i] != (long) 0xBABA) {
1653 failed("Range sort changes right element on position " + i +
1654 ": " + a[i] + ", must be " + 0xBABA);
1655 }
1656 }
1657 }
1658
1659 private static void checkSubArray(char[] a, int fromIndex, int toIndex, int m) {
1660 for (int i = 0; i < fromIndex; i++) {
1661 if (a[i] != (char) 0xDEDA) {
1662 failed("Range sort changes left element on position " + i +
1663 ": " + a[i] + ", must be " + 0xDEDA);
1664 }
1665 }
1666
1667 for (int i = fromIndex; i < toIndex - 1; i++) {
1668 if (a[i] > a[i + 1]) {
1669 failedSort(i, "" + a[i], "" + a[i + 1]);
1670 }
1671 }
1672
1673 for (int i = toIndex; i < a.length; i++) {
1674 if (a[i] != (char) 0xBABA) {
1675 failed("Range sort changes right element on position " + i +
1676 ": " + a[i] + ", must be " + 0xBABA);
1677 }
1678 }
1679 }
1680
1681 private static void checkSubArray(short[] a, int fromIndex, int toIndex, int m) {
1682 for (int i = 0; i < fromIndex; i++) {
1683 if (a[i] != (short) 0xDEDA) {
1684 failed("Range sort changes left element on position " + i +
1685 ": " + a[i] + ", must be " + 0xDEDA);
1686 }
1687 }
1688
1689 for (int i = fromIndex; i < toIndex - 1; i++) {
1690 if (a[i] > a[i + 1]) {
1691 failedSort(i, "" + a[i], "" + a[i + 1]);
1692 }
1693 }
1694
1695 for (int i = toIndex; i < a.length; i++) {
1696 if (a[i] != (short) 0xBABA) {
1697 failed("Range sort changes right element on position " + i +
1698 ": " + a[i] + ", must be " + 0xBABA);
1699 }
1700 }
1701 }
1702
1703 private static void checkSubArray(float[] a, int fromIndex, int toIndex, int m) {
1704 for (int i = 0; i < fromIndex; i++) {
1705 if (a[i] != (float) 0xDEDA) {
1706 failed("Range sort changes left element on position " + i +
1707 ": " + a[i] + ", must be " + 0xDEDA);
1708 }
1709 }
1710
1711 for (int i = fromIndex; i < toIndex - 1; i++) {
1712 if (a[i] > a[i + 1]) {
1713 failedSort(i, "" + a[i], "" + a[i + 1]);
1714 }
1715 }
1716
1717 for (int i = toIndex; i < a.length; i++) {
1718 if (a[i] != (float) 0xBABA) {
1719 failed("Range sort changes right element on position " + i +
1720 ": " + a[i] + ", must be " + 0xBABA);
1721 }
1722 }
1723 }
1724
1725 private static void checkSubArray(double[] a, int fromIndex, int toIndex, int m) {
1726 for (int i = 0; i < fromIndex; i++) {
1727 if (a[i] != (double) 0xDEDA) {
1728 failed("Range sort changes left element on position " + i +
1729 ": " + a[i] + ", must be " + 0xDEDA);
1730 }
1731 }
1732
1733 for (int i = fromIndex; i < toIndex - 1; i++) {
1734 if (a[i] > a[i + 1]) {
1735 failedSort(i, "" + a[i], "" + a[i + 1]);
1736 }
1737 }
1738
1739 for (int i = toIndex; i < a.length; i++) {
1740 if (a[i] != (double) 0xBABA) {
1741 failed("Range sort changes right element on position " + i +
1742 ": " + a[i] + ", must be " + 0xBABA);
1743 }
1744 }
1745 }
1746
1747 private static void checkRange(Object object, int m) {
1748 if (object instanceof int[]) {
1749 checkRange((int[]) object, m);
1750 } else if (object instanceof long[]) {
1751 checkRange((long[]) object, m);
1752 } else if (object instanceof short[]) {
1753 checkRange((short[]) object, m);
1754 } else if (object instanceof byte[]) {
1755 checkRange((byte[]) object, m);
1756 } else if (object instanceof char[]) {
1757 checkRange((char[]) object, m);
1758 } else if (object instanceof float[]) {
1759 checkRange((float[]) object, m);
1760 } else if (object instanceof double[]) {
1761 checkRange((double[]) object, m);
1762 } else if (object instanceof Integer[]) {
1763 checkRange((Integer[]) object, m);
1764 } else {
1765 failed("Unknow type of array: " + object + " of class " +
1766 object.getClass().getName());
1767 }
1768 }
1769
1770 private static void checkRange(Integer[] a, int m) {
1771 try {
1772 Arrays.sort(a, m + 1, m);
1773
1774 failed("Sort does not throw IllegalArgumentException " +
1775 " as expected: fromIndex = " + (m + 1) +
1776 " toIndex = " + m);
1777 }
1778 catch (IllegalArgumentException iae) {
1779 try {
1780 Arrays.sort(a, -m, a.length);
1781
1782 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1783 " as expected: fromIndex = " + (-m));
1784 }
1785 catch (ArrayIndexOutOfBoundsException aoe) {
1786 try {
1787 Arrays.sort(a, 0, a.length + m);
1788
1789 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1790 " as expected: toIndex = " + (a.length + m));
1791 }
1792 catch (ArrayIndexOutOfBoundsException aie) {
1793 return;
1794 }
1795 }
1796 }
1797 }
1798
1799 private static void checkRange(int[] a, int m) {
1800 try {
1801 Arrays.sort(a, m + 1, m);
1802
1803 failed("Sort does not throw IllegalArgumentException " +
1804 " as expected: fromIndex = " + (m + 1) +
1805 " toIndex = " + m);
1806 }
1807 catch (IllegalArgumentException iae) {
1808 try {
1809 Arrays.sort(a, -m, a.length);
1810
1811 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1812 " as expected: fromIndex = " + (-m));
1813 }
1814 catch (ArrayIndexOutOfBoundsException aoe) {
1815 try {
1816 Arrays.sort(a, 0, a.length + m);
1817
1818 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1819 " as expected: toIndex = " + (a.length + m));
1820 }
1821 catch (ArrayIndexOutOfBoundsException aie) {
1822 return;
1823 }
1824 }
1825 }
1826 }
1827
1828 private static void checkRange(long[] a, int m) {
1829 try {
1830 Arrays.sort(a, m + 1, m);
1831
1832 failed("Sort does not throw IllegalArgumentException " +
1833 " as expected: fromIndex = " + (m + 1) +
1834 " toIndex = " + m);
1835 }
1836 catch (IllegalArgumentException iae) {
1837 try {
1838 Arrays.sort(a, -m, a.length);
1839
1840 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1841 " as expected: fromIndex = " + (-m));
1842 }
1843 catch (ArrayIndexOutOfBoundsException aoe) {
1844 try {
1845 Arrays.sort(a, 0, a.length + m);
1846
1847 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1848 " as expected: toIndex = " + (a.length + m));
1849 }
1850 catch (ArrayIndexOutOfBoundsException aie) {
1851 return;
1852 }
1853 }
1854 }
1855 }
1856
1857 private static void checkRange(byte[] a, int m) {
1858 try {
1859 Arrays.sort(a, m + 1, m);
1860
1861 failed("Sort does not throw IllegalArgumentException " +
1862 " as expected: fromIndex = " + (m + 1) +
1863 " toIndex = " + m);
1864 }
1865 catch (IllegalArgumentException iae) {
1866 try {
1867 Arrays.sort(a, -m, a.length);
1868
1869 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1870 " as expected: fromIndex = " + (-m));
1871 }
1872 catch (ArrayIndexOutOfBoundsException aoe) {
1873 try {
1874 Arrays.sort(a, 0, a.length + m);
1875
1876 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1877 " as expected: toIndex = " + (a.length + m));
1878 }
1879 catch (ArrayIndexOutOfBoundsException aie) {
1880 return;
1881 }
1882 }
1883 }
1884 }
1885
1886 private static void checkRange(short[] a, int m) {
1887 try {
1888 Arrays.sort(a, m + 1, m);
1889
1890 failed("Sort does not throw IllegalArgumentException " +
1891 " as expected: fromIndex = " + (m + 1) +
1892 " toIndex = " + m);
1893 }
1894 catch (IllegalArgumentException iae) {
1895 try {
1896 Arrays.sort(a, -m, a.length);
1897
1898 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1899 " as expected: fromIndex = " + (-m));
1900 }
1901 catch (ArrayIndexOutOfBoundsException aoe) {
1902 try {
1903 Arrays.sort(a, 0, a.length + m);
1904
1905 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1906 " as expected: toIndex = " + (a.length + m));
1907 }
1908 catch (ArrayIndexOutOfBoundsException aie) {
1909 return;
1910 }
1911 }
1912 }
1913 }
1914
1915 private static void checkRange(char[] a, int m) {
1916 try {
1917 Arrays.sort(a, m + 1, m);
1918
1919 failed("Sort does not throw IllegalArgumentException " +
1920 " as expected: fromIndex = " + (m + 1) +
1921 " toIndex = " + m);
1922 }
1923 catch (IllegalArgumentException iae) {
1924 try {
1925 Arrays.sort(a, -m, a.length);
1926
1927 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1928 " as expected: fromIndex = " + (-m));
1929 }
1930 catch (ArrayIndexOutOfBoundsException aoe) {
1931 try {
1932 Arrays.sort(a, 0, a.length + m);
1933
1934 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1935 " as expected: toIndex = " + (a.length + m));
1936 }
1937 catch (ArrayIndexOutOfBoundsException aie) {
1938 return;
1939 }
1940 }
1941 }
1942 }
1943
1944 private static void checkRange(float[] a, int m) {
1945 try {
1946 Arrays.sort(a, m + 1, m);
1947
1948 failed("Sort does not throw IllegalArgumentException " +
1949 " as expected: fromIndex = " + (m + 1) +
1950 " toIndex = " + m);
1951 }
1952 catch (IllegalArgumentException iae) {
1953 try {
1954 Arrays.sort(a, -m, a.length);
1955
1956 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1957 " as expected: fromIndex = " + (-m));
1958 }
1959 catch (ArrayIndexOutOfBoundsException aoe) {
1960 try {
1961 Arrays.sort(a, 0, a.length + m);
1962
1963 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1964 " as expected: toIndex = " + (a.length + m));
1965 }
1966 catch (ArrayIndexOutOfBoundsException aie) {
1967 return;
1968 }
1969 }
1970 }
1971 }
1972
1973 private static void checkRange(double[] a, int m) {
1974 try {
1975 Arrays.sort(a, m + 1, m);
1976
1977 failed("Sort does not throw IllegalArgumentException " +
1978 " as expected: fromIndex = " + (m + 1) +
1979 " toIndex = " + m);
1980 }
1981 catch (IllegalArgumentException iae) {
1982 try {
1983 Arrays.sort(a, -m, a.length);
1984
1985 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1986 " as expected: fromIndex = " + (-m));
1987 }
1988 catch (ArrayIndexOutOfBoundsException aoe) {
1989 try {
1990 Arrays.sort(a, 0, a.length + m);
1991
1992 failed("Sort does not throw ArrayIndexOutOfBoundsException " +
1993 " as expected: toIndex = " + (a.length + m));
1994 }
1995 catch (ArrayIndexOutOfBoundsException aie) {
1996 return;
1997 }
1998 }
1999 }
2000 }
2001
2002 private static void outArray(Object[] a) {
2003 for (int i = 0; i < a.length; i++) {
2004 out.print(a[i] + " ");
2005 }
2006 out.println();
2007 }
2008
2009 private static void outArray(int[] a) {
2010 for (int i = 0; i < a.length; i++) {
2011 out.print(a[i] + " ");
2012 }
|
1 /*
2 * Copyright (c) 2009, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /*
25 * @test
26 * @bug 6880672 6896573 6899694 6976036 7013585 7018258
27 * @build Sorting
28 * @run main Sorting -shortrun
29 * @summary Exercise Arrays.sort
30 *
31 * @author Vladimir Yaroslavskiy
32 * @author Jon Bentley
33 * @author Josh Bloch
34 */
35
36 import java.io.PrintStream;
37 import java.util.Arrays;
38 import java.util.Random;
39 import java.util.Comparator;
40
41 public class Sorting {
42
43 private static final PrintStream out = System.out;
44 private static final PrintStream err = System.err;
45
46 // Array lengths used in a long run (default)
47 private static final int[] LONG_RUN_LENGTHS = {
48 1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000 };
49
50 // Array lengths used in a short run
51 private static final int[] SHORT_RUN_LENGTHS = {
52 1, 2, 3, 21, 55, 1000, 10000, 12000 };
53
54 // Random initial values used in a long run (default)
55 private static final long[] LONG_RUN_RANDOMS = { 666, 0xC0FFEE, 999 };
56
57 // Random initial values used in a short run
58 private static final long[] SHORT_RUN_RANDOMS = { 666 };
59
60 // Constant values used in subarray sorting
61 private static final int A380 = 0xA380;
62 private static final int B747 = 0xB747;
63
64 public static void main(String[] args) {
65 boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
66 long start = System.currentTimeMillis();
67
68 if (shortRun) {
69 testAndCheck(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
70 } else {
71 testAndCheck(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
72 }
73 long end = System.currentTimeMillis();
74
75 out.format("PASSED in %d sec.\n", Math.round((end - start) / 1E3));
76 }
77
78 private static void testAndCheck(int[] lengths, long[] randoms) {
79 testEmptyAndNullIntArray();
80 testEmptyAndNullLongArray();
81 testEmptyAndNullShortArray();
82 testEmptyAndNullCharArray();
83 testEmptyAndNullByteArray();
84 testEmptyAndNullFloatArray();
85 testEmptyAndNullDoubleArray();
86
87 for (int length : lengths) {
88 testMergingSort(length);
89 testAndCheckRange(length);
90 testAndCheckSubArray(length);
91 }
92 for (long seed : randoms) {
93 for (int length : lengths) {
94 testAndCheckWithInsertionSort(length, new MyRandom(seed));
95 testAndCheckWithCheckSum(length, new MyRandom(seed));
96 testAndCheckWithScrambling(length, new MyRandom(seed));
97 testAndCheckFloat(length, new MyRandom(seed));
98 testAndCheckDouble(length, new MyRandom(seed));
99 testStable(length, new MyRandom(seed));
100 }
101 }
102 }
103
104 private static void testEmptyAndNullIntArray() {
105 ourDescription = "Check empty and null array";
106 Arrays.sort(new int[] {});
107 Arrays.sort(new int[] {}, 0, 0);
108
272 for (TypeConverter converter : TypeConverter.values()) {
273 out.println("Test 'range': " + converter +
274 ", length = " + length + ", m = " + m);
275 Object convertedGolden = converter.convert(golden);
276 checkRange(convertedGolden, m);
277 }
278 }
279 out.println();
280 }
281
282 private static void testStable(int length, MyRandom random) {
283 ourDescription = "Check if sorting is stable";
284 Pair[] a = build(length, random);
285
286 out.println("Test 'stable': " + "random = " + random.getSeed() +
287 ", length = " + length);
288 Arrays.sort(a);
289 checkSorted(a);
290 checkStable(a);
291 out.println();
292
293 a = build(length, random);
294
295 out.println("Test 'stable' comparator: " + "random = " + random.getSeed() +
296 ", length = " + length);
297 Arrays.sort(a, pairComparator);
298 checkSorted(a);
299 checkStable(a);
300 out.println();
301 }
302
303 private static void checkSorted(Pair[] a) {
304 for (int i = 0; i < a.length - 1; i++) {
305 if (a[i].getKey() > a[i + 1].getKey()) {
306 failedSort(i, "" + a[i].getKey(), "" + a[i + 1].getKey());
307 }
308 }
309 }
310
311 private static void checkStable(Pair[] a) {
312 for (int i = 0; i < a.length / 4; ) {
313 int key1 = a[i].getKey();
314 int value1 = a[i++].getValue();
315 int key2 = a[i].getKey();
316 int value2 = a[i++].getValue();
317 int key3 = a[i].getKey();
318 int value3 = a[i++].getValue();
319 int key4 = a[i].getKey();
320 int value4 = a[i++].getValue();
327 failed("Sorting is not stable at position " + i +
328 ". Second values have been changed: " + value1 + ", " +
329 value2 + ", " + value3 + ", " + value4);
330 }
331 }
332 }
333
334 private static Pair[] build(int length, Random random) {
335 Pair[] a = new Pair[length * 4];
336
337 for (int i = 0; i < a.length; ) {
338 int key = random.nextInt();
339 a[i++] = new Pair(key, 1);
340 a[i++] = new Pair(key, 2);
341 a[i++] = new Pair(key, 3);
342 a[i++] = new Pair(key, 4);
343 }
344 return a;
345 }
346
347 private static Comparator<Pair> pairComparator = new Comparator<Pair>() {
348 public int compare(Pair p1, Pair p2) {
349 return p1.compareTo(p2);
350 }
351 };
352
353 private static final class Pair implements Comparable<Pair> {
354 Pair(int key, int value) {
355 myKey = key;
356 myValue = value;
357 }
358
359 int getKey() {
360 return myKey;
361 }
362
363 int getValue() {
364 return myValue;
365 }
366
367 public int compareTo(Pair pair) {
368 if (myKey < pair.myKey) {
369 return -1;
370 }
371 if (myKey > pair.myKey) {
372 return 1;
395 for (UnsortedBuilder builder : UnsortedBuilder.values()) {
396 builder.build(golden, m, random);
397 int[] test = golden.clone();
398
399 for (TypeConverter converter : TypeConverter.values()) {
400 out.println("Test 'insertion sort': " + converter +
401 " " + builder + "random = " + random.getSeed() +
402 ", length = " + length + ", m = " + m);
403 Object convertedGolden = converter.convert(golden);
404 Object convertedTest1 = converter.convert(test);
405 Object convertedTest2 = converter.convert(test);
406 sort(convertedTest1);
407 sortByInsertionSort(convertedTest2);
408 compare(convertedTest1, convertedTest2);
409 }
410 }
411 }
412 out.println();
413 }
414
415 private static void testMergingSort(int length) {
416 if (length < 1000) {
417 return;
418 }
419 ourDescription = "Check merging sort";
420 int[] golden = new int[length];
421 final int period = 50;
422
423 for (int m = period - 2; m <= period + 2; m++) {
424 for (MergingBuilder builder : MergingBuilder.values()) {
425 builder.build(golden, m);
426 int[] test = golden.clone();
427
428 for (TypeConverter converter : TypeConverter.values()) {
429 out.println("Test 'merging sort': " + converter + " " +
430 builder + "length = " + length + ", m = " + m);
431 Object convertedGolden = converter.convert(golden);
432 sort(convertedGolden);
433 checkSorted(convertedGolden);
434 }
435 }
436 }
437 out.println();
438 }
439
440 private static void testAndCheckWithCheckSum(int length, MyRandom random) {
441 ourDescription = "Check sorting with check sum";
442 int[] golden = new int[length];
443
444 for (int m = 1; m < 2 * length; m *= 2) {
445 for (UnsortedBuilder builder : UnsortedBuilder.values()) {
446 builder.build(golden, m, random);
447 int[] test = golden.clone();
448
449 for (TypeConverter converter : TypeConverter.values()) {
473 int[] test = golden.clone();
474 scramble(test, random);
475
476 for (TypeConverter converter : TypeConverter.values()) {
477 out.println("Test 'scrambling': " + converter +
478 " " + builder + "random = " + random.getSeed() +
479 ", length = " + length + ", m = " + m);
480 Object convertedGolden = converter.convert(golden);
481 Object convertedTest = converter.convert(test);
482 sort(convertedTest);
483 compare(convertedTest, convertedGolden);
484 }
485 }
486 }
487 out.println();
488 }
489
490 private static void testAndCheckFloat(int length, MyRandom random) {
491 ourDescription = "Check float sorting";
492 float[] golden = new float[length];
493 boolean newLine = false;
494 final int MAX = 12;
495
496 for (int a = 0; a <= MAX; a++) {
497 for (int g = 0; g <= MAX; g++) {
498 for (int z = 0; z <= MAX; z++) {
499 for (int n = 0; n <= MAX; n++) {
500 for (int p = 0; p <= MAX; p++) {
501 if (a + g + z + n + p != length) {
502 continue;
503 }
504 for (FloatBuilder builder : FloatBuilder.values()) {
505 out.println("Test 'float': random = " + random.getSeed() +
506 ", length = " + length + ", a = " + a + ", g = " +
507 g + ", z = " + z + ", n = " + n + ", p = " + p);
508 builder.build(golden, a, g, z, n, p, random);
509 float[] test = golden.clone();
510 scramble(test, random);
511 sort(test);
512 compare(test, golden, a, n, g);
513 }
514 newLine = true;
515 }
516 }
517 }
518 }
519 }
520 if (newLine) {
521 out.println();
545 g + ", z = " + z + ", n = " + n + ", p = " + p);
546 builder.build(golden, a, g, z, n, p, random);
547 double[] test = golden.clone();
548 scramble(test, random);
549 sort(test);
550 compare(test, golden, a, n, g);
551 }
552 newLine = true;
553 }
554 }
555 }
556 }
557 }
558 if (newLine) {
559 out.println();
560 }
561 }
562
563 private static void prepareSubArray(int[] a, int fromIndex, int toIndex, int m) {
564 for (int i = 0; i < fromIndex; i++) {
565 a[i] = A380;
566 }
567 int middle = (fromIndex + toIndex) >>> 1;
568 int k = 0;
569
570 for (int i = fromIndex; i < middle; i++) {
571 a[i] = k++;
572 }
573 for (int i = middle; i < toIndex; i++) {
574 a[i] = k--;
575 }
576 for (int i = toIndex; i < a.length; i++) {
577 a[i] = B747;
578 }
579 }
580
581 private static void scramble(int[] a, Random random) {
582 for (int i = 0; i < a.length * 7; i++) {
583 swap(a, random.nextInt(a.length), random.nextInt(a.length));
584 }
585 }
586
587 private static void scramble(float[] a, Random random) {
588 for (int i = 0; i < a.length * 7; i++) {
589 swap(a, random.nextInt(a.length), random.nextInt(a.length));
590 }
591 }
592
593 private static void scramble(double[] a, Random random) {
594 for (int i = 0; i < a.length * 7; i++) {
595 swap(a, random.nextInt(a.length), random.nextInt(a.length));
596 }
597 }
668 b[i] = (float) a[i];
669 }
670 return b;
671 }
672 },
673 DOUBLE {
674 Object convert(int[] a) {
675 double[] b = new double[a.length];
676
677 for (int i = 0; i < a.length; i++) {
678 b[i] = (double) a[i];
679 }
680 return b;
681 }
682 },
683 INTEGER {
684 Object convert(int[] a) {
685 Integer[] b = new Integer[a.length];
686
687 for (int i = 0; i < a.length; i++) {
688 b[i] = Integer.valueOf(a[i]);
689 }
690 return b;
691 }
692 };
693
694 abstract Object convert(int[] a);
695
696 @Override
697 public String toString() {
698 String name = name();
699
700 for (int i = name.length(); i < 9; i++) {
701 name += " ";
702 }
703 return name;
704 }
705 }
706
707 private static enum FloatBuilder {
708 SIMPLE {
709 void build(float[] x, int a, int g, int z, int n, int p, Random random) {
710 int fromIndex = 0;
711 float negativeValue = -random.nextFloat();
712 float positiveValue = random.nextFloat();
713
714 writeValue(x, negativeValue, fromIndex, n);
715 fromIndex += n;
716
717 writeValue(x, -0.0f, fromIndex, g);
830 }
831 },
832 ORGAN_PIPES {
833 void build(int[] a, int m) {
834 int i = 0;
835 int k = m;
836
837 while (true) {
838 for (int t = 1; t <= m; t++) {
839 if (i >= a.length) {
840 return;
841 }
842 a[i++] = k;
843 }
844 }
845 }
846 };
847
848 abstract void build(int[] a, int m);
849
850 @Override
851 public String toString() {
852 String name = name();
853
854 for (int i = name.length(); i < 12; i++) {
855 name += " ";
856 }
857 return name;
858 }
859 }
860
861 private static enum MergingBuilder {
862 ASCENDING {
863 void build(int[] a, int m) {
864 int period = a.length / m;
865 int v = 1, i = 0;
866
867 for (int k = 0; k < m; k++) {
868 v = 1;
869 for (int p = 0; p < period; p++) {
870 a[i++] = v++;
871 }
872 }
873 for (int j = i; j < a.length - 1; j++) {
874 a[j] = v++;
875 }
876 a[a.length - 1] = 0;
877 }
878 },
879 DESCENDING {
880 void build(int[] a, int m) {
881 int period = a.length / m;
882 int v = -1, i = 0;
883
884 for (int k = 0; k < m; k++) {
885 v = -1;
886 for (int p = 0; p < period; p++) {
887 a[i++] = v--;
888 }
889 }
890 for (int j = i; j < a.length - 1; j++) {
891 a[j] = v--;
892 }
893 a[a.length - 1] = 0;
894 }
895 },
896 POINT {
897 void build(int[] a, int m) {
898 for (int i = 0; i < a.length; i++) {
899 a[i] = 0;
900 }
901 a[a.length / 2] = m;
902 }
903 },
904 LINE {
905 void build(int[] a, int m) {
906 for (int i = 0; i < a.length; i++) {
907 a[i] = i;
908 }
909 reverse(a, 0, a.length - 1);
910 }
911 },
912 PEARL {
913 void build(int[] a, int m) {
914 for (int i = 0; i < a.length; i++) {
915 a[i] = i;
916 }
917 reverse(a, 0, 2);
918 }
919 },
920 RING {
921 void build(int[] a, int m) {
922 int k1 = a.length / 3;
923 int k2 = a.length / 3 * 2;
924 int level = a.length / 3;
925
926 for (int i = 0, k = level; i < k1; i++) {
927 a[i] = k--;
928 }
929 for (int i = k1; i < k2; i++) {
930 a[i] = 0;
931 }
932 for (int i = k2, k = level; i < a.length; i++) {
933 a[i] = k--;
934 }
935 }
936 };
937
938 abstract void build(int[] a, int m);
939
940 @Override
941 public String toString() {
942 String name = name();
943
944 for (int i = name.length(); i < 12; i++) {
945 name += " ";
946 }
947 return name;
948 }
949 }
950
951 private static void reverse(int[] a, int lo, int hi) {
952 for (--hi; lo < hi; ) {
953 int tmp = a[lo];
954 a[lo++] = a[hi];
955 a[hi--] = tmp;
956 }
957 }
958
959 private static enum UnsortedBuilder {
960 RANDOM {
961 void build(int[] a, int m, Random random) {
962 for (int i = 0; i < a.length; i++) {
963 a[i] = random.nextInt();
964 }
965 }
966 },
967 ASCENDING {
968 void build(int[] a, int m, Random random) {
969 for (int i = 0; i < a.length; i++) {
970 a[i] = m + i;
971 }
972 }
973 },
974 DESCENDING {
975 void build(int[] a, int m, Random random) {
976 for (int i = 0; i < a.length; i++) {
977 a[i] = a.length - m - i;
978 }
1045 }
1046 },
1047 PLATEAU {
1048 void build(int[] a, int m, Random random) {
1049 for (int i = 0; i < a.length; i++) {
1050 a[i] = Math.min(i, m);
1051 }
1052 }
1053 },
1054 SHUFFLE {
1055 void build(int[] a, int m, Random random) {
1056 int x = 0, y = 0;
1057 for (int i = 0; i < a.length; i++) {
1058 a[i] = random.nextBoolean() ? (x += 2) : (y += 2);
1059 }
1060 }
1061 };
1062
1063 abstract void build(int[] a, int m, Random random);
1064
1065 @Override
1066 public String toString() {
1067 String name = name();
1068
1069 for (int i = name.length(); i < 12; i++) {
1070 name += " ";
1071 }
1072 return name;
1073 }
1074 }
1075
1076 private static void checkWithCheckSum(Object test, Object golden) {
1077 checkSorted(test);
1078 checkCheckSum(test, golden);
1079 }
1080
1081 private static void failed(String message) {
1082 err.format("\n*** TEST FAILED - %s.\n\n%s.\n\n", ourDescription, message);
1083 throw new RuntimeException("Test failed - see log file for details");
1084 }
1085
1086 private static void failedSort(int index, String value1, String value2) {
1093 }
1094
1095 private static void compare(Object test, Object golden) {
1096 if (test instanceof int[]) {
1097 compare((int[]) test, (int[]) golden);
1098 } else if (test instanceof long[]) {
1099 compare((long[]) test, (long[]) golden);
1100 } else if (test instanceof short[]) {
1101 compare((short[]) test, (short[]) golden);
1102 } else if (test instanceof byte[]) {
1103 compare((byte[]) test, (byte[]) golden);
1104 } else if (test instanceof char[]) {
1105 compare((char[]) test, (char[]) golden);
1106 } else if (test instanceof float[]) {
1107 compare((float[]) test, (float[]) golden);
1108 } else if (test instanceof double[]) {
1109 compare((double[]) test, (double[]) golden);
1110 } else if (test instanceof Integer[]) {
1111 compare((Integer[]) test, (Integer[]) golden);
1112 } else {
1113 failed("Unknown type of array: " + test + " of class " +
1114 test.getClass().getName());
1115 }
1116 }
1117
1118 private static void compare(int[] a, int[] b) {
1119 for (int i = 0; i < a.length; i++) {
1120 if (a[i] != b[i]) {
1121 failedCompare(i, "" + a[i], "" + b[i]);
1122 }
1123 }
1124 }
1125
1126 private static void compare(long[] a, long[] b) {
1127 for (int i = 0; i < a.length; i++) {
1128 if (a[i] != b[i]) {
1129 failedCompare(i, "" + a[i], "" + b[i]);
1130 }
1131 }
1132 }
1133
1180 }
1181
1182 private static void checkSorted(Object object) {
1183 if (object instanceof int[]) {
1184 checkSorted((int[]) object);
1185 } else if (object instanceof long[]) {
1186 checkSorted((long[]) object);
1187 } else if (object instanceof short[]) {
1188 checkSorted((short[]) object);
1189 } else if (object instanceof byte[]) {
1190 checkSorted((byte[]) object);
1191 } else if (object instanceof char[]) {
1192 checkSorted((char[]) object);
1193 } else if (object instanceof float[]) {
1194 checkSorted((float[]) object);
1195 } else if (object instanceof double[]) {
1196 checkSorted((double[]) object);
1197 } else if (object instanceof Integer[]) {
1198 checkSorted((Integer[]) object);
1199 } else {
1200 failed("Unknown type of array: " + object + " of class " +
1201 object.getClass().getName());
1202 }
1203 }
1204
1205 private static void checkSorted(int[] a) {
1206 for (int i = 0; i < a.length - 1; i++) {
1207 if (a[i] > a[i + 1]) {
1208 failedSort(i, "" + a[i], "" + a[i + 1]);
1209 }
1210 }
1211 }
1212
1213 private static void checkSorted(long[] a) {
1214 for (int i = 0; i < a.length - 1; i++) {
1215 if (a[i] > a[i + 1]) {
1216 failedSort(i, "" + a[i], "" + a[i + 1]);
1217 }
1218 }
1219 }
1220
1276 }
1277
1278 private static int checkSumXor(Object object) {
1279 if (object instanceof int[]) {
1280 return checkSumXor((int[]) object);
1281 } else if (object instanceof long[]) {
1282 return checkSumXor((long[]) object);
1283 } else if (object instanceof short[]) {
1284 return checkSumXor((short[]) object);
1285 } else if (object instanceof byte[]) {
1286 return checkSumXor((byte[]) object);
1287 } else if (object instanceof char[]) {
1288 return checkSumXor((char[]) object);
1289 } else if (object instanceof float[]) {
1290 return checkSumXor((float[]) object);
1291 } else if (object instanceof double[]) {
1292 return checkSumXor((double[]) object);
1293 } else if (object instanceof Integer[]) {
1294 return checkSumXor((Integer[]) object);
1295 } else {
1296 failed("Unknown type of array: " + object + " of class " +
1297 object.getClass().getName());
1298 return -1;
1299 }
1300 }
1301
1302 private static int checkSumXor(Integer[] a) {
1303 int checkSum = 0;
1304
1305 for (Integer e : a) {
1306 checkSum ^= e.intValue();
1307 }
1308 return checkSum;
1309 }
1310
1311 private static int checkSumXor(int[] a) {
1312 int checkSum = 0;
1313
1314 for (int e : a) {
1315 checkSum ^= e;
1316 }
1372 }
1373
1374 private static int checkSumPlus(Object object) {
1375 if (object instanceof int[]) {
1376 return checkSumPlus((int[]) object);
1377 } else if (object instanceof long[]) {
1378 return checkSumPlus((long[]) object);
1379 } else if (object instanceof short[]) {
1380 return checkSumPlus((short[]) object);
1381 } else if (object instanceof byte[]) {
1382 return checkSumPlus((byte[]) object);
1383 } else if (object instanceof char[]) {
1384 return checkSumPlus((char[]) object);
1385 } else if (object instanceof float[]) {
1386 return checkSumPlus((float[]) object);
1387 } else if (object instanceof double[]) {
1388 return checkSumPlus((double[]) object);
1389 } else if (object instanceof Integer[]) {
1390 return checkSumPlus((Integer[]) object);
1391 } else {
1392 failed("Unknown type of array: " + object + " of class " +
1393 object.getClass().getName());
1394 return -1;
1395 }
1396 }
1397
1398 private static int checkSumPlus(int[] a) {
1399 int checkSum = 0;
1400
1401 for (int e : a) {
1402 checkSum += e;
1403 }
1404 return checkSum;
1405 }
1406
1407 private static int checkSumPlus(long[] a) {
1408 long checkSum = 0;
1409
1410 for (long e : a) {
1411 checkSum += e;
1412 }
1468 }
1469
1470 private static void sortByInsertionSort(Object object) {
1471 if (object instanceof int[]) {
1472 sortByInsertionSort((int[]) object);
1473 } else if (object instanceof long[]) {
1474 sortByInsertionSort((long[]) object);
1475 } else if (object instanceof short[]) {
1476 sortByInsertionSort((short[]) object);
1477 } else if (object instanceof byte[]) {
1478 sortByInsertionSort((byte[]) object);
1479 } else if (object instanceof char[]) {
1480 sortByInsertionSort((char[]) object);
1481 } else if (object instanceof float[]) {
1482 sortByInsertionSort((float[]) object);
1483 } else if (object instanceof double[]) {
1484 sortByInsertionSort((double[]) object);
1485 } else if (object instanceof Integer[]) {
1486 sortByInsertionSort((Integer[]) object);
1487 } else {
1488 failed("Unknown type of array: " + object + " of class " +
1489 object.getClass().getName());
1490 }
1491 }
1492
1493 private static void sortByInsertionSort(int[] a) {
1494 for (int j, i = 1; i < a.length; i++) {
1495 int ai = a[i];
1496 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1497 a[j + 1] = a[j];
1498 }
1499 a[j + 1] = ai;
1500 }
1501 }
1502
1503 private static void sortByInsertionSort(long[] a) {
1504 for (int j, i = 1; i < a.length; i++) {
1505 long ai = a[i];
1506 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1507 a[j + 1] = a[j];
1508 }
1571 }
1572
1573 private static void sort(Object object) {
1574 if (object instanceof int[]) {
1575 Arrays.sort((int[]) object);
1576 } else if (object instanceof long[]) {
1577 Arrays.sort((long[]) object);
1578 } else if (object instanceof short[]) {
1579 Arrays.sort((short[]) object);
1580 } else if (object instanceof byte[]) {
1581 Arrays.sort((byte[]) object);
1582 } else if (object instanceof char[]) {
1583 Arrays.sort((char[]) object);
1584 } else if (object instanceof float[]) {
1585 Arrays.sort((float[]) object);
1586 } else if (object instanceof double[]) {
1587 Arrays.sort((double[]) object);
1588 } else if (object instanceof Integer[]) {
1589 Arrays.sort((Integer[]) object);
1590 } else {
1591 failed("Unknown type of array: " + object + " of class " +
1592 object.getClass().getName());
1593 }
1594 }
1595
1596 private static void sortSubArray(Object object, int fromIndex, int toIndex) {
1597 if (object instanceof int[]) {
1598 Arrays.sort((int[]) object, fromIndex, toIndex);
1599 } else if (object instanceof long[]) {
1600 Arrays.sort((long[]) object, fromIndex, toIndex);
1601 } else if (object instanceof short[]) {
1602 Arrays.sort((short[]) object, fromIndex, toIndex);
1603 } else if (object instanceof byte[]) {
1604 Arrays.sort((byte[]) object, fromIndex, toIndex);
1605 } else if (object instanceof char[]) {
1606 Arrays.sort((char[]) object, fromIndex, toIndex);
1607 } else if (object instanceof float[]) {
1608 Arrays.sort((float[]) object, fromIndex, toIndex);
1609 } else if (object instanceof double[]) {
1610 Arrays.sort((double[]) object, fromIndex, toIndex);
1611 } else if (object instanceof Integer[]) {
1612 Arrays.sort((Integer[]) object, fromIndex, toIndex);
1613 } else {
1614 failed("Unknown type of array: " + object + " of class " +
1615 object.getClass().getName());
1616 }
1617 }
1618
1619 private static void checkSubArray(Object object, int fromIndex, int toIndex, int m) {
1620 if (object instanceof int[]) {
1621 checkSubArray((int[]) object, fromIndex, toIndex, m);
1622 } else if (object instanceof long[]) {
1623 checkSubArray((long[]) object, fromIndex, toIndex, m);
1624 } else if (object instanceof short[]) {
1625 checkSubArray((short[]) object, fromIndex, toIndex, m);
1626 } else if (object instanceof byte[]) {
1627 checkSubArray((byte[]) object, fromIndex, toIndex, m);
1628 } else if (object instanceof char[]) {
1629 checkSubArray((char[]) object, fromIndex, toIndex, m);
1630 } else if (object instanceof float[]) {
1631 checkSubArray((float[]) object, fromIndex, toIndex, m);
1632 } else if (object instanceof double[]) {
1633 checkSubArray((double[]) object, fromIndex, toIndex, m);
1634 } else if (object instanceof Integer[]) {
1635 checkSubArray((Integer[]) object, fromIndex, toIndex, m);
1636 } else {
1637 failed("Unknown type of array: " + object + " of class " +
1638 object.getClass().getName());
1639 }
1640 }
1641
1642 private static void checkSubArray(Integer[] a, int fromIndex, int toIndex, int m) {
1643 for (int i = 0; i < fromIndex; i++) {
1644 if (a[i].intValue() != A380) {
1645 failed("Range sort changes left element on position " + i +
1646 ": " + a[i] + ", must be " + A380);
1647 }
1648 }
1649
1650 for (int i = fromIndex; i < toIndex - 1; i++) {
1651 if (a[i].intValue() > a[i + 1].intValue()) {
1652 failedSort(i, "" + a[i], "" + a[i + 1]);
1653 }
1654 }
1655
1656 for (int i = toIndex; i < a.length; i++) {
1657 if (a[i].intValue() != B747) {
1658 failed("Range sort changes right element on position " + i +
1659 ": " + a[i] + ", must be " + B747);
1660 }
1661 }
1662 }
1663
1664 private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) {
1665 for (int i = 0; i < fromIndex; i++) {
1666 if (a[i] != A380) {
1667 failed("Range sort changes left element on position " + i +
1668 ": " + a[i] + ", must be " + A380);
1669 }
1670 }
1671
1672 for (int i = fromIndex; i < toIndex - 1; i++) {
1673 if (a[i] > a[i + 1]) {
1674 failedSort(i, "" + a[i], "" + a[i + 1]);
1675 }
1676 }
1677
1678 for (int i = toIndex; i < a.length; i++) {
1679 if (a[i] != B747) {
1680 failed("Range sort changes right element on position " + i +
1681 ": " + a[i] + ", must be " + B747);
1682 }
1683 }
1684 }
1685
1686 private static void checkSubArray(byte[] a, int fromIndex, int toIndex, int m) {
1687 for (int i = 0; i < fromIndex; i++) {
1688 if (a[i] != (byte) A380) {
1689 failed("Range sort changes left element on position " + i +
1690 ": " + a[i] + ", must be " + A380);
1691 }
1692 }
1693
1694 for (int i = fromIndex; i < toIndex - 1; i++) {
1695 if (a[i] > a[i + 1]) {
1696 failedSort(i, "" + a[i], "" + a[i + 1]);
1697 }
1698 }
1699
1700 for (int i = toIndex; i < a.length; i++) {
1701 if (a[i] != (byte) B747) {
1702 failed("Range sort changes right element on position " + i +
1703 ": " + a[i] + ", must be " + B747);
1704 }
1705 }
1706 }
1707
1708 private static void checkSubArray(long[] a, int fromIndex, int toIndex, int m) {
1709 for (int i = 0; i < fromIndex; i++) {
1710 if (a[i] != (long) A380) {
1711 failed("Range sort changes left element on position " + i +
1712 ": " + a[i] + ", must be " + A380);
1713 }
1714 }
1715
1716 for (int i = fromIndex; i < toIndex - 1; i++) {
1717 if (a[i] > a[i + 1]) {
1718 failedSort(i, "" + a[i], "" + a[i + 1]);
1719 }
1720 }
1721
1722 for (int i = toIndex; i < a.length; i++) {
1723 if (a[i] != (long) B747) {
1724 failed("Range sort changes right element on position " + i +
1725 ": " + a[i] + ", must be " + B747);
1726 }
1727 }
1728 }
1729
1730 private static void checkSubArray(char[] a, int fromIndex, int toIndex, int m) {
1731 for (int i = 0; i < fromIndex; i++) {
1732 if (a[i] != (char) A380) {
1733 failed("Range sort changes left element on position " + i +
1734 ": " + a[i] + ", must be " + A380);
1735 }
1736 }
1737
1738 for (int i = fromIndex; i < toIndex - 1; i++) {
1739 if (a[i] > a[i + 1]) {
1740 failedSort(i, "" + a[i], "" + a[i + 1]);
1741 }
1742 }
1743
1744 for (int i = toIndex; i < a.length; i++) {
1745 if (a[i] != (char) B747) {
1746 failed("Range sort changes right element on position " + i +
1747 ": " + a[i] + ", must be " + B747);
1748 }
1749 }
1750 }
1751
1752 private static void checkSubArray(short[] a, int fromIndex, int toIndex, int m) {
1753 for (int i = 0; i < fromIndex; i++) {
1754 if (a[i] != (short) A380) {
1755 failed("Range sort changes left element on position " + i +
1756 ": " + a[i] + ", must be " + A380);
1757 }
1758 }
1759
1760 for (int i = fromIndex; i < toIndex - 1; i++) {
1761 if (a[i] > a[i + 1]) {
1762 failedSort(i, "" + a[i], "" + a[i + 1]);
1763 }
1764 }
1765
1766 for (int i = toIndex; i < a.length; i++) {
1767 if (a[i] != (short) B747) {
1768 failed("Range sort changes right element on position " + i +
1769 ": " + a[i] + ", must be " + B747);
1770 }
1771 }
1772 }
1773
1774 private static void checkSubArray(float[] a, int fromIndex, int toIndex, int m) {
1775 for (int i = 0; i < fromIndex; i++) {
1776 if (a[i] != (float) A380) {
1777 failed("Range sort changes left element on position " + i +
1778 ": " + a[i] + ", must be " + A380);
1779 }
1780 }
1781
1782 for (int i = fromIndex; i < toIndex - 1; i++) {
1783 if (a[i] > a[i + 1]) {
1784 failedSort(i, "" + a[i], "" + a[i + 1]);
1785 }
1786 }
1787
1788 for (int i = toIndex; i < a.length; i++) {
1789 if (a[i] != (float) B747) {
1790 failed("Range sort changes right element on position " + i +
1791 ": " + a[i] + ", must be " + B747);
1792 }
1793 }
1794 }
1795
1796 private static void checkSubArray(double[] a, int fromIndex, int toIndex, int m) {
1797 for (int i = 0; i < fromIndex; i++) {
1798 if (a[i] != (double) A380) {
1799 failed("Range sort changes left element on position " + i +
1800 ": " + a[i] + ", must be " + A380);
1801 }
1802 }
1803
1804 for (int i = fromIndex; i < toIndex - 1; i++) {
1805 if (a[i] > a[i + 1]) {
1806 failedSort(i, "" + a[i], "" + a[i + 1]);
1807 }
1808 }
1809
1810 for (int i = toIndex; i < a.length; i++) {
1811 if (a[i] != (double) B747) {
1812 failed("Range sort changes right element on position " + i +
1813 ": " + a[i] + ", must be " + B747);
1814 }
1815 }
1816 }
1817
1818 private static void checkRange(Object object, int m) {
1819 if (object instanceof int[]) {
1820 checkRange((int[]) object, m);
1821 } else if (object instanceof long[]) {
1822 checkRange((long[]) object, m);
1823 } else if (object instanceof short[]) {
1824 checkRange((short[]) object, m);
1825 } else if (object instanceof byte[]) {
1826 checkRange((byte[]) object, m);
1827 } else if (object instanceof char[]) {
1828 checkRange((char[]) object, m);
1829 } else if (object instanceof float[]) {
1830 checkRange((float[]) object, m);
1831 } else if (object instanceof double[]) {
1832 checkRange((double[]) object, m);
1833 } else if (object instanceof Integer[]) {
1834 checkRange((Integer[]) object, m);
1835 } else {
1836 failed("Unknown type of array: " + object + " of class " +
1837 object.getClass().getName());
1838 }
1839 }
1840
1841 private static void checkRange(Integer[] a, int m) {
1842 try {
1843 Arrays.sort(a, m + 1, m);
1844
1845 failed("Arrays.sort does not throw IllegalArgumentException " +
1846 " as expected: fromIndex = " + (m + 1) +
1847 " toIndex = " + m);
1848 }
1849 catch (IllegalArgumentException iae) {
1850 try {
1851 Arrays.sort(a, -m, a.length);
1852
1853 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
1854 " as expected: fromIndex = " + (-m));
1855 }
1856 catch (ArrayIndexOutOfBoundsException aoe) {
1857 try {
1858 Arrays.sort(a, 0, a.length + m);
1859
1860 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
1861 " as expected: toIndex = " + (a.length + m));
1862 }
1863 catch (ArrayIndexOutOfBoundsException aie) {
1864 return;
1865 }
1866 }
1867 }
1868 }
1869
1870 private static void checkRange(int[] a, int m) {
1871 try {
1872 Arrays.sort(a, m + 1, m);
1873
1874 failed("Arrays.sort does not throw IllegalArgumentException " +
1875 " as expected: fromIndex = " + (m + 1) +
1876 " toIndex = " + m);
1877 }
1878 catch (IllegalArgumentException iae) {
1879 try {
1880 Arrays.sort(a, -m, a.length);
1881
1882 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
1883 " as expected: fromIndex = " + (-m));
1884 }
1885 catch (ArrayIndexOutOfBoundsException aoe) {
1886 try {
1887 Arrays.sort(a, 0, a.length + m);
1888
1889 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
1890 " as expected: toIndex = " + (a.length + m));
1891 }
1892 catch (ArrayIndexOutOfBoundsException aie) {
1893 return;
1894 }
1895 }
1896 }
1897 }
1898
1899 private static void checkRange(long[] a, int m) {
1900 try {
1901 Arrays.sort(a, m + 1, m);
1902
1903 failed("Arrays.sort does not throw IllegalArgumentException " +
1904 " as expected: fromIndex = " + (m + 1) +
1905 " toIndex = " + m);
1906 }
1907 catch (IllegalArgumentException iae) {
1908 try {
1909 Arrays.sort(a, -m, a.length);
1910
1911 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
1912 " as expected: fromIndex = " + (-m));
1913 }
1914 catch (ArrayIndexOutOfBoundsException aoe) {
1915 try {
1916 Arrays.sort(a, 0, a.length + m);
1917
1918 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
1919 " as expected: toIndex = " + (a.length + m));
1920 }
1921 catch (ArrayIndexOutOfBoundsException aie) {
1922 return;
1923 }
1924 }
1925 }
1926 }
1927
1928 private static void checkRange(byte[] a, int m) {
1929 try {
1930 Arrays.sort(a, m + 1, m);
1931
1932 failed("Arrays.sort does not throw IllegalArgumentException " +
1933 " as expected: fromIndex = " + (m + 1) +
1934 " toIndex = " + m);
1935 }
1936 catch (IllegalArgumentException iae) {
1937 try {
1938 Arrays.sort(a, -m, a.length);
1939
1940 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
1941 " as expected: fromIndex = " + (-m));
1942 }
1943 catch (ArrayIndexOutOfBoundsException aoe) {
1944 try {
1945 Arrays.sort(a, 0, a.length + m);
1946
1947 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
1948 " as expected: toIndex = " + (a.length + m));
1949 }
1950 catch (ArrayIndexOutOfBoundsException aie) {
1951 return;
1952 }
1953 }
1954 }
1955 }
1956
1957 private static void checkRange(short[] a, int m) {
1958 try {
1959 Arrays.sort(a, m + 1, m);
1960
1961 failed("Arrays.sort does not throw IllegalArgumentException " +
1962 " as expected: fromIndex = " + (m + 1) +
1963 " toIndex = " + m);
1964 }
1965 catch (IllegalArgumentException iae) {
1966 try {
1967 Arrays.sort(a, -m, a.length);
1968
1969 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
1970 " as expected: fromIndex = " + (-m));
1971 }
1972 catch (ArrayIndexOutOfBoundsException aoe) {
1973 try {
1974 Arrays.sort(a, 0, a.length + m);
1975
1976 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
1977 " as expected: toIndex = " + (a.length + m));
1978 }
1979 catch (ArrayIndexOutOfBoundsException aie) {
1980 return;
1981 }
1982 }
1983 }
1984 }
1985
1986 private static void checkRange(char[] a, int m) {
1987 try {
1988 Arrays.sort(a, m + 1, m);
1989
1990 failed("Arrays.sort does not throw IllegalArgumentException " +
1991 " as expected: fromIndex = " + (m + 1) +
1992 " toIndex = " + m);
1993 }
1994 catch (IllegalArgumentException iae) {
1995 try {
1996 Arrays.sort(a, -m, a.length);
1997
1998 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
1999 " as expected: fromIndex = " + (-m));
2000 }
2001 catch (ArrayIndexOutOfBoundsException aoe) {
2002 try {
2003 Arrays.sort(a, 0, a.length + m);
2004
2005 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
2006 " as expected: toIndex = " + (a.length + m));
2007 }
2008 catch (ArrayIndexOutOfBoundsException aie) {
2009 return;
2010 }
2011 }
2012 }
2013 }
2014
2015 private static void checkRange(float[] a, int m) {
2016 try {
2017 Arrays.sort(a, m + 1, m);
2018
2019 failed("Arrays.sort does not throw IllegalArgumentException " +
2020 " as expected: fromIndex = " + (m + 1) +
2021 " toIndex = " + m);
2022 }
2023 catch (IllegalArgumentException iae) {
2024 try {
2025 Arrays.sort(a, -m, a.length);
2026
2027 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
2028 " as expected: fromIndex = " + (-m));
2029 }
2030 catch (ArrayIndexOutOfBoundsException aoe) {
2031 try {
2032 Arrays.sort(a, 0, a.length + m);
2033
2034 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
2035 " as expected: toIndex = " + (a.length + m));
2036 }
2037 catch (ArrayIndexOutOfBoundsException aie) {
2038 return;
2039 }
2040 }
2041 }
2042 }
2043
2044 private static void checkRange(double[] a, int m) {
2045 try {
2046 Arrays.sort(a, m + 1, m);
2047
2048 failed("Arrays.sort does not throw IllegalArgumentException " +
2049 " as expected: fromIndex = " + (m + 1) +
2050 " toIndex = " + m);
2051 }
2052 catch (IllegalArgumentException iae) {
2053 try {
2054 Arrays.sort(a, -m, a.length);
2055
2056 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
2057 " as expected: fromIndex = " + (-m));
2058 }
2059 catch (ArrayIndexOutOfBoundsException aoe) {
2060 try {
2061 Arrays.sort(a, 0, a.length + m);
2062
2063 failed("Arrays.sort does not throw ArrayIndexOutOfBoundsException " +
2064 " as expected: toIndex = " + (a.length + m));
2065 }
2066 catch (ArrayIndexOutOfBoundsException aie) {
2067 return;
2068 }
2069 }
2070 }
2071 }
2072
2073 private static void outArray(Object[] a) {
2074 for (int i = 0; i < a.length; i++) {
2075 out.print(a[i] + " ");
2076 }
2077 out.println();
2078 }
2079
2080 private static void outArray(int[] a) {
2081 for (int i = 0; i < a.length; i++) {
2082 out.print(a[i] + " ");
2083 }
|