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