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
243 for (int m = 1; m < length / 2; m *= 2) {
244 newLine = true;
245 int fromIndex = m;
246 int toIndex = length - m;
247
248 prepareSubArray(golden, fromIndex, toIndex, m);
249 int[] test = golden.clone();
250
251 for (TypeConverter converter : TypeConverter.values()) {
252 out.println("Test 'subarray': " + converter +
253 " length = " + length + ", m = " + m);
254 Object convertedGolden = converter.convert(golden);
255 Object convertedTest = converter.convert(test);
256 sortSubArray(convertedTest, fromIndex, toIndex);
257 checkSubArray(convertedTest, fromIndex, toIndex, m);
258 }
259 }
260 if (newLine) {
261 out.println();
262 }
263 }
264
265 private static void testAndCheckRange(int length) {
266 ourDescription = "Check range check";
267 int[] golden = new int[length];
268
269 for (int m = 1; m < 2 * length; m *= 2) {
270 for (int i = 1; i <= length; i++) {
271 golden[i - 1] = i % m + m % i;
272 }
273 for (TypeConverter converter : TypeConverter.values()) {
274 out.println("Test 'range': " + converter +
275 ", length = " + length + ", m = " + m);
276 Object convertedGolden = converter.convert(golden);
277 checkRange(convertedGolden, m);
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();
323
324 if (!(key1 == key2 && key2 == key3 && key3 == key4)) {
325 failed("On position " + i + " keys are different " +
326 key1 + ", " + key2 + ", " + key3 + ", " + key4);
327 }
328 if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
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) {
370 if (myKey < pair.myKey) {
371 return -1;
372 }
373 if (myKey > pair.myKey) {
374 return 1;
375 }
376 return 0;
377 }
378
379 @Override
380 public String toString() {
381 return "(" + myKey + ", " + myValue + ")";
382 }
383
384 private int myKey;
385 private int myValue;
386 }
387
388
389 private static void testAndCheckWithInsertionSort(int length, MyRandom random) {
390 if (length > 1000) {
391 return;
392 }
393 ourDescription = "Check sorting with insertion sort";
394 int[] golden = new int[length];
395
396 for (int m = 1; m < 2 * length; m *= 2) {
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()) {
452 out.println("Test 'check sum': " + converter +
453 " " + builder + "random = " + random.getSeed() +
454 ", length = " + length + ", m = " + m);
455 Object convertedGolden = converter.convert(golden);
456 Object convertedTest = converter.convert(test);
457 sort(convertedTest);
458 checkWithCheckSum(convertedTest, convertedGolden);
459 }
460 }
461 }
462 out.println();
463 }
464
465 private static void testAndCheckWithScrambling(int length, MyRandom random) {
466 ourDescription = "Check sorting with scrambling";
467 int[] golden = new int[length];
468
469 for (int m = 1; m <= 7; m++) {
470 if (m > length) {
471 break;
472 }
473 for (SortedBuilder builder : SortedBuilder.values()) {
474 builder.build(golden, m);
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();
527 }
528 }
529
530 private static void testAndCheckDouble(int length, MyRandom random) {
531 ourDescription = "Check double sorting";
532 double[] golden = new double[length];
533 final int MAX = 10;
534 boolean newLine = false;
535
536 for (int a = 0; a <= MAX; a++) {
537 for (int g = 0; g <= MAX; g++) {
538 for (int z = 0; z <= MAX; z++) {
539 for (int n = 0; n <= MAX; n++) {
540 for (int p = 0; p <= MAX; p++) {
541 if (a + g + z + n + p > length) {
542 continue;
543 }
544 if (a + g + z + n + p < length) {
545 continue;
546 }
547 for (DoubleBuilder builder : DoubleBuilder.values()) {
548 out.println("Test 'double': random = " + random.getSeed() +
549 ", length = " + length + ", a = " + a + ", g = " +
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 }
603
604 private static void swap(int[] a, int i, int j) {
605 int t = a[i];
606 a[i] = a[j];
607 a[j] = t;
608 }
609
610 private static void swap(float[] a, int i, int j) {
611 float t = a[i];
612 a[i] = a[j];
613 a[j] = t;
614 }
615
616 private static void swap(double[] a, int i, int j) {
617 double t = a[i];
618 a[i] = a[j];
619 a[j] = t;
620 }
621
622 private static enum TypeConverter {
623 INT {
624 Object convert(int[] a) {
625 return a.clone();
626 }
627 },
628 LONG {
629 Object convert(int[] a) {
630 long[] b = new long[a.length];
631
632 for (int i = 0; i < a.length; i++) {
633 b[i] = (long) a[i];
634 }
635 return b;
636 }
637 },
638 BYTE {
639 Object convert(int[] a) {
640 byte[] b = new byte[a.length];
641
642 for (int i = 0; i < a.length; i++) {
643 b[i] = (byte) a[i];
644 }
645 return b;
646 }
647 },
648 SHORT {
649 Object convert(int[] a) {
650 short[] b = new short[a.length];
651
652 for (int i = 0; i < a.length; i++) {
653 b[i] = (short) a[i];
654 }
655 return b;
656 }
657 },
658 CHAR {
659 Object convert(int[] a) {
660 char[] b = new char[a.length];
661
662 for (int i = 0; i < a.length; i++) {
663 b[i] = (char) a[i];
664 }
665 return b;
666 }
667 },
668 FLOAT {
669 Object convert(int[] a) {
670 float[] b = new float[a.length];
671
672 for (int i = 0; i < a.length; i++) {
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);
722 fromIndex += g;
723
724 writeValue(x, 0.0f, fromIndex, z);
725 fromIndex += z;
726
727 writeValue(x, positiveValue, fromIndex, p);
728 fromIndex += p;
729
730 writeValue(x, Float.NaN, fromIndex, a);
731 }
732 };
733
734 abstract void build(float[] x, int a, int g, int z, int n, int p, Random random);
735 }
736
737 private static enum DoubleBuilder {
738 SIMPLE {
739 void build(double[] x, int a, int g, int z, int n, int p, Random random) {
740 int fromIndex = 0;
741 double negativeValue = -random.nextFloat();
742 double positiveValue = random.nextFloat();
743
744 writeValue(x, negativeValue, fromIndex, n);
745 fromIndex += n;
746
747 writeValue(x, -0.0d, fromIndex, g);
748 fromIndex += g;
749
750 writeValue(x, 0.0d, fromIndex, z);
751 fromIndex += z;
752
753 writeValue(x, positiveValue, fromIndex, p);
754 fromIndex += p;
755
756 writeValue(x, Double.NaN, fromIndex, a);
757 }
758 };
759
760 abstract void build(double[] x, int a, int g, int z, int n, int p, Random random);
761 }
762
763 private static void writeValue(float[] a, float value, int fromIndex, int count) {
764 for (int i = fromIndex; i < fromIndex + count; i++) {
765 a[i] = value;
766 }
767 }
768
769 private static void compare(float[] a, float[] b, int numNaN, int numNeg, int numNegZero) {
770 for (int i = a.length - numNaN; i < a.length; i++) {
771 if (a[i] == a[i]) {
772 failed("On position " + i + " must be NaN instead of " + a[i]);
773 }
774 }
775 final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
776
777 for (int i = numNeg; i < numNeg + numNegZero; i++) {
778 if (NEGATIVE_ZERO != Float.floatToIntBits(a[i])) {
779 failed("On position " + i + " must be -0.0 instead of " + a[i]);
780 }
781 }
782 for (int i = 0; i < a.length - numNaN; i++) {
783 if (a[i] != b[i]) {
784 failedCompare(i, "" + a[i], "" + b[i]);
785 }
786 }
787 }
788
789 private static void writeValue(double[] a, double value, int fromIndex, int count) {
790 for (int i = fromIndex; i < fromIndex + count; i++) {
791 a[i] = value;
792 }
793 }
794
795 private static void compare(double[] a, double[] b, int numNaN, int numNeg, int numNegZero) {
796 for (int i = a.length - numNaN; i < a.length; i++) {
797 if (a[i] == a[i]) {
798 failed("On position " + i + " must be NaN instead of " + a[i]);
799 }
800 }
801 final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
802
803 for (int i = numNeg; i < numNeg + numNegZero; i++) {
804 if (NEGATIVE_ZERO != Double.doubleToLongBits(a[i])) {
805 failed("On position " + i + " must be -0.0 instead of " + a[i]);
806 }
807 }
808 for (int i = 0; i < a.length - numNaN; i++) {
809 if (a[i] != b[i]) {
810 failedCompare(i, "" + a[i], "" + b[i]);
811 }
812 }
813 }
814
815 private static enum SortedBuilder {
816 REPEATED {
817 void build(int[] a, int m) {
818 int period = a.length / m;
819 int i = 0;
820 int k = 0;
821
822 while (true) {
823 for (int t = 1; t <= period; t++) {
824 if (i >= a.length) {
825 return;
826 }
827 a[i++] = k;
828 }
829 if (i >= a.length) {
830 return;
831 }
832 k++;
833 }
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 }
932 }
933 },
934 ALL_EQUAL {
935 void build(int[] a, int m, Random random) {
936 for (int i = 0; i < a.length; i++) {
937 a[i] = m;
938 }
939 }
940 },
941 SAW {
942 void build(int[] a, int m, Random random) {
943 int incCount = 1;
944 int decCount = a.length;
945 int i = 0;
946 int period = m--;
947
948 while (true) {
949 for (int k = 1; k <= period; k++) {
950 if (i >= a.length) {
951 return;
952 }
953 a[i++] = incCount++;
954 }
955 period += m;
956
957 for (int k = 1; k <= period; k++) {
958 if (i >= a.length) {
959 return;
960 }
961 a[i++] = decCount--;
962 }
963 period += m;
964 }
965 }
966 },
967 REPEATED {
968 void build(int[] a, int m, Random random) {
969 for (int i = 0; i < a.length; i++) {
970 a[i] = i % m;
971 }
972 }
973 },
974 DUPLICATED {
975 void build(int[] a, int m, Random random) {
976 for (int i = 0; i < a.length; i++) {
977 a[i] = random.nextInt(m);
978 }
979 }
980 },
981 ORGAN_PIPES {
982 void build(int[] a, int m, Random random) {
983 int middle = a.length / (m + 1);
984
985 for (int i = 0; i < middle; i++) {
986 a[i] = i;
987 }
988 for (int i = middle; i < a.length; i++) {
989 a[i] = a.length - i - 1;
990 }
991 }
992 },
993 STAGGER {
994 void build(int[] a, int m, Random random) {
995 for (int i = 0; i < a.length; i++) {
996 a[i] = (i * m + i) % a.length;
997 }
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) {
1039 failed("Array is not sorted at " + index + "-th position: " +
1040 value1 + " and " + value2);
1041 }
1042
1043 private static void failedCompare(int index, String value1, String value2) {
1044 failed("On position " + index + " must be " + value2 + " instead of " + value1);
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
1086 private static void compare(short[] a, short[] b) {
1087 for (int i = 0; i < a.length; i++) {
1088 if (a[i] != b[i]) {
1089 failedCompare(i, "" + a[i], "" + b[i]);
1090 }
1091 }
1092 }
1093
1094 private static void compare(byte[] a, byte[] b) {
1095 for (int i = 0; i < a.length; i++) {
1096 if (a[i] != b[i]) {
1097 failedCompare(i, "" + a[i], "" + b[i]);
1098 }
1099 }
1100 }
1101
1102 private static void compare(char[] a, char[] b) {
1103 for (int i = 0; i < a.length; i++) {
1104 if (a[i] != b[i]) {
1105 failedCompare(i, "" + a[i], "" + b[i]);
1106 }
1107 }
1108 }
1109
1110 private static void compare(float[] a, float[] b) {
1111 for (int i = 0; i < a.length; i++) {
1112 if (a[i] != b[i]) {
1113 failedCompare(i, "" + a[i], "" + b[i]);
1114 }
1115 }
1116 }
1117
1118 private static void compare(double[] a, double[] b) {
1119 for (int i = 0; i < a.length; i++) {
1120 if (a[i] != b[i]) {
1121 failedCompare(i, "" + a[i], "" + b[i]);
1122 }
1123 }
1124 }
1125
1126 private static void compare(Integer[] a, Integer[] b) {
1127 for (int i = 0; i < a.length; i++) {
1128 if (a[i].compareTo(b[i]) != 0) {
1129 failedCompare(i, "" + a[i], "" + b[i]);
1130 }
1131 }
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
1173 private static void checkSorted(short[] a) {
1174 for (int i = 0; i < a.length - 1; i++) {
1175 if (a[i] > a[i + 1]) {
1176 failedSort(i, "" + a[i], "" + a[i + 1]);
1177 }
1178 }
1179 }
1180
1181 private static void checkSorted(byte[] a) {
1182 for (int i = 0; i < a.length - 1; i++) {
1183 if (a[i] > a[i + 1]) {
1184 failedSort(i, "" + a[i], "" + a[i + 1]);
1185 }
1186 }
1187 }
1188
1189 private static void checkSorted(char[] a) {
1190 for (int i = 0; i < a.length - 1; i++) {
1191 if (a[i] > a[i + 1]) {
1192 failedSort(i, "" + a[i], "" + a[i + 1]);
1193 }
1194 }
1195 }
1196
1197 private static void checkSorted(float[] a) {
1198 for (int i = 0; i < a.length - 1; i++) {
1199 if (a[i] > a[i + 1]) {
1200 failedSort(i, "" + a[i], "" + a[i + 1]);
1201 }
1202 }
1203 }
1204
1205 private static void checkSorted(double[] a) {
1206 for (int i = 0; i < a.length - 1; i++) {
1207 if (a[i] > a[i + 1]) {
1208 failedSort(i, "" + a[i], "" + a[i + 1]);
1209 }
1210 }
1211 }
1212
1213 private static void checkSorted(Integer[] a) {
1214 for (int i = 0; i < a.length - 1; i++) {
1215 if (a[i].intValue() > a[i + 1].intValue()) {
1216 failedSort(i, "" + a[i], "" + a[i + 1]);
1217 }
1218 }
1219 }
1220
1221 private static void checkCheckSum(Object test, Object golden) {
1222 if (checkSumXor(test) != checkSumXor(golden)) {
1223 failed("Original and sorted arrays are not identical [xor]");
1224 }
1225 if (checkSumPlus(test) != checkSumPlus(golden)) {
1226 failed("Original and sorted arrays are not identical [plus]");
1227 }
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 }
1269 return checkSum;
1270 }
1271
1272 private static int checkSumXor(long[] a) {
1273 long checkSum = 0;
1274
1275 for (long e : a) {
1276 checkSum ^= e;
1277 }
1278 return (int) checkSum;
1279 }
1280
1281 private static int checkSumXor(short[] a) {
1282 short checkSum = 0;
1283
1284 for (short e : a) {
1285 checkSum ^= e;
1286 }
1287 return (int) checkSum;
1288 }
1289
1290 private static int checkSumXor(byte[] a) {
1291 byte checkSum = 0;
1292
1293 for (byte e : a) {
1294 checkSum ^= e;
1295 }
1296 return (int) checkSum;
1297 }
1298
1299 private static int checkSumXor(char[] a) {
1300 char checkSum = 0;
1301
1302 for (char e : a) {
1303 checkSum ^= e;
1304 }
1305 return (int) checkSum;
1306 }
1307
1308 private static int checkSumXor(float[] a) {
1309 int checkSum = 0;
1310
1311 for (float e : a) {
1312 checkSum ^= (int) e;
1313 }
1314 return checkSum;
1315 }
1316
1317 private static int checkSumXor(double[] a) {
1318 int checkSum = 0;
1319
1320 for (double e : a) {
1321 checkSum ^= (int) e;
1322 }
1323 return checkSum;
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 }
1365 return (int) checkSum;
1366 }
1367
1368 private static int checkSumPlus(short[] a) {
1369 short checkSum = 0;
1370
1371 for (short e : a) {
1372 checkSum += e;
1373 }
1374 return (int) checkSum;
1375 }
1376
1377 private static int checkSumPlus(byte[] a) {
1378 byte checkSum = 0;
1379
1380 for (byte e : a) {
1381 checkSum += e;
1382 }
1383 return (int) checkSum;
1384 }
1385
1386 private static int checkSumPlus(char[] a) {
1387 char checkSum = 0;
1388
1389 for (char e : a) {
1390 checkSum += e;
1391 }
1392 return (int) checkSum;
1393 }
1394
1395 private static int checkSumPlus(float[] a) {
1396 int checkSum = 0;
1397
1398 for (float e : a) {
1399 checkSum += (int) e;
1400 }
1401 return checkSum;
1402 }
1403
1404 private static int checkSumPlus(double[] a) {
1405 int checkSum = 0;
1406
1407 for (double e : a) {
1408 checkSum += (int) e;
1409 }
1410 return checkSum;
1411 }
1412
1413 private static int checkSumPlus(Integer[] a) {
1414 int checkSum = 0;
1415
1416 for (Integer e : a) {
1417 checkSum += e.intValue();
1418 }
1419 return checkSum;
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 }
1461 a[j + 1] = ai;
1462 }
1463 }
1464
1465 private static void sortByInsertionSort(short[] a) {
1466 for (int j, i = 1; i < a.length; i++) {
1467 short ai = a[i];
1468 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1469 a[j + 1] = a[j];
1470 }
1471 a[j + 1] = ai;
1472 }
1473 }
1474
1475 private static void sortByInsertionSort(byte[] a) {
1476 for (int j, i = 1; i < a.length; i++) {
1477 byte ai = a[i];
1478 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1479 a[j + 1] = a[j];
1480 }
1481 a[j + 1] = ai;
1482 }
1483 }
1484
1485 private static void sortByInsertionSort(char[] a) {
1486 for (int j, i = 1; i < a.length; i++) {
1487 char ai = a[i];
1488 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1489 a[j + 1] = a[j];
1490 }
1491 a[j + 1] = ai;
1492 }
1493 }
1494
1495 private static void sortByInsertionSort(float[] a) {
1496 for (int j, i = 1; i < a.length; i++) {
1497 float ai = a[i];
1498 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1499 a[j + 1] = a[j];
1500 }
1501 a[j + 1] = ai;
1502 }
1503 }
1504
1505 private static void sortByInsertionSort(double[] a) {
1506 for (int j, i = 1; i < a.length; i++) {
1507 double ai = a[i];
1508 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1509 a[j + 1] = a[j];
1510 }
1511 a[j + 1] = ai;
1512 }
1513 }
1514
1515 private static void sortByInsertionSort(Integer[] a) {
1516 for (int j, i = 1; i < a.length; i++) {
1517 Integer ai = a[i];
1518 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1519 a[j + 1] = a[j];
1520 }
1521 a[j + 1] = ai;
1522 }
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 }
2036 out.println();
2037 }
2038
2039 private static void outArray(float[] a) {
2040 for (int i = 0; i < a.length; i++) {
2041 out.print(a[i] + " ");
2042 }
2043 out.println();
2044 }
2045
2046 private static void outArray(double[] a) {
2047 for (int i = 0; i < a.length; i++) {
2048 out.print(a[i] + " ");
2049 }
2050 out.println();
2051 }
2052
2053 private static class MyRandom extends Random {
2054 MyRandom(long seed) {
2055 super(seed);
2056 mySeed = seed;
2057 }
2058
2059 long getSeed() {
2060 return mySeed;
2061 }
2062
2063 private long mySeed;
2064 }
2065
2066 private static String ourDescription;
2067 }