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 &gt;= 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 &gt;= 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 &gt;= 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 &gt;= 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 &gt; toIndex</tt>
 643      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
 644      *         <tt>toIndex &gt; 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 &gt; 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 &gt; 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&lt;String&gt; 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 }
--- EOF ---