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