Save This Page
Home » openjdk-7 » java » util » [javadoc | source]
    1   /*
    2    * Copyright (c) 1997, 2011, 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       @SafeVarargs
 2827       public static <T> List<T> asList(T... a) {
 2828           return new ArrayList<>(a);
 2829       }
 2830   
 2831       /**
 2832        * @serial include
 2833        */
 2834       private static class ArrayList<E> extends AbstractList<E>
 2835           implements RandomAccess, java.io.Serializable
 2836       {
 2837           private static final long serialVersionUID = -2764017481108945198L;
 2838           private final E[] a;
 2839   
 2840           ArrayList(E[] array) {
 2841               if (array==null)
 2842                   throw new NullPointerException();
 2843               a = array;
 2844           }
 2845   
 2846           public int size() {
 2847               return a.length;
 2848           }
 2849   
 2850           public Object[] toArray() {
 2851               return a.clone();
 2852           }
 2853   
 2854           public <T> T[] toArray(T[] a) {
 2855               int size = size();
 2856               if (a.length < size)
 2857                   return Arrays.copyOf(this.a, size,
 2858                                        (Class<? extends T[]>) a.getClass());
 2859               System.arraycopy(this.a, 0, a, 0, size);
 2860               if (a.length > size)
 2861                   a[size] = null;
 2862               return a;
 2863           }
 2864   
 2865           public E get(int index) {
 2866               return a[index];
 2867           }
 2868   
 2869           public E set(int index, E element) {
 2870               E oldValue = a[index];
 2871               a[index] = element;
 2872               return oldValue;
 2873           }
 2874   
 2875           public int indexOf(Object o) {
 2876               if (o==null) {
 2877                   for (int i=0; i<a.length; i++)
 2878                       if (a[i]==null)
 2879                           return i;
 2880               } else {
 2881                   for (int i=0; i<a.length; i++)
 2882                       if (o.equals(a[i]))
 2883                           return i;
 2884               }
 2885               return -1;
 2886           }
 2887   
 2888           public boolean contains(Object o) {
 2889               return indexOf(o) != -1;
 2890           }
 2891       }
 2892   
 2893       /**
 2894        * Returns a hash code based on the contents of the specified array.
 2895        * For any two <tt>long</tt> arrays <tt>a</tt> and <tt>b</tt>
 2896        * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
 2897        * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
 2898        *
 2899        * <p>The value returned by this method is the same value that would be
 2900        * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
 2901        * method on a {@link List} containing a sequence of {@link Long}
 2902        * instances representing the elements of <tt>a</tt> in the same order.
 2903        * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
 2904        *
 2905        * @param a the array whose hash value to compute
 2906        * @return a content-based hash code for <tt>a</tt>
 2907        * @since 1.5
 2908        */
 2909       public static int hashCode(long a[]) {
 2910           if (a == null)
 2911               return 0;
 2912   
 2913           int result = 1;
 2914           for (long element : a) {
 2915               int elementHash = (int)(element ^ (element >>> 32));
 2916               result = 31 * result + elementHash;
 2917           }
 2918   
 2919           return result;
 2920       }
 2921   
 2922       /**
 2923        * Returns a hash code based on the contents of the specified array.
 2924        * For any two non-null <tt>int</tt> arrays <tt>a</tt> and <tt>b</tt>
 2925        * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
 2926        * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
 2927        *
 2928        * <p>The value returned by this method is the same value that would be
 2929        * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
 2930        * method on a {@link List} containing a sequence of {@link Integer}
 2931        * instances representing the elements of <tt>a</tt> in the same order.
 2932        * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
 2933        *
 2934        * @param a the array whose hash value to compute
 2935        * @return a content-based hash code for <tt>a</tt>
 2936        * @since 1.5
 2937        */
 2938       public static int hashCode(int a[]) {
 2939           if (a == null)
 2940               return 0;
 2941   
 2942           int result = 1;
 2943           for (int element : a)
 2944               result = 31 * result + element;
 2945   
 2946           return result;
 2947       }
 2948   
 2949       /**
 2950        * Returns a hash code based on the contents of the specified array.
 2951        * For any two <tt>short</tt> arrays <tt>a</tt> and <tt>b</tt>
 2952        * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
 2953        * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
 2954        *
 2955        * <p>The value returned by this method is the same value that would be
 2956        * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
 2957        * method on a {@link List} containing a sequence of {@link Short}
 2958        * instances representing the elements of <tt>a</tt> in the same order.
 2959        * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
 2960        *
 2961        * @param a the array whose hash value to compute
 2962        * @return a content-based hash code for <tt>a</tt>
 2963        * @since 1.5
 2964        */
 2965       public static int hashCode(short a[]) {
 2966           if (a == null)
 2967               return 0;
 2968   
 2969           int result = 1;
 2970           for (short element : a)
 2971               result = 31 * result + element;
 2972   
 2973           return result;
 2974       }
 2975   
 2976       /**
 2977        * Returns a hash code based on the contents of the specified array.
 2978        * For any two <tt>char</tt> arrays <tt>a</tt> and <tt>b</tt>
 2979        * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
 2980        * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
 2981        *
 2982        * <p>The value returned by this method is the same value that would be
 2983        * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
 2984        * method on a {@link List} containing a sequence of {@link Character}
 2985        * instances representing the elements of <tt>a</tt> in the same order.
 2986        * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
 2987        *
 2988        * @param a the array whose hash value to compute
 2989        * @return a content-based hash code for <tt>a</tt>
 2990        * @since 1.5
 2991        */
 2992       public static int hashCode(char a[]) {
 2993           if (a == null)
 2994               return 0;
 2995   
 2996           int result = 1;
 2997           for (char element : a)
 2998               result = 31 * result + element;
 2999   
 3000           return result;
 3001       }
 3002   
 3003       /**
 3004        * Returns a hash code based on the contents of the specified array.
 3005        * For any two <tt>byte</tt> arrays <tt>a</tt> and <tt>b</tt>
 3006        * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
 3007        * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
 3008        *
 3009        * <p>The value returned by this method is the same value that would be
 3010        * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
 3011        * method on a {@link List} containing a sequence of {@link Byte}
 3012        * instances representing the elements of <tt>a</tt> in the same order.
 3013        * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
 3014        *
 3015        * @param a the array whose hash value to compute
 3016        * @return a content-based hash code for <tt>a</tt>
 3017        * @since 1.5
 3018        */
 3019       public static int hashCode(byte a[]) {
 3020           if (a == null)
 3021               return 0;
 3022   
 3023           int result = 1;
 3024           for (byte element : a)
 3025               result = 31 * result + element;
 3026   
 3027           return result;
 3028       }
 3029   
 3030       /**
 3031        * Returns a hash code based on the contents of the specified array.
 3032        * For any two <tt>boolean</tt> arrays <tt>a</tt> and <tt>b</tt>
 3033        * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
 3034        * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
 3035        *
 3036        * <p>The value returned by this method is the same value that would be
 3037        * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
 3038        * method on a {@link List} containing a sequence of {@link Boolean}
 3039        * instances representing the elements of <tt>a</tt> in the same order.
 3040        * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
 3041        *
 3042        * @param a the array whose hash value to compute
 3043        * @return a content-based hash code for <tt>a</tt>
 3044        * @since 1.5
 3045        */
 3046       public static int hashCode(boolean a[]) {
 3047           if (a == null)
 3048               return 0;
 3049   
 3050           int result = 1;
 3051           for (boolean element : a)
 3052               result = 31 * result + (element ? 1231 : 1237);
 3053   
 3054           return result;
 3055       }
 3056   
 3057       /**
 3058        * Returns a hash code based on the contents of the specified array.
 3059        * For any two <tt>float</tt> arrays <tt>a</tt> and <tt>b</tt>
 3060        * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
 3061        * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
 3062        *
 3063        * <p>The value returned by this method is the same value that would be
 3064        * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
 3065        * method on a {@link List} containing a sequence of {@link Float}
 3066        * instances representing the elements of <tt>a</tt> in the same order.
 3067        * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
 3068        *
 3069        * @param a the array whose hash value to compute
 3070        * @return a content-based hash code for <tt>a</tt>
 3071        * @since 1.5
 3072        */
 3073       public static int hashCode(float a[]) {
 3074           if (a == null)
 3075               return 0;
 3076   
 3077           int result = 1;
 3078           for (float element : a)
 3079               result = 31 * result + Float.floatToIntBits(element);
 3080   
 3081           return result;
 3082       }
 3083   
 3084       /**
 3085        * Returns a hash code based on the contents of the specified array.
 3086        * For any two <tt>double</tt> arrays <tt>a</tt> and <tt>b</tt>
 3087        * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
 3088        * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
 3089        *
 3090        * <p>The value returned by this method is the same value that would be
 3091        * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
 3092        * method on a {@link List} containing a sequence of {@link Double}
 3093        * instances representing the elements of <tt>a</tt> in the same order.
 3094        * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
 3095        *
 3096        * @param a the array whose hash value to compute
 3097        * @return a content-based hash code for <tt>a</tt>
 3098        * @since 1.5
 3099        */
 3100       public static int hashCode(double a[]) {
 3101           if (a == null)
 3102               return 0;
 3103   
 3104           int result = 1;
 3105           for (double element : a) {
 3106               long bits = Double.doubleToLongBits(element);
 3107               result = 31 * result + (int)(bits ^ (bits >>> 32));
 3108           }
 3109           return result;
 3110       }
 3111   
 3112       /**
 3113        * Returns a hash code based on the contents of the specified array.  If
 3114        * the array contains other arrays as elements, the hash code is based on
 3115        * their identities rather than their contents.  It is therefore
 3116        * acceptable to invoke this method on an array that contains itself as an
 3117        * element,  either directly or indirectly through one or more levels of
 3118        * arrays.
 3119        *
 3120        * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
 3121        * <tt>Arrays.equals(a, b)</tt>, it is also the case that
 3122        * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
 3123        *
 3124        * <p>The value returned by this method is equal to the value that would
 3125        * be returned by <tt>Arrays.asList(a).hashCode()</tt>, unless <tt>a</tt>
 3126        * is <tt>null</tt>, in which case <tt>0</tt> is returned.
 3127        *
 3128        * @param a the array whose content-based hash code to compute
 3129        * @return a content-based hash code for <tt>a</tt>
 3130        * @see #deepHashCode(Object[])
 3131        * @since 1.5
 3132        */
 3133       public static int hashCode(Object a[]) {
 3134           if (a == null)
 3135               return 0;
 3136   
 3137           int result = 1;
 3138   
 3139           for (Object element : a)
 3140               result = 31 * result + (element == null ? 0 : element.hashCode());
 3141   
 3142           return result;
 3143       }
 3144   
 3145       /**
 3146        * Returns a hash code based on the "deep contents" of the specified
 3147        * array.  If the array contains other arrays as elements, the
 3148        * hash code is based on their contents and so on, ad infinitum.
 3149        * It is therefore unacceptable to invoke this method on an array that
 3150        * contains itself as an element, either directly or indirectly through
 3151        * one or more levels of arrays.  The behavior of such an invocation is
 3152        * undefined.
 3153        *
 3154        * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
 3155        * <tt>Arrays.deepEquals(a, b)</tt>, it is also the case that
 3156        * <tt>Arrays.deepHashCode(a) == Arrays.deepHashCode(b)</tt>.
 3157        *
 3158        * <p>The computation of the value returned by this method is similar to
 3159        * that of the value returned by {@link List#hashCode()} on a list
 3160        * containing the same elements as <tt>a</tt> in the same order, with one
 3161        * difference: If an element <tt>e</tt> of <tt>a</tt> is itself an array,
 3162        * its hash code is computed not by calling <tt>e.hashCode()</tt>, but as
 3163        * by calling the appropriate overloading of <tt>Arrays.hashCode(e)</tt>
 3164        * if <tt>e</tt> is an array of a primitive type, or as by calling
 3165        * <tt>Arrays.deepHashCode(e)</tt> recursively if <tt>e</tt> is an array
 3166        * of a reference type.  If <tt>a</tt> is <tt>null</tt>, this method
 3167        * returns 0.
 3168        *
 3169        * @param a the array whose deep-content-based hash code to compute
 3170        * @return a deep-content-based hash code for <tt>a</tt>
 3171        * @see #hashCode(Object[])
 3172        * @since 1.5
 3173        */
 3174       public static int deepHashCode(Object a[]) {
 3175           if (a == null)
 3176               return 0;
 3177   
 3178           int result = 1;
 3179   
 3180           for (Object element : a) {
 3181               int elementHash = 0;
 3182               if (element instanceof Object[])
 3183                   elementHash = deepHashCode((Object[]) element);
 3184               else if (element instanceof byte[])
 3185                   elementHash = hashCode((byte[]) element);
 3186               else if (element instanceof short[])
 3187                   elementHash = hashCode((short[]) element);
 3188               else if (element instanceof int[])
 3189                   elementHash = hashCode((int[]) element);
 3190               else if (element instanceof long[])
 3191                   elementHash = hashCode((long[]) element);
 3192               else if (element instanceof char[])
 3193                   elementHash = hashCode((char[]) element);
 3194               else if (element instanceof float[])
 3195                   elementHash = hashCode((float[]) element);
 3196               else if (element instanceof double[])
 3197                   elementHash = hashCode((double[]) element);
 3198               else if (element instanceof boolean[])
 3199                   elementHash = hashCode((boolean[]) element);
 3200               else if (element != null)
 3201                   elementHash = element.hashCode();
 3202   
 3203               result = 31 * result + elementHash;
 3204           }
 3205   
 3206           return result;
 3207       }
 3208   
 3209       /**
 3210        * Returns <tt>true</tt> if the two specified arrays are <i>deeply
 3211        * equal</i> to one another.  Unlike the {@link #equals(Object[],Object[])}
 3212        * method, this method is appropriate for use with nested arrays of
 3213        * arbitrary depth.
 3214        *
 3215        * <p>Two array references are considered deeply equal if both
 3216        * are <tt>null</tt>, or if they refer to arrays that contain the same
 3217        * number of elements and all corresponding pairs of elements in the two
 3218        * arrays are deeply equal.
 3219        *
 3220        * <p>Two possibly <tt>null</tt> elements <tt>e1</tt> and <tt>e2</tt> are
 3221        * deeply equal if any of the following conditions hold:
 3222        * <ul>
 3223        *    <li> <tt>e1</tt> and <tt>e2</tt> are both arrays of object reference
 3224        *         types, and <tt>Arrays.deepEquals(e1, e2) would return true</tt>
 3225        *    <li> <tt>e1</tt> and <tt>e2</tt> are arrays of the same primitive
 3226        *         type, and the appropriate overloading of
 3227        *         <tt>Arrays.equals(e1, e2)</tt> would return true.
 3228        *    <li> <tt>e1 == e2</tt>
 3229        *    <li> <tt>e1.equals(e2)</tt> would return true.
 3230        * </ul>
 3231        * Note that this definition permits <tt>null</tt> elements at any depth.
 3232        *
 3233        * <p>If either of the specified arrays contain themselves as elements
 3234        * either directly or indirectly through one or more levels of arrays,
 3235        * the behavior of this method is undefined.
 3236        *
 3237        * @param a1 one array to be tested for equality
 3238        * @param a2 the other array to be tested for equality
 3239        * @return <tt>true</tt> if the two arrays are equal
 3240        * @see #equals(Object[],Object[])
 3241        * @see Objects#deepEquals(Object, Object)
 3242        * @since 1.5
 3243        */
 3244       public static boolean deepEquals(Object[] a1, Object[] a2) {
 3245           if (a1 == a2)
 3246               return true;
 3247           if (a1 == null || a2==null)
 3248               return false;
 3249           int length = a1.length;
 3250           if (a2.length != length)
 3251               return false;
 3252   
 3253           for (int i = 0; i < length; i++) {
 3254               Object e1 = a1[i];
 3255               Object e2 = a2[i];
 3256   
 3257               if (e1 == e2)
 3258                   continue;
 3259               if (e1 == null)
 3260                   return false;
 3261   
 3262               // Figure out whether the two elements are equal
 3263               boolean eq = deepEquals0(e1, e2);
 3264   
 3265               if (!eq)
 3266                   return false;
 3267           }
 3268           return true;
 3269       }
 3270   
 3271       static boolean deepEquals0(Object e1, Object e2) {
 3272           assert e1 != null;
 3273           boolean eq;
 3274           if (e1 instanceof Object[] && e2 instanceof Object[])
 3275               eq = deepEquals ((Object[]) e1, (Object[]) e2);
 3276           else if (e1 instanceof byte[] && e2 instanceof byte[])
 3277               eq = equals((byte[]) e1, (byte[]) e2);
 3278           else if (e1 instanceof short[] && e2 instanceof short[])
 3279               eq = equals((short[]) e1, (short[]) e2);
 3280           else if (e1 instanceof int[] && e2 instanceof int[])
 3281               eq = equals((int[]) e1, (int[]) e2);
 3282           else if (e1 instanceof long[] && e2 instanceof long[])
 3283               eq = equals((long[]) e1, (long[]) e2);
 3284           else if (e1 instanceof char[] && e2 instanceof char[])
 3285               eq = equals((char[]) e1, (char[]) e2);
 3286           else if (e1 instanceof float[] && e2 instanceof float[])
 3287               eq = equals((float[]) e1, (float[]) e2);
 3288           else if (e1 instanceof double[] && e2 instanceof double[])
 3289               eq = equals((double[]) e1, (double[]) e2);
 3290           else if (e1 instanceof boolean[] && e2 instanceof boolean[])
 3291               eq = equals((boolean[]) e1, (boolean[]) e2);
 3292           else
 3293               eq = e1.equals(e2);
 3294           return eq;
 3295       }
 3296   
 3297       /**
 3298        * Returns a string representation of the contents of the specified array.
 3299        * The string representation consists of a list of the array's elements,
 3300        * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
 3301        * separated by the characters <tt>", "</tt> (a comma followed by a
 3302        * space).  Elements are converted to strings as by
 3303        * <tt>String.valueOf(long)</tt>.  Returns <tt>"null"</tt> if <tt>a</tt>
 3304        * is <tt>null</tt>.
 3305        *
 3306        * @param a the array whose string representation to return
 3307        * @return a string representation of <tt>a</tt>
 3308        * @since 1.5
 3309        */
 3310       public static String toString(long[] a) {
 3311           if (a == null)
 3312               return "null";
 3313           int iMax = a.length - 1;
 3314           if (iMax == -1)
 3315               return "[]";
 3316   
 3317           StringBuilder b = new StringBuilder();
 3318           b.append('[');
 3319           for (int i = 0; ; i++) {
 3320               b.append(a[i]);
 3321               if (i == iMax)
 3322                   return b.append(']').toString();
 3323               b.append(", ");
 3324           }
 3325       }
 3326   
 3327       /**
 3328        * Returns a string representation of the contents of the specified array.
 3329        * The string representation consists of a list of the array's elements,
 3330        * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
 3331        * separated by the characters <tt>", "</tt> (a comma followed by a
 3332        * space).  Elements are converted to strings as by
 3333        * <tt>String.valueOf(int)</tt>.  Returns <tt>"null"</tt> if <tt>a</tt> is
 3334        * <tt>null</tt>.
 3335        *
 3336        * @param a the array whose string representation to return
 3337        * @return a string representation of <tt>a</tt>
 3338        * @since 1.5
 3339        */
 3340       public static String toString(int[] a) {
 3341           if (a == null)
 3342               return "null";
 3343           int iMax = a.length - 1;
 3344           if (iMax == -1)
 3345               return "[]";
 3346   
 3347           StringBuilder b = new StringBuilder();
 3348           b.append('[');
 3349           for (int i = 0; ; i++) {
 3350               b.append(a[i]);
 3351               if (i == iMax)
 3352                   return b.append(']').toString();
 3353               b.append(", ");
 3354           }
 3355       }
 3356   
 3357       /**
 3358        * Returns a string representation of the contents of the specified array.
 3359        * The string representation consists of a list of the array's elements,
 3360        * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
 3361        * separated by the characters <tt>", "</tt> (a comma followed by a
 3362        * space).  Elements are converted to strings as by
 3363        * <tt>String.valueOf(short)</tt>.  Returns <tt>"null"</tt> if <tt>a</tt>
 3364        * is <tt>null</tt>.
 3365        *
 3366        * @param a the array whose string representation to return
 3367        * @return a string representation of <tt>a</tt>
 3368        * @since 1.5
 3369        */
 3370       public static String toString(short[] a) {
 3371           if (a == null)
 3372               return "null";
 3373           int iMax = a.length - 1;
 3374           if (iMax == -1)
 3375               return "[]";
 3376   
 3377           StringBuilder b = new StringBuilder();
 3378           b.append('[');
 3379           for (int i = 0; ; i++) {
 3380               b.append(a[i]);
 3381               if (i == iMax)
 3382                   return b.append(']').toString();
 3383               b.append(", ");
 3384           }
 3385       }
 3386   
 3387       /**
 3388        * Returns a string representation of the contents of the specified array.
 3389        * The string representation consists of a list of the array's elements,
 3390        * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
 3391        * separated by the characters <tt>", "</tt> (a comma followed by a
 3392        * space).  Elements are converted to strings as by
 3393        * <tt>String.valueOf(char)</tt>.  Returns <tt>"null"</tt> if <tt>a</tt>
 3394        * is <tt>null</tt>.
 3395        *
 3396        * @param a the array whose string representation to return
 3397        * @return a string representation of <tt>a</tt>
 3398        * @since 1.5
 3399        */
 3400       public static String toString(char[] a) {
 3401           if (a == null)
 3402               return "null";
 3403           int iMax = a.length - 1;
 3404           if (iMax == -1)
 3405               return "[]";
 3406   
 3407           StringBuilder b = new StringBuilder();
 3408           b.append('[');
 3409           for (int i = 0; ; i++) {
 3410               b.append(a[i]);
 3411               if (i == iMax)
 3412                   return b.append(']').toString();
 3413               b.append(", ");
 3414           }
 3415       }
 3416   
 3417       /**
 3418        * Returns a string representation of the contents of the specified array.
 3419        * The string representation consists of a list of the array's elements,
 3420        * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements
 3421        * are separated by the characters <tt>", "</tt> (a comma followed
 3422        * by a space).  Elements are converted to strings as by
 3423        * <tt>String.valueOf(byte)</tt>.  Returns <tt>"null"</tt> if
 3424        * <tt>a</tt> is <tt>null</tt>.
 3425        *
 3426        * @param a the array whose string representation to return
 3427        * @return a string representation of <tt>a</tt>
 3428        * @since 1.5
 3429        */
 3430       public static String toString(byte[] a) {
 3431           if (a == null)
 3432               return "null";
 3433           int iMax = a.length - 1;
 3434           if (iMax == -1)
 3435               return "[]";
 3436   
 3437           StringBuilder b = new StringBuilder();
 3438           b.append('[');
 3439           for (int i = 0; ; i++) {
 3440               b.append(a[i]);
 3441               if (i == iMax)
 3442                   return b.append(']').toString();
 3443               b.append(", ");
 3444           }
 3445       }
 3446   
 3447       /**
 3448        * Returns a string representation of the contents of the specified array.
 3449        * The string representation consists of a list of the array's elements,
 3450        * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
 3451        * separated by the characters <tt>", "</tt> (a comma followed by a
 3452        * space).  Elements are converted to strings as by
 3453        * <tt>String.valueOf(boolean)</tt>.  Returns <tt>"null"</tt> if
 3454        * <tt>a</tt> is <tt>null</tt>.
 3455        *
 3456        * @param a the array whose string representation to return
 3457        * @return a string representation of <tt>a</tt>
 3458        * @since 1.5
 3459        */
 3460       public static String toString(boolean[] a) {
 3461           if (a == null)
 3462               return "null";
 3463           int iMax = a.length - 1;
 3464           if (iMax == -1)
 3465               return "[]";
 3466   
 3467           StringBuilder b = new StringBuilder();
 3468           b.append('[');
 3469           for (int i = 0; ; i++) {
 3470               b.append(a[i]);
 3471               if (i == iMax)
 3472                   return b.append(']').toString();
 3473               b.append(", ");
 3474           }
 3475       }
 3476   
 3477       /**
 3478        * Returns a string representation of the contents of the specified array.
 3479        * The string representation consists of a list of the array's elements,
 3480        * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
 3481        * separated by the characters <tt>", "</tt> (a comma followed by a
 3482        * space).  Elements are converted to strings as by
 3483        * <tt>String.valueOf(float)</tt>.  Returns <tt>"null"</tt> if <tt>a</tt>
 3484        * is <tt>null</tt>.
 3485        *
 3486        * @param a the array whose string representation to return
 3487        * @return a string representation of <tt>a</tt>
 3488        * @since 1.5
 3489        */
 3490       public static String toString(float[] a) {
 3491           if (a == null)
 3492               return "null";
 3493   
 3494           int iMax = a.length - 1;
 3495           if (iMax == -1)
 3496               return "[]";
 3497   
 3498           StringBuilder b = new StringBuilder();
 3499           b.append('[');
 3500           for (int i = 0; ; i++) {
 3501               b.append(a[i]);
 3502               if (i == iMax)
 3503                   return b.append(']').toString();
 3504               b.append(", ");
 3505           }
 3506       }
 3507   
 3508       /**
 3509        * Returns a string representation of the contents of the specified array.
 3510        * The string representation consists of a list of the array's elements,
 3511        * enclosed in square brackets (<tt>"[]"</tt>).  Adjacent elements are
 3512        * separated by the characters <tt>", "</tt> (a comma followed by a
 3513        * space).  Elements are converted to strings as by
 3514        * <tt>String.valueOf(double)</tt>.  Returns <tt>"null"</tt> if <tt>a</tt>
 3515        * is <tt>null</tt>.
 3516        *
 3517        * @param a the array whose string representation to return
 3518        * @return a string representation of <tt>a</tt>
 3519        * @since 1.5
 3520        */
 3521       public static String toString(double[] a) {
 3522           if (a == null)
 3523               return "null";
 3524           int iMax = a.length - 1;
 3525           if (iMax == -1)
 3526               return "[]";
 3527   
 3528           StringBuilder b = new StringBuilder();
 3529           b.append('[');
 3530           for (int i = 0; ; i++) {
 3531               b.append(a[i]);
 3532               if (i == iMax)
 3533                   return b.append(']').toString();
 3534               b.append(", ");
 3535           }
 3536       }
 3537   
 3538       /**
 3539        * Returns a string representation of the contents of the specified array.
 3540        * If the array contains other arrays as elements, they are converted to
 3541        * strings by the {@link Object#toString} method inherited from
 3542        * <tt>Object</tt>, which describes their <i>identities</i> rather than
 3543        * their contents.
 3544        *
 3545        * <p>The value returned by this method is equal to the value that would
 3546        * be returned by <tt>Arrays.asList(a).toString()</tt>, unless <tt>a</tt>
 3547        * is <tt>null</tt>, in which case <tt>"null"</tt> is returned.
 3548        *
 3549        * @param a the array whose string representation to return
 3550        * @return a string representation of <tt>a</tt>
 3551        * @see #deepToString(Object[])
 3552        * @since 1.5
 3553        */
 3554       public static String toString(Object[] a) {
 3555           if (a == null)
 3556               return "null";
 3557   
 3558           int iMax = a.length - 1;
 3559           if (iMax == -1)
 3560               return "[]";
 3561   
 3562           StringBuilder b = new StringBuilder();
 3563           b.append('[');
 3564           for (int i = 0; ; i++) {
 3565               b.append(String.valueOf(a[i]));
 3566               if (i == iMax)
 3567                   return b.append(']').toString();
 3568               b.append(", ");
 3569           }
 3570       }
 3571   
 3572       /**
 3573        * Returns a string representation of the "deep contents" of the specified
 3574        * array.  If the array contains other arrays as elements, the string
 3575        * representation contains their contents and so on.  This method is
 3576        * designed for converting multidimensional arrays to strings.
 3577        *
 3578        * <p>The string representation consists of a list of the array's
 3579        * elements, enclosed in square brackets (<tt>"[]"</tt>).  Adjacent
 3580        * elements are separated by the characters <tt>", "</tt> (a comma
 3581        * followed by a space).  Elements are converted to strings as by
 3582        * <tt>String.valueOf(Object)</tt>, unless they are themselves
 3583        * arrays.
 3584        *
 3585        * <p>If an element <tt>e</tt> is an array of a primitive type, it is
 3586        * converted to a string as by invoking the appropriate overloading of
 3587        * <tt>Arrays.toString(e)</tt>.  If an element <tt>e</tt> is an array of a
 3588        * reference type, it is converted to a string as by invoking
 3589        * this method recursively.
 3590        *
 3591        * <p>To avoid infinite recursion, if the specified array contains itself
 3592        * as an element, or contains an indirect reference to itself through one
 3593        * or more levels of arrays, the self-reference is converted to the string
 3594        * <tt>"[...]"</tt>.  For example, an array containing only a reference
 3595        * to itself would be rendered as <tt>"[[...]]"</tt>.
 3596        *
 3597        * <p>This method returns <tt>"null"</tt> if the specified array
 3598        * is <tt>null</tt>.
 3599        *
 3600        * @param a the array whose string representation to return
 3601        * @return a string representation of <tt>a</tt>
 3602        * @see #toString(Object[])
 3603        * @since 1.5
 3604        */
 3605       public static String deepToString(Object[] a) {
 3606           if (a == null)
 3607               return "null";
 3608   
 3609           int bufLen = 20 * a.length;
 3610           if (a.length != 0 && bufLen <= 0)
 3611               bufLen = Integer.MAX_VALUE;
 3612           StringBuilder buf = new StringBuilder(bufLen);
 3613           deepToString(a, buf, new HashSet<Object[]>());
 3614           return buf.toString();
 3615       }
 3616   
 3617       private static void deepToString(Object[] a, StringBuilder buf,
 3618                                        Set<Object[]> dejaVu) {
 3619           if (a == null) {
 3620               buf.append("null");
 3621               return;
 3622           }
 3623           int iMax = a.length - 1;
 3624           if (iMax == -1) {
 3625               buf.append("[]");
 3626               return;
 3627           }
 3628   
 3629           dejaVu.add(a);
 3630           buf.append('[');
 3631           for (int i = 0; ; i++) {
 3632   
 3633               Object element = a[i];
 3634               if (element == null) {
 3635                   buf.append("null");
 3636               } else {
 3637                   Class eClass = element.getClass();
 3638   
 3639                   if (eClass.isArray()) {
 3640                       if (eClass == byte[].class)
 3641                           buf.append(toString((byte[]) element));
 3642                       else if (eClass == short[].class)
 3643                           buf.append(toString((short[]) element));
 3644                       else if (eClass == int[].class)
 3645                           buf.append(toString((int[]) element));
 3646                       else if (eClass == long[].class)
 3647                           buf.append(toString((long[]) element));
 3648                       else if (eClass == char[].class)
 3649                           buf.append(toString((char[]) element));
 3650                       else if (eClass == float[].class)
 3651                           buf.append(toString((float[]) element));
 3652                       else if (eClass == double[].class)
 3653                           buf.append(toString((double[]) element));
 3654                       else if (eClass == boolean[].class)
 3655                           buf.append(toString((boolean[]) element));
 3656                       else { // element is an array of object references
 3657                           if (dejaVu.contains(element))
 3658                               buf.append("[...]");
 3659                           else
 3660                               deepToString((Object[])element, buf, dejaVu);
 3661                       }
 3662                   } else {  // element is non-null and not an array
 3663                       buf.append(element.toString());
 3664                   }
 3665               }
 3666               if (i == iMax)
 3667                   break;
 3668               buf.append(", ");
 3669           }
 3670           buf.append(']');
 3671           dejaVu.remove(a);
 3672       }
 3673   }

Save This Page
Home » openjdk-7 » java » util » [javadoc | source]