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