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