Sorting.java revision 2571:a5a34c696d62
158713Sjhb/* 258713Sjhb * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved. 358713Sjhb * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 458713Sjhb * 5125517Sru * This code is free software; you can redistribute it and/or modify it 6125517Sru * under the terms of the GNU General Public License version 2 only, as 7125537Sru * published by the Free Software Foundation. 8125537Sru * 9116864Speter * This code is distributed in the hope that it will be useful, but WITHOUT 10116864Speter * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11116864Speter * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12116864Speter * version 2 for more details (a copy is included in the LICENSE file that 13116864Speter * accompanied this code). 14125516Sru * 15125537Sru * You should have received a copy of the GNU General Public License version 16125537Sru * 2 along with this work; if not, write to the Free Software Foundation, 17125537Sru * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18116864Speter * 19125537Sru * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20125537Sru * or visit www.oracle.com if you need additional information or have any 21125537Sru * questions. 22125537Sru */ 23125537Sru 24125537Sru/* 25125537Sru * @test 26125537Sru * @bug 6880672 6896573 6899694 27125537Sru * @summary Exercise Arrays.sort 28125537Sru * @build Sorting 29 * @run main Sorting -shortrun 30 * 31 * @author Vladimir Yaroslavskiy 32 * @author Jon Bentley 33 * @author Josh Bloch 34 */ 35 36import java.util.Arrays; 37import java.util.Random; 38import java.io.PrintStream; 39 40public 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("\nPASSED 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 (long random : randoms) { 82 reset(random); 83 84 for (int length : lengths) { 85 testAndCheckWithCheckSum(length, random); 86 } 87 reset(random); 88 89 for (int length : lengths) { 90 testAndCheckWithScrambling(length, random); 91 } 92 reset(random); 93 94 for (int length : lengths) { 95 testAndCheckFloat(length, random); 96 } 97 reset(random); 98 99 for (int length : lengths) { 100 testAndCheckDouble(length, random); 101 } 102 reset(random); 103 104 for (int length : lengths) { 105 testAndCheckRange(length, random); 106 } 107 reset(random); 108 109 for (int length : lengths) { 110 testAndCheckSubArray(length, random); 111 } 112 reset(random); 113 114 for (int length : lengths) { 115 testStable(length, random); 116 } 117 } 118 } 119 120 private static void testEmptyAndNullIntArray() { 121 ourDescription = "Check empty and null array"; 122 Arrays.sort(new int[] {}); 123 Arrays.sort(new int[] {}, 0, 0); 124 125 try { 126 Arrays.sort((int[]) null); 127 } catch (NullPointerException expected) { 128 try { 129 Arrays.sort((int[]) null, 0, 0); 130 } catch (NullPointerException expected2) { 131 return; 132 } 133 failed("Arrays.sort(int[],fromIndex,toIndex) shouldn't " + 134 "catch null array"); 135 } 136 failed("Arrays.sort(int[]) shouldn't catch null array"); 137 } 138 139 private static void testEmptyAndNullLongArray() { 140 ourDescription = "Check empty and null array"; 141 Arrays.sort(new long[] {}); 142 Arrays.sort(new long[] {}, 0, 0); 143 144 try { 145 Arrays.sort((long[]) null); 146 } catch (NullPointerException expected) { 147 try { 148 Arrays.sort((long[]) null, 0, 0); 149 } catch (NullPointerException expected2) { 150 return; 151 } 152 failed("Arrays.sort(long[],fromIndex,toIndex) shouldn't " + 153 "catch null array"); 154 } 155 failed("Arrays.sort(long[]) shouldn't catch null array"); 156 } 157 158 private static void testEmptyAndNullShortArray() { 159 ourDescription = "Check empty and null array"; 160 Arrays.sort(new short[] {}); 161 Arrays.sort(new short[] {}, 0, 0); 162 163 try { 164 Arrays.sort((short[]) null); 165 } catch (NullPointerException expected) { 166 try { 167 Arrays.sort((short[]) null, 0, 0); 168 } catch (NullPointerException expected2) { 169 return; 170 } 171 failed("Arrays.sort(short[],fromIndex,toIndex) shouldn't " + 172 "catch null array"); 173 } 174 failed("Arrays.sort(short[]) shouldn't catch null array"); 175 } 176 177 private static void testEmptyAndNullCharArray() { 178 ourDescription = "Check empty and null array"; 179 Arrays.sort(new char[] {}); 180 Arrays.sort(new char[] {}, 0, 0); 181 182 try { 183 Arrays.sort((char[]) null); 184 } catch (NullPointerException expected) { 185 try { 186 Arrays.sort((char[]) null, 0, 0); 187 } catch (NullPointerException expected2) { 188 return; 189 } 190 failed("Arrays.sort(char[],fromIndex,toIndex) shouldn't " + 191 "catch null array"); 192 } 193 failed("Arrays.sort(char[]) shouldn't catch null array"); 194 } 195 196 private static void testEmptyAndNullByteArray() { 197 ourDescription = "Check empty and null array"; 198 Arrays.sort(new byte[] {}); 199 Arrays.sort(new byte[] {}, 0, 0); 200 201 try { 202 Arrays.sort((byte[]) null); 203 } catch (NullPointerException expected) { 204 try { 205 Arrays.sort((byte[]) null, 0, 0); 206 } catch (NullPointerException expected2) { 207 return; 208 } 209 failed("Arrays.sort(byte[],fromIndex,toIndex) shouldn't " + 210 "catch null array"); 211 } 212 failed("Arrays.sort(byte[]) shouldn't catch null array"); 213 } 214 215 private static void testEmptyAndNullFloatArray() { 216 ourDescription = "Check empty and null array"; 217 Arrays.sort(new float[] {}); 218 Arrays.sort(new float[] {}, 0, 0); 219 220 try { 221 Arrays.sort((float[]) null); 222 } catch (NullPointerException expected) { 223 try { 224 Arrays.sort((float[]) null, 0, 0); 225 } catch (NullPointerException expected2) { 226 return; 227 } 228 failed("Arrays.sort(float[],fromIndex,toIndex) shouldn't " + 229 "catch null array"); 230 } 231 failed("Arrays.sort(float[]) shouldn't catch null array"); 232 } 233 234 private static void testEmptyAndNullDoubleArray() { 235 ourDescription = "Check empty and null array"; 236 Arrays.sort(new double[] {}); 237 Arrays.sort(new double[] {}, 0, 0); 238 239 try { 240 Arrays.sort((double[]) null); 241 } catch (NullPointerException expected) { 242 try { 243 Arrays.sort((double[]) null, 0, 0); 244 } catch (NullPointerException expected2) { 245 return; 246 } 247 failed("Arrays.sort(double[],fromIndex,toIndex) shouldn't " + 248 "catch null array"); 249 } 250 failed("Arrays.sort(double[]) shouldn't catch null array"); 251 } 252 253 private static void testAndCheckSubArray(int length, long random) { 254 ourDescription = "Check sorting of subarray"; 255 int[] golden = new int[length]; 256 boolean newLine = false; 257 258 for (int m = 1; m < length / 2; m *= 2) { 259 newLine = true; 260 int fromIndex = m; 261 int toIndex = length - m; 262 263 prepareSubArray(golden, fromIndex, toIndex, m); 264 int[] test = golden.clone(); 265 266 for (TypeConverter converter : TypeConverter.values()) { 267 out.println("Test 'subarray': " + converter + 268 " length = " + length + ", m = " + m); 269 Object convertedGolden = converter.convert(golden); 270 Object convertedTest = converter.convert(test); 271 // outArray(test); 272 sortSubArray(convertedTest, fromIndex, toIndex); 273 // outArray(test); 274 checkSubArray(convertedTest, fromIndex, toIndex, m); 275 } 276 } 277 if (newLine) { 278 out.println(); 279 } 280 } 281 282 private static void testAndCheckRange(int length, long random) { 283 ourDescription = "Check range check"; 284 int[] golden = new int[length]; 285 286 for (int m = 1; m < 2 * length; m *= 2) { 287 for (int i = 1; i <= length; i++) { 288 golden[i - 1] = i % m + m % i; 289 } 290 for (TypeConverter converter : TypeConverter.values()) { 291 out.println("Test 'range': " + converter + 292 ", length = " + length + ", m = " + m); 293 Object convertedGolden = converter.convert(golden); 294 checkRange(convertedGolden, m); 295 } 296 } 297 out.println(); 298 } 299 300 private static void testStable(int length, long random) { 301 ourDescription = "Check if sorting is stable"; 302 Pair[] a = build(length); 303 304 out.println("Test 'stable': " + "random = " + random + 305 ", length = " + length); 306 Arrays.sort(a); 307 checkSorted(a); 308 checkStable(a); 309 } 310 311 private static void checkSorted(Pair[] a) { 312 for (int i = 0; i < a.length - 1; i++) { 313 if (a[i].getKey() > a[i + 1].getKey()) { 314 failed(i, "" + a[i].getKey(), "" + a[i + 1].getKey()); 315 } 316 } 317 } 318 319 private static void checkStable(Pair[] a) { 320 for (int i = 0; i < a.length / 4; ) { 321 int key1 = a[i].getKey(); 322 int value1 = a[i++].getValue(); 323 int key2 = a[i].getKey(); 324 int value2 = a[i++].getValue(); 325 int key3 = a[i].getKey(); 326 int value3 = a[i++].getValue(); 327 int key4 = a[i].getKey(); 328 int value4 = a[i++].getValue(); 329 330 if (!(key1 == key2 && key2 == key3 && key3 == key4)) { 331 failed("On position " + i + " must keys are different " + 332 key1 + ", " + key2 + ", " + key3 + ", " + key4); 333 } 334 if (!(value1 < value2 && value2 < value3 && value3 < value4)) { 335 failed("Sorting is not stable at position " + i + 336 ". Second values have been changed: " + value1 + ", " + 337 value2 + ", " + value3 + ", " + value4); 338 } 339 } 340 } 341 342 private static Pair[] build(int length) { 343 Pair[] a = new Pair[length * 4]; 344 345 for (int i = 0; i < a.length; ) { 346 int key = ourRandom.nextInt(); 347 a[i++] = new Pair(key, 1); 348 a[i++] = new Pair(key, 2); 349 a[i++] = new Pair(key, 3); 350 a[i++] = new Pair(key, 4); 351 } 352 return a; 353 } 354 355 private static final class Pair implements Comparable<Pair> { 356 Pair(int key, int value) { 357 myKey = key; 358 myValue = value; 359 } 360 361 int getKey() { 362 return myKey; 363 } 364 365 int getValue() { 366 return myValue; 367 } 368 369 public int compareTo(Pair pair) { 370 if (myKey < pair.myKey) { 371 return -1; 372 } 373 if (myKey > pair.myKey) { 374 return 1; 375 } 376 return 0; 377 } 378 379 @Override 380 public String toString() { 381 return "(" + myKey + ", " + myValue + ")"; 382 } 383 384 private int myKey; 385 private int myValue; 386 } 387 388 private static void testAndCheckWithCheckSum(int length, long random) { 389 ourDescription = "Check sorting with check sum"; 390 int[] golden = new int[length]; 391 392 for (int m = 1; m < 2 * length; m *= 2) { 393 for (UnsortedBuilder builder : UnsortedBuilder.values()) { 394 builder.build(golden, m); 395 int[] test = golden.clone(); 396 397 for (TypeConverter converter : TypeConverter.values()) { 398 out.println("Test 'check sum': " + converter + " " + 399 builder + "random = " + random + ", length = " + 400 length + ", m = " + m); 401 Object convertedGolden = converter.convert(golden); 402 Object convertedTest = converter.convert(test); 403 sort(convertedTest); 404 checkWithCheckSum(convertedTest, convertedGolden); 405 } 406 } 407 } 408 out.println(); 409 } 410 411 private static void testAndCheckWithScrambling(int length, long random) { 412 ourDescription = "Check sorting with scrambling"; 413 int[] golden = new int[length]; 414 415 for (int m = 1; m <= 7; m++) { 416 if (m > length) { 417 break; 418 } 419 for (SortedBuilder builder : SortedBuilder.values()) { 420 builder.build(golden, m); 421 int[] test = golden.clone(); 422 scramble(test); 423 424 for (TypeConverter converter : TypeConverter.values()) { 425 out.println("Test 'scrambling': " + converter + " " + 426 builder + "random = " + random + ", length = " + 427 length + ", m = " + m); 428 Object convertedGolden = converter.convert(golden); 429 Object convertedTest = converter.convert(test); 430 sort(convertedTest); 431 compare(convertedTest, convertedGolden); 432 } 433 } 434 } 435 out.println(); 436 } 437 438 private static void testAndCheckFloat(int length, long random) { 439 ourDescription = "Check float sorting"; 440 float[] golden = new float[length]; 441 final int MAX = 10; 442 boolean newLine = false; 443 444 for (int a = 0; a <= MAX; a++) { 445 for (int g = 0; g <= MAX; g++) { 446 for (int z = 0; z <= MAX; z++) { 447 for (int n = 0; n <= MAX; n++) { 448 for (int p = 0; p <= MAX; p++) { 449 if (a + g + z + n + p > length) { 450 continue; 451 } 452 if (a + g + z + n + p < length) { 453 continue; 454 } 455 for (FloatBuilder builder : FloatBuilder.values()) { 456 out.println("Test 'float': random = " + random + 457 ", length = " + length + ", a = " + a + 458 ", g = " + g + ", z = " + z + ", n = " + n + 459 ", p = " + p); 460 builder.build(golden, a, g, z, n, p); 461 float[] test = golden.clone(); 462 scramble(test); 463 // outArray(test); 464 sort(test); 465 // outArray(test); 466 compare(test, golden, a, n, g); 467 } 468 newLine = true; 469 } 470 } 471 } 472 } 473 } 474 if (newLine) { 475 out.println(); 476 } 477 } 478 479 private static void testAndCheckDouble(int length, long random) { 480 ourDescription = "Check double sorting"; 481 double[] golden = new double[length]; 482 final int MAX = 10; 483 boolean newLine = false; 484 485 for (int a = 0; a <= MAX; a++) { 486 for (int g = 0; g <= MAX; g++) { 487 for (int z = 0; z <= MAX; z++) { 488 for (int n = 0; n <= MAX; n++) { 489 for (int p = 0; p <= MAX; p++) { 490 if (a + g + z + n + p > length) { 491 continue; 492 } 493 if (a + g + z + n + p < length) { 494 continue; 495 } 496 for (DoubleBuilder builder : DoubleBuilder.values()) { 497 out.println("Test 'double': random = " + random + 498 ", length = " + length + ", a = " + a + ", g = " + 499 g + ", z = " + z + ", n = " + n + ", p = " + p); 500 builder.build(golden, a, g, z, n, p); 501 double[] test = golden.clone(); 502 scramble(test); 503 // outArray(test); 504 sort(test); 505 // outArray(test); 506 compare(test, golden, a, n, g); 507 } 508 newLine = true; 509 } 510 } 511 } 512 } 513 } 514 if (newLine) { 515 out.println(); 516 } 517 } 518 519 private static void prepareSubArray(int[] a, int fromIndex, int toIndex, int m) { 520 for (int i = 0; i < fromIndex; i++) { 521 a[i] = 0xBABA; 522 } 523 for (int i = fromIndex; i < toIndex; i++) { 524 a[i] = -i + m; 525 } 526 for (int i = toIndex; i < a.length; i++) { 527 a[i] = 0xDEDA; 528 } 529 } 530 531 private static void scramble(int[] a) { 532 for (int i = 0; i < a.length * 7; i++) { 533 swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.length)); 534 } 535 } 536 537 private static void scramble(float[] a) { 538 for (int i = 0; i < a.length * 7; i++) { 539 swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.length)); 540 } 541 } 542 543 private static void scramble(double[] a) { 544 for (int i = 0; i < a.length * 7; i++) { 545 swap(a, ourRandom.nextInt(a.length), ourRandom.nextInt(a.length)); 546 } 547 } 548 549 private static void swap(int[] a, int i, int j) { 550 int t = a[i]; 551 a[i] = a[j]; 552 a[j] = t; 553 } 554 555 private static void swap(float[] a, int i, int j) { 556 float t = a[i]; 557 a[i] = a[j]; 558 a[j] = t; 559 } 560 561 private static void swap(double[] a, int i, int j) { 562 double t = a[i]; 563 a[i] = a[j]; 564 a[j] = t; 565 } 566 567 private static enum TypeConverter { 568 INT { 569 Object convert(int[] a) { 570 return a.clone(); 571 } 572 }, 573 LONG { 574 Object convert(int[] a) { 575 long[] b = new long[a.length]; 576 577 for (int i = 0; i < a.length; i++) { 578 b[i] = (long) a[i]; 579 } 580 return b; 581 } 582 }, 583 BYTE { 584 Object convert(int[] a) { 585 byte[] b = new byte[a.length]; 586 587 for (int i = 0; i < a.length; i++) { 588 b[i] = (byte) a[i]; 589 } 590 return b; 591 } 592 }, 593 SHORT { 594 Object convert(int[] a) { 595 short[] b = new short[a.length]; 596 597 for (int i = 0; i < a.length; i++) { 598 b[i] = (short) a[i]; 599 } 600 return b; 601 } 602 }, 603 CHAR { 604 Object convert(int[] a) { 605 char[] b = new char[a.length]; 606 607 for (int i = 0; i < a.length; i++) { 608 b[i] = (char) a[i]; 609 } 610 return b; 611 } 612 }, 613 FLOAT { 614 Object convert(int[] a) { 615 float[] b = new float[a.length]; 616 617 for (int i = 0; i < a.length; i++) { 618 b[i] = (float) a[i]; 619 } 620 return b; 621 } 622 }, 623 DOUBLE { 624 Object convert(int[] a) { 625 double[] b = new double[a.length]; 626 627 for (int i = 0; i < a.length; i++) { 628 b[i] = (double) a[i]; 629 } 630 return b; 631 } 632 }, 633 INTEGER { 634 Object convert(int[] a) { 635 Integer[] b = new Integer[a.length]; 636 637 for (int i = 0; i < a.length; i++) { 638 b[i] = new Integer(a[i]); 639 } 640 return b; 641 } 642 }; 643 644 abstract Object convert(int[] a); 645 646 @Override public String toString() { 647 String name = name(); 648 649 for (int i = name.length(); i < 9; i++) { 650 name += " "; 651 } 652 return name; 653 } 654 } 655 656 private static enum FloatBuilder { 657 SIMPLE { 658 void build(float[] x, int a, int g, int z, int n, int p) { 659 int fromIndex = 0; 660 float negativeValue = -ourRandom.nextFloat(); 661 float positiveValue = ourRandom.nextFloat(); 662 663 writeValue(x, negativeValue, fromIndex, n); 664 fromIndex += n; 665 666 writeValue(x, -0.0f, fromIndex, g); 667 fromIndex += g; 668 669 writeValue(x, 0.0f, fromIndex, z); 670 fromIndex += z; 671 672 writeValue(x, positiveValue, fromIndex, p); 673 fromIndex += p; 674 675 writeValue(x, Float.NaN, fromIndex, a); 676 } 677 }; 678 679 abstract void build(float[] x, int a, int g, int z, int n, int p); 680 } 681 682 private static enum DoubleBuilder { 683 SIMPLE { 684 void build(double[] x, int a, int g, int z, int n, int p) { 685 int fromIndex = 0; 686 double negativeValue = -ourRandom.nextFloat(); 687 double positiveValue = ourRandom.nextFloat(); 688 689 writeValue(x, negativeValue, fromIndex, n); 690 fromIndex += n; 691 692 writeValue(x, -0.0d, fromIndex, g); 693 fromIndex += g; 694 695 writeValue(x, 0.0d, fromIndex, z); 696 fromIndex += z; 697 698 writeValue(x, positiveValue, fromIndex, p); 699 fromIndex += p; 700 701 writeValue(x, Double.NaN, fromIndex, a); 702 } 703 }; 704 705 abstract void build(double[] x, int a, int g, int z, int n, int p); 706 } 707 708 private static void writeValue(float[] a, float value, int fromIndex, int count) { 709 for (int i = fromIndex; i < fromIndex + count; i++) { 710 a[i] = value; 711 } 712 } 713 714 private static void compare(float[] a, float[] b, int numNaN, int numNeg, int numNegZero) { 715 for (int i = a.length - numNaN; i < a.length; i++) { 716 if (a[i] == a[i]) { 717 failed("On position " + i + " must be NaN instead of " + a[i]); 718 } 719 } 720 final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f); 721 722 for (int i = numNeg; i < numNeg + numNegZero; i++) { 723 if (NEGATIVE_ZERO != Float.floatToIntBits(a[i])) { 724 failed("On position " + i + " must be -0.0f instead of " + a[i]); 725 } 726 } 727 for (int i = 0; i < a.length - numNaN; i++) { 728 if (a[i] != b[i]) { 729 failed(i, "" + a[i], "" + b[i]); 730 } 731 } 732 } 733 734 private static void writeValue(double[] a, double value, int fromIndex, int count) { 735 for (int i = fromIndex; i < fromIndex + count; i++) { 736 a[i] = value; 737 } 738 } 739 740 private static void compare(double[] a, double[] b, int numNaN, int numNeg, int numNegZero) { 741 for (int i = a.length - numNaN; i < a.length; i++) { 742 if (a[i] == a[i]) { 743 failed("On position " + i + " must be NaN instead of " + a[i]); 744 } 745 } 746 final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d); 747 748 for (int i = numNeg; i < numNeg + numNegZero; i++) { 749 if (NEGATIVE_ZERO != Double.doubleToLongBits(a[i])) { 750 failed("On position " + i + " must be -0.0d instead of " + a[i]); 751 } 752 } 753 for (int i = 0; i < a.length - numNaN; i++) { 754 if (a[i] != b[i]) { 755 failed(i, "" + a[i], "" + b[i]); 756 } 757 } 758 } 759 760 private static enum SortedBuilder { 761 REPEATED { 762 void build(int[] a, int m) { 763 int period = a.length / m; 764 int i = 0; 765 int k = 0; 766 767 while (true) { 768 for (int t = 1; t <= period; t++) { 769 if (i >= a.length) { 770 return; 771 } 772 a[i++] = k; 773 } 774 if (i >= a.length) { 775 return; 776 } 777 k++; 778 } 779 } 780 }, 781 782 ORGAN_PIPES { 783 void build(int[] a, int m) { 784 int i = 0; 785 int k = m; 786 787 while (true) { 788 for (int t = 1; t <= m; t++) { 789 if (i >= a.length) { 790 return; 791 } 792 a[i++] = k; 793 } 794 } 795 } 796 }; 797 798 abstract void build(int[] a, int m); 799 800 @Override public String toString() { 801 String name = name(); 802 803 for (int i = name.length(); i < 12; i++) { 804 name += " "; 805 } 806 return name; 807 } 808 } 809 810 private static enum UnsortedBuilder { 811 RANDOM { 812 void build(int[] a, int m) { 813 for (int i = 0; i < a.length; i++) { 814 a[i] = ourRandom.nextInt(); 815 } 816 } 817 }, 818 ASCENDING { 819 void build(int[] a, int m) { 820 for (int i = 0; i < a.length; i++) { 821 a[i] = m + i; 822 } 823 } 824 }, 825 DESCENDING { 826 void build(int[] a, int m) { 827 for (int i = 0; i < a.length; i++) { 828 a[i] = a.length - m - i; 829 } 830 } 831 }, 832 ALL_EQUAL { 833 void build(int[] a, int m) { 834 for (int i = 0; i < a.length; i++) { 835 a[i] = m; 836 } 837 } 838 }, 839 SAW { 840 void build(int[] a, int m) { 841 int incCount = 1; 842 int decCount = a.length; 843 int i = 0; 844 int period = m; 845 m--; 846 while (true) { 847 for (int k = 1; k <= period; k++) { 848 if (i >= a.length) { 849 return; 850 } 851 a[i++] = incCount++; 852 } 853 period += m; 854 855 for (int k = 1; k <= period; k++) { 856 if (i >= a.length) { 857 return; 858 } 859 a[i++] = decCount--; 860 } 861 period += m; 862 } 863 } 864 }, 865 REPEATED { 866 void build(int[] a, int m) { 867 for (int i = 0; i < a.length; i++) { 868 a[i] = i % m; 869 } 870 } 871 }, 872 DUPLICATED { 873 void build(int[] a, int m) { 874 for (int i = 0; i < a.length; i++) { 875 a[i] = ourRandom.nextInt(m); 876 } 877 } 878 }, 879 ORGAN_PIPES { 880 void build(int[] a, int m) { 881 int middle = a.length / (m + 1); 882 883 for (int i = 0; i < middle; i++) { 884 a[i] = i; 885 } 886 for (int i = middle; i < a.length; i++) { 887 a[i] = a.length - i - 1; 888 } 889 } 890 }, 891 STAGGER { 892 void build(int[] a, int m) { 893 for (int i = 0; i < a.length; i++) { 894 a[i] = (i * m + i) % a.length; 895 } 896 } 897 }, 898 PLATEAU { 899 void build(int[] a, int m) { 900 for (int i = 0; i < a.length; i++) { 901 a[i] = Math.min(i, m); 902 } 903 } 904 }, 905 SHUFFLE { 906 void build(int[] a, int m) { 907 for (int i = 0; i < a.length; i++) { 908 a[i] = ourRandom.nextBoolean() ? (ourFirst += 2) : (ourSecond += 2); 909 } 910 } 911 }; 912 913 abstract void build(int[] a, int m); 914 915 @Override public String toString() { 916 String name = name(); 917 918 for (int i = name.length(); i < 12; i++) { 919 name += " "; 920 } 921 return name; 922 } 923 } 924 925 private static void compare(Object test, Object golden) { 926 if (test instanceof int[]) { 927 compare((int[]) test, (int[]) golden); 928 } else if (test instanceof long[]) { 929 compare((long[]) test, (long[]) golden); 930 } else if (test instanceof short[]) { 931 compare((short[]) test, (short[]) golden); 932 } else if (test instanceof byte[]) { 933 compare((byte[]) test, (byte[]) golden); 934 } else if (test instanceof char[]) { 935 compare((char[]) test, (char[]) golden); 936 } else if (test instanceof float[]) { 937 compare((float[]) test, (float[]) golden); 938 } else if (test instanceof double[]) { 939 compare((double[]) test, (double[]) golden); 940 } else if (test instanceof Integer[]) { 941 compare((Integer[]) test, (Integer[]) golden); 942 } else { 943 failed("Unknow type of array: " + test + " of class " + 944 test.getClass().getName()); 945 } 946 } 947 948 private static void checkWithCheckSum(Object test, Object golden) { 949 checkSorted(test); 950 checkCheckSum(test, golden); 951 } 952 953 private static void failed(String message) { 954 err.format("\n*** TEST FAILED - %s\n\n%s\n\n", ourDescription, message); 955 throw new RuntimeException("Test failed - see log file for details"); 956 } 957 958 private static void failed(int index, String value1, String value2) { 959 failed("Array is not sorted at " + index + "-th position: " + 960 value1 + " and " + value2); 961 } 962 963 private static void checkSorted(Object object) { 964 if (object instanceof int[]) { 965 checkSorted((int[]) object); 966 } else if (object instanceof long[]) { 967 checkSorted((long[]) object); 968 } else if (object instanceof short[]) { 969 checkSorted((short[]) object); 970 } else if (object instanceof byte[]) { 971 checkSorted((byte[]) object); 972 } else if (object instanceof char[]) { 973 checkSorted((char[]) object); 974 } else if (object instanceof float[]) { 975 checkSorted((float[]) object); 976 } else if (object instanceof double[]) { 977 checkSorted((double[]) object); 978 } else if (object instanceof Integer[]) { 979 checkSorted((Integer[]) object); 980 } else { 981 failed("Unknow type of array: " + object + " of class " + 982 object.getClass().getName()); 983 } 984 } 985 986 private static void compare(Integer[] a, Integer[] b) { 987 for (int i = 0; i < a.length; i++) { 988 if (a[i].intValue() != b[i].intValue()) { 989 failed(i, "" + a[i], "" + b[i]); 990 } 991 } 992 } 993 994 private static void compare(int[] a, int[] b) { 995 for (int i = 0; i < a.length; i++) { 996 if (a[i] != b[i]) { 997 failed(i, "" + a[i], "" + b[i]); 998 } 999 } 1000 } 1001 1002 private static void compare(long[] a, long[] b) { 1003 for (int i = 0; i < a.length; i++) { 1004 if (a[i] != b[i]) { 1005 failed(i, "" + a[i], "" + b[i]); 1006 } 1007 } 1008 } 1009 1010 private static void compare(short[] a, short[] b) { 1011 for (int i = 0; i < a.length; i++) { 1012 if (a[i] != b[i]) { 1013 failed(i, "" + a[i], "" + b[i]); 1014 } 1015 } 1016 } 1017 1018 private static void compare(byte[] a, byte[] b) { 1019 for (int i = 0; i < a.length; i++) { 1020 if (a[i] != b[i]) { 1021 failed(i, "" + a[i], "" + b[i]); 1022 } 1023 } 1024 } 1025 1026 private static void compare(char[] a, char[] b) { 1027 for (int i = 0; i < a.length; i++) { 1028 if (a[i] != b[i]) { 1029 failed(i, "" + a[i], "" + b[i]); 1030 } 1031 } 1032 } 1033 1034 private static void compare(float[] a, float[] b) { 1035 for (int i = 0; i < a.length; i++) { 1036 if (a[i] != b[i]) { 1037 failed(i, "" + a[i], "" + b[i]); 1038 } 1039 } 1040 } 1041 1042 private static void compare(double[] a, double[] b) { 1043 for (int i = 0; i < a.length; i++) { 1044 if (a[i] != b[i]) { 1045 failed(i, "" + a[i], "" + b[i]); 1046 } 1047 } 1048 } 1049 1050 private static void checkSorted(Integer[] a) { 1051 for (int i = 0; i < a.length - 1; i++) { 1052 if (a[i].intValue() > a[i + 1].intValue()) { 1053 failed(i, "" + a[i], "" + a[i + 1]); 1054 } 1055 } 1056 } 1057 1058 private static void checkSorted(int[] a) { 1059 for (int i = 0; i < a.length - 1; i++) { 1060 if (a[i] > a[i + 1]) { 1061 failed(i, "" + a[i], "" + a[i + 1]); 1062 } 1063 } 1064 } 1065 1066 private static void checkSorted(long[] a) { 1067 for (int i = 0; i < a.length - 1; i++) { 1068 if (a[i] > a[i + 1]) { 1069 failed(i, "" + a[i], "" + a[i + 1]); 1070 } 1071 } 1072 } 1073 1074 private static void checkSorted(short[] a) { 1075 for (int i = 0; i < a.length - 1; i++) { 1076 if (a[i] > a[i + 1]) { 1077 failed(i, "" + a[i], "" + a[i + 1]); 1078 } 1079 } 1080 } 1081 1082 private static void checkSorted(byte[] a) { 1083 for (int i = 0; i < a.length - 1; i++) { 1084 if (a[i] > a[i + 1]) { 1085 failed(i, "" + a[i], "" + a[i + 1]); 1086 } 1087 } 1088 } 1089 1090 private static void checkSorted(char[] a) { 1091 for (int i = 0; i < a.length - 1; i++) { 1092 if (a[i] > a[i + 1]) { 1093 failed(i, "" + a[i], "" + a[i + 1]); 1094 } 1095 } 1096 } 1097 1098 private static void checkSorted(float[] a) { 1099 for (int i = 0; i < a.length - 1; i++) { 1100 if (a[i] > a[i + 1]) { 1101 failed(i, "" + a[i], "" + a[i + 1]); 1102 } 1103 } 1104 } 1105 1106 private static void checkSorted(double[] a) { 1107 for (int i = 0; i < a.length - 1; i++) { 1108 if (a[i] > a[i + 1]) { 1109 failed(i, "" + a[i], "" + a[i + 1]); 1110 } 1111 } 1112 } 1113 1114 private static void checkCheckSum(Object test, Object golden) { 1115 if (checkSum(test) != checkSum(golden)) { 1116 failed("It seems that original and sorted arrays are not identical"); 1117 } 1118 } 1119 1120 private static int checkSum(Object object) { 1121 if (object instanceof int[]) { 1122 return checkSum((int[]) object); 1123 } else if (object instanceof long[]) { 1124 return checkSum((long[]) object); 1125 } else if (object instanceof short[]) { 1126 return checkSum((short[]) object); 1127 } else if (object instanceof byte[]) { 1128 return checkSum((byte[]) object); 1129 } else if (object instanceof char[]) { 1130 return checkSum((char[]) object); 1131 } else if (object instanceof float[]) { 1132 return checkSum((float[]) object); 1133 } else if (object instanceof double[]) { 1134 return checkSum((double[]) object); 1135 } else if (object instanceof Integer[]) { 1136 return checkSum((Integer[]) object); 1137 } else { 1138 failed("Unknow type of array: " + object + " of class " + 1139 object.getClass().getName()); 1140 return -1; 1141 } 1142 } 1143 1144 private static int checkSum(Integer[] a) { 1145 int checkXorSum = 0; 1146 1147 for (Integer e : a) { 1148 checkXorSum ^= e.intValue(); 1149 } 1150 return checkXorSum; 1151 } 1152 1153 private static int checkSum(int[] a) { 1154 int checkXorSum = 0; 1155 1156 for (int e : a) { 1157 checkXorSum ^= e; 1158 } 1159 return checkXorSum; 1160 } 1161 1162 private static int checkSum(long[] a) { 1163 long checkXorSum = 0; 1164 1165 for (long e : a) { 1166 checkXorSum ^= e; 1167 } 1168 return (int) checkXorSum; 1169 } 1170 1171 private static int checkSum(short[] a) { 1172 short checkXorSum = 0; 1173 1174 for (short e : a) { 1175 checkXorSum ^= e; 1176 } 1177 return (int) checkXorSum; 1178 } 1179 1180 private static int checkSum(byte[] a) { 1181 byte checkXorSum = 0; 1182 1183 for (byte e : a) { 1184 checkXorSum ^= e; 1185 } 1186 return (int) checkXorSum; 1187 } 1188 1189 private static int checkSum(char[] a) { 1190 char checkXorSum = 0; 1191 1192 for (char e : a) { 1193 checkXorSum ^= e; 1194 } 1195 return (int) checkXorSum; 1196 } 1197 1198 private static int checkSum(float[] a) { 1199 int checkXorSum = 0; 1200 1201 for (float e : a) { 1202 checkXorSum ^= (int) e; 1203 } 1204 return checkXorSum; 1205 } 1206 1207 private static int checkSum(double[] a) { 1208 int checkXorSum = 0; 1209 1210 for (double e : a) { 1211 checkXorSum ^= (int) e; 1212 } 1213 return checkXorSum; 1214 } 1215 1216 private static void sort(Object object) { 1217 if (object instanceof int[]) { 1218 Arrays.sort((int[]) object); 1219 } else if (object instanceof long[]) { 1220 Arrays.sort((long[]) object); 1221 } else if (object instanceof short[]) { 1222 Arrays.sort((short[]) object); 1223 } else if (object instanceof byte[]) { 1224 Arrays.sort((byte[]) object); 1225 } else if (object instanceof char[]) { 1226 Arrays.sort((char[]) object); 1227 } else if (object instanceof float[]) { 1228 Arrays.sort((float[]) object); 1229 } else if (object instanceof double[]) { 1230 Arrays.sort((double[]) object); 1231 } else if (object instanceof Integer[]) { 1232 Arrays.sort((Integer[]) object); 1233 } else { 1234 failed("Unknow type of array: " + object + " of class " + 1235 object.getClass().getName()); 1236 } 1237 } 1238 1239 private static void sortSubArray(Object object, int fromIndex, int toIndex) { 1240 if (object instanceof int[]) { 1241 Arrays.sort((int[]) object, fromIndex, toIndex); 1242 } else if (object instanceof long[]) { 1243 Arrays.sort((long[]) object, fromIndex, toIndex); 1244 } else if (object instanceof short[]) { 1245 Arrays.sort((short[]) object, fromIndex, toIndex); 1246 } else if (object instanceof byte[]) { 1247 Arrays.sort((byte[]) object, fromIndex, toIndex); 1248 } else if (object instanceof char[]) { 1249 Arrays.sort((char[]) object, fromIndex, toIndex); 1250 } else if (object instanceof float[]) { 1251 Arrays.sort((float[]) object, fromIndex, toIndex); 1252 } else if (object instanceof double[]) { 1253 Arrays.sort((double[]) object, fromIndex, toIndex); 1254 } else if (object instanceof Integer[]) { 1255 Arrays.sort((Integer[]) object, fromIndex, toIndex); 1256 } else { 1257 failed("Unknow type of array: " + object + " of class " + 1258 object.getClass().getName()); 1259 } 1260 } 1261 1262 private static void checkSubArray(Object object, int fromIndex, int toIndex, int m) { 1263 if (object instanceof int[]) { 1264 checkSubArray((int[]) object, fromIndex, toIndex, m); 1265 } else if (object instanceof long[]) { 1266 checkSubArray((long[]) object, fromIndex, toIndex, m); 1267 } else if (object instanceof short[]) { 1268 checkSubArray((short[]) object, fromIndex, toIndex, m); 1269 } else if (object instanceof byte[]) { 1270 checkSubArray((byte[]) object, fromIndex, toIndex, m); 1271 } else if (object instanceof char[]) { 1272 checkSubArray((char[]) object, fromIndex, toIndex, m); 1273 } else if (object instanceof float[]) { 1274 checkSubArray((float[]) object, fromIndex, toIndex, m); 1275 } else if (object instanceof double[]) { 1276 checkSubArray((double[]) object, fromIndex, toIndex, m); 1277 } else if (object instanceof Integer[]) { 1278 checkSubArray((Integer[]) object, fromIndex, toIndex, m); 1279 } else { 1280 failed("Unknow type of array: " + object + " of class " + 1281 object.getClass().getName()); 1282 } 1283 } 1284 1285 private static void checkSubArray(Integer[] a, int fromIndex, int toIndex, int m) { 1286 for (int i = 0; i < fromIndex; i++) { 1287 if (a[i].intValue() != 0xBABA) { 1288 failed("Range sort changes left element on position " + i + 1289 ": " + a[i] + ", must be " + 0xBABA); 1290 } 1291 } 1292 1293 for (int i = fromIndex; i < toIndex - 1; i++) { 1294 if (a[i].intValue() > a[i + 1].intValue()) { 1295 failed(i, "" + a[i], "" + a[i + 1]); 1296 } 1297 } 1298 1299 for (int i = toIndex; i < a.length; i++) { 1300 if (a[i].intValue() != 0xDEDA) { 1301 failed("Range sort changes right element on position " + i + 1302 ": " + a[i] + ", must be " + 0xDEDA); 1303 } 1304 } 1305 } 1306 1307 private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) { 1308 for (int i = 0; i < fromIndex; i++) { 1309 if (a[i] != 0xBABA) { 1310 failed("Range sort changes left element on position " + i + 1311 ": " + a[i] + ", must be " + 0xBABA); 1312 } 1313 } 1314 1315 for (int i = fromIndex; i < toIndex - 1; i++) { 1316 if (a[i] > a[i + 1]) { 1317 failed(i, "" + a[i], "" + a[i + 1]); 1318 } 1319 } 1320 1321 for (int i = toIndex; i < a.length; i++) { 1322 if (a[i] != 0xDEDA) { 1323 failed("Range sort changes right element on position " + i + 1324 ": " + a[i] + ", must be " + 0xDEDA); 1325 } 1326 } 1327 } 1328 1329 private static void checkSubArray(byte[] a, int fromIndex, int toIndex, int m) { 1330 for (int i = 0; i < fromIndex; i++) { 1331 if (a[i] != (byte) 0xBABA) { 1332 failed("Range sort changes left element on position " + i + 1333 ": " + a[i] + ", must be " + 0xBABA); 1334 } 1335 } 1336 1337 for (int i = fromIndex; i < toIndex - 1; i++) { 1338 if (a[i] > a[i + 1]) { 1339 failed(i, "" + a[i], "" + a[i + 1]); 1340 } 1341 } 1342 1343 for (int i = toIndex; i < a.length; i++) { 1344 if (a[i] != (byte) 0xDEDA) { 1345 failed("Range sort changes right element on position " + i + 1346 ": " + a[i] + ", must be " + 0xDEDA); 1347 } 1348 } 1349 } 1350 1351 private static void checkSubArray(long[] a, int fromIndex, int toIndex, int m) { 1352 for (int i = 0; i < fromIndex; i++) { 1353 if (a[i] != (long) 0xBABA) { 1354 failed("Range sort changes left element on position " + i + 1355 ": " + a[i] + ", must be " + 0xBABA); 1356 } 1357 } 1358 1359 for (int i = fromIndex; i < toIndex - 1; i++) { 1360 if (a[i] > a[i + 1]) { 1361 failed(i, "" + a[i], "" + a[i + 1]); 1362 } 1363 } 1364 1365 for (int i = toIndex; i < a.length; i++) { 1366 if (a[i] != (long) 0xDEDA) { 1367 failed("Range sort changes right element on position " + i + 1368 ": " + a[i] + ", must be " + 0xDEDA); 1369 } 1370 } 1371 } 1372 1373 private static void checkSubArray(char[] a, int fromIndex, int toIndex, int m) { 1374 for (int i = 0; i < fromIndex; i++) { 1375 if (a[i] != (char) 0xBABA) { 1376 failed("Range sort changes left element on position " + i + 1377 ": " + a[i] + ", must be " + 0xBABA); 1378 } 1379 } 1380 1381 for (int i = fromIndex; i < toIndex - 1; i++) { 1382 if (a[i] > a[i + 1]) { 1383 failed(i, "" + a[i], "" + a[i + 1]); 1384 } 1385 } 1386 1387 for (int i = toIndex; i < a.length; i++) { 1388 if (a[i] != (char) 0xDEDA) { 1389 failed("Range sort changes right element on position " + i + 1390 ": " + a[i] + ", must be " + 0xDEDA); 1391 } 1392 } 1393 } 1394 1395 private static void checkSubArray(short[] a, int fromIndex, int toIndex, int m) { 1396 for (int i = 0; i < fromIndex; i++) { 1397 if (a[i] != (short) 0xBABA) { 1398 failed("Range sort changes left element on position " + i + 1399 ": " + a[i] + ", must be " + 0xBABA); 1400 } 1401 } 1402 1403 for (int i = fromIndex; i < toIndex - 1; i++) { 1404 if (a[i] > a[i + 1]) { 1405 failed(i, "" + a[i], "" + a[i + 1]); 1406 } 1407 } 1408 1409 for (int i = toIndex; i < a.length; i++) { 1410 if (a[i] != (short) 0xDEDA) { 1411 failed("Range sort changes right element on position " + i + 1412 ": " + a[i] + ", must be " + 0xDEDA); 1413 } 1414 } 1415 } 1416 1417 private static void checkSubArray(float[] a, int fromIndex, int toIndex, int m) { 1418 for (int i = 0; i < fromIndex; i++) { 1419 if (a[i] != (float) 0xBABA) { 1420 failed("Range sort changes left element on position " + i + 1421 ": " + a[i] + ", must be " + 0xBABA); 1422 } 1423 } 1424 1425 for (int i = fromIndex; i < toIndex - 1; i++) { 1426 if (a[i] > a[i + 1]) { 1427 failed(i, "" + a[i], "" + a[i + 1]); 1428 } 1429 } 1430 1431 for (int i = toIndex; i < a.length; i++) { 1432 if (a[i] != (float) 0xDEDA) { 1433 failed("Range sort changes right element on position " + i + 1434 ": " + a[i] + ", must be " + 0xDEDA); 1435 } 1436 } 1437 } 1438 1439 private static void checkSubArray(double[] a, int fromIndex, int toIndex, int m) { 1440 for (int i = 0; i < fromIndex; i++) { 1441 if (a[i] != (double) 0xBABA) { 1442 failed("Range sort changes left element on position " + i + 1443 ": " + a[i] + ", must be " + 0xBABA); 1444 } 1445 } 1446 1447 for (int i = fromIndex; i < toIndex - 1; i++) { 1448 if (a[i] > a[i + 1]) { 1449 failed(i, "" + a[i], "" + a[i + 1]); 1450 } 1451 } 1452 1453 for (int i = toIndex; i < a.length; i++) { 1454 if (a[i] != (double) 0xDEDA) { 1455 failed("Range sort changes right element on position " + i + 1456 ": " + a[i] + ", must be " + 0xDEDA); 1457 } 1458 } 1459 } 1460 1461 private static void checkRange(Object object, int m) { 1462 if (object instanceof int[]) { 1463 checkRange((int[]) object, m); 1464 } else if (object instanceof long[]) { 1465 checkRange((long[]) object, m); 1466 } else if (object instanceof short[]) { 1467 checkRange((short[]) object, m); 1468 } else if (object instanceof byte[]) { 1469 checkRange((byte[]) object, m); 1470 } else if (object instanceof char[]) { 1471 checkRange((char[]) object, m); 1472 } else if (object instanceof float[]) { 1473 checkRange((float[]) object, m); 1474 } else if (object instanceof double[]) { 1475 checkRange((double[]) object, m); 1476 } else if (object instanceof Integer[]) { 1477 checkRange((Integer[]) object, m); 1478 } else { 1479 failed("Unknow type of array: " + object + " of class " + 1480 object.getClass().getName()); 1481 } 1482 } 1483 1484 private static void checkRange(Integer[] a, int m) { 1485 try { 1486 Arrays.sort(a, m + 1, m); 1487 1488 failed("Sort does not throw IllegalArgumentException " + 1489 " as expected: fromIndex = " + (m + 1) + 1490 " toIndex = " + m); 1491 } 1492 catch (IllegalArgumentException iae) { 1493 try { 1494 Arrays.sort(a, -m, a.length); 1495 1496 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1497 " as expected: fromIndex = " + (-m)); 1498 } 1499 catch (ArrayIndexOutOfBoundsException aoe) { 1500 try { 1501 Arrays.sort(a, 0, a.length + m); 1502 1503 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1504 " as expected: toIndex = " + (a.length + m)); 1505 } 1506 catch (ArrayIndexOutOfBoundsException aie) { 1507 return; 1508 } 1509 } 1510 } 1511 } 1512 1513 private static void checkRange(int[] a, int m) { 1514 try { 1515 Arrays.sort(a, m + 1, m); 1516 1517 failed("Sort does not throw IllegalArgumentException " + 1518 " as expected: fromIndex = " + (m + 1) + 1519 " toIndex = " + m); 1520 } 1521 catch (IllegalArgumentException iae) { 1522 try { 1523 Arrays.sort(a, -m, a.length); 1524 1525 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1526 " as expected: fromIndex = " + (-m)); 1527 } 1528 catch (ArrayIndexOutOfBoundsException aoe) { 1529 try { 1530 Arrays.sort(a, 0, a.length + m); 1531 1532 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1533 " as expected: toIndex = " + (a.length + m)); 1534 } 1535 catch (ArrayIndexOutOfBoundsException aie) { 1536 return; 1537 } 1538 } 1539 } 1540 } 1541 1542 private static void checkRange(long[] a, int m) { 1543 try { 1544 Arrays.sort(a, m + 1, m); 1545 1546 failed("Sort does not throw IllegalArgumentException " + 1547 " as expected: fromIndex = " + (m + 1) + 1548 " toIndex = " + m); 1549 } 1550 catch (IllegalArgumentException iae) { 1551 try { 1552 Arrays.sort(a, -m, a.length); 1553 1554 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1555 " as expected: fromIndex = " + (-m)); 1556 } 1557 catch (ArrayIndexOutOfBoundsException aoe) { 1558 try { 1559 Arrays.sort(a, 0, a.length + m); 1560 1561 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1562 " as expected: toIndex = " + (a.length + m)); 1563 } 1564 catch (ArrayIndexOutOfBoundsException aie) { 1565 return; 1566 } 1567 } 1568 } 1569 } 1570 1571 private static void checkRange(byte[] a, int m) { 1572 try { 1573 Arrays.sort(a, m + 1, m); 1574 1575 failed("Sort does not throw IllegalArgumentException " + 1576 " as expected: fromIndex = " + (m + 1) + 1577 " toIndex = " + m); 1578 } 1579 catch (IllegalArgumentException iae) { 1580 try { 1581 Arrays.sort(a, -m, a.length); 1582 1583 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1584 " as expected: fromIndex = " + (-m)); 1585 } 1586 catch (ArrayIndexOutOfBoundsException aoe) { 1587 try { 1588 Arrays.sort(a, 0, a.length + m); 1589 1590 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1591 " as expected: toIndex = " + (a.length + m)); 1592 } 1593 catch (ArrayIndexOutOfBoundsException aie) { 1594 return; 1595 } 1596 } 1597 } 1598 } 1599 1600 private static void checkRange(short[] a, int m) { 1601 try { 1602 Arrays.sort(a, m + 1, m); 1603 1604 failed("Sort does not throw IllegalArgumentException " + 1605 " as expected: fromIndex = " + (m + 1) + 1606 " toIndex = " + m); 1607 } 1608 catch (IllegalArgumentException iae) { 1609 try { 1610 Arrays.sort(a, -m, a.length); 1611 1612 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1613 " as expected: fromIndex = " + (-m)); 1614 } 1615 catch (ArrayIndexOutOfBoundsException aoe) { 1616 try { 1617 Arrays.sort(a, 0, a.length + m); 1618 1619 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1620 " as expected: toIndex = " + (a.length + m)); 1621 } 1622 catch (ArrayIndexOutOfBoundsException aie) { 1623 return; 1624 } 1625 } 1626 } 1627 } 1628 1629 private static void checkRange(char[] a, int m) { 1630 try { 1631 Arrays.sort(a, m + 1, m); 1632 1633 failed("Sort does not throw IllegalArgumentException " + 1634 " as expected: fromIndex = " + (m + 1) + 1635 " toIndex = " + m); 1636 } 1637 catch (IllegalArgumentException iae) { 1638 try { 1639 Arrays.sort(a, -m, a.length); 1640 1641 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1642 " as expected: fromIndex = " + (-m)); 1643 } 1644 catch (ArrayIndexOutOfBoundsException aoe) { 1645 try { 1646 Arrays.sort(a, 0, a.length + m); 1647 1648 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1649 " as expected: toIndex = " + (a.length + m)); 1650 } 1651 catch (ArrayIndexOutOfBoundsException aie) { 1652 return; 1653 } 1654 } 1655 } 1656 } 1657 1658 private static void checkRange(float[] a, int m) { 1659 try { 1660 Arrays.sort(a, m + 1, m); 1661 1662 failed("Sort does not throw IllegalArgumentException " + 1663 " as expected: fromIndex = " + (m + 1) + 1664 " toIndex = " + m); 1665 } 1666 catch (IllegalArgumentException iae) { 1667 try { 1668 Arrays.sort(a, -m, a.length); 1669 1670 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1671 " as expected: fromIndex = " + (-m)); 1672 } 1673 catch (ArrayIndexOutOfBoundsException aoe) { 1674 try { 1675 Arrays.sort(a, 0, a.length + m); 1676 1677 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1678 " as expected: toIndex = " + (a.length + m)); 1679 } 1680 catch (ArrayIndexOutOfBoundsException aie) { 1681 return; 1682 } 1683 } 1684 } 1685 } 1686 1687 private static void checkRange(double[] a, int m) { 1688 try { 1689 Arrays.sort(a, m + 1, m); 1690 1691 failed("Sort does not throw IllegalArgumentException " + 1692 " as expected: fromIndex = " + (m + 1) + 1693 " toIndex = " + m); 1694 } 1695 catch (IllegalArgumentException iae) { 1696 try { 1697 Arrays.sort(a, -m, a.length); 1698 1699 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1700 " as expected: fromIndex = " + (-m)); 1701 } 1702 catch (ArrayIndexOutOfBoundsException aoe) { 1703 try { 1704 Arrays.sort(a, 0, a.length + m); 1705 1706 failed("Sort does not throw ArrayIndexOutOfBoundsException " + 1707 " as expected: toIndex = " + (a.length + m)); 1708 } 1709 catch (ArrayIndexOutOfBoundsException aie) { 1710 return; 1711 } 1712 } 1713 } 1714 } 1715 1716 private static void prepareRandom(int[] a) { 1717 for (int i = 0; i < a.length; i++) { 1718 a[i] = ourRandom.nextInt(); 1719 } 1720 } 1721 1722 private static void reset(long seed) { 1723 ourRandom = new Random(seed); 1724 ourFirst = 0; 1725 ourSecond = 0; 1726 } 1727 1728 private static void outArray(Object[] a) { 1729 for (int i = 0; i < a.length; i++) { 1730 out.print(a[i] + " "); 1731 } 1732 out.println(); 1733 } 1734 1735 private static void outArray(int[] a) { 1736 for (int i = 0; i < a.length; i++) { 1737 out.print(a[i] + " "); 1738 } 1739 out.println(); 1740 } 1741 1742 private static void outArray(float[] a) { 1743 for (int i = 0; i < a.length; i++) { 1744 out.print(a[i] + " "); 1745 } 1746 out.println(); 1747 } 1748 1749 private static void outArray(double[] a) { 1750 for (int i = 0; i < a.length; i++) { 1751 out.print(a[i] + " "); 1752 } 1753 out.println(); 1754 } 1755 1756 private static int ourFirst; 1757 private static int ourSecond; 1758 private static Random ourRandom; 1759 private static String ourDescription; 1760} 1761