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