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