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