1 /*
2 * Copyright (c) 2011, 2013, 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 /* Adapted from test/java/util/Arrays/Sorting.java
25 *
26 * Where that test checks Arrays.sort against manual quicksort routines,
27 * this test checks parallelSort against either Arrays.sort or manual
28 * quicksort routines.
29 */
30
31 /*
32 * @test
33 * @bug 8003981
34 * @run main ParallelSorting -shortrun
35 * @summary Exercise Arrays.parallelSort (adapted from test Sorting)
36 *
37 * @author Vladimir Yaroslavskiy
38 * @author Jon Bentley
39 * @author Josh Bloch
40 */
41
42 import java.util.Arrays;
43 import java.util.Random;
44 import java.io.PrintStream;
45 import java.util.Comparator;
46
47 public class ParallelSorting {
48 private static final PrintStream out = System.out;
49 private static final PrintStream err = System.err;
50
51 // Array lengths used in a long run (default)
52 private static final int[] LONG_RUN_LENGTHS = {
53 1000, 10000, 100000, 1000000 };
54
55 // Array lengths used in a short run
56 private static final int[] SHORT_RUN_LENGTHS = {
57 5000, 9000, 10000, 12000 };
58
59 // Random initial values used in a long run (default)
60 private static final long[] LONG_RUN_RANDOMS = { 666, 0xC0FFEE, 999 };
61
62 // Random initial values used in a short run
63 private static final long[] SHORT_RUN_RANDOMS = { 666 };
64
65 public static void main(String[] args) {
66 boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
67 long start = System.currentTimeMillis();
68
69 if (shortRun) {
70 testAndCheck(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
71 } else {
72 testAndCheck(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
73 }
74 long end = System.currentTimeMillis();
75
76 out.format("PASSED in %d sec.\n", Math.round((end - start) / 1E3));
77 }
78
79 private static void testAndCheck(int[] lengths, long[] randoms) {
80 testEmptyAndNullIntArray();
81 testEmptyAndNullLongArray();
82 testEmptyAndNullShortArray();
83 testEmptyAndNullCharArray();
84 testEmptyAndNullByteArray();
85 testEmptyAndNullFloatArray();
86 testEmptyAndNullDoubleArray();
87
88 for (int length : lengths) {
89 testMergeSort(length);
90 testAndCheckRange(length);
91 testAndCheckSubArray(length);
92 }
93 for (long seed : randoms) {
94 for (int length : lengths) {
95 testAndCheckWithInsertionSort(length, new MyRandom(seed));
96 testAndCheckWithCheckSum(length, new MyRandom(seed));
97 testAndCheckWithScrambling(length, new MyRandom(seed));
98 testAndCheckFloat(length, new MyRandom(seed));
99 testAndCheckDouble(length, new MyRandom(seed));
100 testStable(length, new MyRandom(seed));
101 }
102 }
103 }
104
105 private static void testEmptyAndNullIntArray() {
106 ourDescription = "Check empty and null array";
107 Arrays.parallelSort(new int[]{});
108 Arrays.parallelSort(new int[]{}, 0, 0);
109
110 try {
111 Arrays.parallelSort((int[]) null);
112 } catch (NullPointerException expected) {
113 try {
114 Arrays.parallelSort((int[]) null, 0, 0);
115 } catch (NullPointerException expected2) {
116 return;
117 }
118 failed("Arrays.parallelSort(int[],fromIndex,toIndex) shouldn't " +
119 "catch null array");
120 }
121 failed("Arrays.parallelSort(int[]) shouldn't catch null array");
122 }
123
124 private static void testEmptyAndNullLongArray() {
125 ourDescription = "Check empty and null array";
126 Arrays.parallelSort(new long[]{});
127 Arrays.parallelSort(new long[]{}, 0, 0);
128
129 try {
130 Arrays.parallelSort((long[]) null);
131 } catch (NullPointerException expected) {
132 try {
133 Arrays.parallelSort((long[]) null, 0, 0);
134 } catch (NullPointerException expected2) {
135 return;
136 }
137 failed("Arrays.parallelSort(long[],fromIndex,toIndex) shouldn't " +
138 "catch null array");
139 }
140 failed("Arrays.parallelSort(long[]) shouldn't catch null array");
141 }
142
143 private static void testEmptyAndNullShortArray() {
144 ourDescription = "Check empty and null array";
145 Arrays.parallelSort(new short[]{});
146 Arrays.parallelSort(new short[]{}, 0, 0);
147
148 try {
149 Arrays.parallelSort((short[]) null);
150 } catch (NullPointerException expected) {
151 try {
152 Arrays.parallelSort((short[]) null, 0, 0);
153 } catch (NullPointerException expected2) {
154 return;
155 }
156 failed("Arrays.parallelSort(short[],fromIndex,toIndex) shouldn't " +
157 "catch null array");
158 }
159 failed("Arrays.parallelSort(short[]) shouldn't catch null array");
160 }
161
162 private static void testEmptyAndNullCharArray() {
163 ourDescription = "Check empty and null array";
164 Arrays.parallelSort(new char[]{});
165 Arrays.parallelSort(new char[]{}, 0, 0);
166
167 try {
168 Arrays.parallelSort((char[]) null);
169 } catch (NullPointerException expected) {
170 try {
171 Arrays.parallelSort((char[]) null, 0, 0);
172 } catch (NullPointerException expected2) {
173 return;
174 }
175 failed("Arrays.parallelSort(char[],fromIndex,toIndex) shouldn't " +
176 "catch null array");
177 }
178 failed("Arrays.parallelSort(char[]) shouldn't catch null array");
179 }
180
181 private static void testEmptyAndNullByteArray() {
182 ourDescription = "Check empty and null array";
183 Arrays.parallelSort(new byte[]{});
184 Arrays.parallelSort(new byte[]{}, 0, 0);
185
186 try {
187 Arrays.parallelSort((byte[]) null);
188 } catch (NullPointerException expected) {
189 try {
190 Arrays.parallelSort((byte[]) null, 0, 0);
191 } catch (NullPointerException expected2) {
192 return;
193 }
194 failed("Arrays.parallelSort(byte[],fromIndex,toIndex) shouldn't " +
195 "catch null array");
196 }
197 failed("Arrays.parallelSort(byte[]) shouldn't catch null array");
198 }
199
200 private static void testEmptyAndNullFloatArray() {
201 ourDescription = "Check empty and null array";
202 Arrays.parallelSort(new float[]{});
203 Arrays.parallelSort(new float[]{}, 0, 0);
204
205 try {
206 Arrays.parallelSort((float[]) null);
207 } catch (NullPointerException expected) {
208 try {
209 Arrays.parallelSort((float[]) null, 0, 0);
210 } catch (NullPointerException expected2) {
211 return;
212 }
213 failed("Arrays.parallelSort(float[],fromIndex,toIndex) shouldn't " +
214 "catch null array");
215 }
216 failed("Arrays.parallelSort(float[]) shouldn't catch null array");
217 }
218
219 private static void testEmptyAndNullDoubleArray() {
220 ourDescription = "Check empty and null array";
221 Arrays.parallelSort(new double[]{});
222 Arrays.parallelSort(new double[]{}, 0, 0);
223
224 try {
225 Arrays.parallelSort((double[]) null);
226 } catch (NullPointerException expected) {
227 try {
228 Arrays.parallelSort((double[]) null, 0, 0);
229 } catch (NullPointerException expected2) {
230 return;
231 }
232 failed("Arrays.parallelSort(double[],fromIndex,toIndex) shouldn't " +
233 "catch null array");
234 }
235 failed("Arrays.parallelSort(double[]) shouldn't catch null array");
236 }
237
238 private static void testAndCheckSubArray(int length) {
239 ourDescription = "Check sorting of subarray";
240 int[] golden = new int[length];
241 boolean newLine = false;
242
278 }
279 }
280 out.println();
281 }
282
283 private static void testStable(int length, MyRandom random) {
284 ourDescription = "Check if sorting is stable";
285 Pair[] a = build(length, random);
286
287 out.println("Test 'stable': " + "random = " + random.getSeed() +
288 ", length = " + length);
289 Arrays.parallelSort(a);
290 checkSorted(a);
291 checkStable(a);
292 out.println();
293
294 a = build(length, random);
295
296 out.println("Test 'stable' comparator: " + "random = " + random.getSeed() +
297 ", length = " + length);
298 Arrays.parallelSort(a, pairCmp);
299 checkSorted(a);
300 checkStable(a);
301 out.println();
302
303 }
304
305 private static void checkSorted(Pair[] a) {
306 for (int i = 0; i < a.length - 1; i++) {
307 if (a[i].getKey() > a[i + 1].getKey()) {
308 failedSort(i, "" + a[i].getKey(), "" + a[i + 1].getKey());
309 }
310 }
311 }
312
313 private static void checkStable(Pair[] a) {
314 for (int i = 0; i < a.length / 4; ) {
315 int key1 = a[i].getKey();
316 int value1 = a[i++].getValue();
317 int key2 = a[i].getKey();
318 int value2 = a[i++].getValue();
319 int key3 = a[i].getKey();
320 int value3 = a[i++].getValue();
321 int key4 = a[i].getKey();
322 int value4 = a[i++].getValue();
329 failed("Sorting is not stable at position " + i +
330 ". Second values have been changed: " + value1 + ", " +
331 value2 + ", " + value3 + ", " + value4);
332 }
333 }
334 }
335
336 private static Pair[] build(int length, Random random) {
337 Pair[] a = new Pair[length * 4];
338
339 for (int i = 0; i < a.length; ) {
340 int key = random.nextInt();
341 a[i++] = new Pair(key, 1);
342 a[i++] = new Pair(key, 2);
343 a[i++] = new Pair(key, 3);
344 a[i++] = new Pair(key, 4);
345 }
346 return a;
347 }
348
349 private static Comparator<Pair> pairCmp = new Comparator<Pair>() {
350 public int compare(Pair p1, Pair p2) {
351 return p1.compareTo(p2);
352 }
353 };
354
355 private static final class Pair implements Comparable<Pair> {
356 Pair(int key, int value) {
357 myKey = key;
358 myValue = value;
359 }
360
361 int getKey() {
362 return myKey;
363 }
364
365 int getValue() {
366 return myValue;
367 }
368
369 public int compareTo(Pair pair) {
397 for (UnsortedBuilder builder : UnsortedBuilder.values()) {
398 builder.build(golden, m, random);
399 int[] test = golden.clone();
400
401 for (TypeConverter converter : TypeConverter.values()) {
402 out.println("Test 'insertion sort': " + converter +
403 " " + builder + "random = " + random.getSeed() +
404 ", length = " + length + ", m = " + m);
405 Object convertedGolden = converter.convert(golden);
406 Object convertedTest1 = converter.convert(test);
407 Object convertedTest2 = converter.convert(test);
408 sort(convertedTest1);
409 sortByInsertionSort(convertedTest2);
410 compare(convertedTest1, convertedTest2);
411 }
412 }
413 }
414 out.println();
415 }
416
417 private static void testMergeSort(int length) {
418 if (length < 1000) {
419 return;
420 }
421 ourDescription = "Check merge sorting";
422 int[] golden = new int[length];
423 int period = 67; // java.util.DualPivotQuicksort.MAX_RUN_COUNT
424
425 for (int m = period - 2; m <= period + 2; m++) {
426 for (MergeBuilder builder : MergeBuilder.values()) {
427 builder.build(golden, m);
428 int[] test = golden.clone();
429
430 for (TypeConverter converter : TypeConverter.values()) {
431 out.println("Test 'merge sort': " + converter + " " +
432 builder + "length = " + length + ", m = " + m);
433 Object convertedGolden = converter.convert(golden);
434 sort(convertedGolden);
435 checkSorted(convertedGolden);
436 }
437 }
438 }
439 out.println();
440 }
441
442 private static void testAndCheckWithCheckSum(int length, MyRandom random) {
443 ourDescription = "Check sorting with check sum";
444 int[] golden = new int[length];
445
446 for (int m = 1; m < 2 * length; m *= 2) {
447 for (UnsortedBuilder builder : UnsortedBuilder.values()) {
448 builder.build(golden, m, random);
449 int[] test = golden.clone();
450
451 for (TypeConverter converter : TypeConverter.values()) {
475 int[] test = golden.clone();
476 scramble(test, random);
477
478 for (TypeConverter converter : TypeConverter.values()) {
479 out.println("Test 'scrambling': " + converter +
480 " " + builder + "random = " + random.getSeed() +
481 ", length = " + length + ", m = " + m);
482 Object convertedGolden = converter.convert(golden);
483 Object convertedTest = converter.convert(test);
484 sort(convertedTest);
485 compare(convertedTest, convertedGolden);
486 }
487 }
488 }
489 out.println();
490 }
491
492 private static void testAndCheckFloat(int length, MyRandom random) {
493 ourDescription = "Check float sorting";
494 float[] golden = new float[length];
495 final int MAX = 10;
496 boolean newLine = false;
497
498 for (int a = 0; a <= MAX; a++) {
499 for (int g = 0; g <= MAX; g++) {
500 for (int z = 0; z <= MAX; z++) {
501 for (int n = 0; n <= MAX; n++) {
502 for (int p = 0; p <= MAX; p++) {
503 if (a + g + z + n + p > length) {
504 continue;
505 }
506 if (a + g + z + n + p < length) {
507 continue;
508 }
509 for (FloatBuilder builder : FloatBuilder.values()) {
510 out.println("Test 'float': random = " + random.getSeed() +
511 ", length = " + length + ", a = " + a + ", g = " +
512 g + ", z = " + z + ", n = " + n + ", p = " + p);
513 builder.build(golden, a, g, z, n, p, random);
514 float[] test = golden.clone();
515 scramble(test, random);
516 sort(test);
517 compare(test, golden, a, n, g);
518 }
519 newLine = true;
520 }
521 }
522 }
523 }
524 }
525 if (newLine) {
526 out.println();
550 g + ", z = " + z + ", n = " + n + ", p = " + p);
551 builder.build(golden, a, g, z, n, p, random);
552 double[] test = golden.clone();
553 scramble(test, random);
554 sort(test);
555 compare(test, golden, a, n, g);
556 }
557 newLine = true;
558 }
559 }
560 }
561 }
562 }
563 if (newLine) {
564 out.println();
565 }
566 }
567
568 private static void prepareSubArray(int[] a, int fromIndex, int toIndex, int m) {
569 for (int i = 0; i < fromIndex; i++) {
570 a[i] = 0xDEDA;
571 }
572 int middle = (fromIndex + toIndex) >>> 1;
573 int k = 0;
574
575 for (int i = fromIndex; i < middle; i++) {
576 a[i] = k++;
577 }
578 for (int i = middle; i < toIndex; i++) {
579 a[i] = k--;
580 }
581 for (int i = toIndex; i < a.length; i++) {
582 a[i] = 0xBABA;
583 }
584 }
585
586 private static void scramble(int[] a, Random random) {
587 for (int i = 0; i < a.length * 7; i++) {
588 swap(a, random.nextInt(a.length), random.nextInt(a.length));
589 }
590 }
591
592 private static void scramble(float[] a, Random random) {
593 for (int i = 0; i < a.length * 7; i++) {
594 swap(a, random.nextInt(a.length), random.nextInt(a.length));
595 }
596 }
597
598 private static void scramble(double[] a, Random random) {
599 for (int i = 0; i < a.length * 7; i++) {
600 swap(a, random.nextInt(a.length), random.nextInt(a.length));
601 }
602 }
673 b[i] = (float) a[i];
674 }
675 return b;
676 }
677 },
678 DOUBLE {
679 Object convert(int[] a) {
680 double[] b = new double[a.length];
681
682 for (int i = 0; i < a.length; i++) {
683 b[i] = (double) a[i];
684 }
685 return b;
686 }
687 },
688 INTEGER {
689 Object convert(int[] a) {
690 Integer[] b = new Integer[a.length];
691
692 for (int i = 0; i < a.length; i++) {
693 b[i] = new Integer(a[i]);
694 }
695 return b;
696 }
697 };
698
699 abstract Object convert(int[] a);
700
701 @Override public String toString() {
702 String name = name();
703
704 for (int i = name.length(); i < 9; i++) {
705 name += " ";
706 }
707 return name;
708 }
709 }
710
711 private static enum FloatBuilder {
712 SIMPLE {
713 void build(float[] x, int a, int g, int z, int n, int p, Random random) {
714 int fromIndex = 0;
715 float negativeValue = -random.nextFloat();
716 float positiveValue = random.nextFloat();
717
718 writeValue(x, negativeValue, fromIndex, n);
719 fromIndex += n;
720
721 writeValue(x, -0.0f, fromIndex, g);
834 }
835 },
836 ORGAN_PIPES {
837 void build(int[] a, int m) {
838 int i = 0;
839 int k = m;
840
841 while (true) {
842 for (int t = 1; t <= m; t++) {
843 if (i >= a.length) {
844 return;
845 }
846 a[i++] = k;
847 }
848 }
849 }
850 };
851
852 abstract void build(int[] a, int m);
853
854 @Override public String toString() {
855 String name = name();
856
857 for (int i = name.length(); i < 12; i++) {
858 name += " ";
859 }
860 return name;
861 }
862 }
863
864 private static enum MergeBuilder {
865 ASCENDING {
866 void build(int[] a, int m) {
867 int period = a.length / m;
868 int v = 1, i = 0;
869
870 for (int k = 0; k < m; k++) {
871 v = 1;
872 for (int p = 0; p < period; p++) {
873 a[i++] = v++;
874 }
875 }
876 for (int j = i; j < a.length - 1; j++) {
877 a[j] = v++;
878 }
879 a[a.length - 1] = 0;
880 }
881 },
882 DESCENDING {
883 void build(int[] a, int m) {
884 int period = a.length / m;
885 int v = -1, i = 0;
886
887 for (int k = 0; k < m; k++) {
888 v = -1;
889 for (int p = 0; p < period; p++) {
890 a[i++] = v--;
891 }
892 }
893 for (int j = i; j < a.length - 1; j++) {
894 a[j] = v--;
895 }
896 a[a.length - 1] = 0;
897 }
898 };
899
900 abstract void build(int[] a, int m);
901
902 @Override public String toString() {
903 String name = name();
904
905 for (int i = name.length(); i < 12; i++) {
906 name += " ";
907 }
908 return name;
909 }
910 }
911
912 private static enum UnsortedBuilder {
913 RANDOM {
914 void build(int[] a, int m, Random random) {
915 for (int i = 0; i < a.length; i++) {
916 a[i] = random.nextInt();
917 }
918 }
919 },
920 ASCENDING {
921 void build(int[] a, int m, Random random) {
922 for (int i = 0; i < a.length; i++) {
923 a[i] = m + i;
924 }
925 }
926 },
927 DESCENDING {
928 void build(int[] a, int m, Random random) {
929 for (int i = 0; i < a.length; i++) {
930 a[i] = a.length - m - i;
931 }
998 }
999 },
1000 PLATEAU {
1001 void build(int[] a, int m, Random random) {
1002 for (int i = 0; i < a.length; i++) {
1003 a[i] = Math.min(i, m);
1004 }
1005 }
1006 },
1007 SHUFFLE {
1008 void build(int[] a, int m, Random random) {
1009 int x = 0, y = 0;
1010 for (int i = 0; i < a.length; i++) {
1011 a[i] = random.nextBoolean() ? (x += 2) : (y += 2);
1012 }
1013 }
1014 };
1015
1016 abstract void build(int[] a, int m, Random random);
1017
1018 @Override public String toString() {
1019 String name = name();
1020
1021 for (int i = name.length(); i < 12; i++) {
1022 name += " ";
1023 }
1024 return name;
1025 }
1026 }
1027
1028 private static void checkWithCheckSum(Object test, Object golden) {
1029 checkSorted(test);
1030 checkCheckSum(test, golden);
1031 }
1032
1033 private static void failed(String message) {
1034 err.format("\n*** TEST FAILED - %s.\n\n%s.\n\n", ourDescription, message);
1035 throw new RuntimeException("Test failed - see log file for details");
1036 }
1037
1038 private static void failedSort(int index, String value1, String value2) {
1045 }
1046
1047 private static void compare(Object test, Object golden) {
1048 if (test instanceof int[]) {
1049 compare((int[]) test, (int[]) golden);
1050 } else if (test instanceof long[]) {
1051 compare((long[]) test, (long[]) golden);
1052 } else if (test instanceof short[]) {
1053 compare((short[]) test, (short[]) golden);
1054 } else if (test instanceof byte[]) {
1055 compare((byte[]) test, (byte[]) golden);
1056 } else if (test instanceof char[]) {
1057 compare((char[]) test, (char[]) golden);
1058 } else if (test instanceof float[]) {
1059 compare((float[]) test, (float[]) golden);
1060 } else if (test instanceof double[]) {
1061 compare((double[]) test, (double[]) golden);
1062 } else if (test instanceof Integer[]) {
1063 compare((Integer[]) test, (Integer[]) golden);
1064 } else {
1065 failed("Unknow type of array: " + test + " of class " +
1066 test.getClass().getName());
1067 }
1068 }
1069
1070 private static void compare(int[] a, int[] b) {
1071 for (int i = 0; i < a.length; i++) {
1072 if (a[i] != b[i]) {
1073 failedCompare(i, "" + a[i], "" + b[i]);
1074 }
1075 }
1076 }
1077
1078 private static void compare(long[] a, long[] b) {
1079 for (int i = 0; i < a.length; i++) {
1080 if (a[i] != b[i]) {
1081 failedCompare(i, "" + a[i], "" + b[i]);
1082 }
1083 }
1084 }
1085
1132 }
1133
1134 private static void checkSorted(Object object) {
1135 if (object instanceof int[]) {
1136 checkSorted((int[]) object);
1137 } else if (object instanceof long[]) {
1138 checkSorted((long[]) object);
1139 } else if (object instanceof short[]) {
1140 checkSorted((short[]) object);
1141 } else if (object instanceof byte[]) {
1142 checkSorted((byte[]) object);
1143 } else if (object instanceof char[]) {
1144 checkSorted((char[]) object);
1145 } else if (object instanceof float[]) {
1146 checkSorted((float[]) object);
1147 } else if (object instanceof double[]) {
1148 checkSorted((double[]) object);
1149 } else if (object instanceof Integer[]) {
1150 checkSorted((Integer[]) object);
1151 } else {
1152 failed("Unknow type of array: " + object + " of class " +
1153 object.getClass().getName());
1154 }
1155 }
1156
1157 private static void checkSorted(int[] a) {
1158 for (int i = 0; i < a.length - 1; i++) {
1159 if (a[i] > a[i + 1]) {
1160 failedSort(i, "" + a[i], "" + a[i + 1]);
1161 }
1162 }
1163 }
1164
1165 private static void checkSorted(long[] a) {
1166 for (int i = 0; i < a.length - 1; i++) {
1167 if (a[i] > a[i + 1]) {
1168 failedSort(i, "" + a[i], "" + a[i + 1]);
1169 }
1170 }
1171 }
1172
1228 }
1229
1230 private static int checkSumXor(Object object) {
1231 if (object instanceof int[]) {
1232 return checkSumXor((int[]) object);
1233 } else if (object instanceof long[]) {
1234 return checkSumXor((long[]) object);
1235 } else if (object instanceof short[]) {
1236 return checkSumXor((short[]) object);
1237 } else if (object instanceof byte[]) {
1238 return checkSumXor((byte[]) object);
1239 } else if (object instanceof char[]) {
1240 return checkSumXor((char[]) object);
1241 } else if (object instanceof float[]) {
1242 return checkSumXor((float[]) object);
1243 } else if (object instanceof double[]) {
1244 return checkSumXor((double[]) object);
1245 } else if (object instanceof Integer[]) {
1246 return checkSumXor((Integer[]) object);
1247 } else {
1248 failed("Unknow type of array: " + object + " of class " +
1249 object.getClass().getName());
1250 return -1;
1251 }
1252 }
1253
1254 private static int checkSumXor(Integer[] a) {
1255 int checkSum = 0;
1256
1257 for (Integer e : a) {
1258 checkSum ^= e.intValue();
1259 }
1260 return checkSum;
1261 }
1262
1263 private static int checkSumXor(int[] a) {
1264 int checkSum = 0;
1265
1266 for (int e : a) {
1267 checkSum ^= e;
1268 }
1324 }
1325
1326 private static int checkSumPlus(Object object) {
1327 if (object instanceof int[]) {
1328 return checkSumPlus((int[]) object);
1329 } else if (object instanceof long[]) {
1330 return checkSumPlus((long[]) object);
1331 } else if (object instanceof short[]) {
1332 return checkSumPlus((short[]) object);
1333 } else if (object instanceof byte[]) {
1334 return checkSumPlus((byte[]) object);
1335 } else if (object instanceof char[]) {
1336 return checkSumPlus((char[]) object);
1337 } else if (object instanceof float[]) {
1338 return checkSumPlus((float[]) object);
1339 } else if (object instanceof double[]) {
1340 return checkSumPlus((double[]) object);
1341 } else if (object instanceof Integer[]) {
1342 return checkSumPlus((Integer[]) object);
1343 } else {
1344 failed("Unknow type of array: " + object + " of class " +
1345 object.getClass().getName());
1346 return -1;
1347 }
1348 }
1349
1350 private static int checkSumPlus(int[] a) {
1351 int checkSum = 0;
1352
1353 for (int e : a) {
1354 checkSum += e;
1355 }
1356 return checkSum;
1357 }
1358
1359 private static int checkSumPlus(long[] a) {
1360 long checkSum = 0;
1361
1362 for (long e : a) {
1363 checkSum += e;
1364 }
1420 }
1421
1422 private static void sortByInsertionSort(Object object) {
1423 if (object instanceof int[]) {
1424 sortByInsertionSort((int[]) object);
1425 } else if (object instanceof long[]) {
1426 sortByInsertionSort((long[]) object);
1427 } else if (object instanceof short[]) {
1428 sortByInsertionSort((short[]) object);
1429 } else if (object instanceof byte[]) {
1430 sortByInsertionSort((byte[]) object);
1431 } else if (object instanceof char[]) {
1432 sortByInsertionSort((char[]) object);
1433 } else if (object instanceof float[]) {
1434 sortByInsertionSort((float[]) object);
1435 } else if (object instanceof double[]) {
1436 sortByInsertionSort((double[]) object);
1437 } else if (object instanceof Integer[]) {
1438 sortByInsertionSort((Integer[]) object);
1439 } else {
1440 failed("Unknow type of array: " + object + " of class " +
1441 object.getClass().getName());
1442 }
1443 }
1444
1445 private static void sortByInsertionSort(int[] a) {
1446 for (int j, i = 1; i < a.length; i++) {
1447 int ai = a[i];
1448 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1449 a[j + 1] = a[j];
1450 }
1451 a[j + 1] = ai;
1452 }
1453 }
1454
1455 private static void sortByInsertionSort(long[] a) {
1456 for (int j, i = 1; i < a.length; i++) {
1457 long ai = a[i];
1458 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1459 a[j + 1] = a[j];
1460 }
1523 }
1524
1525 private static void sort(Object object) {
1526 if (object instanceof int[]) {
1527 Arrays.parallelSort((int[]) object);
1528 } else if (object instanceof long[]) {
1529 Arrays.parallelSort((long[]) object);
1530 } else if (object instanceof short[]) {
1531 Arrays.parallelSort((short[]) object);
1532 } else if (object instanceof byte[]) {
1533 Arrays.parallelSort((byte[]) object);
1534 } else if (object instanceof char[]) {
1535 Arrays.parallelSort((char[]) object);
1536 } else if (object instanceof float[]) {
1537 Arrays.parallelSort((float[]) object);
1538 } else if (object instanceof double[]) {
1539 Arrays.parallelSort((double[]) object);
1540 } else if (object instanceof Integer[]) {
1541 Arrays.parallelSort((Integer[]) object);
1542 } else {
1543 failed("Unknow type of array: " + object + " of class " +
1544 object.getClass().getName());
1545 }
1546 }
1547
1548 private static void sortSubArray(Object object, int fromIndex, int toIndex) {
1549 if (object instanceof int[]) {
1550 Arrays.parallelSort((int[]) object, fromIndex, toIndex);
1551 } else if (object instanceof long[]) {
1552 Arrays.parallelSort((long[]) object, fromIndex, toIndex);
1553 } else if (object instanceof short[]) {
1554 Arrays.parallelSort((short[]) object, fromIndex, toIndex);
1555 } else if (object instanceof byte[]) {
1556 Arrays.parallelSort((byte[]) object, fromIndex, toIndex);
1557 } else if (object instanceof char[]) {
1558 Arrays.parallelSort((char[]) object, fromIndex, toIndex);
1559 } else if (object instanceof float[]) {
1560 Arrays.parallelSort((float[]) object, fromIndex, toIndex);
1561 } else if (object instanceof double[]) {
1562 Arrays.parallelSort((double[]) object, fromIndex, toIndex);
1563 } else if (object instanceof Integer[]) {
1564 Arrays.parallelSort((Integer[]) object, fromIndex, toIndex);
1565 } else {
1566 failed("Unknow type of array: " + object + " of class " +
1567 object.getClass().getName());
1568 }
1569 }
1570
1571 private static void checkSubArray(Object object, int fromIndex, int toIndex, int m) {
1572 if (object instanceof int[]) {
1573 checkSubArray((int[]) object, fromIndex, toIndex, m);
1574 } else if (object instanceof long[]) {
1575 checkSubArray((long[]) object, fromIndex, toIndex, m);
1576 } else if (object instanceof short[]) {
1577 checkSubArray((short[]) object, fromIndex, toIndex, m);
1578 } else if (object instanceof byte[]) {
1579 checkSubArray((byte[]) object, fromIndex, toIndex, m);
1580 } else if (object instanceof char[]) {
1581 checkSubArray((char[]) object, fromIndex, toIndex, m);
1582 } else if (object instanceof float[]) {
1583 checkSubArray((float[]) object, fromIndex, toIndex, m);
1584 } else if (object instanceof double[]) {
1585 checkSubArray((double[]) object, fromIndex, toIndex, m);
1586 } else if (object instanceof Integer[]) {
1587 checkSubArray((Integer[]) object, fromIndex, toIndex, m);
1588 } else {
1589 failed("Unknow type of array: " + object + " of class " +
1590 object.getClass().getName());
1591 }
1592 }
1593
1594 private static void checkSubArray(Integer[] a, int fromIndex, int toIndex, int m) {
1595 for (int i = 0; i < fromIndex; i++) {
1596 if (a[i].intValue() != 0xDEDA) {
1597 failed("Range sort changes left element on position " + i +
1598 ": " + a[i] + ", must be " + 0xDEDA);
1599 }
1600 }
1601
1602 for (int i = fromIndex; i < toIndex - 1; i++) {
1603 if (a[i].intValue() > a[i + 1].intValue()) {
1604 failedSort(i, "" + a[i], "" + a[i + 1]);
1605 }
1606 }
1607
1608 for (int i = toIndex; i < a.length; i++) {
1609 if (a[i].intValue() != 0xBABA) {
1610 failed("Range sort changes right element on position " + i +
1611 ": " + a[i] + ", must be " + 0xBABA);
1612 }
1613 }
1614 }
1615
1616 private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) {
1617 for (int i = 0; i < fromIndex; i++) {
1618 if (a[i] != 0xDEDA) {
1619 failed("Range sort changes left element on position " + i +
1620 ": " + a[i] + ", must be " + 0xDEDA);
1621 }
1622 }
1623
1624 for (int i = fromIndex; i < toIndex - 1; i++) {
1625 if (a[i] > a[i + 1]) {
1626 failedSort(i, "" + a[i], "" + a[i + 1]);
1627 }
1628 }
1629
1630 for (int i = toIndex; i < a.length; i++) {
1631 if (a[i] != 0xBABA) {
1632 failed("Range sort changes right element on position " + i +
1633 ": " + a[i] + ", must be " + 0xBABA);
1634 }
1635 }
1636 }
1637
1638 private static void checkSubArray(byte[] a, int fromIndex, int toIndex, int m) {
1639 for (int i = 0; i < fromIndex; i++) {
1640 if (a[i] != (byte) 0xDEDA) {
1641 failed("Range sort changes left element on position " + i +
1642 ": " + a[i] + ", must be " + 0xDEDA);
1643 }
1644 }
1645
1646 for (int i = fromIndex; i < toIndex - 1; i++) {
1647 if (a[i] > a[i + 1]) {
1648 failedSort(i, "" + a[i], "" + a[i + 1]);
1649 }
1650 }
1651
1652 for (int i = toIndex; i < a.length; i++) {
1653 if (a[i] != (byte) 0xBABA) {
1654 failed("Range sort changes right element on position " + i +
1655 ": " + a[i] + ", must be " + 0xBABA);
1656 }
1657 }
1658 }
1659
1660 private static void checkSubArray(long[] a, int fromIndex, int toIndex, int m) {
1661 for (int i = 0; i < fromIndex; i++) {
1662 if (a[i] != (long) 0xDEDA) {
1663 failed("Range sort changes left element on position " + i +
1664 ": " + a[i] + ", must be " + 0xDEDA);
1665 }
1666 }
1667
1668 for (int i = fromIndex; i < toIndex - 1; i++) {
1669 if (a[i] > a[i + 1]) {
1670 failedSort(i, "" + a[i], "" + a[i + 1]);
1671 }
1672 }
1673
1674 for (int i = toIndex; i < a.length; i++) {
1675 if (a[i] != (long) 0xBABA) {
1676 failed("Range sort changes right element on position " + i +
1677 ": " + a[i] + ", must be " + 0xBABA);
1678 }
1679 }
1680 }
1681
1682 private static void checkSubArray(char[] a, int fromIndex, int toIndex, int m) {
1683 for (int i = 0; i < fromIndex; i++) {
1684 if (a[i] != (char) 0xDEDA) {
1685 failed("Range sort changes left element on position " + i +
1686 ": " + a[i] + ", must be " + 0xDEDA);
1687 }
1688 }
1689
1690 for (int i = fromIndex; i < toIndex - 1; i++) {
1691 if (a[i] > a[i + 1]) {
1692 failedSort(i, "" + a[i], "" + a[i + 1]);
1693 }
1694 }
1695
1696 for (int i = toIndex; i < a.length; i++) {
1697 if (a[i] != (char) 0xBABA) {
1698 failed("Range sort changes right element on position " + i +
1699 ": " + a[i] + ", must be " + 0xBABA);
1700 }
1701 }
1702 }
1703
1704 private static void checkSubArray(short[] a, int fromIndex, int toIndex, int m) {
1705 for (int i = 0; i < fromIndex; i++) {
1706 if (a[i] != (short) 0xDEDA) {
1707 failed("Range sort changes left element on position " + i +
1708 ": " + a[i] + ", must be " + 0xDEDA);
1709 }
1710 }
1711
1712 for (int i = fromIndex; i < toIndex - 1; i++) {
1713 if (a[i] > a[i + 1]) {
1714 failedSort(i, "" + a[i], "" + a[i + 1]);
1715 }
1716 }
1717
1718 for (int i = toIndex; i < a.length; i++) {
1719 if (a[i] != (short) 0xBABA) {
1720 failed("Range sort changes right element on position " + i +
1721 ": " + a[i] + ", must be " + 0xBABA);
1722 }
1723 }
1724 }
1725
1726 private static void checkSubArray(float[] a, int fromIndex, int toIndex, int m) {
1727 for (int i = 0; i < fromIndex; i++) {
1728 if (a[i] != (float) 0xDEDA) {
1729 failed("Range sort changes left element on position " + i +
1730 ": " + a[i] + ", must be " + 0xDEDA);
1731 }
1732 }
1733
1734 for (int i = fromIndex; i < toIndex - 1; i++) {
1735 if (a[i] > a[i + 1]) {
1736 failedSort(i, "" + a[i], "" + a[i + 1]);
1737 }
1738 }
1739
1740 for (int i = toIndex; i < a.length; i++) {
1741 if (a[i] != (float) 0xBABA) {
1742 failed("Range sort changes right element on position " + i +
1743 ": " + a[i] + ", must be " + 0xBABA);
1744 }
1745 }
1746 }
1747
1748 private static void checkSubArray(double[] a, int fromIndex, int toIndex, int m) {
1749 for (int i = 0; i < fromIndex; i++) {
1750 if (a[i] != (double) 0xDEDA) {
1751 failed("Range sort changes left element on position " + i +
1752 ": " + a[i] + ", must be " + 0xDEDA);
1753 }
1754 }
1755
1756 for (int i = fromIndex; i < toIndex - 1; i++) {
1757 if (a[i] > a[i + 1]) {
1758 failedSort(i, "" + a[i], "" + a[i + 1]);
1759 }
1760 }
1761
1762 for (int i = toIndex; i < a.length; i++) {
1763 if (a[i] != (double) 0xBABA) {
1764 failed("Range sort changes right element on position " + i +
1765 ": " + a[i] + ", must be " + 0xBABA);
1766 }
1767 }
1768 }
1769
1770 private static void checkRange(Object object, int m) {
1771 if (object instanceof int[]) {
1772 checkRange((int[]) object, m);
1773 } else if (object instanceof long[]) {
1774 checkRange((long[]) object, m);
1775 } else if (object instanceof short[]) {
1776 checkRange((short[]) object, m);
1777 } else if (object instanceof byte[]) {
1778 checkRange((byte[]) object, m);
1779 } else if (object instanceof char[]) {
1780 checkRange((char[]) object, m);
1781 } else if (object instanceof float[]) {
1782 checkRange((float[]) object, m);
1783 } else if (object instanceof double[]) {
1784 checkRange((double[]) object, m);
1785 } else if (object instanceof Integer[]) {
1786 checkRange((Integer[]) object, m);
1787 } else {
1788 failed("Unknow type of array: " + object + " of class " +
1789 object.getClass().getName());
1790 }
1791 }
1792
1793 private static void checkRange(Integer[] a, int m) {
1794 try {
1795 Arrays.parallelSort(a, m + 1, m);
1796
1797 failed("ParallelSort does not throw IllegalArgumentException " +
1798 " as expected: fromIndex = " + (m + 1) +
1799 " toIndex = " + m);
1800 }
1801 catch (IllegalArgumentException iae) {
1802 try {
1803 Arrays.parallelSort(a, -m, a.length);
1804
1805 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1806 " as expected: fromIndex = " + (-m));
1807 }
1808 catch (ArrayIndexOutOfBoundsException aoe) {
1809 try {
1810 Arrays.parallelSort(a, 0, a.length + m);
1811
1812 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1813 " as expected: toIndex = " + (a.length + m));
1814 }
1815 catch (ArrayIndexOutOfBoundsException aie) {
1816 return;
1817 }
1818 }
1819 }
1820 }
1821
1822 private static void checkRange(int[] a, int m) {
1823 try {
1824 Arrays.parallelSort(a, m + 1, m);
1825
1826 failed("ParallelSort does not throw IllegalArgumentException " +
1827 " as expected: fromIndex = " + (m + 1) +
1828 " toIndex = " + m);
1829 }
1830 catch (IllegalArgumentException iae) {
1831 try {
1832 Arrays.parallelSort(a, -m, a.length);
1833
1834 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1835 " as expected: fromIndex = " + (-m));
1836 }
1837 catch (ArrayIndexOutOfBoundsException aoe) {
1838 try {
1839 Arrays.parallelSort(a, 0, a.length + m);
1840
1841 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1842 " as expected: toIndex = " + (a.length + m));
1843 }
1844 catch (ArrayIndexOutOfBoundsException aie) {
1845 return;
1846 }
1847 }
1848 }
1849 }
1850
1851 private static void checkRange(long[] a, int m) {
1852 try {
1853 Arrays.parallelSort(a, m + 1, m);
1854
1855 failed("ParallelSort does not throw IllegalArgumentException " +
1856 " as expected: fromIndex = " + (m + 1) +
1857 " toIndex = " + m);
1858 }
1859 catch (IllegalArgumentException iae) {
1860 try {
1861 Arrays.parallelSort(a, -m, a.length);
1862
1863 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1864 " as expected: fromIndex = " + (-m));
1865 }
1866 catch (ArrayIndexOutOfBoundsException aoe) {
1867 try {
1868 Arrays.parallelSort(a, 0, a.length + m);
1869
1870 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1871 " as expected: toIndex = " + (a.length + m));
1872 }
1873 catch (ArrayIndexOutOfBoundsException aie) {
1874 return;
1875 }
1876 }
1877 }
1878 }
1879
1880 private static void checkRange(byte[] a, int m) {
1881 try {
1882 Arrays.parallelSort(a, m + 1, m);
1883
1884 failed("ParallelSort does not throw IllegalArgumentException " +
1885 " as expected: fromIndex = " + (m + 1) +
1886 " toIndex = " + m);
1887 }
1888 catch (IllegalArgumentException iae) {
1889 try {
1890 Arrays.parallelSort(a, -m, a.length);
1891
1892 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1893 " as expected: fromIndex = " + (-m));
1894 }
1895 catch (ArrayIndexOutOfBoundsException aoe) {
1896 try {
1897 Arrays.parallelSort(a, 0, a.length + m);
1898
1899 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1900 " as expected: toIndex = " + (a.length + m));
1901 }
1902 catch (ArrayIndexOutOfBoundsException aie) {
1903 return;
1904 }
1905 }
1906 }
1907 }
1908
1909 private static void checkRange(short[] a, int m) {
1910 try {
1911 Arrays.parallelSort(a, m + 1, m);
1912
1913 failed("ParallelSort does not throw IllegalArgumentException " +
1914 " as expected: fromIndex = " + (m + 1) +
1915 " toIndex = " + m);
1916 }
1917 catch (IllegalArgumentException iae) {
1918 try {
1919 Arrays.parallelSort(a, -m, a.length);
1920
1921 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1922 " as expected: fromIndex = " + (-m));
1923 }
1924 catch (ArrayIndexOutOfBoundsException aoe) {
1925 try {
1926 Arrays.parallelSort(a, 0, a.length + m);
1927
1928 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1929 " as expected: toIndex = " + (a.length + m));
1930 }
1931 catch (ArrayIndexOutOfBoundsException aie) {
1932 return;
1933 }
1934 }
1935 }
1936 }
1937
1938 private static void checkRange(char[] a, int m) {
1939 try {
1940 Arrays.parallelSort(a, m + 1, m);
1941
1942 failed("ParallelSort does not throw IllegalArgumentException " +
1943 " as expected: fromIndex = " + (m + 1) +
1944 " toIndex = " + m);
1945 }
1946 catch (IllegalArgumentException iae) {
1947 try {
1948 Arrays.parallelSort(a, -m, a.length);
1949
1950 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1951 " as expected: fromIndex = " + (-m));
1952 }
1953 catch (ArrayIndexOutOfBoundsException aoe) {
1954 try {
1955 Arrays.parallelSort(a, 0, a.length + m);
1956
1957 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1958 " as expected: toIndex = " + (a.length + m));
1959 }
1960 catch (ArrayIndexOutOfBoundsException aie) {
1961 return;
1962 }
1963 }
1964 }
1965 }
1966
1967 private static void checkRange(float[] a, int m) {
1968 try {
1969 Arrays.parallelSort(a, m + 1, m);
1970
1971 failed("ParallelSort does not throw IllegalArgumentException " +
1972 " as expected: fromIndex = " + (m + 1) +
1973 " toIndex = " + m);
1974 }
1975 catch (IllegalArgumentException iae) {
1976 try {
1977 Arrays.parallelSort(a, -m, a.length);
1978
1979 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1980 " as expected: fromIndex = " + (-m));
1981 }
1982 catch (ArrayIndexOutOfBoundsException aoe) {
1983 try {
1984 Arrays.parallelSort(a, 0, a.length + m);
1985
1986 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
1987 " as expected: toIndex = " + (a.length + m));
1988 }
1989 catch (ArrayIndexOutOfBoundsException aie) {
1990 return;
1991 }
1992 }
1993 }
1994 }
1995
1996 private static void checkRange(double[] a, int m) {
1997 try {
1998 Arrays.parallelSort(a, m + 1, m);
1999
2000 failed("ParallelSort does not throw IllegalArgumentException " +
2001 " as expected: fromIndex = " + (m + 1) +
2002 " toIndex = " + m);
2003 }
2004 catch (IllegalArgumentException iae) {
2005 try {
2006 Arrays.parallelSort(a, -m, a.length);
2007
2008 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
2009 " as expected: fromIndex = " + (-m));
2010 }
2011 catch (ArrayIndexOutOfBoundsException aoe) {
2012 try {
2013 Arrays.parallelSort(a, 0, a.length + m);
2014
2015 failed("ParallelSort does not throw ArrayIndexOutOfBoundsException " +
2016 " as expected: toIndex = " + (a.length + m));
2017 }
2018 catch (ArrayIndexOutOfBoundsException aie) {
2019 return;
2020 }
2021 }
2022 }
2023 }
2024
2025 private static void outArray(Object[] a) {
2026 for (int i = 0; i < a.length; i++) {
2027 out.print(a[i] + " ");
2028 }
2029 out.println();
2030 }
2031
2032 private static void outArray(int[] a) {
2033 for (int i = 0; i < a.length; i++) {
2034 out.print(a[i] + " ");
2035 }
|
1 /*
2 * Copyright (c) 2011, 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 /* Adapted from test/java/util/Arrays/Sorting.java
25 *
26 * To generate the source of this class, take the source of Sorting.java
27 * and replace "Arrays.sort' by "Arrays.parallelSort'.
28 *
29 * Where that test checks Arrays.sort against manual quicksort routines,
30 * this test checks parallelSort against manual quicksort routines.
31 */
32
33 /*
34 * @test
35 * @bug 8003981
36 * @run main ParallelSorting -shortrun
37 * @summary Exercise Arrays.parallelSort
38 *
39 * @author Vladimir Yaroslavskiy
40 * @author Jon Bentley
41 * @author Josh Bloch
42 */
43
44 import java.io.PrintStream;
45 import java.util.Arrays;
46 import java.util.Random;
47 import java.util.Comparator;
48
49 public class ParallelSorting {
50
51 private static final PrintStream out = System.out;
52 private static final PrintStream err = System.err;
53
54 // Array lengths used in a long run (default)
55 private static final int[] LONG_RUN_LENGTHS = {
56 1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000 };
57
58 // Array lengths used in a short run
59 private static final int[] SHORT_RUN_LENGTHS = {
60 1, 2, 3, 21, 55, 1000, 10000, 12000 };
61
62 // Random initial values used in a long run (default)
63 private static final long[] LONG_RUN_RANDOMS = { 666, 0xC0FFEE, 999 };
64
65 // Random initial values used in a short run
66 private static final long[] SHORT_RUN_RANDOMS = { 666 };
67
68 // Constant values used in subarray sorting
69 private static final int A380 = 0xA380;
70 private static final int B747 = 0xB747;
71
72 public static void main(String[] args) {
73 boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
74 long start = System.currentTimeMillis();
75
76 if (shortRun) {
77 testAndCheck(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
78 } else {
79 testAndCheck(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
80 }
81 long end = System.currentTimeMillis();
82
83 out.format("PASSED in %d sec.\n", Math.round((end - start) / 1E3));
84 }
85
86 private static void testAndCheck(int[] lengths, long[] randoms) {
87 testEmptyAndNullIntArray();
88 testEmptyAndNullLongArray();
89 testEmptyAndNullShortArray();
90 testEmptyAndNullCharArray();
91 testEmptyAndNullByteArray();
92 testEmptyAndNullFloatArray();
93 testEmptyAndNullDoubleArray();
94
95 for (int length : lengths) {
96 testMergingSort(length);
97 testAndCheckRange(length);
98 testAndCheckSubArray(length);
99 }
100 for (long seed : randoms) {
101 for (int length : lengths) {
102 testAndCheckWithInsertionSort(length, new MyRandom(seed));
103 testAndCheckWithCheckSum(length, new MyRandom(seed));
104 testAndCheckWithScrambling(length, new MyRandom(seed));
105 testAndCheckFloat(length, new MyRandom(seed));
106 testAndCheckDouble(length, new MyRandom(seed));
107 testStable(length, new MyRandom(seed));
108 }
109 }
110 }
111
112 private static void testEmptyAndNullIntArray() {
113 ourDescription = "Check empty and null array";
114 Arrays.parallelSort(new int[] {});
115 Arrays.parallelSort(new int[] {}, 0, 0);
116
117 try {
118 Arrays.parallelSort((int[]) null);
119 } catch (NullPointerException expected) {
120 try {
121 Arrays.parallelSort((int[]) null, 0, 0);
122 } catch (NullPointerException expected2) {
123 return;
124 }
125 failed("Arrays.parallelSort(int[],fromIndex,toIndex) shouldn't " +
126 "catch null array");
127 }
128 failed("Arrays.parallelSort(int[]) shouldn't catch null array");
129 }
130
131 private static void testEmptyAndNullLongArray() {
132 ourDescription = "Check empty and null array";
133 Arrays.parallelSort(new long[] {});
134 Arrays.parallelSort(new long[] {}, 0, 0);
135
136 try {
137 Arrays.parallelSort((long[]) null);
138 } catch (NullPointerException expected) {
139 try {
140 Arrays.parallelSort((long[]) null, 0, 0);
141 } catch (NullPointerException expected2) {
142 return;
143 }
144 failed("Arrays.parallelSort(long[],fromIndex,toIndex) shouldn't " +
145 "catch null array");
146 }
147 failed("Arrays.parallelSort(long[]) shouldn't catch null array");
148 }
149
150 private static void testEmptyAndNullShortArray() {
151 ourDescription = "Check empty and null array";
152 Arrays.parallelSort(new short[] {});
153 Arrays.parallelSort(new short[] {}, 0, 0);
154
155 try {
156 Arrays.parallelSort((short[]) null);
157 } catch (NullPointerException expected) {
158 try {
159 Arrays.parallelSort((short[]) null, 0, 0);
160 } catch (NullPointerException expected2) {
161 return;
162 }
163 failed("Arrays.parallelSort(short[],fromIndex,toIndex) shouldn't " +
164 "catch null array");
165 }
166 failed("Arrays.parallelSort(short[]) shouldn't catch null array");
167 }
168
169 private static void testEmptyAndNullCharArray() {
170 ourDescription = "Check empty and null array";
171 Arrays.parallelSort(new char[] {});
172 Arrays.parallelSort(new char[] {}, 0, 0);
173
174 try {
175 Arrays.parallelSort((char[]) null);
176 } catch (NullPointerException expected) {
177 try {
178 Arrays.parallelSort((char[]) null, 0, 0);
179 } catch (NullPointerException expected2) {
180 return;
181 }
182 failed("Arrays.parallelSort(char[],fromIndex,toIndex) shouldn't " +
183 "catch null array");
184 }
185 failed("Arrays.parallelSort(char[]) shouldn't catch null array");
186 }
187
188 private static void testEmptyAndNullByteArray() {
189 ourDescription = "Check empty and null array";
190 Arrays.parallelSort(new byte[] {});
191 Arrays.parallelSort(new byte[] {}, 0, 0);
192
193 try {
194 Arrays.parallelSort((byte[]) null);
195 } catch (NullPointerException expected) {
196 try {
197 Arrays.parallelSort((byte[]) null, 0, 0);
198 } catch (NullPointerException expected2) {
199 return;
200 }
201 failed("Arrays.parallelSort(byte[],fromIndex,toIndex) shouldn't " +
202 "catch null array");
203 }
204 failed("Arrays.parallelSort(byte[]) shouldn't catch null array");
205 }
206
207 private static void testEmptyAndNullFloatArray() {
208 ourDescription = "Check empty and null array";
209 Arrays.parallelSort(new float[] {});
210 Arrays.parallelSort(new float[] {}, 0, 0);
211
212 try {
213 Arrays.parallelSort((float[]) null);
214 } catch (NullPointerException expected) {
215 try {
216 Arrays.parallelSort((float[]) null, 0, 0);
217 } catch (NullPointerException expected2) {
218 return;
219 }
220 failed("Arrays.parallelSort(float[],fromIndex,toIndex) shouldn't " +
221 "catch null array");
222 }
223 failed("Arrays.parallelSort(float[]) shouldn't catch null array");
224 }
225
226 private static void testEmptyAndNullDoubleArray() {
227 ourDescription = "Check empty and null array";
228 Arrays.parallelSort(new double[] {});
229 Arrays.parallelSort(new double[] {}, 0, 0);
230
231 try {
232 Arrays.parallelSort((double[]) null);
233 } catch (NullPointerException expected) {
234 try {
235 Arrays.parallelSort((double[]) null, 0, 0);
236 } catch (NullPointerException expected2) {
237 return;
238 }
239 failed("Arrays.parallelSort(double[],fromIndex,toIndex) shouldn't " +
240 "catch null array");
241 }
242 failed("Arrays.parallelSort(double[]) shouldn't catch null array");
243 }
244
245 private static void testAndCheckSubArray(int length) {
246 ourDescription = "Check sorting of subarray";
247 int[] golden = new int[length];
248 boolean newLine = false;
249
285 }
286 }
287 out.println();
288 }
289
290 private static void testStable(int length, MyRandom random) {
291 ourDescription = "Check if sorting is stable";
292 Pair[] a = build(length, random);
293
294 out.println("Test 'stable': " + "random = " + random.getSeed() +
295 ", length = " + length);
296 Arrays.parallelSort(a);
297 checkSorted(a);
298 checkStable(a);
299 out.println();
300
301 a = build(length, random);
302
303 out.println("Test 'stable' comparator: " + "random = " + random.getSeed() +
304 ", length = " + length);
305 Arrays.parallelSort(a, pairComparator);
306 checkSorted(a);
307 checkStable(a);
308 out.println();
309 }
310
311 private static void checkSorted(Pair[] a) {
312 for (int i = 0; i < a.length - 1; i++) {
313 if (a[i].getKey() > a[i + 1].getKey()) {
314 failedSort(i, "" + a[i].getKey(), "" + a[i + 1].getKey());
315 }
316 }
317 }
318
319 private static void checkStable(Pair[] a) {
320 for (int i = 0; i < a.length / 4; ) {
321 int key1 = a[i].getKey();
322 int value1 = a[i++].getValue();
323 int key2 = a[i].getKey();
324 int value2 = a[i++].getValue();
325 int key3 = a[i].getKey();
326 int value3 = a[i++].getValue();
327 int key4 = a[i].getKey();
328 int value4 = a[i++].getValue();
335 failed("Sorting is not stable at position " + i +
336 ". Second values have been changed: " + value1 + ", " +
337 value2 + ", " + value3 + ", " + value4);
338 }
339 }
340 }
341
342 private static Pair[] build(int length, Random random) {
343 Pair[] a = new Pair[length * 4];
344
345 for (int i = 0; i < a.length; ) {
346 int key = random.nextInt();
347 a[i++] = new Pair(key, 1);
348 a[i++] = new Pair(key, 2);
349 a[i++] = new Pair(key, 3);
350 a[i++] = new Pair(key, 4);
351 }
352 return a;
353 }
354
355 private static Comparator<Pair> pairComparator = new Comparator<Pair>() {
356 public int compare(Pair p1, Pair p2) {
357 return p1.compareTo(p2);
358 }
359 };
360
361 private static final class Pair implements Comparable<Pair> {
362 Pair(int key, int value) {
363 myKey = key;
364 myValue = value;
365 }
366
367 int getKey() {
368 return myKey;
369 }
370
371 int getValue() {
372 return myValue;
373 }
374
375 public int compareTo(Pair pair) {
403 for (UnsortedBuilder builder : UnsortedBuilder.values()) {
404 builder.build(golden, m, random);
405 int[] test = golden.clone();
406
407 for (TypeConverter converter : TypeConverter.values()) {
408 out.println("Test 'insertion sort': " + converter +
409 " " + builder + "random = " + random.getSeed() +
410 ", length = " + length + ", m = " + m);
411 Object convertedGolden = converter.convert(golden);
412 Object convertedTest1 = converter.convert(test);
413 Object convertedTest2 = converter.convert(test);
414 sort(convertedTest1);
415 sortByInsertionSort(convertedTest2);
416 compare(convertedTest1, convertedTest2);
417 }
418 }
419 }
420 out.println();
421 }
422
423 private static void testMergingSort(int length) {
424 if (length < 1000) {
425 return;
426 }
427 ourDescription = "Check merging sort";
428 int[] golden = new int[length];
429 final int period = 50;
430
431 for (int m = period - 2; m <= period + 2; m++) {
432 for (MergingBuilder builder : MergingBuilder.values()) {
433 builder.build(golden, m);
434 int[] test = golden.clone();
435
436 for (TypeConverter converter : TypeConverter.values()) {
437 out.println("Test 'merging sort': " + converter + " " +
438 builder + "length = " + length + ", m = " + m);
439 Object convertedGolden = converter.convert(golden);
440 sort(convertedGolden);
441 checkSorted(convertedGolden);
442 }
443 }
444 }
445 out.println();
446 }
447
448 private static void testAndCheckWithCheckSum(int length, MyRandom random) {
449 ourDescription = "Check sorting with check sum";
450 int[] golden = new int[length];
451
452 for (int m = 1; m < 2 * length; m *= 2) {
453 for (UnsortedBuilder builder : UnsortedBuilder.values()) {
454 builder.build(golden, m, random);
455 int[] test = golden.clone();
456
457 for (TypeConverter converter : TypeConverter.values()) {
481 int[] test = golden.clone();
482 scramble(test, random);
483
484 for (TypeConverter converter : TypeConverter.values()) {
485 out.println("Test 'scrambling': " + converter +
486 " " + builder + "random = " + random.getSeed() +
487 ", length = " + length + ", m = " + m);
488 Object convertedGolden = converter.convert(golden);
489 Object convertedTest = converter.convert(test);
490 sort(convertedTest);
491 compare(convertedTest, convertedGolden);
492 }
493 }
494 }
495 out.println();
496 }
497
498 private static void testAndCheckFloat(int length, MyRandom random) {
499 ourDescription = "Check float sorting";
500 float[] golden = new float[length];
501 boolean newLine = false;
502 final int MAX = 12;
503
504 for (int a = 0; a <= MAX; a++) {
505 for (int g = 0; g <= MAX; g++) {
506 for (int z = 0; z <= MAX; z++) {
507 for (int n = 0; n <= MAX; n++) {
508 for (int p = 0; p <= MAX; p++) {
509 if (a + g + z + n + p != length) {
510 continue;
511 }
512 for (FloatBuilder builder : FloatBuilder.values()) {
513 out.println("Test 'float': random = " + random.getSeed() +
514 ", length = " + length + ", a = " + a + ", g = " +
515 g + ", z = " + z + ", n = " + n + ", p = " + p);
516 builder.build(golden, a, g, z, n, p, random);
517 float[] test = golden.clone();
518 scramble(test, random);
519 sort(test);
520 compare(test, golden, a, n, g);
521 }
522 newLine = true;
523 }
524 }
525 }
526 }
527 }
528 if (newLine) {
529 out.println();
553 g + ", z = " + z + ", n = " + n + ", p = " + p);
554 builder.build(golden, a, g, z, n, p, random);
555 double[] test = golden.clone();
556 scramble(test, random);
557 sort(test);
558 compare(test, golden, a, n, g);
559 }
560 newLine = true;
561 }
562 }
563 }
564 }
565 }
566 if (newLine) {
567 out.println();
568 }
569 }
570
571 private static void prepareSubArray(int[] a, int fromIndex, int toIndex, int m) {
572 for (int i = 0; i < fromIndex; i++) {
573 a[i] = A380;
574 }
575 int middle = (fromIndex + toIndex) >>> 1;
576 int k = 0;
577
578 for (int i = fromIndex; i < middle; i++) {
579 a[i] = k++;
580 }
581 for (int i = middle; i < toIndex; i++) {
582 a[i] = k--;
583 }
584 for (int i = toIndex; i < a.length; i++) {
585 a[i] = B747;
586 }
587 }
588
589 private static void scramble(int[] a, Random random) {
590 for (int i = 0; i < a.length * 7; i++) {
591 swap(a, random.nextInt(a.length), random.nextInt(a.length));
592 }
593 }
594
595 private static void scramble(float[] a, Random random) {
596 for (int i = 0; i < a.length * 7; i++) {
597 swap(a, random.nextInt(a.length), random.nextInt(a.length));
598 }
599 }
600
601 private static void scramble(double[] a, Random random) {
602 for (int i = 0; i < a.length * 7; i++) {
603 swap(a, random.nextInt(a.length), random.nextInt(a.length));
604 }
605 }
676 b[i] = (float) a[i];
677 }
678 return b;
679 }
680 },
681 DOUBLE {
682 Object convert(int[] a) {
683 double[] b = new double[a.length];
684
685 for (int i = 0; i < a.length; i++) {
686 b[i] = (double) a[i];
687 }
688 return b;
689 }
690 },
691 INTEGER {
692 Object convert(int[] a) {
693 Integer[] b = new Integer[a.length];
694
695 for (int i = 0; i < a.length; i++) {
696 b[i] = Integer.valueOf(a[i]);
697 }
698 return b;
699 }
700 };
701
702 abstract Object convert(int[] a);
703
704 @Override
705 public String toString() {
706 String name = name();
707
708 for (int i = name.length(); i < 9; i++) {
709 name += " ";
710 }
711 return name;
712 }
713 }
714
715 private static enum FloatBuilder {
716 SIMPLE {
717 void build(float[] x, int a, int g, int z, int n, int p, Random random) {
718 int fromIndex = 0;
719 float negativeValue = -random.nextFloat();
720 float positiveValue = random.nextFloat();
721
722 writeValue(x, negativeValue, fromIndex, n);
723 fromIndex += n;
724
725 writeValue(x, -0.0f, fromIndex, g);
838 }
839 },
840 ORGAN_PIPES {
841 void build(int[] a, int m) {
842 int i = 0;
843 int k = m;
844
845 while (true) {
846 for (int t = 1; t <= m; t++) {
847 if (i >= a.length) {
848 return;
849 }
850 a[i++] = k;
851 }
852 }
853 }
854 };
855
856 abstract void build(int[] a, int m);
857
858 @Override
859 public String toString() {
860 String name = name();
861
862 for (int i = name.length(); i < 12; i++) {
863 name += " ";
864 }
865 return name;
866 }
867 }
868
869 private static enum MergingBuilder {
870 ASCENDING {
871 void build(int[] a, int m) {
872 int period = a.length / m;
873 int v = 1, i = 0;
874
875 for (int k = 0; k < m; k++) {
876 v = 1;
877 for (int p = 0; p < period; p++) {
878 a[i++] = v++;
879 }
880 }
881 for (int j = i; j < a.length - 1; j++) {
882 a[j] = v++;
883 }
884 a[a.length - 1] = 0;
885 }
886 },
887 DESCENDING {
888 void build(int[] a, int m) {
889 int period = a.length / m;
890 int v = -1, i = 0;
891
892 for (int k = 0; k < m; k++) {
893 v = -1;
894 for (int p = 0; p < period; p++) {
895 a[i++] = v--;
896 }
897 }
898 for (int j = i; j < a.length - 1; j++) {
899 a[j] = v--;
900 }
901 a[a.length - 1] = 0;
902 }
903 },
904 POINT {
905 void build(int[] a, int m) {
906 for (int i = 0; i < a.length; i++) {
907 a[i] = 0;
908 }
909 a[a.length / 2] = m;
910 }
911 },
912 LINE {
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, a.length - 1);
918 }
919 },
920 PEARL {
921 void build(int[] a, int m) {
922 for (int i = 0; i < a.length; i++) {
923 a[i] = i;
924 }
925 reverse(a, 0, 2);
926 }
927 },
928 RING {
929 void build(int[] a, int m) {
930 int k1 = a.length / 3;
931 int k2 = a.length / 3 * 2;
932 int level = a.length / 3;
933
934 for (int i = 0, k = level; i < k1; i++) {
935 a[i] = k--;
936 }
937 for (int i = k1; i < k2; i++) {
938 a[i] = 0;
939 }
940 for (int i = k2, k = level; i < a.length; i++) {
941 a[i] = k--;
942 }
943 }
944 };
945
946 abstract void build(int[] a, int m);
947
948 @Override
949 public String toString() {
950 String name = name();
951
952 for (int i = name.length(); i < 12; i++) {
953 name += " ";
954 }
955 return name;
956 }
957 }
958
959 private static void reverse(int[] a, int lo, int hi) {
960 for (--hi; lo < hi; ) {
961 int tmp = a[lo];
962 a[lo++] = a[hi];
963 a[hi--] = tmp;
964 }
965 }
966
967 private static enum UnsortedBuilder {
968 RANDOM {
969 void build(int[] a, int m, Random random) {
970 for (int i = 0; i < a.length; i++) {
971 a[i] = random.nextInt();
972 }
973 }
974 },
975 ASCENDING {
976 void build(int[] a, int m, Random random) {
977 for (int i = 0; i < a.length; i++) {
978 a[i] = m + i;
979 }
980 }
981 },
982 DESCENDING {
983 void build(int[] a, int m, Random random) {
984 for (int i = 0; i < a.length; i++) {
985 a[i] = a.length - m - i;
986 }
1053 }
1054 },
1055 PLATEAU {
1056 void build(int[] a, int m, Random random) {
1057 for (int i = 0; i < a.length; i++) {
1058 a[i] = Math.min(i, m);
1059 }
1060 }
1061 },
1062 SHUFFLE {
1063 void build(int[] a, int m, Random random) {
1064 int x = 0, y = 0;
1065 for (int i = 0; i < a.length; i++) {
1066 a[i] = random.nextBoolean() ? (x += 2) : (y += 2);
1067 }
1068 }
1069 };
1070
1071 abstract void build(int[] a, int m, Random random);
1072
1073 @Override
1074 public String toString() {
1075 String name = name();
1076
1077 for (int i = name.length(); i < 12; i++) {
1078 name += " ";
1079 }
1080 return name;
1081 }
1082 }
1083
1084 private static void checkWithCheckSum(Object test, Object golden) {
1085 checkSorted(test);
1086 checkCheckSum(test, golden);
1087 }
1088
1089 private static void failed(String message) {
1090 err.format("\n*** TEST FAILED - %s.\n\n%s.\n\n", ourDescription, message);
1091 throw new RuntimeException("Test failed - see log file for details");
1092 }
1093
1094 private static void failedSort(int index, String value1, String value2) {
1101 }
1102
1103 private static void compare(Object test, Object golden) {
1104 if (test instanceof int[]) {
1105 compare((int[]) test, (int[]) golden);
1106 } else if (test instanceof long[]) {
1107 compare((long[]) test, (long[]) golden);
1108 } else if (test instanceof short[]) {
1109 compare((short[]) test, (short[]) golden);
1110 } else if (test instanceof byte[]) {
1111 compare((byte[]) test, (byte[]) golden);
1112 } else if (test instanceof char[]) {
1113 compare((char[]) test, (char[]) golden);
1114 } else if (test instanceof float[]) {
1115 compare((float[]) test, (float[]) golden);
1116 } else if (test instanceof double[]) {
1117 compare((double[]) test, (double[]) golden);
1118 } else if (test instanceof Integer[]) {
1119 compare((Integer[]) test, (Integer[]) golden);
1120 } else {
1121 failed("Unknown type of array: " + test + " of class " +
1122 test.getClass().getName());
1123 }
1124 }
1125
1126 private static void compare(int[] a, int[] 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
1134 private static void compare(long[] a, long[] b) {
1135 for (int i = 0; i < a.length; i++) {
1136 if (a[i] != b[i]) {
1137 failedCompare(i, "" + a[i], "" + b[i]);
1138 }
1139 }
1140 }
1141
1188 }
1189
1190 private static void checkSorted(Object object) {
1191 if (object instanceof int[]) {
1192 checkSorted((int[]) object);
1193 } else if (object instanceof long[]) {
1194 checkSorted((long[]) object);
1195 } else if (object instanceof short[]) {
1196 checkSorted((short[]) object);
1197 } else if (object instanceof byte[]) {
1198 checkSorted((byte[]) object);
1199 } else if (object instanceof char[]) {
1200 checkSorted((char[]) object);
1201 } else if (object instanceof float[]) {
1202 checkSorted((float[]) object);
1203 } else if (object instanceof double[]) {
1204 checkSorted((double[]) object);
1205 } else if (object instanceof Integer[]) {
1206 checkSorted((Integer[]) object);
1207 } else {
1208 failed("Unknown type of array: " + object + " of class " +
1209 object.getClass().getName());
1210 }
1211 }
1212
1213 private static void checkSorted(int[] 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
1221 private static void checkSorted(long[] a) {
1222 for (int i = 0; i < a.length - 1; i++) {
1223 if (a[i] > a[i + 1]) {
1224 failedSort(i, "" + a[i], "" + a[i + 1]);
1225 }
1226 }
1227 }
1228
1284 }
1285
1286 private static int checkSumXor(Object object) {
1287 if (object instanceof int[]) {
1288 return checkSumXor((int[]) object);
1289 } else if (object instanceof long[]) {
1290 return checkSumXor((long[]) object);
1291 } else if (object instanceof short[]) {
1292 return checkSumXor((short[]) object);
1293 } else if (object instanceof byte[]) {
1294 return checkSumXor((byte[]) object);
1295 } else if (object instanceof char[]) {
1296 return checkSumXor((char[]) object);
1297 } else if (object instanceof float[]) {
1298 return checkSumXor((float[]) object);
1299 } else if (object instanceof double[]) {
1300 return checkSumXor((double[]) object);
1301 } else if (object instanceof Integer[]) {
1302 return checkSumXor((Integer[]) object);
1303 } else {
1304 failed("Unknown type of array: " + object + " of class " +
1305 object.getClass().getName());
1306 return -1;
1307 }
1308 }
1309
1310 private static int checkSumXor(Integer[] a) {
1311 int checkSum = 0;
1312
1313 for (Integer e : a) {
1314 checkSum ^= e.intValue();
1315 }
1316 return checkSum;
1317 }
1318
1319 private static int checkSumXor(int[] a) {
1320 int checkSum = 0;
1321
1322 for (int e : a) {
1323 checkSum ^= e;
1324 }
1380 }
1381
1382 private static int checkSumPlus(Object object) {
1383 if (object instanceof int[]) {
1384 return checkSumPlus((int[]) object);
1385 } else if (object instanceof long[]) {
1386 return checkSumPlus((long[]) object);
1387 } else if (object instanceof short[]) {
1388 return checkSumPlus((short[]) object);
1389 } else if (object instanceof byte[]) {
1390 return checkSumPlus((byte[]) object);
1391 } else if (object instanceof char[]) {
1392 return checkSumPlus((char[]) object);
1393 } else if (object instanceof float[]) {
1394 return checkSumPlus((float[]) object);
1395 } else if (object instanceof double[]) {
1396 return checkSumPlus((double[]) object);
1397 } else if (object instanceof Integer[]) {
1398 return checkSumPlus((Integer[]) object);
1399 } else {
1400 failed("Unknown type of array: " + object + " of class " +
1401 object.getClass().getName());
1402 return -1;
1403 }
1404 }
1405
1406 private static int checkSumPlus(int[] a) {
1407 int checkSum = 0;
1408
1409 for (int e : a) {
1410 checkSum += e;
1411 }
1412 return checkSum;
1413 }
1414
1415 private static int checkSumPlus(long[] a) {
1416 long checkSum = 0;
1417
1418 for (long e : a) {
1419 checkSum += e;
1420 }
1476 }
1477
1478 private static void sortByInsertionSort(Object object) {
1479 if (object instanceof int[]) {
1480 sortByInsertionSort((int[]) object);
1481 } else if (object instanceof long[]) {
1482 sortByInsertionSort((long[]) object);
1483 } else if (object instanceof short[]) {
1484 sortByInsertionSort((short[]) object);
1485 } else if (object instanceof byte[]) {
1486 sortByInsertionSort((byte[]) object);
1487 } else if (object instanceof char[]) {
1488 sortByInsertionSort((char[]) object);
1489 } else if (object instanceof float[]) {
1490 sortByInsertionSort((float[]) object);
1491 } else if (object instanceof double[]) {
1492 sortByInsertionSort((double[]) object);
1493 } else if (object instanceof Integer[]) {
1494 sortByInsertionSort((Integer[]) object);
1495 } else {
1496 failed("Unknown type of array: " + object + " of class " +
1497 object.getClass().getName());
1498 }
1499 }
1500
1501 private static void sortByInsertionSort(int[] a) {
1502 for (int j, i = 1; i < a.length; i++) {
1503 int ai = a[i];
1504 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1505 a[j + 1] = a[j];
1506 }
1507 a[j + 1] = ai;
1508 }
1509 }
1510
1511 private static void sortByInsertionSort(long[] a) {
1512 for (int j, i = 1; i < a.length; i++) {
1513 long ai = a[i];
1514 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1515 a[j + 1] = a[j];
1516 }
1579 }
1580
1581 private static void sort(Object object) {
1582 if (object instanceof int[]) {
1583 Arrays.parallelSort((int[]) object);
1584 } else if (object instanceof long[]) {
1585 Arrays.parallelSort((long[]) object);
1586 } else if (object instanceof short[]) {
1587 Arrays.parallelSort((short[]) object);
1588 } else if (object instanceof byte[]) {
1589 Arrays.parallelSort((byte[]) object);
1590 } else if (object instanceof char[]) {
1591 Arrays.parallelSort((char[]) object);
1592 } else if (object instanceof float[]) {
1593 Arrays.parallelSort((float[]) object);
1594 } else if (object instanceof double[]) {
1595 Arrays.parallelSort((double[]) object);
1596 } else if (object instanceof Integer[]) {
1597 Arrays.parallelSort((Integer[]) object);
1598 } else {
1599 failed("Unknown type of array: " + object + " of class " +
1600 object.getClass().getName());
1601 }
1602 }
1603
1604 private static void sortSubArray(Object object, int fromIndex, int toIndex) {
1605 if (object instanceof int[]) {
1606 Arrays.parallelSort((int[]) object, fromIndex, toIndex);
1607 } else if (object instanceof long[]) {
1608 Arrays.parallelSort((long[]) object, fromIndex, toIndex);
1609 } else if (object instanceof short[]) {
1610 Arrays.parallelSort((short[]) object, fromIndex, toIndex);
1611 } else if (object instanceof byte[]) {
1612 Arrays.parallelSort((byte[]) object, fromIndex, toIndex);
1613 } else if (object instanceof char[]) {
1614 Arrays.parallelSort((char[]) object, fromIndex, toIndex);
1615 } else if (object instanceof float[]) {
1616 Arrays.parallelSort((float[]) object, fromIndex, toIndex);
1617 } else if (object instanceof double[]) {
1618 Arrays.parallelSort((double[]) object, fromIndex, toIndex);
1619 } else if (object instanceof Integer[]) {
1620 Arrays.parallelSort((Integer[]) object, fromIndex, toIndex);
1621 } else {
1622 failed("Unknown type of array: " + object + " of class " +
1623 object.getClass().getName());
1624 }
1625 }
1626
1627 private static void checkSubArray(Object object, int fromIndex, int toIndex, int m) {
1628 if (object instanceof int[]) {
1629 checkSubArray((int[]) object, fromIndex, toIndex, m);
1630 } else if (object instanceof long[]) {
1631 checkSubArray((long[]) object, fromIndex, toIndex, m);
1632 } else if (object instanceof short[]) {
1633 checkSubArray((short[]) object, fromIndex, toIndex, m);
1634 } else if (object instanceof byte[]) {
1635 checkSubArray((byte[]) object, fromIndex, toIndex, m);
1636 } else if (object instanceof char[]) {
1637 checkSubArray((char[]) object, fromIndex, toIndex, m);
1638 } else if (object instanceof float[]) {
1639 checkSubArray((float[]) object, fromIndex, toIndex, m);
1640 } else if (object instanceof double[]) {
1641 checkSubArray((double[]) object, fromIndex, toIndex, m);
1642 } else if (object instanceof Integer[]) {
1643 checkSubArray((Integer[]) object, fromIndex, toIndex, m);
1644 } else {
1645 failed("Unknown type of array: " + object + " of class " +
1646 object.getClass().getName());
1647 }
1648 }
1649
1650 private static void checkSubArray(Integer[] a, int fromIndex, int toIndex, int m) {
1651 for (int i = 0; i < fromIndex; i++) {
1652 if (a[i].intValue() != A380) {
1653 failed("Range sort changes left element on position " + i +
1654 ": " + a[i] + ", must be " + A380);
1655 }
1656 }
1657
1658 for (int i = fromIndex; i < toIndex - 1; i++) {
1659 if (a[i].intValue() > a[i + 1].intValue()) {
1660 failedSort(i, "" + a[i], "" + a[i + 1]);
1661 }
1662 }
1663
1664 for (int i = toIndex; i < a.length; i++) {
1665 if (a[i].intValue() != B747) {
1666 failed("Range sort changes right element on position " + i +
1667 ": " + a[i] + ", must be " + B747);
1668 }
1669 }
1670 }
1671
1672 private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) {
1673 for (int i = 0; i < fromIndex; i++) {
1674 if (a[i] != A380) {
1675 failed("Range sort changes left element on position " + i +
1676 ": " + a[i] + ", must be " + A380);
1677 }
1678 }
1679
1680 for (int i = fromIndex; i < toIndex - 1; i++) {
1681 if (a[i] > a[i + 1]) {
1682 failedSort(i, "" + a[i], "" + a[i + 1]);
1683 }
1684 }
1685
1686 for (int i = toIndex; i < a.length; i++) {
1687 if (a[i] != B747) {
1688 failed("Range sort changes right element on position " + i +
1689 ": " + a[i] + ", must be " + B747);
1690 }
1691 }
1692 }
1693
1694 private static void checkSubArray(byte[] a, int fromIndex, int toIndex, int m) {
1695 for (int i = 0; i < fromIndex; i++) {
1696 if (a[i] != (byte) A380) {
1697 failed("Range sort changes left element on position " + i +
1698 ": " + a[i] + ", must be " + A380);
1699 }
1700 }
1701
1702 for (int i = fromIndex; i < toIndex - 1; i++) {
1703 if (a[i] > a[i + 1]) {
1704 failedSort(i, "" + a[i], "" + a[i + 1]);
1705 }
1706 }
1707
1708 for (int i = toIndex; i < a.length; i++) {
1709 if (a[i] != (byte) B747) {
1710 failed("Range sort changes right element on position " + i +
1711 ": " + a[i] + ", must be " + B747);
1712 }
1713 }
1714 }
1715
1716 private static void checkSubArray(long[] a, int fromIndex, int toIndex, int m) {
1717 for (int i = 0; i < fromIndex; i++) {
1718 if (a[i] != (long) A380) {
1719 failed("Range sort changes left element on position " + i +
1720 ": " + a[i] + ", must be " + A380);
1721 }
1722 }
1723
1724 for (int i = fromIndex; i < toIndex - 1; i++) {
1725 if (a[i] > a[i + 1]) {
1726 failedSort(i, "" + a[i], "" + a[i + 1]);
1727 }
1728 }
1729
1730 for (int i = toIndex; i < a.length; i++) {
1731 if (a[i] != (long) B747) {
1732 failed("Range sort changes right element on position " + i +
1733 ": " + a[i] + ", must be " + B747);
1734 }
1735 }
1736 }
1737
1738 private static void checkSubArray(char[] a, int fromIndex, int toIndex, int m) {
1739 for (int i = 0; i < fromIndex; i++) {
1740 if (a[i] != (char) A380) {
1741 failed("Range sort changes left element on position " + i +
1742 ": " + a[i] + ", must be " + A380);
1743 }
1744 }
1745
1746 for (int i = fromIndex; i < toIndex - 1; i++) {
1747 if (a[i] > a[i + 1]) {
1748 failedSort(i, "" + a[i], "" + a[i + 1]);
1749 }
1750 }
1751
1752 for (int i = toIndex; i < a.length; i++) {
1753 if (a[i] != (char) B747) {
1754 failed("Range sort changes right element on position " + i +
1755 ": " + a[i] + ", must be " + B747);
1756 }
1757 }
1758 }
1759
1760 private static void checkSubArray(short[] a, int fromIndex, int toIndex, int m) {
1761 for (int i = 0; i < fromIndex; i++) {
1762 if (a[i] != (short) A380) {
1763 failed("Range sort changes left element on position " + i +
1764 ": " + a[i] + ", must be " + A380);
1765 }
1766 }
1767
1768 for (int i = fromIndex; i < toIndex - 1; i++) {
1769 if (a[i] > a[i + 1]) {
1770 failedSort(i, "" + a[i], "" + a[i + 1]);
1771 }
1772 }
1773
1774 for (int i = toIndex; i < a.length; i++) {
1775 if (a[i] != (short) B747) {
1776 failed("Range sort changes right element on position " + i +
1777 ": " + a[i] + ", must be " + B747);
1778 }
1779 }
1780 }
1781
1782 private static void checkSubArray(float[] a, int fromIndex, int toIndex, int m) {
1783 for (int i = 0; i < fromIndex; i++) {
1784 if (a[i] != (float) A380) {
1785 failed("Range sort changes left element on position " + i +
1786 ": " + a[i] + ", must be " + A380);
1787 }
1788 }
1789
1790 for (int i = fromIndex; i < toIndex - 1; i++) {
1791 if (a[i] > a[i + 1]) {
1792 failedSort(i, "" + a[i], "" + a[i + 1]);
1793 }
1794 }
1795
1796 for (int i = toIndex; i < a.length; i++) {
1797 if (a[i] != (float) B747) {
1798 failed("Range sort changes right element on position " + i +
1799 ": " + a[i] + ", must be " + B747);
1800 }
1801 }
1802 }
1803
1804 private static void checkSubArray(double[] a, int fromIndex, int toIndex, int m) {
1805 for (int i = 0; i < fromIndex; i++) {
1806 if (a[i] != (double) A380) {
1807 failed("Range sort changes left element on position " + i +
1808 ": " + a[i] + ", must be " + A380);
1809 }
1810 }
1811
1812 for (int i = fromIndex; i < toIndex - 1; i++) {
1813 if (a[i] > a[i + 1]) {
1814 failedSort(i, "" + a[i], "" + a[i + 1]);
1815 }
1816 }
1817
1818 for (int i = toIndex; i < a.length; i++) {
1819 if (a[i] != (double) B747) {
1820 failed("Range sort changes right element on position " + i +
1821 ": " + a[i] + ", must be " + B747);
1822 }
1823 }
1824 }
1825
1826 private static void checkRange(Object object, int m) {
1827 if (object instanceof int[]) {
1828 checkRange((int[]) object, m);
1829 } else if (object instanceof long[]) {
1830 checkRange((long[]) object, m);
1831 } else if (object instanceof short[]) {
1832 checkRange((short[]) object, m);
1833 } else if (object instanceof byte[]) {
1834 checkRange((byte[]) object, m);
1835 } else if (object instanceof char[]) {
1836 checkRange((char[]) object, m);
1837 } else if (object instanceof float[]) {
1838 checkRange((float[]) object, m);
1839 } else if (object instanceof double[]) {
1840 checkRange((double[]) object, m);
1841 } else if (object instanceof Integer[]) {
1842 checkRange((Integer[]) object, m);
1843 } else {
1844 failed("Unknown type of array: " + object + " of class " +
1845 object.getClass().getName());
1846 }
1847 }
1848
1849 private static void checkRange(Integer[] a, int m) {
1850 try {
1851 Arrays.parallelSort(a, m + 1, m);
1852
1853 failed("Arrays.parallelSort does not throw IllegalArgumentException " +
1854 " as expected: fromIndex = " + (m + 1) +
1855 " toIndex = " + m);
1856 }
1857 catch (IllegalArgumentException iae) {
1858 try {
1859 Arrays.parallelSort(a, -m, a.length);
1860
1861 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
1862 " as expected: fromIndex = " + (-m));
1863 }
1864 catch (ArrayIndexOutOfBoundsException aoe) {
1865 try {
1866 Arrays.parallelSort(a, 0, a.length + m);
1867
1868 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
1869 " as expected: toIndex = " + (a.length + m));
1870 }
1871 catch (ArrayIndexOutOfBoundsException aie) {
1872 return;
1873 }
1874 }
1875 }
1876 }
1877
1878 private static void checkRange(int[] a, int m) {
1879 try {
1880 Arrays.parallelSort(a, m + 1, m);
1881
1882 failed("Arrays.parallelSort does not throw IllegalArgumentException " +
1883 " as expected: fromIndex = " + (m + 1) +
1884 " toIndex = " + m);
1885 }
1886 catch (IllegalArgumentException iae) {
1887 try {
1888 Arrays.parallelSort(a, -m, a.length);
1889
1890 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
1891 " as expected: fromIndex = " + (-m));
1892 }
1893 catch (ArrayIndexOutOfBoundsException aoe) {
1894 try {
1895 Arrays.parallelSort(a, 0, a.length + m);
1896
1897 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
1898 " as expected: toIndex = " + (a.length + m));
1899 }
1900 catch (ArrayIndexOutOfBoundsException aie) {
1901 return;
1902 }
1903 }
1904 }
1905 }
1906
1907 private static void checkRange(long[] a, int m) {
1908 try {
1909 Arrays.parallelSort(a, m + 1, m);
1910
1911 failed("Arrays.parallelSort does not throw IllegalArgumentException " +
1912 " as expected: fromIndex = " + (m + 1) +
1913 " toIndex = " + m);
1914 }
1915 catch (IllegalArgumentException iae) {
1916 try {
1917 Arrays.parallelSort(a, -m, a.length);
1918
1919 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
1920 " as expected: fromIndex = " + (-m));
1921 }
1922 catch (ArrayIndexOutOfBoundsException aoe) {
1923 try {
1924 Arrays.parallelSort(a, 0, a.length + m);
1925
1926 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
1927 " as expected: toIndex = " + (a.length + m));
1928 }
1929 catch (ArrayIndexOutOfBoundsException aie) {
1930 return;
1931 }
1932 }
1933 }
1934 }
1935
1936 private static void checkRange(byte[] a, int m) {
1937 try {
1938 Arrays.parallelSort(a, m + 1, m);
1939
1940 failed("Arrays.parallelSort does not throw IllegalArgumentException " +
1941 " as expected: fromIndex = " + (m + 1) +
1942 " toIndex = " + m);
1943 }
1944 catch (IllegalArgumentException iae) {
1945 try {
1946 Arrays.parallelSort(a, -m, a.length);
1947
1948 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
1949 " as expected: fromIndex = " + (-m));
1950 }
1951 catch (ArrayIndexOutOfBoundsException aoe) {
1952 try {
1953 Arrays.parallelSort(a, 0, a.length + m);
1954
1955 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
1956 " as expected: toIndex = " + (a.length + m));
1957 }
1958 catch (ArrayIndexOutOfBoundsException aie) {
1959 return;
1960 }
1961 }
1962 }
1963 }
1964
1965 private static void checkRange(short[] a, int m) {
1966 try {
1967 Arrays.parallelSort(a, m + 1, m);
1968
1969 failed("Arrays.parallelSort does not throw IllegalArgumentException " +
1970 " as expected: fromIndex = " + (m + 1) +
1971 " toIndex = " + m);
1972 }
1973 catch (IllegalArgumentException iae) {
1974 try {
1975 Arrays.parallelSort(a, -m, a.length);
1976
1977 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
1978 " as expected: fromIndex = " + (-m));
1979 }
1980 catch (ArrayIndexOutOfBoundsException aoe) {
1981 try {
1982 Arrays.parallelSort(a, 0, a.length + m);
1983
1984 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
1985 " as expected: toIndex = " + (a.length + m));
1986 }
1987 catch (ArrayIndexOutOfBoundsException aie) {
1988 return;
1989 }
1990 }
1991 }
1992 }
1993
1994 private static void checkRange(char[] a, int m) {
1995 try {
1996 Arrays.parallelSort(a, m + 1, m);
1997
1998 failed("Arrays.parallelSort does not throw IllegalArgumentException " +
1999 " as expected: fromIndex = " + (m + 1) +
2000 " toIndex = " + m);
2001 }
2002 catch (IllegalArgumentException iae) {
2003 try {
2004 Arrays.parallelSort(a, -m, a.length);
2005
2006 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
2007 " as expected: fromIndex = " + (-m));
2008 }
2009 catch (ArrayIndexOutOfBoundsException aoe) {
2010 try {
2011 Arrays.parallelSort(a, 0, a.length + m);
2012
2013 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
2014 " as expected: toIndex = " + (a.length + m));
2015 }
2016 catch (ArrayIndexOutOfBoundsException aie) {
2017 return;
2018 }
2019 }
2020 }
2021 }
2022
2023 private static void checkRange(float[] a, int m) {
2024 try {
2025 Arrays.parallelSort(a, m + 1, m);
2026
2027 failed("Arrays.parallelSort does not throw IllegalArgumentException " +
2028 " as expected: fromIndex = " + (m + 1) +
2029 " toIndex = " + m);
2030 }
2031 catch (IllegalArgumentException iae) {
2032 try {
2033 Arrays.parallelSort(a, -m, a.length);
2034
2035 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
2036 " as expected: fromIndex = " + (-m));
2037 }
2038 catch (ArrayIndexOutOfBoundsException aoe) {
2039 try {
2040 Arrays.parallelSort(a, 0, a.length + m);
2041
2042 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
2043 " as expected: toIndex = " + (a.length + m));
2044 }
2045 catch (ArrayIndexOutOfBoundsException aie) {
2046 return;
2047 }
2048 }
2049 }
2050 }
2051
2052 private static void checkRange(double[] a, int m) {
2053 try {
2054 Arrays.parallelSort(a, m + 1, m);
2055
2056 failed("Arrays.parallelSort does not throw IllegalArgumentException " +
2057 " as expected: fromIndex = " + (m + 1) +
2058 " toIndex = " + m);
2059 }
2060 catch (IllegalArgumentException iae) {
2061 try {
2062 Arrays.parallelSort(a, -m, a.length);
2063
2064 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
2065 " as expected: fromIndex = " + (-m));
2066 }
2067 catch (ArrayIndexOutOfBoundsException aoe) {
2068 try {
2069 Arrays.parallelSort(a, 0, a.length + m);
2070
2071 failed("Arrays.parallelSort does not throw ArrayIndexOutOfBoundsException " +
2072 " as expected: toIndex = " + (a.length + m));
2073 }
2074 catch (ArrayIndexOutOfBoundsException aie) {
2075 return;
2076 }
2077 }
2078 }
2079 }
2080
2081 private static void outArray(Object[] a) {
2082 for (int i = 0; i < a.length; i++) {
2083 out.print(a[i] + " ");
2084 }
2085 out.println();
2086 }
2087
2088 private static void outArray(int[] a) {
2089 for (int i = 0; i < a.length; i++) {
2090 out.print(a[i] + " ");
2091 }
|