1 /*
2 * Copyright (c) 2009, 2023, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /*
25 * @test
26 * @compile/module=java.base java/util/SortingHelper.java
27 * @bug 6880672 6896573 6899694 6976036 7013585 7018258 8003981 8226297
28 * @build Sorting
29 * @run main/othervm -XX:+UnlockDiagnosticVMOptions -XX:DisableIntrinsic=_arraySort,_arrayPartition Sorting -shortrun
30 * @run main/othervm -XX:-TieredCompilation -XX:CompileCommand=CompileThresholdScaling,java.util.DualPivotQuicksort::sort,0.0001 Sorting -shortrun
31 * @summary Exercise Arrays.sort, Arrays.parallelSort
32 *
33 * @author Vladimir Yaroslavskiy
34 * @author Jon Bentley
35 * @author Josh Bloch
36 */
37
38 import java.io.PrintStream;
39 import java.util.Comparator;
40 import java.util.Random;
41 import java.util.SortingHelper;
42
43 public class Sorting {
44
45 private static final PrintStream out = System.out;
46 private static final PrintStream err = System.err;
47
48 // Array lengths used in a long run (default)
49 private static final int[] LONG_RUN_LENGTHS = {
50 1, 3, 8, 21, 55, 100, 1_000, 10_000, 100_000 };
51
52 // Array lengths used in a short run
53 private static final int[] SHORT_RUN_LENGTHS = {
54 1, 8, 55, 100, 10_000 };
55
56 // Random initial values used in a long run (default)
57 private static final TestRandom[] LONG_RUN_RANDOMS = {
58 TestRandom.BABA, TestRandom.DEDA, TestRandom.C0FFEE };
59
60 // Random initial values used in a short run
61 private static final TestRandom[] SHORT_RUN_RANDOMS = {
62 TestRandom.C0FFEE };
63
64 // Constants used in subarray sorting
65 private static final int A380 = 0xA380;
66 private static final int B747 = 0xB747;
67
68 private final SortingHelper sortingHelper;
69 private final TestRandom[] randoms;
70 private final int[] lengths;
71 private Object[] gold;
72 private Object[] test;
73
74 public static void main(String[] args) {
75 long start = System.currentTimeMillis();
76 boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
77
78 int[] lengths = shortRun ? SHORT_RUN_LENGTHS : LONG_RUN_LENGTHS;
79 TestRandom[] randoms = shortRun ? SHORT_RUN_RANDOMS : LONG_RUN_RANDOMS;
80
81 new Sorting(SortingHelper.DUAL_PIVOT_QUICKSORT, randoms, lengths).testCore();
82 new Sorting(SortingHelper.PARALLEL_SORT, randoms, lengths).testCore();
83 new Sorting(SortingHelper.HEAP_SORT, randoms, lengths).testBasic();
84 new Sorting(SortingHelper.ARRAYS_SORT, randoms, lengths).testAll();
85 new Sorting(SortingHelper.ARRAYS_PARALLEL_SORT, randoms, lengths).testAll();
86
87 long end = System.currentTimeMillis();
88 out.format("PASSED in %d sec.\n", (end - start) / 1000);
89 }
90
91 private Sorting(SortingHelper sortingHelper, TestRandom[] randoms, int[] lengths) {
92 this.sortingHelper = sortingHelper;
93 this.randoms = randoms;
94 this.lengths = lengths;
95 }
96
97 private void testBasic() {
98 testEmptyArray();
99
100 for (int length : lengths) {
101 createData(length);
102 testBasic(length);
103 }
104 }
105
106 private void testBasic(int length) {
107 for (TestRandom random : randoms) {
108 testWithInsertionSort(length, random);
109 testWithCheckSum(length, random);
110 testWithScrambling(length, random);
111 }
112 }
113
114 private void testCore() {
115 for (int length : lengths) {
116 createData(length);
117 testCore(length);
118 }
119 }
120
121 private void testCore(int length) {
122 testBasic(length);
123
124 for (TestRandom random : randoms) {
125 testMergingSort(length, random);
126 testSubArray(length, random);
127 testNegativeZero(length, random);
128 testFloatingPointSorting(length, random);
129 }
130 }
131
132 private void testAll() {
133 for (int length : lengths) {
134 createData(length);
135 testAll(length);
136 }
137 }
138
139 private void testAll(int length) {
140 testCore(length);
141
142 for (TestRandom random : randoms) {
143 testRange(length, random);
144 testStability(length, random);
145 }
146 }
147
148 private void testEmptyArray() {
149 testEmptyAndNullIntArray();
150 testEmptyAndNullLongArray();
151 testEmptyAndNullByteArray();
152 testEmptyAndNullCharArray();
153 testEmptyAndNullShortArray();
154 testEmptyAndNullFloatArray();
155 testEmptyAndNullDoubleArray();
156 }
157
158 private void testStability(int length, TestRandom random) {
159 printTestName("Test stability", random, length);
160
161 Pair[] a = build(length, random);
162 sortingHelper.sort(a);
163 checkSorted(a);
164 checkStable(a);
165
166 a = build(length, random);
167 sortingHelper.sort(a, pairComparator);
168 checkSorted(a);
169 checkStable(a);
170
171 out.println();
172 }
173
174 private void testEmptyAndNullIntArray() {
175 sortingHelper.sort(new int[] {});
176 sortingHelper.sort(new int[] {}, 0, 0);
177
178 try {
179 sortingHelper.sort(null);
180 } catch (NullPointerException expected) {
181 try {
182 sortingHelper.sort(null, 0, 0);
183 } catch (NullPointerException expected2) {
184 return;
185 }
186 fail(sortingHelper + "(int[],fromIndex,toIndex) shouldn't " +
187 "catch null array");
188 }
189 fail(sortingHelper + "(int[]) shouldn't catch null array");
190 }
191
192 private void testEmptyAndNullLongArray() {
193 sortingHelper.sort(new long[] {});
194 sortingHelper.sort(new long[] {}, 0, 0);
195
196 try {
197 sortingHelper.sort(null);
198 } catch (NullPointerException expected) {
199 try {
200 sortingHelper.sort(null, 0, 0);
201 } catch (NullPointerException expected2) {
202 return;
203 }
204 fail(sortingHelper + "(long[],fromIndex,toIndex) shouldn't " +
205 "catch null array");
206 }
207 fail(sortingHelper + "(long[]) shouldn't catch null array");
208 }
209
210 private void testEmptyAndNullByteArray() {
211 sortingHelper.sort(new byte[] {});
212 sortingHelper.sort(new byte[] {}, 0, 0);
213
214 try {
215 sortingHelper.sort(null);
216 } catch (NullPointerException expected) {
217 try {
218 sortingHelper.sort(null, 0, 0);
219 } catch (NullPointerException expected2) {
220 return;
221 }
222 fail(sortingHelper + "(byte[],fromIndex,toIndex) shouldn't " +
223 "catch null array");
224 }
225 fail(sortingHelper + "(byte[]) shouldn't catch null array");
226 }
227
228 private void testEmptyAndNullCharArray() {
229 sortingHelper.sort(new char[] {});
230 sortingHelper.sort(new char[] {}, 0, 0);
231
232 try {
233 sortingHelper.sort(null);
234 } catch (NullPointerException expected) {
235 try {
236 sortingHelper.sort(null, 0, 0);
237 } catch (NullPointerException expected2) {
238 return;
239 }
240 fail(sortingHelper + "(char[],fromIndex,toIndex) shouldn't " +
241 "catch null array");
242 }
243 fail(sortingHelper + "(char[]) shouldn't catch null array");
244 }
245
246 private void testEmptyAndNullShortArray() {
247 sortingHelper.sort(new short[] {});
248 sortingHelper.sort(new short[] {}, 0, 0);
249
250 try {
251 sortingHelper.sort(null);
252 } catch (NullPointerException expected) {
253 try {
254 sortingHelper.sort(null, 0, 0);
255 } catch (NullPointerException expected2) {
256 return;
257 }
258 fail(sortingHelper + "(short[],fromIndex,toIndex) shouldn't " +
259 "catch null array");
260 }
261 fail(sortingHelper + "(short[]) shouldn't catch null array");
262 }
263
264 private void testEmptyAndNullFloatArray() {
265 sortingHelper.sort(new float[] {});
266 sortingHelper.sort(new float[] {}, 0, 0);
267
268 try {
269 sortingHelper.sort(null);
270 } catch (NullPointerException expected) {
271 try {
272 sortingHelper.sort(null, 0, 0);
273 } catch (NullPointerException expected2) {
274 return;
275 }
276 fail(sortingHelper + "(float[],fromIndex,toIndex) shouldn't " +
277 "catch null array");
278 }
279 fail(sortingHelper + "(float[]) shouldn't catch null array");
280 }
281
282 private void testEmptyAndNullDoubleArray() {
283 sortingHelper.sort(new double[] {});
284 sortingHelper.sort(new double[] {}, 0, 0);
285
286 try {
287 sortingHelper.sort(null);
288 } catch (NullPointerException expected) {
289 try {
290 sortingHelper.sort(null, 0, 0);
291 } catch (NullPointerException expected2) {
292 return;
293 }
294 fail(sortingHelper + "(double[],fromIndex,toIndex) shouldn't " +
295 "catch null array");
296 }
297 fail(sortingHelper + "(double[]) shouldn't catch null array");
298 }
299
300 private void testSubArray(int length, TestRandom random) {
301 if (length < 4) {
302 return;
303 }
304 for (int m = 1; m < length / 2; m <<= 1) {
305 int fromIndex = m;
306 int toIndex = length - m;
307
308 prepareSubArray((int[]) gold[0], fromIndex, toIndex);
309 convertData(length);
310
311 for (int i = 0; i < test.length; i++) {
312 printTestName("Test subarray", random, length,
313 ", m = " + m + ", " + getType(i));
314 sortingHelper.sort(test[i], fromIndex, toIndex);
315 checkSubArray(test[i], fromIndex, toIndex);
316 }
317 }
318 out.println();
319 }
320
321 private void testRange(int length, TestRandom random) {
322 if (length < 2) {
323 return;
324 }
325 for (int m = 1; m < length; m <<= 1) {
326 for (int i = 1; i <= length; i++) {
327 ((int[]) gold[0]) [i - 1] = i % m + m % i;
328 }
329 convertData(length);
330
331 for (int i = 0; i < test.length; i++) {
332 printTestName("Test range check", random, length,
333 ", m = " + m + ", " + getType(i));
334 checkRange(test[i], m);
335 }
336 }
337 out.println();
338 }
339
340 private void checkSorted(Pair[] a) {
341 for (int i = 0; i < a.length - 1; i++) {
342 if (a[i].getKey() > a[i + 1].getKey()) {
343 fail("Array is not sorted at " + i + "-th position: " +
344 a[i].getKey() + " and " + a[i + 1].getKey());
345 }
346 }
347 }
348
349 private void checkStable(Pair[] a) {
350 for (int i = 0; i < a.length / 4; ) {
351 int key1 = a[i].getKey();
352 int value1 = a[i++].getValue();
353 int key2 = a[i].getKey();
354 int value2 = a[i++].getValue();
355 int key3 = a[i].getKey();
356 int value3 = a[i++].getValue();
357 int key4 = a[i].getKey();
358 int value4 = a[i++].getValue();
359
360 if (!(key1 == key2 && key2 == key3 && key3 == key4)) {
361 fail("Keys are different " + key1 + ", " + key2 + ", " +
362 key3 + ", " + key4 + " at position " + i);
363 }
364 if (!(value1 < value2 && value2 < value3 && value3 < value4)) {
365 fail("Sorting is not stable at position " + i +
366 ". Second values have been changed: " + value1 + ", " +
367 value2 + ", " + value3 + ", " + value4);
368 }
369 }
370 }
371
372 private Pair[] build(int length, Random random) {
373 Pair[] a = new Pair[length * 4];
374
375 for (int i = 0; i < a.length; ) {
376 int key = random.nextInt();
377 a[i++] = new Pair(key, 1);
378 a[i++] = new Pair(key, 2);
379 a[i++] = new Pair(key, 3);
380 a[i++] = new Pair(key, 4);
381 }
382 return a;
383 }
384
385 private void testWithInsertionSort(int length, TestRandom random) {
386 if (length > 1000) {
387 return;
388 }
389 for (int m = 1; m <= length; m <<= 1) {
390 for (UnsortedBuilder builder : UnsortedBuilder.values()) {
391 builder.build((int[]) gold[0], m, random);
392 convertData(length);
393
394 for (int i = 0; i < test.length; i++) {
395 printTestName("Test with insertion sort", random, length,
396 ", m = " + m + ", " + getType(i) + " " + builder);
397 sortingHelper.sort(test[i]);
398 sortByInsertionSort(gold[i]);
399 compare(test[i], gold[i]);
400 }
401 }
402 }
403 out.println();
404 }
405
406 private void testMergingSort(int length, TestRandom random) {
407 if (length < (4 << 10)) { // DualPivotQuicksort.MIN_TRY_MERGE_SIZE
408 return;
409 }
410 final int PERIOD = 50;
411
412 for (int m = PERIOD - 2; m <= PERIOD + 2; m++) {
413 for (MergingBuilder builder : MergingBuilder.values()) {
414 builder.build((int[]) gold[0], m);
415 convertData(length);
416
417 for (int i = 0; i < test.length; i++) {
418 printTestName("Test merging sort", random, length,
419 ", m = " + m + ", " + getType(i) + " " + builder);
420 sortingHelper.sort(test[i]);
421 checkSorted(test[i]);
422 }
423 }
424 }
425 out.println();
426 }
427
428 private void testWithCheckSum(int length, TestRandom random) {
429 for (int m = 1; m <= length; m <<= 1) {
430 for (UnsortedBuilder builder : UnsortedBuilder.values()) {
431 builder.build((int[]) gold[0], m, random);
432 convertData(length);
433
434 for (int i = 0; i < test.length; i++) {
435 printTestName("Test with check sum", random, length,
436 ", m = " + m + ", " + getType(i) + " " + builder);
437 sortingHelper.sort(test[i]);
438 checkWithCheckSum(test[i], gold[i]);
439 }
440 }
441 }
442 out.println();
443 }
444
445 private void testWithScrambling(int length, TestRandom random) {
446 for (int m = 1; m <= length; m <<= 1) {
447 for (SortedBuilder builder : SortedBuilder.values()) {
448 builder.build((int[]) gold[0], m);
449 convertData(length);
450
451 for (int i = 0; i < test.length; i++) {
452 printTestName("Test with scrambling", random, length,
453 ", m = " + m + ", " + getType(i) + " " + builder);
454 scramble(test[i], random);
455 sortingHelper.sort(test[i]);
456 compare(test[i], gold[i]);
457 }
458 }
459 }
460 out.println();
461 }
462
463 private void testNegativeZero(int length, TestRandom random) {
464 for (int i = 5; i < test.length; i++) {
465 printTestName("Test negative zero -0.0", random, length, " " + getType(i));
466
467 NegativeZeroBuilder builder = NegativeZeroBuilder.values() [i - 5];
468 builder.build(test[i], random);
469
470 sortingHelper.sort(test[i]);
471 checkNegativeZero(test[i]);
472 }
473 out.println();
474 }
475
476 private void testFloatingPointSorting(int length, TestRandom random) {
477 if (length < 2) {
478 return;
479 }
480 final int MAX = 13;
481
482 for (int a = 0; a < MAX; a++) {
483 for (int g = 0; g < MAX; g++) {
484 for (int z = 0; z < MAX; z++) {
485 for (int n = 0; n < MAX; n++) {
486 for (int p = 0; p < MAX; p++) {
487 if (a + g + z + n + p != length) {
488 continue;
489 }
490 for (int i = 5; i < test.length; i++) {
491 printTestName("Test float-pointing sorting", random, length,
492 ", a = " + a + ", g = " + g + ", z = " + z +
493 ", n = " + n + ", p = " + p + ", " + getType(i));
494 FloatingPointBuilder builder = FloatingPointBuilder.values()[i - 5];
495 builder.build(gold[i], a, g, z, n, p, random);
496 copy(test[i], gold[i]);
497 scramble(test[i], random);
498 sortingHelper.sort(test[i]);
499 compare(test[i], gold[i], a, n, g);
500 }
501 }
502 }
503 }
504 }
505 }
506
507 for (int m = 13; m > 4; m--) {
508 int t = length / m;
509 int g = t, z = t, n = t, p = t;
510 int a = length - g - z - n - p;
511
512 for (int i = 5; i < test.length; i++) {
513 printTestName("Test float-pointing sorting", random, length,
514 ", a = " + a + ", g = " + g + ", z = " + z +
515 ", n = " + n + ", p = " + p + ", " + getType(i));
516 FloatingPointBuilder builder = FloatingPointBuilder.values() [i - 5];
517 builder.build(gold[i], a, g, z, n, p, random);
518 copy(test[i], gold[i]);
519 scramble(test[i], random);
520 sortingHelper.sort(test[i]);
521 compare(test[i], gold[i], a, n, g);
522 }
523 }
524 out.println();
525 }
526
527 private void prepareSubArray(int[] a, int fromIndex, int toIndex) {
528 for (int i = 0; i < fromIndex; i++) {
529 a[i] = A380;
530 }
531 int middle = (fromIndex + toIndex) >>> 1;
532 int k = 0;
533
534 for (int i = fromIndex; i < middle; i++) {
535 a[i] = k++;
536 }
537
538 for (int i = middle; i < toIndex; i++) {
539 a[i] = k--;
540 }
541
542 for (int i = toIndex; i < a.length; i++) {
543 a[i] = B747;
544 }
545 }
546
547 private void scramble(Object a, Random random) {
548 if (a instanceof int[]) {
549 scramble((int[]) a, random);
550 } else if (a instanceof long[]) {
551 scramble((long[]) a, random);
552 } else if (a instanceof byte[]) {
553 scramble((byte[]) a, random);
554 } else if (a instanceof char[]) {
555 scramble((char[]) a, random);
556 } else if (a instanceof short[]) {
557 scramble((short[]) a, random);
558 } else if (a instanceof float[]) {
559 scramble((float[]) a, random);
560 } else if (a instanceof double[]) {
561 scramble((double[]) a, random);
562 } else {
563 fail("Unknown type of array: " + a.getClass().getName());
564 }
565 }
566
567 private void scramble(int[] a, Random random) {
568 for (int i = 0; i < a.length * 7; i++) {
569 swap(a, random.nextInt(a.length), random.nextInt(a.length));
570 }
571 }
572
573 private void scramble(long[] a, Random random) {
574 for (int i = 0; i < a.length * 7; i++) {
575 swap(a, random.nextInt(a.length), random.nextInt(a.length));
576 }
577 }
578
579 private void scramble(byte[] a, Random random) {
580 for (int i = 0; i < a.length * 7; i++) {
581 swap(a, random.nextInt(a.length), random.nextInt(a.length));
582 }
583 }
584
585 private void scramble(char[] a, Random random) {
586 for (int i = 0; i < a.length * 7; i++) {
587 swap(a, random.nextInt(a.length), random.nextInt(a.length));
588 }
589 }
590
591 private void scramble(short[] a, Random random) {
592 for (int i = 0; i < a.length * 7; i++) {
593 swap(a, random.nextInt(a.length), random.nextInt(a.length));
594 }
595 }
596
597 private void scramble(float[] a, Random random) {
598 for (int i = 0; i < a.length * 7; i++) {
599 swap(a, random.nextInt(a.length), random.nextInt(a.length));
600 }
601 }
602
603 private void scramble(double[] a, Random random) {
604 for (int i = 0; i < a.length * 7; i++) {
605 swap(a, random.nextInt(a.length), random.nextInt(a.length));
606 }
607 }
608
609 private void swap(int[] a, int i, int j) {
610 int t = a[i]; a[i] = a[j]; a[j] = t;
611 }
612
613 private void swap(long[] a, int i, int j) {
614 long t = a[i]; a[i] = a[j]; a[j] = t;
615 }
616
617 private void swap(byte[] a, int i, int j) {
618 byte t = a[i]; a[i] = a[j]; a[j] = t;
619 }
620
621 private void swap(char[] a, int i, int j) {
622 char t = a[i]; a[i] = a[j]; a[j] = t;
623 }
624
625 private void swap(short[] a, int i, int j) {
626 short t = a[i]; a[i] = a[j]; a[j] = t;
627 }
628
629 private void swap(float[] a, int i, int j) {
630 float t = a[i]; a[i] = a[j]; a[j] = t;
631 }
632
633 private void swap(double[] a, int i, int j) {
634 double t = a[i]; a[i] = a[j]; a[j] = t;
635 }
636
637 private void checkWithCheckSum(Object test, Object gold) {
638 checkSorted(test);
639 checkCheckSum(test, gold);
640 }
641
642 private void fail(String message) {
643 err.format("\n*** TEST FAILED ***\n\n%s\n\n", message);
644 throw new RuntimeException("Test failed");
645 }
646
647 private void checkNegativeZero(Object a) {
648 if (a instanceof float[]) {
649 checkNegativeZero((float[]) a);
650 } else if (a instanceof double[]) {
651 checkNegativeZero((double[]) a);
652 } else {
653 fail("Unknown type of array: " + a.getClass().getName());
654 }
655 }
656
657 private void checkNegativeZero(float[] a) {
658 for (int i = 0; i < a.length - 1; i++) {
659 if (Float.floatToRawIntBits(a[i]) == 0 && Float.floatToRawIntBits(a[i + 1]) < 0) {
660 fail(a[i] + " before " + a[i + 1] + " at position " + i);
661 }
662 }
663 }
664
665 private void checkNegativeZero(double[] a) {
666 for (int i = 0; i < a.length - 1; i++) {
667 if (Double.doubleToRawLongBits(a[i]) == 0 && Double.doubleToRawLongBits(a[i + 1]) < 0) {
668 fail(a[i] + " before " + a[i + 1] + " at position " + i);
669 }
670 }
671 }
672
673 private void compare(Object a, Object b, int numNaN, int numNeg, int numNegZero) {
674 if (a instanceof float[]) {
675 compare((float[]) a, (float[]) b, numNaN, numNeg, numNegZero);
676 } else if (a instanceof double[]) {
677 compare((double[]) a, (double[]) b, numNaN, numNeg, numNegZero);
678 } else {
679 fail("Unknown type of array: " + a.getClass().getName());
680 }
681 }
682
683 private void compare(float[] a, float[] b, int numNaN, int numNeg, int numNegZero) {
684 for (int i = a.length - numNaN; i < a.length; i++) {
685 if (a[i] == a[i]) {
686 fail("There must be NaN instead of " + a[i] + " at position " + i);
687 }
688 }
689 final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
690
691 for (int i = numNeg; i < numNeg + numNegZero; i++) {
692 if (NEGATIVE_ZERO != Float.floatToIntBits(a[i])) {
693 fail("There must be -0.0 instead of " + a[i] + " at position " + i);
694 }
695 }
696
697 for (int i = 0; i < a.length - numNaN; i++) {
698 if (a[i] != b[i]) {
699 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
700 }
701 }
702 }
703
704 private void compare(double[] a, double[] b, int numNaN, int numNeg, int numNegZero) {
705 for (int i = a.length - numNaN; i < a.length; i++) {
706 if (a[i] == a[i]) {
707 fail("There must be NaN instead of " + a[i] + " at position " + i);
708 }
709 }
710 final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
711
712 for (int i = numNeg; i < numNeg + numNegZero; i++) {
713 if (NEGATIVE_ZERO != Double.doubleToLongBits(a[i])) {
714 fail("There must be -0.0 instead of " + a[i] + " at position " + i);
715 }
716 }
717
718 for (int i = 0; i < a.length - numNaN; i++) {
719 if (a[i] != b[i]) {
720 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
721 }
722 }
723 }
724
725 private void compare(Object a, Object b) {
726 if (a instanceof int[]) {
727 compare((int[]) a, (int[]) b);
728 } else if (a instanceof long[]) {
729 compare((long[]) a, (long[]) b);
730 } else if (a instanceof byte[]) {
731 compare((byte[]) a, (byte[]) b);
732 } else if (a instanceof char[]) {
733 compare((char[]) a, (char[]) b);
734 } else if (a instanceof short[]) {
735 compare((short[]) a, (short[]) b);
736 } else if (a instanceof float[]) {
737 compare((float[]) a, (float[]) b);
738 } else if (a instanceof double[]) {
739 compare((double[]) a, (double[]) b);
740 } else {
741 fail("Unknown type of array: " + a.getClass().getName());
742 }
743 }
744
745 private void compare(int[] a, int[] b) {
746 for (int i = 0; i < a.length; i++) {
747 if (a[i] != b[i]) {
748 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
749 }
750 }
751 }
752
753 private void compare(long[] a, long[] b) {
754 for (int i = 0; i < a.length; i++) {
755 if (a[i] != b[i]) {
756 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
757 }
758 }
759 }
760
761 private void compare(byte[] a, byte[] b) {
762 for (int i = 0; i < a.length; i++) {
763 if (a[i] != b[i]) {
764 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
765 }
766 }
767 }
768
769 private void compare(char[] a, char[] b) {
770 for (int i = 0; i < a.length; i++) {
771 if (a[i] != b[i]) {
772 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
773 }
774 }
775 }
776
777 private void compare(short[] a, short[] b) {
778 for (int i = 0; i < a.length; i++) {
779 if (a[i] != b[i]) {
780 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
781 }
782 }
783 }
784
785 private void compare(float[] a, float[] b) {
786 for (int i = 0; i < a.length; i++) {
787 if (a[i] != b[i]) {
788 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
789 }
790 }
791 }
792
793 private void compare(double[] a, double[] b) {
794 for (int i = 0; i < a.length; i++) {
795 if (a[i] != b[i]) {
796 fail("There must be " + b[i] + " instead of " + a[i] + " at position " + i);
797 }
798 }
799 }
800
801 private String getType(int i) {
802 Object a = test[i];
803
804 if (a instanceof int[]) {
805 return "INT ";
806 }
807 if (a instanceof long[]) {
808 return "LONG ";
809 }
810 if (a instanceof byte[]) {
811 return "BYTE ";
812 }
813 if (a instanceof char[]) {
814 return "CHAR ";
815 }
816 if (a instanceof short[]) {
817 return "SHORT ";
818 }
819 if (a instanceof float[]) {
820 return "FLOAT ";
821 }
822 if (a instanceof double[]) {
823 return "DOUBLE";
824 }
825 fail("Unknown type of array: " + a.getClass().getName());
826 return null;
827 }
828
829 private void checkSorted(Object a) {
830 if (a instanceof int[]) {
831 checkSorted((int[]) a);
832 } else if (a instanceof long[]) {
833 checkSorted((long[]) a);
834 } else if (a instanceof byte[]) {
835 checkSorted((byte[]) a);
836 } else if (a instanceof char[]) {
837 checkSorted((char[]) a);
838 } else if (a instanceof short[]) {
839 checkSorted((short[]) a);
840 } else if (a instanceof float[]) {
841 checkSorted((float[]) a);
842 } else if (a instanceof double[]) {
843 checkSorted((double[]) a);
844 } else {
845 fail("Unknown type of array: " + a.getClass().getName());
846 }
847 }
848
849 private void checkSorted(int[] a) {
850 for (int i = 0; i < a.length - 1; i++) {
851 if (a[i] > a[i + 1]) {
852 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
853 }
854 }
855 }
856
857 private void checkSorted(long[] a) {
858 for (int i = 0; i < a.length - 1; i++) {
859 if (a[i] > a[i + 1]) {
860 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
861 }
862 }
863 }
864
865 private void checkSorted(byte[] a) {
866 for (int i = 0; i < a.length - 1; i++) {
867 if (a[i] > a[i + 1]) {
868 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
869 }
870 }
871 }
872
873 private void checkSorted(char[] a) {
874 for (int i = 0; i < a.length - 1; i++) {
875 if (a[i] > a[i + 1]) {
876 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
877 }
878 }
879 }
880
881 private void checkSorted(short[] a) {
882 for (int i = 0; i < a.length - 1; i++) {
883 if (a[i] > a[i + 1]) {
884 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
885 }
886 }
887 }
888
889 private void checkSorted(float[] a) {
890 for (int i = 0; i < a.length - 1; i++) {
891 if (a[i] > a[i + 1]) {
892 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
893 }
894 }
895 }
896
897 private void checkSorted(double[] a) {
898 for (int i = 0; i < a.length - 1; i++) {
899 if (a[i] > a[i + 1]) {
900 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
901 }
902 }
903 }
904
905 private void checkCheckSum(Object test, Object gold) {
906 if (checkSumXor(test) != checkSumXor(gold)) {
907 fail("Original and sorted arrays are not identical [^]");
908 }
909 if (checkSumPlus(test) != checkSumPlus(gold)) {
910 fail("Original and sorted arrays are not identical [+]");
911 }
912 }
913
914 private int checkSumXor(Object a) {
915 if (a instanceof int[]) {
916 return checkSumXor((int[]) a);
917 }
918 if (a instanceof long[]) {
919 return checkSumXor((long[]) a);
920 }
921 if (a instanceof byte[]) {
922 return checkSumXor((byte[]) a);
923 }
924 if (a instanceof char[]) {
925 return checkSumXor((char[]) a);
926 }
927 if (a instanceof short[]) {
928 return checkSumXor((short[]) a);
929 }
930 if (a instanceof float[]) {
931 return checkSumXor((float[]) a);
932 }
933 if (a instanceof double[]) {
934 return checkSumXor((double[]) a);
935 }
936 fail("Unknown type of array: " + a.getClass().getName());
937 return -1;
938 }
939
940 private int checkSumXor(int[] a) {
941 int checkSum = 0;
942
943 for (int e : a) {
944 checkSum ^= e;
945 }
946 return checkSum;
947 }
948
949 private int checkSumXor(long[] a) {
950 long checkSum = 0;
951
952 for (long e : a) {
953 checkSum ^= e;
954 }
955 return (int) checkSum;
956 }
957
958 private int checkSumXor(byte[] a) {
959 byte checkSum = 0;
960
961 for (byte e : a) {
962 checkSum ^= e;
963 }
964 return (int) checkSum;
965 }
966
967 private int checkSumXor(char[] a) {
968 char checkSum = 0;
969
970 for (char e : a) {
971 checkSum ^= e;
972 }
973 return (int) checkSum;
974 }
975
976 private int checkSumXor(short[] a) {
977 short checkSum = 0;
978
979 for (short e : a) {
980 checkSum ^= e;
981 }
982 return (int) checkSum;
983 }
984
985 private int checkSumXor(float[] a) {
986 int checkSum = 0;
987
988 for (float e : a) {
989 checkSum ^= (int) e;
990 }
991 return checkSum;
992 }
993
994 private int checkSumXor(double[] a) {
995 int checkSum = 0;
996
997 for (double e : a) {
998 checkSum ^= (int) e;
999 }
1000 return checkSum;
1001 }
1002
1003 private int checkSumPlus(Object a) {
1004 if (a instanceof int[]) {
1005 return checkSumPlus((int[]) a);
1006 }
1007 if (a instanceof long[]) {
1008 return checkSumPlus((long[]) a);
1009 }
1010 if (a instanceof byte[]) {
1011 return checkSumPlus((byte[]) a);
1012 }
1013 if (a instanceof char[]) {
1014 return checkSumPlus((char[]) a);
1015 }
1016 if (a instanceof short[]) {
1017 return checkSumPlus((short[]) a);
1018 }
1019 if (a instanceof float[]) {
1020 return checkSumPlus((float[]) a);
1021 }
1022 if (a instanceof double[]) {
1023 return checkSumPlus((double[]) a);
1024 }
1025 fail("Unknown type of array: " + a.getClass().getName());
1026 return -1;
1027 }
1028
1029 private int checkSumPlus(int[] a) {
1030 int checkSum = 0;
1031
1032 for (int e : a) {
1033 checkSum += e;
1034 }
1035 return checkSum;
1036 }
1037
1038 private int checkSumPlus(long[] a) {
1039 long checkSum = 0;
1040
1041 for (long e : a) {
1042 checkSum += e;
1043 }
1044 return (int) checkSum;
1045 }
1046
1047 private int checkSumPlus(byte[] a) {
1048 byte checkSum = 0;
1049
1050 for (byte e : a) {
1051 checkSum += e;
1052 }
1053 return (int) checkSum;
1054 }
1055
1056 private int checkSumPlus(char[] a) {
1057 char checkSum = 0;
1058
1059 for (char e : a) {
1060 checkSum += e;
1061 }
1062 return (int) checkSum;
1063 }
1064
1065 private int checkSumPlus(short[] a) {
1066 short checkSum = 0;
1067
1068 for (short e : a) {
1069 checkSum += e;
1070 }
1071 return (int) checkSum;
1072 }
1073
1074 private int checkSumPlus(float[] a) {
1075 int checkSum = 0;
1076
1077 for (float e : a) {
1078 checkSum += (int) e;
1079 }
1080 return checkSum;
1081 }
1082
1083 private int checkSumPlus(double[] a) {
1084 int checkSum = 0;
1085
1086 for (double e : a) {
1087 checkSum += (int) e;
1088 }
1089 return checkSum;
1090 }
1091
1092 private void sortByInsertionSort(Object a) {
1093 if (a instanceof int[]) {
1094 sortByInsertionSort((int[]) a);
1095 } else if (a instanceof long[]) {
1096 sortByInsertionSort((long[]) a);
1097 } else if (a instanceof byte[]) {
1098 sortByInsertionSort((byte[]) a);
1099 } else if (a instanceof char[]) {
1100 sortByInsertionSort((char[]) a);
1101 } else if (a instanceof short[]) {
1102 sortByInsertionSort((short[]) a);
1103 } else if (a instanceof float[]) {
1104 sortByInsertionSort((float[]) a);
1105 } else if (a instanceof double[]) {
1106 sortByInsertionSort((double[]) a);
1107 } else {
1108 fail("Unknown type of array: " + a.getClass().getName());
1109 }
1110 }
1111
1112 private void sortByInsertionSort(int[] a) {
1113 for (int j, i = 1; i < a.length; i++) {
1114 int ai = a[i];
1115
1116 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1117 a[j + 1] = a[j];
1118 }
1119 a[j + 1] = ai;
1120 }
1121 }
1122
1123 private void sortByInsertionSort(long[] a) {
1124 for (int j, i = 1; i < a.length; i++) {
1125 long ai = a[i];
1126
1127 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1128 a[j + 1] = a[j];
1129 }
1130 a[j + 1] = ai;
1131 }
1132 }
1133
1134 private void sortByInsertionSort(byte[] a) {
1135 for (int j, i = 1; i < a.length; i++) {
1136 byte ai = a[i];
1137
1138 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1139 a[j + 1] = a[j];
1140 }
1141 a[j + 1] = ai;
1142 }
1143 }
1144
1145 private void sortByInsertionSort(char[] a) {
1146 for (int j, i = 1; i < a.length; i++) {
1147 char ai = a[i];
1148
1149 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1150 a[j + 1] = a[j];
1151 }
1152 a[j + 1] = ai;
1153 }
1154 }
1155
1156 private void sortByInsertionSort(short[] a) {
1157 for (int j, i = 1; i < a.length; i++) {
1158 short ai = a[i];
1159
1160 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1161 a[j + 1] = a[j];
1162 }
1163 a[j + 1] = ai;
1164 }
1165 }
1166
1167 private void sortByInsertionSort(float[] a) {
1168 for (int j, i = 1; i < a.length; i++) {
1169 float ai = a[i];
1170
1171 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1172 a[j + 1] = a[j];
1173 }
1174 a[j + 1] = ai;
1175 }
1176 }
1177
1178 private void sortByInsertionSort(double[] a) {
1179 for (int j, i = 1; i < a.length; i++) {
1180 double ai = a[i];
1181
1182 for (j = i - 1; j >= 0 && ai < a[j]; j--) {
1183 a[j + 1] = a[j];
1184 }
1185 a[j + 1] = ai;
1186 }
1187 }
1188
1189 private void checkSubArray(Object a, int fromIndex, int toIndex) {
1190 if (a instanceof int[]) {
1191 checkSubArray((int[]) a, fromIndex, toIndex);
1192 } else if (a instanceof long[]) {
1193 checkSubArray((long[]) a, fromIndex, toIndex);
1194 } else if (a instanceof byte[]) {
1195 checkSubArray((byte[]) a, fromIndex, toIndex);
1196 } else if (a instanceof char[]) {
1197 checkSubArray((char[]) a, fromIndex, toIndex);
1198 } else if (a instanceof short[]) {
1199 checkSubArray((short[]) a, fromIndex, toIndex);
1200 } else if (a instanceof float[]) {
1201 checkSubArray((float[]) a, fromIndex, toIndex);
1202 } else if (a instanceof double[]) {
1203 checkSubArray((double[]) a, fromIndex, toIndex);
1204 } else {
1205 fail("Unknown type of array: " + a.getClass().getName());
1206 }
1207 }
1208
1209 private void checkSubArray(int[] a, int fromIndex, int toIndex) {
1210 for (int i = 0; i < fromIndex; i++) {
1211 if (a[i] != A380) {
1212 fail("Range sort changes left element at position " + i + hex(a[i], A380));
1213 }
1214 }
1215
1216 for (int i = fromIndex; i < toIndex - 1; i++) {
1217 if (a[i] > a[i + 1]) {
1218 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1219 }
1220 }
1221
1222 for (int i = toIndex; i < a.length; i++) {
1223 if (a[i] != B747) {
1224 fail("Range sort changes right element at position " + i + hex(a[i], B747));
1225 }
1226 }
1227 }
1228
1229 private void checkSubArray(long[] a, int fromIndex, int toIndex) {
1230 for (int i = 0; i < fromIndex; i++) {
1231 if (a[i] != (long) A380) {
1232 fail("Range sort changes left element at position " + i + hex(a[i], A380));
1233 }
1234 }
1235
1236 for (int i = fromIndex; i < toIndex - 1; i++) {
1237 if (a[i] > a[i + 1]) {
1238 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1239 }
1240 }
1241
1242 for (int i = toIndex; i < a.length; i++) {
1243 if (a[i] != (long) B747) {
1244 fail("Range sort changes right element at position " + i + hex(a[i], B747));
1245 }
1246 }
1247 }
1248
1249 private void checkSubArray(byte[] a, int fromIndex, int toIndex) {
1250 for (int i = 0; i < fromIndex; i++) {
1251 if (a[i] != (byte) A380) {
1252 fail("Range sort changes left element at position " + i + hex(a[i], A380));
1253 }
1254 }
1255
1256 for (int i = fromIndex; i < toIndex - 1; i++) {
1257 if (a[i] > a[i + 1]) {
1258 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1259 }
1260 }
1261
1262 for (int i = toIndex; i < a.length; i++) {
1263 if (a[i] != (byte) B747) {
1264 fail("Range sort changes right element at position " + i + hex(a[i], B747));
1265 }
1266 }
1267 }
1268
1269 private void checkSubArray(char[] a, int fromIndex, int toIndex) {
1270 for (int i = 0; i < fromIndex; i++) {
1271 if (a[i] != (char) A380) {
1272 fail("Range sort changes left element at position " + i + hex(a[i], A380));
1273 }
1274 }
1275
1276 for (int i = fromIndex; i < toIndex - 1; i++) {
1277 if (a[i] > a[i + 1]) {
1278 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1279 }
1280 }
1281
1282 for (int i = toIndex; i < a.length; i++) {
1283 if (a[i] != (char) B747) {
1284 fail("Range sort changes right element at position " + i + hex(a[i], B747));
1285 }
1286 }
1287 }
1288
1289 private void checkSubArray(short[] a, int fromIndex, int toIndex) {
1290 for (int i = 0; i < fromIndex; i++) {
1291 if (a[i] != (short) A380) {
1292 fail("Range sort changes left element at position " + i + hex(a[i], A380));
1293 }
1294 }
1295
1296 for (int i = fromIndex; i < toIndex - 1; i++) {
1297 if (a[i] > a[i + 1]) {
1298 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1299 }
1300 }
1301
1302 for (int i = toIndex; i < a.length; i++) {
1303 if (a[i] != (short) B747) {
1304 fail("Range sort changes right element at position " + i + hex(a[i], B747));
1305 }
1306 }
1307 }
1308
1309 private void checkSubArray(float[] a, int fromIndex, int toIndex) {
1310 for (int i = 0; i < fromIndex; i++) {
1311 if (a[i] != (float) A380) {
1312 fail("Range sort changes left element at position " + i + hex((long) a[i], A380));
1313 }
1314 }
1315
1316 for (int i = fromIndex; i < toIndex - 1; i++) {
1317 if (a[i] > a[i + 1]) {
1318 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1319 }
1320 }
1321
1322 for (int i = toIndex; i < a.length; i++) {
1323 if (a[i] != (float) B747) {
1324 fail("Range sort changes right element at position " + i + hex((long) a[i], B747));
1325 }
1326 }
1327 }
1328
1329 private void checkSubArray(double[] a, int fromIndex, int toIndex) {
1330 for (int i = 0; i < fromIndex; i++) {
1331 if (a[i] != (double) A380) {
1332 fail("Range sort changes left element at position " + i + hex((long) a[i], A380));
1333 }
1334 }
1335
1336 for (int i = fromIndex; i < toIndex - 1; i++) {
1337 if (a[i] > a[i + 1]) {
1338 fail("Array is not sorted at " + i + "-th position: " + a[i] + " and " + a[i + 1]);
1339 }
1340 }
1341
1342 for (int i = toIndex; i < a.length; i++) {
1343 if (a[i] != (double) B747) {
1344 fail("Range sort changes right element at position " + i + hex((long) a[i], B747));
1345 }
1346 }
1347 }
1348
1349 private void checkRange(Object a, int m) {
1350 if (a instanceof int[]) {
1351 checkRange((int[]) a, m);
1352 } else if (a instanceof long[]) {
1353 checkRange((long[]) a, m);
1354 } else if (a instanceof byte[]) {
1355 checkRange((byte[]) a, m);
1356 } else if (a instanceof char[]) {
1357 checkRange((char[]) a, m);
1358 } else if (a instanceof short[]) {
1359 checkRange((short[]) a, m);
1360 } else if (a instanceof float[]) {
1361 checkRange((float[]) a, m);
1362 } else if (a instanceof double[]) {
1363 checkRange((double[]) a, m);
1364 } else {
1365 fail("Unknown type of array: " + a.getClass().getName());
1366 }
1367 }
1368
1369 private void checkRange(int[] a, int m) {
1370 try {
1371 sortingHelper.sort(a, m + 1, m);
1372 fail(sortingHelper + " does not throw IllegalArgumentException " +
1373 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1374 } catch (IllegalArgumentException iae) {
1375 try {
1376 sortingHelper.sort(a, -m, a.length);
1377 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1378 "as expected: fromIndex = " + (-m));
1379 } catch (ArrayIndexOutOfBoundsException aoe) {
1380 try {
1381 sortingHelper.sort(a, 0, a.length + m);
1382 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1383 "as expected: toIndex = " + (a.length + m));
1384 } catch (ArrayIndexOutOfBoundsException expected) {}
1385 }
1386 }
1387 }
1388
1389 private void checkRange(long[] a, int m) {
1390 try {
1391 sortingHelper.sort(a, m + 1, m);
1392 fail(sortingHelper + " does not throw IllegalArgumentException " +
1393 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1394 } catch (IllegalArgumentException iae) {
1395 try {
1396 sortingHelper.sort(a, -m, a.length);
1397 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1398 "as expected: fromIndex = " + (-m));
1399 } catch (ArrayIndexOutOfBoundsException aoe) {
1400 try {
1401 sortingHelper.sort(a, 0, a.length + m);
1402 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1403 "as expected: toIndex = " + (a.length + m));
1404 } catch (ArrayIndexOutOfBoundsException expected) {}
1405 }
1406 }
1407 }
1408
1409 private void checkRange(byte[] a, int m) {
1410 try {
1411 sortingHelper.sort(a, m + 1, m);
1412 fail(sortingHelper + " does not throw IllegalArgumentException " +
1413 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1414 } catch (IllegalArgumentException iae) {
1415 try {
1416 sortingHelper.sort(a, -m, a.length);
1417 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1418 "as expected: fromIndex = " + (-m));
1419 } catch (ArrayIndexOutOfBoundsException aoe) {
1420 try {
1421 sortingHelper.sort(a, 0, a.length + m);
1422 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1423 "as expected: toIndex = " + (a.length + m));
1424 } catch (ArrayIndexOutOfBoundsException expected) {}
1425 }
1426 }
1427 }
1428
1429 private void checkRange(char[] a, int m) {
1430 try {
1431 sortingHelper.sort(a, m + 1, m);
1432 fail(sortingHelper + " does not throw IllegalArgumentException " +
1433 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1434 } catch (IllegalArgumentException iae) {
1435 try {
1436 sortingHelper.sort(a, -m, a.length);
1437 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1438 "as expected: fromIndex = " + (-m));
1439 } catch (ArrayIndexOutOfBoundsException aoe) {
1440 try {
1441 sortingHelper.sort(a, 0, a.length + m);
1442 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1443 "as expected: toIndex = " + (a.length + m));
1444 } catch (ArrayIndexOutOfBoundsException expected) {}
1445 }
1446 }
1447 }
1448
1449 private void checkRange(short[] a, int m) {
1450 try {
1451 sortingHelper.sort(a, m + 1, m);
1452 fail(sortingHelper + " does not throw IllegalArgumentException " +
1453 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1454 } catch (IllegalArgumentException iae) {
1455 try {
1456 sortingHelper.sort(a, -m, a.length);
1457 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1458 "as expected: fromIndex = " + (-m));
1459 } catch (ArrayIndexOutOfBoundsException aoe) {
1460 try {
1461 sortingHelper.sort(a, 0, a.length + m);
1462 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1463 "as expected: toIndex = " + (a.length + m));
1464 } catch (ArrayIndexOutOfBoundsException expected) {}
1465 }
1466 }
1467 }
1468
1469 private void checkRange(float[] a, int m) {
1470 try {
1471 sortingHelper.sort(a, m + 1, m);
1472 fail(sortingHelper + " does not throw IllegalArgumentException " +
1473 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1474 } catch (IllegalArgumentException iae) {
1475 try {
1476 sortingHelper.sort(a, -m, a.length);
1477 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1478 "as expected: fromIndex = " + (-m));
1479 } catch (ArrayIndexOutOfBoundsException aoe) {
1480 try {
1481 sortingHelper.sort(a, 0, a.length + m);
1482 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1483 "as expected: toIndex = " + (a.length + m));
1484 } catch (ArrayIndexOutOfBoundsException expected) {}
1485 }
1486 }
1487 }
1488
1489 private void checkRange(double[] a, int m) {
1490 try {
1491 sortingHelper.sort(a, m + 1, m);
1492 fail(sortingHelper + " does not throw IllegalArgumentException " +
1493 "as expected: fromIndex = " + (m + 1) + " toIndex = " + m);
1494 } catch (IllegalArgumentException iae) {
1495 try {
1496 sortingHelper.sort(a, -m, a.length);
1497 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1498 "as expected: fromIndex = " + (-m));
1499 } catch (ArrayIndexOutOfBoundsException aoe) {
1500 try {
1501 sortingHelper.sort(a, 0, a.length + m);
1502 fail(sortingHelper + " does not throw ArrayIndexOutOfBoundsException " +
1503 "as expected: toIndex = " + (a.length + m));
1504 } catch (ArrayIndexOutOfBoundsException expected) {}
1505 }
1506 }
1507 }
1508
1509 private void copy(Object dst, Object src) {
1510 if (src instanceof float[]) {
1511 copy((float[]) dst, (float[]) src);
1512 } else if (src instanceof double[]) {
1513 copy((double[]) dst, (double[]) src);
1514 } else {
1515 fail("Unknown type of array: " + src.getClass().getName());
1516 }
1517 }
1518
1519 private void copy(float[] dst, float[] src) {
1520 System.arraycopy(src, 0, dst, 0, src.length);
1521 }
1522
1523 private void copy(double[] dst, double[] src) {
1524 System.arraycopy(src, 0, dst, 0, src.length);
1525 }
1526
1527 private void printTestName(String test, TestRandom random, int length) {
1528 printTestName(test, random, length, "");
1529 }
1530
1531 private void createData(int length) {
1532 gold = new Object[] {
1533 new int[length], new long[length],
1534 new byte[length], new char[length], new short[length],
1535 new float[length], new double[length]
1536 };
1537
1538 test = new Object[] {
1539 new int[length], new long[length],
1540 new byte[length], new char[length], new short[length],
1541 new float[length], new double[length]
1542 };
1543 }
1544
1545 private void convertData(int length) {
1546 for (int i = 1; i < gold.length; i++) {
1547 TypeConverter converter = TypeConverter.values()[i - 1];
1548 converter.convert((int[])gold[0], gold[i]);
1549 }
1550
1551 for (int i = 0; i < gold.length; i++) {
1552 System.arraycopy(gold[i], 0, test[i], 0, length);
1553 }
1554 }
1555
1556 private String hex(long a, int b) {
1557 return ": " + Long.toHexString(a) + ", must be " + Integer.toHexString(b);
1558 }
1559
1560 private void printTestName(String test, TestRandom random, int length, String message) {
1561 out.println( "[" + sortingHelper + "] '" + test +
1562 "' length = " + length + ", random = " + random + message);
1563 }
1564
1565 private static enum TypeConverter {
1566 LONG {
1567 void convert(int[] src, Object dst) {
1568 long[] b = (long[]) dst;
1569
1570 for (int i = 0; i < src.length; i++) {
1571 b[i] = (long) src[i];
1572 }
1573 }
1574 },
1575
1576 BYTE {
1577 void convert(int[] src, Object dst) {
1578 byte[] b = (byte[]) dst;
1579
1580 for (int i = 0; i < src.length; i++) {
1581 b[i] = (byte) src[i];
1582 }
1583 }
1584 },
1585
1586 CHAR {
1587 void convert(int[] src, Object dst) {
1588 char[] b = (char[]) dst;
1589
1590 for (int i = 0; i < src.length; i++) {
1591 b[i] = (char) src[i];
1592 }
1593 }
1594 },
1595
1596 SHORT {
1597 void convert(int[] src, Object dst) {
1598 short[] b = (short[]) dst;
1599
1600 for (int i = 0; i < src.length; i++) {
1601 b[i] = (short) src[i];
1602 }
1603 }
1604 },
1605
1606 FLOAT {
1607 void convert(int[] src, Object dst) {
1608 float[] b = (float[]) dst;
1609
1610 for (int i = 0; i < src.length; i++) {
1611 b[i] = (float) src[i];
1612 }
1613 }
1614 },
1615
1616 DOUBLE {
1617 void convert(int[] src, Object dst) {
1618 double[] b = (double[]) dst;
1619
1620 for (int i = 0; i < src.length; i++) {
1621 b[i] = (double) src[i];
1622 }
1623 }
1624 };
1625
1626 abstract void convert(int[] src, Object dst);
1627 }
1628
1629 private static enum SortedBuilder {
1630 STEPS {
1631 void build(int[] a, int m) {
1632 for (int i = 0; i < m; i++) {
1633 a[i] = 0;
1634 }
1635
1636 for (int i = m; i < a.length; i++) {
1637 a[i] = 1;
1638 }
1639 }
1640 };
1641
1642 abstract void build(int[] a, int m);
1643 }
1644
1645 private static enum UnsortedBuilder {
1646 RANDOM {
1647 void build(int[] a, int m, Random random) {
1648 for (int i = 0; i < a.length; i++) {
1649 a[i] = random.nextInt();
1650 }
1651 }
1652 },
1653
1654 ASCENDING {
1655 void build(int[] a, int m, Random random) {
1656 for (int i = 0; i < a.length; i++) {
1657 a[i] = m + i;
1658 }
1659 }
1660 },
1661
1662 DESCENDING {
1663 void build(int[] a, int m, Random random) {
1664 for (int i = 0; i < a.length; i++) {
1665 a[i] = a.length - m - i;
1666 }
1667 }
1668 },
1669
1670 EQUAL {
1671 void build(int[] a, int m, Random random) {
1672 for (int i = 0; i < a.length; i++) {
1673 a[i] = m;
1674 }
1675 }
1676 },
1677
1678 SAW {
1679 void build(int[] a, int m, Random random) {
1680 int incCount = 1;
1681 int decCount = a.length;
1682 int i = 0;
1683 int period = m--;
1684
1685 while (true) {
1686 for (int k = 1; k <= period; k++) {
1687 if (i >= a.length) {
1688 return;
1689 }
1690 a[i++] = incCount++;
1691 }
1692 period += m;
1693
1694 for (int k = 1; k <= period; k++) {
1695 if (i >= a.length) {
1696 return;
1697 }
1698 a[i++] = decCount--;
1699 }
1700 period += m;
1701 }
1702 }
1703 },
1704
1705 REPEATED {
1706 void build(int[] a, int m, Random random) {
1707 for (int i = 0; i < a.length; i++) {
1708 a[i] = i % m;
1709 }
1710 }
1711 },
1712
1713 DUPLICATED {
1714 void build(int[] a, int m, Random random) {
1715 for (int i = 0; i < a.length; i++) {
1716 a[i] = random.nextInt(m);
1717 }
1718 }
1719 },
1720
1721 ORGAN_PIPES {
1722 void build(int[] a, int m, Random random) {
1723 int middle = a.length / (m + 1);
1724
1725 for (int i = 0; i < middle; i++) {
1726 a[i] = i;
1727 }
1728
1729 for (int i = middle; i < a.length; i++) {
1730 a[i] = a.length - i - 1;
1731 }
1732 }
1733 },
1734
1735 STAGGER {
1736 void build(int[] a, int m, Random random) {
1737 for (int i = 0; i < a.length; i++) {
1738 a[i] = (i * m + i) % a.length;
1739 }
1740 }
1741 },
1742
1743 PLATEAU {
1744 void build(int[] a, int m, Random random) {
1745 for (int i = 0; i < a.length; i++) {
1746 a[i] = Math.min(i, m);
1747 }
1748 }
1749 },
1750
1751 SHUFFLE {
1752 void build(int[] a, int m, Random random) {
1753 int x = 0, y = 0;
1754
1755 for (int i = 0; i < a.length; i++) {
1756 a[i] = random.nextBoolean() ? (x += 2) : (y += 2);
1757 }
1758 }
1759 },
1760
1761 LATCH {
1762 void build(int[] a, int m, Random random) {
1763 int max = a.length / m;
1764 max = max < 2 ? 2 : max;
1765
1766 for (int i = 0; i < a.length; i++) {
1767 a[i] = i % max;
1768 }
1769 }
1770 };
1771
1772 abstract void build(int[] a, int m, Random random);
1773 }
1774
1775 private static enum MergingBuilder {
1776 ASCENDING {
1777 void build(int[] a, int m) {
1778 int period = a.length / m;
1779 int v = 1, i = 0;
1780
1781 for (int k = 0; k < m; k++) {
1782 v = 1;
1783
1784 for (int p = 0; p < period; p++) {
1785 a[i++] = v++;
1786 }
1787 }
1788
1789 for (int j = i; j < a.length - 1; j++) {
1790 a[j] = v++;
1791 }
1792
1793 a[a.length - 1] = 0;
1794 }
1795 },
1796
1797 DESCENDING {
1798 void build(int[] a, int m) {
1799 int period = a.length / m;
1800 int v = -1, i = 0;
1801
1802 for (int k = 0; k < m; k++) {
1803 v = -1;
1804
1805 for (int p = 0; p < period; p++) {
1806 a[i++] = v--;
1807 }
1808 }
1809
1810 for (int j = i; j < a.length - 1; j++) {
1811 a[j] = v--;
1812 }
1813
1814 a[a.length - 1] = 0;
1815 }
1816 },
1817
1818 POINT {
1819 void build(int[] a, int m) {
1820 for (int i = 0; i < a.length; i++) {
1821 a[i] = 0;
1822 }
1823 a[a.length / 2] = m;
1824 }
1825 },
1826
1827 LINE {
1828 void build(int[] a, int m) {
1829 for (int i = 0; i < a.length; i++) {
1830 a[i] = i;
1831 }
1832 reverse(a, 0, a.length - 1);
1833 }
1834 },
1835
1836 PEARL {
1837 void build(int[] a, int m) {
1838 for (int i = 0; i < a.length; i++) {
1839 a[i] = i;
1840 }
1841 reverse(a, 0, 2);
1842 }
1843 },
1844
1845 RING {
1846 void build(int[] a, int m) {
1847 int k1 = a.length / 3;
1848 int k2 = a.length / 3 * 2;
1849 int level = a.length / 3;
1850
1851 for (int i = 0, k = level; i < k1; i++) {
1852 a[i] = k--;
1853 }
1854
1855 for (int i = k1; i < k2; i++) {
1856 a[i] = 0;
1857 }
1858
1859 for (int i = k2, k = level; i < a.length; i++) {
1860 a[i] = k--;
1861 }
1862 }
1863 };
1864
1865 abstract void build(int[] a, int m);
1866
1867 private static void reverse(int[] a, int lo, int hi) {
1868 for (--hi; lo < hi; ) {
1869 int tmp = a[lo];
1870 a[lo++] = a[hi];
1871 a[hi--] = tmp;
1872 }
1873 }
1874 }
1875
1876 private static enum NegativeZeroBuilder {
1877 FLOAT {
1878 void build(Object o, Random random) {
1879 float[] a = (float[]) o;
1880
1881 for (int i = 0; i < a.length; i++) {
1882 a[i] = random.nextBoolean() ? -0.0f : 0.0f;
1883 }
1884 }
1885 },
1886
1887 DOUBLE {
1888 void build(Object o, Random random) {
1889 double[] a = (double[]) o;
1890
1891 for (int i = 0; i < a.length; i++) {
1892 a[i] = random.nextBoolean() ? -0.0d : 0.0d;
1893 }
1894 }
1895 };
1896
1897 abstract void build(Object o, Random random);
1898 }
1899
1900 private static enum FloatingPointBuilder {
1901 FLOAT {
1902 void build(Object o, int a, int g, int z, int n, int p, Random random) {
1903 float negativeValue = -random.nextFloat();
1904 float positiveValue = random.nextFloat();
1905 float[] x = (float[]) o;
1906 int fromIndex = 0;
1907
1908 writeValue(x, negativeValue, fromIndex, n);
1909 fromIndex += n;
1910
1911 writeValue(x, -0.0f, fromIndex, g);
1912 fromIndex += g;
1913
1914 writeValue(x, 0.0f, fromIndex, z);
1915 fromIndex += z;
1916
1917 writeValue(x, positiveValue, fromIndex, p);
1918 fromIndex += p;
1919
1920 writeValue(x, Float.NaN, fromIndex, a);
1921 }
1922 },
1923
1924 DOUBLE {
1925 void build(Object o, int a, int g, int z, int n, int p, Random random) {
1926 double negativeValue = -random.nextFloat();
1927 double positiveValue = random.nextFloat();
1928 double[] x = (double[]) o;
1929 int fromIndex = 0;
1930
1931 writeValue(x, negativeValue, fromIndex, n);
1932 fromIndex += n;
1933
1934 writeValue(x, -0.0d, fromIndex, g);
1935 fromIndex += g;
1936
1937 writeValue(x, 0.0d, fromIndex, z);
1938 fromIndex += z;
1939
1940 writeValue(x, positiveValue, fromIndex, p);
1941 fromIndex += p;
1942
1943 writeValue(x, Double.NaN, fromIndex, a);
1944 }
1945 };
1946
1947 abstract void build(Object o, int a, int g, int z, int n, int p, Random random);
1948
1949 private static void writeValue(float[] a, float value, int fromIndex, int count) {
1950 for (int i = fromIndex; i < fromIndex + count; i++) {
1951 a[i] = value;
1952 }
1953 }
1954
1955 private static void writeValue(double[] a, double value, int fromIndex, int count) {
1956 for (int i = fromIndex; i < fromIndex + count; i++) {
1957 a[i] = value;
1958 }
1959 }
1960 }
1961
1962 private static Comparator<Pair> pairComparator = new Comparator<Pair>() {
1963
1964 @Override
1965 public int compare(Pair p1, Pair p2) {
1966 return p1.compareTo(p2);
1967 }
1968 };
1969
1970 private static class Pair implements Comparable<Pair> {
1971
1972 private Pair(int key, int value) {
1973 this.key = key;
1974 this.value = value;
1975 }
1976
1977 int getKey() {
1978 return key;
1979 }
1980
1981 int getValue() {
1982 return value;
1983 }
1984
1985 @Override
1986 public int compareTo(Pair pair) {
1987 return Integer.compare(key, pair.key);
1988 }
1989
1990 @Override
1991 public String toString() {
1992 return "(" + key + ", " + value + ")";
1993 }
1994
1995 private int key;
1996 private int value;
1997 }
1998
1999 private static class TestRandom extends Random {
2000
2001 private static final TestRandom BABA = new TestRandom(0xBABA);
2002 private static final TestRandom DEDA = new TestRandom(0xDEDA);
2003 private static final TestRandom C0FFEE = new TestRandom(0xC0FFEE);
2004
2005 private TestRandom(long seed) {
2006 super(seed);
2007 this.seed = Long.toHexString(seed).toUpperCase();
2008 }
2009
2010 @Override
2011 public String toString() {
2012 return seed;
2013 }
2014
2015 private String seed;
2016 }
2017 }