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