Arrays.java revision 6975f84c2ed72e1e26d20190b6f318718c849008
1/* 2 * Copyright (C) 2014 The Android Open Source Project 3 * Copyright (c) 1997, 2014, Oracle and/or its affiliates. All rights reserved. 4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 5 * 6 * This code is free software; you can redistribute it and/or modify it 7 * under the terms of the GNU General Public License version 2 only, as 8 * published by the Free Software Foundation. Oracle designates this 9 * particular file as subject to the "Classpath" exception as provided 10 * by Oracle in the LICENSE file that accompanied this code. 11 * 12 * This code is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 * version 2 for more details (a copy is included in the LICENSE file that 16 * accompanied this code). 17 * 18 * You should have received a copy of the GNU General Public License version 19 * 2 along with this work; if not, write to the Free Software Foundation, 20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 21 * 22 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 23 * or visit www.oracle.com if you need additional information or have any 24 * questions. 25 */ 26 27package java.util; 28 29import java.lang.reflect.Array; 30import java.util.concurrent.ForkJoinPool; 31import java.util.function.BinaryOperator; 32import java.util.function.Consumer; 33import java.util.function.DoubleBinaryOperator; 34import java.util.function.IntBinaryOperator; 35import java.util.function.IntFunction; 36import java.util.function.IntToDoubleFunction; 37import java.util.function.IntToLongFunction; 38import java.util.function.IntUnaryOperator; 39import java.util.function.LongBinaryOperator; 40import java.util.function.UnaryOperator; 41import java.util.stream.DoubleStream; 42import java.util.stream.IntStream; 43import java.util.stream.LongStream; 44import java.util.stream.Stream; 45import java.util.stream.StreamSupport; 46 47/** 48 * This class contains various methods for manipulating arrays (such as 49 * sorting and searching). This class also contains a static factory 50 * that allows arrays to be viewed as lists. 51 * 52 * <p>The methods in this class all throw a {@code NullPointerException}, 53 * if the specified array reference is null, except where noted. 54 * 55 * <p>The documentation for the methods contained in this class includes 56 * briefs description of the <i>implementations</i>. Such descriptions should 57 * be regarded as <i>implementation notes</i>, rather than parts of the 58 * <i>specification</i>. Implementors should feel free to substitute other 59 * algorithms, so long as the specification itself is adhered to. (For 60 * example, the algorithm used by {@code sort(Object[])} does not have to be 61 * a MergeSort, but it does have to be <i>stable</i>.) 62 * 63 * <p>This class is a member of the 64 * <a href="{@docRoot}openjdk-redirect.html?v=8&path=/technotes/guides/collections/index.html"> 65 * Java Collections Framework</a>. 66 * 67 * @author Josh Bloch 68 * @author Neal Gafter 69 * @author John Rose 70 * @since 1.2 71 */ 72public class Arrays { 73 74 /** 75 * The minimum array length below which a parallel sorting 76 * algorithm will not further partition the sorting task. Using 77 * smaller sizes typically results in memory contention across 78 * tasks that makes parallel speedups unlikely. 79 * @hide 80 */ 81 public static final int MIN_ARRAY_SORT_GRAN = 1 << 13; 82 83 // Suppresses default constructor, ensuring non-instantiability. 84 private Arrays() {} 85 86 /** 87 * A comparator that implements the natural ordering of a group of 88 * mutually comparable elements. May be used when a supplied 89 * comparator is null. To simplify code-sharing within underlying 90 * implementations, the compare method only declares type Object 91 * for its second argument. 92 * 93 * Arrays class implementor's note: It is an empirical matter 94 * whether ComparableTimSort offers any performance benefit over 95 * TimSort used with this comparator. If not, you are better off 96 * deleting or bypassing ComparableTimSort. There is currently no 97 * empirical case for separating them for parallel sorting, so all 98 * public Object parallelSort methods use the same comparator 99 * based implementation. 100 */ 101 static final class NaturalOrder implements Comparator<Object> { 102 @SuppressWarnings("unchecked") 103 public int compare(Object first, Object second) { 104 return ((Comparable<Object>)first).compareTo(second); 105 } 106 static final NaturalOrder INSTANCE = new NaturalOrder(); 107 } 108 109 /** 110 * Checks that {@code fromIndex} and {@code toIndex} are in 111 * the range and throws an appropriate exception, if they aren't. 112 */ 113 private static void rangeCheck(int length, int fromIndex, int toIndex) { 114 if (fromIndex > toIndex) { 115 throw new IllegalArgumentException( 116 "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); 117 } 118 if (fromIndex < 0) { 119 throw new ArrayIndexOutOfBoundsException(fromIndex); 120 } 121 if (toIndex > length) { 122 throw new ArrayIndexOutOfBoundsException(toIndex); 123 } 124 } 125 126 /** 127 * Checks that the range described by {@code offset} and {@code count} doesn't exceed 128 * {@code arrayLength}. 129 * 130 * Android-changed. 131 * @hide 132 */ 133 public static void checkOffsetAndCount(int arrayLength, int offset, int count) { 134 if ((offset | count) < 0 || offset > arrayLength || arrayLength - offset < count) { 135 throw new ArrayIndexOutOfBoundsException(arrayLength, offset, 136 count); 137 } 138 } 139 140 /* 141 * Sorting methods. Note that all public "sort" methods take the 142 * same form: Performing argument checks if necessary, and then 143 * expanding arguments into those required for the internal 144 * implementation methods residing in other package-private 145 * classes (except for legacyMergeSort, included in this class). 146 */ 147 148 /** 149 * Sorts the specified array into ascending numerical order. 150 * 151 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 152 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 153 * offers O(n log(n)) performance on many data sets that cause other 154 * quicksorts to degrade to quadratic performance, and is typically 155 * faster than traditional (one-pivot) Quicksort implementations. 156 * 157 * @param a the array to be sorted 158 */ 159 public static void sort(int[] a) { 160 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); 161 } 162 163 /** 164 * Sorts the specified range of the array into ascending order. The range 165 * to be sorted extends from the index {@code fromIndex}, inclusive, to 166 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 167 * the range to be sorted is empty. 168 * 169 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 170 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 171 * offers O(n log(n)) performance on many data sets that cause other 172 * quicksorts to degrade to quadratic performance, and is typically 173 * faster than traditional (one-pivot) Quicksort implementations. 174 * 175 * @param a the array to be sorted 176 * @param fromIndex the index of the first element, inclusive, to be sorted 177 * @param toIndex the index of the last element, exclusive, to be sorted 178 * 179 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 180 * @throws ArrayIndexOutOfBoundsException 181 * if {@code fromIndex < 0} or {@code toIndex > a.length} 182 */ 183 public static void sort(int[] a, int fromIndex, int toIndex) { 184 rangeCheck(a.length, fromIndex, toIndex); 185 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); 186 } 187 188 /** 189 * Sorts the specified array into ascending numerical order. 190 * 191 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 192 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 193 * offers O(n log(n)) performance on many data sets that cause other 194 * quicksorts to degrade to quadratic performance, and is typically 195 * faster than traditional (one-pivot) Quicksort implementations. 196 * 197 * @param a the array to be sorted 198 */ 199 public static void sort(long[] a) { 200 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); 201 } 202 203 /** 204 * Sorts the specified range of the array into ascending order. The range 205 * to be sorted extends from the index {@code fromIndex}, inclusive, to 206 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 207 * the range to be sorted is empty. 208 * 209 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 210 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 211 * offers O(n log(n)) performance on many data sets that cause other 212 * quicksorts to degrade to quadratic performance, and is typically 213 * faster than traditional (one-pivot) Quicksort implementations. 214 * 215 * @param a the array to be sorted 216 * @param fromIndex the index of the first element, inclusive, to be sorted 217 * @param toIndex the index of the last element, exclusive, to be sorted 218 * 219 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 220 * @throws ArrayIndexOutOfBoundsException 221 * if {@code fromIndex < 0} or {@code toIndex > a.length} 222 */ 223 public static void sort(long[] a, int fromIndex, int toIndex) { 224 rangeCheck(a.length, fromIndex, toIndex); 225 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); 226 } 227 228 /** 229 * Sorts the specified array into ascending numerical order. 230 * 231 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 232 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 233 * offers O(n log(n)) performance on many data sets that cause other 234 * quicksorts to degrade to quadratic performance, and is typically 235 * faster than traditional (one-pivot) Quicksort implementations. 236 * 237 * @param a the array to be sorted 238 */ 239 public static void sort(short[] a) { 240 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); 241 } 242 243 /** 244 * Sorts the specified range of the array into ascending order. The range 245 * to be sorted extends from the index {@code fromIndex}, inclusive, to 246 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 247 * the range to be sorted is empty. 248 * 249 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 250 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 251 * offers O(n log(n)) performance on many data sets that cause other 252 * quicksorts to degrade to quadratic performance, and is typically 253 * faster than traditional (one-pivot) Quicksort implementations. 254 * 255 * @param a the array to be sorted 256 * @param fromIndex the index of the first element, inclusive, to be sorted 257 * @param toIndex the index of the last element, exclusive, to be sorted 258 * 259 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 260 * @throws ArrayIndexOutOfBoundsException 261 * if {@code fromIndex < 0} or {@code toIndex > a.length} 262 */ 263 public static void sort(short[] a, int fromIndex, int toIndex) { 264 rangeCheck(a.length, fromIndex, toIndex); 265 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); 266 } 267 268 /** 269 * Sorts the specified array into ascending numerical order. 270 * 271 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 272 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 273 * offers O(n log(n)) performance on many data sets that cause other 274 * quicksorts to degrade to quadratic performance, and is typically 275 * faster than traditional (one-pivot) Quicksort implementations. 276 * 277 * @param a the array to be sorted 278 */ 279 public static void sort(char[] a) { 280 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); 281 } 282 283 /** 284 * Sorts the specified range of the array into ascending order. The range 285 * to be sorted extends from the index {@code fromIndex}, inclusive, to 286 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 287 * the range to be sorted is empty. 288 * 289 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 290 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 291 * offers O(n log(n)) performance on many data sets that cause other 292 * quicksorts to degrade to quadratic performance, and is typically 293 * faster than traditional (one-pivot) Quicksort implementations. 294 * 295 * @param a the array to be sorted 296 * @param fromIndex the index of the first element, inclusive, to be sorted 297 * @param toIndex the index of the last element, exclusive, to be sorted 298 * 299 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 300 * @throws ArrayIndexOutOfBoundsException 301 * if {@code fromIndex < 0} or {@code toIndex > a.length} 302 */ 303 public static void sort(char[] a, int fromIndex, int toIndex) { 304 rangeCheck(a.length, fromIndex, toIndex); 305 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); 306 } 307 308 /** 309 * Sorts the specified array into ascending numerical order. 310 * 311 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 312 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 313 * offers O(n log(n)) performance on many data sets that cause other 314 * quicksorts to degrade to quadratic performance, and is typically 315 * faster than traditional (one-pivot) Quicksort implementations. 316 * 317 * @param a the array to be sorted 318 */ 319 public static void sort(byte[] a) { 320 DualPivotQuicksort.sort(a, 0, a.length - 1); 321 } 322 323 /** 324 * Sorts the specified range of the array into ascending order. The range 325 * to be sorted extends from the index {@code fromIndex}, inclusive, to 326 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 327 * the range to be sorted is empty. 328 * 329 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 330 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 331 * offers O(n log(n)) performance on many data sets that cause other 332 * quicksorts to degrade to quadratic performance, and is typically 333 * faster than traditional (one-pivot) Quicksort implementations. 334 * 335 * @param a the array to be sorted 336 * @param fromIndex the index of the first element, inclusive, to be sorted 337 * @param toIndex the index of the last element, exclusive, to be sorted 338 * 339 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 340 * @throws ArrayIndexOutOfBoundsException 341 * if {@code fromIndex < 0} or {@code toIndex > a.length} 342 */ 343 public static void sort(byte[] a, int fromIndex, int toIndex) { 344 rangeCheck(a.length, fromIndex, toIndex); 345 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); 346 } 347 348 /** 349 * Sorts the specified array into ascending numerical order. 350 * 351 * <p>The {@code <} relation does not provide a total order on all float 352 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN} 353 * value compares neither less than, greater than, nor equal to any value, 354 * even itself. This method uses the total order imposed by the method 355 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value 356 * {@code 0.0f} and {@code Float.NaN} is considered greater than any 357 * other value and all {@code Float.NaN} values are considered equal. 358 * 359 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 360 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 361 * offers O(n log(n)) performance on many data sets that cause other 362 * quicksorts to degrade to quadratic performance, and is typically 363 * faster than traditional (one-pivot) Quicksort implementations. 364 * 365 * @param a the array to be sorted 366 */ 367 public static void sort(float[] a) { 368 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); 369 } 370 371 /** 372 * Sorts the specified range of the array into ascending order. The range 373 * to be sorted extends from the index {@code fromIndex}, inclusive, to 374 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 375 * the range to be sorted is empty. 376 * 377 * <p>The {@code <} relation does not provide a total order on all float 378 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN} 379 * value compares neither less than, greater than, nor equal to any value, 380 * even itself. This method uses the total order imposed by the method 381 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value 382 * {@code 0.0f} and {@code Float.NaN} is considered greater than any 383 * other value and all {@code Float.NaN} values are considered equal. 384 * 385 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 386 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 387 * offers O(n log(n)) performance on many data sets that cause other 388 * quicksorts to degrade to quadratic performance, and is typically 389 * faster than traditional (one-pivot) Quicksort implementations. 390 * 391 * @param a the array to be sorted 392 * @param fromIndex the index of the first element, inclusive, to be sorted 393 * @param toIndex the index of the last element, exclusive, to be sorted 394 * 395 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 396 * @throws ArrayIndexOutOfBoundsException 397 * if {@code fromIndex < 0} or {@code toIndex > a.length} 398 */ 399 public static void sort(float[] a, int fromIndex, int toIndex) { 400 rangeCheck(a.length, fromIndex, toIndex); 401 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); 402 } 403 404 /** 405 * Sorts the specified array into ascending numerical order. 406 * 407 * <p>The {@code <} relation does not provide a total order on all double 408 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN} 409 * value compares neither less than, greater than, nor equal to any value, 410 * even itself. This method uses the total order imposed by the method 411 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value 412 * {@code 0.0d} and {@code Double.NaN} is considered greater than any 413 * other value and all {@code Double.NaN} values are considered equal. 414 * 415 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 416 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 417 * offers O(n log(n)) performance on many data sets that cause other 418 * quicksorts to degrade to quadratic performance, and is typically 419 * faster than traditional (one-pivot) Quicksort implementations. 420 * 421 * @param a the array to be sorted 422 */ 423 public static void sort(double[] a) { 424 DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); 425 } 426 427 /** 428 * Sorts the specified range of the array into ascending order. The range 429 * to be sorted extends from the index {@code fromIndex}, inclusive, to 430 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex}, 431 * the range to be sorted is empty. 432 * 433 * <p>The {@code <} relation does not provide a total order on all double 434 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN} 435 * value compares neither less than, greater than, nor equal to any value, 436 * even itself. This method uses the total order imposed by the method 437 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value 438 * {@code 0.0d} and {@code Double.NaN} is considered greater than any 439 * other value and all {@code Double.NaN} values are considered equal. 440 * 441 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 442 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 443 * offers O(n log(n)) performance on many data sets that cause other 444 * quicksorts to degrade to quadratic performance, and is typically 445 * faster than traditional (one-pivot) Quicksort implementations. 446 * 447 * @param a the array to be sorted 448 * @param fromIndex the index of the first element, inclusive, to be sorted 449 * @param toIndex the index of the last element, exclusive, to be sorted 450 * 451 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 452 * @throws ArrayIndexOutOfBoundsException 453 * if {@code fromIndex < 0} or {@code toIndex > a.length} 454 */ 455 public static void sort(double[] a, int fromIndex, int toIndex) { 456 rangeCheck(a.length, fromIndex, toIndex); 457 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); 458 } 459 460 /** 461 * Sorts the specified array into ascending numerical order. 462 * 463 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 464 * array into sub-arrays that are themselves sorted and then merged. When 465 * the sub-array length reaches a minimum granularity, the sub-array is 466 * sorted using the appropriate {@link Arrays#sort(byte[]) Arrays.sort} 467 * method. If the length of the specified array is less than the minimum 468 * granularity, then it is sorted using the appropriate {@link 469 * Arrays#sort(byte[]) Arrays.sort} method. The algorithm requires a 470 * working space no greater than the size of the original array. The 471 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to 472 * execute any parallel tasks. 473 * 474 * @param a the array to be sorted 475 * 476 * @since 1.8 477 */ 478 public static void parallelSort(byte[] a) { 479 int n = a.length, p, g; 480 if (n <= MIN_ARRAY_SORT_GRAN || 481 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 482 DualPivotQuicksort.sort(a, 0, n - 1); 483 else 484 new ArraysParallelSortHelpers.FJByte.Sorter 485 (null, a, new byte[n], 0, n, 0, 486 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 487 MIN_ARRAY_SORT_GRAN : g).invoke(); 488 } 489 490 /** 491 * Sorts the specified range of the array into ascending numerical order. 492 * The range to be sorted extends from the index {@code fromIndex}, 493 * inclusive, to the index {@code toIndex}, exclusive. If 494 * {@code fromIndex == toIndex}, the range to be sorted is empty. 495 * 496 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 497 * array into sub-arrays that are themselves sorted and then merged. When 498 * the sub-array length reaches a minimum granularity, the sub-array is 499 * sorted using the appropriate {@link Arrays#sort(byte[]) Arrays.sort} 500 * method. If the length of the specified array is less than the minimum 501 * granularity, then it is sorted using the appropriate {@link 502 * Arrays#sort(byte[]) Arrays.sort} method. The algorithm requires a working 503 * space no greater than the size of the specified range of the original 504 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is 505 * used to execute any parallel tasks. 506 * 507 * @param a the array to be sorted 508 * @param fromIndex the index of the first element, inclusive, to be sorted 509 * @param toIndex the index of the last element, exclusive, to be sorted 510 * 511 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 512 * @throws ArrayIndexOutOfBoundsException 513 * if {@code fromIndex < 0} or {@code toIndex > a.length} 514 * 515 * @since 1.8 516 */ 517 public static void parallelSort(byte[] a, int fromIndex, int toIndex) { 518 rangeCheck(a.length, fromIndex, toIndex); 519 int n = toIndex - fromIndex, p, g; 520 if (n <= MIN_ARRAY_SORT_GRAN || 521 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 522 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); 523 else 524 new ArraysParallelSortHelpers.FJByte.Sorter 525 (null, a, new byte[n], fromIndex, n, 0, 526 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 527 MIN_ARRAY_SORT_GRAN : g).invoke(); 528 } 529 530 /** 531 * Sorts the specified array into ascending numerical order. 532 * 533 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 534 * array into sub-arrays that are themselves sorted and then merged. When 535 * the sub-array length reaches a minimum granularity, the sub-array is 536 * sorted using the appropriate {@link Arrays#sort(char[]) Arrays.sort} 537 * method. If the length of the specified array is less than the minimum 538 * granularity, then it is sorted using the appropriate {@link 539 * Arrays#sort(char[]) Arrays.sort} method. The algorithm requires a 540 * working space no greater than the size of the original array. The 541 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to 542 * execute any parallel tasks. 543 * 544 * @param a the array to be sorted 545 * 546 * @since 1.8 547 */ 548 public static void parallelSort(char[] a) { 549 int n = a.length, p, g; 550 if (n <= MIN_ARRAY_SORT_GRAN || 551 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 552 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); 553 else 554 new ArraysParallelSortHelpers.FJChar.Sorter 555 (null, a, new char[n], 0, n, 0, 556 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 557 MIN_ARRAY_SORT_GRAN : g).invoke(); 558 } 559 560 /** 561 * Sorts the specified range of the array into ascending numerical order. 562 * The range to be sorted extends from the index {@code fromIndex}, 563 * inclusive, to the index {@code toIndex}, exclusive. If 564 * {@code fromIndex == toIndex}, the range to be sorted is empty. 565 * 566 @implNote The sorting algorithm is a parallel sort-merge that breaks the 567 * array into sub-arrays that are themselves sorted and then merged. When 568 * the sub-array length reaches a minimum granularity, the sub-array is 569 * sorted using the appropriate {@link Arrays#sort(char[]) Arrays.sort} 570 * method. If the length of the specified array is less than the minimum 571 * granularity, then it is sorted using the appropriate {@link 572 * Arrays#sort(char[]) Arrays.sort} method. The algorithm requires a working 573 * space no greater than the size of the specified range of the original 574 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is 575 * used to execute any parallel tasks. 576 * 577 * @param a the array to be sorted 578 * @param fromIndex the index of the first element, inclusive, to be sorted 579 * @param toIndex the index of the last element, exclusive, to be sorted 580 * 581 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 582 * @throws ArrayIndexOutOfBoundsException 583 * if {@code fromIndex < 0} or {@code toIndex > a.length} 584 * 585 * @since 1.8 586 */ 587 public static void parallelSort(char[] a, int fromIndex, int toIndex) { 588 rangeCheck(a.length, fromIndex, toIndex); 589 int n = toIndex - fromIndex, p, g; 590 if (n <= MIN_ARRAY_SORT_GRAN || 591 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 592 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); 593 else 594 new ArraysParallelSortHelpers.FJChar.Sorter 595 (null, a, new char[n], fromIndex, n, 0, 596 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 597 MIN_ARRAY_SORT_GRAN : g).invoke(); 598 } 599 600 /** 601 * Sorts the specified array into ascending numerical order. 602 * 603 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 604 * array into sub-arrays that are themselves sorted and then merged. When 605 * the sub-array length reaches a minimum granularity, the sub-array is 606 * sorted using the appropriate {@link Arrays#sort(short[]) Arrays.sort} 607 * method. If the length of the specified array is less than the minimum 608 * granularity, then it is sorted using the appropriate {@link 609 * Arrays#sort(short[]) Arrays.sort} method. The algorithm requires a 610 * working space no greater than the size of the original array. The 611 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to 612 * execute any parallel tasks. 613 * 614 * @param a the array to be sorted 615 * 616 * @since 1.8 617 */ 618 public static void parallelSort(short[] a) { 619 int n = a.length, p, g; 620 if (n <= MIN_ARRAY_SORT_GRAN || 621 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 622 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); 623 else 624 new ArraysParallelSortHelpers.FJShort.Sorter 625 (null, a, new short[n], 0, n, 0, 626 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 627 MIN_ARRAY_SORT_GRAN : g).invoke(); 628 } 629 630 /** 631 * Sorts the specified range of the array into ascending numerical order. 632 * The range to be sorted extends from the index {@code fromIndex}, 633 * inclusive, to the index {@code toIndex}, exclusive. If 634 * {@code fromIndex == toIndex}, the range to be sorted is empty. 635 * 636 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 637 * array into sub-arrays that are themselves sorted and then merged. When 638 * the sub-array length reaches a minimum granularity, the sub-array is 639 * sorted using the appropriate {@link Arrays#sort(short[]) Arrays.sort} 640 * method. If the length of the specified array is less than the minimum 641 * granularity, then it is sorted using the appropriate {@link 642 * Arrays#sort(short[]) Arrays.sort} method. The algorithm requires a working 643 * space no greater than the size of the specified range of the original 644 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is 645 * used to execute any parallel tasks. 646 * 647 * @param a the array to be sorted 648 * @param fromIndex the index of the first element, inclusive, to be sorted 649 * @param toIndex the index of the last element, exclusive, to be sorted 650 * 651 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 652 * @throws ArrayIndexOutOfBoundsException 653 * if {@code fromIndex < 0} or {@code toIndex > a.length} 654 * 655 * @since 1.8 656 */ 657 public static void parallelSort(short[] a, int fromIndex, int toIndex) { 658 rangeCheck(a.length, fromIndex, toIndex); 659 int n = toIndex - fromIndex, p, g; 660 if (n <= MIN_ARRAY_SORT_GRAN || 661 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 662 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); 663 else 664 new ArraysParallelSortHelpers.FJShort.Sorter 665 (null, a, new short[n], fromIndex, n, 0, 666 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 667 MIN_ARRAY_SORT_GRAN : g).invoke(); 668 } 669 670 /** 671 * Sorts the specified array into ascending numerical order. 672 * 673 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 674 * array into sub-arrays that are themselves sorted and then merged. When 675 * the sub-array length reaches a minimum granularity, the sub-array is 676 * sorted using the appropriate {@link Arrays#sort(int[]) Arrays.sort} 677 * method. If the length of the specified array is less than the minimum 678 * granularity, then it is sorted using the appropriate {@link 679 * Arrays#sort(int[]) Arrays.sort} method. The algorithm requires a 680 * working space no greater than the size of the original array. The 681 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to 682 * execute any parallel tasks. 683 * 684 * @param a the array to be sorted 685 * 686 * @since 1.8 687 */ 688 public static void parallelSort(int[] a) { 689 int n = a.length, p, g; 690 if (n <= MIN_ARRAY_SORT_GRAN || 691 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 692 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); 693 else 694 new ArraysParallelSortHelpers.FJInt.Sorter 695 (null, a, new int[n], 0, n, 0, 696 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 697 MIN_ARRAY_SORT_GRAN : g).invoke(); 698 } 699 700 /** 701 * Sorts the specified range of the array into ascending numerical order. 702 * The range to be sorted extends from the index {@code fromIndex}, 703 * inclusive, to the index {@code toIndex}, exclusive. If 704 * {@code fromIndex == toIndex}, the range to be sorted is empty. 705 * 706 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 707 * array into sub-arrays that are themselves sorted and then merged. When 708 * the sub-array length reaches a minimum granularity, the sub-array is 709 * sorted using the appropriate {@link Arrays#sort(int[]) Arrays.sort} 710 * method. If the length of the specified array is less than the minimum 711 * granularity, then it is sorted using the appropriate {@link 712 * Arrays#sort(int[]) Arrays.sort} method. The algorithm requires a working 713 * space no greater than the size of the specified range of the original 714 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is 715 * used to execute any parallel tasks. 716 * 717 * @param a the array to be sorted 718 * @param fromIndex the index of the first element, inclusive, to be sorted 719 * @param toIndex the index of the last element, exclusive, to be sorted 720 * 721 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 722 * @throws ArrayIndexOutOfBoundsException 723 * if {@code fromIndex < 0} or {@code toIndex > a.length} 724 * 725 * @since 1.8 726 */ 727 public static void parallelSort(int[] a, int fromIndex, int toIndex) { 728 rangeCheck(a.length, fromIndex, toIndex); 729 int n = toIndex - fromIndex, p, g; 730 if (n <= MIN_ARRAY_SORT_GRAN || 731 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 732 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); 733 else 734 new ArraysParallelSortHelpers.FJInt.Sorter 735 (null, a, new int[n], fromIndex, n, 0, 736 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 737 MIN_ARRAY_SORT_GRAN : g).invoke(); 738 } 739 740 /** 741 * Sorts the specified array into ascending numerical order. 742 * 743 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 744 * array into sub-arrays that are themselves sorted and then merged. When 745 * the sub-array length reaches a minimum granularity, the sub-array is 746 * sorted using the appropriate {@link Arrays#sort(long[]) Arrays.sort} 747 * method. If the length of the specified array is less than the minimum 748 * granularity, then it is sorted using the appropriate {@link 749 * Arrays#sort(long[]) Arrays.sort} method. The algorithm requires a 750 * working space no greater than the size of the original array. The 751 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to 752 * execute any parallel tasks. 753 * 754 * @param a the array to be sorted 755 * 756 * @since 1.8 757 */ 758 public static void parallelSort(long[] a) { 759 int n = a.length, p, g; 760 if (n <= MIN_ARRAY_SORT_GRAN || 761 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 762 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); 763 else 764 new ArraysParallelSortHelpers.FJLong.Sorter 765 (null, a, new long[n], 0, n, 0, 766 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 767 MIN_ARRAY_SORT_GRAN : g).invoke(); 768 } 769 770 /** 771 * Sorts the specified range of the array into ascending numerical order. 772 * The range to be sorted extends from the index {@code fromIndex}, 773 * inclusive, to the index {@code toIndex}, exclusive. If 774 * {@code fromIndex == toIndex}, the range to be sorted is empty. 775 * 776 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 777 * array into sub-arrays that are themselves sorted and then merged. When 778 * the sub-array length reaches a minimum granularity, the sub-array is 779 * sorted using the appropriate {@link Arrays#sort(long[]) Arrays.sort} 780 * method. If the length of the specified array is less than the minimum 781 * granularity, then it is sorted using the appropriate {@link 782 * Arrays#sort(long[]) Arrays.sort} method. The algorithm requires a working 783 * space no greater than the size of the specified range of the original 784 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is 785 * used to execute any parallel tasks. 786 * 787 * @param a the array to be sorted 788 * @param fromIndex the index of the first element, inclusive, to be sorted 789 * @param toIndex the index of the last element, exclusive, to be sorted 790 * 791 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 792 * @throws ArrayIndexOutOfBoundsException 793 * if {@code fromIndex < 0} or {@code toIndex > a.length} 794 * 795 * @since 1.8 796 */ 797 public static void parallelSort(long[] a, int fromIndex, int toIndex) { 798 rangeCheck(a.length, fromIndex, toIndex); 799 int n = toIndex - fromIndex, p, g; 800 if (n <= MIN_ARRAY_SORT_GRAN || 801 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 802 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); 803 else 804 new ArraysParallelSortHelpers.FJLong.Sorter 805 (null, a, new long[n], fromIndex, n, 0, 806 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 807 MIN_ARRAY_SORT_GRAN : g).invoke(); 808 } 809 810 /** 811 * Sorts the specified array into ascending numerical order. 812 * 813 * <p>The {@code <} relation does not provide a total order on all float 814 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN} 815 * value compares neither less than, greater than, nor equal to any value, 816 * even itself. This method uses the total order imposed by the method 817 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value 818 * {@code 0.0f} and {@code Float.NaN} is considered greater than any 819 * other value and all {@code Float.NaN} values are considered equal. 820 * 821 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 822 * array into sub-arrays that are themselves sorted and then merged. When 823 * the sub-array length reaches a minimum granularity, the sub-array is 824 * sorted using the appropriate {@link Arrays#sort(float[]) Arrays.sort} 825 * method. If the length of the specified array is less than the minimum 826 * granularity, then it is sorted using the appropriate {@link 827 * Arrays#sort(float[]) Arrays.sort} method. The algorithm requires a 828 * working space no greater than the size of the original array. The 829 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to 830 * execute any parallel tasks. 831 * 832 * @param a the array to be sorted 833 * 834 * @since 1.8 835 */ 836 public static void parallelSort(float[] a) { 837 int n = a.length, p, g; 838 if (n <= MIN_ARRAY_SORT_GRAN || 839 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 840 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); 841 else 842 new ArraysParallelSortHelpers.FJFloat.Sorter 843 (null, a, new float[n], 0, n, 0, 844 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 845 MIN_ARRAY_SORT_GRAN : g).invoke(); 846 } 847 848 /** 849 * Sorts the specified range of the array into ascending numerical order. 850 * The range to be sorted extends from the index {@code fromIndex}, 851 * inclusive, to the index {@code toIndex}, exclusive. If 852 * {@code fromIndex == toIndex}, the range to be sorted is empty. 853 * 854 * <p>The {@code <} relation does not provide a total order on all float 855 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN} 856 * value compares neither less than, greater than, nor equal to any value, 857 * even itself. This method uses the total order imposed by the method 858 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value 859 * {@code 0.0f} and {@code Float.NaN} is considered greater than any 860 * other value and all {@code Float.NaN} values are considered equal. 861 * 862 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 863 * array into sub-arrays that are themselves sorted and then merged. When 864 * the sub-array length reaches a minimum granularity, the sub-array is 865 * sorted using the appropriate {@link Arrays#sort(float[]) Arrays.sort} 866 * method. If the length of the specified array is less than the minimum 867 * granularity, then it is sorted using the appropriate {@link 868 * Arrays#sort(float[]) Arrays.sort} method. The algorithm requires a working 869 * space no greater than the size of the specified range of the original 870 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is 871 * used to execute any parallel tasks. 872 * 873 * @param a the array to be sorted 874 * @param fromIndex the index of the first element, inclusive, to be sorted 875 * @param toIndex the index of the last element, exclusive, to be sorted 876 * 877 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 878 * @throws ArrayIndexOutOfBoundsException 879 * if {@code fromIndex < 0} or {@code toIndex > a.length} 880 * 881 * @since 1.8 882 */ 883 public static void parallelSort(float[] a, int fromIndex, int toIndex) { 884 rangeCheck(a.length, fromIndex, toIndex); 885 int n = toIndex - fromIndex, p, g; 886 if (n <= MIN_ARRAY_SORT_GRAN || 887 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 888 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); 889 else 890 new ArraysParallelSortHelpers.FJFloat.Sorter 891 (null, a, new float[n], fromIndex, n, 0, 892 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 893 MIN_ARRAY_SORT_GRAN : g).invoke(); 894 } 895 896 /** 897 * Sorts the specified array into ascending numerical order. 898 * 899 * <p>The {@code <} relation does not provide a total order on all double 900 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN} 901 * value compares neither less than, greater than, nor equal to any value, 902 * even itself. This method uses the total order imposed by the method 903 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value 904 * {@code 0.0d} and {@code Double.NaN} is considered greater than any 905 * other value and all {@code Double.NaN} values are considered equal. 906 * 907 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 908 * array into sub-arrays that are themselves sorted and then merged. When 909 * the sub-array length reaches a minimum granularity, the sub-array is 910 * sorted using the appropriate {@link Arrays#sort(double[]) Arrays.sort} 911 * method. If the length of the specified array is less than the minimum 912 * granularity, then it is sorted using the appropriate {@link 913 * Arrays#sort(double[]) Arrays.sort} method. The algorithm requires a 914 * working space no greater than the size of the original array. The 915 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to 916 * execute any parallel tasks. 917 * 918 * @param a the array to be sorted 919 * 920 * @since 1.8 921 */ 922 public static void parallelSort(double[] a) { 923 int n = a.length, p, g; 924 if (n <= MIN_ARRAY_SORT_GRAN || 925 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 926 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0); 927 else 928 new ArraysParallelSortHelpers.FJDouble.Sorter 929 (null, a, new double[n], 0, n, 0, 930 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 931 MIN_ARRAY_SORT_GRAN : g).invoke(); 932 } 933 934 /** 935 * Sorts the specified range of the array into ascending numerical order. 936 * The range to be sorted extends from the index {@code fromIndex}, 937 * inclusive, to the index {@code toIndex}, exclusive. If 938 * {@code fromIndex == toIndex}, the range to be sorted is empty. 939 * 940 * <p>The {@code <} relation does not provide a total order on all double 941 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN} 942 * value compares neither less than, greater than, nor equal to any value, 943 * even itself. This method uses the total order imposed by the method 944 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value 945 * {@code 0.0d} and {@code Double.NaN} is considered greater than any 946 * other value and all {@code Double.NaN} values are considered equal. 947 * 948 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 949 * array into sub-arrays that are themselves sorted and then merged. When 950 * the sub-array length reaches a minimum granularity, the sub-array is 951 * sorted using the appropriate {@link Arrays#sort(double[]) Arrays.sort} 952 * method. If the length of the specified array is less than the minimum 953 * granularity, then it is sorted using the appropriate {@link 954 * Arrays#sort(double[]) Arrays.sort} method. The algorithm requires a working 955 * space no greater than the size of the specified range of the original 956 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is 957 * used to execute any parallel tasks. 958 * 959 * @param a the array to be sorted 960 * @param fromIndex the index of the first element, inclusive, to be sorted 961 * @param toIndex the index of the last element, exclusive, to be sorted 962 * 963 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 964 * @throws ArrayIndexOutOfBoundsException 965 * if {@code fromIndex < 0} or {@code toIndex > a.length} 966 * 967 * @since 1.8 968 */ 969 public static void parallelSort(double[] a, int fromIndex, int toIndex) { 970 rangeCheck(a.length, fromIndex, toIndex); 971 int n = toIndex - fromIndex, p, g; 972 if (n <= MIN_ARRAY_SORT_GRAN || 973 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 974 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0); 975 else 976 new ArraysParallelSortHelpers.FJDouble.Sorter 977 (null, a, new double[n], fromIndex, n, 0, 978 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 979 MIN_ARRAY_SORT_GRAN : g).invoke(); 980 } 981 982 /** 983 * Sorts the specified array of objects into ascending order, according 984 * to the {@linkplain Comparable natural ordering} of its elements. 985 * All elements in the array must implement the {@link Comparable} 986 * interface. Furthermore, all elements in the array must be 987 * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must 988 * not throw a {@code ClassCastException} for any elements {@code e1} 989 * and {@code e2} in the array). 990 * 991 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 992 * not be reordered as a result of the sort. 993 * 994 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 995 * array into sub-arrays that are themselves sorted and then merged. When 996 * the sub-array length reaches a minimum granularity, the sub-array is 997 * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort} 998 * method. If the length of the specified array is less than the minimum 999 * granularity, then it is sorted using the appropriate {@link 1000 * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a 1001 * working space no greater than the size of the original array. The 1002 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to 1003 * execute any parallel tasks. 1004 * 1005 * @param <T> the class of the objects to be sorted 1006 * @param a the array to be sorted 1007 * 1008 * @throws ClassCastException if the array contains elements that are not 1009 * <i>mutually comparable</i> (for example, strings and integers) 1010 * @throws IllegalArgumentException (optional) if the natural 1011 * ordering of the array elements is found to violate the 1012 * {@link Comparable} contract 1013 * 1014 * @since 1.8 1015 */ 1016 @SuppressWarnings("unchecked") 1017 public static <T extends Comparable<? super T>> void parallelSort(T[] a) { 1018 int n = a.length, p, g; 1019 if (n <= MIN_ARRAY_SORT_GRAN || 1020 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 1021 TimSort.sort(a, 0, n, NaturalOrder.INSTANCE, null, 0, 0); 1022 else 1023 new ArraysParallelSortHelpers.FJObject.Sorter<T> 1024 (null, a, 1025 (T[])Array.newInstance(a.getClass().getComponentType(), n), 1026 0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 1027 MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke(); 1028 } 1029 1030 /** 1031 * Sorts the specified range of the specified array of objects into 1032 * ascending order, according to the 1033 * {@linkplain Comparable natural ordering} of its 1034 * elements. The range to be sorted extends from index 1035 * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive. 1036 * (If {@code fromIndex==toIndex}, the range to be sorted is empty.) All 1037 * elements in this range must implement the {@link Comparable} 1038 * interface. Furthermore, all elements in this range must be <i>mutually 1039 * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a 1040 * {@code ClassCastException} for any elements {@code e1} and 1041 * {@code e2} in the array). 1042 * 1043 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 1044 * not be reordered as a result of the sort. 1045 * 1046 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 1047 * array into sub-arrays that are themselves sorted and then merged. When 1048 * the sub-array length reaches a minimum granularity, the sub-array is 1049 * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort} 1050 * method. If the length of the specified array is less than the minimum 1051 * granularity, then it is sorted using the appropriate {@link 1052 * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a working 1053 * space no greater than the size of the specified range of the original 1054 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is 1055 * used to execute any parallel tasks. 1056 * 1057 * @param <T> the class of the objects to be sorted 1058 * @param a the array to be sorted 1059 * @param fromIndex the index of the first element (inclusive) to be 1060 * sorted 1061 * @param toIndex the index of the last element (exclusive) to be sorted 1062 * @throws IllegalArgumentException if {@code fromIndex > toIndex} or 1063 * (optional) if the natural ordering of the array elements is 1064 * found to violate the {@link Comparable} contract 1065 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or 1066 * {@code toIndex > a.length} 1067 * @throws ClassCastException if the array contains elements that are 1068 * not <i>mutually comparable</i> (for example, strings and 1069 * integers). 1070 * 1071 * @since 1.8 1072 */ 1073 @SuppressWarnings("unchecked") 1074 public static <T extends Comparable<? super T>> 1075 void parallelSort(T[] a, int fromIndex, int toIndex) { 1076 rangeCheck(a.length, fromIndex, toIndex); 1077 int n = toIndex - fromIndex, p, g; 1078 if (n <= MIN_ARRAY_SORT_GRAN || 1079 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 1080 TimSort.sort(a, fromIndex, toIndex, NaturalOrder.INSTANCE, null, 0, 0); 1081 else 1082 new ArraysParallelSortHelpers.FJObject.Sorter<T> 1083 (null, a, 1084 (T[])Array.newInstance(a.getClass().getComponentType(), n), 1085 fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 1086 MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke(); 1087 } 1088 1089 /** 1090 * Sorts the specified array of objects according to the order induced by 1091 * the specified comparator. All elements in the array must be 1092 * <i>mutually comparable</i> by the specified comparator (that is, 1093 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} 1094 * for any elements {@code e1} and {@code e2} in the array). 1095 * 1096 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 1097 * not be reordered as a result of the sort. 1098 * 1099 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 1100 * array into sub-arrays that are themselves sorted and then merged. When 1101 * the sub-array length reaches a minimum granularity, the sub-array is 1102 * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort} 1103 * method. If the length of the specified array is less than the minimum 1104 * granularity, then it is sorted using the appropriate {@link 1105 * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a 1106 * working space no greater than the size of the original array. The 1107 * {@link ForkJoinPool#commonPool() ForkJoin common pool} is used to 1108 * execute any parallel tasks. 1109 * 1110 * @param <T> the class of the objects to be sorted 1111 * @param a the array to be sorted 1112 * @param cmp the comparator to determine the order of the array. A 1113 * {@code null} value indicates that the elements' 1114 * {@linkplain Comparable natural ordering} should be used. 1115 * @throws ClassCastException if the array contains elements that are 1116 * not <i>mutually comparable</i> using the specified comparator 1117 * @throws IllegalArgumentException (optional) if the comparator is 1118 * found to violate the {@link java.util.Comparator} contract 1119 * 1120 * @since 1.8 1121 */ 1122 @SuppressWarnings("unchecked") 1123 public static <T> void parallelSort(T[] a, Comparator<? super T> cmp) { 1124 if (cmp == null) 1125 cmp = NaturalOrder.INSTANCE; 1126 int n = a.length, p, g; 1127 if (n <= MIN_ARRAY_SORT_GRAN || 1128 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 1129 TimSort.sort(a, 0, n, cmp, null, 0, 0); 1130 else 1131 new ArraysParallelSortHelpers.FJObject.Sorter<T> 1132 (null, a, 1133 (T[])Array.newInstance(a.getClass().getComponentType(), n), 1134 0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 1135 MIN_ARRAY_SORT_GRAN : g, cmp).invoke(); 1136 } 1137 1138 /** 1139 * Sorts the specified range of the specified array of objects according 1140 * to the order induced by the specified comparator. The range to be 1141 * sorted extends from index {@code fromIndex}, inclusive, to index 1142 * {@code toIndex}, exclusive. (If {@code fromIndex==toIndex}, the 1143 * range to be sorted is empty.) All elements in the range must be 1144 * <i>mutually comparable</i> by the specified comparator (that is, 1145 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} 1146 * for any elements {@code e1} and {@code e2} in the range). 1147 * 1148 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 1149 * not be reordered as a result of the sort. 1150 * 1151 * @implNote The sorting algorithm is a parallel sort-merge that breaks the 1152 * array into sub-arrays that are themselves sorted and then merged. When 1153 * the sub-array length reaches a minimum granularity, the sub-array is 1154 * sorted using the appropriate {@link Arrays#sort(Object[]) Arrays.sort} 1155 * method. If the length of the specified array is less than the minimum 1156 * granularity, then it is sorted using the appropriate {@link 1157 * Arrays#sort(Object[]) Arrays.sort} method. The algorithm requires a working 1158 * space no greater than the size of the specified range of the original 1159 * array. The {@link ForkJoinPool#commonPool() ForkJoin common pool} is 1160 * used to execute any parallel tasks. 1161 * 1162 * @param <T> the class of the objects to be sorted 1163 * @param a the array to be sorted 1164 * @param fromIndex the index of the first element (inclusive) to be 1165 * sorted 1166 * @param toIndex the index of the last element (exclusive) to be sorted 1167 * @param cmp the comparator to determine the order of the array. A 1168 * {@code null} value indicates that the elements' 1169 * {@linkplain Comparable natural ordering} should be used. 1170 * @throws IllegalArgumentException if {@code fromIndex > toIndex} or 1171 * (optional) if the natural ordering of the array elements is 1172 * found to violate the {@link Comparable} contract 1173 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or 1174 * {@code toIndex > a.length} 1175 * @throws ClassCastException if the array contains elements that are 1176 * not <i>mutually comparable</i> (for example, strings and 1177 * integers). 1178 * 1179 * @since 1.8 1180 */ 1181 @SuppressWarnings("unchecked") 1182 public static <T> void parallelSort(T[] a, int fromIndex, int toIndex, 1183 Comparator<? super T> cmp) { 1184 rangeCheck(a.length, fromIndex, toIndex); 1185 if (cmp == null) 1186 cmp = NaturalOrder.INSTANCE; 1187 int n = toIndex - fromIndex, p, g; 1188 if (n <= MIN_ARRAY_SORT_GRAN || 1189 (p = ForkJoinPool.getCommonPoolParallelism()) == 1) 1190 TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0); 1191 else 1192 new ArraysParallelSortHelpers.FJObject.Sorter<T> 1193 (null, a, 1194 (T[])Array.newInstance(a.getClass().getComponentType(), n), 1195 fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ? 1196 MIN_ARRAY_SORT_GRAN : g, cmp).invoke(); 1197 } 1198 1199 /* 1200 * Sorting of complex type arrays. 1201 */ 1202 1203 /** 1204 * Sorts the specified array of objects into ascending order, according 1205 * to the {@linkplain Comparable natural ordering} of its elements. 1206 * All elements in the array must implement the {@link Comparable} 1207 * interface. Furthermore, all elements in the array must be 1208 * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must 1209 * not throw a {@code ClassCastException} for any elements {@code e1} 1210 * and {@code e2} in the array). 1211 * 1212 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 1213 * not be reordered as a result of the sort. 1214 * 1215 * <p>Implementation note: This implementation is a stable, adaptive, 1216 * iterative mergesort that requires far fewer than n lg(n) comparisons 1217 * when the input array is partially sorted, while offering the 1218 * performance of a traditional mergesort when the input array is 1219 * randomly ordered. If the input array is nearly sorted, the 1220 * implementation requires approximately n comparisons. Temporary 1221 * storage requirements vary from a small constant for nearly sorted 1222 * input arrays to n/2 object references for randomly ordered input 1223 * arrays. 1224 * 1225 * <p>The implementation takes equal advantage of ascending and 1226 * descending order in its input array, and can take advantage of 1227 * ascending and descending order in different parts of the the same 1228 * input array. It is well-suited to merging two or more sorted arrays: 1229 * simply concatenate the arrays and sort the resulting array. 1230 * 1231 * <p>The implementation was adapted from Tim Peters's list sort for Python 1232 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> 1233 * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic 1234 * Sorting and Information Theoretic Complexity", in Proceedings of the 1235 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, 1236 * January 1993. 1237 * 1238 * @param a the array to be sorted 1239 * @throws ClassCastException if the array contains elements that are not 1240 * <i>mutually comparable</i> (for example, strings and integers) 1241 * @throws IllegalArgumentException (optional) if the natural 1242 * ordering of the array elements is found to violate the 1243 * {@link Comparable} contract 1244 */ 1245 public static void sort(Object[] a) { 1246 // Android-changed: LegacyMergeSort is no longer supported 1247 // if (LegacyMergeSort.userRequested) 1248 // legacyMergeSort(a); 1249 // else 1250 ComparableTimSort.sort(a, 0, a.length, null, 0, 0); 1251 } 1252 1253 /** 1254 * Sorts the specified range of the specified array of objects into 1255 * ascending order, according to the 1256 * {@linkplain Comparable natural ordering} of its 1257 * elements. The range to be sorted extends from index 1258 * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive. 1259 * (If {@code fromIndex==toIndex}, the range to be sorted is empty.) All 1260 * elements in this range must implement the {@link Comparable} 1261 * interface. Furthermore, all elements in this range must be <i>mutually 1262 * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a 1263 * {@code ClassCastException} for any elements {@code e1} and 1264 * {@code e2} in the array). 1265 * 1266 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 1267 * not be reordered as a result of the sort. 1268 * 1269 * <p>Implementation note: This implementation is a stable, adaptive, 1270 * iterative mergesort that requires far fewer than n lg(n) comparisons 1271 * when the input array is partially sorted, while offering the 1272 * performance of a traditional mergesort when the input array is 1273 * randomly ordered. If the input array is nearly sorted, the 1274 * implementation requires approximately n comparisons. Temporary 1275 * storage requirements vary from a small constant for nearly sorted 1276 * input arrays to n/2 object references for randomly ordered input 1277 * arrays. 1278 * 1279 * <p>The implementation takes equal advantage of ascending and 1280 * descending order in its input array, and can take advantage of 1281 * ascending and descending order in different parts of the the same 1282 * input array. It is well-suited to merging two or more sorted arrays: 1283 * simply concatenate the arrays and sort the resulting array. 1284 * 1285 * <p>The implementation was adapted from Tim Peters's list sort for Python 1286 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> 1287 * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic 1288 * Sorting and Information Theoretic Complexity", in Proceedings of the 1289 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, 1290 * January 1993. 1291 * 1292 * @param a the array to be sorted 1293 * @param fromIndex the index of the first element (inclusive) to be 1294 * sorted 1295 * @param toIndex the index of the last element (exclusive) to be sorted 1296 * @throws IllegalArgumentException if {@code fromIndex > toIndex} or 1297 * (optional) if the natural ordering of the array elements is 1298 * found to violate the {@link Comparable} contract 1299 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or 1300 * {@code toIndex > a.length} 1301 * @throws ClassCastException if the array contains elements that are 1302 * not <i>mutually comparable</i> (for example, strings and 1303 * integers). 1304 */ 1305 public static void sort(Object[] a, int fromIndex, int toIndex) { 1306 rangeCheck(a.length, fromIndex, toIndex); 1307 // Android-changed: LegacyMergeSort is no longer supported 1308 // if (LegacyMergeSort.userRequested) 1309 // legacyMergeSort(a, fromIndex, toIndex); 1310 // else 1311 ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0); 1312 } 1313 1314 /** 1315 * Tuning parameter: list size at or below which insertion sort will be 1316 * used in preference to mergesort. 1317 * To be removed in a future release. 1318 */ 1319 private static final int INSERTIONSORT_THRESHOLD = 7; 1320 1321 /** 1322 * Src is the source array that starts at index 0 1323 * Dest is the (possibly larger) array destination with a possible offset 1324 * low is the index in dest to start sorting 1325 * high is the end index in dest to end sorting 1326 * off is the offset to generate corresponding low, high in src 1327 * To be removed in a future release. 1328 */ 1329 @SuppressWarnings({"unchecked", "rawtypes"}) 1330 private static void mergeSort(Object[] src, 1331 Object[] dest, 1332 int low, 1333 int high, 1334 int off) { 1335 int length = high - low; 1336 1337 // Insertion sort on smallest arrays 1338 if (length < INSERTIONSORT_THRESHOLD) { 1339 for (int i=low; i<high; i++) 1340 for (int j=i; j>low && 1341 ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--) 1342 swap(dest, j, j-1); 1343 return; 1344 } 1345 1346 // Recursively sort halves of dest into src 1347 int destLow = low; 1348 int destHigh = high; 1349 low += off; 1350 high += off; 1351 int mid = (low + high) >>> 1; 1352 mergeSort(dest, src, low, mid, -off); 1353 mergeSort(dest, src, mid, high, -off); 1354 1355 // If list is already sorted, just copy from src to dest. This is an 1356 // optimization that results in faster sorts for nearly ordered lists. 1357 if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) { 1358 System.arraycopy(src, low, dest, destLow, length); 1359 return; 1360 } 1361 1362 // Merge sorted halves (now in src) into dest 1363 for(int i = destLow, p = low, q = mid; i < destHigh; i++) { 1364 if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0) 1365 dest[i] = src[p++]; 1366 else 1367 dest[i] = src[q++]; 1368 } 1369 } 1370 1371 /** 1372 * Swaps x[a] with x[b]. 1373 */ 1374 private static void swap(Object[] x, int a, int b) { 1375 Object t = x[a]; 1376 x[a] = x[b]; 1377 x[b] = t; 1378 } 1379 1380 /** 1381 * Sorts the specified array of objects according to the order induced by 1382 * the specified comparator. All elements in the array must be 1383 * <i>mutually comparable</i> by the specified comparator (that is, 1384 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} 1385 * for any elements {@code e1} and {@code e2} in the array). 1386 * 1387 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 1388 * not be reordered as a result of the sort. 1389 * 1390 * <p>Implementation note: This implementation is a stable, adaptive, 1391 * iterative mergesort that requires far fewer than n lg(n) comparisons 1392 * when the input array is partially sorted, while offering the 1393 * performance of a traditional mergesort when the input array is 1394 * randomly ordered. If the input array is nearly sorted, the 1395 * implementation requires approximately n comparisons. Temporary 1396 * storage requirements vary from a small constant for nearly sorted 1397 * input arrays to n/2 object references for randomly ordered input 1398 * arrays. 1399 * 1400 * <p>The implementation takes equal advantage of ascending and 1401 * descending order in its input array, and can take advantage of 1402 * ascending and descending order in different parts of the the same 1403 * input array. It is well-suited to merging two or more sorted arrays: 1404 * simply concatenate the arrays and sort the resulting array. 1405 * 1406 * <p>The implementation was adapted from Tim Peters's list sort for Python 1407 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> 1408 * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic 1409 * Sorting and Information Theoretic Complexity", in Proceedings of the 1410 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, 1411 * January 1993. 1412 * 1413 * @param <T> the class of the objects to be sorted 1414 * @param a the array to be sorted 1415 * @param c the comparator to determine the order of the array. A 1416 * {@code null} value indicates that the elements' 1417 * {@linkplain Comparable natural ordering} should be used. 1418 * @throws ClassCastException if the array contains elements that are 1419 * not <i>mutually comparable</i> using the specified comparator 1420 * @throws IllegalArgumentException (optional) if the comparator is 1421 * found to violate the {@link Comparator} contract 1422 */ 1423 public static <T> void sort(T[] a, Comparator<? super T> c) { 1424 if (c == null) { 1425 sort(a); 1426 } else { 1427 // Android-changed: LegacyMergeSort is no longer supported 1428 // if (LegacyMergeSort.userRequested) 1429 // legacyMergeSort(a, c); 1430 // else 1431 TimSort.sort(a, 0, a.length, c, null, 0, 0); 1432 } 1433 } 1434 1435 /** 1436 * Sorts the specified range of the specified array of objects according 1437 * to the order induced by the specified comparator. The range to be 1438 * sorted extends from index {@code fromIndex}, inclusive, to index 1439 * {@code toIndex}, exclusive. (If {@code fromIndex==toIndex}, the 1440 * range to be sorted is empty.) All elements in the range must be 1441 * <i>mutually comparable</i> by the specified comparator (that is, 1442 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} 1443 * for any elements {@code e1} and {@code e2} in the range). 1444 * 1445 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 1446 * not be reordered as a result of the sort. 1447 * 1448 * <p>Implementation note: This implementation is a stable, adaptive, 1449 * iterative mergesort that requires far fewer than n lg(n) comparisons 1450 * when the input array is partially sorted, while offering the 1451 * performance of a traditional mergesort when the input array is 1452 * randomly ordered. If the input array is nearly sorted, the 1453 * implementation requires approximately n comparisons. Temporary 1454 * storage requirements vary from a small constant for nearly sorted 1455 * input arrays to n/2 object references for randomly ordered input 1456 * arrays. 1457 * 1458 * <p>The implementation takes equal advantage of ascending and 1459 * descending order in its input array, and can take advantage of 1460 * ascending and descending order in different parts of the the same 1461 * input array. It is well-suited to merging two or more sorted arrays: 1462 * simply concatenate the arrays and sort the resulting array. 1463 * 1464 * <p>The implementation was adapted from Tim Peters's list sort for Python 1465 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> 1466 * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic 1467 * Sorting and Information Theoretic Complexity", in Proceedings of the 1468 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, 1469 * January 1993. 1470 * 1471 * @param <T> the class of the objects to be sorted 1472 * @param a the array to be sorted 1473 * @param fromIndex the index of the first element (inclusive) to be 1474 * sorted 1475 * @param toIndex the index of the last element (exclusive) to be sorted 1476 * @param c the comparator to determine the order of the array. A 1477 * {@code null} value indicates that the elements' 1478 * {@linkplain Comparable natural ordering} should be used. 1479 * @throws ClassCastException if the array contains elements that are not 1480 * <i>mutually comparable</i> using the specified comparator. 1481 * @throws IllegalArgumentException if {@code fromIndex > toIndex} or 1482 * (optional) if the comparator is found to violate the 1483 * {@link Comparator} contract 1484 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or 1485 * {@code toIndex > a.length} 1486 */ 1487 public static <T> void sort(T[] a, int fromIndex, int toIndex, 1488 Comparator<? super T> c) { 1489 if (c == null) { 1490 sort(a, fromIndex, toIndex); 1491 } else { 1492 rangeCheck(a.length, fromIndex, toIndex); 1493 // Android-changed: LegacyMergeSort is no longer supported 1494 // if (LegacyMergeSort.userRequested) 1495 // legacyMergeSort(a, fromIndex, toIndex, c); 1496 // else 1497 TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0); 1498 } 1499 } 1500 1501 // Parallel prefix 1502 1503 /** 1504 * Cumulates, in parallel, each element of the given array in place, 1505 * using the supplied function. For example if the array initially 1506 * holds {@code [2, 1, 0, 3]} and the operation performs addition, 1507 * then upon return the array holds {@code [2, 3, 3, 6]}. 1508 * Parallel prefix computation is usually more efficient than 1509 * sequential loops for large arrays. 1510 * 1511 * @param <T> the class of the objects in the array 1512 * @param array the array, which is modified in-place by this method 1513 * @param op a side-effect-free, associative function to perform the 1514 * cumulation 1515 * @throws NullPointerException if the specified array or function is null 1516 * @since 1.8 1517 */ 1518 public static <T> void parallelPrefix(T[] array, BinaryOperator<T> op) { 1519 Objects.requireNonNull(op); 1520 if (array.length > 0) 1521 new ArrayPrefixHelpers.CumulateTask<> 1522 (null, op, array, 0, array.length).invoke(); 1523 } 1524 1525 /** 1526 * Performs {@link #parallelPrefix(Object[], BinaryOperator)} 1527 * for the given subrange of the array. 1528 * 1529 * @param <T> the class of the objects in the array 1530 * @param array the array 1531 * @param fromIndex the index of the first element, inclusive 1532 * @param toIndex the index of the last element, exclusive 1533 * @param op a side-effect-free, associative function to perform the 1534 * cumulation 1535 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 1536 * @throws ArrayIndexOutOfBoundsException 1537 * if {@code fromIndex < 0} or {@code toIndex > array.length} 1538 * @throws NullPointerException if the specified array or function is null 1539 * @since 1.8 1540 */ 1541 public static <T> void parallelPrefix(T[] array, int fromIndex, 1542 int toIndex, BinaryOperator<T> op) { 1543 Objects.requireNonNull(op); 1544 rangeCheck(array.length, fromIndex, toIndex); 1545 if (fromIndex < toIndex) 1546 new ArrayPrefixHelpers.CumulateTask<> 1547 (null, op, array, fromIndex, toIndex).invoke(); 1548 } 1549 1550 /** 1551 * Cumulates, in parallel, each element of the given array in place, 1552 * using the supplied function. For example if the array initially 1553 * holds {@code [2, 1, 0, 3]} and the operation performs addition, 1554 * then upon return the array holds {@code [2, 3, 3, 6]}. 1555 * Parallel prefix computation is usually more efficient than 1556 * sequential loops for large arrays. 1557 * 1558 * @param array the array, which is modified in-place by this method 1559 * @param op a side-effect-free, associative function to perform the 1560 * cumulation 1561 * @throws NullPointerException if the specified array or function is null 1562 * @since 1.8 1563 */ 1564 public static void parallelPrefix(long[] array, LongBinaryOperator op) { 1565 Objects.requireNonNull(op); 1566 if (array.length > 0) 1567 new ArrayPrefixHelpers.LongCumulateTask 1568 (null, op, array, 0, array.length).invoke(); 1569 } 1570 1571 /** 1572 * Performs {@link #parallelPrefix(long[], LongBinaryOperator)} 1573 * for the given subrange of the array. 1574 * 1575 * @param array the array 1576 * @param fromIndex the index of the first element, inclusive 1577 * @param toIndex the index of the last element, exclusive 1578 * @param op a side-effect-free, associative function to perform the 1579 * cumulation 1580 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 1581 * @throws ArrayIndexOutOfBoundsException 1582 * if {@code fromIndex < 0} or {@code toIndex > array.length} 1583 * @throws NullPointerException if the specified array or function is null 1584 * @since 1.8 1585 */ 1586 public static void parallelPrefix(long[] array, int fromIndex, 1587 int toIndex, LongBinaryOperator op) { 1588 Objects.requireNonNull(op); 1589 rangeCheck(array.length, fromIndex, toIndex); 1590 if (fromIndex < toIndex) 1591 new ArrayPrefixHelpers.LongCumulateTask 1592 (null, op, array, fromIndex, toIndex).invoke(); 1593 } 1594 1595 /** 1596 * Cumulates, in parallel, each element of the given array in place, 1597 * using the supplied function. For example if the array initially 1598 * holds {@code [2.0, 1.0, 0.0, 3.0]} and the operation performs addition, 1599 * then upon return the array holds {@code [2.0, 3.0, 3.0, 6.0]}. 1600 * Parallel prefix computation is usually more efficient than 1601 * sequential loops for large arrays. 1602 * 1603 * <p> Because floating-point operations may not be strictly associative, 1604 * the returned result may not be identical to the value that would be 1605 * obtained if the operation was performed sequentially. 1606 * 1607 * @param array the array, which is modified in-place by this method 1608 * @param op a side-effect-free function to perform the cumulation 1609 * @throws NullPointerException if the specified array or function is null 1610 * @since 1.8 1611 */ 1612 public static void parallelPrefix(double[] array, DoubleBinaryOperator op) { 1613 Objects.requireNonNull(op); 1614 if (array.length > 0) 1615 new ArrayPrefixHelpers.DoubleCumulateTask 1616 (null, op, array, 0, array.length).invoke(); 1617 } 1618 1619 /** 1620 * Performs {@link #parallelPrefix(double[], DoubleBinaryOperator)} 1621 * for the given subrange of the array. 1622 * 1623 * @param array the array 1624 * @param fromIndex the index of the first element, inclusive 1625 * @param toIndex the index of the last element, exclusive 1626 * @param op a side-effect-free, associative function to perform the 1627 * cumulation 1628 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 1629 * @throws ArrayIndexOutOfBoundsException 1630 * if {@code fromIndex < 0} or {@code toIndex > array.length} 1631 * @throws NullPointerException if the specified array or function is null 1632 * @since 1.8 1633 */ 1634 public static void parallelPrefix(double[] array, int fromIndex, 1635 int toIndex, DoubleBinaryOperator op) { 1636 Objects.requireNonNull(op); 1637 rangeCheck(array.length, fromIndex, toIndex); 1638 if (fromIndex < toIndex) 1639 new ArrayPrefixHelpers.DoubleCumulateTask 1640 (null, op, array, fromIndex, toIndex).invoke(); 1641 } 1642 1643 /** 1644 * Cumulates, in parallel, each element of the given array in place, 1645 * using the supplied function. For example if the array initially 1646 * holds {@code [2, 1, 0, 3]} and the operation performs addition, 1647 * then upon return the array holds {@code [2, 3, 3, 6]}. 1648 * Parallel prefix computation is usually more efficient than 1649 * sequential loops for large arrays. 1650 * 1651 * @param array the array, which is modified in-place by this method 1652 * @param op a side-effect-free, associative function to perform the 1653 * cumulation 1654 * @throws NullPointerException if the specified array or function is null 1655 * @since 1.8 1656 */ 1657 public static void parallelPrefix(int[] array, IntBinaryOperator op) { 1658 Objects.requireNonNull(op); 1659 if (array.length > 0) 1660 new ArrayPrefixHelpers.IntCumulateTask 1661 (null, op, array, 0, array.length).invoke(); 1662 } 1663 1664 /** 1665 * Performs {@link #parallelPrefix(int[], IntBinaryOperator)} 1666 * for the given subrange of the array. 1667 * 1668 * @param array the array 1669 * @param fromIndex the index of the first element, inclusive 1670 * @param toIndex the index of the last element, exclusive 1671 * @param op a side-effect-free, associative function to perform the 1672 * cumulation 1673 * @throws IllegalArgumentException if {@code fromIndex > toIndex} 1674 * @throws ArrayIndexOutOfBoundsException 1675 * if {@code fromIndex < 0} or {@code toIndex > array.length} 1676 * @throws NullPointerException if the specified array or function is null 1677 * @since 1.8 1678 */ 1679 public static void parallelPrefix(int[] array, int fromIndex, 1680 int toIndex, IntBinaryOperator op) { 1681 Objects.requireNonNull(op); 1682 rangeCheck(array.length, fromIndex, toIndex); 1683 if (fromIndex < toIndex) 1684 new ArrayPrefixHelpers.IntCumulateTask 1685 (null, op, array, fromIndex, toIndex).invoke(); 1686 } 1687 1688 // Searching 1689 1690 /** 1691 * Searches the specified array of longs for the specified value using the 1692 * binary search algorithm. The array must be sorted (as 1693 * by the {@link #sort(long[])} method) prior to making this call. If it 1694 * is not sorted, the results are undefined. If the array contains 1695 * multiple elements with the specified value, there is no guarantee which 1696 * one will be found. 1697 * 1698 * @param a the array to be searched 1699 * @param key the value to be searched for 1700 * @return index of the search key, if it is contained in the array; 1701 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1702 * <i>insertion point</i> is defined as the point at which the 1703 * key would be inserted into the array: the index of the first 1704 * element greater than the key, or <tt>a.length</tt> if all 1705 * elements in the array are less than the specified key. Note 1706 * that this guarantees that the return value will be >= 0 if 1707 * and only if the key is found. 1708 */ 1709 public static int binarySearch(long[] a, long key) { 1710 return binarySearch0(a, 0, a.length, key); 1711 } 1712 1713 /** 1714 * Searches a range of 1715 * the specified array of longs for the specified value using the 1716 * binary search algorithm. 1717 * The range must be sorted (as 1718 * by the {@link #sort(long[], int, int)} method) 1719 * prior to making this call. If it 1720 * is not sorted, the results are undefined. If the range contains 1721 * multiple elements with the specified value, there is no guarantee which 1722 * one will be found. 1723 * 1724 * @param a the array to be searched 1725 * @param fromIndex the index of the first element (inclusive) to be 1726 * searched 1727 * @param toIndex the index of the last element (exclusive) to be searched 1728 * @param key the value to be searched for 1729 * @return index of the search key, if it is contained in the array 1730 * within the specified range; 1731 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1732 * <i>insertion point</i> is defined as the point at which the 1733 * key would be inserted into the array: the index of the first 1734 * element in the range greater than the key, 1735 * or <tt>toIndex</tt> if all 1736 * elements in the range are less than the specified key. Note 1737 * that this guarantees that the return value will be >= 0 if 1738 * and only if the key is found. 1739 * @throws IllegalArgumentException 1740 * if {@code fromIndex > toIndex} 1741 * @throws ArrayIndexOutOfBoundsException 1742 * if {@code fromIndex < 0 or toIndex > a.length} 1743 * @since 1.6 1744 */ 1745 public static int binarySearch(long[] a, int fromIndex, int toIndex, 1746 long key) { 1747 rangeCheck(a.length, fromIndex, toIndex); 1748 return binarySearch0(a, fromIndex, toIndex, key); 1749 } 1750 1751 // Like public version, but without range checks. 1752 private static int binarySearch0(long[] a, int fromIndex, int toIndex, 1753 long key) { 1754 int low = fromIndex; 1755 int high = toIndex - 1; 1756 1757 while (low <= high) { 1758 int mid = (low + high) >>> 1; 1759 long midVal = a[mid]; 1760 1761 if (midVal < key) 1762 low = mid + 1; 1763 else if (midVal > key) 1764 high = mid - 1; 1765 else 1766 return mid; // key found 1767 } 1768 return -(low + 1); // key not found. 1769 } 1770 1771 /** 1772 * Searches the specified array of ints for the specified value using the 1773 * binary search algorithm. The array must be sorted (as 1774 * by the {@link #sort(int[])} method) prior to making this call. If it 1775 * is not sorted, the results are undefined. If the array contains 1776 * multiple elements with the specified value, there is no guarantee which 1777 * one will be found. 1778 * 1779 * @param a the array to be searched 1780 * @param key the value to be searched for 1781 * @return index of the search key, if it is contained in the array; 1782 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1783 * <i>insertion point</i> is defined as the point at which the 1784 * key would be inserted into the array: the index of the first 1785 * element greater than the key, or <tt>a.length</tt> if all 1786 * elements in the array are less than the specified key. Note 1787 * that this guarantees that the return value will be >= 0 if 1788 * and only if the key is found. 1789 */ 1790 public static int binarySearch(int[] a, int key) { 1791 return binarySearch0(a, 0, a.length, key); 1792 } 1793 1794 /** 1795 * Searches a range of 1796 * the specified array of ints for the specified value using the 1797 * binary search algorithm. 1798 * The range must be sorted (as 1799 * by the {@link #sort(int[], int, int)} method) 1800 * prior to making this call. If it 1801 * is not sorted, the results are undefined. If the range contains 1802 * multiple elements with the specified value, there is no guarantee which 1803 * one will be found. 1804 * 1805 * @param a the array to be searched 1806 * @param fromIndex the index of the first element (inclusive) to be 1807 * searched 1808 * @param toIndex the index of the last element (exclusive) to be searched 1809 * @param key the value to be searched for 1810 * @return index of the search key, if it is contained in the array 1811 * within the specified range; 1812 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1813 * <i>insertion point</i> is defined as the point at which the 1814 * key would be inserted into the array: the index of the first 1815 * element in the range greater than the key, 1816 * or <tt>toIndex</tt> if all 1817 * elements in the range are less than the specified key. Note 1818 * that this guarantees that the return value will be >= 0 if 1819 * and only if the key is found. 1820 * @throws IllegalArgumentException 1821 * if {@code fromIndex > toIndex} 1822 * @throws ArrayIndexOutOfBoundsException 1823 * if {@code fromIndex < 0 or toIndex > a.length} 1824 * @since 1.6 1825 */ 1826 public static int binarySearch(int[] a, int fromIndex, int toIndex, 1827 int key) { 1828 rangeCheck(a.length, fromIndex, toIndex); 1829 return binarySearch0(a, fromIndex, toIndex, key); 1830 } 1831 1832 // Like public version, but without range checks. 1833 private static int binarySearch0(int[] a, int fromIndex, int toIndex, 1834 int key) { 1835 int low = fromIndex; 1836 int high = toIndex - 1; 1837 1838 while (low <= high) { 1839 int mid = (low + high) >>> 1; 1840 int midVal = a[mid]; 1841 1842 if (midVal < key) 1843 low = mid + 1; 1844 else if (midVal > key) 1845 high = mid - 1; 1846 else 1847 return mid; // key found 1848 } 1849 return -(low + 1); // key not found. 1850 } 1851 1852 /** 1853 * Searches the specified array of shorts for the specified value using 1854 * the binary search algorithm. The array must be sorted 1855 * (as by the {@link #sort(short[])} method) prior to making this call. If 1856 * it is not sorted, the results are undefined. If the array contains 1857 * multiple elements with the specified value, there is no guarantee which 1858 * one will be found. 1859 * 1860 * @param a the array to be searched 1861 * @param key the value to be searched for 1862 * @return index of the search key, if it is contained in the array; 1863 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1864 * <i>insertion point</i> is defined as the point at which the 1865 * key would be inserted into the array: the index of the first 1866 * element greater than the key, or <tt>a.length</tt> if all 1867 * elements in the array are less than the specified key. Note 1868 * that this guarantees that the return value will be >= 0 if 1869 * and only if the key is found. 1870 */ 1871 public static int binarySearch(short[] a, short key) { 1872 return binarySearch0(a, 0, a.length, key); 1873 } 1874 1875 /** 1876 * Searches a range of 1877 * the specified array of shorts for the specified value using 1878 * the binary search algorithm. 1879 * The range must be sorted 1880 * (as by the {@link #sort(short[], int, int)} method) 1881 * prior to making this call. If 1882 * it is not sorted, the results are undefined. If the range contains 1883 * multiple elements with the specified value, there is no guarantee which 1884 * one will be found. 1885 * 1886 * @param a the array to be searched 1887 * @param fromIndex the index of the first element (inclusive) to be 1888 * searched 1889 * @param toIndex the index of the last element (exclusive) to be searched 1890 * @param key the value to be searched for 1891 * @return index of the search key, if it is contained in the array 1892 * within the specified range; 1893 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1894 * <i>insertion point</i> is defined as the point at which the 1895 * key would be inserted into the array: the index of the first 1896 * element in the range greater than the key, 1897 * or <tt>toIndex</tt> if all 1898 * elements in the range are less than the specified key. Note 1899 * that this guarantees that the return value will be >= 0 if 1900 * and only if the key is found. 1901 * @throws IllegalArgumentException 1902 * if {@code fromIndex > toIndex} 1903 * @throws ArrayIndexOutOfBoundsException 1904 * if {@code fromIndex < 0 or toIndex > a.length} 1905 * @since 1.6 1906 */ 1907 public static int binarySearch(short[] a, int fromIndex, int toIndex, 1908 short key) { 1909 rangeCheck(a.length, fromIndex, toIndex); 1910 return binarySearch0(a, fromIndex, toIndex, key); 1911 } 1912 1913 // Like public version, but without range checks. 1914 private static int binarySearch0(short[] a, int fromIndex, int toIndex, 1915 short key) { 1916 int low = fromIndex; 1917 int high = toIndex - 1; 1918 1919 while (low <= high) { 1920 int mid = (low + high) >>> 1; 1921 short midVal = a[mid]; 1922 1923 if (midVal < key) 1924 low = mid + 1; 1925 else if (midVal > key) 1926 high = mid - 1; 1927 else 1928 return mid; // key found 1929 } 1930 return -(low + 1); // key not found. 1931 } 1932 1933 /** 1934 * Searches the specified array of chars for the specified value using the 1935 * binary search algorithm. The array must be sorted (as 1936 * by the {@link #sort(char[])} method) prior to making this call. If it 1937 * is not sorted, the results are undefined. If the array contains 1938 * multiple elements with the specified value, there is no guarantee which 1939 * one will be found. 1940 * 1941 * @param a the array to be searched 1942 * @param key the value to be searched for 1943 * @return index of the search key, if it is contained in the array; 1944 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1945 * <i>insertion point</i> is defined as the point at which the 1946 * key would be inserted into the array: the index of the first 1947 * element greater than the key, or <tt>a.length</tt> if all 1948 * elements in the array are less than the specified key. Note 1949 * that this guarantees that the return value will be >= 0 if 1950 * and only if the key is found. 1951 */ 1952 public static int binarySearch(char[] a, char key) { 1953 return binarySearch0(a, 0, a.length, key); 1954 } 1955 1956 /** 1957 * Searches a range of 1958 * the specified array of chars for the specified value using the 1959 * binary search algorithm. 1960 * The range must be sorted (as 1961 * by the {@link #sort(char[], int, int)} method) 1962 * prior to making this call. If it 1963 * is not sorted, the results are undefined. If the range contains 1964 * multiple elements with the specified value, there is no guarantee which 1965 * one will be found. 1966 * 1967 * @param a the array to be searched 1968 * @param fromIndex the index of the first element (inclusive) to be 1969 * searched 1970 * @param toIndex the index of the last element (exclusive) to be searched 1971 * @param key the value to be searched for 1972 * @return index of the search key, if it is contained in the array 1973 * within the specified range; 1974 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 1975 * <i>insertion point</i> is defined as the point at which the 1976 * key would be inserted into the array: the index of the first 1977 * element in the range greater than the key, 1978 * or <tt>toIndex</tt> if all 1979 * elements in the range are less than the specified key. Note 1980 * that this guarantees that the return value will be >= 0 if 1981 * and only if the key is found. 1982 * @throws IllegalArgumentException 1983 * if {@code fromIndex > toIndex} 1984 * @throws ArrayIndexOutOfBoundsException 1985 * if {@code fromIndex < 0 or toIndex > a.length} 1986 * @since 1.6 1987 */ 1988 public static int binarySearch(char[] a, int fromIndex, int toIndex, 1989 char key) { 1990 rangeCheck(a.length, fromIndex, toIndex); 1991 return binarySearch0(a, fromIndex, toIndex, key); 1992 } 1993 1994 // Like public version, but without range checks. 1995 private static int binarySearch0(char[] a, int fromIndex, int toIndex, 1996 char key) { 1997 int low = fromIndex; 1998 int high = toIndex - 1; 1999 2000 while (low <= high) { 2001 int mid = (low + high) >>> 1; 2002 char midVal = a[mid]; 2003 2004 if (midVal < key) 2005 low = mid + 1; 2006 else if (midVal > key) 2007 high = mid - 1; 2008 else 2009 return mid; // key found 2010 } 2011 return -(low + 1); // key not found. 2012 } 2013 2014 /** 2015 * Searches the specified array of bytes for the specified value using the 2016 * binary search algorithm. The array must be sorted (as 2017 * by the {@link #sort(byte[])} method) prior to making this call. If it 2018 * is not sorted, the results are undefined. If the array contains 2019 * multiple elements with the specified value, there is no guarantee which 2020 * one will be found. 2021 * 2022 * @param a the array to be searched 2023 * @param key the value to be searched for 2024 * @return index of the search key, if it is contained in the array; 2025 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 2026 * <i>insertion point</i> is defined as the point at which the 2027 * key would be inserted into the array: the index of the first 2028 * element greater than the key, or <tt>a.length</tt> if all 2029 * elements in the array are less than the specified key. Note 2030 * that this guarantees that the return value will be >= 0 if 2031 * and only if the key is found. 2032 */ 2033 public static int binarySearch(byte[] a, byte key) { 2034 return binarySearch0(a, 0, a.length, key); 2035 } 2036 2037 /** 2038 * Searches a range of 2039 * the specified array of bytes for the specified value using the 2040 * binary search algorithm. 2041 * The range must be sorted (as 2042 * by the {@link #sort(byte[], int, int)} method) 2043 * prior to making this call. If it 2044 * is not sorted, the results are undefined. If the range contains 2045 * multiple elements with the specified value, there is no guarantee which 2046 * one will be found. 2047 * 2048 * @param a the array to be searched 2049 * @param fromIndex the index of the first element (inclusive) to be 2050 * searched 2051 * @param toIndex the index of the last element (exclusive) to be searched 2052 * @param key the value to be searched for 2053 * @return index of the search key, if it is contained in the array 2054 * within the specified range; 2055 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 2056 * <i>insertion point</i> is defined as the point at which the 2057 * key would be inserted into the array: the index of the first 2058 * element in the range greater than the key, 2059 * or <tt>toIndex</tt> if all 2060 * elements in the range are less than the specified key. Note 2061 * that this guarantees that the return value will be >= 0 if 2062 * and only if the key is found. 2063 * @throws IllegalArgumentException 2064 * if {@code fromIndex > toIndex} 2065 * @throws ArrayIndexOutOfBoundsException 2066 * if {@code fromIndex < 0 or toIndex > a.length} 2067 * @since 1.6 2068 */ 2069 public static int binarySearch(byte[] a, int fromIndex, int toIndex, 2070 byte key) { 2071 rangeCheck(a.length, fromIndex, toIndex); 2072 return binarySearch0(a, fromIndex, toIndex, key); 2073 } 2074 2075 // Like public version, but without range checks. 2076 private static int binarySearch0(byte[] a, int fromIndex, int toIndex, 2077 byte key) { 2078 int low = fromIndex; 2079 int high = toIndex - 1; 2080 2081 while (low <= high) { 2082 int mid = (low + high) >>> 1; 2083 byte midVal = a[mid]; 2084 2085 if (midVal < key) 2086 low = mid + 1; 2087 else if (midVal > key) 2088 high = mid - 1; 2089 else 2090 return mid; // key found 2091 } 2092 return -(low + 1); // key not found. 2093 } 2094 2095 /** 2096 * Searches the specified array of doubles for the specified value using 2097 * the binary search algorithm. The array must be sorted 2098 * (as by the {@link #sort(double[])} method) prior to making this call. 2099 * If it is not sorted, the results are undefined. If the array contains 2100 * multiple elements with the specified value, there is no guarantee which 2101 * one will be found. This method considers all NaN values to be 2102 * equivalent and equal. 2103 * 2104 * @param a the array to be searched 2105 * @param key the value to be searched for 2106 * @return index of the search key, if it is contained in the array; 2107 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 2108 * <i>insertion point</i> is defined as the point at which the 2109 * key would be inserted into the array: the index of the first 2110 * element greater than the key, or <tt>a.length</tt> if all 2111 * elements in the array are less than the specified key. Note 2112 * that this guarantees that the return value will be >= 0 if 2113 * and only if the key is found. 2114 */ 2115 public static int binarySearch(double[] a, double key) { 2116 return binarySearch0(a, 0, a.length, key); 2117 } 2118 2119 /** 2120 * Searches a range of 2121 * the specified array of doubles for the specified value using 2122 * the binary search algorithm. 2123 * The range must be sorted 2124 * (as by the {@link #sort(double[], int, int)} method) 2125 * prior to making this call. 2126 * If it is not sorted, the results are undefined. If the range contains 2127 * multiple elements with the specified value, there is no guarantee which 2128 * one will be found. This method considers all NaN values to be 2129 * equivalent and equal. 2130 * 2131 * @param a the array to be searched 2132 * @param fromIndex the index of the first element (inclusive) to be 2133 * searched 2134 * @param toIndex the index of the last element (exclusive) to be searched 2135 * @param key the value to be searched for 2136 * @return index of the search key, if it is contained in the array 2137 * within the specified range; 2138 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 2139 * <i>insertion point</i> is defined as the point at which the 2140 * key would be inserted into the array: the index of the first 2141 * element in the range greater than the key, 2142 * or <tt>toIndex</tt> if all 2143 * elements in the range are less than the specified key. Note 2144 * that this guarantees that the return value will be >= 0 if 2145 * and only if the key is found. 2146 * @throws IllegalArgumentException 2147 * if {@code fromIndex > toIndex} 2148 * @throws ArrayIndexOutOfBoundsException 2149 * if {@code fromIndex < 0 or toIndex > a.length} 2150 * @since 1.6 2151 */ 2152 public static int binarySearch(double[] a, int fromIndex, int toIndex, 2153 double key) { 2154 rangeCheck(a.length, fromIndex, toIndex); 2155 return binarySearch0(a, fromIndex, toIndex, key); 2156 } 2157 2158 // Like public version, but without range checks. 2159 private static int binarySearch0(double[] a, int fromIndex, int toIndex, 2160 double key) { 2161 int low = fromIndex; 2162 int high = toIndex - 1; 2163 2164 while (low <= high) { 2165 int mid = (low + high) >>> 1; 2166 double midVal = a[mid]; 2167 2168 if (midVal < key) 2169 low = mid + 1; // Neither val is NaN, thisVal is smaller 2170 else if (midVal > key) 2171 high = mid - 1; // Neither val is NaN, thisVal is larger 2172 else { 2173 long midBits = Double.doubleToLongBits(midVal); 2174 long keyBits = Double.doubleToLongBits(key); 2175 if (midBits == keyBits) // Values are equal 2176 return mid; // Key found 2177 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN) 2178 low = mid + 1; 2179 else // (0.0, -0.0) or (NaN, !NaN) 2180 high = mid - 1; 2181 } 2182 } 2183 return -(low + 1); // key not found. 2184 } 2185 2186 /** 2187 * Searches the specified array of floats for the specified value using 2188 * the binary search algorithm. The array must be sorted 2189 * (as by the {@link #sort(float[])} method) prior to making this call. If 2190 * it is not sorted, the results are undefined. If the array contains 2191 * multiple elements with the specified value, there is no guarantee which 2192 * one will be found. This method considers all NaN values to be 2193 * equivalent and equal. 2194 * 2195 * @param a the array to be searched 2196 * @param key the value to be searched for 2197 * @return index of the search key, if it is contained in the array; 2198 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 2199 * <i>insertion point</i> is defined as the point at which the 2200 * key would be inserted into the array: the index of the first 2201 * element greater than the key, or <tt>a.length</tt> if all 2202 * elements in the array are less than the specified key. Note 2203 * that this guarantees that the return value will be >= 0 if 2204 * and only if the key is found. 2205 */ 2206 public static int binarySearch(float[] a, float key) { 2207 return binarySearch0(a, 0, a.length, key); 2208 } 2209 2210 /** 2211 * Searches a range of 2212 * the specified array of floats for the specified value using 2213 * the binary search algorithm. 2214 * The range must be sorted 2215 * (as by the {@link #sort(float[], int, int)} method) 2216 * prior to making this call. If 2217 * it is not sorted, the results are undefined. If the range contains 2218 * multiple elements with the specified value, there is no guarantee which 2219 * one will be found. This method considers all NaN values to be 2220 * equivalent and equal. 2221 * 2222 * @param a the array to be searched 2223 * @param fromIndex the index of the first element (inclusive) to be 2224 * searched 2225 * @param toIndex the index of the last element (exclusive) to be searched 2226 * @param key the value to be searched for 2227 * @return index of the search key, if it is contained in the array 2228 * within the specified range; 2229 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 2230 * <i>insertion point</i> is defined as the point at which the 2231 * key would be inserted into the array: the index of the first 2232 * element in the range greater than the key, 2233 * or <tt>toIndex</tt> if all 2234 * elements in the range are less than the specified key. Note 2235 * that this guarantees that the return value will be >= 0 if 2236 * and only if the key is found. 2237 * @throws IllegalArgumentException 2238 * if {@code fromIndex > toIndex} 2239 * @throws ArrayIndexOutOfBoundsException 2240 * if {@code fromIndex < 0 or toIndex > a.length} 2241 * @since 1.6 2242 */ 2243 public static int binarySearch(float[] a, int fromIndex, int toIndex, 2244 float key) { 2245 rangeCheck(a.length, fromIndex, toIndex); 2246 return binarySearch0(a, fromIndex, toIndex, key); 2247 } 2248 2249 // Like public version, but without range checks. 2250 private static int binarySearch0(float[] a, int fromIndex, int toIndex, 2251 float key) { 2252 int low = fromIndex; 2253 int high = toIndex - 1; 2254 2255 while (low <= high) { 2256 int mid = (low + high) >>> 1; 2257 float midVal = a[mid]; 2258 2259 if (midVal < key) 2260 low = mid + 1; // Neither val is NaN, thisVal is smaller 2261 else if (midVal > key) 2262 high = mid - 1; // Neither val is NaN, thisVal is larger 2263 else { 2264 int midBits = Float.floatToIntBits(midVal); 2265 int keyBits = Float.floatToIntBits(key); 2266 if (midBits == keyBits) // Values are equal 2267 return mid; // Key found 2268 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN) 2269 low = mid + 1; 2270 else // (0.0, -0.0) or (NaN, !NaN) 2271 high = mid - 1; 2272 } 2273 } 2274 return -(low + 1); // key not found. 2275 } 2276 2277 /** 2278 * Searches the specified array for the specified object using the binary 2279 * search algorithm. The array must be sorted into ascending order 2280 * according to the 2281 * {@linkplain Comparable natural ordering} 2282 * of its elements (as by the 2283 * {@link #sort(Object[])} method) prior to making this call. 2284 * If it is not sorted, the results are undefined. 2285 * (If the array contains elements that are not mutually comparable (for 2286 * example, strings and integers), it <i>cannot</i> be sorted according 2287 * to the natural ordering of its elements, hence results are undefined.) 2288 * If the array contains multiple 2289 * elements equal to the specified object, there is no guarantee which 2290 * one will be found. 2291 * 2292 * @param a the array to be searched 2293 * @param key the value to be searched for 2294 * @return index of the search key, if it is contained in the array; 2295 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 2296 * <i>insertion point</i> is defined as the point at which the 2297 * key would be inserted into the array: the index of the first 2298 * element greater than the key, or <tt>a.length</tt> if all 2299 * elements in the array are less than the specified key. Note 2300 * that this guarantees that the return value will be >= 0 if 2301 * and only if the key is found. 2302 * @throws ClassCastException if the search key is not comparable to the 2303 * elements of the array. 2304 */ 2305 public static int binarySearch(Object[] a, Object key) { 2306 return binarySearch0(a, 0, a.length, key); 2307 } 2308 2309 /** 2310 * Searches a range of 2311 * the specified array for the specified object using the binary 2312 * search algorithm. 2313 * The range must be sorted into ascending order 2314 * according to the 2315 * {@linkplain Comparable natural ordering} 2316 * of its elements (as by the 2317 * {@link #sort(Object[], int, int)} method) prior to making this 2318 * call. If it is not sorted, the results are undefined. 2319 * (If the range contains elements that are not mutually comparable (for 2320 * example, strings and integers), it <i>cannot</i> be sorted according 2321 * to the natural ordering of its elements, hence results are undefined.) 2322 * If the range contains multiple 2323 * elements equal to the specified object, there is no guarantee which 2324 * one will be found. 2325 * 2326 * @param a the array to be searched 2327 * @param fromIndex the index of the first element (inclusive) to be 2328 * searched 2329 * @param toIndex the index of the last element (exclusive) to be searched 2330 * @param key the value to be searched for 2331 * @return index of the search key, if it is contained in the array 2332 * within the specified range; 2333 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 2334 * <i>insertion point</i> is defined as the point at which the 2335 * key would be inserted into the array: the index of the first 2336 * element in the range greater than the key, 2337 * or <tt>toIndex</tt> if all 2338 * elements in the range are less than the specified key. Note 2339 * that this guarantees that the return value will be >= 0 if 2340 * and only if the key is found. 2341 * @throws ClassCastException if the search key is not comparable to the 2342 * elements of the array within the specified range. 2343 * @throws IllegalArgumentException 2344 * if {@code fromIndex > toIndex} 2345 * @throws ArrayIndexOutOfBoundsException 2346 * if {@code fromIndex < 0 or toIndex > a.length} 2347 * @since 1.6 2348 */ 2349 public static int binarySearch(Object[] a, int fromIndex, int toIndex, 2350 Object key) { 2351 rangeCheck(a.length, fromIndex, toIndex); 2352 return binarySearch0(a, fromIndex, toIndex, key); 2353 } 2354 2355 // Like public version, but without range checks. 2356 private static int binarySearch0(Object[] a, int fromIndex, int toIndex, 2357 Object key) { 2358 int low = fromIndex; 2359 int high = toIndex - 1; 2360 2361 while (low <= high) { 2362 int mid = (low + high) >>> 1; 2363 @SuppressWarnings("rawtypes") 2364 Comparable midVal = (Comparable)a[mid]; 2365 @SuppressWarnings("unchecked") 2366 int cmp = midVal.compareTo(key); 2367 2368 if (cmp < 0) 2369 low = mid + 1; 2370 else if (cmp > 0) 2371 high = mid - 1; 2372 else 2373 return mid; // key found 2374 } 2375 return -(low + 1); // key not found. 2376 } 2377 2378 /** 2379 * Searches the specified array for the specified object using the binary 2380 * search algorithm. The array must be sorted into ascending order 2381 * according to the specified comparator (as by the 2382 * {@link #sort(Object[], Comparator) sort(T[], Comparator)} 2383 * method) prior to making this call. If it is 2384 * not sorted, the results are undefined. 2385 * If the array contains multiple 2386 * elements equal to the specified object, there is no guarantee which one 2387 * will be found. 2388 * 2389 * @param <T> the class of the objects in the array 2390 * @param a the array to be searched 2391 * @param key the value to be searched for 2392 * @param c the comparator by which the array is ordered. A 2393 * <tt>null</tt> value indicates that the elements' 2394 * {@linkplain Comparable natural ordering} should be used. 2395 * @return index of the search key, if it is contained in the array; 2396 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 2397 * <i>insertion point</i> is defined as the point at which the 2398 * key would be inserted into the array: the index of the first 2399 * element greater than the key, or <tt>a.length</tt> if all 2400 * elements in the array are less than the specified key. Note 2401 * that this guarantees that the return value will be >= 0 if 2402 * and only if the key is found. 2403 * @throws ClassCastException if the array contains elements that are not 2404 * <i>mutually comparable</i> using the specified comparator, 2405 * or the search key is not comparable to the 2406 * elements of the array using this comparator. 2407 */ 2408 public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) { 2409 return binarySearch0(a, 0, a.length, key, c); 2410 } 2411 2412 /** 2413 * Searches a range of 2414 * the specified array for the specified object using the binary 2415 * search algorithm. 2416 * The range must be sorted into ascending order 2417 * according to the specified comparator (as by the 2418 * {@link #sort(Object[], int, int, Comparator) 2419 * sort(T[], int, int, Comparator)} 2420 * method) prior to making this call. 2421 * If it is not sorted, the results are undefined. 2422 * If the range contains multiple elements equal to the specified object, 2423 * there is no guarantee which one will be found. 2424 * 2425 * @param <T> the class of the objects in the array 2426 * @param a the array to be searched 2427 * @param fromIndex the index of the first element (inclusive) to be 2428 * searched 2429 * @param toIndex the index of the last element (exclusive) to be searched 2430 * @param key the value to be searched for 2431 * @param c the comparator by which the array is ordered. A 2432 * <tt>null</tt> value indicates that the elements' 2433 * {@linkplain Comparable natural ordering} should be used. 2434 * @return index of the search key, if it is contained in the array 2435 * within the specified range; 2436 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 2437 * <i>insertion point</i> is defined as the point at which the 2438 * key would be inserted into the array: the index of the first 2439 * element in the range greater than the key, 2440 * or <tt>toIndex</tt> if all 2441 * elements in the range are less than the specified key. Note 2442 * that this guarantees that the return value will be >= 0 if 2443 * and only if the key is found. 2444 * @throws ClassCastException if the range contains elements that are not 2445 * <i>mutually comparable</i> using the specified comparator, 2446 * or the search key is not comparable to the 2447 * elements in the range using this comparator. 2448 * @throws IllegalArgumentException 2449 * if {@code fromIndex > toIndex} 2450 * @throws ArrayIndexOutOfBoundsException 2451 * if {@code fromIndex < 0 or toIndex > a.length} 2452 * @since 1.6 2453 */ 2454 public static <T> int binarySearch(T[] a, int fromIndex, int toIndex, 2455 T key, Comparator<? super T> c) { 2456 rangeCheck(a.length, fromIndex, toIndex); 2457 return binarySearch0(a, fromIndex, toIndex, key, c); 2458 } 2459 2460 // Like public version, but without range checks. 2461 private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex, 2462 T key, Comparator<? super T> c) { 2463 if (c == null) { 2464 return binarySearch0(a, fromIndex, toIndex, key); 2465 } 2466 int low = fromIndex; 2467 int high = toIndex - 1; 2468 2469 while (low <= high) { 2470 int mid = (low + high) >>> 1; 2471 T midVal = a[mid]; 2472 int cmp = c.compare(midVal, key); 2473 if (cmp < 0) 2474 low = mid + 1; 2475 else if (cmp > 0) 2476 high = mid - 1; 2477 else 2478 return mid; // key found 2479 } 2480 return -(low + 1); // key not found. 2481 } 2482 2483 // Equality Testing 2484 2485 /** 2486 * Returns <tt>true</tt> if the two specified arrays of longs are 2487 * <i>equal</i> to one another. Two arrays are considered equal if both 2488 * arrays contain the same number of elements, and all corresponding pairs 2489 * of elements in the two arrays are equal. In other words, two arrays 2490 * are equal if they contain the same elements in the same order. Also, 2491 * two array references are considered equal if both are <tt>null</tt>.<p> 2492 * 2493 * @param a one array to be tested for equality 2494 * @param a2 the other array to be tested for equality 2495 * @return <tt>true</tt> if the two arrays are equal 2496 */ 2497 public static boolean equals(long[] a, long[] a2) { 2498 if (a==a2) 2499 return true; 2500 if (a==null || a2==null) 2501 return false; 2502 2503 int length = a.length; 2504 if (a2.length != length) 2505 return false; 2506 2507 for (int i=0; i<length; i++) 2508 if (a[i] != a2[i]) 2509 return false; 2510 2511 return true; 2512 } 2513 2514 /** 2515 * Returns <tt>true</tt> if the two specified arrays of ints are 2516 * <i>equal</i> to one another. Two arrays are considered equal if both 2517 * arrays contain the same number of elements, and all corresponding pairs 2518 * of elements in the two arrays are equal. In other words, two arrays 2519 * are equal if they contain the same elements in the same order. Also, 2520 * two array references are considered equal if both are <tt>null</tt>.<p> 2521 * 2522 * @param a one array to be tested for equality 2523 * @param a2 the other array to be tested for equality 2524 * @return <tt>true</tt> if the two arrays are equal 2525 */ 2526 public static boolean equals(int[] a, int[] a2) { 2527 if (a==a2) 2528 return true; 2529 if (a==null || a2==null) 2530 return false; 2531 2532 int length = a.length; 2533 if (a2.length != length) 2534 return false; 2535 2536 for (int i=0; i<length; i++) 2537 if (a[i] != a2[i]) 2538 return false; 2539 2540 return true; 2541 } 2542 2543 /** 2544 * Returns <tt>true</tt> if the two specified arrays of shorts are 2545 * <i>equal</i> to one another. Two arrays are considered equal if both 2546 * arrays contain the same number of elements, and all corresponding pairs 2547 * of elements in the two arrays are equal. In other words, two arrays 2548 * are equal if they contain the same elements in the same order. Also, 2549 * two array references are considered equal if both are <tt>null</tt>.<p> 2550 * 2551 * @param a one array to be tested for equality 2552 * @param a2 the other array to be tested for equality 2553 * @return <tt>true</tt> if the two arrays are equal 2554 */ 2555 public static boolean equals(short[] a, short a2[]) { 2556 if (a==a2) 2557 return true; 2558 if (a==null || a2==null) 2559 return false; 2560 2561 int length = a.length; 2562 if (a2.length != length) 2563 return false; 2564 2565 for (int i=0; i<length; i++) 2566 if (a[i] != a2[i]) 2567 return false; 2568 2569 return true; 2570 } 2571 2572 /** 2573 * Returns <tt>true</tt> if the two specified arrays of chars are 2574 * <i>equal</i> to one another. Two arrays are considered equal if both 2575 * arrays contain the same number of elements, and all corresponding pairs 2576 * of elements in the two arrays are equal. In other words, two arrays 2577 * are equal if they contain the same elements in the same order. Also, 2578 * two array references are considered equal if both are <tt>null</tt>.<p> 2579 * 2580 * @param a one array to be tested for equality 2581 * @param a2 the other array to be tested for equality 2582 * @return <tt>true</tt> if the two arrays are equal 2583 */ 2584 public static boolean equals(char[] a, char[] a2) { 2585 if (a==a2) 2586 return true; 2587 if (a==null || a2==null) 2588 return false; 2589 2590 int length = a.length; 2591 if (a2.length != length) 2592 return false; 2593 2594 for (int i=0; i<length; i++) 2595 if (a[i] != a2[i]) 2596 return false; 2597 2598 return true; 2599 } 2600 2601 /** 2602 * Returns <tt>true</tt> if the two specified arrays of bytes are 2603 * <i>equal</i> to one another. Two arrays are considered equal if both 2604 * arrays contain the same number of elements, and all corresponding pairs 2605 * of elements in the two arrays are equal. In other words, two arrays 2606 * are equal if they contain the same elements in the same order. Also, 2607 * two array references are considered equal if both are <tt>null</tt>.<p> 2608 * 2609 * @param a one array to be tested for equality 2610 * @param a2 the other array to be tested for equality 2611 * @return <tt>true</tt> if the two arrays are equal 2612 */ 2613 public static boolean equals(byte[] a, byte[] a2) { 2614 if (a==a2) 2615 return true; 2616 if (a==null || a2==null) 2617 return false; 2618 2619 int length = a.length; 2620 if (a2.length != length) 2621 return false; 2622 2623 for (int i=0; i<length; i++) 2624 if (a[i] != a2[i]) 2625 return false; 2626 2627 return true; 2628 } 2629 2630 /** 2631 * Returns <tt>true</tt> if the two specified arrays of booleans are 2632 * <i>equal</i> to one another. Two arrays are considered equal if both 2633 * arrays contain the same number of elements, and all corresponding pairs 2634 * of elements in the two arrays are equal. In other words, two arrays 2635 * are equal if they contain the same elements in the same order. Also, 2636 * two array references are considered equal if both are <tt>null</tt>.<p> 2637 * 2638 * @param a one array to be tested for equality 2639 * @param a2 the other array to be tested for equality 2640 * @return <tt>true</tt> if the two arrays are equal 2641 */ 2642 public static boolean equals(boolean[] a, boolean[] a2) { 2643 if (a==a2) 2644 return true; 2645 if (a==null || a2==null) 2646 return false; 2647 2648 int length = a.length; 2649 if (a2.length != length) 2650 return false; 2651 2652 for (int i=0; i<length; i++) 2653 if (a[i] != a2[i]) 2654 return false; 2655 2656 return true; 2657 } 2658 2659 /** 2660 * Returns <tt>true</tt> if the two specified arrays of doubles are 2661 * <i>equal</i> to one another. Two arrays are considered equal if both 2662 * arrays contain the same number of elements, and all corresponding pairs 2663 * of elements in the two arrays are equal. In other words, two arrays 2664 * are equal if they contain the same elements in the same order. Also, 2665 * two array references are considered equal if both are <tt>null</tt>.<p> 2666 * 2667 * Two doubles <tt>d1</tt> and <tt>d2</tt> are considered equal if: 2668 * <pre> <tt>new Double(d1).equals(new Double(d2))</tt></pre> 2669 * (Unlike the <tt>==</tt> operator, this method considers 2670 * <tt>NaN</tt> equals to itself, and 0.0d unequal to -0.0d.) 2671 * 2672 * @param a one array to be tested for equality 2673 * @param a2 the other array to be tested for equality 2674 * @return <tt>true</tt> if the two arrays are equal 2675 * @see Double#equals(Object) 2676 */ 2677 public static boolean equals(double[] a, double[] a2) { 2678 if (a==a2) 2679 return true; 2680 if (a==null || a2==null) 2681 return false; 2682 2683 int length = a.length; 2684 if (a2.length != length) 2685 return false; 2686 2687 for (int i=0; i<length; i++) 2688 if (Double.doubleToLongBits(a[i])!=Double.doubleToLongBits(a2[i])) 2689 return false; 2690 2691 return true; 2692 } 2693 2694 /** 2695 * Returns <tt>true</tt> if the two specified arrays of floats are 2696 * <i>equal</i> to one another. Two arrays are considered equal if both 2697 * arrays contain the same number of elements, and all corresponding pairs 2698 * of elements in the two arrays are equal. In other words, two arrays 2699 * are equal if they contain the same elements in the same order. Also, 2700 * two array references are considered equal if both are <tt>null</tt>.<p> 2701 * 2702 * Two floats <tt>f1</tt> and <tt>f2</tt> are considered equal if: 2703 * <pre> <tt>new Float(f1).equals(new Float(f2))</tt></pre> 2704 * (Unlike the <tt>==</tt> operator, this method considers 2705 * <tt>NaN</tt> equals to itself, and 0.0f unequal to -0.0f.) 2706 * 2707 * @param a one array to be tested for equality 2708 * @param a2 the other array to be tested for equality 2709 * @return <tt>true</tt> if the two arrays are equal 2710 * @see Float#equals(Object) 2711 */ 2712 public static boolean equals(float[] a, float[] a2) { 2713 if (a==a2) 2714 return true; 2715 if (a==null || a2==null) 2716 return false; 2717 2718 int length = a.length; 2719 if (a2.length != length) 2720 return false; 2721 2722 for (int i=0; i<length; i++) 2723 if (Float.floatToIntBits(a[i])!=Float.floatToIntBits(a2[i])) 2724 return false; 2725 2726 return true; 2727 } 2728 2729 /** 2730 * Returns <tt>true</tt> if the two specified arrays of Objects are 2731 * <i>equal</i> to one another. The two arrays are considered equal if 2732 * both arrays contain the same number of elements, and all corresponding 2733 * pairs of elements in the two arrays are equal. Two objects <tt>e1</tt> 2734 * and <tt>e2</tt> are considered <i>equal</i> if <tt>(e1==null ? e2==null 2735 * : e1.equals(e2))</tt>. In other words, the two arrays are equal if 2736 * they contain the same elements in the same order. Also, two array 2737 * references are considered equal if both are <tt>null</tt>.<p> 2738 * 2739 * @param a one array to be tested for equality 2740 * @param a2 the other array to be tested for equality 2741 * @return <tt>true</tt> if the two arrays are equal 2742 */ 2743 public static boolean equals(Object[] a, Object[] a2) { 2744 if (a==a2) 2745 return true; 2746 if (a==null || a2==null) 2747 return false; 2748 2749 int length = a.length; 2750 if (a2.length != length) 2751 return false; 2752 2753 for (int i=0; i<length; i++) { 2754 Object o1 = a[i]; 2755 Object o2 = a2[i]; 2756 if (!(o1==null ? o2==null : o1.equals(o2))) 2757 return false; 2758 } 2759 2760 return true; 2761 } 2762 2763 // Filling 2764 2765 /** 2766 * Assigns the specified long value to each element of the specified array 2767 * of longs. 2768 * 2769 * @param a the array to be filled 2770 * @param val the value to be stored in all elements of the array 2771 */ 2772 public static void fill(long[] a, long val) { 2773 for (int i = 0, len = a.length; i < len; i++) 2774 a[i] = val; 2775 } 2776 2777 /** 2778 * Assigns the specified long value to each element of the specified 2779 * range of the specified array of longs. The range to be filled 2780 * extends from index <tt>fromIndex</tt>, inclusive, to index 2781 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 2782 * range to be filled is empty.) 2783 * 2784 * @param a the array to be filled 2785 * @param fromIndex the index of the first element (inclusive) to be 2786 * filled with the specified value 2787 * @param toIndex the index of the last element (exclusive) to be 2788 * filled with the specified value 2789 * @param val the value to be stored in all elements of the array 2790 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 2791 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 2792 * <tt>toIndex > a.length</tt> 2793 */ 2794 public static void fill(long[] a, int fromIndex, int toIndex, long val) { 2795 rangeCheck(a.length, fromIndex, toIndex); 2796 for (int i = fromIndex; i < toIndex; i++) 2797 a[i] = val; 2798 } 2799 2800 /** 2801 * Assigns the specified int value to each element of the specified array 2802 * of ints. 2803 * 2804 * @param a the array to be filled 2805 * @param val the value to be stored in all elements of the array 2806 */ 2807 public static void fill(int[] a, int val) { 2808 for (int i = 0, len = a.length; i < len; i++) 2809 a[i] = val; 2810 } 2811 2812 /** 2813 * Assigns the specified int value to each element of the specified 2814 * range of the specified array of ints. The range to be filled 2815 * extends from index <tt>fromIndex</tt>, inclusive, to index 2816 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 2817 * range to be filled is empty.) 2818 * 2819 * @param a the array to be filled 2820 * @param fromIndex the index of the first element (inclusive) to be 2821 * filled with the specified value 2822 * @param toIndex the index of the last element (exclusive) to be 2823 * filled with the specified value 2824 * @param val the value to be stored in all elements of the array 2825 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 2826 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 2827 * <tt>toIndex > a.length</tt> 2828 */ 2829 public static void fill(int[] a, int fromIndex, int toIndex, int val) { 2830 rangeCheck(a.length, fromIndex, toIndex); 2831 for (int i = fromIndex; i < toIndex; i++) 2832 a[i] = val; 2833 } 2834 2835 /** 2836 * Assigns the specified short value to each element of the specified array 2837 * of shorts. 2838 * 2839 * @param a the array to be filled 2840 * @param val the value to be stored in all elements of the array 2841 */ 2842 public static void fill(short[] a, short val) { 2843 for (int i = 0, len = a.length; i < len; i++) 2844 a[i] = val; 2845 } 2846 2847 /** 2848 * Assigns the specified short value to each element of the specified 2849 * range of the specified array of shorts. The range to be filled 2850 * extends from index <tt>fromIndex</tt>, inclusive, to index 2851 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 2852 * range to be filled is empty.) 2853 * 2854 * @param a the array to be filled 2855 * @param fromIndex the index of the first element (inclusive) to be 2856 * filled with the specified value 2857 * @param toIndex the index of the last element (exclusive) to be 2858 * filled with the specified value 2859 * @param val the value to be stored in all elements of the array 2860 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 2861 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 2862 * <tt>toIndex > a.length</tt> 2863 */ 2864 public static void fill(short[] a, int fromIndex, int toIndex, short val) { 2865 rangeCheck(a.length, fromIndex, toIndex); 2866 for (int i = fromIndex; i < toIndex; i++) 2867 a[i] = val; 2868 } 2869 2870 /** 2871 * Assigns the specified char value to each element of the specified array 2872 * of chars. 2873 * 2874 * @param a the array to be filled 2875 * @param val the value to be stored in all elements of the array 2876 */ 2877 public static void fill(char[] a, char val) { 2878 for (int i = 0, len = a.length; i < len; i++) 2879 a[i] = val; 2880 } 2881 2882 /** 2883 * Assigns the specified char value to each element of the specified 2884 * range of the specified array of chars. The range to be filled 2885 * extends from index <tt>fromIndex</tt>, inclusive, to index 2886 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 2887 * range to be filled is empty.) 2888 * 2889 * @param a the array to be filled 2890 * @param fromIndex the index of the first element (inclusive) to be 2891 * filled with the specified value 2892 * @param toIndex the index of the last element (exclusive) to be 2893 * filled with the specified value 2894 * @param val the value to be stored in all elements of the array 2895 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 2896 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 2897 * <tt>toIndex > a.length</tt> 2898 */ 2899 public static void fill(char[] a, int fromIndex, int toIndex, char val) { 2900 rangeCheck(a.length, fromIndex, toIndex); 2901 for (int i = fromIndex; i < toIndex; i++) 2902 a[i] = val; 2903 } 2904 2905 /** 2906 * Assigns the specified byte value to each element of the specified array 2907 * of bytes. 2908 * 2909 * @param a the array to be filled 2910 * @param val the value to be stored in all elements of the array 2911 */ 2912 public static void fill(byte[] a, byte val) { 2913 for (int i = 0, len = a.length; i < len; i++) 2914 a[i] = val; 2915 } 2916 2917 /** 2918 * Assigns the specified byte value to each element of the specified 2919 * range of the specified array of bytes. The range to be filled 2920 * extends from index <tt>fromIndex</tt>, inclusive, to index 2921 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 2922 * range to be filled is empty.) 2923 * 2924 * @param a the array to be filled 2925 * @param fromIndex the index of the first element (inclusive) to be 2926 * filled with the specified value 2927 * @param toIndex the index of the last element (exclusive) to be 2928 * filled with the specified value 2929 * @param val the value to be stored in all elements of the array 2930 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 2931 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 2932 * <tt>toIndex > a.length</tt> 2933 */ 2934 public static void fill(byte[] a, int fromIndex, int toIndex, byte val) { 2935 rangeCheck(a.length, fromIndex, toIndex); 2936 for (int i = fromIndex; i < toIndex; i++) 2937 a[i] = val; 2938 } 2939 2940 /** 2941 * Assigns the specified boolean value to each element of the specified 2942 * array of booleans. 2943 * 2944 * @param a the array to be filled 2945 * @param val the value to be stored in all elements of the array 2946 */ 2947 public static void fill(boolean[] a, boolean val) { 2948 for (int i = 0, len = a.length; i < len; i++) 2949 a[i] = val; 2950 } 2951 2952 /** 2953 * Assigns the specified boolean value to each element of the specified 2954 * range of the specified array of booleans. The range to be filled 2955 * extends from index <tt>fromIndex</tt>, inclusive, to index 2956 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 2957 * range to be filled is empty.) 2958 * 2959 * @param a the array to be filled 2960 * @param fromIndex the index of the first element (inclusive) to be 2961 * filled with the specified value 2962 * @param toIndex the index of the last element (exclusive) to be 2963 * filled with the specified value 2964 * @param val the value to be stored in all elements of the array 2965 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 2966 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 2967 * <tt>toIndex > a.length</tt> 2968 */ 2969 public static void fill(boolean[] a, int fromIndex, int toIndex, 2970 boolean val) { 2971 rangeCheck(a.length, fromIndex, toIndex); 2972 for (int i = fromIndex; i < toIndex; i++) 2973 a[i] = val; 2974 } 2975 2976 /** 2977 * Assigns the specified double value to each element of the specified 2978 * array of doubles. 2979 * 2980 * @param a the array to be filled 2981 * @param val the value to be stored in all elements of the array 2982 */ 2983 public static void fill(double[] a, double val) { 2984 for (int i = 0, len = a.length; i < len; i++) 2985 a[i] = val; 2986 } 2987 2988 /** 2989 * Assigns the specified double value to each element of the specified 2990 * range of the specified array of doubles. The range to be filled 2991 * extends from index <tt>fromIndex</tt>, inclusive, to index 2992 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 2993 * range to be filled is empty.) 2994 * 2995 * @param a the array to be filled 2996 * @param fromIndex the index of the first element (inclusive) to be 2997 * filled with the specified value 2998 * @param toIndex the index of the last element (exclusive) to be 2999 * filled with the specified value 3000 * @param val the value to be stored in all elements of the array 3001 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 3002 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 3003 * <tt>toIndex > a.length</tt> 3004 */ 3005 public static void fill(double[] a, int fromIndex, int toIndex,double val){ 3006 rangeCheck(a.length, fromIndex, toIndex); 3007 for (int i = fromIndex; i < toIndex; i++) 3008 a[i] = val; 3009 } 3010 3011 /** 3012 * Assigns the specified float value to each element of the specified array 3013 * of floats. 3014 * 3015 * @param a the array to be filled 3016 * @param val the value to be stored in all elements of the array 3017 */ 3018 public static void fill(float[] a, float val) { 3019 for (int i = 0, len = a.length; i < len; i++) 3020 a[i] = val; 3021 } 3022 3023 /** 3024 * Assigns the specified float value to each element of the specified 3025 * range of the specified array of floats. The range to be filled 3026 * extends from index <tt>fromIndex</tt>, inclusive, to index 3027 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 3028 * range to be filled is empty.) 3029 * 3030 * @param a the array to be filled 3031 * @param fromIndex the index of the first element (inclusive) to be 3032 * filled with the specified value 3033 * @param toIndex the index of the last element (exclusive) to be 3034 * filled with the specified value 3035 * @param val the value to be stored in all elements of the array 3036 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 3037 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 3038 * <tt>toIndex > a.length</tt> 3039 */ 3040 public static void fill(float[] a, int fromIndex, int toIndex, float val) { 3041 rangeCheck(a.length, fromIndex, toIndex); 3042 for (int i = fromIndex; i < toIndex; i++) 3043 a[i] = val; 3044 } 3045 3046 /** 3047 * Assigns the specified Object reference to each element of the specified 3048 * array of Objects. 3049 * 3050 * @param a the array to be filled 3051 * @param val the value to be stored in all elements of the array 3052 * @throws ArrayStoreException if the specified value is not of a 3053 * runtime type that can be stored in the specified array 3054 */ 3055 public static void fill(Object[] a, Object val) { 3056 for (int i = 0, len = a.length; i < len; i++) 3057 a[i] = val; 3058 } 3059 3060 /** 3061 * Assigns the specified Object reference to each element of the specified 3062 * range of the specified array of Objects. The range to be filled 3063 * extends from index <tt>fromIndex</tt>, inclusive, to index 3064 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the 3065 * range to be filled is empty.) 3066 * 3067 * @param a the array to be filled 3068 * @param fromIndex the index of the first element (inclusive) to be 3069 * filled with the specified value 3070 * @param toIndex the index of the last element (exclusive) to be 3071 * filled with the specified value 3072 * @param val the value to be stored in all elements of the array 3073 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt> 3074 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or 3075 * <tt>toIndex > a.length</tt> 3076 * @throws ArrayStoreException if the specified value is not of a 3077 * runtime type that can be stored in the specified array 3078 */ 3079 public static void fill(Object[] a, int fromIndex, int toIndex, Object val) { 3080 rangeCheck(a.length, fromIndex, toIndex); 3081 for (int i = fromIndex; i < toIndex; i++) 3082 a[i] = val; 3083 } 3084 3085 // Cloning 3086 3087 /** 3088 * Copies the specified array, truncating or padding with nulls (if necessary) 3089 * so the copy has the specified length. For all indices that are 3090 * valid in both the original array and the copy, the two arrays will 3091 * contain identical values. For any indices that are valid in the 3092 * copy but not the original, the copy will contain <tt>null</tt>. 3093 * Such indices will exist if and only if the specified length 3094 * is greater than that of the original array. 3095 * The resulting array is of exactly the same class as the original array. 3096 * 3097 * @param <T> the class of the objects in the array 3098 * @param original the array to be copied 3099 * @param newLength the length of the copy to be returned 3100 * @return a copy of the original array, truncated or padded with nulls 3101 * to obtain the specified length 3102 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 3103 * @throws NullPointerException if <tt>original</tt> is null 3104 * @since 1.6 3105 */ 3106 @SuppressWarnings("unchecked") 3107 public static <T> T[] copyOf(T[] original, int newLength) { 3108 return (T[]) copyOf(original, newLength, original.getClass()); 3109 } 3110 3111 /** 3112 * Copies the specified array, truncating or padding with nulls (if necessary) 3113 * so the copy has the specified length. For all indices that are 3114 * valid in both the original array and the copy, the two arrays will 3115 * contain identical values. For any indices that are valid in the 3116 * copy but not the original, the copy will contain <tt>null</tt>. 3117 * Such indices will exist if and only if the specified length 3118 * is greater than that of the original array. 3119 * The resulting array is of the class <tt>newType</tt>. 3120 * 3121 * @param <U> the class of the objects in the original array 3122 * @param <T> the class of the objects in the returned array 3123 * @param original the array to be copied 3124 * @param newLength the length of the copy to be returned 3125 * @param newType the class of the copy to be returned 3126 * @return a copy of the original array, truncated or padded with nulls 3127 * to obtain the specified length 3128 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 3129 * @throws NullPointerException if <tt>original</tt> is null 3130 * @throws ArrayStoreException if an element copied from 3131 * <tt>original</tt> is not of a runtime type that can be stored in 3132 * an array of class <tt>newType</tt> 3133 * @since 1.6 3134 */ 3135 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { 3136 @SuppressWarnings("unchecked") 3137 T[] copy = ((Object)newType == (Object)Object[].class) 3138 ? (T[]) new Object[newLength] 3139 : (T[]) Array.newInstance(newType.getComponentType(), newLength); 3140 System.arraycopy(original, 0, copy, 0, 3141 Math.min(original.length, newLength)); 3142 return copy; 3143 } 3144 3145 /** 3146 * Copies the specified array, truncating or padding with zeros (if necessary) 3147 * so the copy has the specified length. For all indices that are 3148 * valid in both the original array and the copy, the two arrays will 3149 * contain identical values. For any indices that are valid in the 3150 * copy but not the original, the copy will contain <tt>(byte)0</tt>. 3151 * Such indices will exist if and only if the specified length 3152 * is greater than that of the original array. 3153 * 3154 * @param original the array to be copied 3155 * @param newLength the length of the copy to be returned 3156 * @return a copy of the original array, truncated or padded with zeros 3157 * to obtain the specified length 3158 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 3159 * @throws NullPointerException if <tt>original</tt> is null 3160 * @since 1.6 3161 */ 3162 public static byte[] copyOf(byte[] original, int newLength) { 3163 byte[] copy = new byte[newLength]; 3164 System.arraycopy(original, 0, copy, 0, 3165 Math.min(original.length, newLength)); 3166 return copy; 3167 } 3168 3169 /** 3170 * Copies the specified array, truncating or padding with zeros (if necessary) 3171 * so the copy has the specified length. For all indices that are 3172 * valid in both the original array and the copy, the two arrays will 3173 * contain identical values. For any indices that are valid in the 3174 * copy but not the original, the copy will contain <tt>(short)0</tt>. 3175 * Such indices will exist if and only if the specified length 3176 * is greater than that of the original array. 3177 * 3178 * @param original the array to be copied 3179 * @param newLength the length of the copy to be returned 3180 * @return a copy of the original array, truncated or padded with zeros 3181 * to obtain the specified length 3182 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 3183 * @throws NullPointerException if <tt>original</tt> is null 3184 * @since 1.6 3185 */ 3186 public static short[] copyOf(short[] original, int newLength) { 3187 short[] copy = new short[newLength]; 3188 System.arraycopy(original, 0, copy, 0, 3189 Math.min(original.length, newLength)); 3190 return copy; 3191 } 3192 3193 /** 3194 * Copies the specified array, truncating or padding with zeros (if necessary) 3195 * so the copy has the specified length. For all indices that are 3196 * valid in both the original array and the copy, the two arrays will 3197 * contain identical values. For any indices that are valid in the 3198 * copy but not the original, the copy will contain <tt>0</tt>. 3199 * Such indices will exist if and only if the specified length 3200 * is greater than that of the original array. 3201 * 3202 * @param original the array to be copied 3203 * @param newLength the length of the copy to be returned 3204 * @return a copy of the original array, truncated or padded with zeros 3205 * to obtain the specified length 3206 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 3207 * @throws NullPointerException if <tt>original</tt> is null 3208 * @since 1.6 3209 */ 3210 public static int[] copyOf(int[] original, int newLength) { 3211 int[] copy = new int[newLength]; 3212 System.arraycopy(original, 0, copy, 0, 3213 Math.min(original.length, newLength)); 3214 return copy; 3215 } 3216 3217 /** 3218 * Copies the specified array, truncating or padding with zeros (if necessary) 3219 * so the copy has the specified length. For all indices that are 3220 * valid in both the original array and the copy, the two arrays will 3221 * contain identical values. For any indices that are valid in the 3222 * copy but not the original, the copy will contain <tt>0L</tt>. 3223 * Such indices will exist if and only if the specified length 3224 * is greater than that of the original array. 3225 * 3226 * @param original the array to be copied 3227 * @param newLength the length of the copy to be returned 3228 * @return a copy of the original array, truncated or padded with zeros 3229 * to obtain the specified length 3230 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 3231 * @throws NullPointerException if <tt>original</tt> is null 3232 * @since 1.6 3233 */ 3234 public static long[] copyOf(long[] original, int newLength) { 3235 long[] copy = new long[newLength]; 3236 System.arraycopy(original, 0, copy, 0, 3237 Math.min(original.length, newLength)); 3238 return copy; 3239 } 3240 3241 /** 3242 * Copies the specified array, truncating or padding with null characters (if necessary) 3243 * so the copy has the specified length. For all indices that are valid 3244 * in both the original array and the copy, the two arrays will contain 3245 * identical values. For any indices that are valid in the copy but not 3246 * the original, the copy will contain <tt>'\\u000'</tt>. Such indices 3247 * will exist if and only if the specified length is greater than that of 3248 * the original array. 3249 * 3250 * @param original the array to be copied 3251 * @param newLength the length of the copy to be returned 3252 * @return a copy of the original array, truncated or padded with null characters 3253 * to obtain the specified length 3254 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 3255 * @throws NullPointerException if <tt>original</tt> is null 3256 * @since 1.6 3257 */ 3258 public static char[] copyOf(char[] original, int newLength) { 3259 char[] copy = new char[newLength]; 3260 System.arraycopy(original, 0, copy, 0, 3261 Math.min(original.length, newLength)); 3262 return copy; 3263 } 3264 3265 /** 3266 * Copies the specified array, truncating or padding with zeros (if necessary) 3267 * so the copy has the specified length. For all indices that are 3268 * valid in both the original array and the copy, the two arrays will 3269 * contain identical values. For any indices that are valid in the 3270 * copy but not the original, the copy will contain <tt>0f</tt>. 3271 * Such indices will exist if and only if the specified length 3272 * is greater than that of the original array. 3273 * 3274 * @param original the array to be copied 3275 * @param newLength the length of the copy to be returned 3276 * @return a copy of the original array, truncated or padded with zeros 3277 * to obtain the specified length 3278 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 3279 * @throws NullPointerException if <tt>original</tt> is null 3280 * @since 1.6 3281 */ 3282 public static float[] copyOf(float[] original, int newLength) { 3283 float[] copy = new float[newLength]; 3284 System.arraycopy(original, 0, copy, 0, 3285 Math.min(original.length, newLength)); 3286 return copy; 3287 } 3288 3289 /** 3290 * Copies the specified array, truncating or padding with zeros (if necessary) 3291 * so the copy has the specified length. For all indices that are 3292 * valid in both the original array and the copy, the two arrays will 3293 * contain identical values. For any indices that are valid in the 3294 * copy but not the original, the copy will contain <tt>0d</tt>. 3295 * Such indices will exist if and only if the specified length 3296 * is greater than that of the original array. 3297 * 3298 * @param original the array to be copied 3299 * @param newLength the length of the copy to be returned 3300 * @return a copy of the original array, truncated or padded with zeros 3301 * to obtain the specified length 3302 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 3303 * @throws NullPointerException if <tt>original</tt> is null 3304 * @since 1.6 3305 */ 3306 public static double[] copyOf(double[] original, int newLength) { 3307 double[] copy = new double[newLength]; 3308 System.arraycopy(original, 0, copy, 0, 3309 Math.min(original.length, newLength)); 3310 return copy; 3311 } 3312 3313 /** 3314 * Copies the specified array, truncating or padding with <tt>false</tt> (if necessary) 3315 * so the copy has the specified length. For all indices that are 3316 * valid in both the original array and the copy, the two arrays will 3317 * contain identical values. For any indices that are valid in the 3318 * copy but not the original, the copy will contain <tt>false</tt>. 3319 * Such indices will exist if and only if the specified length 3320 * is greater than that of the original array. 3321 * 3322 * @param original the array to be copied 3323 * @param newLength the length of the copy to be returned 3324 * @return a copy of the original array, truncated or padded with false elements 3325 * to obtain the specified length 3326 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative 3327 * @throws NullPointerException if <tt>original</tt> is null 3328 * @since 1.6 3329 */ 3330 public static boolean[] copyOf(boolean[] original, int newLength) { 3331 boolean[] copy = new boolean[newLength]; 3332 System.arraycopy(original, 0, copy, 0, 3333 Math.min(original.length, newLength)); 3334 return copy; 3335 } 3336 3337 /** 3338 * Copies the specified range of the specified array into a new array. 3339 * The initial index of the range (<tt>from</tt>) must lie between zero 3340 * and <tt>original.length</tt>, inclusive. The value at 3341 * <tt>original[from]</tt> is placed into the initial element of the copy 3342 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 3343 * Values from subsequent elements in the original array are placed into 3344 * subsequent elements in the copy. The final index of the range 3345 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 3346 * may be greater than <tt>original.length</tt>, in which case 3347 * <tt>null</tt> is placed in all elements of the copy whose index is 3348 * greater than or equal to <tt>original.length - from</tt>. The length 3349 * of the returned array will be <tt>to - from</tt>. 3350 * <p> 3351 * The resulting array is of exactly the same class as the original array. 3352 * 3353 * @param <T> the class of the objects in the array 3354 * @param original the array from which a range is to be copied 3355 * @param from the initial index of the range to be copied, inclusive 3356 * @param to the final index of the range to be copied, exclusive. 3357 * (This index may lie outside the array.) 3358 * @return a new array containing the specified range from the original array, 3359 * truncated or padded with nulls to obtain the required length 3360 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 3361 * or {@code from > original.length} 3362 * @throws IllegalArgumentException if <tt>from > to</tt> 3363 * @throws NullPointerException if <tt>original</tt> is null 3364 * @since 1.6 3365 */ 3366 @SuppressWarnings("unchecked") 3367 public static <T> T[] copyOfRange(T[] original, int from, int to) { 3368 return copyOfRange(original, from, to, (Class<? extends T[]>) original.getClass()); 3369 } 3370 3371 /** 3372 * Copies the specified range of the specified array into a new array. 3373 * The initial index of the range (<tt>from</tt>) must lie between zero 3374 * and <tt>original.length</tt>, inclusive. The value at 3375 * <tt>original[from]</tt> is placed into the initial element of the copy 3376 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 3377 * Values from subsequent elements in the original array are placed into 3378 * subsequent elements in the copy. The final index of the range 3379 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 3380 * may be greater than <tt>original.length</tt>, in which case 3381 * <tt>null</tt> is placed in all elements of the copy whose index is 3382 * greater than or equal to <tt>original.length - from</tt>. The length 3383 * of the returned array will be <tt>to - from</tt>. 3384 * The resulting array is of the class <tt>newType</tt>. 3385 * 3386 * @param <U> the class of the objects in the original array 3387 * @param <T> the class of the objects in the returned array 3388 * @param original the array from which a range is to be copied 3389 * @param from the initial index of the range to be copied, inclusive 3390 * @param to the final index of the range to be copied, exclusive. 3391 * (This index may lie outside the array.) 3392 * @param newType the class of the copy to be returned 3393 * @return a new array containing the specified range from the original array, 3394 * truncated or padded with nulls to obtain the required length 3395 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 3396 * or {@code from > original.length} 3397 * @throws IllegalArgumentException if <tt>from > to</tt> 3398 * @throws NullPointerException if <tt>original</tt> is null 3399 * @throws ArrayStoreException if an element copied from 3400 * <tt>original</tt> is not of a runtime type that can be stored in 3401 * an array of class <tt>newType</tt>. 3402 * @since 1.6 3403 */ 3404 public static <T,U> T[] copyOfRange(U[] original, int from, int to, Class<? extends T[]> newType) { 3405 int newLength = to - from; 3406 if (newLength < 0) 3407 throw new IllegalArgumentException(from + " > " + to); 3408 @SuppressWarnings("unchecked") 3409 T[] copy = ((Object)newType == (Object)Object[].class) 3410 ? (T[]) new Object[newLength] 3411 : (T[]) Array.newInstance(newType.getComponentType(), newLength); 3412 System.arraycopy(original, from, copy, 0, 3413 Math.min(original.length - from, newLength)); 3414 return copy; 3415 } 3416 3417 /** 3418 * Copies the specified range of the specified array into a new array. 3419 * The initial index of the range (<tt>from</tt>) must lie between zero 3420 * and <tt>original.length</tt>, inclusive. The value at 3421 * <tt>original[from]</tt> is placed into the initial element of the copy 3422 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 3423 * Values from subsequent elements in the original array are placed into 3424 * subsequent elements in the copy. The final index of the range 3425 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 3426 * may be greater than <tt>original.length</tt>, in which case 3427 * <tt>(byte)0</tt> is placed in all elements of the copy whose index is 3428 * greater than or equal to <tt>original.length - from</tt>. The length 3429 * of the returned array will be <tt>to - from</tt>. 3430 * 3431 * @param original the array from which a range is to be copied 3432 * @param from the initial index of the range to be copied, inclusive 3433 * @param to the final index of the range to be copied, exclusive. 3434 * (This index may lie outside the array.) 3435 * @return a new array containing the specified range from the original array, 3436 * truncated or padded with zeros to obtain the required length 3437 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 3438 * or {@code from > original.length} 3439 * @throws IllegalArgumentException if <tt>from > to</tt> 3440 * @throws NullPointerException if <tt>original</tt> is null 3441 * @since 1.6 3442 */ 3443 public static byte[] copyOfRange(byte[] original, int from, int to) { 3444 int newLength = to - from; 3445 if (newLength < 0) 3446 throw new IllegalArgumentException(from + " > " + to); 3447 byte[] copy = new byte[newLength]; 3448 System.arraycopy(original, from, copy, 0, 3449 Math.min(original.length - from, newLength)); 3450 return copy; 3451 } 3452 3453 /** 3454 * Copies the specified range of the specified array into a new array. 3455 * The initial index of the range (<tt>from</tt>) must lie between zero 3456 * and <tt>original.length</tt>, inclusive. The value at 3457 * <tt>original[from]</tt> is placed into the initial element of the copy 3458 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 3459 * Values from subsequent elements in the original array are placed into 3460 * subsequent elements in the copy. The final index of the range 3461 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 3462 * may be greater than <tt>original.length</tt>, in which case 3463 * <tt>(short)0</tt> is placed in all elements of the copy whose index is 3464 * greater than or equal to <tt>original.length - from</tt>. The length 3465 * of the returned array will be <tt>to - from</tt>. 3466 * 3467 * @param original the array from which a range is to be copied 3468 * @param from the initial index of the range to be copied, inclusive 3469 * @param to the final index of the range to be copied, exclusive. 3470 * (This index may lie outside the array.) 3471 * @return a new array containing the specified range from the original array, 3472 * truncated or padded with zeros to obtain the required length 3473 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 3474 * or {@code from > original.length} 3475 * @throws IllegalArgumentException if <tt>from > to</tt> 3476 * @throws NullPointerException if <tt>original</tt> is null 3477 * @since 1.6 3478 */ 3479 public static short[] copyOfRange(short[] original, int from, int to) { 3480 int newLength = to - from; 3481 if (newLength < 0) 3482 throw new IllegalArgumentException(from + " > " + to); 3483 short[] copy = new short[newLength]; 3484 System.arraycopy(original, from, copy, 0, 3485 Math.min(original.length - from, newLength)); 3486 return copy; 3487 } 3488 3489 /** 3490 * Copies the specified range of the specified array into a new array. 3491 * The initial index of the range (<tt>from</tt>) must lie between zero 3492 * and <tt>original.length</tt>, inclusive. The value at 3493 * <tt>original[from]</tt> is placed into the initial element of the copy 3494 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 3495 * Values from subsequent elements in the original array are placed into 3496 * subsequent elements in the copy. The final index of the range 3497 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 3498 * may be greater than <tt>original.length</tt>, in which case 3499 * <tt>0</tt> is placed in all elements of the copy whose index is 3500 * greater than or equal to <tt>original.length - from</tt>. The length 3501 * of the returned array will be <tt>to - from</tt>. 3502 * 3503 * @param original the array from which a range is to be copied 3504 * @param from the initial index of the range to be copied, inclusive 3505 * @param to the final index of the range to be copied, exclusive. 3506 * (This index may lie outside the array.) 3507 * @return a new array containing the specified range from the original array, 3508 * truncated or padded with zeros to obtain the required length 3509 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 3510 * or {@code from > original.length} 3511 * @throws IllegalArgumentException if <tt>from > to</tt> 3512 * @throws NullPointerException if <tt>original</tt> is null 3513 * @since 1.6 3514 */ 3515 public static int[] copyOfRange(int[] original, int from, int to) { 3516 int newLength = to - from; 3517 if (newLength < 0) 3518 throw new IllegalArgumentException(from + " > " + to); 3519 int[] copy = new int[newLength]; 3520 System.arraycopy(original, from, copy, 0, 3521 Math.min(original.length - from, newLength)); 3522 return copy; 3523 } 3524 3525 /** 3526 * Copies the specified range of the specified array into a new array. 3527 * The initial index of the range (<tt>from</tt>) must lie between zero 3528 * and <tt>original.length</tt>, inclusive. The value at 3529 * <tt>original[from]</tt> is placed into the initial element of the copy 3530 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 3531 * Values from subsequent elements in the original array are placed into 3532 * subsequent elements in the copy. The final index of the range 3533 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 3534 * may be greater than <tt>original.length</tt>, in which case 3535 * <tt>0L</tt> is placed in all elements of the copy whose index is 3536 * greater than or equal to <tt>original.length - from</tt>. The length 3537 * of the returned array will be <tt>to - from</tt>. 3538 * 3539 * @param original the array from which a range is to be copied 3540 * @param from the initial index of the range to be copied, inclusive 3541 * @param to the final index of the range to be copied, exclusive. 3542 * (This index may lie outside the array.) 3543 * @return a new array containing the specified range from the original array, 3544 * truncated or padded with zeros to obtain the required length 3545 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 3546 * or {@code from > original.length} 3547 * @throws IllegalArgumentException if <tt>from > to</tt> 3548 * @throws NullPointerException if <tt>original</tt> is null 3549 * @since 1.6 3550 */ 3551 public static long[] copyOfRange(long[] original, int from, int to) { 3552 int newLength = to - from; 3553 if (newLength < 0) 3554 throw new IllegalArgumentException(from + " > " + to); 3555 long[] copy = new long[newLength]; 3556 System.arraycopy(original, from, copy, 0, 3557 Math.min(original.length - from, newLength)); 3558 return copy; 3559 } 3560 3561 /** 3562 * Copies the specified range of the specified array into a new array. 3563 * The initial index of the range (<tt>from</tt>) must lie between zero 3564 * and <tt>original.length</tt>, inclusive. The value at 3565 * <tt>original[from]</tt> is placed into the initial element of the copy 3566 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 3567 * Values from subsequent elements in the original array are placed into 3568 * subsequent elements in the copy. The final index of the range 3569 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 3570 * may be greater than <tt>original.length</tt>, in which case 3571 * <tt>'\\u000'</tt> is placed in all elements of the copy whose index is 3572 * greater than or equal to <tt>original.length - from</tt>. The length 3573 * of the returned array will be <tt>to - from</tt>. 3574 * 3575 * @param original the array from which a range is to be copied 3576 * @param from the initial index of the range to be copied, inclusive 3577 * @param to the final index of the range to be copied, exclusive. 3578 * (This index may lie outside the array.) 3579 * @return a new array containing the specified range from the original array, 3580 * truncated or padded with null characters to obtain the required length 3581 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 3582 * or {@code from > original.length} 3583 * @throws IllegalArgumentException if <tt>from > to</tt> 3584 * @throws NullPointerException if <tt>original</tt> is null 3585 * @since 1.6 3586 */ 3587 public static char[] copyOfRange(char[] original, int from, int to) { 3588 int newLength = to - from; 3589 if (newLength < 0) 3590 throw new IllegalArgumentException(from + " > " + to); 3591 char[] copy = new char[newLength]; 3592 System.arraycopy(original, from, copy, 0, 3593 Math.min(original.length - from, newLength)); 3594 return copy; 3595 } 3596 3597 /** 3598 * Copies the specified range of the specified array into a new array. 3599 * The initial index of the range (<tt>from</tt>) must lie between zero 3600 * and <tt>original.length</tt>, inclusive. The value at 3601 * <tt>original[from]</tt> is placed into the initial element of the copy 3602 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 3603 * Values from subsequent elements in the original array are placed into 3604 * subsequent elements in the copy. The final index of the range 3605 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 3606 * may be greater than <tt>original.length</tt>, in which case 3607 * <tt>0f</tt> is placed in all elements of the copy whose index is 3608 * greater than or equal to <tt>original.length - from</tt>. The length 3609 * of the returned array will be <tt>to - from</tt>. 3610 * 3611 * @param original the array from which a range is to be copied 3612 * @param from the initial index of the range to be copied, inclusive 3613 * @param to the final index of the range to be copied, exclusive. 3614 * (This index may lie outside the array.) 3615 * @return a new array containing the specified range from the original array, 3616 * truncated or padded with zeros to obtain the required length 3617 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 3618 * or {@code from > original.length} 3619 * @throws IllegalArgumentException if <tt>from > to</tt> 3620 * @throws NullPointerException if <tt>original</tt> is null 3621 * @since 1.6 3622 */ 3623 public static float[] copyOfRange(float[] original, int from, int to) { 3624 int newLength = to - from; 3625 if (newLength < 0) 3626 throw new IllegalArgumentException(from + " > " + to); 3627 float[] copy = new float[newLength]; 3628 System.arraycopy(original, from, copy, 0, 3629 Math.min(original.length - from, newLength)); 3630 return copy; 3631 } 3632 3633 /** 3634 * Copies the specified range of the specified array into a new array. 3635 * The initial index of the range (<tt>from</tt>) must lie between zero 3636 * and <tt>original.length</tt>, inclusive. The value at 3637 * <tt>original[from]</tt> is placed into the initial element of the copy 3638 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 3639 * Values from subsequent elements in the original array are placed into 3640 * subsequent elements in the copy. The final index of the range 3641 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 3642 * may be greater than <tt>original.length</tt>, in which case 3643 * <tt>0d</tt> is placed in all elements of the copy whose index is 3644 * greater than or equal to <tt>original.length - from</tt>. The length 3645 * of the returned array will be <tt>to - from</tt>. 3646 * 3647 * @param original the array from which a range is to be copied 3648 * @param from the initial index of the range to be copied, inclusive 3649 * @param to the final index of the range to be copied, exclusive. 3650 * (This index may lie outside the array.) 3651 * @return a new array containing the specified range from the original array, 3652 * truncated or padded with zeros to obtain the required length 3653 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 3654 * or {@code from > original.length} 3655 * @throws IllegalArgumentException if <tt>from > to</tt> 3656 * @throws NullPointerException if <tt>original</tt> is null 3657 * @since 1.6 3658 */ 3659 public static double[] copyOfRange(double[] original, int from, int to) { 3660 int newLength = to - from; 3661 if (newLength < 0) 3662 throw new IllegalArgumentException(from + " > " + to); 3663 double[] copy = new double[newLength]; 3664 System.arraycopy(original, from, copy, 0, 3665 Math.min(original.length - from, newLength)); 3666 return copy; 3667 } 3668 3669 /** 3670 * Copies the specified range of the specified array into a new array. 3671 * The initial index of the range (<tt>from</tt>) must lie between zero 3672 * and <tt>original.length</tt>, inclusive. The value at 3673 * <tt>original[from]</tt> is placed into the initial element of the copy 3674 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>). 3675 * Values from subsequent elements in the original array are placed into 3676 * subsequent elements in the copy. The final index of the range 3677 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>, 3678 * may be greater than <tt>original.length</tt>, in which case 3679 * <tt>false</tt> is placed in all elements of the copy whose index is 3680 * greater than or equal to <tt>original.length - from</tt>. The length 3681 * of the returned array will be <tt>to - from</tt>. 3682 * 3683 * @param original the array from which a range is to be copied 3684 * @param from the initial index of the range to be copied, inclusive 3685 * @param to the final index of the range to be copied, exclusive. 3686 * (This index may lie outside the array.) 3687 * @return a new array containing the specified range from the original array, 3688 * truncated or padded with false elements to obtain the required length 3689 * @throws ArrayIndexOutOfBoundsException if {@code from < 0} 3690 * or {@code from > original.length} 3691 * @throws IllegalArgumentException if <tt>from > to</tt> 3692 * @throws NullPointerException if <tt>original</tt> is null 3693 * @since 1.6 3694 */ 3695 public static boolean[] copyOfRange(boolean[] original, int from, int to) { 3696 int newLength = to - from; 3697 if (newLength < 0) 3698 throw new IllegalArgumentException(from + " > " + to); 3699 boolean[] copy = new boolean[newLength]; 3700 System.arraycopy(original, from, copy, 0, 3701 Math.min(original.length - from, newLength)); 3702 return copy; 3703 } 3704 3705 // Misc 3706 3707 /** 3708 * Returns a fixed-size list backed by the specified array. (Changes to 3709 * the returned list "write through" to the array.) This method acts 3710 * as bridge between array-based and collection-based APIs, in 3711 * combination with {@link Collection#toArray}. The returned list is 3712 * serializable and implements {@link RandomAccess}. 3713 * 3714 * <p>This method also provides a convenient way to create a fixed-size 3715 * list initialized to contain several elements: 3716 * <pre> 3717 * List<String> stooges = Arrays.asList("Larry", "Moe", "Curly"); 3718 * </pre> 3719 * 3720 * @param <T> the class of the objects in the array 3721 * @param a the array by which the list will be backed 3722 * @return a list view of the specified array 3723 */ 3724 @SafeVarargs 3725 @SuppressWarnings("varargs") 3726 public static <T> List<T> asList(T... a) { 3727 return new ArrayList<>(a); 3728 } 3729 3730 /** 3731 * @serial include 3732 */ 3733 private static class ArrayList<E> extends AbstractList<E> 3734 implements RandomAccess, java.io.Serializable 3735 { 3736 private static final long serialVersionUID = -2764017481108945198L; 3737 private final E[] a; 3738 3739 ArrayList(E[] array) { 3740 a = Objects.requireNonNull(array); 3741 } 3742 3743 @Override 3744 public int size() { 3745 return a.length; 3746 } 3747 3748 @Override 3749 public Object[] toArray() { 3750 return a.clone(); 3751 } 3752 3753 @Override 3754 @SuppressWarnings("unchecked") 3755 public <T> T[] toArray(T[] a) { 3756 int size = size(); 3757 if (a.length < size) 3758 return Arrays.copyOf(this.a, size, 3759 (Class<? extends T[]>) a.getClass()); 3760 System.arraycopy(this.a, 0, a, 0, size); 3761 if (a.length > size) 3762 a[size] = null; 3763 return a; 3764 } 3765 3766 @Override 3767 public E get(int index) { 3768 return a[index]; 3769 } 3770 3771 @Override 3772 public E set(int index, E element) { 3773 E oldValue = a[index]; 3774 a[index] = element; 3775 return oldValue; 3776 } 3777 3778 @Override 3779 public int indexOf(Object o) { 3780 E[] a = this.a; 3781 if (o == null) { 3782 for (int i = 0; i < a.length; i++) 3783 if (a[i] == null) 3784 return i; 3785 } else { 3786 for (int i = 0; i < a.length; i++) 3787 if (o.equals(a[i])) 3788 return i; 3789 } 3790 return -1; 3791 } 3792 3793 @Override 3794 public boolean contains(Object o) { 3795 return indexOf(o) != -1; 3796 } 3797 3798 @Override 3799 public Spliterator<E> spliterator() { 3800 return Spliterators.spliterator(a, Spliterator.ORDERED); 3801 } 3802 3803 @Override 3804 public void forEach(Consumer<? super E> action) { 3805 Objects.requireNonNull(action); 3806 for (E e : a) { 3807 action.accept(e); 3808 } 3809 } 3810 3811 @Override 3812 public void replaceAll(UnaryOperator<E> operator) { 3813 Objects.requireNonNull(operator); 3814 E[] a = this.a; 3815 for (int i = 0; i < a.length; i++) { 3816 a[i] = operator.apply(a[i]); 3817 } 3818 } 3819 3820 @Override 3821 public void sort(Comparator<? super E> c) { 3822 Arrays.sort(a, c); 3823 } 3824 } 3825 3826 /** 3827 * Returns a hash code based on the contents of the specified array. 3828 * For any two <tt>long</tt> arrays <tt>a</tt> and <tt>b</tt> 3829 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 3830 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 3831 * 3832 * <p>The value returned by this method is the same value that would be 3833 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 3834 * method on a {@link List} containing a sequence of {@link Long} 3835 * instances representing the elements of <tt>a</tt> in the same order. 3836 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 3837 * 3838 * @param a the array whose hash value to compute 3839 * @return a content-based hash code for <tt>a</tt> 3840 * @since 1.5 3841 */ 3842 public static int hashCode(long a[]) { 3843 if (a == null) 3844 return 0; 3845 3846 int result = 1; 3847 for (long element : a) { 3848 int elementHash = (int)(element ^ (element >>> 32)); 3849 result = 31 * result + elementHash; 3850 } 3851 3852 return result; 3853 } 3854 3855 /** 3856 * Returns a hash code based on the contents of the specified array. 3857 * For any two non-null <tt>int</tt> arrays <tt>a</tt> and <tt>b</tt> 3858 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 3859 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 3860 * 3861 * <p>The value returned by this method is the same value that would be 3862 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 3863 * method on a {@link List} containing a sequence of {@link Integer} 3864 * instances representing the elements of <tt>a</tt> in the same order. 3865 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 3866 * 3867 * @param a the array whose hash value to compute 3868 * @return a content-based hash code for <tt>a</tt> 3869 * @since 1.5 3870 */ 3871 public static int hashCode(int a[]) { 3872 if (a == null) 3873 return 0; 3874 3875 int result = 1; 3876 for (int element : a) 3877 result = 31 * result + element; 3878 3879 return result; 3880 } 3881 3882 /** 3883 * Returns a hash code based on the contents of the specified array. 3884 * For any two <tt>short</tt> arrays <tt>a</tt> and <tt>b</tt> 3885 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 3886 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 3887 * 3888 * <p>The value returned by this method is the same value that would be 3889 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 3890 * method on a {@link List} containing a sequence of {@link Short} 3891 * instances representing the elements of <tt>a</tt> in the same order. 3892 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 3893 * 3894 * @param a the array whose hash value to compute 3895 * @return a content-based hash code for <tt>a</tt> 3896 * @since 1.5 3897 */ 3898 public static int hashCode(short a[]) { 3899 if (a == null) 3900 return 0; 3901 3902 int result = 1; 3903 for (short element : a) 3904 result = 31 * result + element; 3905 3906 return result; 3907 } 3908 3909 /** 3910 * Returns a hash code based on the contents of the specified array. 3911 * For any two <tt>char</tt> arrays <tt>a</tt> and <tt>b</tt> 3912 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 3913 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 3914 * 3915 * <p>The value returned by this method is the same value that would be 3916 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 3917 * method on a {@link List} containing a sequence of {@link Character} 3918 * instances representing the elements of <tt>a</tt> in the same order. 3919 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 3920 * 3921 * @param a the array whose hash value to compute 3922 * @return a content-based hash code for <tt>a</tt> 3923 * @since 1.5 3924 */ 3925 public static int hashCode(char a[]) { 3926 if (a == null) 3927 return 0; 3928 3929 int result = 1; 3930 for (char element : a) 3931 result = 31 * result + element; 3932 3933 return result; 3934 } 3935 3936 /** 3937 * Returns a hash code based on the contents of the specified array. 3938 * For any two <tt>byte</tt> arrays <tt>a</tt> and <tt>b</tt> 3939 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 3940 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 3941 * 3942 * <p>The value returned by this method is the same value that would be 3943 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 3944 * method on a {@link List} containing a sequence of {@link Byte} 3945 * instances representing the elements of <tt>a</tt> in the same order. 3946 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 3947 * 3948 * @param a the array whose hash value to compute 3949 * @return a content-based hash code for <tt>a</tt> 3950 * @since 1.5 3951 */ 3952 public static int hashCode(byte a[]) { 3953 if (a == null) 3954 return 0; 3955 3956 int result = 1; 3957 for (byte element : a) 3958 result = 31 * result + element; 3959 3960 return result; 3961 } 3962 3963 /** 3964 * Returns a hash code based on the contents of the specified array. 3965 * For any two <tt>boolean</tt> arrays <tt>a</tt> and <tt>b</tt> 3966 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 3967 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 3968 * 3969 * <p>The value returned by this method is the same value that would be 3970 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 3971 * method on a {@link List} containing a sequence of {@link Boolean} 3972 * instances representing the elements of <tt>a</tt> in the same order. 3973 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 3974 * 3975 * @param a the array whose hash value to compute 3976 * @return a content-based hash code for <tt>a</tt> 3977 * @since 1.5 3978 */ 3979 public static int hashCode(boolean a[]) { 3980 if (a == null) 3981 return 0; 3982 3983 int result = 1; 3984 for (boolean element : a) 3985 result = 31 * result + (element ? 1231 : 1237); 3986 3987 return result; 3988 } 3989 3990 /** 3991 * Returns a hash code based on the contents of the specified array. 3992 * For any two <tt>float</tt> arrays <tt>a</tt> and <tt>b</tt> 3993 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 3994 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 3995 * 3996 * <p>The value returned by this method is the same value that would be 3997 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 3998 * method on a {@link List} containing a sequence of {@link Float} 3999 * instances representing the elements of <tt>a</tt> in the same order. 4000 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 4001 * 4002 * @param a the array whose hash value to compute 4003 * @return a content-based hash code for <tt>a</tt> 4004 * @since 1.5 4005 */ 4006 public static int hashCode(float a[]) { 4007 if (a == null) 4008 return 0; 4009 4010 int result = 1; 4011 for (float element : a) 4012 result = 31 * result + Float.floatToIntBits(element); 4013 4014 return result; 4015 } 4016 4017 /** 4018 * Returns a hash code based on the contents of the specified array. 4019 * For any two <tt>double</tt> arrays <tt>a</tt> and <tt>b</tt> 4020 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that 4021 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 4022 * 4023 * <p>The value returned by this method is the same value that would be 4024 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>} 4025 * method on a {@link List} containing a sequence of {@link Double} 4026 * instances representing the elements of <tt>a</tt> in the same order. 4027 * If <tt>a</tt> is <tt>null</tt>, this method returns 0. 4028 * 4029 * @param a the array whose hash value to compute 4030 * @return a content-based hash code for <tt>a</tt> 4031 * @since 1.5 4032 */ 4033 public static int hashCode(double a[]) { 4034 if (a == null) 4035 return 0; 4036 4037 int result = 1; 4038 for (double element : a) { 4039 long bits = Double.doubleToLongBits(element); 4040 result = 31 * result + (int)(bits ^ (bits >>> 32)); 4041 } 4042 return result; 4043 } 4044 4045 /** 4046 * Returns a hash code based on the contents of the specified array. If 4047 * the array contains other arrays as elements, the hash code is based on 4048 * their identities rather than their contents. It is therefore 4049 * acceptable to invoke this method on an array that contains itself as an 4050 * element, either directly or indirectly through one or more levels of 4051 * arrays. 4052 * 4053 * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that 4054 * <tt>Arrays.equals(a, b)</tt>, it is also the case that 4055 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>. 4056 * 4057 * <p>The value returned by this method is equal to the value that would 4058 * be returned by <tt>Arrays.asList(a).hashCode()</tt>, unless <tt>a</tt> 4059 * is <tt>null</tt>, in which case <tt>0</tt> is returned. 4060 * 4061 * @param a the array whose content-based hash code to compute 4062 * @return a content-based hash code for <tt>a</tt> 4063 * @see #deepHashCode(Object[]) 4064 * @since 1.5 4065 */ 4066 public static int hashCode(Object a[]) { 4067 if (a == null) 4068 return 0; 4069 4070 int result = 1; 4071 4072 for (Object element : a) 4073 result = 31 * result + (element == null ? 0 : element.hashCode()); 4074 4075 return result; 4076 } 4077 4078 /** 4079 * Returns a hash code based on the "deep contents" of the specified 4080 * array. If the array contains other arrays as elements, the 4081 * hash code is based on their contents and so on, ad infinitum. 4082 * It is therefore unacceptable to invoke this method on an array that 4083 * contains itself as an element, either directly or indirectly through 4084 * one or more levels of arrays. The behavior of such an invocation is 4085 * undefined. 4086 * 4087 * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that 4088 * <tt>Arrays.deepEquals(a, b)</tt>, it is also the case that 4089 * <tt>Arrays.deepHashCode(a) == Arrays.deepHashCode(b)</tt>. 4090 * 4091 * <p>The computation of the value returned by this method is similar to 4092 * that of the value returned by {@link List#hashCode()} on a list 4093 * containing the same elements as <tt>a</tt> in the same order, with one 4094 * difference: If an element <tt>e</tt> of <tt>a</tt> is itself an array, 4095 * its hash code is computed not by calling <tt>e.hashCode()</tt>, but as 4096 * by calling the appropriate overloading of <tt>Arrays.hashCode(e)</tt> 4097 * if <tt>e</tt> is an array of a primitive type, or as by calling 4098 * <tt>Arrays.deepHashCode(e)</tt> recursively if <tt>e</tt> is an array 4099 * of a reference type. If <tt>a</tt> is <tt>null</tt>, this method 4100 * returns 0. 4101 * 4102 * @param a the array whose deep-content-based hash code to compute 4103 * @return a deep-content-based hash code for <tt>a</tt> 4104 * @see #hashCode(Object[]) 4105 * @since 1.5 4106 */ 4107 public static int deepHashCode(Object a[]) { 4108 if (a == null) 4109 return 0; 4110 4111 int result = 1; 4112 4113 for (Object element : a) { 4114 int elementHash = 0; 4115 // Android-changed: getComponentType() is faster than instanceof() 4116 if (element != null) { 4117 Class<?> cl = element.getClass().getComponentType(); 4118 if (cl == null) 4119 elementHash = element.hashCode(); 4120 else if (element instanceof Object[]) 4121 elementHash = deepHashCode((Object[]) element); 4122 else if (cl == byte.class) 4123 elementHash = hashCode((byte[]) element); 4124 else if (cl == short.class) 4125 elementHash = hashCode((short[]) element); 4126 else if (cl == int.class) 4127 elementHash = hashCode((int[]) element); 4128 else if (cl == long.class) 4129 elementHash = hashCode((long[]) element); 4130 else if (cl == char.class) 4131 elementHash = hashCode((char[]) element); 4132 else if (cl == float.class) 4133 elementHash = hashCode((float[]) element); 4134 else if (cl == double.class) 4135 elementHash = hashCode((double[]) element); 4136 else if (cl == boolean.class) 4137 elementHash = hashCode((boolean[]) element); 4138 else 4139 elementHash = element.hashCode(); 4140 } 4141 result = 31 * result + elementHash; 4142 } 4143 4144 return result; 4145 } 4146 4147 /** 4148 * Returns <tt>true</tt> if the two specified arrays are <i>deeply 4149 * equal</i> to one another. Unlike the {@link #equals(Object[],Object[])} 4150 * method, this method is appropriate for use with nested arrays of 4151 * arbitrary depth. 4152 * 4153 * <p>Two array references are considered deeply equal if both 4154 * are <tt>null</tt>, or if they refer to arrays that contain the same 4155 * number of elements and all corresponding pairs of elements in the two 4156 * arrays are deeply equal. 4157 * 4158 * <p>Two possibly <tt>null</tt> elements <tt>e1</tt> and <tt>e2</tt> are 4159 * deeply equal if any of the following conditions hold: 4160 * <ul> 4161 * <li> <tt>e1</tt> and <tt>e2</tt> are both arrays of object reference 4162 * types, and <tt>Arrays.deepEquals(e1, e2) would return true</tt> 4163 * <li> <tt>e1</tt> and <tt>e2</tt> are arrays of the same primitive 4164 * type, and the appropriate overloading of 4165 * <tt>Arrays.equals(e1, e2)</tt> would return true. 4166 * <li> <tt>e1 == e2</tt> 4167 * <li> <tt>e1.equals(e2)</tt> would return true. 4168 * </ul> 4169 * Note that this definition permits <tt>null</tt> elements at any depth. 4170 * 4171 * <p>If either of the specified arrays contain themselves as elements 4172 * either directly or indirectly through one or more levels of arrays, 4173 * the behavior of this method is undefined. 4174 * 4175 * @param a1 one array to be tested for equality 4176 * @param a2 the other array to be tested for equality 4177 * @return <tt>true</tt> if the two arrays are equal 4178 * @see #equals(Object[],Object[]) 4179 * @see Objects#deepEquals(Object, Object) 4180 * @since 1.5 4181 */ 4182 public static boolean deepEquals(Object[] a1, Object[] a2) { 4183 if (a1 == a2) 4184 return true; 4185 if (a1 == null || a2==null) 4186 return false; 4187 int length = a1.length; 4188 if (a2.length != length) 4189 return false; 4190 4191 for (int i = 0; i < length; i++) { 4192 Object e1 = a1[i]; 4193 Object e2 = a2[i]; 4194 4195 if (e1 == e2) 4196 continue; 4197 // Android-changed: Return early if e2 == null 4198 if (e1 == null || e2 == null) 4199 return false; 4200 4201 // Figure out whether the two elements are equal 4202 boolean eq = deepEquals0(e1, e2); 4203 4204 if (!eq) 4205 return false; 4206 } 4207 return true; 4208 } 4209 4210 static boolean deepEquals0(Object e1, Object e2) { 4211 // Android-changed: getComponentType() is faster than instanceof() 4212 Class<?> cl1 = e1.getClass().getComponentType(); 4213 Class<?> cl2 = e2.getClass().getComponentType(); 4214 4215 if (cl1 != cl2) { 4216 return false; 4217 } 4218 if (e1 instanceof Object[]) 4219 return deepEquals ((Object[]) e1, (Object[]) e2); 4220 else if (cl1 == byte.class) 4221 return equals((byte[]) e1, (byte[]) e2); 4222 else if (cl1 == short.class) 4223 return equals((short[]) e1, (short[]) e2); 4224 else if (cl1 == int.class) 4225 return equals((int[]) e1, (int[]) e2); 4226 else if (cl1 == long.class) 4227 return equals((long[]) e1, (long[]) e2); 4228 else if (cl1 == char.class) 4229 return equals((char[]) e1, (char[]) e2); 4230 else if (cl1 == float.class) 4231 return equals((float[]) e1, (float[]) e2); 4232 else if (cl1 == double.class) 4233 return equals((double[]) e1, (double[]) e2); 4234 else if (cl1 == boolean.class) 4235 return equals((boolean[]) e1, (boolean[]) e2); 4236 else 4237 return e1.equals(e2); 4238 } 4239 4240 /** 4241 * Returns a string representation of the contents of the specified array. 4242 * The string representation consists of a list of the array's elements, 4243 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 4244 * separated by the characters <tt>", "</tt> (a comma followed by a 4245 * space). Elements are converted to strings as by 4246 * <tt>String.valueOf(long)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> 4247 * is <tt>null</tt>. 4248 * 4249 * @param a the array whose string representation to return 4250 * @return a string representation of <tt>a</tt> 4251 * @since 1.5 4252 */ 4253 public static String toString(long[] a) { 4254 if (a == null) 4255 return "null"; 4256 int iMax = a.length - 1; 4257 if (iMax == -1) 4258 return "[]"; 4259 4260 StringBuilder b = new StringBuilder(); 4261 b.append('['); 4262 for (int i = 0; ; i++) { 4263 b.append(a[i]); 4264 if (i == iMax) 4265 return b.append(']').toString(); 4266 b.append(", "); 4267 } 4268 } 4269 4270 /** 4271 * Returns a string representation of the contents of the specified array. 4272 * The string representation consists of a list of the array's elements, 4273 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 4274 * separated by the characters <tt>", "</tt> (a comma followed by a 4275 * space). Elements are converted to strings as by 4276 * <tt>String.valueOf(int)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> is 4277 * <tt>null</tt>. 4278 * 4279 * @param a the array whose string representation to return 4280 * @return a string representation of <tt>a</tt> 4281 * @since 1.5 4282 */ 4283 public static String toString(int[] a) { 4284 if (a == null) 4285 return "null"; 4286 int iMax = a.length - 1; 4287 if (iMax == -1) 4288 return "[]"; 4289 4290 StringBuilder b = new StringBuilder(); 4291 b.append('['); 4292 for (int i = 0; ; i++) { 4293 b.append(a[i]); 4294 if (i == iMax) 4295 return b.append(']').toString(); 4296 b.append(", "); 4297 } 4298 } 4299 4300 /** 4301 * Returns a string representation of the contents of the specified array. 4302 * The string representation consists of a list of the array's elements, 4303 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 4304 * separated by the characters <tt>", "</tt> (a comma followed by a 4305 * space). Elements are converted to strings as by 4306 * <tt>String.valueOf(short)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> 4307 * is <tt>null</tt>. 4308 * 4309 * @param a the array whose string representation to return 4310 * @return a string representation of <tt>a</tt> 4311 * @since 1.5 4312 */ 4313 public static String toString(short[] a) { 4314 if (a == null) 4315 return "null"; 4316 int iMax = a.length - 1; 4317 if (iMax == -1) 4318 return "[]"; 4319 4320 StringBuilder b = new StringBuilder(); 4321 b.append('['); 4322 for (int i = 0; ; i++) { 4323 b.append(a[i]); 4324 if (i == iMax) 4325 return b.append(']').toString(); 4326 b.append(", "); 4327 } 4328 } 4329 4330 /** 4331 * Returns a string representation of the contents of the specified array. 4332 * The string representation consists of a list of the array's elements, 4333 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 4334 * separated by the characters <tt>", "</tt> (a comma followed by a 4335 * space). Elements are converted to strings as by 4336 * <tt>String.valueOf(char)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> 4337 * is <tt>null</tt>. 4338 * 4339 * @param a the array whose string representation to return 4340 * @return a string representation of <tt>a</tt> 4341 * @since 1.5 4342 */ 4343 public static String toString(char[] a) { 4344 if (a == null) 4345 return "null"; 4346 int iMax = a.length - 1; 4347 if (iMax == -1) 4348 return "[]"; 4349 4350 StringBuilder b = new StringBuilder(); 4351 b.append('['); 4352 for (int i = 0; ; i++) { 4353 b.append(a[i]); 4354 if (i == iMax) 4355 return b.append(']').toString(); 4356 b.append(", "); 4357 } 4358 } 4359 4360 /** 4361 * Returns a string representation of the contents of the specified array. 4362 * The string representation consists of a list of the array's elements, 4363 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements 4364 * are separated by the characters <tt>", "</tt> (a comma followed 4365 * by a space). Elements are converted to strings as by 4366 * <tt>String.valueOf(byte)</tt>. Returns <tt>"null"</tt> if 4367 * <tt>a</tt> is <tt>null</tt>. 4368 * 4369 * @param a the array whose string representation to return 4370 * @return a string representation of <tt>a</tt> 4371 * @since 1.5 4372 */ 4373 public static String toString(byte[] a) { 4374 if (a == null) 4375 return "null"; 4376 int iMax = a.length - 1; 4377 if (iMax == -1) 4378 return "[]"; 4379 4380 StringBuilder b = new StringBuilder(); 4381 b.append('['); 4382 for (int i = 0; ; i++) { 4383 b.append(a[i]); 4384 if (i == iMax) 4385 return b.append(']').toString(); 4386 b.append(", "); 4387 } 4388 } 4389 4390 /** 4391 * Returns a string representation of the contents of the specified array. 4392 * The string representation consists of a list of the array's elements, 4393 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 4394 * separated by the characters <tt>", "</tt> (a comma followed by a 4395 * space). Elements are converted to strings as by 4396 * <tt>String.valueOf(boolean)</tt>. Returns <tt>"null"</tt> if 4397 * <tt>a</tt> is <tt>null</tt>. 4398 * 4399 * @param a the array whose string representation to return 4400 * @return a string representation of <tt>a</tt> 4401 * @since 1.5 4402 */ 4403 public static String toString(boolean[] a) { 4404 if (a == null) 4405 return "null"; 4406 int iMax = a.length - 1; 4407 if (iMax == -1) 4408 return "[]"; 4409 4410 StringBuilder b = new StringBuilder(); 4411 b.append('['); 4412 for (int i = 0; ; i++) { 4413 b.append(a[i]); 4414 if (i == iMax) 4415 return b.append(']').toString(); 4416 b.append(", "); 4417 } 4418 } 4419 4420 /** 4421 * Returns a string representation of the contents of the specified array. 4422 * The string representation consists of a list of the array's elements, 4423 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 4424 * separated by the characters <tt>", "</tt> (a comma followed by a 4425 * space). Elements are converted to strings as by 4426 * <tt>String.valueOf(float)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> 4427 * is <tt>null</tt>. 4428 * 4429 * @param a the array whose string representation to return 4430 * @return a string representation of <tt>a</tt> 4431 * @since 1.5 4432 */ 4433 public static String toString(float[] a) { 4434 if (a == null) 4435 return "null"; 4436 4437 int iMax = a.length - 1; 4438 if (iMax == -1) 4439 return "[]"; 4440 4441 StringBuilder b = new StringBuilder(); 4442 b.append('['); 4443 for (int i = 0; ; i++) { 4444 b.append(a[i]); 4445 if (i == iMax) 4446 return b.append(']').toString(); 4447 b.append(", "); 4448 } 4449 } 4450 4451 /** 4452 * Returns a string representation of the contents of the specified array. 4453 * The string representation consists of a list of the array's elements, 4454 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are 4455 * separated by the characters <tt>", "</tt> (a comma followed by a 4456 * space). Elements are converted to strings as by 4457 * <tt>String.valueOf(double)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> 4458 * is <tt>null</tt>. 4459 * 4460 * @param a the array whose string representation to return 4461 * @return a string representation of <tt>a</tt> 4462 * @since 1.5 4463 */ 4464 public static String toString(double[] a) { 4465 if (a == null) 4466 return "null"; 4467 int iMax = a.length - 1; 4468 if (iMax == -1) 4469 return "[]"; 4470 4471 StringBuilder b = new StringBuilder(); 4472 b.append('['); 4473 for (int i = 0; ; i++) { 4474 b.append(a[i]); 4475 if (i == iMax) 4476 return b.append(']').toString(); 4477 b.append(", "); 4478 } 4479 } 4480 4481 /** 4482 * Returns a string representation of the contents of the specified array. 4483 * If the array contains other arrays as elements, they are converted to 4484 * strings by the {@link Object#toString} method inherited from 4485 * <tt>Object</tt>, which describes their <i>identities</i> rather than 4486 * their contents. 4487 * 4488 * <p>The value returned by this method is equal to the value that would 4489 * be returned by <tt>Arrays.asList(a).toString()</tt>, unless <tt>a</tt> 4490 * is <tt>null</tt>, in which case <tt>"null"</tt> is returned. 4491 * 4492 * @param a the array whose string representation to return 4493 * @return a string representation of <tt>a</tt> 4494 * @see #deepToString(Object[]) 4495 * @since 1.5 4496 */ 4497 public static String toString(Object[] a) { 4498 if (a == null) 4499 return "null"; 4500 4501 int iMax = a.length - 1; 4502 if (iMax == -1) 4503 return "[]"; 4504 4505 StringBuilder b = new StringBuilder(); 4506 b.append('['); 4507 for (int i = 0; ; i++) { 4508 b.append(String.valueOf(a[i])); 4509 if (i == iMax) 4510 return b.append(']').toString(); 4511 b.append(", "); 4512 } 4513 } 4514 4515 /** 4516 * Returns a string representation of the "deep contents" of the specified 4517 * array. If the array contains other arrays as elements, the string 4518 * representation contains their contents and so on. This method is 4519 * designed for converting multidimensional arrays to strings. 4520 * 4521 * <p>The string representation consists of a list of the array's 4522 * elements, enclosed in square brackets (<tt>"[]"</tt>). Adjacent 4523 * elements are separated by the characters <tt>", "</tt> (a comma 4524 * followed by a space). Elements are converted to strings as by 4525 * <tt>String.valueOf(Object)</tt>, unless they are themselves 4526 * arrays. 4527 * 4528 * <p>If an element <tt>e</tt> is an array of a primitive type, it is 4529 * converted to a string as by invoking the appropriate overloading of 4530 * <tt>Arrays.toString(e)</tt>. If an element <tt>e</tt> is an array of a 4531 * reference type, it is converted to a string as by invoking 4532 * this method recursively. 4533 * 4534 * <p>To avoid infinite recursion, if the specified array contains itself 4535 * as an element, or contains an indirect reference to itself through one 4536 * or more levels of arrays, the self-reference is converted to the string 4537 * <tt>"[...]"</tt>. For example, an array containing only a reference 4538 * to itself would be rendered as <tt>"[[...]]"</tt>. 4539 * 4540 * <p>This method returns <tt>"null"</tt> if the specified array 4541 * is <tt>null</tt>. 4542 * 4543 * @param a the array whose string representation to return 4544 * @return a string representation of <tt>a</tt> 4545 * @see #toString(Object[]) 4546 * @since 1.5 4547 */ 4548 public static String deepToString(Object[] a) { 4549 if (a == null) 4550 return "null"; 4551 4552 int bufLen = 20 * a.length; 4553 if (a.length != 0 && bufLen <= 0) 4554 bufLen = Integer.MAX_VALUE; 4555 StringBuilder buf = new StringBuilder(bufLen); 4556 deepToString(a, buf, new HashSet<Object[]>()); 4557 return buf.toString(); 4558 } 4559 4560 private static void deepToString(Object[] a, StringBuilder buf, 4561 Set<Object[]> dejaVu) { 4562 if (a == null) { 4563 buf.append("null"); 4564 return; 4565 } 4566 int iMax = a.length - 1; 4567 if (iMax == -1) { 4568 buf.append("[]"); 4569 return; 4570 } 4571 4572 dejaVu.add(a); 4573 buf.append('['); 4574 for (int i = 0; ; i++) { 4575 4576 Object element = a[i]; 4577 if (element == null) { 4578 buf.append("null"); 4579 } else { 4580 Class<?> eClass = element.getClass(); 4581 4582 if (eClass.isArray()) { 4583 if (eClass == byte[].class) 4584 buf.append(toString((byte[]) element)); 4585 else if (eClass == short[].class) 4586 buf.append(toString((short[]) element)); 4587 else if (eClass == int[].class) 4588 buf.append(toString((int[]) element)); 4589 else if (eClass == long[].class) 4590 buf.append(toString((long[]) element)); 4591 else if (eClass == char[].class) 4592 buf.append(toString((char[]) element)); 4593 else if (eClass == float[].class) 4594 buf.append(toString((float[]) element)); 4595 else if (eClass == double[].class) 4596 buf.append(toString((double[]) element)); 4597 else if (eClass == boolean[].class) 4598 buf.append(toString((boolean[]) element)); 4599 else { // element is an array of object references 4600 if (dejaVu.contains(element)) 4601 buf.append("[...]"); 4602 else 4603 deepToString((Object[])element, buf, dejaVu); 4604 } 4605 } else { // element is non-null and not an array 4606 buf.append(element.toString()); 4607 } 4608 } 4609 if (i == iMax) 4610 break; 4611 buf.append(", "); 4612 } 4613 buf.append(']'); 4614 dejaVu.remove(a); 4615 } 4616 4617 4618 /** 4619 * Set all elements of the specified array, using the provided 4620 * generator function to compute each element. 4621 * 4622 * <p>If the generator function throws an exception, it is relayed to 4623 * the caller and the array is left in an indeterminate state. 4624 * 4625 * @param <T> type of elements of the array 4626 * @param array array to be initialized 4627 * @param generator a function accepting an index and producing the desired 4628 * value for that position 4629 * @throws NullPointerException if the generator is null 4630 * @since 1.8 4631 */ 4632 public static <T> void setAll(T[] array, IntFunction<? extends T> generator) { 4633 Objects.requireNonNull(generator); 4634 for (int i = 0; i < array.length; i++) 4635 array[i] = generator.apply(i); 4636 } 4637 4638 /** 4639 * Set all elements of the specified array, in parallel, using the 4640 * provided generator function to compute each element. 4641 * 4642 * <p>If the generator function throws an exception, an unchecked exception 4643 * is thrown from {@code parallelSetAll} and the array is left in an 4644 * indeterminate state. 4645 * 4646 * @param <T> type of elements of the array 4647 * @param array array to be initialized 4648 * @param generator a function accepting an index and producing the desired 4649 * value for that position 4650 * @throws NullPointerException if the generator is null 4651 * @since 1.8 4652 */ 4653 public static <T> void parallelSetAll(T[] array, IntFunction<? extends T> generator) { 4654 Objects.requireNonNull(generator); 4655 IntStream.range(0, array.length).parallel().forEach(i -> { array[i] = generator.apply(i); }); 4656 } 4657 4658 /** 4659 * Set all elements of the specified array, using the provided 4660 * generator function to compute each element. 4661 * 4662 * <p>If the generator function throws an exception, it is relayed to 4663 * the caller and the array is left in an indeterminate state. 4664 * 4665 * @param array array to be initialized 4666 * @param generator a function accepting an index and producing the desired 4667 * value for that position 4668 * @throws NullPointerException if the generator is null 4669 * @since 1.8 4670 */ 4671 public static void setAll(int[] array, IntUnaryOperator generator) { 4672 Objects.requireNonNull(generator); 4673 for (int i = 0; i < array.length; i++) 4674 array[i] = generator.applyAsInt(i); 4675 } 4676 4677 /** 4678 * Set all elements of the specified array, in parallel, using the 4679 * provided generator function to compute each element. 4680 * 4681 * <p>If the generator function throws an exception, an unchecked exception 4682 * is thrown from {@code parallelSetAll} and the array is left in an 4683 * indeterminate state. 4684 * 4685 * @param array array to be initialized 4686 * @param generator a function accepting an index and producing the desired 4687 * value for that position 4688 * @throws NullPointerException if the generator is null 4689 * @since 1.8 4690 */ 4691 public static void parallelSetAll(int[] array, IntUnaryOperator generator) { 4692 Objects.requireNonNull(generator); 4693 IntStream.range(0, array.length).parallel().forEach(i -> { array[i] = generator.applyAsInt(i); }); 4694 } 4695 4696 /** 4697 * Set all elements of the specified array, using the provided 4698 * generator function to compute each element. 4699 * 4700 * <p>If the generator function throws an exception, it is relayed to 4701 * the caller and the array is left in an indeterminate state. 4702 * 4703 * @param array array to be initialized 4704 * @param generator a function accepting an index and producing the desired 4705 * value for that position 4706 * @throws NullPointerException if the generator is null 4707 * @since 1.8 4708 */ 4709 public static void setAll(long[] array, IntToLongFunction generator) { 4710 Objects.requireNonNull(generator); 4711 for (int i = 0; i < array.length; i++) 4712 array[i] = generator.applyAsLong(i); 4713 } 4714 4715 /** 4716 * Set all elements of the specified array, in parallel, using the 4717 * provided generator function to compute each element. 4718 * 4719 * <p>If the generator function throws an exception, an unchecked exception 4720 * is thrown from {@code parallelSetAll} and the array is left in an 4721 * indeterminate state. 4722 * 4723 * @param array array to be initialized 4724 * @param generator a function accepting an index and producing the desired 4725 * value for that position 4726 * @throws NullPointerException if the generator is null 4727 * @since 1.8 4728 */ 4729 public static void parallelSetAll(long[] array, IntToLongFunction generator) { 4730 Objects.requireNonNull(generator); 4731 IntStream.range(0, array.length).parallel().forEach(i -> { array[i] = generator.applyAsLong(i); }); 4732 } 4733 4734 /** 4735 * Set all elements of the specified array, using the provided 4736 * generator function to compute each element. 4737 * 4738 * <p>If the generator function throws an exception, it is relayed to 4739 * the caller and the array is left in an indeterminate state. 4740 * 4741 * @param array array to be initialized 4742 * @param generator a function accepting an index and producing the desired 4743 * value for that position 4744 * @throws NullPointerException if the generator is null 4745 * @since 1.8 4746 */ 4747 public static void setAll(double[] array, IntToDoubleFunction generator) { 4748 Objects.requireNonNull(generator); 4749 for (int i = 0; i < array.length; i++) 4750 array[i] = generator.applyAsDouble(i); 4751 } 4752 4753 /** 4754 * Set all elements of the specified array, in parallel, using the 4755 * provided generator function to compute each element. 4756 * 4757 * <p>If the generator function throws an exception, an unchecked exception 4758 * is thrown from {@code parallelSetAll} and the array is left in an 4759 * indeterminate state. 4760 * 4761 * @param array array to be initialized 4762 * @param generator a function accepting an index and producing the desired 4763 * value for that position 4764 * @throws NullPointerException if the generator is null 4765 * @since 1.8 4766 */ 4767 public static void parallelSetAll(double[] array, IntToDoubleFunction generator) { 4768 Objects.requireNonNull(generator); 4769 IntStream.range(0, array.length).parallel().forEach(i -> { array[i] = generator.applyAsDouble(i); }); 4770 } 4771 4772 /** 4773 * Returns a {@link Spliterator} covering all of the specified array. 4774 * 4775 * <p>The spliterator reports {@link Spliterator#SIZED}, 4776 * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and 4777 * {@link Spliterator#IMMUTABLE}. 4778 * 4779 * @param <T> type of elements 4780 * @param array the array, assumed to be unmodified during use 4781 * @return a spliterator for the array elements 4782 * @since 1.8 4783 */ 4784 public static <T> Spliterator<T> spliterator(T[] array) { 4785 return Spliterators.spliterator(array, 4786 Spliterator.ORDERED | Spliterator.IMMUTABLE); 4787 } 4788 4789 /** 4790 * Returns a {@link Spliterator} covering the specified range of the 4791 * specified array. 4792 * 4793 * <p>The spliterator reports {@link Spliterator#SIZED}, 4794 * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and 4795 * {@link Spliterator#IMMUTABLE}. 4796 * 4797 * @param <T> type of elements 4798 * @param array the array, assumed to be unmodified during use 4799 * @param startInclusive the first index to cover, inclusive 4800 * @param endExclusive index immediately past the last index to cover 4801 * @return a spliterator for the array elements 4802 * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is 4803 * negative, {@code endExclusive} is less than 4804 * {@code startInclusive}, or {@code endExclusive} is greater than 4805 * the array size 4806 * @since 1.8 4807 */ 4808 public static <T> Spliterator<T> spliterator(T[] array, int startInclusive, int endExclusive) { 4809 return Spliterators.spliterator(array, startInclusive, endExclusive, 4810 Spliterator.ORDERED | Spliterator.IMMUTABLE); 4811 } 4812 4813 /** 4814 * Returns a {@link Spliterator.OfInt} covering all of the specified array. 4815 * 4816 * <p>The spliterator reports {@link Spliterator#SIZED}, 4817 * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and 4818 * {@link Spliterator#IMMUTABLE}. 4819 * 4820 * @param array the array, assumed to be unmodified during use 4821 * @return a spliterator for the array elements 4822 * @since 1.8 4823 */ 4824 public static Spliterator.OfInt spliterator(int[] array) { 4825 return Spliterators.spliterator(array, 4826 Spliterator.ORDERED | Spliterator.IMMUTABLE); 4827 } 4828 4829 /** 4830 * Returns a {@link Spliterator.OfInt} covering the specified range of the 4831 * specified array. 4832 * 4833 * <p>The spliterator reports {@link Spliterator#SIZED}, 4834 * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and 4835 * {@link Spliterator#IMMUTABLE}. 4836 * 4837 * @param array the array, assumed to be unmodified during use 4838 * @param startInclusive the first index to cover, inclusive 4839 * @param endExclusive index immediately past the last index to cover 4840 * @return a spliterator for the array elements 4841 * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is 4842 * negative, {@code endExclusive} is less than 4843 * {@code startInclusive}, or {@code endExclusive} is greater than 4844 * the array size 4845 * @since 1.8 4846 */ 4847 public static Spliterator.OfInt spliterator(int[] array, int startInclusive, int endExclusive) { 4848 return Spliterators.spliterator(array, startInclusive, endExclusive, 4849 Spliterator.ORDERED | Spliterator.IMMUTABLE); 4850 } 4851 4852 /** 4853 * Returns a {@link Spliterator.OfLong} covering all of the specified array. 4854 * 4855 * <p>The spliterator reports {@link Spliterator#SIZED}, 4856 * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and 4857 * {@link Spliterator#IMMUTABLE}. 4858 * 4859 * @param array the array, assumed to be unmodified during use 4860 * @return the spliterator for the array elements 4861 * @since 1.8 4862 */ 4863 public static Spliterator.OfLong spliterator(long[] array) { 4864 return Spliterators.spliterator(array, 4865 Spliterator.ORDERED | Spliterator.IMMUTABLE); 4866 } 4867 4868 /** 4869 * Returns a {@link Spliterator.OfLong} covering the specified range of the 4870 * specified array. 4871 * 4872 * <p>The spliterator reports {@link Spliterator#SIZED}, 4873 * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and 4874 * {@link Spliterator#IMMUTABLE}. 4875 * 4876 * @param array the array, assumed to be unmodified during use 4877 * @param startInclusive the first index to cover, inclusive 4878 * @param endExclusive index immediately past the last index to cover 4879 * @return a spliterator for the array elements 4880 * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is 4881 * negative, {@code endExclusive} is less than 4882 * {@code startInclusive}, or {@code endExclusive} is greater than 4883 * the array size 4884 * @since 1.8 4885 */ 4886 public static Spliterator.OfLong spliterator(long[] array, int startInclusive, int endExclusive) { 4887 return Spliterators.spliterator(array, startInclusive, endExclusive, 4888 Spliterator.ORDERED | Spliterator.IMMUTABLE); 4889 } 4890 4891 /** 4892 * Returns a {@link Spliterator.OfDouble} covering all of the specified 4893 * array. 4894 * 4895 * <p>The spliterator reports {@link Spliterator#SIZED}, 4896 * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and 4897 * {@link Spliterator#IMMUTABLE}. 4898 * 4899 * @param array the array, assumed to be unmodified during use 4900 * @return a spliterator for the array elements 4901 * @since 1.8 4902 */ 4903 public static Spliterator.OfDouble spliterator(double[] array) { 4904 return Spliterators.spliterator(array, 4905 Spliterator.ORDERED | Spliterator.IMMUTABLE); 4906 } 4907 4908 /** 4909 * Returns a {@link Spliterator.OfDouble} covering the specified range of 4910 * the specified array. 4911 * 4912 * <p>The spliterator reports {@link Spliterator#SIZED}, 4913 * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and 4914 * {@link Spliterator#IMMUTABLE}. 4915 * 4916 * @param array the array, assumed to be unmodified during use 4917 * @param startInclusive the first index to cover, inclusive 4918 * @param endExclusive index immediately past the last index to cover 4919 * @return a spliterator for the array elements 4920 * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is 4921 * negative, {@code endExclusive} is less than 4922 * {@code startInclusive}, or {@code endExclusive} is greater than 4923 * the array size 4924 * @since 1.8 4925 */ 4926 public static Spliterator.OfDouble spliterator(double[] array, int startInclusive, int endExclusive) { 4927 return Spliterators.spliterator(array, startInclusive, endExclusive, 4928 Spliterator.ORDERED | Spliterator.IMMUTABLE); 4929 } 4930 4931 /** 4932 * Returns a sequential {@link Stream} with the specified array as its 4933 * source. 4934 * 4935 * @param <T> The type of the array elements 4936 * @param array The array, assumed to be unmodified during use 4937 * @return a {@code Stream} for the array 4938 * @since 1.8 4939 */ 4940 public static <T> Stream<T> stream(T[] array) { 4941 return stream(array, 0, array.length); 4942 } 4943 4944 /** 4945 * Returns a sequential {@link Stream} with the specified range of the 4946 * specified array as its source. 4947 * 4948 * @param <T> the type of the array elements 4949 * @param array the array, assumed to be unmodified during use 4950 * @param startInclusive the first index to cover, inclusive 4951 * @param endExclusive index immediately past the last index to cover 4952 * @return a {@code Stream} for the array range 4953 * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is 4954 * negative, {@code endExclusive} is less than 4955 * {@code startInclusive}, or {@code endExclusive} is greater than 4956 * the array size 4957 * @since 1.8 4958 */ 4959 public static <T> Stream<T> stream(T[] array, int startInclusive, int endExclusive) { 4960 return StreamSupport.stream(spliterator(array, startInclusive, endExclusive), false); 4961 } 4962 4963 /** 4964 * Returns a sequential {@link IntStream} with the specified array as its 4965 * source. 4966 * 4967 * @param array the array, assumed to be unmodified during use 4968 * @return an {@code IntStream} for the array 4969 * @since 1.8 4970 */ 4971 public static IntStream stream(int[] array) { 4972 return stream(array, 0, array.length); 4973 } 4974 4975 /** 4976 * Returns a sequential {@link IntStream} with the specified range of the 4977 * specified array as its source. 4978 * 4979 * @param array the array, assumed to be unmodified during use 4980 * @param startInclusive the first index to cover, inclusive 4981 * @param endExclusive index immediately past the last index to cover 4982 * @return an {@code IntStream} for the array range 4983 * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is 4984 * negative, {@code endExclusive} is less than 4985 * {@code startInclusive}, or {@code endExclusive} is greater than 4986 * the array size 4987 * @since 1.8 4988 */ 4989 public static IntStream stream(int[] array, int startInclusive, int endExclusive) { 4990 return StreamSupport.intStream(spliterator(array, startInclusive, endExclusive), false); 4991 } 4992 4993 /** 4994 * Returns a sequential {@link LongStream} with the specified array as its 4995 * source. 4996 * 4997 * @param array the array, assumed to be unmodified during use 4998 * @return a {@code LongStream} for the array 4999 * @since 1.8 5000 */ 5001 public static LongStream stream(long[] array) { 5002 return stream(array, 0, array.length); 5003 } 5004 5005 /** 5006 * Returns a sequential {@link LongStream} with the specified range of the 5007 * specified array as its source. 5008 * 5009 * @param array the array, assumed to be unmodified during use 5010 * @param startInclusive the first index to cover, inclusive 5011 * @param endExclusive index immediately past the last index to cover 5012 * @return a {@code LongStream} for the array range 5013 * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is 5014 * negative, {@code endExclusive} is less than 5015 * {@code startInclusive}, or {@code endExclusive} is greater than 5016 * the array size 5017 * @since 1.8 5018 */ 5019 public static LongStream stream(long[] array, int startInclusive, int endExclusive) { 5020 return StreamSupport.longStream(spliterator(array, startInclusive, endExclusive), false); 5021 } 5022 5023 /** 5024 * Returns a sequential {@link DoubleStream} with the specified array as its 5025 * source. 5026 * 5027 * @param array the array, assumed to be unmodified during use 5028 * @return a {@code DoubleStream} for the array 5029 * @since 1.8 5030 */ 5031 public static DoubleStream stream(double[] array) { 5032 return stream(array, 0, array.length); 5033 } 5034 5035 /** 5036 * Returns a sequential {@link DoubleStream} with the specified range of the 5037 * specified array as its source. 5038 * 5039 * @param array the array, assumed to be unmodified during use 5040 * @param startInclusive the first index to cover, inclusive 5041 * @param endExclusive index immediately past the last index to cover 5042 * @return a {@code DoubleStream} for the array range 5043 * @throws ArrayIndexOutOfBoundsException if {@code startInclusive} is 5044 * negative, {@code endExclusive} is less than 5045 * {@code startInclusive}, or {@code endExclusive} is greater than 5046 * the array size 5047 * @since 1.8 5048 */ 5049 public static DoubleStream stream(double[] array, int startInclusive, int endExclusive) { 5050 return StreamSupport.doubleStream(spliterator(array, startInclusive, endExclusive), false); 5051 } 5052} 5053