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
250 for (int m = 1; m < length / 2; m *= 2) {
251 newLine = true;
252 int fromIndex = m;
253 int toIndex = length - m;
254
255 prepareSubArray(golden, fromIndex, toIndex, m);
256 int[] test = golden.clone();
257
258 for (TypeConverter converter : TypeConverter.values()) {
259 out.println("Test 'subarray': " + converter +
260 " length = " + length + ", m = " + m);
261 Object convertedGolden = converter.convert(golden);
262 Object convertedTest = converter.convert(test);
263 sortSubArray(convertedTest, fromIndex, toIndex);
264 checkSubArray(convertedTest, fromIndex, toIndex, m);
265 }
266 }
267 if (newLine) {
268 out.println();
269 }
270 }
271
272 private static void testAndCheckRange(int length) {
273 ourDescription = "Check range check";
274 int[] golden = new int[length];
275
276 for (int m = 1; m < 2 * length; m *= 2) {
277 for (int i = 1; i <= length; i++) {
278 golden[i - 1] = i % m + m % i;
279 }
280 for (TypeConverter converter : TypeConverter.values()) {
281 out.println("Test 'range': " + converter +
282 ", length = " + length + ", m = " + m);
283 Object convertedGolden = converter.convert(golden);
284 checkRange(convertedGolden, m);
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();
329
330 if (!(key1 == key2 && key2 == key3 && key3 == key4)) {
331 failed("On position " + i + " keys are different " +
332 key1 + ", " + key2 + ", " + key3 + ", " + key4);
333 }
334 if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
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) {
376 if (myKey < pair.myKey) {
377 return -1;
378 }
379 if (myKey > pair.myKey) {
380 return 1;
381 }
382 return 0;
383 }
384
385 @Override
386 public String toString() {
387 return "(" + myKey + ", " + myValue + ")";
388 }
389
390 private int myKey;
391 private int myValue;
392 }
393
394
395 private static void testAndCheckWithInsertionSort(int length, MyRandom random) {
396 if (length > 1000) {
397 return;
398 }
399 ourDescription = "Check sorting with insertion sort";
400 int[] golden = new int[length];
401
402 for (int m = 1; m < 2 * length; m *= 2) {
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()) {
458 out.println("Test 'check sum': " + converter +
459 " " + builder + "random = " + random.getSeed() +
460 ", length = " + length + ", m = " + m);
461 Object convertedGolden = converter.convert(golden);
462 Object convertedTest = converter.convert(test);
463 sort(convertedTest);
464 checkWithCheckSum(convertedTest, convertedGolden);
465 }
466 }
467 }
468 out.println();
469 }
470
471 private static void testAndCheckWithScrambling(int length, MyRandom random) {
472 ourDescription = "Check sorting with scrambling";
473 int[] golden = new int[length];
474
475 for (int m = 1; m <= 7; m++) {
476 if (m > length) {
477 break;
478 }
479 for (SortedBuilder builder : SortedBuilder.values()) {
480 builder.build(golden, m);
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();
530 }
531 }
532
533 private static void testAndCheckDouble(int length, MyRandom random) {
534 ourDescription = "Check double sorting";
535 double[] golden = new double[length];
536 final int MAX = 10;
537 boolean newLine = false;
538
539 for (int a = 0; a <= MAX; a++) {
540 for (int g = 0; g <= MAX; g++) {
541 for (int z = 0; z <= MAX; z++) {
542 for (int n = 0; n <= MAX; n++) {
543 for (int p = 0; p <= MAX; p++) {
544 if (a + g + z + n + p > length) {
545 continue;
546 }
547 if (a + g + z + n + p < length) {
548 continue;
549 }
550 for (DoubleBuilder builder : DoubleBuilder.values()) {
551 out.println("Test 'double': random = " + random.getSeed() +
552 ", length = " + length + ", a = " + a + ", g = " +
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 }
606
607 private static void swap(int[] a, int i, int j) {
608 int t = a[i];
609 a[i] = a[j];
610 a[j] = t;
611 }
612
613 private static void swap(float[] a, int i, int j) {
614 float t = a[i];
615 a[i] = a[j];
616 a[j] = t;
617 }
618
619 private static void swap(double[] a, int i, int j) {
620 double t = a[i];
621 a[i] = a[j];
622 a[j] = t;
623 }
624
625 private static enum TypeConverter {
626 INT {
627 Object convert(int[] a) {
628 return a.clone();
629 }
630 },
631 LONG {
632 Object convert(int[] a) {
633 long[] b = new long[a.length];
634
635 for (int i = 0; i < a.length; i++) {
636 b[i] = (long) a[i];
637 }
638 return b;
639 }
640 },
641 BYTE {
642 Object convert(int[] a) {
643 byte[] b = new byte[a.length];
644
645 for (int i = 0; i < a.length; i++) {
646 b[i] = (byte) a[i];
647 }
648 return b;
649 }
650 },
651 SHORT {
652 Object convert(int[] a) {
653 short[] b = new short[a.length];
654
655 for (int i = 0; i < a.length; i++) {
656 b[i] = (short) a[i];
657 }
658 return b;
659 }
660 },
661 CHAR {
662 Object convert(int[] a) {
663 char[] b = new char[a.length];
664
665 for (int i = 0; i < a.length; i++) {
666 b[i] = (char) a[i];
667 }
668 return b;
669 }
670 },
671 FLOAT {
672 Object convert(int[] a) {
673 float[] b = new float[a.length];
674
675 for (int i = 0; i < a.length; i++) {
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);
726 fromIndex += g;
727
728 writeValue(x, 0.0f, fromIndex, z);
729 fromIndex += z;
730
731 writeValue(x, positiveValue, fromIndex, p);
732 fromIndex += p;
733
734 writeValue(x, Float.NaN, fromIndex, a);
735 }
736 };
737
738 abstract void build(float[] x, int a, int g, int z, int n, int p, Random random);
739 }
740
741 private static enum DoubleBuilder {
742 SIMPLE {
743 void build(double[] x, int a, int g, int z, int n, int p, Random random) {
744 int fromIndex = 0;
745 double negativeValue = -random.nextFloat();
746 double positiveValue = random.nextFloat();
747
748 writeValue(x, negativeValue, fromIndex, n);
749 fromIndex += n;
750
751 writeValue(x, -0.0d, fromIndex, g);
752 fromIndex += g;
753
754 writeValue(x, 0.0d, fromIndex, z);
755 fromIndex += z;
756
757 writeValue(x, positiveValue, fromIndex, p);
758 fromIndex += p;
759
760 writeValue(x, Double.NaN, fromIndex, a);
761 }
762 };
763
764 abstract void build(double[] x, int a, int g, int z, int n, int p, Random random);
765 }
766
767 private static void writeValue(float[] a, float value, int fromIndex, int count) {
768 for (int i = fromIndex; i < fromIndex + count; i++) {
769 a[i] = value;
770 }
771 }
772
773 private static void compare(float[] a, float[] b, int numNaN, int numNeg, int numNegZero) {
774 for (int i = a.length - numNaN; i < a.length; i++) {
775 if (a[i] == a[i]) {
776 failed("On position " + i + " must be NaN instead of " + a[i]);
777 }
778 }
779 final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
780
781 for (int i = numNeg; i < numNeg + numNegZero; i++) {
782 if (NEGATIVE_ZERO != Float.floatToIntBits(a[i])) {
783 failed("On position " + i + " must be -0.0 instead of " + a[i]);
784 }
785 }
786 for (int i = 0; i < a.length - numNaN; i++) {
787 if (a[i] != b[i]) {
788 failedCompare(i, "" + a[i], "" + b[i]);
789 }
790 }
791 }
792
793 private static void writeValue(double[] a, double value, int fromIndex, int count) {
794 for (int i = fromIndex; i < fromIndex + count; i++) {
795 a[i] = value;
796 }
797 }
798
799 private static void compare(double[] a, double[] b, int numNaN, int numNeg, int numNegZero) {
800 for (int i = a.length - numNaN; i < a.length; i++) {
801 if (a[i] == a[i]) {
802 failed("On position " + i + " must be NaN instead of " + a[i]);
803 }
804 }
805 final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
806
807 for (int i = numNeg; i < numNeg + numNegZero; i++) {
808 if (NEGATIVE_ZERO != Double.doubleToLongBits(a[i])) {
809 failed("On position " + i + " must be -0.0 instead of " + a[i]);
810 }
811 }
812 for (int i = 0; i < a.length - numNaN; i++) {
813 if (a[i] != b[i]) {
814 failedCompare(i, "" + a[i], "" + b[i]);
815 }
816 }
817 }
818
819 private static enum SortedBuilder {
820 REPEATED {
821 void build(int[] a, int m) {
822 int period = a.length / m;
823 int i = 0;
824 int k = 0;
825
826 while (true) {
827 for (int t = 1; t <= period; t++) {
828 if (i >= a.length) {
829 return;
830 }
831 a[i++] = k;
832 }
833 if (i >= a.length) {
834 return;
835 }
836 k++;
837 }
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 }
987 }
988 },
989 ALL_EQUAL {
990 void build(int[] a, int m, Random random) {
991 for (int i = 0; i < a.length; i++) {
992 a[i] = m;
993 }
994 }
995 },
996 SAW {
997 void build(int[] a, int m, Random random) {
998 int incCount = 1;
999 int decCount = a.length;
1000 int i = 0;
1001 int period = m--;
1002
1003 while (true) {
1004 for (int k = 1; k <= period; k++) {
1005 if (i >= a.length) {
1006 return;
1007 }
1008 a[i++] = incCount++;
1009 }
1010 period += m;
1011
1012 for (int k = 1; k <= period; k++) {
1013 if (i >= a.length) {
1014 return;
1015 }
1016 a[i++] = decCount--;
1017 }
1018 period += m;
1019 }
1020 }
1021 },
1022 REPEATED {
1023 void build(int[] a, int m, Random random) {
1024 for (int i = 0; i < a.length; i++) {
1025 a[i] = i % m;
1026 }
1027 }
1028 },
1029 DUPLICATED {
1030 void build(int[] a, int m, Random random) {
1031 for (int i = 0; i < a.length; i++) {
1032 a[i] = random.nextInt(m);
1033 }
1034 }
1035 },
1036 ORGAN_PIPES {
1037 void build(int[] a, int m, Random random) {
1038 int middle = a.length / (m + 1);
1039
1040 for (int i = 0; i < middle; i++) {
1041 a[i] = i;
1042 }
1043 for (int i = middle; i < a.length; i++) {
1044 a[i] = a.length - i - 1;
1045 }
1046 }
1047 },
1048 STAGGER {
1049 void build(int[] a, int m, Random random) {
1050 for (int i = 0; i < a.length; i++) {
1051 a[i] = (i * m + i) % a.length;
1052 }
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) {
1095 failed("Array is not sorted at " + index + "-th position: " +
1096 value1 + " and " + value2);
1097 }
1098
1099 private static void failedCompare(int index, String value1, String value2) {
1100 failed("On position " + index + " must be " + value2 + " instead of " + value1);
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
1142 private static void compare(short[] a, short[] b) {
1143 for (int i = 0; i < a.length; i++) {
1144 if (a[i] != b[i]) {
1145 failedCompare(i, "" + a[i], "" + b[i]);
1146 }
1147 }
1148 }
1149
1150 private static void compare(byte[] a, byte[] b) {
1151 for (int i = 0; i < a.length; i++) {
1152 if (a[i] != b[i]) {
1153 failedCompare(i, "" + a[i], "" + b[i]);
1154 }
1155 }
1156 }
1157
1158 private static void compare(char[] a, char[] b) {
1159 for (int i = 0; i < a.length; i++) {
1160 if (a[i] != b[i]) {
1161 failedCompare(i, "" + a[i], "" + b[i]);
1162 }
1163 }
1164 }
1165
1166 private static void compare(float[] a, float[] b) {
1167 for (int i = 0; i < a.length; i++) {
1168 if (a[i] != b[i]) {
1169 failedCompare(i, "" + a[i], "" + b[i]);
1170 }
1171 }
1172 }
1173
1174 private static void compare(double[] a, double[] b) {
1175 for (int i = 0; i < a.length; i++) {
1176 if (a[i] != b[i]) {
1177 failedCompare(i, "" + a[i], "" + b[i]);
1178 }
1179 }
1180 }
1181
1182 private static void compare(Integer[] a, Integer[] b) {
1183 for (int i = 0; i < a.length; i++) {
1184 if (a[i].compareTo(b[i]) != 0) {
1185 failedCompare(i, "" + a[i], "" + b[i]);
1186 }
1187 }
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
1229 private static void checkSorted(short[] a) {
1230 for (int i = 0; i < a.length - 1; i++) {
1231 if (a[i] > a[i + 1]) {
1232 failedSort(i, "" + a[i], "" + a[i + 1]);
1233 }
1234 }
1235 }
1236
1237 private static void checkSorted(byte[] a) {
1238 for (int i = 0; i < a.length - 1; i++) {
1239 if (a[i] > a[i + 1]) {
1240 failedSort(i, "" + a[i], "" + a[i + 1]);
1241 }
1242 }
1243 }
1244
1245 private static void checkSorted(char[] a) {
1246 for (int i = 0; i < a.length - 1; i++) {
1247 if (a[i] > a[i + 1]) {
1248 failedSort(i, "" + a[i], "" + a[i + 1]);
1249 }
1250 }
1251 }
1252
1253 private static void checkSorted(float[] a) {
1254 for (int i = 0; i < a.length - 1; i++) {
1255 if (a[i] > a[i + 1]) {
1256 failedSort(i, "" + a[i], "" + a[i + 1]);
1257 }
1258 }
1259 }
1260
1261 private static void checkSorted(double[] a) {
1262 for (int i = 0; i < a.length - 1; i++) {
1263 if (a[i] > a[i + 1]) {
1264 failedSort(i, "" + a[i], "" + a[i + 1]);
1265 }
1266 }
1267 }
1268
1269 private static void checkSorted(Integer[] a) {
1270 for (int i = 0; i < a.length - 1; i++) {
1271 if (a[i].intValue() > a[i + 1].intValue()) {
1272 failedSort(i, "" + a[i], "" + a[i + 1]);
1273 }
1274 }
1275 }
1276
1277 private static void checkCheckSum(Object test, Object golden) {
1278 if (checkSumXor(test) != checkSumXor(golden)) {
1279 failed("Original and sorted arrays are not identical [xor]");
1280 }
1281 if (checkSumPlus(test) != checkSumPlus(golden)) {
1282 failed("Original and sorted arrays are not identical [plus]");
1283 }
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 }
1325 return checkSum;
1326 }
1327
1328 private static int checkSumXor(long[] a) {
1329 long checkSum = 0;
1330
1331 for (long e : a) {
1332 checkSum ^= e;
1333 }
1334 return (int) checkSum;
1335 }
1336
1337 private static int checkSumXor(short[] a) {
1338 short checkSum = 0;
1339
1340 for (short e : a) {
1341 checkSum ^= e;
1342 }
1343 return (int) checkSum;
1344 }
1345
1346 private static int checkSumXor(byte[] a) {
1347 byte checkSum = 0;
1348
1349 for (byte e : a) {
1350 checkSum ^= e;
1351 }
1352 return (int) checkSum;
1353 }
1354
1355 private static int checkSumXor(char[] a) {
1356 char checkSum = 0;
1357
1358 for (char e : a) {
1359 checkSum ^= e;
1360 }
1361 return (int) checkSum;
1362 }
1363
1364 private static int checkSumXor(float[] a) {
1365 int checkSum = 0;
1366
1367 for (float e : a) {
1368 checkSum ^= (int) e;
1369 }
1370 return checkSum;
1371 }
1372
1373 private static int checkSumXor(double[] a) {
1374 int checkSum = 0;
1375
1376 for (double e : a) {
1377 checkSum ^= (int) e;
1378 }
1379 return checkSum;
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 }
1421 return (int) checkSum;
1422 }
1423
1424 private static int checkSumPlus(short[] a) {
1425 short checkSum = 0;
1426
1427 for (short e : a) {
1428 checkSum += e;
1429 }
1430 return (int) checkSum;
1431 }
1432
1433 private static int checkSumPlus(byte[] a) {
1434 byte checkSum = 0;
1435
1436 for (byte e : a) {
1437 checkSum += e;
1438 }
1439 return (int) checkSum;
1440 }
1441
1442 private static int checkSumPlus(char[] a) {
1443 char checkSum = 0;
1444
1445 for (char e : a) {
1446 checkSum += e;
1447 }
1448 return (int) checkSum;
1449 }
1450
1451 private static int checkSumPlus(float[] a) {
1452 int checkSum = 0;
1453
1454 for (float e : a) {
1455 checkSum += (int) e;
1456 }
1457 return checkSum;
1458 }
1459
1460 private static int checkSumPlus(double[] a) {
1461 int checkSum = 0;
1462
1463 for (double e : a) {
1464 checkSum += (int) e;
1465 }
1466 return checkSum;
1467 }
1468
1469 private static int checkSumPlus(Integer[] a) {
1470 int checkSum = 0;
1471
1472 for (Integer e : a) {
1473 checkSum += e.intValue();
1474 }
1475 return checkSum;
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 }
1517 a[j + 1] = ai;
1518 }
1519 }
1520
1521 private static void sortByInsertionSort(short[] a) {
1522 for (int j, i = 1; i < a.length; i++) {
1523 short ai = a[i];
1524 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1525 a[j + 1] = a[j];
1526 }
1527 a[j + 1] = ai;
1528 }
1529 }
1530
1531 private static void sortByInsertionSort(byte[] a) {
1532 for (int j, i = 1; i < a.length; i++) {
1533 byte ai = a[i];
1534 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1535 a[j + 1] = a[j];
1536 }
1537 a[j + 1] = ai;
1538 }
1539 }
1540
1541 private static void sortByInsertionSort(char[] a) {
1542 for (int j, i = 1; i < a.length; i++) {
1543 char ai = a[i];
1544 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1545 a[j + 1] = a[j];
1546 }
1547 a[j + 1] = ai;
1548 }
1549 }
1550
1551 private static void sortByInsertionSort(float[] a) {
1552 for (int j, i = 1; i < a.length; i++) {
1553 float ai = a[i];
1554 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1555 a[j + 1] = a[j];
1556 }
1557 a[j + 1] = ai;
1558 }
1559 }
1560
1561 private static void sortByInsertionSort(double[] a) {
1562 for (int j, i = 1; i < a.length; i++) {
1563 double ai = a[i];
1564 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1565 a[j + 1] = a[j];
1566 }
1567 a[j + 1] = ai;
1568 }
1569 }
1570
1571 private static void sortByInsertionSort(Integer[] a) {
1572 for (int j, i = 1; i < a.length; i++) {
1573 Integer ai = a[i];
1574 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1575 a[j + 1] = a[j];
1576 }
1577 a[j + 1] = ai;
1578 }
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 }
2092 out.println();
2093 }
2094
2095 private static void outArray(float[] a) {
2096 for (int i = 0; i < a.length; i++) {
2097 out.print(a[i] + " ");
2098 }
2099 out.println();
2100 }
2101
2102 private static void outArray(double[] a) {
2103 for (int i = 0; i < a.length; i++) {
2104 out.print(a[i] + " ");
2105 }
2106 out.println();
2107 }
2108
2109 private static class MyRandom extends Random {
2110 MyRandom(long seed) {
2111 super(seed);
2112 mySeed = seed;
2113 }
2114
2115 long getSeed() {
2116 return mySeed;
2117 }
2118
2119 private long mySeed;
2120 }
2121
2122 private static String ourDescription;
2123 }