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