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;
1260
1261 for (short e : a) {
1262 checkSum ^= e;
1263 }
1264 return (int) checkSum;
1265 }
1266
1267 private static int checkSumXor(byte[] a) {
1268 byte checkSum = 0;
1269
1270 for (byte e : a) {
1271 checkSum ^= e;
1272 }
1273 return (int) checkSum;
1274 }
1275
1276 private static int checkSumXor(char[] a) {
1277 char checkSum = 0;
1278
1279 for (char e : a) {
1280 checkSum ^= e;
1281 }
1282 return (int) checkSum;
1283 }
1284
1285 private static int checkSumXor(float[] a) {
1286 int checkSum = 0;
1287
1288 for (float e : a) {
1289 checkSum ^= (int) e;
1290 }
1291 return checkSum;
1292 }
1293
1294 private static int checkSumXor(double[] a) {
1295 int checkSum = 0;
1296
1297 for (double e : a) {
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 }
1342 return (int) checkSum;
1343 }
1344
1345 private static int checkSumPlus(short[] a) {
1346 short checkSum = 0;
1347
1348 for (short e : a) {
1349 checkSum += e;
1350 }
1351 return (int) checkSum;
1352 }
1353
1354 private static int checkSumPlus(byte[] a) {
1355 byte checkSum = 0;
1356
1357 for (byte e : a) {
1358 checkSum += e;
1359 }
1360 return (int) checkSum;
1361 }
1362
1363 private static int checkSumPlus(char[] a) {
1364 char checkSum = 0;
1365
1366 for (char e : a) {
1367 checkSum += e;
1368 }
1369 return (int) checkSum;
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 }