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