1 /* 2 * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.util; 27 28 import java.lang.reflect.*; 29 30 /** 31 * This class contains various methods for manipulating arrays (such as 32 * sorting and searching). This class also contains a static factory 33 * that allows arrays to be viewed as lists. 34 * 35 * <p>The methods in this class all throw a {@code NullPointerException}, 36 * if the specified array reference is null, except where noted. 37 * 38 * <p>The documentation for the methods contained in this class includes 39 * briefs description of the <i>implementations</i>. Such descriptions should 40 * be regarded as <i>implementation notes</i>, rather than parts of the 41 * <i>specification</i>. Implementors should feel free to substitute other 42 * algorithms, so long as the specification itself is adhered to. (For 43 * example, the algorithm used by {@code sort(Object[])} does not have to be 44 * a MergeSort, but it does have to be <i>stable</i>.) 45 * 46 * <p>This class is a member of the 47 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 48 * Java Collections Framework</a>. 49 * 50 * @author Josh Bloch 51 * @author Neal Gafter 52 * @author John Rose 53 * @since 1.2 54 */ 55 public class Arrays { 56 57 // Suppresses default constructor, ensuring non-instantiability. 58 private Arrays() {} 59 60 /* 61 * Sorting of primitive type arrays. 62 */ 63 64 /** 65 * Sorts the specified array into ascending numerical order. 66 * 67 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 68 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 69 * offers O(n log(n)) performance on many data sets that cause other 70 * quicksorts to degrade to quadratic performance, and is typically 71 * faster than traditional (one-pivot) Quicksort implementations. 72 * 73 * @param a the array to be sorted 74 */ 75 public static void sort(int[] a) { 76 DualPivotQuicksort.sort(a); 77 } 78 79 /** 80 * Sorts the specified range of the array into ascending order. The range 81 * to be sorted extends from the index {@code fromIndex}, inclusive, to 82 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 83 * the range to be sorted is empty. 84 * 85 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 86 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 87 * offers O(n log(n)) performance on many data sets that cause other 88 * quicksorts to degrade to quadratic performance, and is typically 89 * faster than traditional (one-pivot) Quicksort implementations. 90 * 91 * @param a the array to be sorted 92 * @param fromIndex the index of the first element, inclusive, to be sorted 93 * @param toIndex the index of the last element, exclusive, to be sorted 94 * 95 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 96 * @throws ArrayIndexOutOfBoundsException 97 * if {@code fromIndex < 0} or {@code toIndex > a.length} 98 */ 99 public static void sort(int[] a, int fromIndex, int toIndex) { 100 rangeCheck(a.length, fromIndex, toIndex); 101 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); 102 } 103 104 /** 105 * Sorts the specified array into ascending numerical order. 106 * 107 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 108 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 109 * offers O(n log(n)) performance on many data sets that cause other 110 * quicksorts to degrade to quadratic performance, and is typically 111 * faster than traditional (one-pivot) Quicksort implementations. 112 * 113 * @param a the array to be sorted 114 */ 115 public static void sort(long[] a) { 116 DualPivotQuicksort.sort(a); 117 } 118 119 /** 120 * Sorts the specified range of the array into ascending order. The range 121 * to be sorted extends from the index {@code fromIndex}, inclusive, to 122 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 123 * the range to be sorted is empty. 124 * 125 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 126 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 127 * offers O(n log(n)) performance on many data sets that cause other 128 * quicksorts to degrade to quadratic performance, and is typically 129 * faster than traditional (one-pivot) Quicksort implementations. 130 * 131 * @param a the array to be sorted 132 * @param fromIndex the index of the first element, inclusive, to be sorted 133 * @param toIndex the index of the last element, exclusive, to be sorted 134 * 135 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 136 * @throws ArrayIndexOutOfBoundsException 137 * if {@code fromIndex < 0} or {@code toIndex > a.length} 138 */ 139 public static void sort(long[] a, int fromIndex, int toIndex) { 140 rangeCheck(a.length, fromIndex, toIndex); 141 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); 142 } 143 144 /** 145 * Sorts the specified array into ascending numerical order. 146 * 147 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 148 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 149 * offers O(n log(n)) performance on many data sets that cause other 150 * quicksorts to degrade to quadratic performance, and is typically 151 * faster than traditional (one-pivot) Quicksort implementations. 152 * 153 * @param a the array to be sorted 154 */ 155 public static void sort(short[] a) { 156 DualPivotQuicksort.sort(a); 157 } 158 159 /** 160 * Sorts the specified range of the array into ascending order. The range 161 * to be sorted extends from the index {@code fromIndex}, inclusive, to 162 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 163 * the range to be sorted is empty. 164 * 165 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 166 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 167 * offers O(n log(n)) performance on many data sets that cause other 168 * quicksorts to degrade to quadratic performance, and is typically 169 * faster than traditional (one-pivot) Quicksort implementations. 170 * 171 * @param a the array to be sorted 172 * @param fromIndex the index of the first element, inclusive, to be sorted 173 * @param toIndex the index of the last element, exclusive, to be sorted 174 * 175 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 176 * @throws ArrayIndexOutOfBoundsException 177 * if {@code fromIndex < 0} or {@code toIndex > a.length} 178 */ 179 public static void sort(short[] a, int fromIndex, int toIndex) { 180 rangeCheck(a.length, fromIndex, toIndex); 181 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); 182 } 183 184 /** 185 * Sorts the specified array into ascending numerical order. 186 * 187 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 188 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 189 * offers O(n log(n)) performance on many data sets that cause other 190 * quicksorts to degrade to quadratic performance, and is typically 191 * faster than traditional (one-pivot) Quicksort implementations. 192 * 193 * @param a the array to be sorted 194 */ 195 public static void sort(char[] a) { 196 DualPivotQuicksort.sort(a); 197 } 198 199 /** 200 * Sorts the specified range of the array into ascending order. The range 201 * to be sorted extends from the index {@code fromIndex}, inclusive, to 202 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 203 * the range to be sorted is empty. 204 * 205 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 206 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 207 * offers O(n log(n)) performance on many data sets that cause other 208 * quicksorts to degrade to quadratic performance, and is typically 209 * faster than traditional (one-pivot) Quicksort implementations. 210 * 211 * @param a the array to be sorted 212 * @param fromIndex the index of the first element, inclusive, to be sorted 213 * @param toIndex the index of the last element, exclusive, to be sorted 214 * 215 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 216 * @throws ArrayIndexOutOfBoundsException 217 * if {@code fromIndex < 0} or {@code toIndex > a.length} 218 */ 219 public static void sort(char[] a, int fromIndex, int toIndex) { 220 rangeCheck(a.length, fromIndex, toIndex); 221 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); 222 } 223 224 /** 225 * Sorts the specified array into ascending numerical order. 226 * 227 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 228 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 229 * offers O(n log(n)) performance on many data sets that cause other 230 * quicksorts to degrade to quadratic performance, and is typically 231 * faster than traditional (one-pivot) Quicksort implementations. 232 * 233 * @param a the array to be sorted 234 */ 235 public static void sort(byte[] a) { 236 DualPivotQuicksort.sort(a); 237 } 238 239 /** 240 * Sorts the specified range of the array into ascending order. The range 241 * to be sorted extends from the index {@code fromIndex}, inclusive, to 242 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 243 * the range to be sorted is empty. 244 * 245 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 246 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 247 * offers O(n log(n)) performance on many data sets that cause other 248 * quicksorts to degrade to quadratic performance, and is typically 249 * faster than traditional (one-pivot) Quicksort implementations. 250 * 251 * @param a the array to be sorted 252 * @param fromIndex the index of the first element, inclusive, to be sorted 253 * @param toIndex the index of the last element, exclusive, to be sorted 254 * 255 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 256 * @throws ArrayIndexOutOfBoundsException 257 * if {@code fromIndex < 0} or {@code toIndex > a.length} 258 */ 259 public static void sort(byte[] a, int fromIndex, int toIndex) { 260 rangeCheck(a.length, fromIndex, toIndex); 261 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); 262 } 263 264 /** 265 * Sorts the specified array into ascending numerical order. 266 * 267 * <p>The {@code <} relation does not provide a total order on all float 268 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN} 269 * value compares neither less than, greater than, nor equal to any value, 270 * even itself. This method uses the total order imposed by the method 271 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value 272 * {@code 0.0f} and {@code Float.NaN} is considered greater than any 273 * other value and all {@code Float.NaN} values are considered equal. 274 * 275 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 276 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 277 * offers O(n log(n)) performance on many data sets that cause other 278 * quicksorts to degrade to quadratic performance, and is typically 279 * faster than traditional (one-pivot) Quicksort implementations. 280 * 281 * @param a the array to be sorted 282 */ 283 public static void sort(float[] a) { 284 DualPivotQuicksort.sort(a); 285 } 286 287 /** 288 * Sorts the specified range of the array into ascending order. The range 289 * to be sorted extends from the index {@code fromIndex}, inclusive, to 290 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 291 * the range to be sorted is empty. 292 * 293 * <p>The {@code <} relation does not provide a total order on all float 294 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN} 295 * value compares neither less than, greater than, nor equal to any value, 296 * even itself. This method uses the total order imposed by the method 297 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value 298 * {@code 0.0f} and {@code Float.NaN} is considered greater than any 299 * other value and all {@code Float.NaN} values are considered equal. 300 * 301 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 302 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 303 * offers O(n log(n)) performance on many data sets that cause other 304 * quicksorts to degrade to quadratic performance, and is typically 305 * faster than traditional (one-pivot) Quicksort implementations. 306 * 307 * @param a the array to be sorted 308 * @param fromIndex the index of the first element, inclusive, to be sorted 309 * @param toIndex the index of the last element, exclusive, to be sorted 310 * 311 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 312 * @throws ArrayIndexOutOfBoundsException 313 * if {@code fromIndex < 0} or {@code toIndex > a.length} 314 */ 315 public static void sort(float[] a, int fromIndex, int toIndex) { 316 rangeCheck(a.length, fromIndex, toIndex); 317 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); 318 } 319 320 /** 321 * Sorts the specified array into ascending numerical order. 322 * 323 * <p>The {@code <} relation does not provide a total order on all double 324 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN} 325 * value compares neither less than, greater than, nor equal to any value, 326 * even itself. This method uses the total order imposed by the method 327 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value 328 * {@code 0.0d} and {@code Double.NaN} is considered greater than any 329 * other value and all {@code Double.NaN} values are considered equal. 330 * 331 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 332 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 333 * offers O(n log(n)) performance on many data sets that cause other 334 * quicksorts to degrade to quadratic performance, and is typically 335 * faster than traditional (one-pivot) Quicksort implementations. 336 * 337 * @param a the array to be sorted 338 */ 339 public static void sort(double[] a) { 340 DualPivotQuicksort.sort(a); 341 } 342 343 /** 344 * Sorts the specified range of the array into ascending order. The range 345 * to be sorted extends from the index {@code fromIndex}, inclusive, to 346 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 347 * the range to be sorted is empty. 348 * 349 * <p>The {@code <} relation does not provide a total order on all double 350 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN} 351 * value compares neither less than, greater than, nor equal to any value, 352 * even itself. This method uses the total order imposed by the method 353 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value 354 * {@code 0.0d} and {@code Double.NaN} is considered greater than any 355 * other value and all {@code Double.NaN} values are considered equal. 356 * 357 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 358 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 359 * offers O(n log(n)) performance on many data sets that cause other 360 * quicksorts to degrade to quadratic performance, and is typically 361 * faster than traditional (one-pivot) Quicksort implementations. 362 * 363 * @param a the array to be sorted 364 * @param fromIndex the index of the first element, inclusive, to be sorted 365 * @param toIndex the index of the last element, exclusive, to be sorted 366 * 367 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 368 * @throws ArrayIndexOutOfBoundsException 369 * if {@code fromIndex < 0} or {@code toIndex > a.length} 370 */ 371 public static void sort(double[] a, int fromIndex, int toIndex) { 372 rangeCheck(a.length, fromIndex, toIndex); 373 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); 374 } 375 376 /* 377 * Sorting of complex type arrays. 378 */ 379 380 /** 381 * Old merge sort implementation can be selected (for 382 * compatibility with broken comparators) using a system property. 383 * Cannot be a static boolean in the enclosing class due to 384 * circular dependencies. To be removed in a future release. 385 */ 386 static final class LegacyMergeSort { 387 private static final boolean userRequested = 388 java.security.AccessController.doPrivileged( 389 new sun.security.action.GetBooleanAction( 390 "java.util.Arrays.useLegacyMergeSort")).booleanValue(); 391 } 392 393 /* 394 * If this platform has an optimizing VM, check whether ComparableTimSort 395 * offers any performance benefit over TimSort in conjunction with a 396 * comparator that returns: 397 * {@code ((Comparable)first).compareTo(Second)}. 398 * If not, you are better off deleting ComparableTimSort to 399 * eliminate the code duplication. In other words, the commented 400 * out code below is the preferable implementation for sorting 401 * arrays of Comparables if it offers sufficient performance. 402 */ 403 404 // /** 405 // * A comparator that implements the natural ordering of a group of 406 // * mutually comparable elements. Using this comparator saves us 407 // * from duplicating most of the code in this file (one version for 408 // * Comparables, one for explicit Comparators). 409 // */ 410 // private static final Comparator<Object> NATURAL_ORDER = 411 // new Comparator<Object>() { 412 // @SuppressWarnings("unchecked") 413 // public int compare(Object first, Object second) { 414 // return ((Comparable<Object>)first).compareTo(second); 415 // } 416 // }; 417 // 418 // public static void sort(Object[] a) { 419 // sort(a, 0, a.length, NATURAL_ORDER); 420 // } 421 // 422 // public static void sort(Object[] a, int fromIndex, int toIndex) { 423 // sort(a, fromIndex, toIndex, NATURAL_ORDER); 424 // } 425 426 /** 427 * Sorts the specified array of objects into ascending order, according 428 * to the {@linkplain Comparable natural ordering} of its elements. 429 * All elements in the array must implement the {@link Comparable} 430 * interface. Furthermore, all elements in the array must be 431 * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must 432 * not throw a {@code ClassCastException} for any elements {@code e1} 433 * and {@code e2} in the array). 434 * 435 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 436 * not be reordered as a result of the sort. 437 * 438 * <p>Implementation note: This implementation is a stable, adaptive, 439 * iterative mergesort that requires far fewer than n lg(n) comparisons 440 * when the input array is partially sorted, while offering the 441 * performance of a traditional mergesort when the input array is 442 * randomly ordered. If the input array is nearly sorted, the 443 * implementation requires approximately n comparisons. Temporary 444 * storage requirements vary from a small constant for nearly sorted 445 * input arrays to n/2 object references for randomly ordered input 446 * arrays. 447 * 448 * <p>The implementation takes equal advantage of ascending and 449 * descending order in its input array, and can take advantage of 450 * ascending and descending order in different parts of the the same 451 * input array. It is well-suited to merging two or more sorted arrays: 452 * simply concatenate the arrays and sort the resulting array. 453 * 454 * <p>The implementation was adapted from Tim Peters's list sort for Python 455 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> 456 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic 457 * Sorting and Information Theoretic Complexity", in Proceedings of the 458 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, 459 * January 1993. 460 * 461 * @param a the array to be sorted 462 * @throws ClassCastException if the array contains elements that are not 463 * <i>mutually comparable</i> (for example, strings and integers) 464 * @throws IllegalArgumentException (optional) if the natural 465 * ordering of the array elements is found to violate the 466 * {@link Comparable} contract 467 */ 468 public static void sort(Object[] a) { 469 if (LegacyMergeSort.userRequested) 470 legacyMergeSort(a); 471 else 472 ComparableTimSort.sort(a); 473 } 474 475 /** To be removed in a future release. */ 476 private static void legacyMergeSort(Object[] a) { 477 Object[] aux = a.clone(); 478 mergeSort(aux, a, 0, a.length, 0); 479 } 480 481 /** 482 * Sorts the specified range of the specified array of objects into 483 * ascending order, according to the 484 * {@linkplain Comparable natural ordering} of its 485 * elements. The range to be sorted extends from index 486 * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive. 487 * (If {@code fromIndex==toIndex}, the range to be sorted is empty.) All 488 * elements in this range must implement the {@link Comparable} 489 * interface. Furthermore, all elements in this range must be <i>mutually 490 * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a 491 * {@code ClassCastException} for any elements {@code e1} and 492 * {@code e2} in the array). 493 * 494 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 495 * not be reordered as a result of the sort. 496 * 497 * <p>Implementation note: This implementation is a stable, adaptive, 498 * iterative mergesort that requires far fewer than n lg(n) comparisons 499 * when the input array is partially sorted, while offering the 500 * performance of a traditional mergesort when the input array is 501 * randomly ordered. If the input array is nearly sorted, the 502 * implementation requires approximately n comparisons. Temporary 503 * storage requirements vary from a small constant for nearly sorted 504 * input arrays to n/2 object references for randomly ordered input 505 * arrays. 506 * 507 * <p>The implementation takes equal advantage of ascending and 508 * descending order in its input array, and can take advantage of 509 * ascending and descending order in different parts of the the same 510 * input array. It is well-suited to merging two or more sorted arrays: 511 * simply concatenate the arrays and sort the resulting array. 512 * 513 * <p>The implementation was adapted from Tim Peters's list sort for Python 514 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> 515 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic 516 * Sorting and Information Theoretic Complexity", in Proceedings of the 517 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, 518 * January 1993. 519 * 520 * @param a the array to be sorted 521 * @param fromIndex the index of the first element (inclusive) to be 522 * sorted 523 * @param toIndex the index of the last element (exclusive) to be sorted 524 * @throws IllegalArgumentException if {@code fromIndex > toIndex} or 525 * (optional) if the natural ordering of the array elements is 526 * found to violate the {@link Comparable} contract 527 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or 528 * {@code toIndex > a.length} 529 * @throws ClassCastException if the array contains elements that are 530 * not <i>mutually comparable</i> (for example, strings and 531 * integers). 532 */ 533 public static void sort(Object[] a, int fromIndex, int toIndex) { 534 if (LegacyMergeSort.userRequested) 535 legacyMergeSort(a, fromIndex, toIndex); 536 else 537 ComparableTimSort.sort(a, fromIndex, toIndex); 538 } 539 540 /** To be removed in a future release. */ 541 private static void legacyMergeSort(Object[] a, 542 int fromIndex, int toIndex) { 543 rangeCheck(a.length, fromIndex, toIndex); 544 Object[] aux = copyOfRange(a, fromIndex, toIndex); 545 mergeSort(aux, a, fromIndex, toIndex, -fromIndex); 546 } 547 548 /** 549 * Tuning parameter: list size at or below which insertion sort will be 550 * used in preference to mergesort. 551 * To be removed in a future release. 552 */ 553 private static final int INSERTIONSORT_THRESHOLD = 7; 554 555 /** 556 * Src is the source array that starts at index 0 557 * Dest is the (possibly larger) array destination with a possible offset 558 * low is the index in dest to start sorting 559 * high is the end index in dest to end sorting 560 * off is the offset to generate corresponding low, high in src 561 * To be removed in a future release. 562 */ 563 @SuppressWarnings({ "unchecked", "rawtypes" }) 564 private static void mergeSort(Object[] src, 565 Object[] dest, 566 int low, 567 int high, 568 int off) { 569 int length = high - low; 570 571 // Insertion sort on smallest arrays 572 if (length < INSERTIONSORT_THRESHOLD) { 573 for (int i=low; i<high; i++) 574 for (int j=i; j>low && 575 ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--) 576 swap(dest, j, j-1); 577 return; 578 } 579 580 // Recursively sort halves of dest into src 581 int destLow = low; 582 int destHigh = high; 583 low += off; 584 high += off; 585 int mid = (low + high) >>> 1; 586 mergeSort(dest, src, low, mid, -off); 587 mergeSort(dest, src, mid, high, -off); 588 589 // If list is already sorted, just copy from src to dest. This is an 590 // optimization that results in faster sorts for nearly ordered lists. 591 if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) { 592 System.arraycopy(src, low, dest, destLow, length); 593 return; 594 } 595 596 // Merge sorted halves (now in src) into dest 597 for(int i = destLow, p = low, q = mid; i < destHigh; i++) { 598 if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0) 599 dest[i] = src[p++]; 600 else 601 dest[i] = src[q++]; 602 } 603 } 604 605 /** 606 * Swaps x[a] with x[b]. 607 */ 608 private static void swap(Object[] x, int a, int b) { 609 Object t = x[a]; 610 x[a] = x[b]; 611 x[b] = t; 612 } 613 614 /** 615 * Sorts the specified array of objects according to the order induced by 616 * the specified comparator. All elements in the array must be 617 * <i>mutually comparable</i> by the specified comparator (that is, 618 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} 619 * for any elements {@code e1} and {@code e2} in the array). 620 * 621 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 622 * not be reordered as a result of the sort. 623 * 624 * <p>Implementation note: This implementation is a stable, adaptive, 625 * iterative mergesort that requires far fewer than n lg(n) comparisons 626 * when the input array is partially sorted, while offering the 627 * performance of a traditional mergesort when the input array is 628 * randomly ordered. If the input array is nearly sorted, the 629 * implementation requires approximately n comparisons. Temporary 630 * storage requirements vary from a small constant for nearly sorted 631 * input arrays to n/2 object references for randomly ordered input 632 * arrays. 633 * 634 * <p>The implementation takes equal advantage of ascending and 635 * descending order in its input array, and can take advantage of 636 * ascending and descending order in different parts of the the same 637 * input array. It is well-suited to merging two or more sorted arrays: 638 * simply concatenate the arrays and sort the resulting array. 639 * 640 * <p>The implementation was adapted from Tim Peters's list sort for Python 641 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> 642 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic 643 * Sorting and Information Theoretic Complexity", in Proceedings of the 644 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, 645 * January 1993. 646 * 647 * @param a the array to be sorted 648 * @param c the comparator to determine the order of the array. A 649 * {@code null} value indicates that the elements' 650 * {@linkplain Comparable natural ordering} should be used. 651 * @throws ClassCastException if the array contains elements that are 652 * not <i>mutually comparable</i> using the specified comparator 653 * @throws IllegalArgumentException (optional) if the comparator is 654 * found to violate the {@link Comparator} contract 655 */ 656 public static <T> void sort(T[] a, Comparator<? super T> c) { 657 if (LegacyMergeSort.userRequested) 658 legacyMergeSort(a, c); 659 else 660 TimSort.sort(a, c); 661 } 662 663 /** To be removed in a future release. */ 664 private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) { 665 T[] aux = a.clone(); 666 if (c==null) 667 mergeSort(aux, a, 0, a.length, 0); 668 else 669 mergeSort(aux, a, 0, a.length, 0, c); 670 } 671 672 /** 673 * Sorts the specified range of the specified array of objects according 674 * to the order induced by the specified comparator. The range to be 675 * sorted extends from index {@code fromIndex}, inclusive, to index 676 * {@code toIndex}, exclusive. (If {@code fromIndex==toIndex}, the 677 * range to be sorted is empty.) All elements in the range must be 678 * <i>mutually comparable</i> by the specified comparator (that is, 679 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} 680 * for any elements {@code e1} and {@code e2} in the range). 681 * 682 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 683 * not be reordered as a result of the sort. 684 * 685 * <p>Implementation note: This implementation is a stable, adaptive, 686 * iterative mergesort that requires far fewer than n lg(n) comparisons 687 * when the input array is partially sorted, while offering the 688 * performance of a traditional mergesort when the input array is 689 * randomly ordered. If the input array is nearly sorted, the 690 * implementation requires approximately n comparisons. Temporary 691 * storage requirements vary from a small constant for nearly sorted 692 * input arrays to n/2 object references for randomly ordered input 693 * arrays. 694 * 695 * <p>The implementation takes equal advantage of ascending and 696 * descending order in its input array, and can take advantage of 697 * ascending and descending order in different parts of the the same 698 * input array. It is well-suited to merging two or more sorted arrays: 699 * simply concatenate the arrays and sort the resulting array. 700 * 701 * <p>The implementation was adapted from Tim Peters's list sort for Python 702 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> 703 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic 704 * Sorting and Information Theoretic Complexity", in Proceedings of the 705 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, 706 * January 1993. 707 * 708 * @param a the array to be sorted 709 * @param fromIndex the index of the first element (inclusive) to be 710 * sorted 711 * @param toIndex the index of the last element (exclusive) to be sorted 712 * @param c the comparator to determine the order of the array. A 713 * {@code null} value indicates that the elements' 714 * {@linkplain Comparable natural ordering} should be used. 715 * @throws ClassCastException if the array contains elements that are not 716 * <i>mutually comparable</i> using the specified comparator. 717 * @throws IllegalArgumentException if {@code fromIndex > toIndex} or 718 * (optional) if the comparator is found to violate the 719 * {@link Comparator} contract 720 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or 721 * {@code toIndex > a.length} 722 */ 723 public static <T> void sort(T[] a, int fromIndex, int toIndex, 724 Comparator<? super T> c) { 725 if (LegacyMergeSort.userRequested) 726 legacyMergeSort(a, fromIndex, toIndex, c); 727 else 728 TimSort.sort(a, fromIndex, toIndex, c); 729 } 730 731 /** To be removed in a future release. */ 732 private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex, 733 Comparator<? super T> c) { 734 rangeCheck(a.length, fromIndex, toIndex); 735 T[] aux = copyOfRange(a, fromIndex, toIndex); 736 if (c==null) 737 mergeSort(aux, a, fromIndex, toIndex, -fromIndex); 738 else 739 mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c); 740 } 741 742 /** 743 * Src is the source array that starts at index 0 744 * Dest is the (possibly larger) array destination with a possible offset 745 * low is the index in dest to start sorting 746 * high is the end index in dest to end sorting 747 * off is the offset into src corresponding to low in dest 748 * To be removed in a future release. 749 */ 750 @SuppressWarnings({ "rawtypes", "unchecked" }) 751 private static void mergeSort(Object[] src, 752 Object[] dest, 753 int low, int high, int off, 754 Comparator c) { 755 int length = high - low; 756 757 // Insertion sort on smallest arrays 758 if (length < INSERTIONSORT_THRESHOLD) { 759 for (int i=low; i<high; i++) 760 for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--) 761 swap(dest, j, j-1); 762 return; 763 } 764 765 // Recursively sort halves of dest into src 766 int destLow = low; 767 int destHigh = high; 768 low += off; 769 high += off; 770 int mid = (low + high) >>> 1; 771 mergeSort(dest, src, low, mid, -off, c); 772 mergeSort(dest, src, mid, high, -off, c); 773 774 // If list is already sorted, just copy from src to dest. This is an 775 // optimization that results in faster sorts for nearly ordered lists. 776 if (c.compare(src[mid-1], src[mid]) <= 0) { 777 System.arraycopy(src, low, dest, destLow, length); 778 return; 779 } 780 781 // Merge sorted halves (now in src) into dest 782 for(int i = destLow, p = low, q = mid; i < destHigh; i++) { 783 if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0) 784 dest[i] = src[p++]; 785 else 786 dest[i] = src[q++]; 787 } 788 } 789 790 /** 791 * Checks that {@code fromIndex} and {@code toIndex} are in 792 * the range and throws an appropriate exception, if they aren't. 793 */ 794 private static void rangeCheck(int length, int fromIndex, int toIndex) { 795 if (fromIndex > toIndex) { 796 throw new IllegalArgumentException( 797 "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); 798 } 799 if (fromIndex < 0) { 800 throw new ArrayIndexOutOfBoundsException(fromIndex); 801 } 802 if (toIndex > length) { 803 throw new ArrayIndexOutOfBoundsException(toIndex); 804 } 805 } 806 807 // Searching 808 809 /** 810 * Searches the specified array of longs for the specified value using the 811 * binary search algorithm. The array must be sorted (as 812 * by the {@link #sort(long[])} method) prior to making this call. If it 813 * is not sorted, the results are undefined. If the array contains 814 * multiple elements with the specified value, there is no guarantee which 815 * one will be found. 816 * 817 * @param a the array to be searched 818 * @param key the value to be searched for 819 * @return index of the search key, if it is contained in the array; 820 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 821 * <i>insertion point</i> is defined as the point at which the 822 * key would be inserted into the array: the index of the first 823 * element greater than the key, or <tt>a.length</tt> if all 824 * elements in the array are less than the specified key. Note 825 * that this guarantees that the return value will be >= 0 if 826 * and only if the key is found. 827 */ 828 public static int binarySearch(long[] a, long key) { 829 return binarySearch0(a, 0, a.length, key); 830 } 831 832 /** 833 * Searches a range of 834 * the specified array of longs for the specified value using the 835 * binary search algorithm. 836 * The range must be sorted (as 837 * by the {@link #sort(long[], int, int)} method) 838 * prior to making this call. If it 839 * is not sorted, the results are undefined. If the range contains 840 * multiple elements with the specified value, there is no guarantee which 841 * one will be found. 842 * 843 * @param a the array to be searched 844 * @param fromIndex the index of the first element (inclusive) to be 845 * searched 846 * @param toIndex the index of the last element (exclusive) to be searched 847 * @param key the value to be searched for 848 * @return index of the search key, if it is contained in the array 849 * within the specified range; 850 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 851 * <i>insertion point</i> is defined as the point at which the 852 * key would be inserted into the array: the index of the first 853 * element in the range greater than the key, 854 * or <tt>toIndex</tt> if all 855 * elements in the range are less than the specified key. Note 856 * that this guarantees that the return value will be >= 0 if 857 * and only if the key is found. 858 * @throws IllegalArgumentException 859 * if {@code fromIndex > toIndex} 860 * @throws ArrayIndexOutOfBoundsException 861 * if {@code fromIndex < 0 or toIndex > a.length} 862 * @since 1.6 863 */ 864 public static int binarySearch(long[] a, int fromIndex, int toIndex, 865 long key) { 866 rangeCheck(a.length, fromIndex, toIndex); 867 return binarySearch0(a, fromIndex, toIndex, key); 868 } 869 870 // Like public version, but without range checks. 871 private static int binarySearch0(long[] a, int fromIndex, int toIndex, 872 long key) { 873 int low = fromIndex; 874 int high = toIndex - 1; 875 876 while (low <= high) { 877 int mid = (low + high) >>> 1; 878 long midVal = a[mid]; 879 880 if (midVal < key) 881 low = mid + 1; 882 else if (midVal > key) 883 high = mid - 1; 884 else 885 return mid; // key found 886 } 887 return -(low + 1); // key not found. 888 } 889 890 /** 891 * Searches the specified array of ints for the specified value using the 892 * binary search algorithm. The array must be sorted (as 893 * by the {@link #sort(int[])} method) prior to making this call. If it 894 * is not sorted, the results are undefined. If the array contains 895 * multiple elements with the specified value, there is no guarantee which 896 * one will be found. 897 * 898 * @param a the array to be searched 899 * @param key the value to be searched for 900 * @return index of the search key, if it is contained in the array; 901 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 902 * <i>insertion point</i> is defined as the point at which the 903 * key would be inserted into the array: the index of the first 904 * element greater than the key, or <tt>a.length</tt> if all 905 * elements in the array are less than the specified key. Note 906 * that this guarantees that the return value will be >= 0 if 907 * and only if the key is found. 908 */ 909 public static int binarySearch(int[] a, int key) { 910 return binarySearch0(a, 0, a.length, key); 911 } 912 913 /** 914 * Searches a range of 915 * the specified array of ints for the specified value using the 916 * binary search algorithm. 917 * The range must be sorted (as 918 * by the {@link #sort(int[], int, int)} method) 919 * prior to making this call. If it 920 * is not sorted, the results are undefined. If the range contains 921 * multiple elements with the specified value, there is no guarantee which 922 * one will be found. 923 * 924 * @param a the array to be searched 925 * @param fromIndex the index of the first element (inclusive) to be 926 * searched 927 * @param toIndex the index of the last element (exclusive) to be searched 928 * @param key the value to be searched for 929 * @return index of the search key, if it is contained in the array 930 * within the specified range; 931 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 932 * <i>insertion point</i> is defined as the point at which the 933 * key would be inserted into the array: the index of the first 934 * element in the range greater than the key, 935 * or <tt>toIndex</tt> if all 936 * elements in the range are less than the specified key. Note 937 * that this guarantees that the return value will be >= 0 if 938 * and only if the key is found. 939 * @throws IllegalArgumentException 940 * if {@code fromIndex > toIndex} 941 * @throws ArrayIndexOutOfBoundsException 942 * if {@code fromIndex < 0 or toIndex > a.length} 943 * @since 1.6 944 */ 945 public static int binarySearch(int[] a, int fromIndex, int toIndex, 946 int key) { 947 rangeCheck(a.length, fromIndex, toIndex); 948 return binarySearch0(a, fromIndex, toIndex, key); 949 } 950 951 // Like public version, but without range checks. 952 private static int binarySearch0(int[] a, int fromIndex, int toIndex, 953 int key) { 954 int low = fromIndex; 955 int high = toIndex - 1; 956 957 while (low <= high) { 958 int mid = (low + high) >>> 1; 959 int midVal = a[mid]; 960 961 if (midVal < key) 962 low = mid + 1; 963 else if (midVal > key) 964 high = mid - 1; 965 else 966 return mid; // key found 967 } 968 return -(low + 1); // key not found. 969 } 970 971 /** 972 * Searches the specified array of shorts for the specified value using 973 * the binary search algorithm. The array must be sorted 974 * (as by the {@link #sort(short[])} method) prior to making this call. If 975 * it is not sorted, the results are undefined. If the array contains 976 * multiple elements with the specified value, there is no guarantee which 977 * one will be found. 978 * 979 * @param a the array to be searched 980 * @param key the value to be searched for 981 * @return index of the search key, if it is contained in the array; 982 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 983 * <i>insertion point</i> is defined as the point at which the 984 * key would be inserted into the array: the index of the first 985 * element greater than the key, or <tt>a.length</tt> if all 986 * elements in the array are less than the specified key. Note 987 * that this guarantees that the return value will be >= 0 if 988 * and only if the key is found. 989 */ 990 public static int binarySearch(short[] a, short key) { 991 return binarySearch0(a, 0, a.length, key); 992 } 993 994 /** 995 * Searches a range of 996 * the specified array of shorts for the specified value using 997 * the binary search algorithm. 998 * The range must be sorted 999 * (as by the {@link #sort(short[], int, int)} method) 1000 * prior to making this call. If 1001 * it is not sorted, the results are undefined. If the range contains 1002 * multiple elements with the specified value, there is no guarantee which 1003 * one will be found. 1004 * 1005 * @param a the array to be searched 1006 * @param fromIndex the index of the first element (inclusive) to be 1007 * searched 1008 * @param toIndex the index of the last element (exclusive) to be searched 1009 * @param key the value to be searched for 1010 * @return index of the search key, if it is contained in the array 1011 * within the specified range; 1012 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1013 * <i>insertion point</i> is defined as the point at which the 1014 * key would be inserted into the array: the index of the first 1015 * element in the range greater than the key, 1016 * or <tt>toIndex</tt> if all 1017 * elements in the range are less than the specified key. Note 1018 * that this guarantees that the return value will be >= 0 if 1019 * and only if the key is found. 1020 * @throws IllegalArgumentException 1021 * if {@code fromIndex > toIndex} 1022 * @throws ArrayIndexOutOfBoundsException 1023 * if {@code fromIndex < 0 or toIndex > a.length} 1024 * @since 1.6 1025 */ 1026 public static int binarySearch(short[] a, int fromIndex, int toIndex, 1027 short key) { 1028 rangeCheck(a.length, fromIndex, toIndex); 1029 return binarySearch0(a, fromIndex, toIndex, key); 1030 } 1031 1032 // Like public version, but without range checks. 1033 private static int binarySearch0(short[] a, int fromIndex, int toIndex, 1034 short key) { 1035 int low = fromIndex; 1036 int high = toIndex - 1; 1037 1038 while (low <= high) { 1039 int mid = (low + high) >>> 1; 1040 short midVal = a[mid]; 1041 1042 if (midVal < key) 1043 low = mid + 1; 1044 else if (midVal > key) 1045 high = mid - 1; 1046 else 1047 return mid; // key found 1048 } 1049 return -(low + 1); // key not found. 1050 } 1051 1052 /** 1053 * Searches the specified array of chars for the specified value using the 1054 * binary search algorithm. The array must be sorted (as 1055 * by the {@link #sort(char[])} method) prior to making this call. If it 1056 * is not sorted, the results are undefined. If the array contains 1057 * multiple elements with the specified value, there is no guarantee which 1058 * one will be found. 1059 * 1060 * @param a the array to be searched 1061 * @param key the value to be searched for 1062 * @return index of the search key, if it is contained in the array; 1063 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1064 * <i>insertion point</i> is defined as the point at which the 1065 * key would be inserted into the array: the index of the first 1066 * element greater than the key, or <tt>a.length</tt> if all 1067 * elements in the array are less than the specified key. Note 1068 * that this guarantees that the return value will be >= 0 if 1069 * and only if the key is found. 1070 */ 1071 public static int binarySearch(char[] a, char key) { 1072 return binarySearch0(a, 0, a.length, key); 1073 } 1074 1075 /** 1076 * Searches a range of 1077 * the specified array of chars for the specified value using the 1078 * binary search algorithm. 1079 * The range must be sorted (as 1080 * by the {@link #sort(char[], int, int)} method) 1081 * prior to making this call. If it 1082 * is not sorted, the results are undefined. If the range contains 1083 * multiple elements with the specified value, there is no guarantee which 1084 * one will be found. 1085 * 1086 * @param a the array to be searched 1087 * @param fromIndex the index of the first element (inclusive) to be 1088 * searched 1089 * @param toIndex the index of the last element (exclusive) to be searched 1090 * @param key the value to be searched for 1091 * @return index of the search key, if it is contained in the array 1092 * within the specified range; 1093 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1094 * <i>insertion point</i> is defined as the point at which the 1095 * key would be inserted into the array: the index of the first 1096 * element in the range greater than the key, 1097 * or <tt>toIndex</tt> if all 1098 * elements in the range are less than the specified key. Note 1099 * that this guarantees that the return value will be >= 0 if 1100 * and only if the key is found. 1101 * @throws IllegalArgumentException 1102 * if {@code fromIndex > toIndex} 1103 * @throws ArrayIndexOutOfBoundsException 1104 * if {@code fromIndex < 0 or toIndex > a.length} 1105 * @since 1.6 1106 */ 1107 public static int binarySearch(char[] a, int fromIndex, int toIndex, 1108 char key) { 1109 rangeCheck(a.length, fromIndex, toIndex); 1110 return binarySearch0(a, fromIndex, toIndex, key); 1111 } 1112 1113 // Like public version, but without range checks. 1114 private static int binarySearch0(char[] a, int fromIndex, int toIndex, 1115 char key) { 1116 int low = fromIndex; 1117 int high = toIndex - 1; 1118 1119 while (low <= high) { 1120 int mid = (low + high) >>> 1; 1121 char midVal = a[mid]; 1122 1123 if (midVal < key) 1124 low = mid + 1; 1125 else if (midVal > key) 1126 high = mid - 1; 1127 else 1128 return mid; // key found 1129 } 1130 return -(low + 1); // key not found. 1131 } 1132 1133 /** 1134 * Searches the specified array of bytes for the specified value using the 1135 * binary search algorithm. The array must be sorted (as 1136 * by the {@link #sort(byte[])} method) prior to making this call. If it 1137 * is not sorted, the results are undefined. If the array contains 1138 * multiple elements with the specified value, there is no guarantee which 1139 * one will be found. 1140 * 1141 * @param a the array to be searched 1142 * @param key the value to be searched for 1143 * @return index of the search key, if it is contained in the array; 1144 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1145 * <i>insertion point</i> is defined as the point at which the 1146 * key would be inserted into the array: the index of the first 1147 * element greater than the key, or <tt>a.length</tt> if all 1148 * elements in the array are less than the specified key. Note 1149 * that this guarantees that the return value will be >= 0 if 1150 * and only if the key is found. 1151 */ 1152 public static int binarySearch(byte[] a, byte key) { 1153 return binarySearch0(a, 0, a.length, key); 1154 } 1155 1156 /** 1157 * Searches a range of 1158 * the specified array of bytes for the specified value using the 1159 * binary search algorithm. 1160 * The range must be sorted (as 1161 * by the {@link #sort(byte[], int, int)} method) 1162 * prior to making this call. If it 1163 * is not sorted, the results are undefined. If the range contains 1164 * multiple elements with the specified value, there is no guarantee which 1165 * one will be found. 1166 * 1167 * @param a the array to be searched 1168 * @param fromIndex the index of the first element (inclusive) to be 1169 * searched 1170 * @param toIndex the index of the last element (exclusive) to be searched 1171 * @param key the value to be searched for 1172 * @return index of the search key, if it is contained in the array 1173 * within the specified range; 1174 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1175 * <i>insertion point</i> is defined as the point at which the 1176 * key would be inserted into the array: the index of the first 1177 * element in the range greater than the key, 1178 * or <tt>toIndex</tt> if all 1179 * elements in the range are less than the specified key. Note 1180 * that this guarantees that the return value will be >= 0 if 1181 * and only if the key is found. 1182 * @throws IllegalArgumentException 1183 * if {@code fromIndex > toIndex} 1184 * @throws ArrayIndexOutOfBoundsException 1185 * if {@code fromIndex < 0 or toIndex > a.length} 1186 * @since 1.6 1187 */ 1188 public static int binarySearch(byte[] a, int fromIndex, int toIndex, 1189 byte key) { 1190 rangeCheck(a.length, fromIndex, toIndex); 1191 return binarySearch0(a, fromIndex, toIndex, key); 1192 } 1193 1194 // Like public version, but without range checks. 1195 private static int binarySearch0(byte[] a, int fromIndex, int toIndex, 1196 byte key) { 1197 int low = fromIndex; 1198 int high = toIndex - 1; 1199 1200 while (low <= high) { 1201 int mid = (low + high) >>> 1; 1202 byte midVal = a[mid]; 1203 1204 if (midVal < key) 1205 low = mid + 1; 1206 else if (midVal > key) 1207 high = mid - 1; 1208 else 1209 return mid; // key found 1210 } 1211 return -(low + 1); // key not found. 1212 } 1213 1214 /** 1215 * Searches the specified array of doubles for the specified value using 1216 * the binary search algorithm. The array must be sorted 1217 * (as by the {@link #sort(double[])} method) prior to making this call. 1218 * If it is not sorted, the results are undefined. If the array contains 1219 * multiple elements with the specified value, there is no guarantee which 1220 * one will be found. This method considers all NaN values to be 1221 * equivalent and equal. 1222 * 1223 * @param a the array to be searched 1224 * @param key the value to be searched for 1225 * @return index of the search key, if it is contained in the array; 1226 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1227 * <i>insertion point</i> is defined as the point at which the 1228 * key would be inserted into the array: the index of the first 1229 * element greater than the key, or <tt>a.length</tt> if all 1230 * elements in the array are less than the specified key. Note 1231 * that this guarantees that the return value will be >= 0 if 1232 * and only if the key is found. 1233 */ 1234 public static int binarySearch(double[] a, double key) { 1235 return binarySearch0(a, 0, a.length, key); 1236 } 1237 1238 /** 1239 * Searches a range of 1240 * the specified array of doubles for the specified value using 1241 * the binary search algorithm. 1242 * The range must be sorted 1243 * (as by the {@link #sort(double[], int, int)} method) 1244 * prior to making this call. 1245 * If it is not sorted, the results are undefined. If the range contains 1246 * multiple elements with the specified value, there is no guarantee which 1247 * one will be found. This method considers all NaN values to be 1248 * equivalent and equal. 1249 * 1250 * @param a the array to be searched 1251 * @param fromIndex the index of the first element (inclusive) to be 1252 * searched 1253 * @param toIndex the index of the last element (exclusive) to be searched 1254 * @param key the value to be searched for 1255 * @return index of the search key, if it is contained in the array 1256 * within the specified range; 1257 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1258 * <i>insertion point</i> is defined as the point at which the 1259 * key would be inserted into the array: the index of the first 1260 * element in the range greater than the key, 1261 * or <tt>toIndex</tt> if all 1262 * elements in the range are less than the specified key. Note 1263 * that this guarantees that the return value will be >= 0 if 1264 * and only if the key is found. 1265 * @throws IllegalArgumentException 1266 * if {@code fromIndex > toIndex} 1267 * @throws ArrayIndexOutOfBoundsException 1268 * if {@code fromIndex < 0 or toIndex > a.length} 1269 * @since 1.6 1270 */ 1271 public static int binarySearch(double[] a, int fromIndex, int toIndex, 1272 double key) { 1273 rangeCheck(a.length, fromIndex, toIndex); 1274 return binarySearch0(a, fromIndex, toIndex, key); 1275 } 1276 1277 // Like public version, but without range checks. 1278 private static int binarySearch0(double[] a, int fromIndex, int toIndex, 1279 double key) { 1280 int low = fromIndex; 1281 int high = toIndex - 1; 1282 1283 while (low <= high) { 1284 int mid = (low + high) >>> 1; 1285 double midVal = a[mid]; 1286 1287 if (midVal < key) 1288 low = mid + 1; // Neither val is NaN, thisVal is smaller 1289 else if (midVal > key) 1290 high = mid - 1; // Neither val is NaN, thisVal is larger 1291 else { 1292 long midBits = Double.doubleToLongBits(midVal); 1293 long keyBits = Double.doubleToLongBits(key); 1294 if (midBits == keyBits) // Values are equal 1295 return mid; // Key found 1296 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN) 1297 low = mid + 1; 1298 else // (0.0, -0.0) or (NaN, !NaN) 1299 high = mid - 1; 1300 } 1301 } 1302 return -(low + 1); // key not found. 1303 } 1304 1305 /** 1306 * Searches the specified array of floats for the specified value using 1307 * the binary search algorithm. The array must be sorted 1308 * (as by the {@link #sort(float[])} method) prior to making this call. If 1309 * it is not sorted, the results are undefined. If the array contains 1310 * multiple elements with the specified value, there is no guarantee which 1311 * one will be found. This method considers all NaN values to be 1312 * equivalent and equal. 1313 * 1314 * @param a the array to be searched 1315 * @param key the value to be searched for 1316 * @return index of the search key, if it is contained in the array; 1317 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1318 * <i>insertion point</i> is defined as the point at which the 1319 * key would be inserted into the array: the index of the first 1320 * element greater than the key, or <tt>a.length</tt> if all 1321 * elements in the array are less than the specified key. Note 1322 * that this guarantees that the return value will be >= 0 if 1323 * and only if the key is found. 1324 */ 1325 public static int binarySearch(float[] a, float key) { 1326 return binarySearch0(a, 0, a.length, key); 1327 } 1328 1329 /** 1330 * Searches a range of 1331 * the specified array of floats for the specified value using 1332 * the binary search algorithm. 1333 * The range must be sorted 1334 * (as by the {@link #sort(float[], int, int)} method) 1335 * prior to making this call. If 1336 * it is not sorted, the results are undefined. If the range contains 1337 * multiple elements with the specified value, there is no guarantee which 1338 * one will be found. This method considers all NaN values to be 1339 * equivalent and equal. 1340 * 1341 * @param a the array to be searched 1342 * @param fromIndex the index of the first element (inclusive) to be 1343 * searched 1344 * @param toIndex the index of the last element (exclusive) to be searched 1345 * @param key the value to be searched for 1346 * @return index of the search key, if it is contained in the array 1347 * within the specified range; 1348 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1349 * <i>insertion point</i> is defined as the point at which the 1350 * key would be inserted into the array: the index of the first 1351 * element in the range greater than the key, 1352 * or <tt>toIndex</tt> if all 1353 * elements in the range are less than the specified key. Note 1354 * that this guarantees that the return value will be >= 0 if 1355 * and only if the key is found. 1356 * @throws IllegalArgumentException 1357 * if {@code fromIndex > toIndex} 1358 * @throws ArrayIndexOutOfBoundsException 1359 * if {@code fromIndex < 0 or toIndex > a.length} 1360 * @since 1.6 1361 */ 1362 public static int binarySearch(float[] a, int fromIndex, int toIndex, 1363 float key) { 1364 rangeCheck(a.length, fromIndex, toIndex); 1365 return binarySearch0(a, fromIndex, toIndex, key); 1366 } 1367 1368 // Like public version, but without range checks. 1369 private static int binarySearch0(float[] a, int fromIndex, int toIndex, 1370 float key) { 1371 int low = fromIndex; 1372 int high = toIndex - 1; 1373 1374 while (low <= high) { 1375 int mid = (low + high) >>> 1; 1376 float midVal = a[mid]; 1377 1378 if (midVal < key) 1379 low = mid + 1; // Neither val is NaN, thisVal is smaller 1380 else if (midVal > key) 1381 high = mid - 1; // Neither val is NaN, thisVal is larger 1382 else { 1383 int midBits = Float.floatToIntBits(midVal); 1384 int keyBits = Float.floatToIntBits(key); 1385 if (midBits == keyBits) // Values are equal 1386 return mid; // Key found 1387 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN) 1388 low = mid + 1; 1389 else // (0.0, -0.0) or (NaN, !NaN) 1390 high = mid - 1; 1391 } 1392 } 1393 return -(low + 1); // key not found. 1394 } 1395 1396 /** 1397 * Searches the specified array for the specified object using the binary 1398 * search algorithm. The array must be sorted into ascending order 1399 * according to the 1400 * {@linkplain Comparable natural ordering} 1401 * of its elements (as by the 1402 * {@link #sort(Object[])} method) prior to making this call. 1403 * If it is not sorted, the results are undefined. 1404 * (If the array contains elements that are not mutually comparable (for 1405 * example, strings and integers), it <i>cannot</i> be sorted according 1406 * to the natural ordering of its elements, hence results are undefined.) 1407 * If the array contains multiple 1408 * elements equal to the specified object, there is no guarantee which 1409 * one will be found. 1410 * 1411 * @param a the array to be searched 1412 * @param key the value to be searched for 1413 * @return index of the search key, if it is contained in the array; 1414 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1415 * <i>insertion point</i> is defined as the point at which the 1416 * key would be inserted into the array: the index of the first 1417 * element greater than the key, or <tt>a.length</tt> if all 1418 * elements in the array are less than the specified key. Note 1419 * that this guarantees that the return value will be >= 0 if 1420 * and only if the key is found. 1421 * @throws ClassCastException if the search key is not comparable to the 1422 * elements of the array. 1423 */ 1424 public static int binarySearch(Object[] a, Object key) { 1425 return binarySearch0(a, 0, a.length, key); 1426 } 1427 1428 /** 1429 * Searches a range of 1430 * the specified array for the specified object using the binary 1431 * search algorithm. 1432 * The range must be sorted into ascending order 1433 * according to the 1434 * {@linkplain Comparable natural ordering} 1435 * of its elements (as by the 1436 * {@link #sort(Object[], int, int)} method) prior to making this 1437 * call. If it is not sorted, the results are undefined. 1438 * (If the range contains elements that are not mutually comparable (for 1439 * example, strings and integers), it <i>cannot</i> be sorted according 1440 * to the natural ordering of its elements, hence results are undefined.) 1441 * If the range contains multiple 1442 * elements equal to the specified object, there is no guarantee which 1443 * one will be found. 1444 * 1445 * @param a the array to be searched 1446 * @param fromIndex the index of the first element (inclusive) to be 1447 * searched 1448 * @param toIndex the index of the last element (exclusive) to be searched 1449 * @param key the value to be searched for 1450 * @return index of the search key, if it is contained in the array 1451 * within the specified range; 1452 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1453 * <i>insertion point</i> is defined as the point at which the 1454 * key would be inserted into the array: the index of the first 1455 * element in the range greater than the key, 1456 * or <tt>toIndex</tt> if all 1457 * elements in the range are less than the specified key. Note 1458 * that this guarantees that the return value will be >= 0 if 1459 * and only if the key is found. 1460 * @throws ClassCastException if the search key is not comparable to the 1461 * elements of the array within the specified range. 1462 * @throws IllegalArgumentException 1463 * if {@code fromIndex > toIndex} 1464 * @throws ArrayIndexOutOfBoundsException 1465 * if {@code fromIndex < 0 or toIndex > a.length} 1466 * @since 1.6 1467 */ 1468 public static int binarySearch(Object[] a, int fromIndex, int toIndex, 1469 Object key) { 1470 rangeCheck(a.length, fromIndex, toIndex); 1471 return binarySearch0(a, fromIndex, toIndex, key); 1472 } 1473 1474 // Like public version, but without range checks. 1475 private static int binarySearch0(Object[] a, int fromIndex, int toIndex, 1476 Object key) { 1477 int low = fromIndex; 1478 int high = toIndex - 1; 1479 1480 while (low <= high) { 1481 int mid = (low + high) >>> 1; 1482 @SuppressWarnings("rawtypes") 1483 Comparable midVal = (Comparable)a[mid]; 1484 @SuppressWarnings("unchecked") 1485 int cmp = midVal.compareTo(key); 1486 1487 if (cmp < 0) 1488 low = mid + 1; 1489 else if (cmp > 0) 1490 high = mid - 1; 1491 else 1492 return mid; // key found 1493 } 1494 return -(low + 1); // key not found. 1495 } 1496 1497 /** 1498 * Searches the specified array for the specified object using the binary 1499 * search algorithm. The array must be sorted into ascending order 1500 * according to the specified comparator (as by the 1501 * {@link #sort(Object[], Comparator) sort(T[], Comparator)} 1502 * method) prior to making this call. If it is 1503 * not sorted, the results are undefined. 1504 * If the array contains multiple 1505 * elements equal to the specified object, there is no guarantee which one 1506 * will be found. 1507 * 1508 * @param a the array to be searched 1509 * @param key the value to be searched for 1510 * @param c the comparator by which the array is ordered. A 1511 * <tt>null</tt> value indicates that the elements' 1512 * {@linkplain Comparable natural ordering} should be used. 1513 * @return index of the search key, if it is contained in the array; 1514 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1515 * <i>insertion point</i> is defined as the point at which the 1516 * key would be inserted into the array: the index of the first 1517 * element greater than the key, or <tt>a.length</tt> if all 1518 * elements in the array are less than the specified key. Note 1519 * that this guarantees that the return value will be >= 0 if 1520 * and only if the key is found. 1521 * @throws ClassCastException if the array contains elements that are not 1522 * <i>mutually comparable</i> using the specified comparator, 1523 * or the search key is not comparable to the 1524 * elements of the array using this comparator. 1525 */ 1526 public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) { 1527 return binarySearch0(a, 0, a.length, key, c); 1528 } 1529 1530 /** 1531 * Searches a range of 1532 * the specified array for the specified object using the binary 1533 * search algorithm. 1534 * The range must be sorted into ascending order 1535 * according to the specified comparator (as by the 1536 * {@link #sort(Object[], int, int, Comparator) 1537 * sort(T[], int, int, Comparator)} 1538 * method) prior to making this call. 1539 * If it is not sorted, the results are undefined. 1540 * If the range contains multiple elements equal to the specified object, 1541 * there is no guarantee which one will be found. 1542 * 1543 * @param a the array to be searched 1544 * @param fromIndex the index of the first element (inclusive) to be 1545 * searched 1546 * @param toIndex the index of the last element (exclusive) to be searched 1547 * @param key the value to be searched for 1548 * @param c the comparator by which the array is ordered. A 1549 * <tt>null</tt> value indicates that the elements' 1550 * {@linkplain Comparable natural ordering} should be used. 1551 * @return index of the search key, if it is contained in the array 1552 * within the specified range; 1553 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1554 * <i>insertion point</i> is defined as the point at which the 1555 * key would be inserted into the array: the index of the first 1556 * element in the range greater than the key, 1557 * or <tt>toIndex</tt> if all 1558 * elements in the range are less than the specified key. Note 1559 * that this guarantees that the return value will be >= 0 if 1560 * and only if the key is found. 1561 * @throws ClassCastException if the range contains elements that are not 1562 * <i>mutually comparable</i> using the specified comparator, 1563 * or the search key is not comparable to the 1564 * elements in the range using this comparator. 1565 * @throws IllegalArgumentException 1566 * if {@code fromIndex > toIndex} 1567 * @throws ArrayIndexOutOfBoundsException 1568 * if {@code fromIndex < 0 or toIndex > a.length} 1569 * @since 1.6 1570 */ 1571 public static <T> int binarySearch(T[] a, int fromIndex, int toIndex, 1572 T key, Comparator<? super T> c) { 1573 rangeCheck(a.length, fromIndex, toIndex); 1574 return binarySearch0(a, fromIndex, toIndex, key, c); 1575 } 1576 1577 // Like public version, but without range checks. 1578 private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex, 1579 T key, Comparator<? super T> c) { 1580 if (c == null) { 1581 return binarySearch0(a, fromIndex, toIndex, key); 1582 } 1583 int low = fromIndex; 1584 int high = toIndex - 1; 1585 1586 while (low <= high) { 1587 int mid = (low + high) >>> 1; 1588 T midVal = a[mid]; 1589 int cmp = c.compare(midVal, key); 1590 if (cmp < 0) 1591 low = mid + 1; 1592 else if (cmp > 0) 1593 high = mid - 1; 1594 else 1595 return mid; // key found 1596 } 1597 return -(low + 1); // key not found. 1598 } 1599 1600 // Equality Testing 1601 1602 /** 1603 * Returns <tt>true</tt> if the two specified arrays of longs are 1604 * <i>equal</i> to one another. Two arrays are considered equal if both 1605 * arrays contain the same number of elements, and all corresponding pairs 1606 * of elements in the two arrays are equal. In other words, two arrays 1607 * are equal if they contain the same elements in the same order. Also, 1608 * two array references are considered equal if both are <tt>null</tt>.<p> 1609 * 1610 * @param a one array to be tested for equality 1611 * @param a2 the other array to be tested for equality 1612 * @return <tt>true</tt> if the two arrays are equal 1613 */ 1614 public static boolean equals(long[] a, long[] a2) { 1615 if (a==a2) 1616 return true; 1617 if (a==null || a2==null) 1618 return false; 1619 1620 int length = a.length; 1621 if (a2.length != length) 1622 return false; 1623 1624 for (int i=0; i<length; i++) 1625 if (a[i] != a2[i]) 1626 return false; 1627 1628 return true; 1629 } 1630 1631 /** 1632 * Returns <tt>true</tt> if the two specified arrays of ints are 1633 * <i>equal</i> to one another. Two arrays are considered equal if both 1634 * arrays contain the same number of elements, and all corresponding pairs 1635 * of elements in the two arrays are equal. In other words, two arrays 1636 * are equal if they contain the same elements in the same order. Also, 1637 * two array references are considered equal if both are <tt>null</tt>.<p> 1638 * 1639 * @param a one array to be tested for equality 1640 * @param a2 the other array to be tested for equality 1641 * @return <tt>true</tt> if the two arrays are equal 1642 */ 1643 public static boolean equals(int[] a, int[] a2) { 1644 if (a==a2) 1645 return true; 1646 if (a==null || a2==null) 1647 return false; 1648 1649 int length = a.length; 1650 if (a2.length != length) 1651 return false; 1652 1653 for (int i=0; i<length; i++) 1654 if (a[i] != a2[i]) 1655 return false; 1656 1657 return true; 1658 } 1659 1660 /** 1661 * Returns <tt>true</tt> if the two specified arrays of shorts are 1662 * <i>equal</i> to one another. Two arrays are considered equal if both 1663 * arrays contain the same number of elements, and all corresponding pairs 1664 * of elements in the two arrays are equal. In other words, two arrays 1665 * are equal if they contain the same elements in the same order. Also, 1666 * two array references are considered equal if both are <tt>null</tt>.<p> 1667 * 1668 * @param a one array to be tested for equality 1669 * @param a2 the other array to be tested for equality 1670 * @return <tt>true</tt> if the two arrays are equal 1671 */ 1672 public static boolean equals(short[] a, short a2[]) { 1673 if (a==a2) 1674 return true; 1675 if (a==null || a2==null) 1676 return false; 1677 1678 int length = a.length; 1679 if (a2.length != length) 1680 return false; 1681 1682 for (int i=0; i<length; i++) 1683 if (a[i] != a2[i]) 1684 return false; 1685 1686 return true; 1687 } 1688 1689 /** 1690 * Returns <tt>true</tt> if the two specified arrays of chars are 1691 * <i>equal</i> to one another. Two arrays are considered equal if both 1692 * arrays contain the same number of elements, and all corresponding pairs 1693 * of elements in the two arrays are equal. In other words, two arrays 1694 * are equal if they contain the same elements in the same order. Also, 1695 * two array references are considered equal if both are <tt>null</tt>.<p> 1696 * 1697 * @param a one array to be tested for equality 1698 * @param a2 the other array to be tested for equality 1699 * @return <tt>true</tt> if the two arrays are equal 1700 */ 1701 public static boolean equals(char[] a, char[] a2) { 1702 if (a==a2) 1703 return true; 1704 if (a==null || a2==null) 1705 return false; 1706 1707 int length = a.length; 1708 if (a2.length != length) 1709 return false; 1710 1711 for (int i=0; i<length; i++) 1712 if (a[i] != a2[i]) 1713 return false; 1714 1715 return true; 1716 } 1717 1718 /** 1719 * Returns <tt>true</tt> if the two specified arrays of bytes are 1720 * <i>equal</i> to one another. Two arrays are considered equal if both 1721 * arrays contain the same number of elements, and all corresponding pairs 1722 * of elements in the two arrays are equal. In other words, two arrays 1723 * are equal if they contain the same elements in the same order. Also, 1724 * two array references are considered equal if both are <tt>null</tt>.<p> 1725 * 1726 * @param a one array to be tested for equality 1727 * @param a2 the other array to be tested for equality 1728 * @return <tt>true</tt> if the two arrays are equal 1729 */ 1730 public static boolean equals(byte[] a, byte[] a2) { 1731 if (a==a2) 1732 return true; 1733 if (a==null || a2==null) 1734 return false; 1735 1736 int length = a.length; 1737 if (a2.length != length) 1738 return false; 1739 1740 for (int i=0; i<length; i++) 1741 if (a[i] != a2[i]) 1742 return false; 1743 1744 return true; 1745 } 1746 1747 /** 1748 * Returns <tt>true</tt> if the two specified arrays of booleans are 1749 * <i>equal</i> to one another. Two arrays are considered equal if both 1750 * arrays contain the same number of elements, and all corresponding pairs 1751 * of elements in the two arrays are equal. In other words, two arrays 1752 * are equal if they contain the same elements in the same order. Also, 1753 * two array references are considered equal if both are <tt>null</tt>.<p> 1754 * 1755 * @param a one array to be tested for equality 1756 * @param a2 the other array to be tested for equality 1757 * @return <tt>true</tt> if the two arrays are equal 1758 */ 1759 public static boolean equals(boolean[] a, boolean[] a2) { 1760 if (a==a2) 1761 return true; 1762 if (a==null || a2==null) 1763 return false; 1764 1765 int length = a.length; 1766 if (a2.length != length) 1767 return false; 1768 1769 for (int i=0; i<length; i++) 1770 if (a[i] != a2[i]) 1771 return false; 1772 1773 return true; 1774 } 1775 1776 /** 1777 * Returns <tt>true</tt> if the two specified arrays of doubles are 1778 * <i>equal</i> to one another. Two arrays are considered equal if both 1779 * arrays contain the same number of elements, and all corresponding pairs 1780 * of elements in the two arrays are equal. In other words, two arrays 1781 * are equal if they contain the same elements in the same order. Also, 1782 * two array references are considered equal if both are <tt>null</tt>.<p> 1783 * 1784 * Two doubles <tt>d1</tt> and <tt>d2</tt> are considered equal if: 1785 * <pre> <tt>new Double(d1).equals(new Double(d2))</tt></pre> 1786 * (Unlike the <tt>==</tt> operator, this method considers 1787 * <tt>NaN</tt> equals to itself, and 0.0d unequal to -0.0d.) 1788 * 1789 * @param a one array to be tested for equality 1790 * @param a2 the other array to be tested for equality 1791 * @return <tt>true</tt> if the two arrays are equal 1792 * @see Double#equals(Object) 1793 */ 1794 public static boolean equals(double[] a, double[] a2) { 1795 if (a==a2) 1796 return true; 1797 if (a==null || a2==null) 1798 return false; 1799 1800 int length = a.length; 1801 if (a2.length != length) 1802 return false; 1803 1804 for (int i=0; i<length; i++) 1805 if (Double.doubleToLongBits(a[i])!=Double.doubleToLongBits(a2[i])) 1806 return false; 1807 1808 return true; 1809 } 1810 1811 /** 1812 * Returns <tt>true</tt> if the two specified arrays of floats are 1813 * <i>equal</i> to one another. Two arrays are considered equal if both 1814 * arrays contain the same number of elements, and all corresponding pairs 1815 * of elements in the two arrays are equal. In other words, two arrays 1816 * are equal if they contain the same elements in the same order. Also, 1817 * two array references are considered equal if both are <tt>null</tt>.<p> 1818 * 1819 * Two floats <tt>f1</tt> and <tt>f2</tt> are considered equal if: 1820 * <pre> <tt>new Float(f1).equals(new Float(f2))</tt></pre> 1821 * (Unlike the <tt>==</tt> operator, this method considers 1822 * <tt>NaN</tt> equals to itself, and 0.0f unequal to -0.0f.) 1823 * 1824 * @param a one array to be tested for equality 1825 * @param a2 the other array to be tested for equality 1826 * @return <tt>true</tt> if the two arrays are equal 1827 * @see Float#equals(Object) 1828 */ 1829 public static boolean equals(float[] a, float[] a2) { 1830 if (a==a2) 1831 return true; 1832 if (a==null || a2==null) 1833 return false; 1834 1835 int length = a.length; 1836 if (a2.length != length) 1837 return false; 1838 1839 for (int i=0; i<length; i++) 1840 if (Float.floatToIntBits(a[i])!=Float.floatToIntBits(a2[i])) 1841 return false; 1842 1843 return true; 1844 } 1845 1846 /** 1847 * Returns <tt>true</tt> if the two specified arrays of Objects are 1848 * <i>equal</i> to one another. The two arrays are considered equal if 1849 * both arrays contain the same number of elements, and all corresponding 1850 * pairs of elements in the two arrays are equal. Two objects <tt>e1</tt> 1851 * and <tt>e2</tt> are considered <i>equal</i> if <tt>(e1==null ? e2==null 1852 * : e1.equals(e2))</tt>. In other words, the two arrays are equal if 1853 * they contain the same elements in the same order. Also, two array 1854 * references are considered equal if both are <tt>null</tt>.<p> 1855 * 1856 * @param a one array to be tested for equality 1857 * @param a2 the other array to be tested for equality 1858 * @return <tt>true</tt> if the two arrays are equal 1859 */ 1860 public static boolean equals(Object[] a, Object[] a2) { 1861 if (a==a2) 1862 return true; 1863 if (a==null || a2==null) 1864 return false; 1865 1866 int length = a.length; 1867 if (a2.length != length) 1868 return false; 1869 1870 for (int i=0; i<length; i++) { 1871 Object o1 = a[i]; 1872 Object o2 = a2[i]; 1873 if (!(o1==null ? o2==null : o1.equals(o2))) 1874 return false; 1875 } 1876 1877 return true; 1878 } 1879 1880 // Filling 1881 1882 /** 1883 * Assigns the specified long value to each element of the specified array 1884 * of longs. 1885 * 1886 * @param a the array to be filled 1887 * @param val the value to be stored in all elements of the array 1888 */ 1889 public static void fill(long[] a, long val) { 1890 for (int i = 0, len = a.length; i < len; i++) 1891 a[i] = val; 1892 } 1893 1894 /** 1895 * Assigns the specified long value to each element of the specified 1896 * range of the specified array of longs. The range to be filled 1897 * extends from index <tt>fromIndex</tt>, inclusive, to index 1898 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 1899 * range to be filled is empty.) 1900 * 1901 * @param a the array to be filled 1902 * @param fromIndex the index of the first element (inclusive) to be 1903 * filled with the specified value 1904 * @param toIndex the index of the last element (exclusive) to be 1905 * filled with the specified value 1906 * @param val the value to be stored in all elements of the array 1907 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 1908 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 1909 * <tt>toIndex > a.length</tt> 1910 */ 1911 public static void fill(long[] a, int fromIndex, int toIndex, long val) { 1912 rangeCheck(a.length, fromIndex, toIndex); 1913 for (int i = fromIndex; i < toIndex; i++) 1914 a[i] = val; 1915 } 1916 1917 /** 1918 * Assigns the specified int value to each element of the specified array 1919 * of ints. 1920 * 1921 * @param a the array to be filled 1922 * @param val the value to be stored in all elements of the array 1923 */ 1924 public static void fill(int[] a, int val) { 1925 for (int i = 0, len = a.length; i < len; i++) 1926 a[i] = val; 1927 } 1928 1929 /** 1930 * Assigns the specified int value to each element of the specified 1931 * range of the specified array of ints. The range to be filled 1932 * extends from index <tt>fromIndex</tt>, inclusive, to index 1933 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 1934 * range to be filled is empty.) 1935 * 1936 * @param a the array to be filled 1937 * @param fromIndex the index of the first element (inclusive) to be 1938 * filled with the specified value 1939 * @param toIndex the index of the last element (exclusive) to be 1940 * filled with the specified value 1941 * @param val the value to be stored in all elements of the array 1942 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 1943 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 1944 * <tt>toIndex > a.length</tt> 1945 */ 1946 public static void fill(int[] a, int fromIndex, int toIndex, int val) { 1947 rangeCheck(a.length, fromIndex, toIndex); 1948 for (int i = fromIndex; i < toIndex; i++) 1949 a[i] = val; 1950 } 1951 1952 /** 1953 * Assigns the specified short value to each element of the specified array 1954 * of shorts. 1955 * 1956 * @param a the array to be filled 1957 * @param val the value to be stored in all elements of the array 1958 */ 1959 public static void fill(short[] a, short val) { 1960 for (int i = 0, len = a.length; i < len; i++) 1961 a[i] = val; 1962 } 1963 1964 /** 1965 * Assigns the specified short value to each element of the specified 1966 * range of the specified array of shorts. The range to be filled 1967 * extends from index <tt>fromIndex</tt>, inclusive, to index 1968 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 1969 * range to be filled is empty.) 1970 * 1971 * @param a the array to be filled 1972 * @param fromIndex the index of the first element (inclusive) to be 1973 * filled with the specified value 1974 * @param toIndex the index of the last element (exclusive) to be 1975 * filled with the specified value 1976 * @param val the value to be stored in all elements of the array 1977 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 1978 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 1979 * <tt>toIndex > a.length</tt> 1980 */ 1981 public static void fill(short[] a, int fromIndex, int toIndex, short val) { 1982 rangeCheck(a.length, fromIndex, toIndex); 1983 for (int i = fromIndex; i < toIndex; i++) 1984 a[i] = val; 1985 } 1986 1987 /** 1988 * Assigns the specified char value to each element of the specified array 1989 * of chars. 1990 * 1991 * @param a the array to be filled 1992 * @param val the value to be stored in all elements of the array 1993 */ 1994 public static void fill(char[] a, char val) { 1995 for (int i = 0, len = a.length; i < len; i++) 1996 a[i] = val; 1997 } 1998 1999 /** 2000 * Assigns the specified char value to each element of the specified 2001 * range of the specified array of chars. The range to be filled 2002 * extends from index <tt>fromIndex</tt>, inclusive, to index 2003 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 2004 * range to be filled is empty.) 2005 * 2006 * @param a the array to be filled 2007 * @param fromIndex the index of the first element (inclusive) to be 2008 * filled with the specified value 2009 * @param toIndex the index of the last element (exclusive) to be 2010 * filled with the specified value 2011 * @param val the value to be stored in all elements of the array 2012 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 2013 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 2014 * <tt>toIndex > a.length</tt> 2015 */ 2016 public static void fill(char[] a, int fromIndex, int toIndex, char val) { 2017 rangeCheck(a.length, fromIndex, toIndex); 2018 for (int i = fromIndex; i < toIndex; i++) 2019 a[i] = val; 2020 } 2021 2022 /** 2023 * Assigns the specified byte value to each element of the specified array 2024 * of bytes. 2025 * 2026 * @param a the array to be filled 2027 * @param val the value to be stored in all elements of the array 2028 */ 2029 public static void fill(byte[] a, byte val) { 2030 for (int i = 0, len = a.length; i < len; i++) 2031 a[i] = val; 2032 } 2033 2034 /** 2035 * Assigns the specified byte value to each element of the specified 2036 * range of the specified array of bytes. The range to be filled 2037 * extends from index <tt>fromIndex</tt>, inclusive, to index 2038 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 2039 * range to be filled is empty.) 2040 * 2041 * @param a the array to be filled 2042 * @param fromIndex the index of the first element (inclusive) to be 2043 * filled with the specified value 2044 * @param toIndex the index of the last element (exclusive) to be 2045 * filled with the specified value 2046 * @param val the value to be stored in all elements of the array 2047 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 2048 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 2049 * <tt>toIndex > a.length</tt> 2050 */ 2051 public static void fill(byte[] a, int fromIndex, int toIndex, byte val) { 2052 rangeCheck(a.length, fromIndex, toIndex); 2053 for (int i = fromIndex; i < toIndex; i++) 2054 a[i] = val; 2055 } 2056 2057 /** 2058 * Assigns the specified boolean value to each element of the specified 2059 * array of booleans. 2060 * 2061 * @param a the array to be filled 2062 * @param val the value to be stored in all elements of the array 2063 */ 2064 public static void fill(boolean[] a, boolean val) { 2065 for (int i = 0, len = a.length; i < len; i++) 2066 a[i] = val; 2067 } 2068 2069 /** 2070 * Assigns the specified boolean value to each element of the specified 2071 * range of the specified array of booleans. The range to be filled 2072 * extends from index <tt>fromIndex</tt>, inclusive, to index 2073 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 2074 * range to be filled is empty.) 2075 * 2076 * @param a the array to be filled 2077 * @param fromIndex the index of the first element (inclusive) to be 2078 * filled with the specified value 2079 * @param toIndex the index of the last element (exclusive) to be 2080 * filled with the specified value 2081 * @param val the value to be stored in all elements of the array 2082 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 2083 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 2084 * <tt>toIndex > a.length</tt> 2085 */ 2086 public static void fill(boolean[] a, int fromIndex, int toIndex, 2087 boolean val) { 2088 rangeCheck(a.length, fromIndex, toIndex); 2089 for (int i = fromIndex; i < toIndex; i++) 2090 a[i] = val; 2091 } 2092 2093 /** 2094 * Assigns the specified double value to each element of the specified 2095 * array of doubles. 2096 * 2097 * @param a the array to be filled 2098 * @param val the value to be stored in all elements of the array 2099 */ 2100 public static void fill(double[] a, double val) { 2101 for (int i = 0, len = a.length; i < len; i++) 2102 a[i] = val; 2103 } 2104 2105 /** 2106 * Assigns the specified double value to each element of the specified 2107 * range of the specified array of doubles. The range to be filled 2108 * extends from index <tt>fromIndex</tt>, inclusive, to index 2109 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 2110 * range to be filled is empty.) 2111 * 2112 * @param a the array to be filled 2113 * @param fromIndex the index of the first element (inclusive) to be 2114 * filled with the specified value 2115 * @param toIndex the index of the last element (exclusive) to be 2116 * filled with the specified value 2117 * @param val the value to be stored in all elements of the array 2118 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 2119 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 2120 * <tt>toIndex > a.length</tt> 2121 */ 2122 public static void fill(double[] a, int fromIndex, int toIndex,double val){ 2123 rangeCheck(a.length, fromIndex, toIndex); 2124 for (int i = fromIndex; i < toIndex; i++) 2125 a[i] = val; 2126 } 2127 2128 /** 2129 * Assigns the specified float value to each element of the specified array 2130 * of floats. 2131 * 2132 * @param a the array to be filled 2133 * @param val the value to be stored in all elements of the array 2134 */ 2135 public static void fill(float[] a, float val) { 2136 for (int i = 0, len = a.length; i < len; i++) 2137 a[i] = val; 2138 } 2139 2140 /** 2141 * Assigns the specified float value to each element of the specified 2142 * range of the specified array of floats. The range to be filled 2143 * extends from index <tt>fromIndex</tt>, inclusive, to index 2144 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 2145 * range to be filled is empty.) 2146 * 2147 * @param a the array to be filled 2148 * @param fromIndex the index of the first element (inclusive) to be 2149 * filled with the specified value 2150 * @param toIndex the index of the last element (exclusive) to be 2151 * filled with the specified value 2152 * @param val the value to be stored in all elements of the array 2153 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 2154 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 2155 * <tt>toIndex > a.length</tt> 2156 */ 2157 public static void fill(float[] a, int fromIndex, int toIndex, float val) { 2158 rangeCheck(a.length, fromIndex, toIndex); 2159 for (int i = fromIndex; i < toIndex; i++) 2160 a[i] = val; 2161 } 2162 2163 /** 2164 * Assigns the specified Object reference to each element of the specified 2165 * array of Objects. 2166 * 2167 * @param a the array to be filled 2168 * @param val the value to be stored in all elements of the array 2169 * @throws ArrayStoreException if the specified value is not of a 2170 * runtime type that can be stored in the specified array 2171 */ 2172 public static void fill(Object[] a, Object val) { 2173 for (int i = 0, len = a.length; i < len; i++) 2174 a[i] = val; 2175 } 2176 2177 /** 2178 * Assigns the specified Object reference to each element of the specified 2179 * range of the specified array of Objects. The range to be filled 2180 * extends from index <tt>fromIndex</tt>, inclusive, to index 2181 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 2182 * range to be filled is empty.) 2183 * 2184 * @param a the array to be filled 2185 * @param fromIndex the index of the first element (inclusive) to be 2186 * filled with the specified value 2187 * @param toIndex the index of the last element (exclusive) to be 2188 * filled with the specified value 2189 * @param val the value to be stored in all elements of the array 2190 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 2191 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 2192 * <tt>toIndex > a.length</tt> 2193 * @throws ArrayStoreException if the specified value is not of a 2194 * runtime type that can be stored in the specified array 2195 */ 2196 public static void fill(Object[] a, int fromIndex, int toIndex, Object val) { 2197 rangeCheck(a.length, fromIndex, toIndex); 2198 for (int i = fromIndex; i < toIndex; i++) 2199 a[i] = val; 2200 } 2201 2202 // Cloning 2203 2204 /** 2205 * Copies the specified array, truncating or padding with nulls (if necessary) 2206 * so the copy has the specified length. For all indices that are 2207 * valid in both the original array and the copy, the two arrays will 2208 * contain identical values. For any indices that are valid in the 2209 * copy but not the original, the copy will contain <tt>null</tt>. 2210 * Such indices will exist if and only if the specified length 2211 * is greater than that of the original array. 2212 * The resulting array is of exactly the same class as the original array. 2213 * 2214 * @param original the array to be copied 2215 * @param newLength the length of the copy to be returned 2216 * @return a copy of the original array, truncated or padded with nulls 2217 * to obtain the specified length 2218 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 2219 * @throws NullPointerException if <tt>original</tt> is null 2220 * @since 1.6 2221 */ 2222 @SuppressWarnings("unchecked") 2223 public static <T> T[] copyOf(T[] original, int newLength) { 2224 return (T[]) copyOf(original, newLength, original.getClass()); 2225 } 2226 2227 /** 2228 * Copies the specified array, truncating or padding with nulls (if necessary) 2229 * so the copy has the specified length. For all indices that are 2230 * valid in both the original array and the copy, the two arrays will 2231 * contain identical values. For any indices that are valid in the 2232 * copy but not the original, the copy will contain <tt>null</tt>. 2233 * Such indices will exist if and only if the specified length 2234 * is greater than that of the original array. 2235 * The resulting array is of the class <tt>newType</tt>. 2236 * 2237 * @param original the array to be copied 2238 * @param newLength the length of the copy to be returned 2239 * @param newType the class of the copy to be returned 2240 * @return a copy of the original array, truncated or padded with nulls 2241 * to obtain the specified length 2242 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 2243 * @throws NullPointerException if <tt>original</tt> is null 2244 * @throws ArrayStoreException if an element copied from 2245 * <tt>original</tt> is not of a runtime type that can be stored in 2246 * an array of class <tt>newType</tt> 2247 * @since 1.6 2248 */ 2249 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { 2250 @SuppressWarnings("unchecked") 2251 T[] copy = ((Object)newType == (Object)Object[].class) 2252 ? (T[]) new Object[newLength] 2253 : (T[]) Array.newInstance(newType.getComponentType(), newLength); 2254 System.arraycopy(original, 0, copy, 0, 2255 Math.min(original.length, newLength)); 2256 return copy; 2257 } 2258 2259 /** 2260 * Copies the specified array, truncating or padding with zeros (if necessary) 2261 * so the copy has the specified length. For all indices that are 2262 * valid in both the original array and the copy, the two arrays will 2263 * contain identical values. For any indices that are valid in the 2264 * copy but not the original, the copy will contain <tt>(byte)0</tt>. 2265 * Such indices will exist if and only if the specified length 2266 * is greater than that of the original array. 2267 * 2268 * @param original the array to be copied 2269 * @param newLength the length of the copy to be returned 2270 * @return a copy of the original array, truncated or padded with zeros 2271 * to obtain the specified length 2272 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 2273 * @throws NullPointerException if <tt>original</tt> is null 2274 * @since 1.6 2275 */ 2276 public static byte[] copyOf(byte[] original, int newLength) { 2277 byte[] copy = new byte[newLength]; 2278 System.arraycopy(original, 0, copy, 0, 2279 Math.min(original.length, newLength)); 2280 return copy; 2281 } 2282 2283 /** 2284 * Copies the specified array, truncating or padding with zeros (if necessary) 2285 * so the copy has the specified length. For all indices that are 2286 * valid in both the original array and the copy, the two arrays will 2287 * contain identical values. For any indices that are valid in the 2288 * copy but not the original, the copy will contain <tt>(short)0</tt>. 2289 * Such indices will exist if and only if the specified length 2290 * is greater than that of the original array. 2291 * 2292 * @param original the array to be copied 2293 * @param newLength the length of the copy to be returned 2294 * @return a copy of the original array, truncated or padded with zeros 2295 * to obtain the specified length 2296 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 2297 * @throws NullPointerException if <tt>original</tt> is null 2298 * @since 1.6 2299 */ 2300 public static short[] copyOf(short[] original, int newLength) { 2301 short[] copy = new short[newLength]; 2302 System.arraycopy(original, 0, copy, 0, 2303 Math.min(original.length, newLength)); 2304 return copy; 2305 } 2306 2307 /** 2308 * Copies the specified array, truncating or padding with zeros (if necessary) 2309 * so the copy has the specified length. For all indices that are 2310 * valid in both the original array and the copy, the two arrays will 2311 * contain identical values. For any indices that are valid in the 2312 * copy but not the original, the copy will contain <tt>0</tt>. 2313 * Such indices will exist if and only if the specified length 2314 * is greater than that of the original array. 2315 * 2316 * @param original the array to be copied 2317 * @param newLength the length of the copy to be returned 2318 * @return a copy of the original array, truncated or padded with zeros 2319 * to obtain the specified length 2320 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 2321 * @throws NullPointerException if <tt>original</tt> is null 2322 * @since 1.6 2323 */ 2324 public static int[] copyOf(int[] original, int newLength) { 2325 int[] copy = new int[newLength]; 2326 System.arraycopy(original, 0, copy, 0, 2327 Math.min(original.length, newLength)); 2328 return copy; 2329 } 2330 2331 /** 2332 * Copies the specified array, truncating or padding with zeros (if necessary) 2333 * so the copy has the specified length. For all indices that are 2334 * valid in both the original array and the copy, the two arrays will 2335 * contain identical values. For any indices that are valid in the 2336 * copy but not the original, the copy will contain <tt>0L</tt>. 2337 * Such indices will exist if and only if the specified length 2338 * is greater than that of the original array. 2339 * 2340 * @param original the array to be copied 2341 * @param newLength the length of the copy to be returned 2342 * @return a copy of the original array, truncated or padded with zeros 2343 * to obtain the specified length 2344 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 2345 * @throws NullPointerException if <tt>original</tt> is null 2346 * @since 1.6 2347 */ 2348 public static long[] copyOf(long[] original, int newLength) { 2349 long[] copy = new long[newLength]; 2350 System.arraycopy(original, 0, copy, 0, 2351 Math.min(original.length, newLength)); 2352 return copy; 2353 } 2354 2355 /** 2356 * Copies the specified array, truncating or padding with null characters (if necessary) 2357 * so the copy has the specified length. For all indices that are valid 2358 * in both the original array and the copy, the two arrays will contain 2359 * identical values. For any indices that are valid in the copy but not 2360 * the original, the copy will contain <tt>'\\u000'</tt>. Such indices 2361 * will exist if and only if the specified length is greater than that of 2362 * the original array. 2363 * 2364 * @param original the array to be copied 2365 * @param newLength the length of the copy to be returned 2366 * @return a copy of the original array, truncated or padded with null characters 2367 * to obtain the specified length 2368 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 2369 * @throws NullPointerException if <tt>original</tt> is null 2370 * @since 1.6 2371 */ 2372 public static char[] copyOf(char[] original, int newLength) { 2373 char[] copy = new char[newLength]; 2374 System.arraycopy(original, 0, copy, 0, 2375 Math.min(original.length, newLength)); 2376 return copy; 2377 } 2378 2379 /** 2380 * Copies the specified array, truncating or padding with zeros (if necessary) 2381 * so the copy has the specified length. For all indices that are 2382 * valid in both the original array and the copy, the two arrays will 2383 * contain identical values. For any indices that are valid in the 2384 * copy but not the original, the copy will contain <tt>0f</tt>. 2385 * Such indices will exist if and only if the specified length 2386 * is greater than that of the original array. 2387 * 2388 * @param original the array to be copied 2389 * @param newLength the length of the copy to be returned 2390 * @return a copy of the original array, truncated or padded with zeros 2391 * to obtain the specified length 2392 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 2393 * @throws NullPointerException if <tt>original</tt> is null 2394 * @since 1.6 2395 */ 2396 public static float[] copyOf(float[] original, int newLength) { 2397 float[] copy = new float[newLength]; 2398 System.arraycopy(original, 0, copy, 0, 2399 Math.min(original.length, newLength)); 2400 return copy; 2401 } 2402 2403 /** 2404 * Copies the specified array, truncating or padding with zeros (if necessary) 2405 * so the copy has the specified length. For all indices that are 2406 * valid in both the original array and the copy, the two arrays will 2407 * contain identical values. For any indices that are valid in the 2408 * copy but not the original, the copy will contain <tt>0d</tt>. 2409 * Such indices will exist if and only if the specified length 2410 * is greater than that of the original array. 2411 * 2412 * @param original the array to be copied 2413 * @param newLength the length of the copy to be returned 2414 * @return a copy of the original array, truncated or padded with zeros 2415 * to obtain the specified length 2416 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 2417 * @throws NullPointerException if <tt>original</tt> is null 2418 * @since 1.6 2419 */ 2420 public static double[] copyOf(double[] original, int newLength) { 2421 double[] copy = new double[newLength]; 2422 System.arraycopy(original, 0, copy, 0, 2423 Math.min(original.length, newLength)); 2424 return copy; 2425 } 2426 2427 /** 2428 * Copies the specified array, truncating or padding with <tt>false</tt> (if necessary) 2429 * so the copy has the specified length. For all indices that are 2430 * valid in both the original array and the copy, the two arrays will 2431 * contain identical values. For any indices that are valid in the 2432 * copy but not the original, the copy will contain <tt>false</tt>. 2433 * Such indices will exist if and only if the specified length 2434 * is greater than that of the original array. 2435 * 2436 * @param original the array to be copied 2437 * @param newLength the length of the copy to be returned 2438 * @return a copy of the original array, truncated or padded with false elements 2439 * to obtain the specified length 2440 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 2441 * @throws NullPointerException if <tt>original</tt> is null 2442 * @since 1.6 2443 */ 2444 public static boolean[] copyOf(boolean[] original, int newLength) { 2445 boolean[] copy = new boolean[newLength]; 2446 System.arraycopy(original, 0, copy, 0, 2447 Math.min(original.length, newLength)); 2448 return copy; 2449 } 2450 2451 /** 2452 * Copies the specified range of the specified array into a new array. 2453 * The initial index of the range (<tt>from</tt>) must lie between zero 2454 * and <tt>original.length</tt>, inclusive. The value at 2455 * <tt>original[from]</tt> is placed into the initial element of the copy 2456 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 2457 * Values from subsequent elements in the original array are placed into 2458 * subsequent elements in the copy. The final index of the range 2459 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 2460 * may be greater than <tt>original.length</tt>, in which case 2461 * <tt>null</tt> is placed in all elements of the copy whose index is 2462 * greater than or equal to <tt>original.length - from</tt>. The length 2463 * of the returned array will be <tt>to - from</tt>. 2464 * <p> 2465 * The resulting array is of exactly the same class as the original array. 2466 * 2467 * @param original the array from which a range is to be copied 2468 * @param from the initial index of the range to be copied, inclusive 2469 * @param to the final index of the range to be copied, exclusive. 2470 * (This index may lie outside the array.) 2471 * @return a new array containing the specified range from the original array, 2472 * truncated or padded with nulls to obtain the required length 2473 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 2474 * or {@code from > original.length} 2475 * @throws IllegalArgumentException if <tt>from > to</tt> 2476 * @throws NullPointerException if <tt>original</tt> is null 2477 * @since 1.6 2478 */ 2479 @SuppressWarnings("unchecked") 2480 public static <T> T[] copyOfRange(T[] original, int from, int to) { 2481 return copyOfRange(original, from, to, (Class<? extends T[]>) original.getClass()); 2482 } 2483 2484 /** 2485 * Copies the specified range of the specified array into a new array. 2486 * The initial index of the range (<tt>from</tt>) must lie between zero 2487 * and <tt>original.length</tt>, inclusive. The value at 2488 * <tt>original[from]</tt> is placed into the initial element of the copy 2489 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 2490 * Values from subsequent elements in the original array are placed into 2491 * subsequent elements in the copy. The final index of the range 2492 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 2493 * may be greater than <tt>original.length</tt>, in which case 2494 * <tt>null</tt> is placed in all elements of the copy whose index is 2495 * greater than or equal to <tt>original.length - from</tt>. The length 2496 * of the returned array will be <tt>to - from</tt>. 2497 * The resulting array is of the class <tt>newType</tt>. 2498 * 2499 * @param original the array from which a range is to be copied 2500 * @param from the initial index of the range to be copied, inclusive 2501 * @param to the final index of the range to be copied, exclusive. 2502 * (This index may lie outside the array.) 2503 * @param newType the class of the copy to be returned 2504 * @return a new array containing the specified range from the original array, 2505 * truncated or padded with nulls to obtain the required length 2506 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 2507 * or {@code from > original.length} 2508 * @throws IllegalArgumentException if <tt>from > to</tt> 2509 * @throws NullPointerException if <tt>original</tt> is null 2510 * @throws ArrayStoreException if an element copied from 2511 * <tt>original</tt> is not of a runtime type that can be stored in 2512 * an array of class <tt>newType</tt>. 2513 * @since 1.6 2514 */ 2515 public static <T,U> T[] copyOfRange(U[] original, int from, int to, Class<? extends T[]> newType) { 2516 int newLength = to - from; 2517 if (newLength < 0) 2518 throw new IllegalArgumentException(from + " > " + to); 2519 @SuppressWarnings("unchecked") 2520 T[] copy = ((Object)newType == (Object)Object[].class) 2521 ? (T[]) new Object[newLength] 2522 : (T[]) Array.newInstance(newType.getComponentType(), newLength); 2523 System.arraycopy(original, from, copy, 0, 2524 Math.min(original.length - from, newLength)); 2525 return copy; 2526 } 2527 2528 /** 2529 * Copies the specified range of the specified array into a new array. 2530 * The initial index of the range (<tt>from</tt>) must lie between zero 2531 * and <tt>original.length</tt>, inclusive. The value at 2532 * <tt>original[from]</tt> is placed into the initial element of the copy 2533 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 2534 * Values from subsequent elements in the original array are placed into 2535 * subsequent elements in the copy. The final index of the range 2536 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 2537 * may be greater than <tt>original.length</tt>, in which case 2538 * <tt>(byte)0</tt> is placed in all elements of the copy whose index is 2539 * greater than or equal to <tt>original.length - from</tt>. The length 2540 * of the returned array will be <tt>to - from</tt>. 2541 * 2542 * @param original the array from which a range is to be copied 2543 * @param from the initial index of the range to be copied, inclusive 2544 * @param to the final index of the range to be copied, exclusive. 2545 * (This index may lie outside the array.) 2546 * @return a new array containing the specified range from the original array, 2547 * truncated or padded with zeros to obtain the required length 2548 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 2549 * or {@code from > original.length} 2550 * @throws IllegalArgumentException if <tt>from > to</tt> 2551 * @throws NullPointerException if <tt>original</tt> is null 2552 * @since 1.6 2553 */ 2554 public static byte[] copyOfRange(byte[] original, int from, int to) { 2555 int newLength = to - from; 2556 if (newLength < 0) 2557 throw new IllegalArgumentException(from + " > " + to); 2558 byte[] copy = new byte[newLength]; 2559 System.arraycopy(original, from, copy, 0, 2560 Math.min(original.length - from, newLength)); 2561 return copy; 2562 } 2563 2564 /** 2565 * Copies the specified range of the specified array into a new array. 2566 * The initial index of the range (<tt>from</tt>) must lie between zero 2567 * and <tt>original.length</tt>, inclusive. The value at 2568 * <tt>original[from]</tt> is placed into the initial element of the copy 2569 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 2570 * Values from subsequent elements in the original array are placed into 2571 * subsequent elements in the copy. The final index of the range 2572 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 2573 * may be greater than <tt>original.length</tt>, in which case 2574 * <tt>(short)0</tt> is placed in all elements of the copy whose index is 2575 * greater than or equal to <tt>original.length - from</tt>. The length 2576 * of the returned array will be <tt>to - from</tt>. 2577 * 2578 * @param original the array from which a range is to be copied 2579 * @param from the initial index of the range to be copied, inclusive 2580 * @param to the final index of the range to be copied, exclusive. 2581 * (This index may lie outside the array.) 2582 * @return a new array containing the specified range from the original array, 2583 * truncated or padded with zeros to obtain the required length 2584 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 2585 * or {@code from > original.length} 2586 * @throws IllegalArgumentException if <tt>from > to</tt> 2587 * @throws NullPointerException if <tt>original</tt> is null 2588 * @since 1.6 2589 */ 2590 public static short[] copyOfRange(short[] original, int from, int to) { 2591 int newLength = to - from; 2592 if (newLength < 0) 2593 throw new IllegalArgumentException(from + " > " + to); 2594 short[] copy = new short[newLength]; 2595 System.arraycopy(original, from, copy, 0, 2596 Math.min(original.length - from, newLength)); 2597 return copy; 2598 } 2599 2600 /** 2601 * Copies the specified range of the specified array into a new array. 2602 * The initial index of the range (<tt>from</tt>) must lie between zero 2603 * and <tt>original.length</tt>, inclusive. The value at 2604 * <tt>original[from]</tt> is placed into the initial element of the copy 2605 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 2606 * Values from subsequent elements in the original array are placed into 2607 * subsequent elements in the copy. The final index of the range 2608 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 2609 * may be greater than <tt>original.length</tt>, in which case 2610 * <tt>0</tt> is placed in all elements of the copy whose index is 2611 * greater than or equal to <tt>original.length - from</tt>. The length 2612 * of the returned array will be <tt>to - from</tt>. 2613 * 2614 * @param original the array from which a range is to be copied 2615 * @param from the initial index of the range to be copied, inclusive 2616 * @param to the final index of the range to be copied, exclusive. 2617 * (This index may lie outside the array.) 2618 * @return a new array containing the specified range from the original array, 2619 * truncated or padded with zeros to obtain the required length 2620 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 2621 * or {@code from > original.length} 2622 * @throws IllegalArgumentException if <tt>from > to</tt> 2623 * @throws NullPointerException if <tt>original</tt> is null 2624 * @since 1.6 2625 */ 2626 public static int[] copyOfRange(int[] original, int from, int to) { 2627 int newLength = to - from; 2628 if (newLength < 0) 2629 throw new IllegalArgumentException(from + " > " + to); 2630 int[] copy = new int[newLength]; 2631 System.arraycopy(original, from, copy, 0, 2632 Math.min(original.length - from, newLength)); 2633 return copy; 2634 } 2635 2636 /** 2637 * Copies the specified range of the specified array into a new array. 2638 * The initial index of the range (<tt>from</tt>) must lie between zero 2639 * and <tt>original.length</tt>, inclusive. The value at 2640 * <tt>original[from]</tt> is placed into the initial element of the copy 2641 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 2642 * Values from subsequent elements in the original array are placed into 2643 * subsequent elements in the copy. The final index of the range 2644 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 2645 * may be greater than <tt>original.length</tt>, in which case 2646 * <tt>0L</tt> is placed in all elements of the copy whose index is 2647 * greater than or equal to <tt>original.length - from</tt>. The length 2648 * of the returned array will be <tt>to - from</tt>. 2649 * 2650 * @param original the array from which a range is to be copied 2651 * @param from the initial index of the range to be copied, inclusive 2652 * @param to the final index of the range to be copied, exclusive. 2653 * (This index may lie outside the array.) 2654 * @return a new array containing the specified range from the original array, 2655 * truncated or padded with zeros to obtain the required length 2656 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 2657 * or {@code from > original.length} 2658 * @throws IllegalArgumentException if <tt>from > to</tt> 2659 * @throws NullPointerException if <tt>original</tt> is null 2660 * @since 1.6 2661 */ 2662 public static long[] copyOfRange(long[] original, int from, int to) { 2663 int newLength = to - from; 2664 if (newLength < 0) 2665 throw new IllegalArgumentException(from + " > " + to); 2666 long[] copy = new long[newLength]; 2667 System.arraycopy(original, from, copy, 0, 2668 Math.min(original.length - from, newLength)); 2669 return copy; 2670 } 2671 2672 /** 2673 * Copies the specified range of the specified array into a new array. 2674 * The initial index of the range (<tt>from</tt>) must lie between zero 2675 * and <tt>original.length</tt>, inclusive. The value at 2676 * <tt>original[from]</tt> is placed into the initial element of the copy 2677 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 2678 * Values from subsequent elements in the original array are placed into 2679 * subsequent elements in the copy. The final index of the range 2680 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 2681 * may be greater than <tt>original.length</tt>, in which case 2682 * <tt>'\\u000'</tt> is placed in all elements of the copy whose index is 2683 * greater than or equal to <tt>original.length - from</tt>. The length 2684 * of the returned array will be <tt>to - from</tt>. 2685 * 2686 * @param original the array from which a range is to be copied 2687 * @param from the initial index of the range to be copied, inclusive 2688 * @param to the final index of the range to be copied, exclusive. 2689 * (This index may lie outside the array.) 2690 * @return a new array containing the specified range from the original array, 2691 * truncated or padded with null characters to obtain the required length 2692 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 2693 * or {@code from > original.length} 2694 * @throws IllegalArgumentException if <tt>from > to</tt> 2695 * @throws NullPointerException if <tt>original</tt> is null 2696 * @since 1.6 2697 */ 2698 public static char[] copyOfRange(char[] original, int from, int to) { 2699 int newLength = to - from; 2700 if (newLength < 0) 2701 throw new IllegalArgumentException(from + " > " + to); 2702 char[] copy = new char[newLength]; 2703 System.arraycopy(original, from, copy, 0, 2704 Math.min(original.length - from, newLength)); 2705 return copy; 2706 } 2707 2708 /** 2709 * Copies the specified range of the specified array into a new array. 2710 * The initial index of the range (<tt>from</tt>) must lie between zero 2711 * and <tt>original.length</tt>, inclusive. The value at 2712 * <tt>original[from]</tt> is placed into the initial element of the copy 2713 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 2714 * Values from subsequent elements in the original array are placed into 2715 * subsequent elements in the copy. The final index of the range 2716 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 2717 * may be greater than <tt>original.length</tt>, in which case 2718 * <tt>0f</tt> is placed in all elements of the copy whose index is 2719 * greater than or equal to <tt>original.length - from</tt>. The length 2720 * of the returned array will be <tt>to - from</tt>. 2721 * 2722 * @param original the array from which a range is to be copied 2723 * @param from the initial index of the range to be copied, inclusive 2724 * @param to the final index of the range to be copied, exclusive. 2725 * (This index may lie outside the array.) 2726 * @return a new array containing the specified range from the original array, 2727 * truncated or padded with zeros to obtain the required length 2728 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 2729 * or {@code from > original.length} 2730 * @throws IllegalArgumentException if <tt>from > to</tt> 2731 * @throws NullPointerException if <tt>original</tt> is null 2732 * @since 1.6 2733 */ 2734 public static float[] copyOfRange(float[] original, int from, int to) { 2735 int newLength = to - from; 2736 if (newLength < 0) 2737 throw new IllegalArgumentException(from + " > " + to); 2738 float[] copy = new float[newLength]; 2739 System.arraycopy(original, from, copy, 0, 2740 Math.min(original.length - from, newLength)); 2741 return copy; 2742 } 2743 2744 /** 2745 * Copies the specified range of the specified array into a new array. 2746 * The initial index of the range (<tt>from</tt>) must lie between zero 2747 * and <tt>original.length</tt>, inclusive. The value at 2748 * <tt>original[from]</tt> is placed into the initial element of the copy 2749 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 2750 * Values from subsequent elements in the original array are placed into 2751 * subsequent elements in the copy. The final index of the range 2752 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 2753 * may be greater than <tt>original.length</tt>, in which case 2754 * <tt>0d</tt> is placed in all elements of the copy whose index is 2755 * greater than or equal to <tt>original.length - from</tt>. The length 2756 * of the returned array will be <tt>to - from</tt>. 2757 * 2758 * @param original the array from which a range is to be copied 2759 * @param from the initial index of the range to be copied, inclusive 2760 * @param to the final index of the range to be copied, exclusive. 2761 * (This index may lie outside the array.) 2762 * @return a new array containing the specified range from the original array, 2763 * truncated or padded with zeros to obtain the required length 2764 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 2765 * or {@code from > original.length} 2766 * @throws IllegalArgumentException if <tt>from > to</tt> 2767 * @throws NullPointerException if <tt>original</tt> is null 2768 * @since 1.6 2769 */ 2770 public static double[] copyOfRange(double[] original, int from, int to) { 2771 int newLength = to - from; 2772 if (newLength < 0) 2773 throw new IllegalArgumentException(from + " > " + to); 2774 double[] copy = new double[newLength]; 2775 System.arraycopy(original, from, copy, 0, 2776 Math.min(original.length - from, newLength)); 2777 return copy; 2778 } 2779 2780 /** 2781 * Copies the specified range of the specified array into a new array. 2782 * The initial index of the range (<tt>from</tt>) must lie between zero 2783 * and <tt>original.length</tt>, inclusive. The value at 2784 * <tt>original[from]</tt> is placed into the initial element of the copy 2785 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 2786 * Values from subsequent elements in the original array are placed into 2787 * subsequent elements in the copy. The final index of the range 2788 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 2789 * may be greater than <tt>original.length</tt>, in which case 2790 * <tt>false</tt> is placed in all elements of the copy whose index is 2791 * greater than or equal to <tt>original.length - from</tt>. The length 2792 * of the returned array will be <tt>to - from</tt>. 2793 * 2794 * @param original the array from which a range is to be copied 2795 * @param from the initial index of the range to be copied, inclusive 2796 * @param to the final index of the range to be copied, exclusive. 2797 * (This index may lie outside the array.) 2798 * @return a new array containing the specified range from the original array, 2799 * truncated or padded with false elements to obtain the required length 2800 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 2801 * or {@code from > original.length} 2802 * @throws IllegalArgumentException if <tt>from > to</tt> 2803 * @throws NullPointerException if <tt>original</tt> is null 2804 * @since 1.6 2805 */ 2806 public static boolean[] copyOfRange(boolean[] original, int from, int to) { 2807 int newLength = to - from; 2808 if (newLength < 0) 2809 throw new IllegalArgumentException(from + " > " + to); 2810 boolean[] copy = new boolean[newLength]; 2811 System.arraycopy(original, from, copy, 0, 2812 Math.min(original.length - from, newLength)); 2813 return copy; 2814 } 2815 2816 // Misc 2817 2818 /** 2819 * Returns a fixed-size list backed by the specified array. (Changes to 2820 * the returned list "write through" to the array.) This method acts 2821 * as bridge between array-based and collection-based APIs, in 2822 * combination with {@link Collection#toArray}. The returned list is 2823 * serializable and implements {@link RandomAccess}. 2824 * 2825 * <p>This method also provides a convenient way to create a fixed-size 2826 * list initialized to contain several elements: 2827 * <pre> 2828 * List<String> stooges = Arrays.asList("Larry", "Moe", "Curly"); 2829 * </pre> 2830 * 2831 * @param a the array by which the list will be backed 2832 * @return a list view of the specified array 2833 */ 2834 @SafeVarargs 2835 public static <T> List<T> asList(T... a) { 2836 return new ArrayList<>(a); 2837 } 2838 2839 /** 2840 * @serial include 2841 */ 2842 private static class ArrayList<E> extends AbstractList<E> 2843 implements RandomAccess, java.io.Serializable 2844 { 2845 private static final long serialVersionUID = -2764017481108945198L; 2846 private final E[] a; 2847 2848 ArrayList(E[] array) { 2849 if (array==null) 2850 throw new NullPointerException(); 2851 a = array; 2852 } 2853 2854 public int size() { 2855 return a.length; 2856 } 2857 2858 public Object[] toArray() { 2859 return a.clone(); 2860 } 2861 2862 @SuppressWarnings("unchecked") 2863 public <T> T[] toArray(T[] a) { 2864 int size = size(); 2865 if (a.length < size) 2866 return Arrays.copyOf(this.a, size, 2867 (Class<? extends T[]>) a.getClass()); 2868 System.arraycopy(this.a, 0, a, 0, size); 2869 if (a.length > size) 2870 a[size] = null; 2871 return a; 2872 } 2873 2874 public E get(int index) { 2875 return a[index]; 2876 } 2877 2878 public E set(int index, E element) { 2879 E oldValue = a[index]; 2880 a[index] = element; 2881 return oldValue; 2882 } 2883 2884 public int indexOf(Object o) { 2885 if (o==null) { 2886 for (int i=0; i<a.length; i++) 2887 if (a[i]==null) 2888 return i; 2889 } else { 2890 for (int i=0; i<a.length; i++) 2891 if (o.equals(a[i])) 2892 return i; 2893 } 2894 return -1; 2895 } 2896 2897 public boolean contains(Object o) { 2898 return indexOf(o) != -1; 2899 } 2900 } 2901 2902 /** 2903 * Returns a hash code based on the contents of the specified array. 2904 * For any two <tt>long</tt> arrays <tt>a</tt> and <tt>b</tt> 2905 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 2906 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 2907 * 2908 * <p>The value returned by this method is the same value that would be 2909 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 2910 * method on a {@link List} containing a sequence of {@link Long} 2911 * instances representing the elements of <tt>a</tt> in the same order. 2912 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 2913 * 2914 * @param a the array whose hash value to compute 2915 * @return a content-based hash code for <tt>a</tt> 2916 * @since 1.5 2917 */ 2918 public static int hashCode(long a[]) { 2919 if (a == null) 2920 return 0; 2921 2922 int result = 1; 2923 for (long element : a) { 2924 int elementHash = (int)(element ^ (element >>> 32)); 2925 result = 31 * result + elementHash; 2926 } 2927 2928 return result; 2929 } 2930 2931 /** 2932 * Returns a hash code based on the contents of the specified array. 2933 * For any two non-null <tt>int</tt> arrays <tt>a</tt> and <tt>b</tt> 2934 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 2935 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 2936 * 2937 * <p>The value returned by this method is the same value that would be 2938 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 2939 * method on a {@link List} containing a sequence of {@link Integer} 2940 * instances representing the elements of <tt>a</tt> in the same order. 2941 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 2942 * 2943 * @param a the array whose hash value to compute 2944 * @return a content-based hash code for <tt>a</tt> 2945 * @since 1.5 2946 */ 2947 public static int hashCode(int a[]) { 2948 if (a == null) 2949 return 0; 2950 2951 int result = 1; 2952 for (int element : a) 2953 result = 31 * result + element; 2954 2955 return result; 2956 } 2957 2958 /** 2959 * Returns a hash code based on the contents of the specified array. 2960 * For any two <tt>short</tt> arrays <tt>a</tt> and <tt>b</tt> 2961 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 2962 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 2963 * 2964 * <p>The value returned by this method is the same value that would be 2965 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 2966 * method on a {@link List} containing a sequence of {@link Short} 2967 * instances representing the elements of <tt>a</tt> in the same order. 2968 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 2969 * 2970 * @param a the array whose hash value to compute 2971 * @return a content-based hash code for <tt>a</tt> 2972 * @since 1.5 2973 */ 2974 public static int hashCode(short a[]) { 2975 if (a == null) 2976 return 0; 2977 2978 int result = 1; 2979 for (short element : a) 2980 result = 31 * result + element; 2981 2982 return result; 2983 } 2984 2985 /** 2986 * Returns a hash code based on the contents of the specified array. 2987 * For any two <tt>char</tt> arrays <tt>a</tt> and <tt>b</tt> 2988 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 2989 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 2990 * 2991 * <p>The value returned by this method is the same value that would be 2992 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 2993 * method on a {@link List} containing a sequence of {@link Character} 2994 * instances representing the elements of <tt>a</tt> in the same order. 2995 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 2996 * 2997 * @param a the array whose hash value to compute 2998 * @return a content-based hash code for <tt>a</tt> 2999 * @since 1.5 3000 */ 3001 public static int hashCode(char a[]) { 3002 if (a == null) 3003 return 0; 3004 3005 int result = 1; 3006 for (char element : a) 3007 result = 31 * result + element; 3008 3009 return result; 3010 } 3011 3012 /** 3013 * Returns a hash code based on the contents of the specified array. 3014 * For any two <tt>byte</tt> arrays <tt>a</tt> and <tt>b</tt> 3015 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 3016 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 3017 * 3018 * <p>The value returned by this method is the same value that would be 3019 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 3020 * method on a {@link List} containing a sequence of {@link Byte} 3021 * instances representing the elements of <tt>a</tt> in the same order. 3022 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 3023 * 3024 * @param a the array whose hash value to compute 3025 * @return a content-based hash code for <tt>a</tt> 3026 * @since 1.5 3027 */ 3028 public static int hashCode(byte a[]) { 3029 if (a == null) 3030 return 0; 3031 3032 int result = 1; 3033 for (byte element : a) 3034 result = 31 * result + element; 3035 3036 return result; 3037 } 3038 3039 /** 3040 * Returns a hash code based on the contents of the specified array. 3041 * For any two <tt>boolean</tt> arrays <tt>a</tt> and <tt>b</tt> 3042 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 3043 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 3044 * 3045 * <p>The value returned by this method is the same value that would be 3046 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 3047 * method on a {@link List} containing a sequence of {@link Boolean} 3048 * instances representing the elements of <tt>a</tt> in the same order. 3049 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 3050 * 3051 * @param a the array whose hash value to compute 3052 * @return a content-based hash code for <tt>a</tt> 3053 * @since 1.5 3054 */ 3055 public static int hashCode(boolean a[]) { 3056 if (a == null) 3057 return 0; 3058 3059 int result = 1; 3060 for (boolean element : a) 3061 result = 31 * result + (element ? 1231 : 1237); 3062 3063 return result; 3064 } 3065 3066 /** 3067 * Returns a hash code based on the contents of the specified array. 3068 * For any two <tt>float</tt> arrays <tt>a</tt> and <tt>b</tt> 3069 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 3070 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 3071 * 3072 * <p>The value returned by this method is the same value that would be 3073 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 3074 * method on a {@link List} containing a sequence of {@link Float} 3075 * instances representing the elements of <tt>a</tt> in the same order. 3076 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 3077 * 3078 * @param a the array whose hash value to compute 3079 * @return a content-based hash code for <tt>a</tt> 3080 * @since 1.5 3081 */ 3082 public static int hashCode(float a[]) { 3083 if (a == null) 3084 return 0; 3085 3086 int result = 1; 3087 for (float element : a) 3088 result = 31 * result + Float.floatToIntBits(element); 3089 3090 return result; 3091 } 3092 3093 /** 3094 * Returns a hash code based on the contents of the specified array. 3095 * For any two <tt>double</tt> arrays <tt>a</tt> and <tt>b</tt> 3096 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 3097 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 3098 * 3099 * <p>The value returned by this method is the same value that would be 3100 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 3101 * method on a {@link List} containing a sequence of {@link Double} 3102 * instances representing the elements of <tt>a</tt> in the same order. 3103 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 3104 * 3105 * @param a the array whose hash value to compute 3106 * @return a content-based hash code for <tt>a</tt> 3107 * @since 1.5 3108 */ 3109 public static int hashCode(double a[]) { 3110 if (a == null) 3111 return 0; 3112 3113 int result = 1; 3114 for (double element : a) { 3115 long bits = Double.doubleToLongBits(element); 3116 result = 31 * result + (int)(bits ^ (bits >>> 32)); 3117 } 3118 return result; 3119 } 3120 3121 /** 3122 * Returns a hash code based on the contents of the specified array. If 3123 * the array contains other arrays as elements, the hash code is based on 3124 * their identities rather than their contents. It is therefore 3125 * acceptable to invoke this method on an array that contains itself as an 3126 * element, either directly or indirectly through one or more levels of 3127 * arrays. 3128 * 3129 * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that 3130 * <tt>Arrays.equals(a, b)</tt>, it is also the case that 3131 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 3132 * 3133 * <p>The value returned by this method is equal to the value that would 3134 * be returned by <tt>Arrays.asList(a).hashCode()</tt>, unless <tt>a</tt> 3135 * is <tt>null</tt>, in which case <tt>0</tt> is returned. 3136 * 3137 * @param a the array whose content-based hash code to compute 3138 * @return a content-based hash code for <tt>a</tt> 3139 * @see #deepHashCode(Object[]) 3140 * @since 1.5 3141 */ 3142 public static int hashCode(Object a[]) { 3143 if (a == null) 3144 return 0; 3145 3146 int result = 1; 3147 3148 for (Object element : a) 3149 result = 31 * result + (element == null ? 0 : element.hashCode()); 3150 3151 return result; 3152 } 3153 3154 /** 3155 * Returns a hash code based on the "deep contents" of the specified 3156 * array. If the array contains other arrays as elements, the 3157 * hash code is based on their contents and so on, ad infinitum. 3158 * It is therefore unacceptable to invoke this method on an array that 3159 * contains itself as an element, either directly or indirectly through 3160 * one or more levels of arrays. The behavior of such an invocation is 3161 * undefined. 3162 * 3163 * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that 3164 * <tt>Arrays.deepEquals(a, b)</tt>, it is also the case that 3165 * <tt>Arrays.deepHashCode(a) == Arrays.deepHashCode(b)</tt>. 3166 * 3167 * <p>The computation of the value returned by this method is similar to 3168 * that of the value returned by {@link List#hashCode()} on a list 3169 * containing the same elements as <tt>a</tt> in the same order, with one 3170 * difference: If an element <tt>e</tt> of <tt>a</tt> is itself an array, 3171 * its hash code is computed not by calling <tt>e.hashCode()</tt>, but as 3172 * by calling the appropriate overloading of <tt>Arrays.hashCode(e)</tt> 3173 * if <tt>e</tt> is an array of a primitive type, or as by calling 3174 * <tt>Arrays.deepHashCode(e)</tt> recursively if <tt>e</tt> is an array 3175 * of a reference type. If <tt>a</tt> is <tt>null</tt>, this method 3176 * returns 0. 3177 * 3178 * @param a the array whose deep-content-based hash code to compute 3179 * @return a deep-content-based hash code for <tt>a</tt> 3180 * @see #hashCode(Object[]) 3181 * @since 1.5 3182 */ 3183 public static int deepHashCode(Object a[]) { 3184 if (a == null) 3185 return 0; 3186 3187 int result = 1; 3188 3189 for (Object element : a) { 3190 int elementHash = 0; 3191 if (element instanceof Object[]) 3192 elementHash = deepHashCode((Object[]) element); 3193 else if (element instanceof byte[]) 3194 elementHash = hashCode((byte[]) element); 3195 else if (element instanceof short[]) 3196 elementHash = hashCode((short[]) element); 3197 else if (element instanceof int[]) 3198 elementHash = hashCode((int[]) element); 3199 else if (element instanceof long[]) 3200 elementHash = hashCode((long[]) element); 3201 else if (element instanceof char[]) 3202 elementHash = hashCode((char[]) element); 3203 else if (element instanceof float[]) 3204 elementHash = hashCode((float[]) element); 3205 else if (element instanceof double[]) 3206 elementHash = hashCode((double[]) element); 3207 else if (element instanceof boolean[]) 3208 elementHash = hashCode((boolean[]) element); 3209 else if (element != null) 3210 elementHash = element.hashCode(); 3211 3212 result = 31 * result + elementHash; 3213 } 3214 3215 return result; 3216 } 3217 3218 /** 3219 * Returns <tt>true</tt> if the two specified arrays are <i>deeply 3220 * equal</i> to one another. Unlike the {@link #equals(Object[],Object[])} 3221 * method, this method is appropriate for use with nested arrays of 3222 * arbitrary depth. 3223 * 3224 * <p>Two array references are considered deeply equal if both 3225 * are <tt>null</tt>, or if they refer to arrays that contain the same 3226 * number of elements and all corresponding pairs of elements in the two 3227 * arrays are deeply equal. 3228 * 3229 * <p>Two possibly <tt>null</tt> elements <tt>e1</tt> and <tt>e2</tt> are 3230 * deeply equal if any of the following conditions hold: 3231 * <ul> 3232 * <li> <tt>e1</tt> and <tt>e2</tt> are both arrays of object reference 3233 * types, and <tt>Arrays.deepEquals(e1, e2) would return true</tt> 3234 * <li> <tt>e1</tt> and <tt>e2</tt> are arrays of the same primitive 3235 * type, and the appropriate overloading of 3236 * <tt>Arrays.equals(e1, e2)</tt> would return true. 3237 * <li> <tt>e1 == e2</tt> 3238 * <li> <tt>e1.equals(e2)</tt> would return true. 3239 * </ul> 3240 * Note that this definition permits <tt>null</tt> elements at any depth. 3241 * 3242 * <p>If either of the specified arrays contain themselves as elements 3243 * either directly or indirectly through one or more levels of arrays, 3244 * the behavior of this method is undefined. 3245 * 3246 * @param a1 one array to be tested for equality 3247 * @param a2 the other array to be tested for equality 3248 * @return <tt>true</tt> if the two arrays are equal 3249 * @see #equals(Object[],Object[]) 3250 * @see Objects#deepEquals(Object, Object) 3251 * @since 1.5 3252 */ 3253 public static boolean deepEquals(Object[] a1, Object[] a2) { 3254 if (a1 == a2) 3255 return true; 3256 if (a1 == null || a2==null) 3257 return false; 3258 int length = a1.length; 3259 if (a2.length != length) 3260 return false; 3261 3262 for (int i = 0; i < length; i++) { 3263 Object e1 = a1[i]; 3264 Object e2 = a2[i]; 3265 3266 if (e1 == e2) 3267 continue; 3268 if (e1 == null) 3269 return false; 3270 3271 // Figure out whether the two elements are equal 3272 boolean eq = deepEquals0(e1, e2); 3273 3274 if (!eq) 3275 return false; 3276 } 3277 return true; 3278 } 3279 3280 static boolean deepEquals0(Object e1, Object e2) { 3281 assert e1 != null; 3282 boolean eq; 3283 if (e1 instanceof Object[] && e2 instanceof Object[]) 3284 eq = deepEquals ((Object[]) e1, (Object[]) e2); 3285 else if (e1 instanceof byte[] && e2 instanceof byte[]) 3286 eq = equals((byte[]) e1, (byte[]) e2); 3287 else if (e1 instanceof short[] && e2 instanceof short[]) 3288 eq = equals((short[]) e1, (short[]) e2); 3289 else if (e1 instanceof int[] && e2 instanceof int[]) 3290 eq = equals((int[]) e1, (int[]) e2); 3291 else if (e1 instanceof long[] && e2 instanceof long[]) 3292 eq = equals((long[]) e1, (long[]) e2); 3293 else if (e1 instanceof char[] && e2 instanceof char[]) 3294 eq = equals((char[]) e1, (char[]) e2); 3295 else if (e1 instanceof float[] && e2 instanceof float[]) 3296 eq = equals((float[]) e1, (float[]) e2); 3297 else if (e1 instanceof double[] && e2 instanceof double[]) 3298 eq = equals((double[]) e1, (double[]) e2); 3299 else if (e1 instanceof boolean[] && e2 instanceof boolean[]) 3300 eq = equals((boolean[]) e1, (boolean[]) e2); 3301 else 3302 eq = e1.equals(e2); 3303 return eq; 3304 } 3305 3306 /** 3307 * Returns a string representation of the contents of the specified array. 3308 * The string representation consists of a list of the array's elements, 3309 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 3310 * separated by the characters <tt>", "</tt> (a comma followed by a 3311 * space). Elements are converted to strings as by 3312 * <tt>String.valueOf(long)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> 3313 * is <tt>null</tt>. 3314 * 3315 * @param a the array whose string representation to return 3316 * @return a string representation of <tt>a</tt> 3317 * @since 1.5 3318 */ 3319 public static String toString(long[] a) { 3320 if (a == null) 3321 return "null"; 3322 int iMax = a.length - 1; 3323 if (iMax == -1) 3324 return "[]"; 3325 3326 StringBuilder b = new StringBuilder(); 3327 b.append('['); 3328 for (int i = 0; ; i++) { 3329 b.append(a[i]); 3330 if (i == iMax) 3331 return b.append(']').toString(); 3332 b.append(", "); 3333 } 3334 } 3335 3336 /** 3337 * Returns a string representation of the contents of the specified array. 3338 * The string representation consists of a list of the array's elements, 3339 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 3340 * separated by the characters <tt>", "</tt> (a comma followed by a 3341 * space). Elements are converted to strings as by 3342 * <tt>String.valueOf(int)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> is 3343 * <tt>null</tt>. 3344 * 3345 * @param a the array whose string representation to return 3346 * @return a string representation of <tt>a</tt> 3347 * @since 1.5 3348 */ 3349 public static String toString(int[] a) { 3350 if (a == null) 3351 return "null"; 3352 int iMax = a.length - 1; 3353 if (iMax == -1) 3354 return "[]"; 3355 3356 StringBuilder b = new StringBuilder(); 3357 b.append('['); 3358 for (int i = 0; ; i++) { 3359 b.append(a[i]); 3360 if (i == iMax) 3361 return b.append(']').toString(); 3362 b.append(", "); 3363 } 3364 } 3365 3366 /** 3367 * Returns a string representation of the contents of the specified array. 3368 * The string representation consists of a list of the array's elements, 3369 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 3370 * separated by the characters <tt>", "</tt> (a comma followed by a 3371 * space). Elements are converted to strings as by 3372 * <tt>String.valueOf(short)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> 3373 * is <tt>null</tt>. 3374 * 3375 * @param a the array whose string representation to return 3376 * @return a string representation of <tt>a</tt> 3377 * @since 1.5 3378 */ 3379 public static String toString(short[] a) { 3380 if (a == null) 3381 return "null"; 3382 int iMax = a.length - 1; 3383 if (iMax == -1) 3384 return "[]"; 3385 3386 StringBuilder b = new StringBuilder(); 3387 b.append('['); 3388 for (int i = 0; ; i++) { 3389 b.append(a[i]); 3390 if (i == iMax) 3391 return b.append(']').toString(); 3392 b.append(", "); 3393 } 3394 } 3395 3396 /** 3397 * Returns a string representation of the contents of the specified array. 3398 * The string representation consists of a list of the array's elements, 3399 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 3400 * separated by the characters <tt>", "</tt> (a comma followed by a 3401 * space). Elements are converted to strings as by 3402 * <tt>String.valueOf(char)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> 3403 * is <tt>null</tt>. 3404 * 3405 * @param a the array whose string representation to return 3406 * @return a string representation of <tt>a</tt> 3407 * @since 1.5 3408 */ 3409 public static String toString(char[] a) { 3410 if (a == null) 3411 return "null"; 3412 int iMax = a.length - 1; 3413 if (iMax == -1) 3414 return "[]"; 3415 3416 StringBuilder b = new StringBuilder(); 3417 b.append('['); 3418 for (int i = 0; ; i++) { 3419 b.append(a[i]); 3420 if (i == iMax) 3421 return b.append(']').toString(); 3422 b.append(", "); 3423 } 3424 } 3425 3426 /** 3427 * Returns a string representation of the contents of the specified array. 3428 * The string representation consists of a list of the array's elements, 3429 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements 3430 * are separated by the characters <tt>", "</tt> (a comma followed 3431 * by a space). Elements are converted to strings as by 3432 * <tt>String.valueOf(byte)</tt>. Returns <tt>"null"</tt> if 3433 * <tt>a</tt> is <tt>null</tt>. 3434 * 3435 * @param a the array whose string representation to return 3436 * @return a string representation of <tt>a</tt> 3437 * @since 1.5 3438 */ 3439 public static String toString(byte[] a) { 3440 if (a == null) 3441 return "null"; 3442 int iMax = a.length - 1; 3443 if (iMax == -1) 3444 return "[]"; 3445 3446 StringBuilder b = new StringBuilder(); 3447 b.append('['); 3448 for (int i = 0; ; i++) { 3449 b.append(a[i]); 3450 if (i == iMax) 3451 return b.append(']').toString(); 3452 b.append(", "); 3453 } 3454 } 3455 3456 /** 3457 * Returns a string representation of the contents of the specified array. 3458 * The string representation consists of a list of the array's elements, 3459 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 3460 * separated by the characters <tt>", "</tt> (a comma followed by a 3461 * space). Elements are converted to strings as by 3462 * <tt>String.valueOf(boolean)</tt>. Returns <tt>"null"</tt> if 3463 * <tt>a</tt> is <tt>null</tt>. 3464 * 3465 * @param a the array whose string representation to return 3466 * @return a string representation of <tt>a</tt> 3467 * @since 1.5 3468 */ 3469 public static String toString(boolean[] a) { 3470 if (a == null) 3471 return "null"; 3472 int iMax = a.length - 1; 3473 if (iMax == -1) 3474 return "[]"; 3475 3476 StringBuilder b = new StringBuilder(); 3477 b.append('['); 3478 for (int i = 0; ; i++) { 3479 b.append(a[i]); 3480 if (i == iMax) 3481 return b.append(']').toString(); 3482 b.append(", "); 3483 } 3484 } 3485 3486 /** 3487 * Returns a string representation of the contents of the specified array. 3488 * The string representation consists of a list of the array's elements, 3489 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 3490 * separated by the characters <tt>", "</tt> (a comma followed by a 3491 * space). Elements are converted to strings as by 3492 * <tt>String.valueOf(float)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> 3493 * is <tt>null</tt>. 3494 * 3495 * @param a the array whose string representation to return 3496 * @return a string representation of <tt>a</tt> 3497 * @since 1.5 3498 */ 3499 public static String toString(float[] a) { 3500 if (a == null) 3501 return "null"; 3502 3503 int iMax = a.length - 1; 3504 if (iMax == -1) 3505 return "[]"; 3506 3507 StringBuilder b = new StringBuilder(); 3508 b.append('['); 3509 for (int i = 0; ; i++) { 3510 b.append(a[i]); 3511 if (i == iMax) 3512 return b.append(']').toString(); 3513 b.append(", "); 3514 } 3515 } 3516 3517 /** 3518 * Returns a string representation of the contents of the specified array. 3519 * The string representation consists of a list of the array's elements, 3520 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 3521 * separated by the characters <tt>", "</tt> (a comma followed by a 3522 * space). Elements are converted to strings as by 3523 * <tt>String.valueOf(double)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> 3524 * is <tt>null</tt>. 3525 * 3526 * @param a the array whose string representation to return 3527 * @return a string representation of <tt>a</tt> 3528 * @since 1.5 3529 */ 3530 public static String toString(double[] a) { 3531 if (a == null) 3532 return "null"; 3533 int iMax = a.length - 1; 3534 if (iMax == -1) 3535 return "[]"; 3536 3537 StringBuilder b = new StringBuilder(); 3538 b.append('['); 3539 for (int i = 0; ; i++) { 3540 b.append(a[i]); 3541 if (i == iMax) 3542 return b.append(']').toString(); 3543 b.append(", "); 3544 } 3545 } 3546 3547 /** 3548 * Returns a string representation of the contents of the specified array. 3549 * If the array contains other arrays as elements, they are converted to 3550 * strings by the {@link Object#toString} method inherited from 3551 * <tt>Object</tt>, which describes their <i>identities</i> rather than 3552 * their contents. 3553 * 3554 * <p>The value returned by this method is equal to the value that would 3555 * be returned by <tt>Arrays.asList(a).toString()</tt>, unless <tt>a</tt> 3556 * is <tt>null</tt>, in which case <tt>"null"</tt> is returned. 3557 * 3558 * @param a the array whose string representation to return 3559 * @return a string representation of <tt>a</tt> 3560 * @see #deepToString(Object[]) 3561 * @since 1.5 3562 */ 3563 public static String toString(Object[] a) { 3564 if (a == null) 3565 return "null"; 3566 3567 int iMax = a.length - 1; 3568 if (iMax == -1) 3569 return "[]"; 3570 3571 StringBuilder b = new StringBuilder(); 3572 b.append('['); 3573 for (int i = 0; ; i++) { 3574 b.append(String.valueOf(a[i])); 3575 if (i == iMax) 3576 return b.append(']').toString(); 3577 b.append(", "); 3578 } 3579 } 3580 3581 /** 3582 * Returns a string representation of the "deep contents" of the specified 3583 * array. If the array contains other arrays as elements, the string 3584 * representation contains their contents and so on. This method is 3585 * designed for converting multidimensional arrays to strings. 3586 * 3587 * <p>The string representation consists of a list of the array's 3588 * elements, enclosed in square brackets (<tt>"[]"</tt>). Adjacent 3589 * elements are separated by the characters <tt>", "</tt> (a comma 3590 * followed by a space). Elements are converted to strings as by 3591 * <tt>String.valueOf(Object)</tt>, unless they are themselves 3592 * arrays. 3593 * 3594 * <p>If an element <tt>e</tt> is an array of a primitive type, it is 3595 * converted to a string as by invoking the appropriate overloading of 3596 * <tt>Arrays.toString(e)</tt>. If an element <tt>e</tt> is an array of a 3597 * reference type, it is converted to a string as by invoking 3598 * this method recursively. 3599 * 3600 * <p>To avoid infinite recursion, if the specified array contains itself 3601 * as an element, or contains an indirect reference to itself through one 3602 * or more levels of arrays, the self-reference is converted to the string 3603 * <tt>"[...]"</tt>. For example, an array containing only a reference 3604 * to itself would be rendered as <tt>"[[...]]"</tt>. 3605 * 3606 * <p>This method returns <tt>"null"</tt> if the specified array 3607 * is <tt>null</tt>. 3608 * 3609 * @param a the array whose string representation to return 3610 * @return a string representation of <tt>a</tt> 3611 * @see #toString(Object[]) 3612 * @since 1.5 3613 */ 3614 public static String deepToString(Object[] a) { 3615 if (a == null) 3616 return "null"; 3617 3618 int bufLen = 20 * a.length; 3619 if (a.length != 0 && bufLen <= 0) 3620 bufLen = Integer.MAX_VALUE; 3621 StringBuilder buf = new StringBuilder(bufLen); 3622 deepToString(a, buf, new HashSet<Object[]>()); 3623 return buf.toString(); 3624 } 3625 3626 private static void deepToString(Object[] a, StringBuilder buf, 3627 Set<Object[]> dejaVu) { 3628 if (a == null) { 3629 buf.append("null"); 3630 return; 3631 } 3632 int iMax = a.length - 1; 3633 if (iMax == -1) { 3634 buf.append("[]"); 3635 return; 3636 } 3637 3638 dejaVu.add(a); 3639 buf.append('['); 3640 for (int i = 0; ; i++) { 3641 3642 Object element = a[i]; 3643 if (element == null) { 3644 buf.append("null"); 3645 } else { 3646 Class<?> eClass = element.getClass(); 3647 3648 if (eClass.isArray()) { 3649 if (eClass == byte[].class) 3650 buf.append(toString((byte[]) element)); 3651 else if (eClass == short[].class) 3652 buf.append(toString((short[]) element)); 3653 else if (eClass == int[].class) 3654 buf.append(toString((int[]) element)); 3655 else if (eClass == long[].class) 3656 buf.append(toString((long[]) element)); 3657 else if (eClass == char[].class) 3658 buf.append(toString((char[]) element)); 3659 else if (eClass == float[].class) 3660 buf.append(toString((float[]) element)); 3661 else if (eClass == double[].class) 3662 buf.append(toString((double[]) element)); 3663 else if (eClass == boolean[].class) 3664 buf.append(toString((boolean[]) element)); 3665 else { // element is an array of object references 3666 if (dejaVu.contains(element)) 3667 buf.append("[...]"); 3668 else 3669 deepToString((Object[])element, buf, dejaVu); 3670 } 3671 } else { // element is non-null and not an array 3672 buf.append(element.toString()); 3673 } 3674 } 3675 if (i == iMax) 3676 break; 3677 buf.append(", "); 3678 } 3679 buf.append(']'); 3680 dejaVu.remove(a); 3681 } 3682 }