Arrays


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