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