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 }