1 /*
   2  * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 
  28 import java.lang.reflect.*;
  29 
  30 /**
  31  * This class contains various methods for manipulating arrays (such as
  32  * sorting and searching). This class also contains a static factory
  33  * that allows arrays to be viewed as lists.
  34  *
  35  * <p>The methods in this class all throw a {@code NullPointerException},
  36  * if the specified array reference is null, except where noted.
  37  *
  38  * <p>The documentation for the methods contained in this class includes
  39  * briefs description of the <i>implementations</i>. Such descriptions should
  40  * be regarded as <i>implementation notes</i>, rather than parts of the
  41  * <i>specification</i>. Implementors should feel free to substitute other
  42  * algorithms, so long as the specification itself is adhered to. (For
  43  * example, the algorithm used by {@code sort(Object[])} does not have to be
  44  * a MergeSort, but it does have to be <i>stable</i>.)
  45  *
  46  * <p>This class is a member of the
  47  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  48  * Java Collections Framework</a>.
  49  *
  50  * @author Josh Bloch
  51  * @author Neal Gafter
  52  * @author John Rose
  53  * @since  1.2
  54  */
  55 public class Arrays {
  56 
  57     // Suppresses default constructor, ensuring non-instantiability.
  58     private Arrays() {}
  59 
  60     /*
  61      * Sorting of primitive type arrays.
  62      */
  63 
  64     /**
  65      * Sorts the specified array into ascending numerical order.
  66      *
  67      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
  68      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
  69      * offers O(n log(n)) performance on many data sets that cause other
  70      * quicksorts to degrade to quadratic performance, and is typically
  71      * faster than traditional (one-pivot) Quicksort implementations.
  72      *
  73      * @param a the array to be sorted
  74      */
  75     public static void sort(int[] a) {
  76         DualPivotQuicksort.sort(a);
  77     }
  78 
  79     /**
  80      * Sorts the specified range of the array into ascending order. The range
  81      * to be sorted extends from the index {@code fromIndex}, inclusive, to
  82      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
  83      * the range to be sorted is empty.
  84      *
  85      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
  86      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
  87      * offers O(n log(n)) performance on many data sets that cause other
  88      * quicksorts to degrade to quadratic performance, and is typically
  89      * faster than traditional (one-pivot) Quicksort implementations.
  90      *
  91      * @param a the array to be sorted
  92      * @param fromIndex the index of the first element, inclusive, to be sorted
  93      * @param toIndex the index of the last element, exclusive, to be sorted
  94      *
  95      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
  96      * @throws ArrayIndexOutOfBoundsException
  97      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
  98      */
  99     public static void sort(int[] a, int fromIndex, int toIndex) {
 100         rangeCheck(a.length, fromIndex, toIndex);
 101         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
 102     }
 103 
 104     /**
 105      * Sorts the specified array into ascending numerical order.
 106      *
 107      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
 108      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 109      * offers O(n log(n)) performance on many data sets that cause other
 110      * quicksorts to degrade to quadratic performance, and is typically
 111      * faster than traditional (one-pivot) Quicksort implementations.
 112      *
 113      * @param a the array to be sorted
 114      */
 115     public static void sort(long[] a) {
 116         DualPivotQuicksort.sort(a);
 117     }
 118 
 119     /**
 120      * Sorts the specified range of the array into ascending order. The range
 121      * to be sorted extends from the index {@code fromIndex}, inclusive, to
 122      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
 123      * the range to be sorted is empty.
 124      *
 125      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
 126      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 127      * offers O(n log(n)) performance on many data sets that cause other
 128      * quicksorts to degrade to quadratic performance, and is typically
 129      * faster than traditional (one-pivot) Quicksort implementations.
 130      *
 131      * @param a the array to be sorted
 132      * @param fromIndex the index of the first element, inclusive, to be sorted
 133      * @param toIndex the index of the last element, exclusive, to be sorted
 134      *
 135      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
 136      * @throws ArrayIndexOutOfBoundsException
 137      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
 138      */
 139     public static void sort(long[] a, int fromIndex, int toIndex) {
 140         rangeCheck(a.length, fromIndex, toIndex);
 141         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
 142     }
 143 
 144     /**
 145      * Sorts the specified array into ascending numerical order.
 146      *
 147      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
 148      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 149      * offers O(n log(n)) performance on many data sets that cause other
 150      * quicksorts to degrade to quadratic performance, and is typically
 151      * faster than traditional (one-pivot) Quicksort implementations.
 152      *
 153      * @param a the array to be sorted
 154      */
 155     public static void sort(short[] a) {
 156         DualPivotQuicksort.sort(a);
 157     }
 158 
 159     /**
 160      * Sorts the specified range of the array into ascending order. The range
 161      * to be sorted extends from the index {@code fromIndex}, inclusive, to
 162      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
 163      * the range to be sorted is empty.
 164      *
 165      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
 166      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 167      * offers O(n log(n)) performance on many data sets that cause other
 168      * quicksorts to degrade to quadratic performance, and is typically
 169      * faster than traditional (one-pivot) Quicksort implementations.
 170      *
 171      * @param a the array to be sorted
 172      * @param fromIndex the index of the first element, inclusive, to be sorted
 173      * @param toIndex the index of the last element, exclusive, to be sorted
 174      *
 175      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
 176      * @throws ArrayIndexOutOfBoundsException
 177      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
 178      */
 179     public static void sort(short[] a, int fromIndex, int toIndex) {
 180         rangeCheck(a.length, fromIndex, toIndex);
 181         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
 182     }
 183 
 184     /**
 185      * Sorts the specified array into ascending numerical order.
 186      *
 187      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
 188      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 189      * offers O(n log(n)) performance on many data sets that cause other
 190      * quicksorts to degrade to quadratic performance, and is typically
 191      * faster than traditional (one-pivot) Quicksort implementations.
 192      *
 193      * @param a the array to be sorted
 194      */
 195     public static void sort(char[] a) {
 196         DualPivotQuicksort.sort(a);
 197     }
 198 
 199     /**
 200      * Sorts the specified range of the array into ascending order. The range
 201      * to be sorted extends from the index {@code fromIndex}, inclusive, to
 202      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
 203      * the range to be sorted is empty.
 204      *
 205      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
 206      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 207      * offers O(n log(n)) performance on many data sets that cause other
 208      * quicksorts to degrade to quadratic performance, and is typically
 209      * faster than traditional (one-pivot) Quicksort implementations.
 210      *
 211      * @param a the array to be sorted
 212      * @param fromIndex the index of the first element, inclusive, to be sorted
 213      * @param toIndex the index of the last element, exclusive, to be sorted
 214      *
 215      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
 216      * @throws ArrayIndexOutOfBoundsException
 217      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
 218      */
 219     public static void sort(char[] a, int fromIndex, int toIndex) {
 220         rangeCheck(a.length, fromIndex, toIndex);
 221         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
 222     }
 223 
 224     /**
 225      * Sorts the specified array into ascending numerical order.
 226      *
 227      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
 228      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 229      * offers O(n log(n)) performance on many data sets that cause other
 230      * quicksorts to degrade to quadratic performance, and is typically
 231      * faster than traditional (one-pivot) Quicksort implementations.
 232      *
 233      * @param a the array to be sorted
 234      */
 235     public static void sort(byte[] a) {
 236         DualPivotQuicksort.sort(a);
 237     }
 238 
 239     /**
 240      * Sorts the specified range of the array into ascending order. The range
 241      * to be sorted extends from the index {@code fromIndex}, inclusive, to
 242      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
 243      * the range to be sorted is empty.
 244      *
 245      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
 246      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 247      * offers O(n log(n)) performance on many data sets that cause other
 248      * quicksorts to degrade to quadratic performance, and is typically
 249      * faster than traditional (one-pivot) Quicksort implementations.
 250      *
 251      * @param a the array to be sorted
 252      * @param fromIndex the index of the first element, inclusive, to be sorted
 253      * @param toIndex the index of the last element, exclusive, to be sorted
 254      *
 255      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
 256      * @throws ArrayIndexOutOfBoundsException
 257      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
 258      */
 259     public static void sort(byte[] a, int fromIndex, int toIndex) {
 260         rangeCheck(a.length, fromIndex, toIndex);
 261         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
 262     }
 263 
 264     /**
 265      * Sorts the specified array into ascending numerical order.
 266      *
 267      * <p>The {@code <} relation does not provide a total order on all float
 268      * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
 269      * value compares neither less than, greater than, nor equal to any value,
 270      * even itself. This method uses the total order imposed by the method
 271      * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
 272      * {@code 0.0f} and {@code Float.NaN} is considered greater than any
 273      * other value and all {@code Float.NaN} values are considered equal.
 274      *
 275      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
 276      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 277      * offers O(n log(n)) performance on many data sets that cause other
 278      * quicksorts to degrade to quadratic performance, and is typically
 279      * faster than traditional (one-pivot) Quicksort implementations.
 280      *
 281      * @param a the array to be sorted
 282      */
 283     public static void sort(float[] a) {
 284         DualPivotQuicksort.sort(a);
 285     }
 286 
 287     /**
 288      * Sorts the specified range of the array into ascending order. The range
 289      * to be sorted extends from the index {@code fromIndex}, inclusive, to
 290      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
 291      * the range to be sorted is empty.
 292      *
 293      * <p>The {@code <} relation does not provide a total order on all float
 294      * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
 295      * value compares neither less than, greater than, nor equal to any value,
 296      * even itself. This method uses the total order imposed by the method
 297      * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
 298      * {@code 0.0f} and {@code Float.NaN} is considered greater than any
 299      * other value and all {@code Float.NaN} values are considered equal.
 300      *
 301      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
 302      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 303      * offers O(n log(n)) performance on many data sets that cause other
 304      * quicksorts to degrade to quadratic performance, and is typically
 305      * faster than traditional (one-pivot) Quicksort implementations.
 306      *
 307      * @param a the array to be sorted
 308      * @param fromIndex the index of the first element, inclusive, to be sorted
 309      * @param toIndex the index of the last element, exclusive, to be sorted
 310      *
 311      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
 312      * @throws ArrayIndexOutOfBoundsException
 313      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
 314      */
 315     public static void sort(float[] a, int fromIndex, int toIndex) {
 316         rangeCheck(a.length, fromIndex, toIndex);
 317         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
 318     }
 319 
 320     /**
 321      * Sorts the specified array into ascending numerical order.
 322      *
 323      * <p>The {@code <} relation does not provide a total order on all double
 324      * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
 325      * value compares neither less than, greater than, nor equal to any value,
 326      * even itself. This method uses the total order imposed by the method
 327      * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
 328      * {@code 0.0d} and {@code Double.NaN} is considered greater than any
 329      * other value and all {@code Double.NaN} values are considered equal.
 330      *
 331      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
 332      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 333      * offers O(n log(n)) performance on many data sets that cause other
 334      * quicksorts to degrade to quadratic performance, and is typically
 335      * faster than traditional (one-pivot) Quicksort implementations.
 336      *
 337      * @param a the array to be sorted
 338      */
 339     public static void sort(double[] a) {
 340         DualPivotQuicksort.sort(a);
 341     }
 342 
 343     /**
 344      * Sorts the specified range of the array into ascending order. The range
 345      * to be sorted extends from the index {@code fromIndex}, inclusive, to
 346      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
 347      * the range to be sorted is empty.
 348      *
 349      * <p>The {@code <} relation does not provide a total order on all double
 350      * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
 351      * value compares neither less than, greater than, nor equal to any value,
 352      * even itself. This method uses the total order imposed by the method
 353      * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
 354      * {@code 0.0d} and {@code Double.NaN} is considered greater than any
 355      * other value and all {@code Double.NaN} values are considered equal.
 356      *
 357      * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
 358      * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 359      * offers O(n log(n)) performance on many data sets that cause other
 360      * quicksorts to degrade to quadratic performance, and is typically
 361      * faster than traditional (one-pivot) Quicksort implementations.
 362      *
 363      * @param a the array to be sorted
 364      * @param fromIndex the index of the first element, inclusive, to be sorted
 365      * @param toIndex the index of the last element, exclusive, to be sorted
 366      *
 367      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
 368      * @throws ArrayIndexOutOfBoundsException
 369      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
 370      */
 371     public static void sort(double[] a, int fromIndex, int toIndex) {
 372         rangeCheck(a.length, fromIndex, toIndex);
 373         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
 374     }
 375 
 376     /*
 377      * Sorting of complex type arrays.
 378      */
 379 
 380     /**
 381      * Old merge sort implementation can be selected (for
 382      * compatibility with broken comparators) using a system property.
 383      * Cannot be a static boolean in the enclosing class due to
 384      * circular dependencies. To be removed in a future release.
 385      */
 386     static final class LegacyMergeSort {
 387         private static final boolean userRequested =
 388             java.security.AccessController.doPrivileged(
 389                 new sun.security.action.GetBooleanAction(
 390                     "java.util.Arrays.useLegacyMergeSort")).booleanValue();
 391     }
 392 
 393     /*
 394      * If this platform has an optimizing VM, check whether ComparableTimSort
 395      * offers any performance benefit over TimSort in conjunction with a
 396      * comparator that returns:
 397      *    {@code ((Comparable)first).compareTo(Second)}.
 398      * If not, you are better off deleting ComparableTimSort to
 399      * eliminate the code duplication.  In other words, the commented
 400      * out code below is the preferable implementation for sorting
 401      * arrays of Comparables if it offers sufficient performance.
 402      */
 403 
 404 //    /**
 405 //     * A comparator that implements the natural ordering of a group of
 406 //     * mutually comparable elements.  Using this comparator saves us
 407 //     * from duplicating most of the code in this file (one version for
 408 //     * Comparables, one for explicit Comparators).
 409 //     */
 410 //    private static final Comparator<Object> NATURAL_ORDER =
 411 //            new Comparator<Object>() {
 412 //        @SuppressWarnings("unchecked")
 413 //        public int compare(Object first, Object second) {
 414 //            return ((Comparable<Object>)first).compareTo(second);
 415 //        }
 416 //    };
 417 //
 418 //    public static void sort(Object[] a) {
 419 //        sort(a, 0, a.length, NATURAL_ORDER);
 420 //    }
 421 //
 422 //    public static void sort(Object[] a, int fromIndex, int toIndex) {
 423 //        sort(a, fromIndex, toIndex, NATURAL_ORDER);
 424 //    }
 425 
 426     /**
 427      * Sorts the specified array of objects into ascending order, according
 428      * to the {@linkplain Comparable natural ordering} of its elements.
 429      * All elements in the array must implement the {@link Comparable}
 430      * interface.  Furthermore, all elements in the array must be
 431      * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
 432      * not throw a {@code ClassCastException} for any elements {@code e1}
 433      * and {@code e2} in the array).
 434      *
 435      * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
 436      * not be reordered as a result of the sort.
 437      *
 438      * <p>Implementation note: This implementation is a stable, adaptive,
 439      * iterative mergesort that requires far fewer than n lg(n) comparisons
 440      * when the input array is partially sorted, while offering the
 441      * performance of a traditional mergesort when the input array is
 442      * randomly ordered.  If the input array is nearly sorted, the
 443      * implementation requires approximately n comparisons.  Temporary
 444      * storage requirements vary from a small constant for nearly sorted
 445      * input arrays to n/2 object references for randomly ordered input
 446      * arrays.
 447      *
 448      * <p>The implementation takes equal advantage of ascending and
 449      * descending order in its input array, and can take advantage of
 450      * ascending and descending order in different parts of the the same
 451      * input array.  It is well-suited to merging two or more sorted arrays:
 452      * simply concatenate the arrays and sort the resulting array.
 453      *
 454      * <p>The implementation was adapted from Tim Peters's list sort for Python
 455      * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
 456      * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic
 457      * Sorting and Information Theoretic Complexity", in Proceedings of the
 458      * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
 459      * January 1993.
 460      *
 461      * @param a the array to be sorted
 462      * @throws ClassCastException if the array contains elements that are not
 463      *         <i>mutually comparable</i> (for example, strings and integers)
 464      * @throws IllegalArgumentException (optional) if the natural
 465      *         ordering of the array elements is found to violate the
 466      *         {@link Comparable} contract
 467      */
 468     public static void sort(Object[] a) {
 469         if (LegacyMergeSort.userRequested)
 470             legacyMergeSort(a);
 471         else
 472             ComparableTimSort.sort(a);
 473     }
 474 
 475     /** To be removed in a future release. */
 476     private static void legacyMergeSort(Object[] a) {
 477         Object[] aux = a.clone();
 478         mergeSort(aux, a, 0, a.length, 0);
 479     }
 480 
 481     /**
 482      * Sorts the specified range of the specified array of objects into
 483      * ascending order, according to the
 484      * {@linkplain Comparable natural ordering} of its
 485      * elements.  The range to be sorted extends from index
 486      * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive.
 487      * (If {@code fromIndex==toIndex}, the range to be sorted is empty.)  All
 488      * elements in this range must implement the {@link Comparable}
 489      * interface.  Furthermore, all elements in this range must be <i>mutually
 490      * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a
 491      * {@code ClassCastException} for any elements {@code e1} and
 492      * {@code e2} in the array).
 493      *
 494      * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
 495      * not be reordered as a result of the sort.
 496      *
 497      * <p>Implementation note: This implementation is a stable, adaptive,
 498      * iterative mergesort that requires far fewer than n lg(n) comparisons
 499      * when the input array is partially sorted, while offering the
 500      * performance of a traditional mergesort when the input array is
 501      * randomly ordered.  If the input array is nearly sorted, the
 502      * implementation requires approximately n comparisons.  Temporary
 503      * storage requirements vary from a small constant for nearly sorted
 504      * input arrays to n/2 object references for randomly ordered input
 505      * arrays.
 506      *
 507      * <p>The implementation takes equal advantage of ascending and
 508      * descending order in its input array, and can take advantage of
 509      * ascending and descending order in different parts of the the same
 510      * input array.  It is well-suited to merging two or more sorted arrays:
 511      * simply concatenate the arrays and sort the resulting array.
 512      *
 513      * <p>The implementation was adapted from Tim Peters's list sort for Python
 514      * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
 515      * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic
 516      * Sorting and Information Theoretic Complexity", in Proceedings of the
 517      * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
 518      * January 1993.
 519      *
 520      * @param a the array to be sorted
 521      * @param fromIndex the index of the first element (inclusive) to be
 522      *        sorted
 523      * @param toIndex the index of the last element (exclusive) to be sorted
 524      * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
 525      *         (optional) if the natural ordering of the array elements is
 526      *         found to violate the {@link Comparable} contract
 527      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
 528      *         {@code toIndex > a.length}
 529      * @throws ClassCastException if the array contains elements that are
 530      *         not <i>mutually comparable</i> (for example, strings and
 531      *         integers).
 532      */
 533     public static void sort(Object[] a, int fromIndex, int toIndex) {
 534         if (LegacyMergeSort.userRequested)
 535             legacyMergeSort(a, fromIndex, toIndex);
 536         else
 537             ComparableTimSort.sort(a, fromIndex, toIndex);
 538     }
 539 
 540     /** To be removed in a future release. */
 541     private static void legacyMergeSort(Object[] a,
 542                                         int fromIndex, int toIndex) {
 543         rangeCheck(a.length, fromIndex, toIndex);
 544         Object[] aux = copyOfRange(a, fromIndex, toIndex);
 545         mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
 546     }
 547 
 548     /**
 549      * Tuning parameter: list size at or below which insertion sort will be
 550      * used in preference to mergesort.
 551      * To be removed in a future release.
 552      */
 553     private static final int INSERTIONSORT_THRESHOLD = 7;
 554 
 555     /**
 556      * Src is the source array that starts at index 0
 557      * Dest is the (possibly larger) array destination with a possible offset
 558      * low is the index in dest to start sorting
 559      * high is the end index in dest to end sorting
 560      * off is the offset to generate corresponding low, high in src
 561      * To be removed in a future release.
 562      */
 563     private static void mergeSort(Object[] src,
 564                                   Object[] dest,
 565                                   int low,
 566                                   int high,
 567                                   int off) {
 568         int length = high - low;
 569 
 570         // Insertion sort on smallest arrays
 571         if (length < INSERTIONSORT_THRESHOLD) {
 572             for (int i=low; i<high; i++)
 573                 for (int j=i; j>low &&
 574                          ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
 575                     swap(dest, j, j-1);
 576             return;
 577         }
 578 
 579         // Recursively sort halves of dest into src
 580         int destLow  = low;
 581         int destHigh = high;
 582         low  += off;
 583         high += off;
 584         int mid = (low + high) >>> 1;
 585         mergeSort(dest, src, low, mid, -off);
 586         mergeSort(dest, src, mid, high, -off);
 587 
 588         // If list is already sorted, just copy from src to dest.  This is an
 589         // optimization that results in faster sorts for nearly ordered lists.
 590         if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
 591             System.arraycopy(src, low, dest, destLow, length);
 592             return;
 593         }
 594 
 595         // Merge sorted halves (now in src) into dest
 596         for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
 597             if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
 598                 dest[i] = src[p++];
 599             else
 600                 dest[i] = src[q++];
 601         }
 602     }
 603 
 604     /**
 605      * Swaps x[a] with x[b].
 606      */
 607     private static void swap(Object[] x, int a, int b) {
 608         Object t = x[a];
 609         x[a] = x[b];
 610         x[b] = t;
 611     }
 612 
 613     /**
 614      * Sorts the specified array of objects according to the order induced by
 615      * the specified comparator.  All elements in the array must be
 616      * <i>mutually comparable</i> by the specified comparator (that is,
 617      * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
 618      * for any elements {@code e1} and {@code e2} in the array).
 619      *
 620      * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
 621      * not be reordered as a result of the sort.
 622      *
 623      * <p>Implementation note: This implementation is a stable, adaptive,
 624      * iterative mergesort that requires far fewer than n lg(n) comparisons
 625      * when the input array is partially sorted, while offering the
 626      * performance of a traditional mergesort when the input array is
 627      * randomly ordered.  If the input array is nearly sorted, the
 628      * implementation requires approximately n comparisons.  Temporary
 629      * storage requirements vary from a small constant for nearly sorted
 630      * input arrays to n/2 object references for randomly ordered input
 631      * arrays.
 632      *
 633      * <p>The implementation takes equal advantage of ascending and
 634      * descending order in its input array, and can take advantage of
 635      * ascending and descending order in different parts of the the same
 636      * input array.  It is well-suited to merging two or more sorted arrays:
 637      * simply concatenate the arrays and sort the resulting array.
 638      *
 639      * <p>The implementation was adapted from Tim Peters's list sort for Python
 640      * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
 641      * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic
 642      * Sorting and Information Theoretic Complexity", in Proceedings of the
 643      * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
 644      * January 1993.
 645      *
 646      * @param a the array to be sorted
 647      * @param c the comparator to determine the order of the array.  A
 648      *        {@code null} value indicates that the elements'
 649      *        {@linkplain Comparable natural ordering} should be used.
 650      * @throws ClassCastException if the array contains elements that are
 651      *         not <i>mutually comparable</i> using the specified comparator
 652      * @throws IllegalArgumentException (optional) if the comparator is
 653      *         found to violate the {@link Comparator} contract
 654      */
 655     public static <T> void sort(T[] a, Comparator<? super T> c) {
 656         if (LegacyMergeSort.userRequested)
 657             legacyMergeSort(a, c);
 658         else
 659             TimSort.sort(a, c);
 660     }
 661 
 662     /** To be removed in a future release. */
 663     private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {
 664         T[] aux = a.clone();
 665         if (c==null)
 666             mergeSort(aux, a, 0, a.length, 0);
 667         else
 668             mergeSort(aux, a, 0, a.length, 0, c);
 669     }
 670 
 671     /**
 672      * Sorts the specified range of the specified array of objects according
 673      * to the order induced by the specified comparator.  The range to be
 674      * sorted extends from index {@code fromIndex}, inclusive, to index
 675      * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
 676      * range to be sorted is empty.)  All elements in the range must be
 677      * <i>mutually comparable</i> by the specified comparator (that is,
 678      * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
 679      * for any elements {@code e1} and {@code e2} in the range).
 680      *
 681      * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
 682      * not be reordered as a result of the sort.
 683      *
 684      * <p>Implementation note: This implementation is a stable, adaptive,
 685      * iterative mergesort that requires far fewer than n lg(n) comparisons
 686      * when the input array is partially sorted, while offering the
 687      * performance of a traditional mergesort when the input array is
 688      * randomly ordered.  If the input array is nearly sorted, the
 689      * implementation requires approximately n comparisons.  Temporary
 690      * storage requirements vary from a small constant for nearly sorted
 691      * input arrays to n/2 object references for randomly ordered input
 692      * arrays.
 693      *
 694      * <p>The implementation takes equal advantage of ascending and
 695      * descending order in its input array, and can take advantage of
 696      * ascending and descending order in different parts of the the same
 697      * input array.  It is well-suited to merging two or more sorted arrays:
 698      * simply concatenate the arrays and sort the resulting array.
 699      *
 700      * <p>The implementation was adapted from Tim Peters's list sort for Python
 701      * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
 702      * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic
 703      * Sorting and Information Theoretic Complexity", in Proceedings of the
 704      * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
 705      * January 1993.
 706      *
 707      * @param a the array to be sorted
 708      * @param fromIndex the index of the first element (inclusive) to be
 709      *        sorted
 710      * @param toIndex the index of the last element (exclusive) to be sorted
 711      * @param c the comparator to determine the order of the array.  A
 712      *        {@code null} value indicates that the elements'
 713      *        {@linkplain Comparable natural ordering} should be used.
 714      * @throws ClassCastException if the array contains elements that are not
 715      *         <i>mutually comparable</i> using the specified comparator.
 716      * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
 717      *         (optional) if the comparator is found to violate the
 718      *         {@link Comparator} contract
 719      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
 720      *         {@code toIndex > a.length}
 721      */
 722     public static <T> void sort(T[] a, int fromIndex, int toIndex,
 723                                 Comparator<? super T> c) {
 724         if (LegacyMergeSort.userRequested)
 725             legacyMergeSort(a, fromIndex, toIndex, c);
 726         else
 727             TimSort.sort(a, fromIndex, toIndex, c);
 728     }
 729 
 730     /** To be removed in a future release. */
 731     private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
 732                                             Comparator<? super T> c) {
 733         rangeCheck(a.length, fromIndex, toIndex);
 734         T[] aux = copyOfRange(a, fromIndex, toIndex);
 735         if (c==null)
 736             mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
 737         else
 738             mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
 739     }
 740 
 741     /**
 742      * Src is the source array that starts at index 0
 743      * Dest is the (possibly larger) array destination with a possible offset
 744      * low is the index in dest to start sorting
 745      * high is the end index in dest to end sorting
 746      * off is the offset into src corresponding to low in dest
 747      * To be removed in a future release.
 748      */
 749     private static void mergeSort(Object[] src,
 750                                   Object[] dest,
 751                                   int low, int high, int off,
 752                                   Comparator c) {
 753         int length = high - low;
 754 
 755         // Insertion sort on smallest arrays
 756         if (length < INSERTIONSORT_THRESHOLD) {
 757             for (int i=low; i<high; i++)
 758                 for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
 759                     swap(dest, j, j-1);
 760             return;
 761         }
 762 
 763         // Recursively sort halves of dest into src
 764         int destLow  = low;
 765         int destHigh = high;
 766         low  += off;
 767         high += off;
 768         int mid = (low + high) >>> 1;
 769         mergeSort(dest, src, low, mid, -off, c);
 770         mergeSort(dest, src, mid, high, -off, c);
 771 
 772         // If list is already sorted, just copy from src to dest.  This is an
 773         // optimization that results in faster sorts for nearly ordered lists.
 774         if (c.compare(src[mid-1], src[mid]) <= 0) {
 775            System.arraycopy(src, low, dest, destLow, length);
 776            return;
 777         }
 778 
 779         // Merge sorted halves (now in src) into dest
 780         for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
 781             if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
 782                 dest[i] = src[p++];
 783             else
 784                 dest[i] = src[q++];
 785         }
 786     }
 787 
 788     /**
 789      * Checks that {@code fromIndex} and {@code toIndex} are in
 790      * the range and throws an appropriate exception, if they aren't.
 791      */
 792     private static void rangeCheck(int length, int fromIndex, int toIndex) {
 793         if (fromIndex > toIndex) {
 794             throw new IllegalArgumentException(
 795                 "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
 796         }
 797         if (fromIndex < 0) {
 798             throw new ArrayIndexOutOfBoundsException(fromIndex);
 799         }
 800         if (toIndex > length) {
 801             throw new ArrayIndexOutOfBoundsException(toIndex);
 802         }
 803     }
 804 
 805     // Searching
 806 
 807     /**
 808      * Searches the specified array of longs for the specified value using the
 809      * binary search algorithm.  The array must be sorted (as
 810      * by the {@link #sort(long[])} method) prior to making this call.  If it
 811      * is not sorted, the results are undefined.  If the array contains
 812      * multiple elements with the specified value, there is no guarantee which
 813      * one will be found.
 814      *
 815      * @param a the array to be searched
 816      * @param key the value to be searched for
 817      * @return index of the search key, if it is contained in the array;
 818      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
 819      *         <i>insertion point</i> is defined as the point at which the
 820      *         key would be inserted into the array: the index of the first
 821      *         element greater than the key, or <tt>a.length</tt> if all
 822      *         elements in the array are less than the specified key.  Note
 823      *         that this guarantees that the return value will be &gt;= 0 if
 824      *         and only if the key is found.
 825      */
 826     public static int binarySearch(long[] a, long key) {
 827         return binarySearch0(a, 0, a.length, key);
 828     }
 829 
 830     /**
 831      * Searches a range of
 832      * the specified array of longs for the specified value using the
 833      * binary search algorithm.
 834      * The range must be sorted (as
 835      * by the {@link #sort(long[], int, int)} method)
 836      * prior to making this call.  If it
 837      * is not sorted, the results are undefined.  If the range contains
 838      * multiple elements with the specified value, there is no guarantee which
 839      * one will be found.
 840      *
 841      * @param a the array to be searched
 842      * @param fromIndex the index of the first element (inclusive) to be
 843      *          searched
 844      * @param toIndex the index of the last element (exclusive) to be searched
 845      * @param key the value to be searched for
 846      * @return index of the search key, if it is contained in the array
 847      *         within the specified range;
 848      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
 849      *         <i>insertion point</i> is defined as the point at which the
 850      *         key would be inserted into the array: the index of the first
 851      *         element in the range greater than the key,
 852      *         or <tt>toIndex</tt> if all
 853      *         elements in the range are less than the specified key.  Note
 854      *         that this guarantees that the return value will be &gt;= 0 if
 855      *         and only if the key is found.
 856      * @throws IllegalArgumentException
 857      *         if {@code fromIndex > toIndex}
 858      * @throws ArrayIndexOutOfBoundsException
 859      *         if {@code fromIndex < 0 or toIndex > a.length}
 860      * @since 1.6
 861      */
 862     public static int binarySearch(long[] a, int fromIndex, int toIndex,
 863                                    long key) {
 864         rangeCheck(a.length, fromIndex, toIndex);
 865         return binarySearch0(a, fromIndex, toIndex, key);
 866     }
 867 
 868     // Like public version, but without range checks.
 869     private static int binarySearch0(long[] a, int fromIndex, int toIndex,
 870                                      long key) {
 871         int low = fromIndex;
 872         int high = toIndex - 1;
 873 
 874         while (low <= high) {
 875             int mid = (low + high) >>> 1;
 876             long midVal = a[mid];
 877 
 878             if (midVal < key)
 879                 low = mid + 1;
 880             else if (midVal > key)
 881                 high = mid - 1;
 882             else
 883                 return mid; // key found
 884         }
 885         return -(low + 1);  // key not found.
 886     }
 887 
 888     /**
 889      * Searches the specified array of ints for the specified value using the
 890      * binary search algorithm.  The array must be sorted (as
 891      * by the {@link #sort(int[])} method) prior to making this call.  If it
 892      * is not sorted, the results are undefined.  If the array contains
 893      * multiple elements with the specified value, there is no guarantee which
 894      * one will be found.
 895      *
 896      * @param a the array to be searched
 897      * @param key the value to be searched for
 898      * @return index of the search key, if it is contained in the array;
 899      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
 900      *         <i>insertion point</i> is defined as the point at which the
 901      *         key would be inserted into the array: the index of the first
 902      *         element greater than the key, or <tt>a.length</tt> if all
 903      *         elements in the array are less than the specified key.  Note
 904      *         that this guarantees that the return value will be &gt;= 0 if
 905      *         and only if the key is found.
 906      */
 907     public static int binarySearch(int[] a, int key) {
 908         return binarySearch0(a, 0, a.length, key);
 909     }
 910 
 911     /**
 912      * Searches a range of
 913      * the specified array of ints for the specified value using the
 914      * binary search algorithm.
 915      * The range must be sorted (as
 916      * by the {@link #sort(int[], int, int)} method)
 917      * prior to making this call.  If it
 918      * is not sorted, the results are undefined.  If the range contains
 919      * multiple elements with the specified value, there is no guarantee which
 920      * one will be found.
 921      *
 922      * @param a the array to be searched
 923      * @param fromIndex the index of the first element (inclusive) to be
 924      *          searched
 925      * @param toIndex the index of the last element (exclusive) to be searched
 926      * @param key the value to be searched for
 927      * @return index of the search key, if it is contained in the array
 928      *         within the specified range;
 929      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
 930      *         <i>insertion point</i> is defined as the point at which the
 931      *         key would be inserted into the array: the index of the first
 932      *         element in the range greater than the key,
 933      *         or <tt>toIndex</tt> if all
 934      *         elements in the range are less than the specified key.  Note
 935      *         that this guarantees that the return value will be &gt;= 0 if
 936      *         and only if the key is found.
 937      * @throws IllegalArgumentException
 938      *         if {@code fromIndex > toIndex}
 939      * @throws ArrayIndexOutOfBoundsException
 940      *         if {@code fromIndex < 0 or toIndex > a.length}
 941      * @since 1.6
 942      */
 943     public static int binarySearch(int[] a, int fromIndex, int toIndex,
 944                                    int key) {
 945         rangeCheck(a.length, fromIndex, toIndex);
 946         return binarySearch0(a, fromIndex, toIndex, key);
 947     }
 948 
 949     // Like public version, but without range checks.
 950     private static int binarySearch0(int[] a, int fromIndex, int toIndex,
 951                                      int key) {
 952         int low = fromIndex;
 953         int high = toIndex - 1;
 954 
 955         while (low <= high) {
 956             int mid = (low + high) >>> 1;
 957             int midVal = a[mid];
 958 
 959             if (midVal < key)
 960                 low = mid + 1;
 961             else if (midVal > key)
 962                 high = mid - 1;
 963             else
 964                 return mid; // key found
 965         }
 966         return -(low + 1);  // key not found.
 967     }
 968 
 969     /**
 970      * Searches the specified array of shorts for the specified value using
 971      * the binary search algorithm.  The array must be sorted
 972      * (as by the {@link #sort(short[])} method) prior to making this call.  If
 973      * it is not sorted, the results are undefined.  If the array contains
 974      * multiple elements with the specified value, there is no guarantee which
 975      * one will be found.
 976      *
 977      * @param a the array to be searched
 978      * @param key the value to be searched for
 979      * @return index of the search key, if it is contained in the array;
 980      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
 981      *         <i>insertion point</i> is defined as the point at which the
 982      *         key would be inserted into the array: the index of the first
 983      *         element greater than the key, or <tt>a.length</tt> if all
 984      *         elements in the array are less than the specified key.  Note
 985      *         that this guarantees that the return value will be &gt;= 0 if
 986      *         and only if the key is found.
 987      */
 988     public static int binarySearch(short[] a, short key) {
 989         return binarySearch0(a, 0, a.length, key);
 990     }
 991 
 992     /**
 993      * Searches a range of
 994      * the specified array of shorts for the specified value using
 995      * the binary search algorithm.
 996      * The range must be sorted
 997      * (as by the {@link #sort(short[], int, int)} method)
 998      * prior to making this call.  If
 999      * it is not sorted, the results are undefined.  If the range contains
1000      * multiple elements with the specified value, there is no guarantee which
1001      * one will be found.
1002      *
1003      * @param a the array to be searched
1004      * @param fromIndex the index of the first element (inclusive) to be
1005      *          searched
1006      * @param toIndex the index of the last element (exclusive) to be searched
1007      * @param key the value to be searched for
1008      * @return index of the search key, if it is contained in the array
1009      *         within the specified range;
1010      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
1011      *         <i>insertion point</i> is defined as the point at which the
1012      *         key would be inserted into the array: the index of the first
1013      *         element in the range greater than the key,
1014      *         or <tt>toIndex</tt> if all
1015      *         elements in the range are less than the specified key.  Note
1016      *         that this guarantees that the return value will be &gt;= 0 if
1017      *         and only if the key is found.
1018      * @throws IllegalArgumentException
1019      *         if {@code fromIndex > toIndex}
1020      * @throws ArrayIndexOutOfBoundsException
1021      *         if {@code fromIndex < 0 or toIndex > a.length}
1022      * @since 1.6
1023      */
1024     public static int binarySearch(short[] a, int fromIndex, int toIndex,
1025                                    short key) {
1026         rangeCheck(a.length, fromIndex, toIndex);
1027         return binarySearch0(a, fromIndex, toIndex, key);
1028     }
1029 
1030     // Like public version, but without range checks.
1031     private static int binarySearch0(short[] a, int fromIndex, int toIndex,
1032                                      short key) {
1033         int low = fromIndex;
1034         int high = toIndex - 1;
1035 
1036         while (low <= high) {
1037             int mid = (low + high) >>> 1;
1038             short midVal = a[mid];
1039 
1040             if (midVal < key)
1041                 low = mid + 1;
1042             else if (midVal > key)
1043                 high = mid - 1;
1044             else
1045                 return mid; // key found
1046         }
1047         return -(low + 1);  // key not found.
1048     }
1049 
1050     /**
1051      * Searches the specified array of chars for the specified value using the
1052      * binary search algorithm.  The array must be sorted (as
1053      * by the {@link #sort(char[])} method) prior to making this call.  If it
1054      * is not sorted, the results are undefined.  If the array contains
1055      * multiple elements with the specified value, there is no guarantee which
1056      * one will be found.
1057      *
1058      * @param a the array to be searched
1059      * @param key the value to be searched for
1060      * @return index of the search key, if it is contained in the array;
1061      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
1062      *         <i>insertion point</i> is defined as the point at which the
1063      *         key would be inserted into the array: the index of the first
1064      *         element greater than the key, or <tt>a.length</tt> if all
1065      *         elements in the array are less than the specified key.  Note
1066      *         that this guarantees that the return value will be &gt;= 0 if
1067      *         and only if the key is found.
1068      */
1069     public static int binarySearch(char[] a, char key) {
1070         return binarySearch0(a, 0, a.length, key);
1071     }
1072 
1073     /**
1074      * Searches a range of
1075      * the specified array of chars for the specified value using the
1076      * binary search algorithm.
1077      * The range must be sorted (as
1078      * by the {@link #sort(char[], int, int)} method)
1079      * prior to making this call.  If it
1080      * is not sorted, the results are undefined.  If the range contains
1081      * multiple elements with the specified value, there is no guarantee which
1082      * one will be found.
1083      *
1084      * @param a the array to be searched
1085      * @param fromIndex the index of the first element (inclusive) to be
1086      *          searched
1087      * @param toIndex the index of the last element (exclusive) to be searched
1088      * @param key the value to be searched for
1089      * @return index of the search key, if it is contained in the array
1090      *         within the specified range;
1091      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
1092      *         <i>insertion point</i> is defined as the point at which the
1093      *         key would be inserted into the array: the index of the first
1094      *         element in the range greater than the key,
1095      *         or <tt>toIndex</tt> if all
1096      *         elements in the range are less than the specified key.  Note
1097      *         that this guarantees that the return value will be &gt;= 0 if
1098      *         and only if the key is found.
1099      * @throws IllegalArgumentException
1100      *         if {@code fromIndex > toIndex}
1101      * @throws ArrayIndexOutOfBoundsException
1102      *         if {@code fromIndex < 0 or toIndex > a.length}
1103      * @since 1.6
1104      */
1105     public static int binarySearch(char[] a, int fromIndex, int toIndex,
1106                                    char key) {
1107         rangeCheck(a.length, fromIndex, toIndex);
1108         return binarySearch0(a, fromIndex, toIndex, key);
1109     }
1110 
1111     // Like public version, but without range checks.
1112     private static int binarySearch0(char[] a, int fromIndex, int toIndex,
1113                                      char key) {
1114         int low = fromIndex;
1115         int high = toIndex - 1;
1116 
1117         while (low <= high) {
1118             int mid = (low + high) >>> 1;
1119             char midVal = a[mid];
1120 
1121             if (midVal < key)
1122                 low = mid + 1;
1123             else if (midVal > key)
1124                 high = mid - 1;
1125             else
1126                 return mid; // key found
1127         }
1128         return -(low + 1);  // key not found.
1129     }
1130 
1131     /**
1132      * Searches the specified array of bytes for the specified value using the
1133      * binary search algorithm.  The array must be sorted (as
1134      * by the {@link #sort(byte[])} method) prior to making this call.  If it
1135      * is not sorted, the results are undefined.  If the array contains
1136      * multiple elements with the specified value, there is no guarantee which
1137      * one will be found.
1138      *
1139      * @param a the array to be searched
1140      * @param key the value to be searched for
1141      * @return index of the search key, if it is contained in the array;
1142      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
1143      *         <i>insertion point</i> is defined as the point at which the
1144      *         key would be inserted into the array: the index of the first
1145      *         element greater than the key, or <tt>a.length</tt> if all
1146      *         elements in the array are less than the specified key.  Note
1147      *         that this guarantees that the return value will be &gt;= 0 if
1148      *         and only if the key is found.
1149      */
1150     public static int binarySearch(byte[] a, byte key) {
1151         return binarySearch0(a, 0, a.length, key);
1152     }
1153 
1154     /**
1155      * Searches a range of
1156      * the specified array of bytes for the specified value using the
1157      * binary search algorithm.
1158      * The range must be sorted (as
1159      * by the {@link #sort(byte[], int, int)} method)
1160      * prior to making this call.  If it
1161      * is not sorted, the results are undefined.  If the range contains
1162      * multiple elements with the specified value, there is no guarantee which
1163      * one will be found.
1164      *
1165      * @param a the array to be searched
1166      * @param fromIndex the index of the first element (inclusive) to be
1167      *          searched
1168      * @param toIndex the index of the last element (exclusive) to be searched
1169      * @param key the value to be searched for
1170      * @return index of the search key, if it is contained in the array
1171      *         within the specified range;
1172      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
1173      *         <i>insertion point</i> is defined as the point at which the
1174      *         key would be inserted into the array: the index of the first
1175      *         element in the range greater than the key,
1176      *         or <tt>toIndex</tt> if all
1177      *         elements in the range are less than the specified key.  Note
1178      *         that this guarantees that the return value will be &gt;= 0 if
1179      *         and only if the key is found.
1180      * @throws IllegalArgumentException
1181      *         if {@code fromIndex > toIndex}
1182      * @throws ArrayIndexOutOfBoundsException
1183      *         if {@code fromIndex < 0 or toIndex > a.length}
1184      * @since 1.6
1185      */
1186     public static int binarySearch(byte[] a, int fromIndex, int toIndex,
1187                                    byte key) {
1188         rangeCheck(a.length, fromIndex, toIndex);
1189         return binarySearch0(a, fromIndex, toIndex, key);
1190     }
1191 
1192     // Like public version, but without range checks.
1193     private static int binarySearch0(byte[] a, int fromIndex, int toIndex,
1194                                      byte key) {
1195         int low = fromIndex;
1196         int high = toIndex - 1;
1197 
1198         while (low <= high) {
1199             int mid = (low + high) >>> 1;
1200             byte midVal = a[mid];
1201 
1202             if (midVal < key)
1203                 low = mid + 1;
1204             else if (midVal > key)
1205                 high = mid - 1;
1206             else
1207                 return mid; // key found
1208         }
1209         return -(low + 1);  // key not found.
1210     }
1211 
1212     /**
1213      * Searches the specified array of doubles for the specified value using
1214      * the binary search algorithm.  The array must be sorted
1215      * (as by the {@link #sort(double[])} method) prior to making this call.
1216      * If it is not sorted, the results are undefined.  If the array contains
1217      * multiple elements with the specified value, there is no guarantee which
1218      * one will be found.  This method considers all NaN values to be
1219      * equivalent and equal.
1220      *
1221      * @param a the array to be searched
1222      * @param key the value to be searched for
1223      * @return index of the search key, if it is contained in the array;
1224      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
1225      *         <i>insertion point</i> is defined as the point at which the
1226      *         key would be inserted into the array: the index of the first
1227      *         element greater than the key, or <tt>a.length</tt> if all
1228      *         elements in the array are less than the specified key.  Note
1229      *         that this guarantees that the return value will be &gt;= 0 if
1230      *         and only if the key is found.
1231      */
1232     public static int binarySearch(double[] a, double key) {
1233         return binarySearch0(a, 0, a.length, key);
1234     }
1235 
1236     /**
1237      * Searches a range of
1238      * the specified array of doubles for the specified value using
1239      * the binary search algorithm.
1240      * The range must be sorted
1241      * (as by the {@link #sort(double[], int, int)} method)
1242      * prior to making this call.
1243      * If it is not sorted, the results are undefined.  If the range contains
1244      * multiple elements with the specified value, there is no guarantee which
1245      * one will be found.  This method considers all NaN values to be
1246      * equivalent and equal.
1247      *
1248      * @param a the array to be searched
1249      * @param fromIndex the index of the first element (inclusive) to be
1250      *          searched
1251      * @param toIndex the index of the last element (exclusive) to be searched
1252      * @param key the value to be searched for
1253      * @return index of the search key, if it is contained in the array
1254      *         within the specified range;
1255      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
1256      *         <i>insertion point</i> is defined as the point at which the
1257      *         key would be inserted into the array: the index of the first
1258      *         element in the range greater than the key,
1259      *         or <tt>toIndex</tt> if all
1260      *         elements in the range are less than the specified key.  Note
1261      *         that this guarantees that the return value will be &gt;= 0 if
1262      *         and only if the key is found.
1263      * @throws IllegalArgumentException
1264      *         if {@code fromIndex > toIndex}
1265      * @throws ArrayIndexOutOfBoundsException
1266      *         if {@code fromIndex < 0 or toIndex > a.length}
1267      * @since 1.6
1268      */
1269     public static int binarySearch(double[] a, int fromIndex, int toIndex,
1270                                    double key) {
1271         rangeCheck(a.length, fromIndex, toIndex);
1272         return binarySearch0(a, fromIndex, toIndex, key);
1273     }
1274 
1275     // Like public version, but without range checks.
1276     private static int binarySearch0(double[] a, int fromIndex, int toIndex,
1277                                      double key) {
1278         int low = fromIndex;
1279         int high = toIndex - 1;
1280 
1281         while (low <= high) {
1282             int mid = (low + high) >>> 1;
1283             double midVal = a[mid];
1284 
1285             if (midVal < key)
1286                 low = mid + 1;  // Neither val is NaN, thisVal is smaller
1287             else if (midVal > key)
1288                 high = mid - 1; // Neither val is NaN, thisVal is larger
1289             else {
1290                 long midBits = Double.doubleToLongBits(midVal);
1291                 long keyBits = Double.doubleToLongBits(key);
1292                 if (midBits == keyBits)     // Values are equal
1293                     return mid;             // Key found
1294                 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
1295                     low = mid + 1;
1296                 else                        // (0.0, -0.0) or (NaN, !NaN)
1297                     high = mid - 1;
1298             }
1299         }
1300         return -(low + 1);  // key not found.
1301     }
1302 
1303     /**
1304      * Searches the specified array of floats for the specified value using
1305      * the binary search algorithm. The array must be sorted
1306      * (as by the {@link #sort(float[])} method) prior to making this call. If
1307      * it is not sorted, the results are undefined. If the array contains
1308      * multiple elements with the specified value, there is no guarantee which
1309      * one will be found. This method considers all NaN values to be
1310      * equivalent and equal.
1311      *
1312      * @param a the array to be searched
1313      * @param key the value to be searched for
1314      * @return index of the search key, if it is contained in the array;
1315      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1316      *         <i>insertion point</i> is defined as the point at which the
1317      *         key would be inserted into the array: the index of the first
1318      *         element greater than the key, or <tt>a.length</tt> if all
1319      *         elements in the array are less than the specified key. Note
1320      *         that this guarantees that the return value will be &gt;= 0 if
1321      *         and only if the key is found.
1322      */
1323     public static int binarySearch(float[] a, float key) {
1324         return binarySearch0(a, 0, a.length, key);
1325     }
1326 
1327     /**
1328      * Searches a range of
1329      * the specified array of floats for the specified value using
1330      * the binary search algorithm.
1331      * The range must be sorted
1332      * (as by the {@link #sort(float[], int, int)} method)
1333      * prior to making this call. If
1334      * it is not sorted, the results are undefined. If the range contains
1335      * multiple elements with the specified value, there is no guarantee which
1336      * one will be found. This method considers all NaN values to be
1337      * equivalent and equal.
1338      *
1339      * @param a the array to be searched
1340      * @param fromIndex the index of the first element (inclusive) to be
1341      *          searched
1342      * @param toIndex the index of the last element (exclusive) to be searched
1343      * @param key the value to be searched for
1344      * @return index of the search key, if it is contained in the array
1345      *         within the specified range;
1346      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1347      *         <i>insertion point</i> is defined as the point at which the
1348      *         key would be inserted into the array: the index of the first
1349      *         element in the range greater than the key,
1350      *         or <tt>toIndex</tt> if all
1351      *         elements in the range are less than the specified key. Note
1352      *         that this guarantees that the return value will be &gt;= 0 if
1353      *         and only if the key is found.
1354      * @throws IllegalArgumentException
1355      *         if {@code fromIndex > toIndex}
1356      * @throws ArrayIndexOutOfBoundsException
1357      *         if {@code fromIndex < 0 or toIndex > a.length}
1358      * @since 1.6
1359      */
1360     public static int binarySearch(float[] a, int fromIndex, int toIndex,
1361                                    float key) {
1362         rangeCheck(a.length, fromIndex, toIndex);
1363         return binarySearch0(a, fromIndex, toIndex, key);
1364     }
1365 
1366     // Like public version, but without range checks.
1367     private static int binarySearch0(float[] a, int fromIndex, int toIndex,
1368                                      float key) {
1369         int low = fromIndex;
1370         int high = toIndex - 1;
1371 
1372         while (low <= high) {
1373             int mid = (low + high) >>> 1;
1374             float midVal = a[mid];
1375 
1376             if (midVal < key)
1377                 low = mid + 1;  // Neither val is NaN, thisVal is smaller
1378             else if (midVal > key)
1379                 high = mid - 1; // Neither val is NaN, thisVal is larger
1380             else {
1381                 int midBits = Float.floatToIntBits(midVal);
1382                 int keyBits = Float.floatToIntBits(key);
1383                 if (midBits == keyBits)     // Values are equal
1384                     return mid;             // Key found
1385                 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
1386                     low = mid + 1;
1387                 else                        // (0.0, -0.0) or (NaN, !NaN)
1388                     high = mid - 1;
1389             }
1390         }
1391         return -(low + 1);  // key not found.
1392     }
1393 
1394     /**
1395      * Searches the specified array for the specified object using the binary
1396      * search algorithm. The array must be sorted into ascending order
1397      * according to the
1398      * {@linkplain Comparable natural ordering}
1399      * of its elements (as by the
1400      * {@link #sort(Object[])} method) prior to making this call.
1401      * If it is not sorted, the results are undefined.
1402      * (If the array contains elements that are not mutually comparable (for
1403      * example, strings and integers), it <i>cannot</i> be sorted according
1404      * to the natural ordering of its elements, hence results are undefined.)
1405      * If the array contains multiple
1406      * elements equal to the specified object, there is no guarantee which
1407      * one will be found.
1408      *
1409      * @param a the array to be searched
1410      * @param key the value to be searched for
1411      * @return index of the search key, if it is contained in the array;
1412      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
1413      *         <i>insertion point</i> is defined as the point at which the
1414      *         key would be inserted into the array: the index of the first
1415      *         element greater than the key, or <tt>a.length</tt> if all
1416      *         elements in the array are less than the specified key.  Note
1417      *         that this guarantees that the return value will be &gt;= 0 if
1418      *         and only if the key is found.
1419      * @throws ClassCastException if the search key is not comparable to the
1420      *         elements of the array.
1421      */
1422     public static int binarySearch(Object[] a, Object key) {
1423         return binarySearch0(a, 0, a.length, key);
1424     }
1425 
1426     /**
1427      * Searches a range of
1428      * the specified array for the specified object using the binary
1429      * search algorithm.
1430      * The range must be sorted into ascending order
1431      * according to the
1432      * {@linkplain Comparable natural ordering}
1433      * of its elements (as by the
1434      * {@link #sort(Object[], int, int)} method) prior to making this
1435      * call.  If it is not sorted, the results are undefined.
1436      * (If the range contains elements that are not mutually comparable (for
1437      * example, strings and integers), it <i>cannot</i> be sorted according
1438      * to the natural ordering of its elements, hence results are undefined.)
1439      * If the range contains multiple
1440      * elements equal to the specified object, there is no guarantee which
1441      * one will be found.
1442      *
1443      * @param a the array to be searched
1444      * @param fromIndex the index of the first element (inclusive) to be
1445      *          searched
1446      * @param toIndex the index of the last element (exclusive) to be searched
1447      * @param key the value to be searched for
1448      * @return index of the search key, if it is contained in the array
1449      *         within the specified range;
1450      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
1451      *         <i>insertion point</i> is defined as the point at which the
1452      *         key would be inserted into the array: the index of the first
1453      *         element in the range greater than the key,
1454      *         or <tt>toIndex</tt> if all
1455      *         elements in the range are less than the specified key.  Note
1456      *         that this guarantees that the return value will be &gt;= 0 if
1457      *         and only if the key is found.
1458      * @throws ClassCastException if the search key is not comparable to the
1459      *         elements of the array within the specified range.
1460      * @throws IllegalArgumentException
1461      *         if {@code fromIndex > toIndex}
1462      * @throws ArrayIndexOutOfBoundsException
1463      *         if {@code fromIndex < 0 or toIndex > a.length}
1464      * @since 1.6
1465      */
1466     public static int binarySearch(Object[] a, int fromIndex, int toIndex,
1467                                    Object key) {
1468         rangeCheck(a.length, fromIndex, toIndex);
1469         return binarySearch0(a, fromIndex, toIndex, key);
1470     }
1471 
1472     // Like public version, but without range checks.
1473     private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
1474                                      Object key) {
1475         int low = fromIndex;
1476         int high = toIndex - 1;
1477 
1478         while (low <= high) {
1479             int mid = (low + high) >>> 1;
1480             Comparable midVal = (Comparable)a[mid];
1481             int cmp = midVal.compareTo(key);
1482 
1483             if (cmp < 0)
1484                 low = mid + 1;
1485             else if (cmp > 0)
1486                 high = mid - 1;
1487             else
1488                 return mid; // key found
1489         }
1490         return -(low + 1);  // key not found.
1491     }
1492 
1493     /**
1494      * Searches the specified array for the specified object using the binary
1495      * search algorithm.  The array must be sorted into ascending order
1496      * according to the specified comparator (as by the
1497      * {@link #sort(Object[], Comparator) sort(T[], Comparator)}
1498      * method) prior to making this call.  If it is
1499      * not sorted, the results are undefined.
1500      * If the array contains multiple
1501      * elements equal to the specified object, there is no guarantee which one
1502      * will be found.
1503      *
1504      * @param a the array to be searched
1505      * @param key the value to be searched for
1506      * @param c the comparator by which the array is ordered.  A
1507      *        <tt>null</tt> value indicates that the elements'
1508      *        {@linkplain Comparable natural ordering} should be used.
1509      * @return index of the search key, if it is contained in the array;
1510      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
1511      *         <i>insertion point</i> is defined as the point at which the
1512      *         key would be inserted into the array: the index of the first
1513      *         element greater than the key, or <tt>a.length</tt> if all
1514      *         elements in the array are less than the specified key.  Note
1515      *         that this guarantees that the return value will be &gt;= 0 if
1516      *         and only if the key is found.
1517      * @throws ClassCastException if the array contains elements that are not
1518      *         <i>mutually comparable</i> using the specified comparator,
1519      *         or the search key is not comparable to the
1520      *         elements of the array using this comparator.
1521      */
1522     public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) {
1523         return binarySearch0(a, 0, a.length, key, c);
1524     }
1525 
1526     /**
1527      * Searches a range of
1528      * the specified array for the specified object using the binary
1529      * search algorithm.
1530      * The range must be sorted into ascending order
1531      * according to the specified comparator (as by the
1532      * {@link #sort(Object[], int, int, Comparator)
1533      * sort(T[], int, int, Comparator)}
1534      * method) prior to making this call.
1535      * If it is not sorted, the results are undefined.
1536      * If the range contains multiple elements equal to the specified object,
1537      * there is no guarantee which one will be found.
1538      *
1539      * @param a the array to be searched
1540      * @param fromIndex the index of the first element (inclusive) to be
1541      *          searched
1542      * @param toIndex the index of the last element (exclusive) to be searched
1543      * @param key the value to be searched for
1544      * @param c the comparator by which the array is ordered.  A
1545      *        <tt>null</tt> value indicates that the elements'
1546      *        {@linkplain Comparable natural ordering} should be used.
1547      * @return index of the search key, if it is contained in the array
1548      *         within the specified range;
1549      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
1550      *         <i>insertion point</i> is defined as the point at which the
1551      *         key would be inserted into the array: the index of the first
1552      *         element in the range greater than the key,
1553      *         or <tt>toIndex</tt> if all
1554      *         elements in the range are less than the specified key.  Note
1555      *         that this guarantees that the return value will be &gt;= 0 if
1556      *         and only if the key is found.
1557      * @throws ClassCastException if the range contains elements that are not
1558      *         <i>mutually comparable</i> using the specified comparator,
1559      *         or the search key is not comparable to the
1560      *         elements in the range using this comparator.
1561      * @throws IllegalArgumentException
1562      *         if {@code fromIndex > toIndex}
1563      * @throws ArrayIndexOutOfBoundsException
1564      *         if {@code fromIndex < 0 or toIndex > a.length}
1565      * @since 1.6
1566      */
1567     public static <T> int binarySearch(T[] a, int fromIndex, int toIndex,
1568                                        T key, Comparator<? super T> c) {
1569         rangeCheck(a.length, fromIndex, toIndex);
1570         return binarySearch0(a, fromIndex, toIndex, key, c);
1571     }
1572 
1573     // Like public version, but without range checks.
1574     private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
1575                                          T key, Comparator<? super T> c) {
1576         if (c == null) {
1577             return binarySearch0(a, fromIndex, toIndex, key);
1578         }
1579         int low = fromIndex;
1580         int high = toIndex - 1;
1581 
1582         while (low <= high) {
1583             int mid = (low + high) >>> 1;
1584             T midVal = a[mid];
1585             int cmp = c.compare(midVal, key);
1586             if (cmp < 0)
1587                 low = mid + 1;
1588             else if (cmp > 0)
1589                 high = mid - 1;
1590             else
1591                 return mid; // key found
1592         }
1593         return -(low + 1);  // key not found.
1594     }
1595 
1596     // Equality Testing
1597 
1598     /**
1599      * Returns <tt>true</tt> if the two specified arrays of longs are
1600      * <i>equal</i> to one another.  Two arrays are considered equal if both
1601      * arrays contain the same number of elements, and all corresponding pairs
1602      * of elements in the two arrays are equal.  In other words, two arrays
1603      * are equal if they contain the same elements in the same order.  Also,
1604      * two array references are considered equal if both are <tt>null</tt>.<p>
1605      *
1606      * @param a one array to be tested for equality
1607      * @param a2 the other array to be tested for equality
1608      * @return <tt>true</tt> if the two arrays are equal
1609      */
1610     public static boolean equals(long[] a, long[] a2) {
1611         if (a==a2)
1612             return true;
1613         if (a==null || a2==null)
1614             return false;
1615 
1616         int length = a.length;
1617         if (a2.length != length)
1618             return false;
1619 
1620         for (int i=0; i<length; i++)
1621             if (a[i] != a2[i])
1622                 return false;
1623 
1624         return true;
1625     }
1626 
1627     /**
1628      * Returns <tt>true</tt> if the two specified arrays of ints are
1629      * <i>equal</i> to one another.  Two arrays are considered equal if both
1630      * arrays contain the same number of elements, and all corresponding pairs
1631      * of elements in the two arrays are equal.  In other words, two arrays
1632      * are equal if they contain the same elements in the same order.  Also,
1633      * two array references are considered equal if both are <tt>null</tt>.<p>
1634      *
1635      * @param a one array to be tested for equality
1636      * @param a2 the other array to be tested for equality
1637      * @return <tt>true</tt> if the two arrays are equal
1638      */
1639     public static boolean equals(int[] a, int[] a2) {
1640         if (a==a2)
1641             return true;
1642         if (a==null || a2==null)
1643             return false;
1644 
1645         int length = a.length;
1646         if (a2.length != length)
1647             return false;
1648 
1649         for (int i=0; i<length; i++)
1650             if (a[i] != a2[i])
1651                 return false;
1652 
1653         return true;
1654     }
1655 
1656     /**
1657      * Returns <tt>true</tt> if the two specified arrays of shorts are
1658      * <i>equal</i> to one another.  Two arrays are considered equal if both
1659      * arrays contain the same number of elements, and all corresponding pairs
1660      * of elements in the two arrays are equal.  In other words, two arrays
1661      * are equal if they contain the same elements in the same order.  Also,
1662      * two array references are considered equal if both are <tt>null</tt>.<p>
1663      *
1664      * @param a one array to be tested for equality
1665      * @param a2 the other array to be tested for equality
1666      * @return <tt>true</tt> if the two arrays are equal
1667      */
1668     public static boolean equals(short[] a, short a2[]) {
1669         if (a==a2)
1670             return true;
1671         if (a==null || a2==null)
1672             return false;
1673 
1674         int length = a.length;
1675         if (a2.length != length)
1676             return false;
1677 
1678         for (int i=0; i<length; i++)
1679             if (a[i] != a2[i])
1680                 return false;
1681 
1682         return true;
1683     }
1684 
1685     /**
1686      * Returns <tt>true</tt> if the two specified arrays of chars are
1687      * <i>equal</i> to one another.  Two arrays are considered equal if both
1688      * arrays contain the same number of elements, and all corresponding pairs
1689      * of elements in the two arrays are equal.  In other words, two arrays
1690      * are equal if they contain the same elements in the same order.  Also,
1691      * two array references are considered equal if both are <tt>null</tt>.<p>
1692      *
1693      * @param a one array to be tested for equality
1694      * @param a2 the other array to be tested for equality
1695      * @return <tt>true</tt> if the two arrays are equal
1696      */
1697     public static boolean equals(char[] a, char[] a2) {
1698         if (a==a2)
1699             return true;
1700         if (a==null || a2==null)
1701             return false;
1702 
1703         int length = a.length;
1704         if (a2.length != length)
1705             return false;
1706 
1707         for (int i=0; i<length; i++)
1708             if (a[i] != a2[i])
1709                 return false;
1710 
1711         return true;
1712     }
1713 
1714     /**
1715      * Returns <tt>true</tt> if the two specified arrays of bytes are
1716      * <i>equal</i> to one another.  Two arrays are considered equal if both
1717      * arrays contain the same number of elements, and all corresponding pairs
1718      * of elements in the two arrays are equal.  In other words, two arrays
1719      * are equal if they contain the same elements in the same order.  Also,
1720      * two array references are considered equal if both are <tt>null</tt>.<p>
1721      *
1722      * @param a one array to be tested for equality
1723      * @param a2 the other array to be tested for equality
1724      * @return <tt>true</tt> if the two arrays are equal
1725      */
1726     public static boolean equals(byte[] a, byte[] a2) {
1727         if (a==a2)
1728             return true;
1729         if (a==null || a2==null)
1730             return false;
1731 
1732         int length = a.length;
1733         if (a2.length != length)
1734             return false;
1735 
1736         for (int i=0; i<length; i++)
1737             if (a[i] != a2[i])
1738                 return false;
1739 
1740         return true;
1741     }
1742 
1743     /**
1744      * Returns <tt>true</tt> if the two specified arrays of booleans are
1745      * <i>equal</i> to one another.  Two arrays are considered equal if both
1746      * arrays contain the same number of elements, and all corresponding pairs
1747      * of elements in the two arrays are equal.  In other words, two arrays
1748      * are equal if they contain the same elements in the same order.  Also,
1749      * two array references are considered equal if both are <tt>null</tt>.<p>
1750      *
1751      * @param a one array to be tested for equality
1752      * @param a2 the other array to be tested for equality
1753      * @return <tt>true</tt> if the two arrays are equal
1754      */
1755     public static boolean equals(boolean[] a, boolean[] a2) {
1756         if (a==a2)
1757             return true;
1758         if (a==null || a2==null)
1759             return false;
1760 
1761         int length = a.length;
1762         if (a2.length != length)
1763             return false;
1764 
1765         for (int i=0; i<length; i++)
1766             if (a[i] != a2[i])
1767                 return false;
1768 
1769         return true;
1770     }
1771 
1772     /**
1773      * Returns <tt>true</tt> if the two specified arrays of doubles are
1774      * <i>equal</i> to one another.  Two arrays are considered equal if both
1775      * arrays contain the same number of elements, and all corresponding pairs
1776      * of elements in the two arrays are equal.  In other words, two arrays
1777      * are equal if they contain the same elements in the same order.  Also,
1778      * two array references are considered equal if both are <tt>null</tt>.<p>
1779      *
1780      * Two doubles <tt>d1</tt> and <tt>d2</tt> are considered equal if:
1781      * <pre>    <tt>new Double(d1).equals(new Double(d2))</tt></pre>
1782      * (Unlike the <tt>==</tt> operator, this method considers
1783      * <tt>NaN</tt> equals to itself, and 0.0d unequal to -0.0d.)
1784      *
1785      * @param a one array to be tested for equality
1786      * @param a2 the other array to be tested for equality
1787      * @return <tt>true</tt> if the two arrays are equal
1788      * @see Double#equals(Object)
1789      */
1790     public static boolean equals(double[] a, double[] a2) {
1791         if (a==a2)
1792             return true;
1793         if (a==null || a2==null)
1794             return false;
1795 
1796         int length = a.length;
1797         if (a2.length != length)
1798             return false;
1799 
1800         for (int i=0; i<length; i++)
1801             if (Double.doubleToLongBits(a[i])!=Double.doubleToLongBits(a2[i]))
1802                 return false;
1803 
1804         return true;
1805     }
1806 
1807     /**
1808      * Returns <tt>true</tt> if the two specified arrays of floats are
1809      * <i>equal</i> to one another.  Two arrays are considered equal if both
1810      * arrays contain the same number of elements, and all corresponding pairs
1811      * of elements in the two arrays are equal.  In other words, two arrays
1812      * are equal if they contain the same elements in the same order.  Also,
1813      * two array references are considered equal if both are <tt>null</tt>.<p>
1814      *
1815      * Two floats <tt>f1</tt> and <tt>f2</tt> are considered equal if:
1816      * <pre>    <tt>new Float(f1).equals(new Float(f2))</tt></pre>
1817      * (Unlike the <tt>==</tt> operator, this method considers
1818      * <tt>NaN</tt> equals to itself, and 0.0f unequal to -0.0f.)
1819      *
1820      * @param a one array to be tested for equality
1821      * @param a2 the other array to be tested for equality
1822      * @return <tt>true</tt> if the two arrays are equal
1823      * @see Float#equals(Object)
1824      */
1825     public static boolean equals(float[] a, float[] a2) {
1826         if (a==a2)
1827             return true;
1828         if (a==null || a2==null)
1829             return false;
1830 
1831         int length = a.length;
1832         if (a2.length != length)
1833             return false;
1834 
1835         for (int i=0; i<length; i++)
1836             if (Float.floatToIntBits(a[i])!=Float.floatToIntBits(a2[i]))
1837                 return false;
1838 
1839         return true;
1840     }
1841 
1842     /**
1843      * Returns <tt>true</tt> if the two specified arrays of Objects are
1844      * <i>equal</i> to one another.  The two arrays are considered equal if
1845      * both arrays contain the same number of elements, and all corresponding
1846      * pairs of elements in the two arrays are equal.  Two objects <tt>e1</tt>
1847      * and <tt>e2</tt> are considered <i>equal</i> if <tt>(e1==null ? e2==null
1848      * : e1.equals(e2))</tt>.  In other words, the two arrays are equal if
1849      * they contain the same elements in the same order.  Also, two array
1850      * references are considered equal if both are <tt>null</tt>.<p>
1851      *
1852      * @param a one array to be tested for equality
1853      * @param a2 the other array to be tested for equality
1854      * @return <tt>true</tt> if the two arrays are equal
1855      */
1856     public static boolean equals(Object[] a, Object[] a2) {
1857         if (a==a2)
1858             return true;
1859         if (a==null || a2==null)
1860             return false;
1861 
1862         int length = a.length;
1863         if (a2.length != length)
1864             return false;
1865 
1866         for (int i=0; i<length; i++) {
1867             Object o1 = a[i];
1868             Object o2 = a2[i];
1869             if (!(o1==null ? o2==null : o1.equals(o2)))
1870                 return false;
1871         }
1872 
1873         return true;
1874     }
1875 
1876     // Filling
1877 
1878     /**
1879      * Assigns the specified long value to each element of the specified array
1880      * of longs.
1881      *
1882      * @param a the array to be filled
1883      * @param val the value to be stored in all elements of the array
1884      */
1885     public static void fill(long[] a, long val) {
1886         for (int i = 0, len = a.length; i < len; i++)
1887             a[i] = val;
1888     }
1889 
1890     /**
1891      * Assigns the specified long value to each element of the specified
1892      * range of the specified array of longs.  The range to be filled
1893      * extends from index <tt>fromIndex</tt>, inclusive, to index
1894      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the
1895      * range to be filled is empty.)
1896      *
1897      * @param a the array to be filled
1898      * @param fromIndex the index of the first element (inclusive) to be
1899      *        filled with the specified value
1900      * @param toIndex the index of the last element (exclusive) to be
1901      *        filled with the specified value
1902      * @param val the value to be stored in all elements of the array
1903      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
1904      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
1905      *         <tt>toIndex &gt; a.length</tt>
1906      */
1907     public static void fill(long[] a, int fromIndex, int toIndex, long val) {
1908         rangeCheck(a.length, fromIndex, toIndex);
1909         for (int i = fromIndex; i < toIndex; i++)
1910             a[i] = val;
1911     }
1912 
1913     /**
1914      * Assigns the specified int value to each element of the specified array
1915      * of ints.
1916      *
1917      * @param a the array to be filled
1918      * @param val the value to be stored in all elements of the array
1919      */
1920     public static void fill(int[] a, int val) {
1921         for (int i = 0, len = a.length; i < len; i++)
1922             a[i] = val;
1923     }
1924 
1925     /**
1926      * Assigns the specified int value to each element of the specified
1927      * range of the specified array of ints.  The range to be filled
1928      * extends from index <tt>fromIndex</tt>, inclusive, to index
1929      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the
1930      * range to be filled is empty.)
1931      *
1932      * @param a the array to be filled
1933      * @param fromIndex the index of the first element (inclusive) to be
1934      *        filled with the specified value
1935      * @param toIndex the index of the last element (exclusive) to be
1936      *        filled with the specified value
1937      * @param val the value to be stored in all elements of the array
1938      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
1939      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
1940      *         <tt>toIndex &gt; a.length</tt>
1941      */
1942     public static void fill(int[] a, int fromIndex, int toIndex, int val) {
1943         rangeCheck(a.length, fromIndex, toIndex);
1944         for (int i = fromIndex; i < toIndex; i++)
1945             a[i] = val;
1946     }
1947 
1948     /**
1949      * Assigns the specified short value to each element of the specified array
1950      * of shorts.
1951      *
1952      * @param a the array to be filled
1953      * @param val the value to be stored in all elements of the array
1954      */
1955     public static void fill(short[] a, short val) {
1956         for (int i = 0, len = a.length; i < len; i++)
1957             a[i] = val;
1958     }
1959 
1960     /**
1961      * Assigns the specified short value to each element of the specified
1962      * range of the specified array of shorts.  The range to be filled
1963      * extends from index <tt>fromIndex</tt>, inclusive, to index
1964      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the
1965      * range to be filled is empty.)
1966      *
1967      * @param a the array to be filled
1968      * @param fromIndex the index of the first element (inclusive) to be
1969      *        filled with the specified value
1970      * @param toIndex the index of the last element (exclusive) to be
1971      *        filled with the specified value
1972      * @param val the value to be stored in all elements of the array
1973      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
1974      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
1975      *         <tt>toIndex &gt; a.length</tt>
1976      */
1977     public static void fill(short[] a, int fromIndex, int toIndex, short val) {
1978         rangeCheck(a.length, fromIndex, toIndex);
1979         for (int i = fromIndex; i < toIndex; i++)
1980             a[i] = val;
1981     }
1982 
1983     /**
1984      * Assigns the specified char value to each element of the specified array
1985      * of chars.
1986      *
1987      * @param a the array to be filled
1988      * @param val the value to be stored in all elements of the array
1989      */
1990     public static void fill(char[] a, char val) {
1991         for (int i = 0, len = a.length; i < len; i++)
1992             a[i] = val;
1993     }
1994 
1995     /**
1996      * Assigns the specified char value to each element of the specified
1997      * range of the specified array of chars.  The range to be filled
1998      * extends from index <tt>fromIndex</tt>, inclusive, to index
1999      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the
2000      * range to be filled is empty.)
2001      *
2002      * @param a the array to be filled
2003      * @param fromIndex the index of the first element (inclusive) to be
2004      *        filled with the specified value
2005      * @param toIndex the index of the last element (exclusive) to be
2006      *        filled with the specified value
2007      * @param val the value to be stored in all elements of the array
2008      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
2009      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
2010      *         <tt>toIndex &gt; a.length</tt>
2011      */
2012     public static void fill(char[] a, int fromIndex, int toIndex, char val) {
2013         rangeCheck(a.length, fromIndex, toIndex);
2014         for (int i = fromIndex; i < toIndex; i++)
2015             a[i] = val;
2016     }
2017 
2018     /**
2019      * Assigns the specified byte value to each element of the specified array
2020      * of bytes.
2021      *
2022      * @param a the array to be filled
2023      * @param val the value to be stored in all elements of the array
2024      */
2025     public static void fill(byte[] a, byte val) {
2026         for (int i = 0, len = a.length; i < len; i++)
2027             a[i] = val;
2028     }
2029 
2030     /**
2031      * Assigns the specified byte value to each element of the specified
2032      * range of the specified array of bytes.  The range to be filled
2033      * extends from index <tt>fromIndex</tt>, inclusive, to index
2034      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the
2035      * range to be filled is empty.)
2036      *
2037      * @param a the array to be filled
2038      * @param fromIndex the index of the first element (inclusive) to be
2039      *        filled with the specified value
2040      * @param toIndex the index of the last element (exclusive) to be
2041      *        filled with the specified value
2042      * @param val the value to be stored in all elements of the array
2043      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
2044      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
2045      *         <tt>toIndex &gt; a.length</tt>
2046      */
2047     public static void fill(byte[] a, int fromIndex, int toIndex, byte val) {
2048         rangeCheck(a.length, fromIndex, toIndex);
2049         for (int i = fromIndex; i < toIndex; i++)
2050             a[i] = val;
2051     }
2052 
2053     /**
2054      * Assigns the specified boolean value to each element of the specified
2055      * array of booleans.
2056      *
2057      * @param a the array to be filled
2058      * @param val the value to be stored in all elements of the array
2059      */
2060     public static void fill(boolean[] a, boolean val) {
2061         for (int i = 0, len = a.length; i < len; i++)
2062             a[i] = val;
2063     }
2064 
2065     /**
2066      * Assigns the specified boolean value to each element of the specified
2067      * range of the specified array of booleans.  The range to be filled
2068      * extends from index <tt>fromIndex</tt>, inclusive, to index
2069      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the
2070      * range to be filled is empty.)
2071      *
2072      * @param a the array to be filled
2073      * @param fromIndex the index of the first element (inclusive) to be
2074      *        filled with the specified value
2075      * @param toIndex the index of the last element (exclusive) to be
2076      *        filled with the specified value
2077      * @param val the value to be stored in all elements of the array
2078      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
2079      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
2080      *         <tt>toIndex &gt; a.length</tt>
2081      */
2082     public static void fill(boolean[] a, int fromIndex, int toIndex,
2083                             boolean val) {
2084         rangeCheck(a.length, fromIndex, toIndex);
2085         for (int i = fromIndex; i < toIndex; i++)
2086             a[i] = val;
2087     }
2088 
2089     /**
2090      * Assigns the specified double value to each element of the specified
2091      * array of doubles.
2092      *
2093      * @param a the array to be filled
2094      * @param val the value to be stored in all elements of the array
2095      */
2096     public static void fill(double[] a, double val) {
2097         for (int i = 0, len = a.length; i < len; i++)
2098             a[i] = val;
2099     }
2100 
2101     /**
2102      * Assigns the specified double value to each element of the specified
2103      * range of the specified array of doubles.  The range to be filled
2104      * extends from index <tt>fromIndex</tt>, inclusive, to index
2105      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the
2106      * range to be filled is empty.)
2107      *
2108      * @param a the array to be filled
2109      * @param fromIndex the index of the first element (inclusive) to be
2110      *        filled with the specified value
2111      * @param toIndex the index of the last element (exclusive) to be
2112      *        filled with the specified value
2113      * @param val the value to be stored in all elements of the array
2114      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
2115      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
2116      *         <tt>toIndex &gt; a.length</tt>
2117      */
2118     public static void fill(double[] a, int fromIndex, int toIndex,double val){
2119         rangeCheck(a.length, fromIndex, toIndex);
2120         for (int i = fromIndex; i < toIndex; i++)
2121             a[i] = val;
2122     }
2123 
2124     /**
2125      * Assigns the specified float value to each element of the specified array
2126      * of floats.
2127      *
2128      * @param a the array to be filled
2129      * @param val the value to be stored in all elements of the array
2130      */
2131     public static void fill(float[] a, float val) {
2132         for (int i = 0, len = a.length; i < len; i++)
2133             a[i] = val;
2134     }
2135 
2136     /**
2137      * Assigns the specified float value to each element of the specified
2138      * range of the specified array of floats.  The range to be filled
2139      * extends from index <tt>fromIndex</tt>, inclusive, to index
2140      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the
2141      * range to be filled is empty.)
2142      *
2143      * @param a the array to be filled
2144      * @param fromIndex the index of the first element (inclusive) to be
2145      *        filled with the specified value
2146      * @param toIndex the index of the last element (exclusive) to be
2147      *        filled with the specified value
2148      * @param val the value to be stored in all elements of the array
2149      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
2150      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
2151      *         <tt>toIndex &gt; a.length</tt>
2152      */
2153     public static void fill(float[] a, int fromIndex, int toIndex, float val) {
2154         rangeCheck(a.length, fromIndex, toIndex);
2155         for (int i = fromIndex; i < toIndex; i++)
2156             a[i] = val;
2157     }
2158 
2159     /**
2160      * Assigns the specified Object reference to each element of the specified
2161      * array of Objects.
2162      *
2163      * @param a the array to be filled
2164      * @param val the value to be stored in all elements of the array
2165      * @throws ArrayStoreException if the specified value is not of a
2166      *         runtime type that can be stored in the specified array
2167      */
2168     public static void fill(Object[] a, Object val) {
2169         for (int i = 0, len = a.length; i < len; i++)
2170             a[i] = val;
2171     }
2172 
2173     /**
2174      * Assigns the specified Object reference to each element of the specified
2175      * range of the specified array of Objects.  The range to be filled
2176      * extends from index <tt>fromIndex</tt>, inclusive, to index
2177      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the
2178      * range to be filled is empty.)
2179      *
2180      * @param a the array to be filled
2181      * @param fromIndex the index of the first element (inclusive) to be
2182      *        filled with the specified value
2183      * @param toIndex the index of the last element (exclusive) to be
2184      *        filled with the specified value
2185      * @param val the value to be stored in all elements of the array
2186      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>
2187      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or
2188      *         <tt>toIndex &gt; a.length</tt>
2189      * @throws ArrayStoreException if the specified value is not of a
2190      *         runtime type that can be stored in the specified array
2191      */
2192     public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
2193         rangeCheck(a.length, fromIndex, toIndex);
2194         for (int i = fromIndex; i < toIndex; i++)
2195             a[i] = val;
2196     }
2197 
2198     // Cloning
2199 
2200     /**
2201      * Copies the specified array, truncating or padding with nulls (if necessary)
2202      * so the copy has the specified length.  For all indices that are
2203      * valid in both the original array and the copy, the two arrays will
2204      * contain identical values.  For any indices that are valid in the
2205      * copy but not the original, the copy will contain <tt>null</tt>.
2206      * Such indices will exist if and only if the specified length
2207      * is greater than that of the original array.
2208      * The resulting array is of exactly the same class as the original array.
2209      *
2210      * @param original the array to be copied
2211      * @param newLength the length of the copy to be returned
2212      * @return a copy of the original array, truncated or padded with nulls
2213      *     to obtain the specified length
2214      * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2215      * @throws NullPointerException if <tt>original</tt> is null
2216      * @since 1.6
2217      */
2218     public static <T> T[] copyOf(T[] original, int newLength) {
2219         return (T[]) copyOf(original, newLength, original.getClass());
2220     }
2221 
2222     /**
2223      * Copies the specified array, truncating or padding with nulls (if necessary)
2224      * so the copy has the specified length.  For all indices that are
2225      * valid in both the original array and the copy, the two arrays will
2226      * contain identical values.  For any indices that are valid in the
2227      * copy but not the original, the copy will contain <tt>null</tt>.
2228      * Such indices will exist if and only if the specified length
2229      * is greater than that of the original array.
2230      * The resulting array is of the class <tt>newType</tt>.
2231      *
2232      * @param original the array to be copied
2233      * @param newLength the length of the copy to be returned
2234      * @param newType the class of the copy to be returned
2235      * @return a copy of the original array, truncated or padded with nulls
2236      *     to obtain the specified length
2237      * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2238      * @throws NullPointerException if <tt>original</tt> is null
2239      * @throws ArrayStoreException if an element copied from
2240      *     <tt>original</tt> is not of a runtime type that can be stored in
2241      *     an array of class <tt>newType</tt>
2242      * @since 1.6
2243      */
2244     public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
2245         T[] copy = ((Object)newType == (Object)Object[].class)
2246             ? (T[]) new Object[newLength]
2247             : (T[]) Array.newInstance(newType.getComponentType(), newLength);
2248         System.arraycopy(original, 0, copy, 0,
2249                          Math.min(original.length, newLength));
2250         return copy;
2251     }
2252 
2253     /**
2254      * Copies the specified array, truncating or padding with zeros (if necessary)
2255      * so the copy has the specified length.  For all indices that are
2256      * valid in both the original array and the copy, the two arrays will
2257      * contain identical values.  For any indices that are valid in the
2258      * copy but not the original, the copy will contain <tt>(byte)0</tt>.
2259      * Such indices will exist if and only if the specified length
2260      * is greater than that of the original array.
2261      *
2262      * @param original the array to be copied
2263      * @param newLength the length of the copy to be returned
2264      * @return a copy of the original array, truncated or padded with zeros
2265      *     to obtain the specified length
2266      * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2267      * @throws NullPointerException if <tt>original</tt> is null
2268      * @since 1.6
2269      */
2270     public static byte[] copyOf(byte[] original, int newLength) {
2271         byte[] copy = new byte[newLength];
2272         System.arraycopy(original, 0, copy, 0,
2273                          Math.min(original.length, newLength));
2274         return copy;
2275     }
2276 
2277     /**
2278      * Copies the specified array, truncating or padding with zeros (if necessary)
2279      * so the copy has the specified length.  For all indices that are
2280      * valid in both the original array and the copy, the two arrays will
2281      * contain identical values.  For any indices that are valid in the
2282      * copy but not the original, the copy will contain <tt>(short)0</tt>.
2283      * Such indices will exist if and only if the specified length
2284      * is greater than that of the original array.
2285      *
2286      * @param original the array to be copied
2287      * @param newLength the length of the copy to be returned
2288      * @return a copy of the original array, truncated or padded with zeros
2289      *     to obtain the specified length
2290      * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2291      * @throws NullPointerException if <tt>original</tt> is null
2292      * @since 1.6
2293      */
2294     public static short[] copyOf(short[] original, int newLength) {
2295         short[] copy = new short[newLength];
2296         System.arraycopy(original, 0, copy, 0,
2297                          Math.min(original.length, newLength));
2298         return copy;
2299     }
2300 
2301     /**
2302      * Copies the specified array, truncating or padding with zeros (if necessary)
2303      * so the copy has the specified length.  For all indices that are
2304      * valid in both the original array and the copy, the two arrays will
2305      * contain identical values.  For any indices that are valid in the
2306      * copy but not the original, the copy will contain <tt>0</tt>.
2307      * Such indices will exist if and only if the specified length
2308      * is greater than that of the original array.
2309      *
2310      * @param original the array to be copied
2311      * @param newLength the length of the copy to be returned
2312      * @return a copy of the original array, truncated or padded with zeros
2313      *     to obtain the specified length
2314      * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2315      * @throws NullPointerException if <tt>original</tt> is null
2316      * @since 1.6
2317      */
2318     public static int[] copyOf(int[] original, int newLength) {
2319         int[] copy = new int[newLength];
2320         System.arraycopy(original, 0, copy, 0,
2321                          Math.min(original.length, newLength));
2322         return copy;
2323     }
2324 
2325     /**
2326      * Copies the specified array, truncating or padding with zeros (if necessary)
2327      * so the copy has the specified length.  For all indices that are
2328      * valid in both the original array and the copy, the two arrays will
2329      * contain identical values.  For any indices that are valid in the
2330      * copy but not the original, the copy will contain <tt>0L</tt>.
2331      * Such indices will exist if and only if the specified length
2332      * is greater than that of the original array.
2333      *
2334      * @param original the array to be copied
2335      * @param newLength the length of the copy to be returned
2336      * @return a copy of the original array, truncated or padded with zeros
2337      *     to obtain the specified length
2338      * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2339      * @throws NullPointerException if <tt>original</tt> is null
2340      * @since 1.6
2341      */
2342     public static long[] copyOf(long[] original, int newLength) {
2343         long[] copy = new long[newLength];
2344         System.arraycopy(original, 0, copy, 0,
2345                          Math.min(original.length, newLength));
2346         return copy;
2347     }
2348 
2349     /**
2350      * Copies the specified array, truncating or padding with null characters (if necessary)
2351      * so the copy has the specified length.  For all indices that are valid
2352      * in both the original array and the copy, the two arrays will contain
2353      * identical values.  For any indices that are valid in the copy but not
2354      * the original, the copy will contain <tt>'\\u000'</tt>.  Such indices
2355      * will exist if and only if the specified length is greater than that of
2356      * the original array.
2357      *
2358      * @param original the array to be copied
2359      * @param newLength the length of the copy to be returned
2360      * @return a copy of the original array, truncated or padded with null characters
2361      *     to obtain the specified length
2362      * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2363      * @throws NullPointerException if <tt>original</tt> is null
2364      * @since 1.6
2365      */
2366     public static char[] copyOf(char[] original, int newLength) {
2367         char[] copy = new char[newLength];
2368         System.arraycopy(original, 0, copy, 0,
2369                          Math.min(original.length, newLength));
2370         return copy;
2371     }
2372 
2373     /**
2374      * Copies the specified array, truncating or padding with zeros (if necessary)
2375      * so the copy has the specified length.  For all indices that are
2376      * valid in both the original array and the copy, the two arrays will
2377      * contain identical values.  For any indices that are valid in the
2378      * copy but not the original, the copy will contain <tt>0f</tt>.
2379      * Such indices will exist if and only if the specified length
2380      * is greater than that of the original array.
2381      *
2382      * @param original the array to be copied
2383      * @param newLength the length of the copy to be returned
2384      * @return a copy of the original array, truncated or padded with zeros
2385      *     to obtain the specified length
2386      * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2387      * @throws NullPointerException if <tt>original</tt> is null
2388      * @since 1.6
2389      */
2390     public static float[] copyOf(float[] original, int newLength) {
2391         float[] copy = new float[newLength];
2392         System.arraycopy(original, 0, copy, 0,
2393                          Math.min(original.length, newLength));
2394         return copy;
2395     }
2396 
2397     /**
2398      * Copies the specified array, truncating or padding with zeros (if necessary)
2399      * so the copy has the specified length.  For all indices that are
2400      * valid in both the original array and the copy, the two arrays will
2401      * contain identical values.  For any indices that are valid in the
2402      * copy but not the original, the copy will contain <tt>0d</tt>.
2403      * Such indices will exist if and only if the specified length
2404      * is greater than that of the original array.
2405      *
2406      * @param original the array to be copied
2407      * @param newLength the length of the copy to be returned
2408      * @return a copy of the original array, truncated or padded with zeros
2409      *     to obtain the specified length
2410      * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2411      * @throws NullPointerException if <tt>original</tt> is null
2412      * @since 1.6
2413      */
2414     public static double[] copyOf(double[] original, int newLength) {
2415         double[] copy = new double[newLength];
2416         System.arraycopy(original, 0, copy, 0,
2417                          Math.min(original.length, newLength));
2418         return copy;
2419     }
2420 
2421     /**
2422      * Copies the specified array, truncating or padding with <tt>false</tt> (if necessary)
2423      * so the copy has the specified length.  For all indices that are
2424      * valid in both the original array and the copy, the two arrays will
2425      * contain identical values.  For any indices that are valid in the
2426      * copy but not the original, the copy will contain <tt>false</tt>.
2427      * Such indices will exist if and only if the specified length
2428      * is greater than that of the original array.
2429      *
2430      * @param original the array to be copied
2431      * @param newLength the length of the copy to be returned
2432      * @return a copy of the original array, truncated or padded with false elements
2433      *     to obtain the specified length
2434      * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2435      * @throws NullPointerException if <tt>original</tt> is null
2436      * @since 1.6
2437      */
2438     public static boolean[] copyOf(boolean[] original, int newLength) {
2439         boolean[] copy = new boolean[newLength];
2440         System.arraycopy(original, 0, copy, 0,
2441                          Math.min(original.length, newLength));
2442         return copy;
2443     }
2444 
2445     /**
2446      * Copies the specified range of the specified array into a new array.
2447      * The initial index of the range (<tt>from</tt>) must lie between zero
2448      * and <tt>original.length</tt>, inclusive.  The value at
2449      * <tt>original[from]</tt> is placed into the initial element of the copy
2450      * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2451      * Values from subsequent elements in the original array are placed into
2452      * subsequent elements in the copy.  The final index of the range
2453      * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2454      * may be greater than <tt>original.length</tt>, in which case
2455      * <tt>null</tt> is placed in all elements of the copy whose index is
2456      * greater than or equal to <tt>original.length - from</tt>.  The length
2457      * of the returned array will be <tt>to - from</tt>.
2458      * <p>
2459      * The resulting array is of exactly the same class as the original array.
2460      *
2461      * @param original the array from which a range is to be copied
2462      * @param from the initial index of the range to be copied, inclusive
2463      * @param to the final index of the range to be copied, exclusive.
2464      *     (This index may lie outside the array.)
2465      * @return a new array containing the specified range from the original array,
2466      *     truncated or padded with nulls to obtain the required length
2467      * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2468      *     or {@code from > original.length}
2469      * @throws IllegalArgumentException if <tt>from &gt; to</tt>
2470      * @throws NullPointerException if <tt>original</tt> is null
2471      * @since 1.6
2472      */
2473     public static <T> T[] copyOfRange(T[] original, int from, int to) {
2474         return copyOfRange(original, from, to, (Class<T[]>) original.getClass());
2475     }
2476 
2477     /**
2478      * Copies the specified range of the specified array into a new array.
2479      * The initial index of the range (<tt>from</tt>) must lie between zero
2480      * and <tt>original.length</tt>, inclusive.  The value at
2481      * <tt>original[from]</tt> is placed into the initial element of the copy
2482      * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2483      * Values from subsequent elements in the original array are placed into
2484      * subsequent elements in the copy.  The final index of the range
2485      * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2486      * may be greater than <tt>original.length</tt>, in which case
2487      * <tt>null</tt> is placed in all elements of the copy whose index is
2488      * greater than or equal to <tt>original.length - from</tt>.  The length
2489      * of the returned array will be <tt>to - from</tt>.
2490      * The resulting array is of the class <tt>newType</tt>.
2491      *
2492      * @param original the array from which a range is to be copied
2493      * @param from the initial index of the range to be copied, inclusive
2494      * @param to the final index of the range to be copied, exclusive.
2495      *     (This index may lie outside the array.)
2496      * @param newType the class of the copy to be returned
2497      * @return a new array containing the specified range from the original array,
2498      *     truncated or padded with nulls to obtain the required length
2499      * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2500      *     or {@code from > original.length}
2501      * @throws IllegalArgumentException if <tt>from &gt; to</tt>
2502      * @throws NullPointerException if <tt>original</tt> is null
2503      * @throws ArrayStoreException if an element copied from
2504      *     <tt>original</tt> is not of a runtime type that can be stored in
2505      *     an array of class <tt>newType</tt>.
2506      * @since 1.6
2507      */
2508     public static <T,U> T[] copyOfRange(U[] original, int from, int to, Class<? extends T[]> newType) {
2509         int newLength = to - from;
2510         if (newLength < 0)
2511             throw new IllegalArgumentException(from + " > " + to);
2512         T[] copy = ((Object)newType == (Object)Object[].class)
2513             ? (T[]) new Object[newLength]
2514             : (T[]) Array.newInstance(newType.getComponentType(), newLength);
2515         System.arraycopy(original, from, copy, 0,
2516                          Math.min(original.length - from, newLength));
2517         return copy;
2518     }
2519 
2520     /**
2521      * Copies the specified range of the specified array into a new array.
2522      * The initial index of the range (<tt>from</tt>) must lie between zero
2523      * and <tt>original.length</tt>, inclusive.  The value at
2524      * <tt>original[from]</tt> is placed into the initial element of the copy
2525      * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2526      * Values from subsequent elements in the original array are placed into
2527      * subsequent elements in the copy.  The final index of the range
2528      * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2529      * may be greater than <tt>original.length</tt>, in which case
2530      * <tt>(byte)0</tt> is placed in all elements of the copy whose index is
2531      * greater than or equal to <tt>original.length - from</tt>.  The length
2532      * of the returned array will be <tt>to - from</tt>.
2533      *
2534      * @param original the array from which a range is to be copied
2535      * @param from the initial index of the range to be copied, inclusive
2536      * @param to the final index of the range to be copied, exclusive.
2537      *     (This index may lie outside the array.)
2538      * @return a new array containing the specified range from the original array,
2539      *     truncated or padded with zeros to obtain the required length
2540      * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2541      *     or {@code from > original.length}
2542      * @throws IllegalArgumentException if <tt>from &gt; to</tt>
2543      * @throws NullPointerException if <tt>original</tt> is null
2544      * @since 1.6
2545      */
2546     public static byte[] copyOfRange(byte[] original, int from, int to) {
2547         int newLength = to - from;
2548         if (newLength < 0)
2549             throw new IllegalArgumentException(from + " > " + to);
2550         byte[] copy = new byte[newLength];
2551         System.arraycopy(original, from, copy, 0,
2552                          Math.min(original.length - from, newLength));
2553         return copy;
2554     }
2555 
2556     /**
2557      * Copies the specified range of the specified array into a new array.
2558      * The initial index of the range (<tt>from</tt>) must lie between zero
2559      * and <tt>original.length</tt>, inclusive.  The value at
2560      * <tt>original[from]</tt> is placed into the initial element of the copy
2561      * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2562      * Values from subsequent elements in the original array are placed into
2563      * subsequent elements in the copy.  The final index of the range
2564      * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2565      * may be greater than <tt>original.length</tt>, in which case
2566      * <tt>(short)0</tt> is placed in all elements of the copy whose index is
2567      * greater than or equal to <tt>original.length - from</tt>.  The length
2568      * of the returned array will be <tt>to - from</tt>.
2569      *
2570      * @param original the array from which a range is to be copied
2571      * @param from the initial index of the range to be copied, inclusive
2572      * @param to the final index of the range to be copied, exclusive.
2573      *     (This index may lie outside the array.)
2574      * @return a new array containing the specified range from the original array,
2575      *     truncated or padded with zeros to obtain the required length
2576      * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2577      *     or {@code from > original.length}
2578      * @throws IllegalArgumentException if <tt>from &gt; to</tt>
2579      * @throws NullPointerException if <tt>original</tt> is null
2580      * @since 1.6
2581      */
2582     public static short[] copyOfRange(short[] original, int from, int to) {
2583         int newLength = to - from;
2584         if (newLength < 0)
2585             throw new IllegalArgumentException(from + " > " + to);
2586         short[] copy = new short[newLength];
2587         System.arraycopy(original, from, copy, 0,
2588                          Math.min(original.length - from, newLength));
2589         return copy;
2590     }
2591 
2592     /**
2593      * Copies the specified range of the specified array into a new array.
2594      * The initial index of the range (<tt>from</tt>) must lie between zero
2595      * and <tt>original.length</tt>, inclusive.  The value at
2596      * <tt>original[from]</tt> is placed into the initial element of the copy
2597      * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2598      * Values from subsequent elements in the original array are placed into
2599      * subsequent elements in the copy.  The final index of the range
2600      * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2601      * may be greater than <tt>original.length</tt>, in which case
2602      * <tt>0</tt> is placed in all elements of the copy whose index is
2603      * greater than or equal to <tt>original.length - from</tt>.  The length
2604      * of the returned array will be <tt>to - from</tt>.
2605      *
2606      * @param original the array from which a range is to be copied
2607      * @param from the initial index of the range to be copied, inclusive
2608      * @param to the final index of the range to be copied, exclusive.
2609      *     (This index may lie outside the array.)
2610      * @return a new array containing the specified range from the original array,
2611      *     truncated or padded with zeros to obtain the required length
2612      * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2613      *     or {@code from > original.length}
2614      * @throws IllegalArgumentException if <tt>from &gt; to</tt>
2615      * @throws NullPointerException if <tt>original</tt> is null
2616      * @since 1.6
2617      */
2618     public static int[] copyOfRange(int[] original, int from, int to) {
2619         int newLength = to - from;
2620         if (newLength < 0)
2621             throw new IllegalArgumentException(from + " > " + to);
2622         int[] copy = new int[newLength];
2623         System.arraycopy(original, from, copy, 0,
2624                          Math.min(original.length - from, newLength));
2625         return copy;
2626     }
2627 
2628     /**
2629      * Copies the specified range of the specified array into a new array.
2630      * The initial index of the range (<tt>from</tt>) must lie between zero
2631      * and <tt>original.length</tt>, inclusive.  The value at
2632      * <tt>original[from]</tt> is placed into the initial element of the copy
2633      * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2634      * Values from subsequent elements in the original array are placed into
2635      * subsequent elements in the copy.  The final index of the range
2636      * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2637      * may be greater than <tt>original.length</tt>, in which case
2638      * <tt>0L</tt> is placed in all elements of the copy whose index is
2639      * greater than or equal to <tt>original.length - from</tt>.  The length
2640      * of the returned array will be <tt>to - from</tt>.
2641      *
2642      * @param original the array from which a range is to be copied
2643      * @param from the initial index of the range to be copied, inclusive
2644      * @param to the final index of the range to be copied, exclusive.
2645      *     (This index may lie outside the array.)
2646      * @return a new array containing the specified range from the original array,
2647      *     truncated or padded with zeros to obtain the required length
2648      * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2649      *     or {@code from > original.length}
2650      * @throws IllegalArgumentException if <tt>from &gt; to</tt>
2651      * @throws NullPointerException if <tt>original</tt> is null
2652      * @since 1.6
2653      */
2654     public static long[] copyOfRange(long[] original, int from, int to) {
2655         int newLength = to - from;
2656         if (newLength < 0)
2657             throw new IllegalArgumentException(from + " > " + to);
2658         long[] copy = new long[newLength];
2659         System.arraycopy(original, from, copy, 0,
2660                          Math.min(original.length - from, newLength));
2661         return copy;
2662     }
2663 
2664     /**
2665      * Copies the specified range of the specified array into a new array.
2666      * The initial index of the range (<tt>from</tt>) must lie between zero
2667      * and <tt>original.length</tt>, inclusive.  The value at
2668      * <tt>original[from]</tt> is placed into the initial element of the copy
2669      * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2670      * Values from subsequent elements in the original array are placed into
2671      * subsequent elements in the copy.  The final index of the range
2672      * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2673      * may be greater than <tt>original.length</tt>, in which case
2674      * <tt>'\\u000'</tt> is placed in all elements of the copy whose index is
2675      * greater than or equal to <tt>original.length - from</tt>.  The length
2676      * of the returned array will be <tt>to - from</tt>.
2677      *
2678      * @param original the array from which a range is to be copied
2679      * @param from the initial index of the range to be copied, inclusive
2680      * @param to the final index of the range to be copied, exclusive.
2681      *     (This index may lie outside the array.)
2682      * @return a new array containing the specified range from the original array,
2683      *     truncated or padded with null characters to obtain the required length
2684      * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2685      *     or {@code from > original.length}
2686      * @throws IllegalArgumentException if <tt>from &gt; to</tt>
2687      * @throws NullPointerException if <tt>original</tt> is null
2688      * @since 1.6
2689      */
2690     public static char[] copyOfRange(char[] original, int from, int to) {
2691         int newLength = to - from;
2692         if (newLength < 0)
2693             throw new IllegalArgumentException(from + " > " + to);
2694         char[] copy = new char[newLength];
2695         System.arraycopy(original, from, copy, 0,
2696                          Math.min(original.length - from, newLength));
2697         return copy;
2698     }
2699 
2700     /**
2701      * Copies the specified range of the specified array into a new array.
2702      * The initial index of the range (<tt>from</tt>) must lie between zero
2703      * and <tt>original.length</tt>, inclusive.  The value at
2704      * <tt>original[from]</tt> is placed into the initial element of the copy
2705      * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2706      * Values from subsequent elements in the original array are placed into
2707      * subsequent elements in the copy.  The final index of the range
2708      * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2709      * may be greater than <tt>original.length</tt>, in which case
2710      * <tt>0f</tt> is placed in all elements of the copy whose index is
2711      * greater than or equal to <tt>original.length - from</tt>.  The length
2712      * of the returned array will be <tt>to - from</tt>.
2713      *
2714      * @param original the array from which a range is to be copied
2715      * @param from the initial index of the range to be copied, inclusive
2716      * @param to the final index of the range to be copied, exclusive.
2717      *     (This index may lie outside the array.)
2718      * @return a new array containing the specified range from the original array,
2719      *     truncated or padded with zeros to obtain the required length
2720      * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2721      *     or {@code from > original.length}
2722      * @throws IllegalArgumentException if <tt>from &gt; to</tt>
2723      * @throws NullPointerException if <tt>original</tt> is null
2724      * @since 1.6
2725      */
2726     public static float[] copyOfRange(float[] original, int from, int to) {
2727         int newLength = to - from;
2728         if (newLength < 0)
2729             throw new IllegalArgumentException(from + " > " + to);
2730         float[] copy = new float[newLength];
2731         System.arraycopy(original, from, copy, 0,
2732                          Math.min(original.length - from, newLength));
2733         return copy;
2734     }
2735 
2736     /**
2737      * Copies the specified range of the specified array into a new array.
2738      * The initial index of the range (<tt>from</tt>) must lie between zero
2739      * and <tt>original.length</tt>, inclusive.  The value at
2740      * <tt>original[from]</tt> is placed into the initial element of the copy
2741      * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2742      * Values from subsequent elements in the original array are placed into
2743      * subsequent elements in the copy.  The final index of the range
2744      * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2745      * may be greater than <tt>original.length</tt>, in which case
2746      * <tt>0d</tt> is placed in all elements of the copy whose index is
2747      * greater than or equal to <tt>original.length - from</tt>.  The length
2748      * of the returned array will be <tt>to - from</tt>.
2749      *
2750      * @param original the array from which a range is to be copied
2751      * @param from the initial index of the range to be copied, inclusive
2752      * @param to the final index of the range to be copied, exclusive.
2753      *     (This index may lie outside the array.)
2754      * @return a new array containing the specified range from the original array,
2755      *     truncated or padded with zeros to obtain the required length
2756      * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2757      *     or {@code from > original.length}
2758      * @throws IllegalArgumentException if <tt>from &gt; to</tt>
2759      * @throws NullPointerException if <tt>original</tt> is null
2760      * @since 1.6
2761      */
2762     public static double[] copyOfRange(double[] original, int from, int to) {
2763         int newLength = to - from;
2764         if (newLength < 0)
2765             throw new IllegalArgumentException(from + " > " + to);
2766         double[] copy = new double[newLength];
2767         System.arraycopy(original, from, copy, 0,
2768                          Math.min(original.length - from, newLength));
2769         return copy;
2770     }
2771 
2772     /**
2773      * Copies the specified range of the specified array into a new array.
2774      * The initial index of the range (<tt>from</tt>) must lie between zero
2775      * and <tt>original.length</tt>, inclusive.  The value at
2776      * <tt>original[from]</tt> is placed into the initial element of the copy
2777      * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2778      * Values from subsequent elements in the original array are placed into
2779      * subsequent elements in the copy.  The final index of the range
2780      * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2781      * may be greater than <tt>original.length</tt>, in which case
2782      * <tt>false</tt> is placed in all elements of the copy whose index is
2783      * greater than or equal to <tt>original.length - from</tt>.  The length
2784      * of the returned array will be <tt>to - from</tt>.
2785      *
2786      * @param original the array from which a range is to be copied
2787      * @param from the initial index of the range to be copied, inclusive
2788      * @param to the final index of the range to be copied, exclusive.
2789      *     (This index may lie outside the array.)
2790      * @return a new array containing the specified range from the original array,
2791      *     truncated or padded with false elements to obtain the required length
2792      * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2793      *     or {@code from > original.length}
2794      * @throws IllegalArgumentException if <tt>from &gt; to</tt>
2795      * @throws NullPointerException if <tt>original</tt> is null
2796      * @since 1.6
2797      */
2798     public static boolean[] copyOfRange(boolean[] original, int from, int to) {
2799         int newLength = to - from;
2800         if (newLength < 0)
2801             throw new IllegalArgumentException(from + " > " + to);
2802         boolean[] copy = new boolean[newLength];
2803         System.arraycopy(original, from, copy, 0,
2804                          Math.min(original.length - from, newLength));
2805         return copy;
2806     }
2807 
2808     // Misc
2809 
2810     /**
2811      * Returns a fixed-size list backed by the specified array.  (Changes to
2812      * the returned list "write through" to the array.)  This method acts
2813      * as bridge between array-based and collection-based APIs, in
2814      * combination with {@link Collection#toArray}.  The returned list is
2815      * serializable and implements {@link RandomAccess}.
2816      *
2817      * <p>This method also provides a convenient way to create a fixed-size
2818      * list initialized to contain several elements:
2819      * <pre>
2820      *     List&lt;String&gt; stooges = Arrays.asList("Larry", "Moe", "Curly");
2821      * </pre>
2822      *
2823      * @param a the array by which the list will be backed
2824      * @return a list view of the specified array
2825      */
2826     public static <T> List<T> asList(T... a) {
2827         return new ArrayList<T>(a);
2828     }
2829 
2830     /**
2831      * @serial include
2832      */
2833     private static class ArrayList<E> extends AbstractList<E>
2834         implements RandomAccess, java.io.Serializable
2835     {
2836         private static final long serialVersionUID = -2764017481108945198L;
2837         private final E[] a;
2838 
2839         ArrayList(E[] array) {
2840             if (array==null)
2841                 throw new NullPointerException();
2842             a = array;
2843         }
2844 
2845         public int size() {
2846             return a.length;
2847         }
2848 
2849         public Object[] toArray() {
2850             return a.clone();
2851         }
2852 
2853         public <T> T[] toArray(T[] a) {
2854             int size = size();
2855             if (a.length < size)
2856                 return Arrays.copyOf(this.a, size,
2857                                      (Class<? extends T[]>) a.getClass());
2858             System.arraycopy(this.a, 0, a, 0, size);
2859             if (a.length > size)
2860                 a[size] = null;
2861             return a;
2862         }
2863 
2864         public E get(int index) {
2865             return a[index];
2866         }
2867 
2868         public E set(int index, E element) {
2869             E oldValue = a[index];
2870             a[index] = element;
2871             return oldValue;
2872         }
2873 
2874         public int indexOf(Object o) {
2875             if (o==null) {
2876                 for (int i=0; i<a.length; i++)
2877                     if (a[i]==null)
2878                         return i;
2879             } else {
2880                 for (int i=0; i<a.length; i++)
2881                     if (o.equals(a[i]))
2882                         return i;
2883             }
2884             return -1;
2885         }
2886 
2887         public boolean contains(Object o) {
2888             return indexOf(o) != -1;
2889         }
2890     }
2891 
2892     /**
2893      * Returns a hash code based on the contents of the specified array.
2894      * For any two <tt>long</tt> arrays <tt>a</tt> and <tt>b</tt>
2895      * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
2896      * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
2897      *
2898      * <p>The value returned by this method is the same value that would be
2899      * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
2900      * method on a {@link List} containing a sequence of {@link Long}
2901      * instances representing the elements of <tt>a</tt> in the same order.
2902      * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
2903      *
2904      * @param a the array whose hash value to compute
2905      * @return a content-based hash code for <tt>a</tt>
2906      * @since 1.5
2907      */
2908     public static int hashCode(long a[]) {
2909         if (a == null)
2910             return 0;
2911 
2912         int result = 1;
2913         for (long element : a) {
2914             int elementHash = (int)(element ^ (element >>> 32));
2915             result = 31 * result + elementHash;
2916         }
2917 
2918         return result;
2919     }
2920 
2921     /**
2922      * Returns a hash code based on the contents of the specified array.
2923      * For any two non-null <tt>int</tt> arrays <tt>a</tt> and <tt>b</tt>
2924      * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
2925      * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
2926      *
2927      * <p>The value returned by this method is the same value that would be
2928      * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
2929      * method on a {@link List} containing a sequence of {@link Integer}
2930      * instances representing the elements of <tt>a</tt> in the same order.
2931      * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
2932      *
2933      * @param a the array whose hash value to compute
2934      * @return a content-based hash code for <tt>a</tt>
2935      * @since 1.5
2936      */
2937     public static int hashCode(int a[]) {
2938         if (a == null)
2939             return 0;
2940 
2941         int result = 1;
2942         for (int element : a)
2943             result = 31 * result + element;
2944 
2945         return result;
2946     }
2947 
2948     /**
2949      * Returns a hash code based on the contents of the specified array.
2950      * For any two <tt>short</tt> arrays <tt>a</tt> and <tt>b</tt>
2951      * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
2952      * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
2953      *
2954      * <p>The value returned by this method is the same value that would be
2955      * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
2956      * method on a {@link List} containing a sequence of {@link Short}
2957      * instances representing the elements of <tt>a</tt> in the same order.
2958      * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
2959      *
2960      * @param a the array whose hash value to compute
2961      * @return a content-based hash code for <tt>a</tt>
2962      * @since 1.5
2963      */
2964     public static int hashCode(short a[]) {
2965         if (a == null)
2966             return 0;
2967 
2968         int result = 1;
2969         for (short element : a)
2970             result = 31 * result + element;
2971 
2972         return result;
2973     }
2974 
2975     /**
2976      * Returns a hash code based on the contents of the specified array.
2977      * For any two <tt>char</tt> arrays <tt>a</tt> and <tt>b</tt>
2978      * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
2979      * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
2980      *
2981      * <p>The value returned by this method is the same value that would be
2982      * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
2983      * method on a {@link List} containing a sequence of {@link Character}
2984      * instances representing the elements of <tt>a</tt> in the same order.
2985      * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
2986      *
2987      * @param a the array whose hash value to compute
2988      * @return a content-based hash code for <tt>a</tt>
2989      * @since 1.5
2990      */
2991     public static int hashCode(char a[]) {
2992         if (a == null)
2993             return 0;
2994 
2995         int result = 1;
2996         for (char element : a)
2997             result = 31 * result + element;
2998 
2999         return result;
3000     }
3001 
3002     /**
3003      * Returns a hash code based on the contents of the specified array.
3004      * For any two <tt>byte</tt> arrays <tt>a</tt> and <tt>b</tt>
3005      * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3006      * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3007      *
3008      * <p>The value returned by this method is the same value that would be
3009      * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3010      * method on a {@link List} containing a sequence of {@link Byte}
3011      * instances representing the elements of <tt>a</tt> in the same order.
3012      * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3013      *
3014      * @param a the array whose hash value to compute
3015      * @return a content-based hash code for <tt>a</tt>
3016      * @since 1.5
3017      */
3018     public static int hashCode(byte a[]) {
3019         if (a == null)
3020             return 0;
3021 
3022         int result = 1;
3023         for (byte element : a)
3024             result = 31 * result + element;
3025 
3026         return result;
3027     }
3028 
3029     /**
3030      * Returns a hash code based on the contents of the specified array.
3031      * For any two <tt>boolean</tt> arrays <tt>a</tt> and <tt>b</tt>
3032      * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3033      * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3034      *
3035      * <p>The value returned by this method is the same value that would be
3036      * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3037      * method on a {@link List} containing a sequence of {@link Boolean}
3038      * instances representing the elements of <tt>a</tt> in the same order.
3039      * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3040      *
3041      * @param a the array whose hash value to compute
3042      * @return a content-based hash code for <tt>a</tt>
3043      * @since 1.5
3044      */
3045     public static int hashCode(boolean a[]) {
3046         if (a == null)
3047             return 0;
3048 
3049         int result = 1;
3050         for (boolean element : a)
3051             result = 31 * result + (element ? 1231 : 1237);
3052 
3053         return result;
3054     }
3055 
3056     /**
3057      * Returns a hash code based on the contents of the specified array.
3058      * For any two <tt>float</tt> arrays <tt>a</tt> and <tt>b</tt>
3059      * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3060      * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3061      *
3062      * <p>The value returned by this method is the same value that would be
3063      * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3064      * method on a {@link List} containing a sequence of {@link Float}
3065      * instances representing the elements of <tt>a</tt> in the same order.
3066      * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3067      *
3068      * @param a the array whose hash value to compute
3069      * @return a content-based hash code for <tt>a</tt>
3070      * @since 1.5
3071      */
3072     public static int hashCode(float a[]) {
3073         if (a == null)
3074             return 0;
3075 
3076         int result = 1;
3077         for (float element : a)
3078             result = 31 * result + Float.floatToIntBits(element);
3079 
3080         return result;
3081     }
3082 
3083     /**
3084      * Returns a hash code based on the contents of the specified array.
3085      * For any two <tt>double</tt> arrays <tt>a</tt> and <tt>b</tt>
3086      * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3087      * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3088      *
3089      * <p>The value returned by this method is the same value that would be
3090      * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3091      * method on a {@link List} containing a sequence of {@link Double}
3092      * instances representing the elements of <tt>a</tt> in the same order.
3093      * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3094      *
3095      * @param a the array whose hash value to compute
3096      * @return a content-based hash code for <tt>a</tt>
3097      * @since 1.5
3098      */
3099     public static int hashCode(double a[]) {
3100         if (a == null)
3101             return 0;
3102 
3103         int result = 1;
3104         for (double element : a) {
3105             long bits = Double.doubleToLongBits(element);
3106             result = 31 * result + (int)(bits ^ (bits >>> 32));
3107         }
3108         return result;
3109     }
3110 
3111     /**
3112      * Returns a hash code based on the contents of the specified array.  If
3113      * the array contains other arrays as elements, the hash code is based on
3114      * their identities rather than their contents.  It is therefore
3115      * acceptable to invoke this method on an array that contains itself as an
3116      * element,  either directly or indirectly through one or more levels of
3117      * arrays.
3118      *
3119      * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
3120      * <tt>Arrays.equals(a, b)</tt>, it is also the case that
3121      * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3122      *
3123      * <p>The value returned by this method is equal to the value that would
3124      * be returned by <tt>Arrays.asList(a).hashCode()</tt>, unless <tt>a</tt>
3125      * is <tt>null</tt>, in which case <tt>0</tt> is returned.
3126      *
3127      * @param a the array whose content-based hash code to compute
3128      * @return a content-based hash code for <tt>a</tt>
3129      * @see #deepHashCode(Object[])
3130      * @since 1.5
3131      */
3132     public static int hashCode(Object a[]) {
3133         if (a == null)
3134             return 0;
3135 
3136         int result = 1;
3137 
3138         for (Object element : a)
3139             result = 31 * result + (element == null ? 0 : element.hashCode());
3140 
3141         return result;
3142     }
3143 
3144     /**
3145      * Returns a hash code based on the "deep contents" of the specified
3146      * array.  If the array contains other arrays as elements, the
3147      * hash code is based on their contents and so on, ad infinitum.
3148      * It is therefore unacceptable to invoke this method on an array that
3149      * contains itself as an element, either directly or indirectly through
3150      * one or more levels of arrays.  The behavior of such an invocation is
3151      * undefined.
3152      *
3153      * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
3154      * <tt>Arrays.deepEquals(a, b)</tt>, it is also the case that
3155      * <tt>Arrays.deepHashCode(a) == Arrays.deepHashCode(b)</tt>.
3156      *
3157      * <p>The computation of the value returned by this method is similar to
3158      * that of the value returned by {@link List#hashCode()} on a list
3159      * containing the same elements as <tt>a</tt> in the same order, with one
3160      * difference: If an element <tt>e</tt> of <tt>a</tt> is itself an array,
3161      * its hash code is computed not by calling <tt>e.hashCode()</tt>, but as
3162      * by calling the appropriate overloading of <tt>Arrays.hashCode(e)</tt>
3163      * if <tt>e</tt> is an array of a primitive type, or as by calling
3164      * <tt>Arrays.deepHashCode(e)</tt> recursively if <tt>e</tt> is an array
3165      * of a reference type.  If <tt>a</tt> is <tt>null</tt>, this method
3166      * returns 0.
3167      *
3168      * @param a the array whose deep-content-based hash code to compute
3169      * @return a deep-content-based hash code for <tt>a</tt>
3170      * @see #hashCode(Object[])
3171      * @since 1.5
3172      */
3173     public static int deepHashCode(Object a[]) {
3174         if (a == null)
3175             return 0;
3176 
3177         int result = 1;
3178 
3179         for (Object element : a) {
3180             int elementHash = 0;
3181             if (element instanceof Object[])
3182                 elementHash = deepHashCode((Object[]) element);
3183             else if (element instanceof byte[])
3184                 elementHash = hashCode((byte[]) element);
3185             else if (element instanceof short[])
3186                 elementHash = hashCode((short[]) element);
3187             else if (element instanceof int[])
3188                 elementHash = hashCode((int[]) element);
3189             else if (element instanceof long[])
3190                 elementHash = hashCode((long[]) element);
3191             else if (element instanceof char[])
3192                 elementHash = hashCode((char[]) element);
3193             else if (element instanceof float[])
3194                 elementHash = hashCode((float[]) element);
3195             else if (element instanceof double[])
3196                 elementHash = hashCode((double[]) element);
3197             else if (element instanceof boolean[])
3198                 elementHash = hashCode((boolean[]) element);
3199             else if (element != null)
3200                 elementHash = element.hashCode();
3201 
3202             result = 31 * result + elementHash;
3203         }
3204 
3205         return result;
3206     }
3207 
3208     /**
3209      * Returns <tt>true</tt> if the two specified arrays are <i>deeply
3210      * equal</i> to one another.  Unlike the {@link #equals(Object[],Object[])}
3211      * method, this method is appropriate for use with nested arrays of
3212      * arbitrary depth.
3213      *
3214      * <p>Two array references are considered deeply equal if both
3215      * are <tt>null</tt>, or if they refer to arrays that contain the same
3216      * number of elements and all corresponding pairs of elements in the two
3217      * arrays are deeply equal.
3218      *
3219      * <p>Two possibly <tt>null</tt> elements <tt>e1</tt> and <tt>e2</tt> are
3220      * deeply equal if any of the following conditions hold:
3221      * <ul>
3222      *    <li> <tt>e1</tt> and <tt>e2</tt> are both arrays of object reference
3223      *         types, and <tt>Arrays.deepEquals(e1, e2) would return true</tt>
3224      *    <li> <tt>e1</tt> and <tt>e2</tt> are arrays of the same primitive
3225      *         type, and the appropriate overloading of
3226      *         <tt>Arrays.equals(e1, e2)</tt> would return true.
3227      *    <li> <tt>e1 == e2</tt>
3228      *    <li> <tt>e1.equals(e2)</tt> would return true.
3229      * </ul>
3230      * Note that this definition permits <tt>null</tt> elements at any depth.
3231      *
3232      * <p>If either of the specified arrays contain themselves as elements
3233      * either directly or indirectly through one or more levels of arrays,
3234      * the behavior of this method is undefined.
3235      *
3236      * @param a1 one array to be tested for equality
3237      * @param a2 the other array to be tested for equality
3238      * @return <tt>true</tt> if the two arrays are equal
3239      * @see #equals(Object[],Object[])
3240      * @see Objects#deepEquals(Object, Object)
3241      * @since 1.5
3242      */
3243     public static boolean deepEquals(Object[] a1, Object[] a2) {
3244         if (a1 == a2)
3245             return true;
3246         if (a1 == null || a2==null)
3247             return false;
3248         int length = a1.length;
3249         if (a2.length != length)
3250             return false;
3251 
3252         for (int i = 0; i < length; i++) {
3253             Object e1 = a1[i];
3254             Object e2 = a2[i];
3255 
3256             if (e1 == e2)
3257                 continue;
3258             if (e1 == null)
3259                 return false;
3260 
3261             // Figure out whether the two elements are equal
3262             boolean eq = deepEquals0(e1, e2);
3263 
3264             if (!eq)
3265                 return false;
3266         }
3267         return true;
3268     }
3269 
3270     static boolean deepEquals0(Object e1, Object e2) {
3271         assert e1 != null;
3272         boolean eq;
3273         if (e1 instanceof Object[] && e2 instanceof Object[])
3274             eq = deepEquals ((Object[]) e1, (Object[]) e2);
3275         else if (e1 instanceof byte[] && e2 instanceof byte[])
3276             eq = equals((byte[]) e1, (byte[]) e2);
3277         else if (e1 instanceof short[] && e2 instanceof short[])
3278             eq = equals((short[]) e1, (short[]) e2);
3279         else if (e1 instanceof int[] && e2 instanceof int[])
3280             eq = equals((int[]) e1, (int[]) e2);
3281         else if (e1 instanceof long[] && e2 instanceof long[])
3282             eq = equals((long[]) e1, (long[]) e2);
3283         else if (e1 instanceof char[] && e2 instanceof char[])
3284             eq = equals((char[]) e1, (char[]) e2);
3285         else if (e1 instanceof float[] && e2 instanceof float[])
3286             eq = equals((float[]) e1, (float[]) e2);
3287         else if (e1 instanceof double[] && e2 instanceof double[])
3288             eq = equals((double[]) e1, (double[]) e2);
3289         else if (e1 instanceof boolean[] && e2 instanceof boolean[])
3290             eq = equals((boolean[]) e1, (boolean[]) e2);
3291         else
3292             eq = e1.equals(e2);
3293         return eq;
3294     }
3295 
3296     /**
3297      * Returns a string representation of the contents of the specified array.
3298      * The string representation consists of a list of the array's elements,
3299      * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
3300      * separated by the characters <tt>", "</tt> (a comma followed by a
3301      * space).  Elements are converted to strings as by
3302      * <tt>String.valueOf(long)</tt>.  Returns <tt>"null"</tt> if <tt>a</tt>
3303      * is <tt>null</tt>.
3304      *
3305      * @param a the array whose string representation to return
3306      * @return a string representation of <tt>a</tt>
3307      * @since 1.5
3308      */
3309     public static String toString(long[] a) {
3310         if (a == null)
3311             return "null";
3312         int iMax = a.length - 1;
3313         if (iMax == -1)
3314             return "[]";
3315 
3316         StringBuilder b = new StringBuilder();
3317         b.append('[');
3318         for (int i = 0; ; i++) {
3319             b.append(a[i]);
3320             if (i == iMax)
3321                 return b.append(']').toString();
3322             b.append(", ");
3323         }
3324     }
3325 
3326     /**
3327      * Returns a string representation of the contents of the specified array.
3328      * The string representation consists of a list of the array's elements,
3329      * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
3330      * separated by the characters <tt>", "</tt> (a comma followed by a
3331      * space).  Elements are converted to strings as by
3332      * <tt>String.valueOf(int)</tt>.  Returns <tt>"null"</tt> if <tt>a</tt> is
3333      * <tt>null</tt>.
3334      *
3335      * @param a the array whose string representation to return
3336      * @return a string representation of <tt>a</tt>
3337      * @since 1.5
3338      */
3339     public static String toString(int[] a) {
3340         if (a == null)
3341             return "null";
3342         int iMax = a.length - 1;
3343         if (iMax == -1)
3344             return "[]";
3345 
3346         StringBuilder b = new StringBuilder();
3347         b.append('[');
3348         for (int i = 0; ; i++) {
3349             b.append(a[i]);
3350             if (i == iMax)
3351                 return b.append(']').toString();
3352             b.append(", ");
3353         }
3354     }
3355 
3356     /**
3357      * Returns a string representation of the contents of the specified array.
3358      * The string representation consists of a list of the array's elements,
3359      * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
3360      * separated by the characters <tt>", "</tt> (a comma followed by a
3361      * space).  Elements are converted to strings as by
3362      * <tt>String.valueOf(short)</tt>.  Returns <tt>"null"</tt> if <tt>a</tt>
3363      * is <tt>null</tt>.
3364      *
3365      * @param a the array whose string representation to return
3366      * @return a string representation of <tt>a</tt>
3367      * @since 1.5
3368      */
3369     public static String toString(short[] a) {
3370         if (a == null)
3371             return "null";
3372         int iMax = a.length - 1;
3373         if (iMax == -1)
3374             return "[]";
3375 
3376         StringBuilder b = new StringBuilder();
3377         b.append('[');
3378         for (int i = 0; ; i++) {
3379             b.append(a[i]);
3380             if (i == iMax)
3381                 return b.append(']').toString();
3382             b.append(", ");
3383         }
3384     }
3385 
3386     /**
3387      * Returns a string representation of the contents of the specified array.
3388      * The string representation consists of a list of the array's elements,
3389      * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
3390      * separated by the characters <tt>", "</tt> (a comma followed by a
3391      * space).  Elements are converted to strings as by
3392      * <tt>String.valueOf(char)</tt>.  Returns <tt>"null"</tt> if <tt>a</tt>
3393      * is <tt>null</tt>.
3394      *
3395      * @param a the array whose string representation to return
3396      * @return a string representation of <tt>a</tt>
3397      * @since 1.5
3398      */
3399     public static String toString(char[] a) {
3400         if (a == null)
3401             return "null";
3402         int iMax = a.length - 1;
3403         if (iMax == -1)
3404             return "[]";
3405 
3406         StringBuilder b = new StringBuilder();
3407         b.append('[');
3408         for (int i = 0; ; i++) {
3409             b.append(a[i]);
3410             if (i == iMax)
3411                 return b.append(']').toString();
3412             b.append(", ");
3413         }
3414     }
3415 
3416     /**
3417      * Returns a string representation of the contents of the specified array.
3418      * The string representation consists of a list of the array's elements,
3419      * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements
3420      * are separated by the characters <tt>", "</tt> (a comma followed
3421      * by a space).  Elements are converted to strings as by
3422      * <tt>String.valueOf(byte)</tt>.  Returns <tt>"null"</tt> if
3423      * <tt>a</tt> is <tt>null</tt>.
3424      *
3425      * @param a the array whose string representation to return
3426      * @return a string representation of <tt>a</tt>
3427      * @since 1.5
3428      */
3429     public static String toString(byte[] a) {
3430         if (a == null)
3431             return "null";
3432         int iMax = a.length - 1;
3433         if (iMax == -1)
3434             return "[]";
3435 
3436         StringBuilder b = new StringBuilder();
3437         b.append('[');
3438         for (int i = 0; ; i++) {
3439             b.append(a[i]);
3440             if (i == iMax)
3441                 return b.append(']').toString();
3442             b.append(", ");
3443         }
3444     }
3445 
3446     /**
3447      * Returns a string representation of the contents of the specified array.
3448      * The string representation consists of a list of the array's elements,
3449      * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
3450      * separated by the characters <tt>", "</tt> (a comma followed by a
3451      * space).  Elements are converted to strings as by
3452      * <tt>String.valueOf(boolean)</tt>.  Returns <tt>"null"</tt> if
3453      * <tt>a</tt> is <tt>null</tt>.
3454      *
3455      * @param a the array whose string representation to return
3456      * @return a string representation of <tt>a</tt>
3457      * @since 1.5
3458      */
3459     public static String toString(boolean[] a) {
3460         if (a == null)
3461             return "null";
3462         int iMax = a.length - 1;
3463         if (iMax == -1)
3464             return "[]";
3465 
3466         StringBuilder b = new StringBuilder();
3467         b.append('[');
3468         for (int i = 0; ; i++) {
3469             b.append(a[i]);
3470             if (i == iMax)
3471                 return b.append(']').toString();
3472             b.append(", ");
3473         }
3474     }
3475 
3476     /**
3477      * Returns a string representation of the contents of the specified array.
3478      * The string representation consists of a list of the array's elements,
3479      * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
3480      * separated by the characters <tt>", "</tt> (a comma followed by a
3481      * space).  Elements are converted to strings as by
3482      * <tt>String.valueOf(float)</tt>.  Returns <tt>"null"</tt> if <tt>a</tt>
3483      * is <tt>null</tt>.
3484      *
3485      * @param a the array whose string representation to return
3486      * @return a string representation of <tt>a</tt>
3487      * @since 1.5
3488      */
3489     public static String toString(float[] a) {
3490         if (a == null)
3491             return "null";
3492 
3493         int iMax = a.length - 1;
3494         if (iMax == -1)
3495             return "[]";
3496 
3497         StringBuilder b = new StringBuilder();
3498         b.append('[');
3499         for (int i = 0; ; i++) {
3500             b.append(a[i]);
3501             if (i == iMax)
3502                 return b.append(']').toString();
3503             b.append(", ");
3504         }
3505     }
3506 
3507     /**
3508      * Returns a string representation of the contents of the specified array.
3509      * The string representation consists of a list of the array's elements,
3510      * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
3511      * separated by the characters <tt>", "</tt> (a comma followed by a
3512      * space).  Elements are converted to strings as by
3513      * <tt>String.valueOf(double)</tt>.  Returns <tt>"null"</tt> if <tt>a</tt>
3514      * is <tt>null</tt>.
3515      *
3516      * @param a the array whose string representation to return
3517      * @return a string representation of <tt>a</tt>
3518      * @since 1.5
3519      */
3520     public static String toString(double[] a) {
3521         if (a == null)
3522             return "null";
3523         int iMax = a.length - 1;
3524         if (iMax == -1)
3525             return "[]";
3526 
3527         StringBuilder b = new StringBuilder();
3528         b.append('[');
3529         for (int i = 0; ; i++) {
3530             b.append(a[i]);
3531             if (i == iMax)
3532                 return b.append(']').toString();
3533             b.append(", ");
3534         }
3535     }
3536 
3537     /**
3538      * Returns a string representation of the contents of the specified array.
3539      * If the array contains other arrays as elements, they are converted to
3540      * strings by the {@link Object#toString} method inherited from
3541      * <tt>Object</tt>, which describes their <i>identities</i> rather than
3542      * their contents.
3543      *
3544      * <p>The value returned by this method is equal to the value that would
3545      * be returned by <tt>Arrays.asList(a).toString()</tt>, unless <tt>a</tt>
3546      * is <tt>null</tt>, in which case <tt>"null"</tt> is returned.
3547      *
3548      * @param a the array whose string representation to return
3549      * @return a string representation of <tt>a</tt>
3550      * @see #deepToString(Object[])
3551      * @since 1.5
3552      */
3553     public static String toString(Object[] a) {
3554         if (a == null)
3555             return "null";
3556 
3557         int iMax = a.length - 1;
3558         if (iMax == -1)
3559             return "[]";
3560 
3561         StringBuilder b = new StringBuilder();
3562         b.append('[');
3563         for (int i = 0; ; i++) {
3564             b.append(String.valueOf(a[i]));
3565             if (i == iMax)
3566                 return b.append(']').toString();
3567             b.append(", ");
3568         }
3569     }
3570 
3571     /**
3572      * Returns a string representation of the "deep contents" of the specified
3573      * array.  If the array contains other arrays as elements, the string
3574      * representation contains their contents and so on.  This method is
3575      * designed for converting multidimensional arrays to strings.
3576      *
3577      * <p>The string representation consists of a list of the array's
3578      * elements, enclosed in square brackets (<tt>"[]"</tt>).  Adjacent
3579      * elements are separated by the characters <tt>", "</tt> (a comma
3580      * followed by a space).  Elements are converted to strings as by
3581      * <tt>String.valueOf(Object)</tt>, unless they are themselves
3582      * arrays.
3583      *
3584      * <p>If an element <tt>e</tt> is an array of a primitive type, it is
3585      * converted to a string as by invoking the appropriate overloading of
3586      * <tt>Arrays.toString(e)</tt>.  If an element <tt>e</tt> is an array of a
3587      * reference type, it is converted to a string as by invoking
3588      * this method recursively.
3589      *
3590      * <p>To avoid infinite recursion, if the specified array contains itself
3591      * as an element, or contains an indirect reference to itself through one
3592      * or more levels of arrays, the self-reference is converted to the string
3593      * <tt>"[...]"</tt>.  For example, an array containing only a reference
3594      * to itself would be rendered as <tt>"[[...]]"</tt>.
3595      *
3596      * <p>This method returns <tt>"null"</tt> if the specified array
3597      * is <tt>null</tt>.
3598      *
3599      * @param a the array whose string representation to return
3600      * @return a string representation of <tt>a</tt>
3601      * @see #toString(Object[])
3602      * @since 1.5
3603      */
3604     public static String deepToString(Object[] a) {
3605         if (a == null)
3606             return "null";
3607 
3608         int bufLen = 20 * a.length;
3609         if (a.length != 0 && bufLen <= 0)
3610             bufLen = Integer.MAX_VALUE;
3611         StringBuilder buf = new StringBuilder(bufLen);
3612         deepToString(a, buf, new HashSet<Object[]>());
3613         return buf.toString();
3614     }
3615 
3616     private static void deepToString(Object[] a, StringBuilder buf,
3617                                      Set<Object[]> dejaVu) {
3618         if (a == null) {
3619             buf.append("null");
3620             return;
3621         }
3622         int iMax = a.length - 1;
3623         if (iMax == -1) {
3624             buf.append("[]");
3625             return;
3626         }
3627 
3628         dejaVu.add(a);
3629         buf.append('[');
3630         for (int i = 0; ; i++) {
3631 
3632             Object element = a[i];
3633             if (element == null) {
3634                 buf.append("null");
3635             } else {
3636                 Class eClass = element.getClass();
3637 
3638                 if (eClass.isArray()) {
3639                     if (eClass == byte[].class)
3640                         buf.append(toString((byte[]) element));
3641                     else if (eClass == short[].class)
3642                         buf.append(toString((short[]) element));
3643                     else if (eClass == int[].class)
3644                         buf.append(toString((int[]) element));
3645                     else if (eClass == long[].class)
3646                         buf.append(toString((long[]) element));
3647                     else if (eClass == char[].class)
3648                         buf.append(toString((char[]) element));
3649                     else if (eClass == float[].class)
3650                         buf.append(toString((float[]) element));
3651                     else if (eClass == double[].class)
3652                         buf.append(toString((double[]) element));
3653                     else if (eClass == boolean[].class)
3654                         buf.append(toString((boolean[]) element));
3655                     else { // element is an array of object references
3656                         if (dejaVu.contains(element))
3657                             buf.append("[...]");
3658                         else
3659                             deepToString((Object[])element, buf, dejaVu);
3660                     }
3661                 } else {  // element is non-null and not an array
3662                     buf.append(element.toString());
3663                 }
3664             }
3665             if (i == iMax)
3666                 break;
3667             buf.append(", ");
3668         }
3669         buf.append(']');
3670         dejaVu.remove(a);
3671     }
3672 }