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