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