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