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