1 /*
2 * Copyright (c) 1997, 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package 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:
1048 * <ul>
1049 * <li> <tt>e1</tt> and <tt>e2</tt> are both arrays of object reference
1050 * types, and <tt>Arrays.deepEquals(e1, e2) would return true</tt>
1051 * <li> <tt>e1</tt> and <tt>e2</tt> are arrays of the same primitive
1052 * type, and the appropriate overloading of
1053 * <tt>Arrays.equals(e1, e2)</tt> would return true.
1054 * <li> <tt>e1 == e2</tt>
1055 * <li> <tt>e1.equals(e2)</tt> would return true.
1056 * </ul>
1057 * Note that this definition permits <tt>null</tt> elements at any depth.
1058 *
1059 * <p>If either of the specified arrays contain themselves as elements
1060 * either directly or indirectly through one or more levels of arrays,
1061 * the behavior of this method is undefined.
1062 *
1063 * @param a1 one array to be tested for equality
1064 * @param a2 the other array to be tested for equality
1065 * @return <tt>true</tt> if the two arrays are equal
1066 * @see #equals(Object[],Object[])
1067 * @see Objects#deepEquals(Object, Object)
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
1172 * converted to a string as by invoking the appropriate overloading of
1173 * <tt>Arrays.toString(e)</tt>. If an element <tt>e</tt> is an array of a
1174 * reference type, it is converted to a string as by invoking
1175 * this method recursively.
1176 *
1177 * <p>To avoid infinite recursion, if the specified array contains itself
1178 * as an element, or contains an indirect reference to itself through one
1179 * or more levels of arrays, the self-reference is converted to the string
1180 * <tt>"[...]"</tt>. For example, an array containing only a reference
1181 * to itself would be rendered as <tt>"[[...]]"</tt>.
1182 *
1183 * <p>This method returns <tt>"null"</tt> if the specified array
1184 * is <tt>null</tt>.
1185 *
1186 * @param a the array whose string representation to return
1187 * @return a string representation of <tt>a</tt>
1188 * @see #toString(Object[])
1189 * @since 1.5
1190 */
1191 public static String deepToString(Object[] a) {
1192 if (a == null)
1193 return "null";
1194
1195 int bufLen = 20 * a.length;
1196 if (a.length != 0 && bufLen <= 0)
1197 bufLen = Integer.MAX_VALUE;
1198 StringBuilder buf = new StringBuilder(bufLen);
1199 deepToString(a, buf, new HashSet<>());
1200 return buf.toString();
1201 }
1202
1203 private static void deepToString(Object[] a, StringBuilder buf,
1204 Set<Object[]> dejaVu) {
1205 if (a == null) {
1206 buf.append("null");
1207 return;
1208 }
1209 int iMax = a.length - 1;
1210 if (iMax == -1) {
1211 buf.append("[]");
1212 return;
1213 }
1214
1215 dejaVu.add(a);
1216 buf.append('[');
1217 for (int i = 0; ; i++) {
1218
1219 Object element = a[i];
1220 if (element == null) {
1221 buf.append("null");
1222 } else {
1223 Class<?> eClass = element.getClass();
1224
1225 if (eClass.isArray()) {
1226 if (eClass == byte[].class)
1227 buf.append(toString((byte[]) element));
1228 else if (eClass == short[].class)
1229 buf.append(toString((short[]) element));
1230 else if (eClass == int[].class)
1231 buf.append(toString((int[]) element));
1232 else if (eClass == long[].class)
1233 buf.append(toString((long[]) element));
1234 else if (eClass == char[].class)
1235 buf.append(toString((char[]) element));
1236 else if (eClass == float[].class)
1237 buf.append(toString((float[]) element));
1238 else if (eClass == double[].class)
1239 buf.append(toString((double[]) element));
1240 else if (eClass == boolean[].class)
1241 buf.append(toString((boolean[]) element));
1242 else { // element is an array of object references
1243 if (dejaVu.contains(element))
1244 buf.append("[...]");
1245 else
1246 deepToString((Object[])element, buf, dejaVu);
1247 }
1248 } else { // element is non-null and not an array
1249 buf.append(element.toString());
1250 }
1251 }
1252 if (i == iMax)
1253 break;
1254 buf.append(", ");
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 }