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