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