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