OSDN Git Service

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