1 /*

        2  * Copyright (c) 1997, 2007, 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 <tt>NullPointerException</tt> if

       36  * 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 <tt>sort(Object[])</tt> 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 

       56 public class Arrays {

       57     // Suppresses default constructor, ensuring non-instantiability.

       58     private Arrays() {

       59     }

       60 

       61     // Sorting

       62 

       63     /**

       64      * Sorts the specified array of longs into ascending numerical order.

       65      * The sorting algorithm is a tuned quicksort, adapted from Jon

       66      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

       67      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

       68      * 1993).  This algorithm offers n*log(n) performance on many data sets

       69      * that cause other quicksorts to degrade to quadratic performance.

       70      *

       71      * @param a the array to be sorted

       72      */

       73     public static void sort(long[] a) {

       74         sort1(a, 0, a.length);

       75     }

       76 

       77     /**

       78      * Sorts the specified range of the specified array of longs into

       79      * ascending numerical order.  The range to be sorted extends from index

       80      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.

       81      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)

       82      *

       83      * <p>The sorting algorithm is a tuned quicksort, adapted from Jon

       84      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

       85      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

       86      * 1993).  This algorithm offers n*log(n) performance on many data sets

       87      * that cause other quicksorts to degrade to quadratic performance.

       88      *

       89      * @param a the array to be sorted

       90      * @param fromIndex the index of the first element (inclusive) to be

       91      *        sorted

       92      * @param toIndex the index of the last element (exclusive) to be sorted

       93      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

       94      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

       95      * <tt>toIndex &gt; a.length</tt>

       96      */

       97     public static void sort(long[] a, int fromIndex, int toIndex) {

       98         rangeCheck(a.length, fromIndex, toIndex);

       99         sort1(a, fromIndex, toIndex-fromIndex);

      100     }

      101 

      102     /**

      103      * Sorts the specified array of ints into ascending numerical order.

      104      * The sorting algorithm is a tuned quicksort, adapted from Jon

      105      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

      106      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

      107      * 1993).  This algorithm offers n*log(n) performance on many data sets

      108      * that cause other quicksorts to degrade to quadratic performance.

      109      *

      110      * @param a the array to be sorted

      111      */

      112     public static void sort(int[] a) {

      113         sort1(a, 0, a.length);

      114     }

      115 

      116     /**

      117      * Sorts the specified range of the specified array of ints into

      118      * ascending numerical order.  The range to be sorted extends from index

      119      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.

      120      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>

      121      *

      122      * The sorting algorithm is a tuned quicksort, adapted from Jon

      123      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

      124      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

      125      * 1993).  This algorithm offers n*log(n) performance on many data sets

      126      * that cause other quicksorts to degrade to quadratic performance.

      127      *

      128      * @param a the array to be sorted

      129      * @param fromIndex the index of the first element (inclusive) to be

      130      *        sorted

      131      * @param toIndex the index of the last element (exclusive) to be sorted

      132      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

      133      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

      134      *         <tt>toIndex &gt; a.length</tt>

      135      */

      136     public static void sort(int[] a, int fromIndex, int toIndex) {

      137         rangeCheck(a.length, fromIndex, toIndex);

      138         sort1(a, fromIndex, toIndex-fromIndex);

      139     }

      140 

      141     /**

      142      * Sorts the specified array of shorts into ascending numerical order.

      143      * The sorting algorithm is a tuned quicksort, adapted from Jon

      144      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

      145      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

      146      * 1993).  This algorithm offers n*log(n) performance on many data sets

      147      * that cause other quicksorts to degrade to quadratic performance.

      148      *

      149      * @param a the array to be sorted

      150      */

      151     public static void sort(short[] a) {

      152         sort1(a, 0, a.length);

      153     }

      154 

      155     /**

      156      * Sorts the specified range of the specified array of shorts into

      157      * ascending numerical order.  The range to be sorted extends from index

      158      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.

      159      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>

      160      *

      161      * The sorting algorithm is a tuned quicksort, adapted from Jon

      162      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

      163      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

      164      * 1993).  This algorithm offers n*log(n) performance on many data sets

      165      * that cause other quicksorts to degrade to quadratic performance.

      166      *

      167      * @param a the array to be sorted

      168      * @param fromIndex the index of the first element (inclusive) to be

      169      *        sorted

      170      * @param toIndex the index of the last element (exclusive) to be sorted

      171      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

      172      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

      173      *         <tt>toIndex &gt; a.length</tt>

      174      */

      175     public static void sort(short[] a, int fromIndex, int toIndex) {

      176         rangeCheck(a.length, fromIndex, toIndex);

      177         sort1(a, fromIndex, toIndex-fromIndex);

      178     }

      179 

      180     /**

      181      * Sorts the specified array of chars into ascending numerical order.

      182      * The sorting algorithm is a tuned quicksort, adapted from Jon

      183      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

      184      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

      185      * 1993).  This algorithm offers n*log(n) performance on many data sets

      186      * that cause other quicksorts to degrade to quadratic performance.

      187      *

      188      * @param a the array to be sorted

      189      */

      190     public static void sort(char[] a) {

      191         sort1(a, 0, a.length);

      192     }

      193 

      194     /**

      195      * Sorts the specified range of the specified array of chars into

      196      * ascending numerical order.  The range to be sorted extends from index

      197      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.

      198      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>

      199      *

      200      * The sorting algorithm is a tuned quicksort, adapted from Jon

      201      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

      202      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

      203      * 1993).  This algorithm offers n*log(n) performance on many data sets

      204      * that cause other quicksorts to degrade to quadratic performance.

      205      *

      206      * @param a the array to be sorted

      207      * @param fromIndex the index of the first element (inclusive) to be

      208      *        sorted

      209      * @param toIndex the index of the last element (exclusive) to be sorted

      210      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

      211      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

      212      *         <tt>toIndex &gt; a.length</tt>

      213      */

      214     public static void sort(char[] a, int fromIndex, int toIndex) {

      215         rangeCheck(a.length, fromIndex, toIndex);

      216         sort1(a, fromIndex, toIndex-fromIndex);

      217     }

      218 

      219     /**

      220      * Sorts the specified array of bytes into ascending numerical order.

      221      * The sorting algorithm is a tuned quicksort, adapted from Jon

      222      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

      223      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

      224      * 1993).  This algorithm offers n*log(n) performance on many data sets

      225      * that cause other quicksorts to degrade to quadratic performance.

      226      *

      227      * @param a the array to be sorted

      228      */

      229     public static void sort(byte[] a) {

      230         sort1(a, 0, a.length);

      231     }

      232 

      233     /**

      234      * Sorts the specified range of the specified array of bytes into

      235      * ascending numerical order.  The range to be sorted extends from index

      236      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.

      237      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>

      238      *

      239      * The sorting algorithm is a tuned quicksort, adapted from Jon

      240      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

      241      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

      242      * 1993).  This algorithm offers n*log(n) performance on many data sets

      243      * that cause other quicksorts to degrade to quadratic performance.

      244      *

      245      * @param a the array to be sorted

      246      * @param fromIndex the index of the first element (inclusive) to be

      247      *        sorted

      248      * @param toIndex the index of the last element (exclusive) to be sorted

      249      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

      250      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

      251      *         <tt>toIndex &gt; a.length</tt>

      252      */

      253     public static void sort(byte[] a, int fromIndex, int toIndex) {

      254         rangeCheck(a.length, fromIndex, toIndex);

      255         sort1(a, fromIndex, toIndex-fromIndex);

      256     }

      257 

      258     /**

      259      * Sorts the specified array of doubles into ascending numerical order.

      260      * <p>

      261      * The <code>&lt;</code> relation does not provide a total order on

      262      * all floating-point values; although they are distinct numbers

      263      * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value

      264      * compares neither less than, greater than, nor equal to any

      265      * floating-point value, even itself.  To allow the sort to

      266      * proceed, instead of using the <code>&lt;</code> relation to

      267      * determine ascending numerical order, this method uses the total

      268      * order imposed by {@link Double#compareTo}.  This ordering

      269      * differs from the <code>&lt;</code> relation in that

      270      * <code>-0.0</code> is treated as less than <code>0.0</code> and

      271      * NaN is considered greater than any other floating-point value.

      272      * For the purposes of sorting, all NaN values are considered

      273      * equivalent and equal.

      274      * <p>

      275      * The sorting algorithm is a tuned quicksort, adapted from Jon

      276      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

      277      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

      278      * 1993).  This algorithm offers n*log(n) performance on many data sets

      279      * that cause other quicksorts to degrade to quadratic performance.

      280      *

      281      * @param a the array to be sorted

      282      */

      283     public static void sort(double[] a) {

      284         sort2(a, 0, a.length);

      285     }

      286 

      287     /**

      288      * Sorts the specified range of the specified array of doubles into

      289      * ascending numerical order.  The range to be sorted extends from index

      290      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.

      291      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)

      292      * <p>

      293      * The <code>&lt;</code> relation does not provide a total order on

      294      * all floating-point values; although they are distinct numbers

      295      * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value

      296      * compares neither less than, greater than, nor equal to any

      297      * floating-point value, even itself.  To allow the sort to

      298      * proceed, instead of using the <code>&lt;</code> relation to

      299      * determine ascending numerical order, this method uses the total

      300      * order imposed by {@link Double#compareTo}.  This ordering

      301      * differs from the <code>&lt;</code> relation in that

      302      * <code>-0.0</code> is treated as less than <code>0.0</code> and

      303      * NaN is considered greater than any other floating-point value.

      304      * For the purposes of sorting, all NaN values are considered

      305      * equivalent and equal.

      306      * <p>

      307      * The sorting algorithm is a tuned quicksort, adapted from Jon

      308      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

      309      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

      310      * 1993).  This algorithm offers n*log(n) performance on many data sets

      311      * that cause other quicksorts to degrade to quadratic performance.

      312      *

      313      * @param a the array to be sorted

      314      * @param fromIndex the index of the first element (inclusive) to be

      315      *        sorted

      316      * @param toIndex the index of the last element (exclusive) to be sorted

      317      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

      318      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

      319      *         <tt>toIndex &gt; a.length</tt>

      320      */

      321     public static void sort(double[] a, int fromIndex, int toIndex) {

      322         rangeCheck(a.length, fromIndex, toIndex);

      323         sort2(a, fromIndex, toIndex);

      324     }

      325 

      326     /**

      327      * Sorts the specified array of floats into ascending numerical order.

      328      * <p>

      329      * The <code>&lt;</code> relation does not provide a total order on

      330      * all floating-point values; although they are distinct numbers

      331      * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value

      332      * compares neither less than, greater than, nor equal to any

      333      * floating-point value, even itself.  To allow the sort to

      334      * proceed, instead of using the <code>&lt;</code> relation to

      335      * determine ascending numerical order, this method uses the total

      336      * order imposed by {@link Float#compareTo}.  This ordering

      337      * differs from the <code>&lt;</code> relation in that

      338      * <code>-0.0f</code> is treated as less than <code>0.0f</code> and

      339      * NaN is considered greater than any other floating-point value.

      340      * For the purposes of sorting, all NaN values are considered

      341      * equivalent and equal.

      342      * <p>

      343      * The sorting algorithm is a tuned quicksort, adapted from Jon

      344      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

      345      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

      346      * 1993).  This algorithm offers n*log(n) performance on many data sets

      347      * that cause other quicksorts to degrade to quadratic performance.

      348      *

      349      * @param a the array to be sorted

      350      */

      351     public static void sort(float[] a) {

      352         sort2(a, 0, a.length);

      353     }

      354 

      355     /**

      356      * Sorts the specified range of the specified array of floats into

      357      * ascending numerical order.  The range to be sorted extends from index

      358      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.

      359      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)

      360      * <p>

      361      * The <code>&lt;</code> relation does not provide a total order on

      362      * all floating-point values; although they are distinct numbers

      363      * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value

      364      * compares neither less than, greater than, nor equal to any

      365      * floating-point value, even itself.  To allow the sort to

      366      * proceed, instead of using the <code>&lt;</code> relation to

      367      * determine ascending numerical order, this method uses the total

      368      * order imposed by {@link Float#compareTo}.  This ordering

      369      * differs from the <code>&lt;</code> relation in that

      370      * <code>-0.0f</code> is treated as less than <code>0.0f</code> and

      371      * NaN is considered greater than any other floating-point value.

      372      * For the purposes of sorting, all NaN values are considered

      373      * equivalent and equal.

      374      * <p>

      375      * The sorting algorithm is a tuned quicksort, adapted from Jon

      376      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",

      377      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November

      378      * 1993).  This algorithm offers n*log(n) performance on many data sets

      379      * that cause other quicksorts to degrade to quadratic performance.

      380      *

      381      * @param a the array to be sorted

      382      * @param fromIndex the index of the first element (inclusive) to be

      383      *        sorted

      384      * @param toIndex the index of the last element (exclusive) to be sorted

      385      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

      386      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

      387      *         <tt>toIndex &gt; a.length</tt>

      388      */

      389     public static void sort(float[] a, int fromIndex, int toIndex) {

      390         rangeCheck(a.length, fromIndex, toIndex);

      391         sort2(a, fromIndex, toIndex);

      392     }

      393 

      394     private static void sort2(double a[], int fromIndex, int toIndex) {

      395         final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d);

      396         /*

      397          * The sort is done in three phases to avoid the expense of using

      398          * NaN and -0.0 aware comparisons during the main sort.

      399          */

      400 

      401         /*

      402          * Preprocessing phase:  Move any NaN's to end of array, count the

      403          * number of -0.0's, and turn them into 0.0's.

      404          */

      405         int numNegZeros = 0;

      406         int i = fromIndex, n = toIndex;

      407         while(i < n) {

      408             if (a[i] != a[i]) {

      409                 swap(a, i, --n);

      410             } else {

      411                 if (a[i]==0 && Double.doubleToLongBits(a[i])==NEG_ZERO_BITS) {

      412                     a[i] = 0.0d;

      413                     numNegZeros++;

      414                 }

      415                 i++;

      416             }

      417         }

      418 

      419         // Main sort phase: quicksort everything but the NaN's

      420         sort1(a, fromIndex, n-fromIndex);

      421 

      422         // Postprocessing phase: change 0.0's to -0.0's as required

      423         if (numNegZeros != 0) {

      424             int j = binarySearch0(a, fromIndex, n, 0.0d); // posn of ANY zero

      425             do {

      426                 j--;

      427             } while (j>=fromIndex && a[j]==0.0d);

      428 

      429             // j is now one less than the index of the FIRST zero

      430             for (int k=0; k<numNegZeros; k++)

      431                 a[++j] = -0.0d;

      432         }

      433     }

      434 

      435 

      436     private static void sort2(float a[], int fromIndex, int toIndex) {

      437         final int NEG_ZERO_BITS = Float.floatToIntBits(-0.0f);

      438         /*

      439          * The sort is done in three phases to avoid the expense of using

      440          * NaN and -0.0 aware comparisons during the main sort.

      441          */

      442 

      443         /*

      444          * Preprocessing phase:  Move any NaN's to end of array, count the

      445          * number of -0.0's, and turn them into 0.0's.

      446          */

      447         int numNegZeros = 0;

      448         int i = fromIndex, n = toIndex;

      449         while(i < n) {

      450             if (a[i] != a[i]) {

      451                 swap(a, i, --n);

      452             } else {

      453                 if (a[i]==0 && Float.floatToIntBits(a[i])==NEG_ZERO_BITS) {

      454                     a[i] = 0.0f;

      455                     numNegZeros++;

      456                 }

      457                 i++;

      458             }

      459         }

      460 

      461         // Main sort phase: quicksort everything but the NaN's

      462         sort1(a, fromIndex, n-fromIndex);

      463 

      464         // Postprocessing phase: change 0.0's to -0.0's as required

      465         if (numNegZeros != 0) {

      466             int j = binarySearch0(a, fromIndex, n, 0.0f); // posn of ANY zero

      467             do {

      468                 j--;

      469             } while (j>=fromIndex && a[j]==0.0f);

      470 

      471             // j is now one less than the index of the FIRST zero

      472             for (int k=0; k<numNegZeros; k++)

      473                 a[++j] = -0.0f;

      474         }

      475     }

      476 

      477 

      478     /*

      479      * The code for each of the seven primitive types is largely identical.

      480      * C'est la vie.

      481      */

      482 

      483     /**

      484      * Sorts the specified sub-array of longs into ascending order.

      485      */

      486     private static void sort1(long x[], int off, int len) {

      487         // Insertion sort on smallest arrays

      488         if (len < 7) {

      489             for (int i=off; i<len+off; i++)

      490                 for (int j=i; j>off && x[j-1]>x[j]; j--)

      491                     swap(x, j, j-1);

      492             return;

      493         }

      494 

      495         // Choose a partition element, v

      496         int m = off + (len >> 1);       // Small arrays, middle element

      497         if (len > 7) {

      498             int l = off;

      499             int n = off + len - 1;

      500             if (len > 40) {        // Big arrays, pseudomedian of 9

      501                 int s = len/8;

      502                 l = med3(x, l,     l+s, l+2*s);

      503                 m = med3(x, m-s,   m,   m+s);

      504                 n = med3(x, n-2*s, n-s, n);

      505             }

      506             m = med3(x, l, m, n); // Mid-size, med of 3

      507         }

      508         long v = x[m];

      509 

      510         // Establish Invariant: v* (<v)* (>v)* v*

      511         int a = off, b = a, c = off + len - 1, d = c;

      512         while(true) {

      513             while (b <= c && x[b] <= v) {

      514                 if (x[b] == v)

      515                     swap(x, a++, b);

      516                 b++;

      517             }

      518             while (c >= b && x[c] >= v) {

      519                 if (x[c] == v)

      520                     swap(x, c, d--);

      521                 c--;

      522             }

      523             if (b > c)

      524                 break;

      525             swap(x, b++, c--);

      526         }

      527 

      528         // Swap partition elements back to middle

      529         int s, n = off + len;

      530         s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);

      531         s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

      532 

      533         // Recursively sort non-partition-elements

      534         if ((s = b-a) > 1)

      535             sort1(x, off, s);

      536         if ((s = d-c) > 1)

      537             sort1(x, n-s, s);

      538     }

      539 

      540     /**

      541      * Swaps x[a] with x[b].

      542      */

      543     private static void swap(long x[], int a, int b) {

      544         long t = x[a];

      545         x[a] = x[b];

      546         x[b] = t;

      547     }

      548 

      549     /**

      550      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].

      551      */

      552     private static void vecswap(long x[], int a, int b, int n) {

      553         for (int i=0; i<n; i++, a++, b++)

      554             swap(x, a, b);

      555     }

      556 

      557     /**

      558      * Returns the index of the median of the three indexed longs.

      559      */

      560     private static int med3(long x[], int a, int b, int c) {

      561         return (x[a] < x[b] ?

      562                 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :

      563                 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));

      564     }

      565 

      566     /**

      567      * Sorts the specified sub-array of integers into ascending order.

      568      */

      569     private static void sort1(int x[], int off, int len) {

      570         // Insertion sort on smallest arrays

      571         if (len < 7) {

      572             for (int i=off; i<len+off; i++)

      573                 for (int j=i; j>off && x[j-1]>x[j]; j--)

      574                     swap(x, j, j-1);

      575             return;

      576         }

      577 

      578         // Choose a partition element, v

      579         int m = off + (len >> 1);       // Small arrays, middle element

      580         if (len > 7) {

      581             int l = off;

      582             int n = off + len - 1;

      583             if (len > 40) {        // Big arrays, pseudomedian of 9

      584                 int s = len/8;

      585                 l = med3(x, l,     l+s, l+2*s);

      586                 m = med3(x, m-s,   m,   m+s);

      587                 n = med3(x, n-2*s, n-s, n);

      588             }

      589             m = med3(x, l, m, n); // Mid-size, med of 3

      590         }

      591         int v = x[m];

      592 

      593         // Establish Invariant: v* (<v)* (>v)* v*

      594         int a = off, b = a, c = off + len - 1, d = c;

      595         while(true) {

      596             while (b <= c && x[b] <= v) {

      597                 if (x[b] == v)

      598                     swap(x, a++, b);

      599                 b++;

      600             }

      601             while (c >= b && x[c] >= v) {

      602                 if (x[c] == v)

      603                     swap(x, c, d--);

      604                 c--;

      605             }

      606             if (b > c)

      607                 break;

      608             swap(x, b++, c--);

      609         }

      610 

      611         // Swap partition elements back to middle

      612         int s, n = off + len;

      613         s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);

      614         s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

      615 

      616         // Recursively sort non-partition-elements

      617         if ((s = b-a) > 1)

      618             sort1(x, off, s);

      619         if ((s = d-c) > 1)

      620             sort1(x, n-s, s);

      621     }

      622 

      623     /**

      624      * Swaps x[a] with x[b].

      625      */

      626     private static void swap(int x[], int a, int b) {

      627         int t = x[a];

      628         x[a] = x[b];

      629         x[b] = t;

      630     }

      631 

      632     /**

      633      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].

      634      */

      635     private static void vecswap(int x[], int a, int b, int n) {

      636         for (int i=0; i<n; i++, a++, b++)

      637             swap(x, a, b);

      638     }

      639 

      640     /**

      641      * Returns the index of the median of the three indexed integers.

      642      */

      643     private static int med3(int x[], int a, int b, int c) {

      644         return (x[a] < x[b] ?

      645                 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :

      646                 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));

      647     }

      648 

      649     /**

      650      * Sorts the specified sub-array of shorts into ascending order.

      651      */

      652     private static void sort1(short x[], int off, int len) {

      653         // Insertion sort on smallest arrays

      654         if (len < 7) {

      655             for (int i=off; i<len+off; i++)

      656                 for (int j=i; j>off && x[j-1]>x[j]; j--)

      657                     swap(x, j, j-1);

      658             return;

      659         }

      660 

      661         // Choose a partition element, v

      662         int m = off + (len >> 1);       // Small arrays, middle element

      663         if (len > 7) {

      664             int l = off;

      665             int n = off + len - 1;

      666             if (len > 40) {        // Big arrays, pseudomedian of 9

      667                 int s = len/8;

      668                 l = med3(x, l,     l+s, l+2*s);

      669                 m = med3(x, m-s,   m,   m+s);

      670                 n = med3(x, n-2*s, n-s, n);

      671             }

      672             m = med3(x, l, m, n); // Mid-size, med of 3

      673         }

      674         short v = x[m];

      675 

      676         // Establish Invariant: v* (<v)* (>v)* v*

      677         int a = off, b = a, c = off + len - 1, d = c;

      678         while(true) {

      679             while (b <= c && x[b] <= v) {

      680                 if (x[b] == v)

      681                     swap(x, a++, b);

      682                 b++;

      683             }

      684             while (c >= b && x[c] >= v) {

      685                 if (x[c] == v)

      686                     swap(x, c, d--);

      687                 c--;

      688             }

      689             if (b > c)

      690                 break;

      691             swap(x, b++, c--);

      692         }

      693 

      694         // Swap partition elements back to middle

      695         int s, n = off + len;

      696         s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);

      697         s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

      698 

      699         // Recursively sort non-partition-elements

      700         if ((s = b-a) > 1)

      701             sort1(x, off, s);

      702         if ((s = d-c) > 1)

      703             sort1(x, n-s, s);

      704     }

      705 

      706     /**

      707      * Swaps x[a] with x[b].

      708      */

      709     private static void swap(short x[], int a, int b) {

      710         short t = x[a];

      711         x[a] = x[b];

      712         x[b] = t;

      713     }

      714 

      715     /**

      716      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].

      717      */

      718     private static void vecswap(short x[], int a, int b, int n) {

      719         for (int i=0; i<n; i++, a++, b++)

      720             swap(x, a, b);

      721     }

      722 

      723     /**

      724      * Returns the index of the median of the three indexed shorts.

      725      */

      726     private static int med3(short x[], int a, int b, int c) {

      727         return (x[a] < x[b] ?

      728                 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :

      729                 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));

      730     }

      731 

      732 

      733     /**

      734      * Sorts the specified sub-array of chars into ascending order.

      735      */

      736     private static void sort1(char x[], int off, int len) {

      737         // Insertion sort on smallest arrays

      738         if (len < 7) {

      739             for (int i=off; i<len+off; i++)

      740                 for (int j=i; j>off && x[j-1]>x[j]; j--)

      741                     swap(x, j, j-1);

      742             return;

      743         }

      744 

      745         // Choose a partition element, v

      746         int m = off + (len >> 1);       // Small arrays, middle element

      747         if (len > 7) {

      748             int l = off;

      749             int n = off + len - 1;

      750             if (len > 40) {        // Big arrays, pseudomedian of 9

      751                 int s = len/8;

      752                 l = med3(x, l,     l+s, l+2*s);

      753                 m = med3(x, m-s,   m,   m+s);

      754                 n = med3(x, n-2*s, n-s, n);

      755             }

      756             m = med3(x, l, m, n); // Mid-size, med of 3

      757         }

      758         char v = x[m];

      759 

      760         // Establish Invariant: v* (<v)* (>v)* v*

      761         int a = off, b = a, c = off + len - 1, d = c;

      762         while(true) {

      763             while (b <= c && x[b] <= v) {

      764                 if (x[b] == v)

      765                     swap(x, a++, b);

      766                 b++;

      767             }

      768             while (c >= b && x[c] >= v) {

      769                 if (x[c] == v)

      770                     swap(x, c, d--);

      771                 c--;

      772             }

      773             if (b > c)

      774                 break;

      775             swap(x, b++, c--);

      776         }

      777 

      778         // Swap partition elements back to middle

      779         int s, n = off + len;

      780         s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);

      781         s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

      782 

      783         // Recursively sort non-partition-elements

      784         if ((s = b-a) > 1)

      785             sort1(x, off, s);

      786         if ((s = d-c) > 1)

      787             sort1(x, n-s, s);

      788     }

      789 

      790     /**

      791      * Swaps x[a] with x[b].

      792      */

      793     private static void swap(char x[], int a, int b) {

      794         char t = x[a];

      795         x[a] = x[b];

      796         x[b] = t;

      797     }

      798 

      799     /**

      800      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].

      801      */

      802     private static void vecswap(char x[], int a, int b, int n) {

      803         for (int i=0; i<n; i++, a++, b++)

      804             swap(x, a, b);

      805     }

      806 

      807     /**

      808      * Returns the index of the median of the three indexed chars.

      809      */

      810     private static int med3(char x[], int a, int b, int c) {

      811         return (x[a] < x[b] ?

      812                 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :

      813                 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));

      814     }

      815 

      816 

      817     /**

      818      * Sorts the specified sub-array of bytes into ascending order.

      819      */

      820     private static void sort1(byte x[], int off, int len) {

      821         // Insertion sort on smallest arrays

      822         if (len < 7) {

      823             for (int i=off; i<len+off; i++)

      824                 for (int j=i; j>off && x[j-1]>x[j]; j--)

      825                     swap(x, j, j-1);

      826             return;

      827         }

      828 

      829         // Choose a partition element, v

      830         int m = off + (len >> 1);       // Small arrays, middle element

      831         if (len > 7) {

      832             int l = off;

      833             int n = off + len - 1;

      834             if (len > 40) {        // Big arrays, pseudomedian of 9

      835                 int s = len/8;

      836                 l = med3(x, l,     l+s, l+2*s);

      837                 m = med3(x, m-s,   m,   m+s);

      838                 n = med3(x, n-2*s, n-s, n);

      839             }

      840             m = med3(x, l, m, n); // Mid-size, med of 3

      841         }

      842         byte v = x[m];

      843 

      844         // Establish Invariant: v* (<v)* (>v)* v*

      845         int a = off, b = a, c = off + len - 1, d = c;

      846         while(true) {

      847             while (b <= c && x[b] <= v) {

      848                 if (x[b] == v)

      849                     swap(x, a++, b);

      850                 b++;

      851             }

      852             while (c >= b && x[c] >= v) {

      853                 if (x[c] == v)

      854                     swap(x, c, d--);

      855                 c--;

      856             }

      857             if (b > c)

      858                 break;

      859             swap(x, b++, c--);

      860         }

      861 

      862         // Swap partition elements back to middle

      863         int s, n = off + len;

      864         s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);

      865         s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

      866 

      867         // Recursively sort non-partition-elements

      868         if ((s = b-a) > 1)

      869             sort1(x, off, s);

      870         if ((s = d-c) > 1)

      871             sort1(x, n-s, s);

      872     }

      873 

      874     /**

      875      * Swaps x[a] with x[b].

      876      */

      877     private static void swap(byte x[], int a, int b) {

      878         byte t = x[a];

      879         x[a] = x[b];

      880         x[b] = t;

      881     }

      882 

      883     /**

      884      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].

      885      */

      886     private static void vecswap(byte x[], int a, int b, int n) {

      887         for (int i=0; i<n; i++, a++, b++)

      888             swap(x, a, b);

      889     }

      890 

      891     /**

      892      * Returns the index of the median of the three indexed bytes.

      893      */

      894     private static int med3(byte x[], int a, int b, int c) {

      895         return (x[a] < x[b] ?

      896                 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :

      897                 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));

      898     }

      899 

      900 

      901     /**

      902      * Sorts the specified sub-array of doubles into ascending order.

      903      */

      904     private static void sort1(double x[], int off, int len) {

      905         // Insertion sort on smallest arrays

      906         if (len < 7) {

      907             for (int i=off; i<len+off; i++)

      908                 for (int j=i; j>off && x[j-1]>x[j]; j--)

      909                     swap(x, j, j-1);

      910             return;

      911         }

      912 

      913         // Choose a partition element, v

      914         int m = off + (len >> 1);       // Small arrays, middle element

      915         if (len > 7) {

      916             int l = off;

      917             int n = off + len - 1;

      918             if (len > 40) {        // Big arrays, pseudomedian of 9

      919                 int s = len/8;

      920                 l = med3(x, l,     l+s, l+2*s);

      921                 m = med3(x, m-s,   m,   m+s);

      922                 n = med3(x, n-2*s, n-s, n);

      923             }

      924             m = med3(x, l, m, n); // Mid-size, med of 3

      925         }

      926         double v = x[m];

      927 

      928         // Establish Invariant: v* (<v)* (>v)* v*

      929         int a = off, b = a, c = off + len - 1, d = c;

      930         while(true) {

      931             while (b <= c && x[b] <= v) {

      932                 if (x[b] == v)

      933                     swap(x, a++, b);

      934                 b++;

      935             }

      936             while (c >= b && x[c] >= v) {

      937                 if (x[c] == v)

      938                     swap(x, c, d--);

      939                 c--;

      940             }

      941             if (b > c)

      942                 break;

      943             swap(x, b++, c--);

      944         }

      945 

      946         // Swap partition elements back to middle

      947         int s, n = off + len;

      948         s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);

      949         s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

      950 

      951         // Recursively sort non-partition-elements

      952         if ((s = b-a) > 1)

      953             sort1(x, off, s);

      954         if ((s = d-c) > 1)

      955             sort1(x, n-s, s);

      956     }

      957 

      958     /**

      959      * Swaps x[a] with x[b].

      960      */

      961     private static void swap(double x[], int a, int b) {

      962         double t = x[a];

      963         x[a] = x[b];

      964         x[b] = t;

      965     }

      966 

      967     /**

      968      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].

      969      */

      970     private static void vecswap(double x[], int a, int b, int n) {

      971         for (int i=0; i<n; i++, a++, b++)

      972             swap(x, a, b);

      973     }

      974 

      975     /**

      976      * Returns the index of the median of the three indexed doubles.

      977      */

      978     private static int med3(double x[], int a, int b, int c) {

      979         return (x[a] < x[b] ?

      980                 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :

      981                 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));

      982     }

      983 

      984 

      985     /**

      986      * Sorts the specified sub-array of floats into ascending order.

      987      */

      988     private static void sort1(float x[], int off, int len) {

      989         // Insertion sort on smallest arrays

      990         if (len < 7) {

      991             for (int i=off; i<len+off; i++)

      992                 for (int j=i; j>off && x[j-1]>x[j]; j--)

      993                     swap(x, j, j-1);

      994             return;

      995         }

      996 

      997         // Choose a partition element, v

      998         int m = off + (len >> 1);       // Small arrays, middle element

      999         if (len > 7) {

     1000             int l = off;

     1001             int n = off + len - 1;

     1002             if (len > 40) {        // Big arrays, pseudomedian of 9

     1003                 int s = len/8;

     1004                 l = med3(x, l,     l+s, l+2*s);

     1005                 m = med3(x, m-s,   m,   m+s);

     1006                 n = med3(x, n-2*s, n-s, n);

     1007             }

     1008             m = med3(x, l, m, n); // Mid-size, med of 3

     1009         }

     1010         float v = x[m];

     1011 

     1012         // Establish Invariant: v* (<v)* (>v)* v*

     1013         int a = off, b = a, c = off + len - 1, d = c;

     1014         while(true) {

     1015             while (b <= c && x[b] <= v) {

     1016                 if (x[b] == v)

     1017                     swap(x, a++, b);

     1018                 b++;

     1019             }

     1020             while (c >= b && x[c] >= v) {

     1021                 if (x[c] == v)

     1022                     swap(x, c, d--);

     1023                 c--;

     1024             }

     1025             if (b > c)

     1026                 break;

     1027             swap(x, b++, c--);

     1028         }

     1029 

     1030         // Swap partition elements back to middle

     1031         int s, n = off + len;

     1032         s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);

     1033         s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);

     1034 

     1035         // Recursively sort non-partition-elements

     1036         if ((s = b-a) > 1)

     1037             sort1(x, off, s);

     1038         if ((s = d-c) > 1)

     1039             sort1(x, n-s, s);

     1040     }

     1041 

     1042     /**

     1043      * Swaps x[a] with x[b].

     1044      */

     1045     private static void swap(float x[], int a, int b) {

     1046         float t = x[a];

     1047         x[a] = x[b];

     1048         x[b] = t;

     1049     }

     1050 

     1051     /**

     1052      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].

     1053      */

     1054     private static void vecswap(float x[], int a, int b, int n) {

     1055         for (int i=0; i<n; i++, a++, b++)

     1056             swap(x, a, b);

     1057     }

     1058 

     1059     /**

     1060      * Returns the index of the median of the three indexed floats.

     1061      */

     1062     private static int med3(float x[], int a, int b, int c) {

     1063         return (x[a] < x[b] ?

     1064                 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :

     1065                 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));

     1066     }

     1067 

     1068 

     1069     /**

     1070      * Sorts the specified array of objects into ascending order, according to

     1071      * the {@linkplain Comparable natural ordering}

     1072      * of its elements.  All elements in the array

     1073      * must implement the {@link Comparable} interface.  Furthermore, all

     1074      * elements in the array must be <i>mutually comparable</i> (that is,

     1075      * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>

     1076      * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>

     1077      *

     1078      * This sort is guaranteed to be <i>stable</i>:  equal elements will

     1079      * not be reordered as a result of the sort.<p>

     1080      *

     1081      * The sorting algorithm is a modified mergesort (in which the merge is

     1082      * omitted if the highest element in the low sublist is less than the

     1083      * lowest element in the high sublist).  This algorithm offers guaranteed

     1084      * n*log(n) performance.

     1085      *

     1086      * @param a the array to be sorted

     1087      * @throws  ClassCastException if the array contains elements that are not

     1088      *          <i>mutually comparable</i> (for example, strings and integers).

     1089      */

     1090     public static void sort(Object[] a) {

     1091         Object[] aux = (Object[])a.clone();

     1092         mergeSort(aux, a, 0, a.length, 0);

     1093     }

     1094 

     1095     /**

     1096      * Sorts the specified range of the specified array of objects into

     1097      * ascending order, according to the

     1098      * {@linkplain Comparable natural ordering} of its

     1099      * elements.  The range to be sorted extends from index

     1100      * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.

     1101      * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)  All

     1102      * elements in this range must implement the {@link Comparable}

     1103      * interface.  Furthermore, all elements in this range must be <i>mutually

     1104      * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a

     1105      * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and

     1106      * <tt>e2</tt> in the array).<p>

     1107      *

     1108      * This sort is guaranteed to be <i>stable</i>:  equal elements will

     1109      * not be reordered as a result of the sort.<p>

     1110      *

     1111      * The sorting algorithm is a modified mergesort (in which the merge is

     1112      * omitted if the highest element in the low sublist is less than the

     1113      * lowest element in the high sublist).  This algorithm offers guaranteed

     1114      * n*log(n) performance.

     1115      *

     1116      * @param a the array to be sorted

     1117      * @param fromIndex the index of the first element (inclusive) to be

     1118      *        sorted

     1119      * @param toIndex the index of the last element (exclusive) to be sorted

     1120      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

     1121      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

     1122      *         <tt>toIndex &gt; a.length</tt>

     1123      * @throws    ClassCastException if the array contains elements that are

     1124      *            not <i>mutually comparable</i> (for example, strings and

     1125      *            integers).

     1126      */

     1127     public static void sort(Object[] a, int fromIndex, int toIndex) {

     1128         rangeCheck(a.length, fromIndex, toIndex);

     1129         Object[] aux = copyOfRange(a, fromIndex, toIndex);

     1130         mergeSort(aux, a, fromIndex, toIndex, -fromIndex);

     1131     }

     1132 

     1133     /**

     1134      * Tuning parameter: list size at or below which insertion sort will be

     1135      * used in preference to mergesort or quicksort.

     1136      */

     1137     private static final int INSERTIONSORT_THRESHOLD = 7;

     1138 

     1139     /**

     1140      * Src is the source array that starts at index 0

     1141      * Dest is the (possibly larger) array destination with a possible offset

     1142      * low is the index in dest to start sorting

     1143      * high is the end index in dest to end sorting

     1144      * off is the offset to generate corresponding low, high in src

     1145      */

     1146     private static void mergeSort(Object[] src,

     1147                                   Object[] dest,

     1148                                   int low,

     1149                                   int high,

     1150                                   int off) {

     1151         int length = high - low;

     1152 

     1153         // Insertion sort on smallest arrays

     1154         if (length < INSERTIONSORT_THRESHOLD) {

     1155             for (int i=low; i<high; i++)

     1156                 for (int j=i; j>low &&

     1157                          ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)

     1158                     swap(dest, j, j-1);

     1159             return;

     1160         }

     1161 

     1162         // Recursively sort halves of dest into src

     1163         int destLow  = low;

     1164         int destHigh = high;

     1165         low  += off;

     1166         high += off;

     1167         int mid = (low + high) >>> 1;

     1168         mergeSort(dest, src, low, mid, -off);

     1169         mergeSort(dest, src, mid, high, -off);

     1170 

     1171         // If list is already sorted, just copy from src to dest.  This is an

     1172         // optimization that results in faster sorts for nearly ordered lists.

     1173         if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {

     1174             System.arraycopy(src, low, dest, destLow, length);

     1175             return;

     1176         }

     1177 

     1178         // Merge sorted halves (now in src) into dest

     1179         for(int i = destLow, p = low, q = mid; i < destHigh; i++) {

     1180             if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)

     1181                 dest[i] = src[p++];

     1182             else

     1183                 dest[i] = src[q++];

     1184         }

     1185     }

     1186 

     1187     /**

     1188      * Swaps x[a] with x[b].

     1189      */

     1190     private static void swap(Object[] x, int a, int b) {

     1191         Object t = x[a];

     1192         x[a] = x[b];

     1193         x[b] = t;

     1194     }

     1195 

     1196     /**

     1197      * Sorts the specified array of objects according to the order induced by

     1198      * the specified comparator.  All elements in the array must be

     1199      * <i>mutually comparable</i> by the specified comparator (that is,

     1200      * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>

     1201      * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>

     1202      *

     1203      * This sort is guaranteed to be <i>stable</i>:  equal elements will

     1204      * not be reordered as a result of the sort.<p>

     1205      *

     1206      * The sorting algorithm is a modified mergesort (in which the merge is

     1207      * omitted if the highest element in the low sublist is less than the

     1208      * lowest element in the high sublist).  This algorithm offers guaranteed

     1209      * n*log(n) performance.

     1210      *

     1211      * @param a the array to be sorted

     1212      * @param c the comparator to determine the order of the array.  A

     1213      *        <tt>null</tt> value indicates that the elements'

     1214      *        {@linkplain Comparable natural ordering} should be used.

     1215      * @throws  ClassCastException if the array contains elements that are

     1216      *          not <i>mutually comparable</i> using the specified comparator.

     1217      */

     1218     public static <T> void sort(T[] a, Comparator<? super T> c) {

     1219         T[] aux = (T[])a.clone();

     1220         if (c==null)

     1221             mergeSort(aux, a, 0, a.length, 0);

     1222         else

     1223             mergeSort(aux, a, 0, a.length, 0, c);

     1224     }

     1225 

     1226     /**

     1227      * Sorts the specified range of the specified array of objects according

     1228      * to the order induced by the specified comparator.  The range to be

     1229      * sorted extends from index <tt>fromIndex</tt>, inclusive, to index

     1230      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the

     1231      * range to be sorted is empty.)  All elements in the range must be

     1232      * <i>mutually comparable</i> by the specified comparator (that is,

     1233      * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>

     1234      * for any elements <tt>e1</tt> and <tt>e2</tt> in the range).<p>

     1235      *

     1236      * This sort is guaranteed to be <i>stable</i>:  equal elements will

     1237      * not be reordered as a result of the sort.<p>

     1238      *

     1239      * The sorting algorithm is a modified mergesort (in which the merge is

     1240      * omitted if the highest element in the low sublist is less than the

     1241      * lowest element in the high sublist).  This algorithm offers guaranteed

     1242      * n*log(n) performance.

     1243      *

     1244      * @param a the array to be sorted

     1245      * @param fromIndex the index of the first element (inclusive) to be

     1246      *        sorted

     1247      * @param toIndex the index of the last element (exclusive) to be sorted

     1248      * @param c the comparator to determine the order of the array.  A

     1249      *        <tt>null</tt> value indicates that the elements'

     1250      *        {@linkplain Comparable natural ordering} should be used.

     1251      * @throws ClassCastException if the array contains elements that are not

     1252      *         <i>mutually comparable</i> using the specified comparator.

     1253      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

     1254      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

     1255      *         <tt>toIndex &gt; a.length</tt>

     1256      */

     1257     public static <T> void sort(T[] a, int fromIndex, int toIndex,

     1258                                 Comparator<? super T> c) {

     1259         rangeCheck(a.length, fromIndex, toIndex);

     1260         T[] aux = (T[])copyOfRange(a, fromIndex, toIndex);

     1261         if (c==null)

     1262             mergeSort(aux, a, fromIndex, toIndex, -fromIndex);

     1263         else

     1264             mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);

     1265     }

     1266 

     1267     /**

     1268      * Src is the source array that starts at index 0

     1269      * Dest is the (possibly larger) array destination with a possible offset

     1270      * low is the index in dest to start sorting

     1271      * high is the end index in dest to end sorting

     1272      * off is the offset into src corresponding to low in dest

     1273      */

     1274     private static void mergeSort(Object[] src,

     1275                                   Object[] dest,

     1276                                   int low, int high, int off,

     1277                                   Comparator c) {

     1278         int length = high - low;

     1279 

     1280         // Insertion sort on smallest arrays

     1281         if (length < INSERTIONSORT_THRESHOLD) {

     1282             for (int i=low; i<high; i++)

     1283                 for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)

     1284                     swap(dest, j, j-1);

     1285             return;

     1286         }

     1287 

     1288         // Recursively sort halves of dest into src

     1289         int destLow  = low;

     1290         int destHigh = high;

     1291         low  += off;

     1292         high += off;

     1293         int mid = (low + high) >>> 1;

     1294         mergeSort(dest, src, low, mid, -off, c);

     1295         mergeSort(dest, src, mid, high, -off, c);

     1296 

     1297         // If list is already sorted, just copy from src to dest.  This is an

     1298         // optimization that results in faster sorts for nearly ordered lists.

     1299         if (c.compare(src[mid-1], src[mid]) <= 0) {

     1300            System.arraycopy(src, low, dest, destLow, length);

     1301            return;

     1302         }

     1303 

     1304         // Merge sorted halves (now in src) into dest

     1305         for(int i = destLow, p = low, q = mid; i < destHigh; i++) {

     1306             if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)

     1307                 dest[i] = src[p++];

     1308             else

     1309                 dest[i] = src[q++];

     1310         }

     1311     }

     1312 

     1313     /**

     1314      * Check that fromIndex and toIndex are in range, and throw an

     1315      * appropriate exception if they aren't.

     1316      */

     1317     private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {

     1318         if (fromIndex > toIndex)

     1319             throw new IllegalArgumentException("fromIndex(" + fromIndex +

     1320                        ") > toIndex(" + toIndex+")");

     1321         if (fromIndex < 0)

     1322             throw new ArrayIndexOutOfBoundsException(fromIndex);

     1323         if (toIndex > arrayLen)

     1324             throw new ArrayIndexOutOfBoundsException(toIndex);

     1325     }

     1326 

     1327     // Searching

     1328 

     1329     /**

     1330      * Searches the specified array of longs for the specified value using the

     1331      * binary search algorithm.  The array must be sorted (as

     1332      * by the {@link #sort(long[])} method) prior to making this call.  If it

     1333      * is not sorted, the results are undefined.  If the array contains

     1334      * multiple elements with the specified value, there is no guarantee which

     1335      * one will be found.

     1336      *

     1337      * @param a the array to be searched

     1338      * @param key the value to be searched for

     1339      * @return index of the search key, if it is contained in the array;

     1340      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1341      *         <i>insertion point</i> is defined as the point at which the

     1342      *         key would be inserted into the array: the index of the first

     1343      *         element greater than the key, or <tt>a.length</tt> if all

     1344      *         elements in the array are less than the specified key.  Note

     1345      *         that this guarantees that the return value will be >= 0 if

     1346      *         and only if the key is found.

     1347      */

     1348     public static int binarySearch(long[] a, long key) {

     1349         return binarySearch0(a, 0, a.length, key);

     1350     }

     1351 

     1352     /**

     1353      * Searches a range of

     1354      * the specified array of longs for the specified value using the

     1355      * binary search algorithm.

     1356      * The range must be sorted (as

     1357      * by the {@link #sort(long[], int, int)} method)

     1358      * prior to making this call.  If it

     1359      * is not sorted, the results are undefined.  If the range contains

     1360      * multiple elements with the specified value, there is no guarantee which

     1361      * one will be found.

     1362      *

     1363      * @param a the array to be searched

     1364      * @param fromIndex the index of the first element (inclusive) to be

     1365      *          searched

     1366      * @param toIndex the index of the last element (exclusive) to be searched

     1367      * @param key the value to be searched for

     1368      * @return index of the search key, if it is contained in the array

     1369      *         within the specified range;

     1370      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1371      *         <i>insertion point</i> is defined as the point at which the

     1372      *         key would be inserted into the array: the index of the first

     1373      *         element in the range greater than the key,

     1374      *         or <tt>toIndex</tt> if all

     1375      *         elements in the range are less than the specified key.  Note

     1376      *         that this guarantees that the return value will be >= 0 if

     1377      *         and only if the key is found.

     1378      * @throws IllegalArgumentException

     1379      *         if {@code fromIndex > toIndex}

     1380      * @throws ArrayIndexOutOfBoundsException

     1381      *         if {@code fromIndex < 0 or toIndex > a.length}

     1382      * @since 1.6

     1383      */

     1384     public static int binarySearch(long[] a, int fromIndex, int toIndex,

     1385                                    long key) {

     1386         rangeCheck(a.length, fromIndex, toIndex);

     1387         return binarySearch0(a, fromIndex, toIndex, key);

     1388     }

     1389 

     1390     // Like public version, but without range checks.

     1391     private static int binarySearch0(long[] a, int fromIndex, int toIndex,

     1392                                      long key) {

     1393         int low = fromIndex;

     1394         int high = toIndex - 1;

     1395 

     1396         while (low <= high) {

     1397             int mid = (low + high) >>> 1;

     1398             long midVal = a[mid];

     1399 

     1400             if (midVal < key)

     1401                 low = mid + 1;

     1402             else if (midVal > key)

     1403                 high = mid - 1;

     1404             else

     1405                 return mid; // key found

     1406         }

     1407         return -(low + 1);  // key not found.

     1408     }

     1409 

     1410     /**

     1411      * Searches the specified array of ints for the specified value using the

     1412      * binary search algorithm.  The array must be sorted (as

     1413      * by the {@link #sort(int[])} method) prior to making this call.  If it

     1414      * is not sorted, the results are undefined.  If the array contains

     1415      * multiple elements with the specified value, there is no guarantee which

     1416      * one will be found.

     1417      *

     1418      * @param a the array to be searched

     1419      * @param key the value to be searched for

     1420      * @return index of the search key, if it is contained in the array;

     1421      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1422      *         <i>insertion point</i> is defined as the point at which the

     1423      *         key would be inserted into the array: the index of the first

     1424      *         element greater than the key, or <tt>a.length</tt> if all

     1425      *         elements in the array are less than the specified key.  Note

     1426      *         that this guarantees that the return value will be >= 0 if

     1427      *         and only if the key is found.

     1428      */

     1429     public static int binarySearch(int[] a, int key) {

     1430         return binarySearch0(a, 0, a.length, key);

     1431     }

     1432 

     1433     /**

     1434      * Searches a range of

     1435      * the specified array of ints for the specified value using the

     1436      * binary search algorithm.

     1437      * The range must be sorted (as

     1438      * by the {@link #sort(int[], int, int)} method)

     1439      * prior to making this call.  If it

     1440      * is not sorted, the results are undefined.  If the range contains

     1441      * multiple elements with the specified value, there is no guarantee which

     1442      * one will be found.

     1443      *

     1444      * @param a the array to be searched

     1445      * @param fromIndex the index of the first element (inclusive) to be

     1446      *          searched

     1447      * @param toIndex the index of the last element (exclusive) to be searched

     1448      * @param key the value to be searched for

     1449      * @return index of the search key, if it is contained in the array

     1450      *         within the specified range;

     1451      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1452      *         <i>insertion point</i> is defined as the point at which the

     1453      *         key would be inserted into the array: the index of the first

     1454      *         element in the range greater than the key,

     1455      *         or <tt>toIndex</tt> if all

     1456      *         elements in the range are less than the specified key.  Note

     1457      *         that this guarantees that the return value will be >= 0 if

     1458      *         and only if the key is found.

     1459      * @throws IllegalArgumentException

     1460      *         if {@code fromIndex > toIndex}

     1461      * @throws ArrayIndexOutOfBoundsException

     1462      *         if {@code fromIndex < 0 or toIndex > a.length}

     1463      * @since 1.6

     1464      */

     1465     public static int binarySearch(int[] a, int fromIndex, int toIndex,

     1466                                    int key) {

     1467         rangeCheck(a.length, fromIndex, toIndex);

     1468         return binarySearch0(a, fromIndex, toIndex, key);

     1469     }

     1470 

     1471     // Like public version, but without range checks.

     1472     private static int binarySearch0(int[] a, int fromIndex, int toIndex,

     1473                                      int key) {

     1474         int low = fromIndex;

     1475         int high = toIndex - 1;

     1476 

     1477         while (low <= high) {

     1478             int mid = (low + high) >>> 1;

     1479             int midVal = a[mid];

     1480 

     1481             if (midVal < key)

     1482                 low = mid + 1;

     1483             else if (midVal > key)

     1484                 high = mid - 1;

     1485             else

     1486                 return mid; // key found

     1487         }

     1488         return -(low + 1);  // key not found.

     1489     }

     1490 

     1491     /**

     1492      * Searches the specified array of shorts for the specified value using

     1493      * the binary search algorithm.  The array must be sorted

     1494      * (as by the {@link #sort(short[])} method) prior to making this call.  If

     1495      * it is not sorted, the results are undefined.  If the array contains

     1496      * multiple elements with the specified value, there is no guarantee which

     1497      * one will be found.

     1498      *

     1499      * @param a the array to be searched

     1500      * @param key the value to be searched for

     1501      * @return index of the search key, if it is contained in the array;

     1502      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1503      *         <i>insertion point</i> is defined as the point at which the

     1504      *         key would be inserted into the array: the index of the first

     1505      *         element greater than the key, or <tt>a.length</tt> if all

     1506      *         elements in the array are less than the specified key.  Note

     1507      *         that this guarantees that the return value will be >= 0 if

     1508      *         and only if the key is found.

     1509      */

     1510     public static int binarySearch(short[] a, short key) {

     1511         return binarySearch0(a, 0, a.length, key);

     1512     }

     1513 

     1514     /**

     1515      * Searches a range of

     1516      * the specified array of shorts for the specified value using

     1517      * the binary search algorithm.

     1518      * The range must be sorted

     1519      * (as by the {@link #sort(short[], int, int)} method)

     1520      * prior to making this call.  If

     1521      * it is not sorted, the results are undefined.  If the range contains

     1522      * multiple elements with the specified value, there is no guarantee which

     1523      * one will be found.

     1524      *

     1525      * @param a the array to be searched

     1526      * @param fromIndex the index of the first element (inclusive) to be

     1527      *          searched

     1528      * @param toIndex the index of the last element (exclusive) to be searched

     1529      * @param key the value to be searched for

     1530      * @return index of the search key, if it is contained in the array

     1531      *         within the specified range;

     1532      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1533      *         <i>insertion point</i> is defined as the point at which the

     1534      *         key would be inserted into the array: the index of the first

     1535      *         element in the range greater than the key,

     1536      *         or <tt>toIndex</tt> if all

     1537      *         elements in the range are less than the specified key.  Note

     1538      *         that this guarantees that the return value will be >= 0 if

     1539      *         and only if the key is found.

     1540      * @throws IllegalArgumentException

     1541      *         if {@code fromIndex > toIndex}

     1542      * @throws ArrayIndexOutOfBoundsException

     1543      *         if {@code fromIndex < 0 or toIndex > a.length}

     1544      * @since 1.6

     1545      */

     1546     public static int binarySearch(short[] a, int fromIndex, int toIndex,

     1547                                    short key) {

     1548         rangeCheck(a.length, fromIndex, toIndex);

     1549         return binarySearch0(a, fromIndex, toIndex, key);

     1550     }

     1551 

     1552     // Like public version, but without range checks.

     1553     private static int binarySearch0(short[] a, int fromIndex, int toIndex,

     1554                                      short key) {

     1555         int low = fromIndex;

     1556         int high = toIndex - 1;

     1557 

     1558         while (low <= high) {

     1559             int mid = (low + high) >>> 1;

     1560             short midVal = a[mid];

     1561 

     1562             if (midVal < key)

     1563                 low = mid + 1;

     1564             else if (midVal > key)

     1565                 high = mid - 1;

     1566             else

     1567                 return mid; // key found

     1568         }

     1569         return -(low + 1);  // key not found.

     1570     }

     1571 

     1572     /**

     1573      * Searches the specified array of chars for the specified value using the

     1574      * binary search algorithm.  The array must be sorted (as

     1575      * by the {@link #sort(char[])} method) prior to making this call.  If it

     1576      * is not sorted, the results are undefined.  If the array contains

     1577      * multiple elements with the specified value, there is no guarantee which

     1578      * one will be found.

     1579      *

     1580      * @param a the array to be searched

     1581      * @param key the value to be searched for

     1582      * @return index of the search key, if it is contained in the array;

     1583      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1584      *         <i>insertion point</i> is defined as the point at which the

     1585      *         key would be inserted into the array: the index of the first

     1586      *         element greater than the key, or <tt>a.length</tt> if all

     1587      *         elements in the array are less than the specified key.  Note

     1588      *         that this guarantees that the return value will be >= 0 if

     1589      *         and only if the key is found.

     1590      */

     1591     public static int binarySearch(char[] a, char key) {

     1592         return binarySearch0(a, 0, a.length, key);

     1593     }

     1594 

     1595     /**

     1596      * Searches a range of

     1597      * the specified array of chars for the specified value using the

     1598      * binary search algorithm.

     1599      * The range must be sorted (as

     1600      * by the {@link #sort(char[], int, int)} method)

     1601      * prior to making this call.  If it

     1602      * is not sorted, the results are undefined.  If the range contains

     1603      * multiple elements with the specified value, there is no guarantee which

     1604      * one will be found.

     1605      *

     1606      * @param a the array to be searched

     1607      * @param fromIndex the index of the first element (inclusive) to be

     1608      *          searched

     1609      * @param toIndex the index of the last element (exclusive) to be searched

     1610      * @param key the value to be searched for

     1611      * @return index of the search key, if it is contained in the array

     1612      *         within the specified range;

     1613      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1614      *         <i>insertion point</i> is defined as the point at which the

     1615      *         key would be inserted into the array: the index of the first

     1616      *         element in the range greater than the key,

     1617      *         or <tt>toIndex</tt> if all

     1618      *         elements in the range are less than the specified key.  Note

     1619      *         that this guarantees that the return value will be >= 0 if

     1620      *         and only if the key is found.

     1621      * @throws IllegalArgumentException

     1622      *         if {@code fromIndex > toIndex}

     1623      * @throws ArrayIndexOutOfBoundsException

     1624      *         if {@code fromIndex < 0 or toIndex > a.length}

     1625      * @since 1.6

     1626      */

     1627     public static int binarySearch(char[] a, int fromIndex, int toIndex,

     1628                                    char key) {

     1629         rangeCheck(a.length, fromIndex, toIndex);

     1630         return binarySearch0(a, fromIndex, toIndex, key);

     1631     }

     1632 

     1633     // Like public version, but without range checks.

     1634     private static int binarySearch0(char[] a, int fromIndex, int toIndex,

     1635                                      char key) {

     1636         int low = fromIndex;

     1637         int high = toIndex - 1;

     1638 

     1639         while (low <= high) {

     1640             int mid = (low + high) >>> 1;

     1641             char midVal = a[mid];

     1642 

     1643             if (midVal < key)

     1644                 low = mid + 1;

     1645             else if (midVal > key)

     1646                 high = mid - 1;

     1647             else

     1648                 return mid; // key found

     1649         }

     1650         return -(low + 1);  // key not found.

     1651     }

     1652 

     1653     /**

     1654      * Searches the specified array of bytes for the specified value using the

     1655      * binary search algorithm.  The array must be sorted (as

     1656      * by the {@link #sort(byte[])} method) prior to making this call.  If it

     1657      * is not sorted, the results are undefined.  If the array contains

     1658      * multiple elements with the specified value, there is no guarantee which

     1659      * one will be found.

     1660      *

     1661      * @param a the array to be searched

     1662      * @param key the value to be searched for

     1663      * @return index of the search key, if it is contained in the array;

     1664      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1665      *         <i>insertion point</i> is defined as the point at which the

     1666      *         key would be inserted into the array: the index of the first

     1667      *         element greater than the key, or <tt>a.length</tt> if all

     1668      *         elements in the array are less than the specified key.  Note

     1669      *         that this guarantees that the return value will be >= 0 if

     1670      *         and only if the key is found.

     1671      */

     1672     public static int binarySearch(byte[] a, byte key) {

     1673         return binarySearch0(a, 0, a.length, key);

     1674     }

     1675 

     1676     /**

     1677      * Searches a range of

     1678      * the specified array of bytes for the specified value using the

     1679      * binary search algorithm.

     1680      * The range must be sorted (as

     1681      * by the {@link #sort(byte[], int, int)} method)

     1682      * prior to making this call.  If it

     1683      * is not sorted, the results are undefined.  If the range contains

     1684      * multiple elements with the specified value, there is no guarantee which

     1685      * one will be found.

     1686      *

     1687      * @param a the array to be searched

     1688      * @param fromIndex the index of the first element (inclusive) to be

     1689      *          searched

     1690      * @param toIndex the index of the last element (exclusive) to be searched

     1691      * @param key the value to be searched for

     1692      * @return index of the search key, if it is contained in the array

     1693      *         within the specified range;

     1694      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1695      *         <i>insertion point</i> is defined as the point at which the

     1696      *         key would be inserted into the array: the index of the first

     1697      *         element in the range greater than the key,

     1698      *         or <tt>toIndex</tt> if all

     1699      *         elements in the range are less than the specified key.  Note

     1700      *         that this guarantees that the return value will be >= 0 if

     1701      *         and only if the key is found.

     1702      * @throws IllegalArgumentException

     1703      *         if {@code fromIndex > toIndex}

     1704      * @throws ArrayIndexOutOfBoundsException

     1705      *         if {@code fromIndex < 0 or toIndex > a.length}

     1706      * @since 1.6

     1707      */

     1708     public static int binarySearch(byte[] a, int fromIndex, int toIndex,

     1709                                    byte key) {

     1710         rangeCheck(a.length, fromIndex, toIndex);

     1711         return binarySearch0(a, fromIndex, toIndex, key);

     1712     }

     1713 

     1714     // Like public version, but without range checks.

     1715     private static int binarySearch0(byte[] a, int fromIndex, int toIndex,

     1716                                      byte key) {

     1717         int low = fromIndex;

     1718         int high = toIndex - 1;

     1719 

     1720         while (low <= high) {

     1721             int mid = (low + high) >>> 1;

     1722             byte midVal = a[mid];

     1723 

     1724             if (midVal < key)

     1725                 low = mid + 1;

     1726             else if (midVal > key)

     1727                 high = mid - 1;

     1728             else

     1729                 return mid; // key found

     1730         }

     1731         return -(low + 1);  // key not found.

     1732     }

     1733 

     1734     /**

     1735      * Searches the specified array of doubles for the specified value using

     1736      * the binary search algorithm.  The array must be sorted

     1737      * (as by the {@link #sort(double[])} method) prior to making this call.

     1738      * If it is not sorted, the results are undefined.  If the array contains

     1739      * multiple elements with the specified value, there is no guarantee which

     1740      * one will be found.  This method considers all NaN values to be

     1741      * equivalent and equal.

     1742      *

     1743      * @param a the array to be searched

     1744      * @param key the value to be searched for

     1745      * @return index of the search key, if it is contained in the array;

     1746      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1747      *         <i>insertion point</i> is defined as the point at which the

     1748      *         key would be inserted into the array: the index of the first

     1749      *         element greater than the key, or <tt>a.length</tt> if all

     1750      *         elements in the array are less than the specified key.  Note

     1751      *         that this guarantees that the return value will be >= 0 if

     1752      *         and only if the key is found.

     1753      */

     1754     public static int binarySearch(double[] a, double key) {

     1755         return binarySearch0(a, 0, a.length, key);

     1756     }

     1757 

     1758     /**

     1759      * Searches a range of

     1760      * the specified array of doubles for the specified value using

     1761      * the binary search algorithm.

     1762      * The range must be sorted

     1763      * (as by the {@link #sort(double[], int, int)} method)

     1764      * prior to making this call.

     1765      * If it is not sorted, the results are undefined.  If the range contains

     1766      * multiple elements with the specified value, there is no guarantee which

     1767      * one will be found.  This method considers all NaN values to be

     1768      * equivalent and equal.

     1769      *

     1770      * @param a the array to be searched

     1771      * @param fromIndex the index of the first element (inclusive) to be

     1772      *          searched

     1773      * @param toIndex the index of the last element (exclusive) to be searched

     1774      * @param key the value to be searched for

     1775      * @return index of the search key, if it is contained in the array

     1776      *         within the specified range;

     1777      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1778      *         <i>insertion point</i> is defined as the point at which the

     1779      *         key would be inserted into the array: the index of the first

     1780      *         element in the range greater than the key,

     1781      *         or <tt>toIndex</tt> if all

     1782      *         elements in the range are less than the specified key.  Note

     1783      *         that this guarantees that the return value will be >= 0 if

     1784      *         and only if the key is found.

     1785      * @throws IllegalArgumentException

     1786      *         if {@code fromIndex > toIndex}

     1787      * @throws ArrayIndexOutOfBoundsException

     1788      *         if {@code fromIndex < 0 or toIndex > a.length}

     1789      * @since 1.6

     1790      */

     1791     public static int binarySearch(double[] a, int fromIndex, int toIndex,

     1792                                    double key) {

     1793         rangeCheck(a.length, fromIndex, toIndex);

     1794         return binarySearch0(a, fromIndex, toIndex, key);

     1795     }

     1796 

     1797     // Like public version, but without range checks.

     1798     private static int binarySearch0(double[] a, int fromIndex, int toIndex,

     1799                                      double key) {

     1800         int low = fromIndex;

     1801         int high = toIndex - 1;

     1802 

     1803         while (low <= high) {

     1804             int mid = (low + high) >>> 1;

     1805             double midVal = a[mid];

     1806 

     1807             if (midVal < key)

     1808                 low = mid + 1;  // Neither val is NaN, thisVal is smaller

     1809             else if (midVal > key)

     1810                 high = mid - 1; // Neither val is NaN, thisVal is larger

     1811             else {

     1812                 long midBits = Double.doubleToLongBits(midVal);

     1813                 long keyBits = Double.doubleToLongBits(key);

     1814                 if (midBits == keyBits)     // Values are equal

     1815                     return mid;             // Key found

     1816                 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)

     1817                     low = mid + 1;

     1818                 else                        // (0.0, -0.0) or (NaN, !NaN)

     1819                     high = mid - 1;

     1820             }

     1821         }

     1822         return -(low + 1);  // key not found.

     1823     }

     1824 

     1825     /**

     1826      * Searches the specified array of floats for the specified value using

     1827      * the binary search algorithm.  The array must be sorted

     1828      * (as by the {@link #sort(float[])} method) prior to making this call.  If

     1829      * it is not sorted, the results are undefined.  If the array contains

     1830      * multiple elements with the specified value, there is no guarantee which

     1831      * one will be found.  This method considers all NaN values to be

     1832      * equivalent and equal.

     1833      *

     1834      * @param a the array to be searched

     1835      * @param key the value to be searched for

     1836      * @return index of the search key, if it is contained in the array;

     1837      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1838      *         <i>insertion point</i> is defined as the point at which the

     1839      *         key would be inserted into the array: the index of the first

     1840      *         element greater than the key, or <tt>a.length</tt> if all

     1841      *         elements in the array are less than the specified key.  Note

     1842      *         that this guarantees that the return value will be >= 0 if

     1843      *         and only if the key is found.

     1844      */

     1845     public static int binarySearch(float[] a, float key) {

     1846         return binarySearch0(a, 0, a.length, key);

     1847     }

     1848 

     1849     /**

     1850      * Searches a range of

     1851      * the specified array of floats for the specified value using

     1852      * the binary search algorithm.

     1853      * The range must be sorted

     1854      * (as by the {@link #sort(float[], int, int)} method)

     1855      * prior to making this call.  If

     1856      * it is not sorted, the results are undefined.  If the range contains

     1857      * multiple elements with the specified value, there is no guarantee which

     1858      * one will be found.  This method considers all NaN values to be

     1859      * equivalent and equal.

     1860      *

     1861      * @param a the array to be searched

     1862      * @param fromIndex the index of the first element (inclusive) to be

     1863      *          searched

     1864      * @param toIndex the index of the last element (exclusive) to be searched

     1865      * @param key the value to be searched for

     1866      * @return index of the search key, if it is contained in the array

     1867      *         within the specified range;

     1868      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1869      *         <i>insertion point</i> is defined as the point at which the

     1870      *         key would be inserted into the array: the index of the first

     1871      *         element in the range greater than the key,

     1872      *         or <tt>toIndex</tt> if all

     1873      *         elements in the range are less than the specified key.  Note

     1874      *         that this guarantees that the return value will be >= 0 if

     1875      *         and only if the key is found.

     1876      * @throws IllegalArgumentException

     1877      *         if {@code fromIndex > toIndex}

     1878      * @throws ArrayIndexOutOfBoundsException

     1879      *         if {@code fromIndex < 0 or toIndex > a.length}

     1880      * @since 1.6

     1881      */

     1882     public static int binarySearch(float[] a, int fromIndex, int toIndex,

     1883                                    float key) {

     1884         rangeCheck(a.length, fromIndex, toIndex);

     1885         return binarySearch0(a, fromIndex, toIndex, key);

     1886     }

     1887 

     1888     // Like public version, but without range checks.

     1889     private static int binarySearch0(float[] a, int fromIndex, int toIndex,

     1890                                      float key) {

     1891         int low = fromIndex;

     1892         int high = toIndex - 1;

     1893 

     1894         while (low <= high) {

     1895             int mid = (low + high) >>> 1;

     1896             float midVal = a[mid];

     1897 

     1898             if (midVal < key)

     1899                 low = mid + 1;  // Neither val is NaN, thisVal is smaller

     1900             else if (midVal > key)

     1901                 high = mid - 1; // Neither val is NaN, thisVal is larger

     1902             else {

     1903                 int midBits = Float.floatToIntBits(midVal);

     1904                 int keyBits = Float.floatToIntBits(key);

     1905                 if (midBits == keyBits)     // Values are equal

     1906                     return mid;             // Key found

     1907                 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)

     1908                     low = mid + 1;

     1909                 else                        // (0.0, -0.0) or (NaN, !NaN)

     1910                     high = mid - 1;

     1911             }

     1912         }

     1913         return -(low + 1);  // key not found.

     1914     }

     1915 

     1916 

     1917     /**

     1918      * Searches the specified array for the specified object using the binary

     1919      * search algorithm.  The array must be sorted into ascending order

     1920      * according to the

     1921      * {@linkplain Comparable natural ordering}

     1922      * of its elements (as by the

     1923      * {@link #sort(Object[])} method) prior to making this call.

     1924      * If it is not sorted, the results are undefined.

     1925      * (If the array contains elements that are not mutually comparable (for

     1926      * example, strings and integers), it <i>cannot</i> be sorted according

     1927      * to the natural ordering of its elements, hence results are undefined.)

     1928      * If the array contains multiple

     1929      * elements equal to the specified object, there is no guarantee which

     1930      * one will be found.

     1931      *

     1932      * @param a the array to be searched

     1933      * @param key the value to be searched for

     1934      * @return index of the search key, if it is contained in the array;

     1935      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1936      *         <i>insertion point</i> is defined as the point at which the

     1937      *         key would be inserted into the array: the index of the first

     1938      *         element greater than the key, or <tt>a.length</tt> if all

     1939      *         elements in the array are less than the specified key.  Note

     1940      *         that this guarantees that the return value will be >= 0 if

     1941      *         and only if the key is found.

     1942      * @throws ClassCastException if the search key is not comparable to the

     1943      *         elements of the array.

     1944      */

     1945     public static int binarySearch(Object[] a, Object key) {

     1946         return binarySearch0(a, 0, a.length, key);

     1947     }

     1948 

     1949     /**

     1950      * Searches a range of

     1951      * the specified array for the specified object using the binary

     1952      * search algorithm.

     1953      * The range must be sorted into ascending order

     1954      * according to the

     1955      * {@linkplain Comparable natural ordering}

     1956      * of its elements (as by the

     1957      * {@link #sort(Object[], int, int)} method) prior to making this

     1958      * call.  If it is not sorted, the results are undefined.

     1959      * (If the range contains elements that are not mutually comparable (for

     1960      * example, strings and integers), it <i>cannot</i> be sorted according

     1961      * to the natural ordering of its elements, hence results are undefined.)

     1962      * If the range contains multiple

     1963      * elements equal to the specified object, there is no guarantee which

     1964      * one will be found.

     1965      *

     1966      * @param a the array to be searched

     1967      * @param fromIndex the index of the first element (inclusive) to be

     1968      *          searched

     1969      * @param toIndex the index of the last element (exclusive) to be searched

     1970      * @param key the value to be searched for

     1971      * @return index of the search key, if it is contained in the array

     1972      *         within the specified range;

     1973      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     1974      *         <i>insertion point</i> is defined as the point at which the

     1975      *         key would be inserted into the array: the index of the first

     1976      *         element in the range greater than the key,

     1977      *         or <tt>toIndex</tt> if all

     1978      *         elements in the range are less than the specified key.  Note

     1979      *         that this guarantees that the return value will be >= 0 if

     1980      *         and only if the key is found.

     1981      * @throws ClassCastException if the search key is not comparable to the

     1982      *         elements of the array within the specified range.

     1983      * @throws IllegalArgumentException

     1984      *         if {@code fromIndex > toIndex}

     1985      * @throws ArrayIndexOutOfBoundsException

     1986      *         if {@code fromIndex < 0 or toIndex > a.length}

     1987      * @since 1.6

     1988      */

     1989     public static int binarySearch(Object[] a, int fromIndex, int toIndex,

     1990                                    Object key) {

     1991         rangeCheck(a.length, fromIndex, toIndex);

     1992         return binarySearch0(a, fromIndex, toIndex, key);

     1993     }

     1994 

     1995     // Like public version, but without range checks.

     1996     private static int binarySearch0(Object[] a, int fromIndex, int toIndex,

     1997                                      Object key) {

     1998         int low = fromIndex;

     1999         int high = toIndex - 1;

     2000 

     2001         while (low <= high) {

     2002             int mid = (low + high) >>> 1;

     2003             Comparable midVal = (Comparable)a[mid];

     2004             int cmp = midVal.compareTo(key);

     2005 

     2006             if (cmp < 0)

     2007                 low = mid + 1;

     2008             else if (cmp > 0)

     2009                 high = mid - 1;

     2010             else

     2011                 return mid; // key found

     2012         }

     2013         return -(low + 1);  // key not found.

     2014     }

     2015 

     2016     /**

     2017      * Searches the specified array for the specified object using the binary

     2018      * search algorithm.  The array must be sorted into ascending order

     2019      * according to the specified comparator (as by the

     2020      * {@link #sort(Object[], Comparator) sort(T[], Comparator)}

     2021      * method) prior to making this call.  If it is

     2022      * not sorted, the results are undefined.

     2023      * If the array contains multiple

     2024      * elements equal to the specified object, there is no guarantee which one

     2025      * will be found.

     2026      *

     2027      * @param a the array to be searched

     2028      * @param key the value to be searched for

     2029      * @param c the comparator by which the array is ordered.  A

     2030      *        <tt>null</tt> value indicates that the elements'

     2031      *        {@linkplain Comparable natural ordering} should be used.

     2032      * @return index of the search key, if it is contained in the array;

     2033      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     2034      *         <i>insertion point</i> is defined as the point at which the

     2035      *         key would be inserted into the array: the index of the first

     2036      *         element greater than the key, or <tt>a.length</tt> if all

     2037      *         elements in the array are less than the specified key.  Note

     2038      *         that this guarantees that the return value will be >= 0 if

     2039      *         and only if the key is found.

     2040      * @throws ClassCastException if the array contains elements that are not

     2041      *         <i>mutually comparable</i> using the specified comparator,

     2042      *         or the search key is not comparable to the

     2043      *         elements of the array using this comparator.

     2044      */

     2045     public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) {

     2046         return binarySearch0(a, 0, a.length, key, c);

     2047     }

     2048 

     2049     /**

     2050      * Searches a range of

     2051      * the specified array for the specified object using the binary

     2052      * search algorithm.

     2053      * The range must be sorted into ascending order

     2054      * according to the specified comparator (as by the

     2055      * {@link #sort(Object[], int, int, Comparator)

     2056      * sort(T[], int, int, Comparator)}

     2057      * method) prior to making this call.

     2058      * If it is not sorted, the results are undefined.

     2059      * If the range contains multiple elements equal to the specified object,

     2060      * there is no guarantee which one will be found.

     2061      *

     2062      * @param a the array to be searched

     2063      * @param fromIndex the index of the first element (inclusive) to be

     2064      *          searched

     2065      * @param toIndex the index of the last element (exclusive) to be searched

     2066      * @param key the value to be searched for

     2067      * @param c the comparator by which the array is ordered.  A

     2068      *        <tt>null</tt> value indicates that the elements'

     2069      *        {@linkplain Comparable natural ordering} should be used.

     2070      * @return index of the search key, if it is contained in the array

     2071      *         within the specified range;

     2072      *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The

     2073      *         <i>insertion point</i> is defined as the point at which the

     2074      *         key would be inserted into the array: the index of the first

     2075      *         element in the range greater than the key,

     2076      *         or <tt>toIndex</tt> if all

     2077      *         elements in the range are less than the specified key.  Note

     2078      *         that this guarantees that the return value will be >= 0 if

     2079      *         and only if the key is found.

     2080      * @throws ClassCastException if the range contains elements that are not

     2081      *         <i>mutually comparable</i> using the specified comparator,

     2082      *         or the search key is not comparable to the

     2083      *         elements in the range using this comparator.

     2084      * @throws IllegalArgumentException

     2085      *         if {@code fromIndex > toIndex}

     2086      * @throws ArrayIndexOutOfBoundsException

     2087      *         if {@code fromIndex < 0 or toIndex > a.length}

     2088      * @since 1.6

     2089      */

     2090     public static <T> int binarySearch(T[] a, int fromIndex, int toIndex,

     2091                                        T key, Comparator<? super T> c) {

     2092         rangeCheck(a.length, fromIndex, toIndex);

     2093         return binarySearch0(a, fromIndex, toIndex, key, c);

     2094     }

     2095 

     2096     // Like public version, but without range checks.

     2097     private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,

     2098                                          T key, Comparator<? super T> c) {

     2099         if (c == null) {

     2100             return binarySearch0(a, fromIndex, toIndex, key);

     2101         }

     2102         int low = fromIndex;

     2103         int high = toIndex - 1;

     2104 

     2105         while (low <= high) {

     2106             int mid = (low + high) >>> 1;

     2107             T midVal = a[mid];

     2108             int cmp = c.compare(midVal, key);

     2109 

     2110             if (cmp < 0)

     2111                 low = mid + 1;

     2112             else if (cmp > 0)

     2113                 high = mid - 1;

     2114             else

     2115                 return mid; // key found

     2116         }

     2117         return -(low + 1);  // key not found.

     2118     }

     2119 

     2120 

     2121     // Equality Testing

     2122 

     2123     /**

     2124      * Returns <tt>true</tt> if the two specified arrays of longs are

     2125      * <i>equal</i> to one another.  Two arrays are considered equal if both

     2126      * arrays contain the same number of elements, and all corresponding pairs

     2127      * of elements in the two arrays are equal.  In other words, two arrays

     2128      * are equal if they contain the same elements in the same order.  Also,

     2129      * two array references are considered equal if both are <tt>null</tt>.<p>

     2130      *

     2131      * @param a one array to be tested for equality

     2132      * @param a2 the other array to be tested for equality

     2133      * @return <tt>true</tt> if the two arrays are equal

     2134      */

     2135     public static boolean equals(long[] a, long[] a2) {

     2136         if (a==a2)

     2137             return true;

     2138         if (a==null || a2==null)

     2139             return false;

     2140 

     2141         int length = a.length;

     2142         if (a2.length != length)

     2143             return false;

     2144 

     2145         for (int i=0; i<length; i++)

     2146             if (a[i] != a2[i])

     2147                 return false;

     2148 

     2149         return true;

     2150     }

     2151 

     2152     /**

     2153      * Returns <tt>true</tt> if the two specified arrays of ints are

     2154      * <i>equal</i> to one another.  Two arrays are considered equal if both

     2155      * arrays contain the same number of elements, and all corresponding pairs

     2156      * of elements in the two arrays are equal.  In other words, two arrays

     2157      * are equal if they contain the same elements in the same order.  Also,

     2158      * two array references are considered equal if both are <tt>null</tt>.<p>

     2159      *

     2160      * @param a one array to be tested for equality

     2161      * @param a2 the other array to be tested for equality

     2162      * @return <tt>true</tt> if the two arrays are equal

     2163      */

     2164     public static boolean equals(int[] a, int[] a2) {

     2165         if (a==a2)

     2166             return true;

     2167         if (a==null || a2==null)

     2168             return false;

     2169 

     2170         int length = a.length;

     2171         if (a2.length != length)

     2172             return false;

     2173 

     2174         for (int i=0; i<length; i++)

     2175             if (a[i] != a2[i])

     2176                 return false;

     2177 

     2178         return true;

     2179     }

     2180 

     2181     /**

     2182      * Returns <tt>true</tt> if the two specified arrays of shorts are

     2183      * <i>equal</i> to one another.  Two arrays are considered equal if both

     2184      * arrays contain the same number of elements, and all corresponding pairs

     2185      * of elements in the two arrays are equal.  In other words, two arrays

     2186      * are equal if they contain the same elements in the same order.  Also,

     2187      * two array references are considered equal if both are <tt>null</tt>.<p>

     2188      *

     2189      * @param a one array to be tested for equality

     2190      * @param a2 the other array to be tested for equality

     2191      * @return <tt>true</tt> if the two arrays are equal

     2192      */

     2193     public static boolean equals(short[] a, short a2[]) {

     2194         if (a==a2)

     2195             return true;

     2196         if (a==null || a2==null)

     2197             return false;

     2198 

     2199         int length = a.length;

     2200         if (a2.length != length)

     2201             return false;

     2202 

     2203         for (int i=0; i<length; i++)

     2204             if (a[i] != a2[i])

     2205                 return false;

     2206 

     2207         return true;

     2208     }

     2209 

     2210     /**

     2211      * Returns <tt>true</tt> if the two specified arrays of chars are

     2212      * <i>equal</i> to one another.  Two arrays are considered equal if both

     2213      * arrays contain the same number of elements, and all corresponding pairs

     2214      * of elements in the two arrays are equal.  In other words, two arrays

     2215      * are equal if they contain the same elements in the same order.  Also,

     2216      * two array references are considered equal if both are <tt>null</tt>.<p>

     2217      *

     2218      * @param a one array to be tested for equality

     2219      * @param a2 the other array to be tested for equality

     2220      * @return <tt>true</tt> if the two arrays are equal

     2221      */

     2222     public static boolean equals(char[] a, char[] a2) {

     2223         if (a==a2)

     2224             return true;

     2225         if (a==null || a2==null)

     2226             return false;

     2227 

     2228         int length = a.length;

     2229         if (a2.length != length)

     2230             return false;

     2231 

     2232         for (int i=0; i<length; i++)

     2233             if (a[i] != a2[i])

     2234                 return false;

     2235 

     2236         return true;

     2237     }

     2238 

     2239     /**

     2240      * Returns <tt>true</tt> if the two specified arrays of bytes are

     2241      * <i>equal</i> to one another.  Two arrays are considered equal if both

     2242      * arrays contain the same number of elements, and all corresponding pairs

     2243      * of elements in the two arrays are equal.  In other words, two arrays

     2244      * are equal if they contain the same elements in the same order.  Also,

     2245      * two array references are considered equal if both are <tt>null</tt>.<p>

     2246      *

     2247      * @param a one array to be tested for equality

     2248      * @param a2 the other array to be tested for equality

     2249      * @return <tt>true</tt> if the two arrays are equal

     2250      */

     2251     public static boolean equals(byte[] a, byte[] a2) {

     2252         if (a==a2)

     2253             return true;

     2254         if (a==null || a2==null)

     2255             return false;

     2256 

     2257         int length = a.length;

     2258         if (a2.length != length)

     2259             return false;

     2260 

     2261         for (int i=0; i<length; i++)

     2262             if (a[i] != a2[i])

     2263                 return false;

     2264 

     2265         return true;

     2266     }

     2267 

     2268     /**

     2269      * Returns <tt>true</tt> if the two specified arrays of booleans are

     2270      * <i>equal</i> to one another.  Two arrays are considered equal if both

     2271      * arrays contain the same number of elements, and all corresponding pairs

     2272      * of elements in the two arrays are equal.  In other words, two arrays

     2273      * are equal if they contain the same elements in the same order.  Also,

     2274      * two array references are considered equal if both are <tt>null</tt>.<p>

     2275      *

     2276      * @param a one array to be tested for equality

     2277      * @param a2 the other array to be tested for equality

     2278      * @return <tt>true</tt> if the two arrays are equal

     2279      */

     2280     public static boolean equals(boolean[] a, boolean[] a2) {

     2281         if (a==a2)

     2282             return true;

     2283         if (a==null || a2==null)

     2284             return false;

     2285 

     2286         int length = a.length;

     2287         if (a2.length != length)

     2288             return false;

     2289 

     2290         for (int i=0; i<length; i++)

     2291             if (a[i] != a2[i])

     2292                 return false;

     2293 

     2294         return true;

     2295     }

     2296 

     2297     /**

     2298      * Returns <tt>true</tt> if the two specified arrays of doubles are

     2299      * <i>equal</i> to one another.  Two arrays are considered equal if both

     2300      * arrays contain the same number of elements, and all corresponding pairs

     2301      * of elements in the two arrays are equal.  In other words, two arrays

     2302      * are equal if they contain the same elements in the same order.  Also,

     2303      * two array references are considered equal if both are <tt>null</tt>.<p>

     2304      *

     2305      * Two doubles <tt>d1</tt> and <tt>d2</tt> are considered equal if:

     2306      * <pre>    <tt>new Double(d1).equals(new Double(d2))</tt></pre>

     2307      * (Unlike the <tt>==</tt> operator, this method considers

     2308      * <tt>NaN</tt> equals to itself, and 0.0d unequal to -0.0d.)

     2309      *

     2310      * @param a one array to be tested for equality

     2311      * @param a2 the other array to be tested for equality

     2312      * @return <tt>true</tt> if the two arrays are equal

     2313      * @see Double#equals(Object)

     2314      */

     2315     public static boolean equals(double[] a, double[] a2) {

     2316         if (a==a2)

     2317             return true;

     2318         if (a==null || a2==null)

     2319             return false;

     2320 

     2321         int length = a.length;

     2322         if (a2.length != length)

     2323             return false;

     2324 

     2325         for (int i=0; i<length; i++)

     2326             if (Double.doubleToLongBits(a[i])!=Double.doubleToLongBits(a2[i]))

     2327                 return false;

     2328 

     2329         return true;

     2330     }

     2331 

     2332     /**

     2333      * Returns <tt>true</tt> if the two specified arrays of floats are

     2334      * <i>equal</i> to one another.  Two arrays are considered equal if both

     2335      * arrays contain the same number of elements, and all corresponding pairs

     2336      * of elements in the two arrays are equal.  In other words, two arrays

     2337      * are equal if they contain the same elements in the same order.  Also,

     2338      * two array references are considered equal if both are <tt>null</tt>.<p>

     2339      *

     2340      * Two floats <tt>f1</tt> and <tt>f2</tt> are considered equal if:

     2341      * <pre>    <tt>new Float(f1).equals(new Float(f2))</tt></pre>

     2342      * (Unlike the <tt>==</tt> operator, this method considers

     2343      * <tt>NaN</tt> equals to itself, and 0.0f unequal to -0.0f.)

     2344      *

     2345      * @param a one array to be tested for equality

     2346      * @param a2 the other array to be tested for equality

     2347      * @return <tt>true</tt> if the two arrays are equal

     2348      * @see Float#equals(Object)

     2349      */

     2350     public static boolean equals(float[] a, float[] a2) {

     2351         if (a==a2)

     2352             return true;

     2353         if (a==null || a2==null)

     2354             return false;

     2355 

     2356         int length = a.length;

     2357         if (a2.length != length)

     2358             return false;

     2359 

     2360         for (int i=0; i<length; i++)

     2361             if (Float.floatToIntBits(a[i])!=Float.floatToIntBits(a2[i]))

     2362                 return false;

     2363 

     2364         return true;

     2365     }

     2366 

     2367 

     2368     /**

     2369      * Returns <tt>true</tt> if the two specified arrays of Objects are

     2370      * <i>equal</i> to one another.  The two arrays are considered equal if

     2371      * both arrays contain the same number of elements, and all corresponding

     2372      * pairs of elements in the two arrays are equal.  Two objects <tt>e1</tt>

     2373      * and <tt>e2</tt> are considered <i>equal</i> if <tt>(e1==null ? e2==null

     2374      * : e1.equals(e2))</tt>.  In other words, the two arrays are equal if

     2375      * they contain the same elements in the same order.  Also, two array

     2376      * references are considered equal if both are <tt>null</tt>.<p>

     2377      *

     2378      * @param a one array to be tested for equality

     2379      * @param a2 the other array to be tested for equality

     2380      * @return <tt>true</tt> if the two arrays are equal

     2381      */

     2382     public static boolean equals(Object[] a, Object[] a2) {

     2383         if (a==a2)

     2384             return true;

     2385         if (a==null || a2==null)

     2386             return false;

     2387 

     2388         int length = a.length;

     2389         if (a2.length != length)

     2390             return false;

     2391 

     2392         for (int i=0; i<length; i++) {

     2393             Object o1 = a[i];

     2394             Object o2 = a2[i];

     2395             if (!(o1==null ? o2==null : o1.equals(o2)))

     2396                 return false;

     2397         }

     2398 

     2399         return true;

     2400     }

     2401 

     2402 

     2403     // Filling

     2404 

     2405     /**

     2406      * Assigns the specified long value to each element of the specified array

     2407      * of longs.

     2408      *

     2409      * @param a the array to be filled

     2410      * @param val the value to be stored in all elements of the array

     2411      */

     2412     public static void fill(long[] a, long val) {

     2413         for (int i = 0, len = a.length; i < len; i++)

     2414             a[i] = val;

     2415     }

     2416 

     2417     /**

     2418      * Assigns the specified long value to each element of the specified

     2419      * range of the specified array of longs.  The range to be filled

     2420      * extends from index <tt>fromIndex</tt>, inclusive, to index

     2421      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the

     2422      * range to be filled is empty.)

     2423      *

     2424      * @param a the array to be filled

     2425      * @param fromIndex the index of the first element (inclusive) to be

     2426      *        filled with the specified value

     2427      * @param toIndex the index of the last element (exclusive) to be

     2428      *        filled with the specified value

     2429      * @param val the value to be stored in all elements of the array

     2430      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

     2431      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

     2432      *         <tt>toIndex &gt; a.length</tt>

     2433      */

     2434     public static void fill(long[] a, int fromIndex, int toIndex, long val) {

     2435         rangeCheck(a.length, fromIndex, toIndex);

     2436         for (int i = fromIndex; i < toIndex; i++)

     2437             a[i] = val;

     2438     }

     2439 

     2440     /**

     2441      * Assigns the specified int value to each element of the specified array

     2442      * of ints.

     2443      *

     2444      * @param a the array to be filled

     2445      * @param val the value to be stored in all elements of the array

     2446      */

     2447     public static void fill(int[] a, int val) {

     2448         for (int i = 0, len = a.length; i < len; i++)

     2449             a[i] = val;

     2450     }

     2451 

     2452     /**

     2453      * Assigns the specified int value to each element of the specified

     2454      * range of the specified array of ints.  The range to be filled

     2455      * extends from index <tt>fromIndex</tt>, inclusive, to index

     2456      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the

     2457      * range to be filled is empty.)

     2458      *

     2459      * @param a the array to be filled

     2460      * @param fromIndex the index of the first element (inclusive) to be

     2461      *        filled with the specified value

     2462      * @param toIndex the index of the last element (exclusive) to be

     2463      *        filled with the specified value

     2464      * @param val the value to be stored in all elements of the array

     2465      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

     2466      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

     2467      *         <tt>toIndex &gt; a.length</tt>

     2468      */

     2469     public static void fill(int[] a, int fromIndex, int toIndex, int val) {

     2470         rangeCheck(a.length, fromIndex, toIndex);

     2471         for (int i = fromIndex; i < toIndex; i++)

     2472             a[i] = val;

     2473     }

     2474 

     2475     /**

     2476      * Assigns the specified short value to each element of the specified array

     2477      * of shorts.

     2478      *

     2479      * @param a the array to be filled

     2480      * @param val the value to be stored in all elements of the array

     2481      */

     2482     public static void fill(short[] a, short val) {

     2483         for (int i = 0, len = a.length; i < len; i++)

     2484             a[i] = val;

     2485     }

     2486 

     2487     /**

     2488      * Assigns the specified short value to each element of the specified

     2489      * range of the specified array of shorts.  The range to be filled

     2490      * extends from index <tt>fromIndex</tt>, inclusive, to index

     2491      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the

     2492      * range to be filled is empty.)

     2493      *

     2494      * @param a the array to be filled

     2495      * @param fromIndex the index of the first element (inclusive) to be

     2496      *        filled with the specified value

     2497      * @param toIndex the index of the last element (exclusive) to be

     2498      *        filled with the specified value

     2499      * @param val the value to be stored in all elements of the array

     2500      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

     2501      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

     2502      *         <tt>toIndex &gt; a.length</tt>

     2503      */

     2504     public static void fill(short[] a, int fromIndex, int toIndex, short val) {

     2505         rangeCheck(a.length, fromIndex, toIndex);

     2506         for (int i = fromIndex; i < toIndex; i++)

     2507             a[i] = val;

     2508     }

     2509 

     2510     /**

     2511      * Assigns the specified char value to each element of the specified array

     2512      * of chars.

     2513      *

     2514      * @param a the array to be filled

     2515      * @param val the value to be stored in all elements of the array

     2516      */

     2517     public static void fill(char[] a, char val) {

     2518         for (int i = 0, len = a.length; i < len; i++)

     2519             a[i] = val;

     2520     }

     2521 

     2522     /**

     2523      * Assigns the specified char value to each element of the specified

     2524      * range of the specified array of chars.  The range to be filled

     2525      * extends from index <tt>fromIndex</tt>, inclusive, to index

     2526      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the

     2527      * range to be filled is empty.)

     2528      *

     2529      * @param a the array to be filled

     2530      * @param fromIndex the index of the first element (inclusive) to be

     2531      *        filled with the specified value

     2532      * @param toIndex the index of the last element (exclusive) to be

     2533      *        filled with the specified value

     2534      * @param val the value to be stored in all elements of the array

     2535      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

     2536      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

     2537      *         <tt>toIndex &gt; a.length</tt>

     2538      */

     2539     public static void fill(char[] a, int fromIndex, int toIndex, char val) {

     2540         rangeCheck(a.length, fromIndex, toIndex);

     2541         for (int i = fromIndex; i < toIndex; i++)

     2542             a[i] = val;

     2543     }

     2544 

     2545     /**

     2546      * Assigns the specified byte value to each element of the specified array

     2547      * of bytes.

     2548      *

     2549      * @param a the array to be filled

     2550      * @param val the value to be stored in all elements of the array

     2551      */

     2552     public static void fill(byte[] a, byte val) {

     2553         for (int i = 0, len = a.length; i < len; i++)

     2554             a[i] = val;

     2555     }

     2556 

     2557     /**

     2558      * Assigns the specified byte value to each element of the specified

     2559      * range of the specified array of bytes.  The range to be filled

     2560      * extends from index <tt>fromIndex</tt>, inclusive, to index

     2561      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the

     2562      * range to be filled is empty.)

     2563      *

     2564      * @param a the array to be filled

     2565      * @param fromIndex the index of the first element (inclusive) to be

     2566      *        filled with the specified value

     2567      * @param toIndex the index of the last element (exclusive) to be

     2568      *        filled with the specified value

     2569      * @param val the value to be stored in all elements of the array

     2570      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

     2571      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

     2572      *         <tt>toIndex &gt; a.length</tt>

     2573      */

     2574     public static void fill(byte[] a, int fromIndex, int toIndex, byte val) {

     2575         rangeCheck(a.length, fromIndex, toIndex);

     2576         for (int i = fromIndex; i < toIndex; i++)

     2577             a[i] = val;

     2578     }

     2579 

     2580     /**

     2581      * Assigns the specified boolean value to each element of the specified

     2582      * array of booleans.

     2583      *

     2584      * @param a the array to be filled

     2585      * @param val the value to be stored in all elements of the array

     2586      */

     2587     public static void fill(boolean[] a, boolean val) {

     2588         for (int i = 0, len = a.length; i < len; i++)

     2589             a[i] = val;

     2590     }

     2591 

     2592     /**

     2593      * Assigns the specified boolean value to each element of the specified

     2594      * range of the specified array of booleans.  The range to be filled

     2595      * extends from index <tt>fromIndex</tt>, inclusive, to index

     2596      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the

     2597      * range to be filled is empty.)

     2598      *

     2599      * @param a the array to be filled

     2600      * @param fromIndex the index of the first element (inclusive) to be

     2601      *        filled with the specified value

     2602      * @param toIndex the index of the last element (exclusive) to be

     2603      *        filled with the specified value

     2604      * @param val the value to be stored in all elements of the array

     2605      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

     2606      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

     2607      *         <tt>toIndex &gt; a.length</tt>

     2608      */

     2609     public static void fill(boolean[] a, int fromIndex, int toIndex,

     2610                             boolean val) {

     2611         rangeCheck(a.length, fromIndex, toIndex);

     2612         for (int i = fromIndex; i < toIndex; i++)

     2613             a[i] = val;

     2614     }

     2615 

     2616     /**

     2617      * Assigns the specified double value to each element of the specified

     2618      * array of doubles.

     2619      *

     2620      * @param a the array to be filled

     2621      * @param val the value to be stored in all elements of the array

     2622      */

     2623     public static void fill(double[] a, double val) {

     2624         for (int i = 0, len = a.length; i < len; i++)

     2625             a[i] = val;

     2626     }

     2627 

     2628     /**

     2629      * Assigns the specified double value to each element of the specified

     2630      * range of the specified array of doubles.  The range to be filled

     2631      * extends from index <tt>fromIndex</tt>, inclusive, to index

     2632      * <tt>toIndex</tt>, exclusive.  (If <tt>fromIndex==toIndex</tt>, the

     2633      * range to be filled is empty.)

     2634      *

     2635      * @param a the array to be filled

     2636      * @param fromIndex the index of the first element (inclusive) to be

     2637      *        filled with the specified value

     2638      * @param toIndex the index of the last element (exclusive) to be

     2639      *        filled with the specified value

     2640      * @param val the value to be stored in all elements of the array

     2641      * @throws IllegalArgumentException if <tt>fromIndex &gt; toIndex</tt>

     2642      * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex &lt; 0</tt> or

     2643      *         <tt>toIndex &gt; a.length</tt>

     2644      */

     2645     public static void fill(double[] a, int fromIndex, int toIndex,double val){

     2646         rangeCheck(a.length, fromIndex, toIndex);

     2647         for (int i = fromIndex; i < toIndex; i++)

     2648             a[i] = val;

     2649     }

     2650 

     2651     /**

     2652      * Assigns the specified float value to each element of the specified array

     2653      * of floats.