001    /* Arrays.java -- Utility class with methods to operate on arrays
002       Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
003       Free Software Foundation, Inc.
004    
005    This file is part of GNU Classpath.
006    
007    GNU Classpath is free software; you can redistribute it and/or modify
008    it under the terms of the GNU General Public License as published by
009    the Free Software Foundation; either version 2, or (at your option)
010    any later version.
011    
012    GNU Classpath is distributed in the hope that it will be useful, but
013    WITHOUT ANY WARRANTY; without even the implied warranty of
014    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
015    General Public License for more details.
016    
017    You should have received a copy of the GNU General Public License
018    along with GNU Classpath; see the file COPYING.  If not, write to the
019    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
020    02110-1301 USA.
021    
022    Linking this library statically or dynamically with other modules is
023    making a combined work based on this library.  Thus, the terms and
024    conditions of the GNU General Public License cover the whole
025    combination.
026    
027    As a special exception, the copyright holders of this library give you
028    permission to link this library with independent modules to produce an
029    executable, regardless of the license terms of these independent
030    modules, and to copy and distribute the resulting executable under
031    terms of your choice, provided that you also meet, for each linked
032    independent module, the terms and conditions of the license of that
033    module.  An independent module is a module which is not derived from
034    or based on this library.  If you modify this library, you may extend
035    this exception to your version of the library, but you are not
036    obligated to do so.  If you do not wish to do so, delete this
037    exception statement from your version. */
038    
039    
040    package java.util;
041    
042    import java.io.Serializable;
043    import java.lang.reflect.Array;
044    
045    /**
046     * This class contains various static utility methods performing operations on
047     * arrays, and a method to provide a List "view" of an array to facilitate
048     * using arrays with Collection-based APIs. All methods throw a
049     * {@link NullPointerException} if the parameter array is null.
050     * <p>
051     *
052     * Implementations may use their own algorithms, but must obey the general
053     * properties; for example, the sort must be stable and n*log(n) complexity.
054     * Sun's implementation of sort, and therefore ours, is a tuned quicksort,
055     * adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort
056     * Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265
057     * (November 1993). This algorithm offers n*log(n) performance on many data
058     * sets that cause other quicksorts to degrade to quadratic performance.
059     *
060     * @author Original author unknown
061     * @author Bryce McKinlay
062     * @author Eric Blake (ebb9@email.byu.edu)
063     * @see Comparable
064     * @see Comparator
065     * @since 1.2
066     * @status updated to 1.4
067     */
068    public class Arrays
069    {
070      /**
071       * This class is non-instantiable.
072       */
073      private Arrays()
074      {
075      }
076    
077    
078    // binarySearch
079      /**
080       * Perform a binary search of a byte array for a key. The array must be
081       * sorted (as by the sort() method) - if it is not, the behaviour of this
082       * method is undefined, and may be an infinite loop. If the array contains
083       * the key more than once, any one of them may be found. Note: although the
084       * specification allows for an infinite loop if the array is unsorted, it
085       * will not happen in this implementation.
086       *
087       * @param a the array to search (must be sorted)
088       * @param key the value to search for
089       * @return the index at which the key was found, or -n-1 if it was not
090       *         found, where n is the index of the first value higher than key or
091       *         a.length if there is no such value.
092       */
093      public static int binarySearch(byte[] a, byte key)
094      {
095        if (a.length == 0)
096          return -1;
097        return binarySearch(a, 0, a.length - 1, key);
098      }
099    
100      /**
101       * Perform a binary search of a range of a byte array for a key. The range
102       * must be sorted (as by the <code>sort(byte[], int, int)</code> method) -
103       * if it is not, the behaviour of this method is undefined, and may be an
104       * infinite loop. If the array contains the key more than once, any one of
105       * them may be found. Note: although the specification allows for an infinite
106       * loop if the array is unsorted, it will not happen in this implementation.
107       *
108       * @param a the array to search (must be sorted)
109       * @param low the lowest index to search from.
110       * @param hi the highest index to search to.
111       * @param key the value to search for
112       * @return the index at which the key was found, or -n-1 if it was not
113       *         found, where n is the index of the first value higher than key or
114       *         a.length if there is no such value.
115       * @throws IllegalArgumentException if <code>low > hi</code>
116       * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
117       *                                        <code>hi > a.length</code>.
118       */
119      public static int binarySearch(byte[] a, int low, int hi, byte key)
120      {
121        if (low > hi)
122          throw new IllegalArgumentException("The start index is higher than " +
123                                             "the finish index.");
124        if (low < 0 || hi > a.length)
125          throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
126                                                   "of bounds.");
127        int mid = 0;
128        while (low <= hi)
129          {
130            mid = (low + hi) >>> 1;
131            final byte d = a[mid];
132            if (d == key)
133              return mid;
134            else if (d > key)
135              hi = mid - 1;
136            else
137              // This gets the insertion point right on the last loop.
138              low = ++mid;
139          }
140        return -mid - 1;
141      }
142    
143      /**
144       * Perform a binary search of a char array for a key. The array must be
145       * sorted (as by the sort() method) - if it is not, the behaviour of this
146       * method is undefined, and may be an infinite loop. If the array contains
147       * the key more than once, any one of them may be found. Note: although the
148       * specification allows for an infinite loop if the array is unsorted, it
149       * will not happen in this implementation.
150       *
151       * @param a the array to search (must be sorted)
152       * @param key the value to search for
153       * @return the index at which the key was found, or -n-1 if it was not
154       *         found, where n is the index of the first value higher than key or
155       *         a.length if there is no such value.
156       */
157      public static int binarySearch(char[] a, char key)
158      {
159        if (a.length == 0)
160          return -1;
161        return binarySearch(a, 0, a.length - 1, key);
162      }
163    
164      /**
165       * Perform a binary search of a range of a char array for a key. The range
166       * must be sorted (as by the <code>sort(char[], int, int)</code> method) -
167       * if it is not, the behaviour of this method is undefined, and may be an
168       * infinite loop. If the array contains the key more than once, any one of
169       * them may be found. Note: although the specification allows for an infinite
170       * loop if the array is unsorted, it will not happen in this implementation.
171       *
172       * @param a the array to search (must be sorted)
173       * @param low the lowest index to search from.
174       * @param hi the highest index to search to.
175       * @param key the value to search for
176       * @return the index at which the key was found, or -n-1 if it was not
177       *         found, where n is the index of the first value higher than key or
178       *         a.length if there is no such value.
179       * @throws IllegalArgumentException if <code>low > hi</code>
180       * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
181       *                                        <code>hi > a.length</code>.
182       */
183      public static int binarySearch(char[] a, int low, int hi, char key)
184      {
185        if (low > hi)
186          throw new IllegalArgumentException("The start index is higher than " +
187                                             "the finish index.");
188        if (low < 0 || hi > a.length)
189          throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
190                                                   "of bounds.");
191        int mid = 0;
192        while (low <= hi)
193          {
194            mid = (low + hi) >>> 1;
195            final char d = a[mid];
196            if (d == key)
197              return mid;
198            else if (d > key)
199              hi = mid - 1;
200            else
201              // This gets the insertion point right on the last loop.
202              low = ++mid;
203          }
204        return -mid - 1;
205      }
206    
207      /**
208       * Perform a binary search of a short array for a key. The array must be
209       * sorted (as by the sort() method) - if it is not, the behaviour of this
210       * method is undefined, and may be an infinite loop. If the array contains
211       * the key more than once, any one of them may be found. Note: although the
212       * specification allows for an infinite loop if the array is unsorted, it
213       * will not happen in this implementation.
214       *
215       * @param a the array to search (must be sorted)
216       * @param key the value to search for
217       * @return the index at which the key was found, or -n-1 if it was not
218       *         found, where n is the index of the first value higher than key or
219       *         a.length if there is no such value.
220       */
221      public static int binarySearch(short[] a, short key)
222      {
223        if (a.length == 0)
224          return -1;
225        return binarySearch(a, 0, a.length - 1, key);
226      }
227    
228      /**
229       * Perform a binary search of a range of a short array for a key. The range
230       * must be sorted (as by the <code>sort(short[], int, int)</code> method) -
231       * if it is not, the behaviour of this method is undefined, and may be an
232       * infinite loop. If the array contains the key more than once, any one of
233       * them may be found. Note: although the specification allows for an infinite
234       * loop if the array is unsorted, it will not happen in this implementation.
235       *
236       * @param a the array to search (must be sorted)
237       * @param low the lowest index to search from.
238       * @param hi the highest index to search to.
239       * @param key the value to search for
240       * @return the index at which the key was found, or -n-1 if it was not
241       *         found, where n is the index of the first value higher than key or
242       *         a.length if there is no such value.
243       * @throws IllegalArgumentException if <code>low > hi</code>
244       * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
245       *                                        <code>hi > a.length</code>.
246       */
247      public static int binarySearch(short[] a, int low, int hi, short key)
248      {
249        if (low > hi)
250          throw new IllegalArgumentException("The start index is higher than " +
251                                             "the finish index.");
252        if (low < 0 || hi > a.length)
253          throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
254                                                   "of bounds.");
255        int mid = 0;
256        while (low <= hi)
257          {
258            mid = (low + hi) >>> 1;
259            final short d = a[mid];
260            if (d == key)
261              return mid;
262            else if (d > key)
263              hi = mid - 1;
264            else
265              // This gets the insertion point right on the last loop.
266              low = ++mid;
267          }
268        return -mid - 1;
269      }
270    
271      /**
272       * Perform a binary search of an int array for a key. The array must be
273       * sorted (as by the sort() method) - if it is not, the behaviour of this
274       * method is undefined, and may be an infinite loop. If the array contains
275       * the key more than once, any one of them may be found. Note: although the
276       * specification allows for an infinite loop if the array is unsorted, it
277       * will not happen in this implementation.
278       *
279       * @param a the array to search (must be sorted)
280       * @param key the value to search for
281       * @return the index at which the key was found, or -n-1 if it was not
282       *         found, where n is the index of the first value higher than key or
283       *         a.length if there is no such value.
284       */
285      public static int binarySearch(int[] a, int key)
286      {
287        if (a.length == 0)
288          return -1;
289        return binarySearch(a, 0, a.length - 1, key);
290      }
291    
292      /**
293       * Perform a binary search of a range of an integer array for a key. The range
294       * must be sorted (as by the <code>sort(int[], int, int)</code> method) -
295       * if it is not, the behaviour of this method is undefined, and may be an
296       * infinite loop. If the array contains the key more than once, any one of
297       * them may be found. Note: although the specification allows for an infinite
298       * loop if the array is unsorted, it will not happen in this implementation.
299       *
300       * @param a the array to search (must be sorted)
301       * @param low the lowest index to search from.
302       * @param hi the highest index to search to.
303       * @param key the value to search for
304       * @return the index at which the key was found, or -n-1 if it was not
305       *         found, where n is the index of the first value higher than key or
306       *         a.length if there is no such value.
307       * @throws IllegalArgumentException if <code>low > hi</code>
308       * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
309       *                                        <code>hi > a.length</code>.
310       */
311      public static int binarySearch(int[] a, int low, int hi, int key)
312      {
313        if (low > hi)
314          throw new IllegalArgumentException("The start index is higher than " +
315                                             "the finish index.");
316        if (low < 0 || hi > a.length)
317          throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
318                                                   "of bounds.");
319        int mid = 0;
320        while (low <= hi)
321          {
322            mid = (low + hi) >>> 1;
323            final int d = a[mid];
324            if (d == key)
325              return mid;
326            else if (d > key)
327              hi = mid - 1;
328            else
329              // This gets the insertion point right on the last loop.
330              low = ++mid;
331          }
332        return -mid - 1;
333      }
334    
335      /**
336       * Perform a binary search of a long array for a key. The array must be
337       * sorted (as by the sort() method) - if it is not, the behaviour of this
338       * method is undefined, and may be an infinite loop. If the array contains
339       * the key more than once, any one of them may be found. Note: although the
340       * specification allows for an infinite loop if the array is unsorted, it
341       * will not happen in this implementation.
342       *
343       * @param a the array to search (must be sorted)
344       * @param key the value to search for
345       * @return the index at which the key was found, or -n-1 if it was not
346       *         found, where n is the index of the first value higher than key or
347       *         a.length if there is no such value.
348       */
349      public static int binarySearch(long[] a, long key)
350      {
351        if (a.length == 0)
352          return -1;
353        return binarySearch(a, 0, a.length - 1, key);
354      }
355    
356      /**
357       * Perform a binary search of a range of a long array for a key. The range
358       * must be sorted (as by the <code>sort(long[], int, int)</code> method) -
359       * if it is not, the behaviour of this method is undefined, and may be an
360       * infinite loop. If the array contains the key more than once, any one of
361       * them may be found. Note: although the specification allows for an infinite
362       * loop if the array is unsorted, it will not happen in this implementation.
363       *
364       * @param a the array to search (must be sorted)
365       * @param low the lowest index to search from.
366       * @param hi the highest index to search to.
367       * @param key the value to search for
368       * @return the index at which the key was found, or -n-1 if it was not
369       *         found, where n is the index of the first value higher than key or
370       *         a.length if there is no such value.
371       * @throws IllegalArgumentException if <code>low > hi</code>
372       * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
373       *                                        <code>hi > a.length</code>.
374       */
375      public static int binarySearch(long[] a, int low, int hi, long key)
376      {
377        if (low > hi)
378          throw new IllegalArgumentException("The start index is higher than " +
379                                             "the finish index.");
380        if (low < 0 || hi > a.length)
381          throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
382                                                   "of bounds.");
383        int mid = 0;
384        while (low <= hi)
385          {
386            mid = (low + hi) >>> 1;
387            final long d = a[mid];
388            if (d == key)
389              return mid;
390            else if (d > key)
391              hi = mid - 1;
392            else
393              // This gets the insertion point right on the last loop.
394              low = ++mid;
395          }
396        return -mid - 1;
397      }
398    
399      /**
400       * Perform a binary search of a float array for a key. The array must be
401       * sorted (as by the sort() method) - if it is not, the behaviour of this
402       * method is undefined, and may be an infinite loop. If the array contains
403       * the key more than once, any one of them may be found. Note: although the
404       * specification allows for an infinite loop if the array is unsorted, it
405       * will not happen in this implementation.
406       *
407       * @param a the array to search (must be sorted)
408       * @param key the value to search for
409       * @return the index at which the key was found, or -n-1 if it was not
410       *         found, where n is the index of the first value higher than key or
411       *         a.length if there is no such value.
412       */
413      public static int binarySearch(float[] a, float key)
414      {
415        if (a.length == 0)
416          return -1;
417        return binarySearch(a, 0, a.length - 1, key);
418      }
419    
420      /**
421       * Perform a binary search of a range of a float array for a key. The range
422       * must be sorted (as by the <code>sort(float[], int, int)</code> method) -
423       * if it is not, the behaviour of this method is undefined, and may be an
424       * infinite loop. If the array contains the key more than once, any one of
425       * them may be found. Note: although the specification allows for an infinite
426       * loop if the array is unsorted, it will not happen in this implementation.
427       *
428       * @param a the array to search (must be sorted)
429       * @param low the lowest index to search from.
430       * @param hi the highest index to search to.
431       * @param key the value to search for
432       * @return the index at which the key was found, or -n-1 if it was not
433       *         found, where n is the index of the first value higher than key or
434       *         a.length if there is no such value.
435       * @throws IllegalArgumentException if <code>low > hi</code>
436       * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
437       *                                        <code>hi > a.length</code>.
438       */
439      public static int binarySearch(float[] a, int low, int hi, float key)
440      {
441        if (low > hi)
442          throw new IllegalArgumentException("The start index is higher than " +
443                                             "the finish index.");
444        if (low < 0 || hi > a.length)
445          throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
446                                                   "of bounds.");
447        // Must use Float.compare to take into account NaN, +-0.
448        int mid = 0;
449        while (low <= hi)
450          {
451            mid = (low + hi) >>> 1;
452            final int r = Float.compare(a[mid], key);
453            if (r == 0)
454              return mid;
455            else if (r > 0)
456              hi = mid - 1;
457            else
458              // This gets the insertion point right on the last loop
459              low = ++mid;
460          }
461        return -mid - 1;
462      }
463    
464      /**
465       * Perform a binary search of a double array for a key. The array must be
466       * sorted (as by the sort() method) - if it is not, the behaviour of this
467       * method is undefined, and may be an infinite loop. If the array contains
468       * the key more than once, any one of them may be found. Note: although the
469       * specification allows for an infinite loop if the array is unsorted, it
470       * will not happen in this implementation.
471       *
472       * @param a the array to search (must be sorted)
473       * @param key the value to search for
474       * @return the index at which the key was found, or -n-1 if it was not
475       *         found, where n is the index of the first value higher than key or
476       *         a.length if there is no such value.
477       */
478      public static int binarySearch(double[] a, double key)
479      {
480        if (a.length == 0)
481          return -1;
482        return binarySearch(a, 0, a.length - 1, key);
483      }
484    
485      /**
486       * Perform a binary search of a range of a double array for a key. The range
487       * must be sorted (as by the <code>sort(double[], int, int)</code> method) -
488       * if it is not, the behaviour of this method is undefined, and may be an
489       * infinite loop. If the array contains the key more than once, any one of
490       * them may be found. Note: although the specification allows for an infinite
491       * loop if the array is unsorted, it will not happen in this implementation.
492       *
493       * @param a the array to search (must be sorted)
494       * @param low the lowest index to search from.
495       * @param hi the highest index to search to.
496       * @param key the value to search for
497       * @return the index at which the key was found, or -n-1 if it was not
498       *         found, where n is the index of the first value higher than key or
499       *         a.length if there is no such value.
500       * @throws IllegalArgumentException if <code>low > hi</code>
501       * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
502       *                                        <code>hi > a.length</code>.
503       */
504      public static int binarySearch(double[] a, int low, int hi, double key)
505      {
506        if (low > hi)
507          throw new IllegalArgumentException("The start index is higher than " +
508                                             "the finish index.");
509        if (low < 0 || hi > a.length)
510          throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
511                                                   "of bounds.");
512        // Must use Double.compare to take into account NaN, +-0.
513        int mid = 0;
514        while (low <= hi)
515          {
516            mid = (low + hi) >>> 1;
517            final int r = Double.compare(a[mid], key);
518            if (r == 0)
519              return mid;
520            else if (r > 0)
521              hi = mid - 1;
522            else
523              // This gets the insertion point right on the last loop
524              low = ++mid;
525          }
526        return -mid - 1;
527      }
528    
529      /**
530       * Perform a binary search of an Object array for a key, using the natural
531       * ordering of the elements. The array must be sorted (as by the sort()
532       * method) - if it is not, the behaviour of this method is undefined, and may
533       * be an infinite loop. Further, the key must be comparable with every item
534       * in the array. If the array contains the key more than once, any one of
535       * them may be found. Note: although the specification allows for an infinite
536       * loop if the array is unsorted, it will not happen in this (JCL)
537       * implementation.
538       *
539       * @param a the array to search (must be sorted)
540       * @param key the value to search for
541       * @return the index at which the key was found, or -n-1 if it was not
542       *         found, where n is the index of the first value higher than key or
543       *         a.length if there is no such value.
544       * @throws ClassCastException if key could not be compared with one of the
545       *         elements of a
546       * @throws NullPointerException if a null element in a is compared
547       */
548      public static int binarySearch(Object[] a, Object key)
549      {
550        if (a.length == 0)
551          return -1;
552        return binarySearch(a, key, null);
553      }
554    
555      /**
556       * Perform a binary search of a range of an Object array for a key. The range
557       * must be sorted (as by the <code>sort(Object[], int, int)</code> method) -
558       * if it is not, the behaviour of this method is undefined, and may be an
559       * infinite loop. If the array contains the key more than once, any one of
560       * them may be found. Note: although the specification allows for an infinite
561       * loop if the array is unsorted, it will not happen in this implementation.
562       *
563       * @param a the array to search (must be sorted)
564       * @param low the lowest index to search from.
565       * @param hi the highest index to search to.
566       * @param key the value to search for
567       * @return the index at which the key was found, or -n-1 if it was not
568       *         found, where n is the index of the first value higher than key or
569       *         a.length if there is no such value.
570       */
571      public static int binarySearch(Object[] a, int low, int hi, Object key)
572      {
573        return binarySearch(a, low, hi, key, null);
574      }
575    
576      /**
577       * Perform a binary search of an Object array for a key, using a supplied
578       * Comparator. The array must be sorted (as by the sort() method with the
579       * same Comparator) - if it is not, the behaviour of this method is
580       * undefined, and may be an infinite loop. Further, the key must be
581       * comparable with every item in the array. If the array contains the key
582       * more than once, any one of them may be found. Note: although the
583       * specification allows for an infinite loop if the array is unsorted, it
584       * will not happen in this (JCL) implementation.
585       *
586       * @param a the array to search (must be sorted)
587       * @param key the value to search for
588       * @param c the comparator by which the array is sorted; or null to
589       *        use the elements' natural order
590       * @return the index at which the key was found, or -n-1 if it was not
591       *         found, where n is the index of the first value higher than key or
592       *         a.length if there is no such value.
593       * @throws ClassCastException if key could not be compared with one of the
594       *         elements of a
595       * @throws NullPointerException if a null element is compared with natural
596       *         ordering (only possible when c is null)
597       */
598      public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
599      {
600        if (a.length == 0)
601          return -1;
602        return binarySearch(a, 0, a.length - 1, key, c);
603      }
604    
605      /**
606       * Perform a binary search of a range of an Object array for a key using
607       * a {@link Comparator}. The range must be sorted (as by the
608       * <code>sort(Object[], int, int)</code> method) - if it is not, the
609       * behaviour of this method is undefined, and may be an infinite loop. If
610       * the array contains the key more than once, any one of them may be found.
611       * Note: although the specification allows for an infinite loop if the array
612       * is unsorted, it will not happen in this implementation.
613       *
614       * @param a the array to search (must be sorted)
615       * @param low the lowest index to search from.
616       * @param hi the highest index to search to.
617       * @param key the value to search for
618       * @param c the comparator by which the array is sorted; or null to
619       *        use the elements' natural order
620       * @return the index at which the key was found, or -n-1 if it was not
621       *         found, where n is the index of the first value higher than key or
622       *         a.length if there is no such value.
623       * @throws ClassCastException if key could not be compared with one of the
624       *         elements of a
625       * @throws IllegalArgumentException if <code>low > hi</code>
626       * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
627       *                                        <code>hi > a.length</code>.
628       */
629      public static <T> int binarySearch(T[] a, int low, int hi, T key,
630                                         Comparator<? super T> c)
631      {
632        if (low > hi)
633          throw new IllegalArgumentException("The start index is higher than " +
634                                             "the finish index.");
635        if (low < 0 || hi > a.length)
636          throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
637                                                   "of bounds.");
638        int mid = 0;
639        while (low <= hi)
640          {
641            mid = (low + hi) >>> 1;
642            // NOTE: Please keep the order of a[mid] and key.  Although
643            // not required by the specs, the RI has it in this order as
644            // well, and real programs (erroneously) depend on it.
645            final int d = Collections.compare(a[mid], key, c);
646            if (d == 0)
647              return mid;
648            else if (d > 0)
649              hi = mid - 1;
650            else
651              // This gets the insertion point right on the last loop
652              low = ++mid;
653          }
654        return -mid - 1;
655      }
656    
657    
658    // equals
659      /**
660       * Compare two boolean arrays for equality.
661       *
662       * @param a1 the first array to compare
663       * @param a2 the second array to compare
664       * @return true if a1 and a2 are both null, or if a2 is of the same length
665       *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
666       */
667      public static boolean equals(boolean[] a1, boolean[] a2)
668      {
669        // Quick test which saves comparing elements of the same array, and also
670        // catches the case that both are null.
671        if (a1 == a2)
672          return true;
673    
674        if (null == a1 || null == a2)
675          return false;
676        
677        // If they're the same length, test each element
678        if (a1.length == a2.length)
679          {
680            int i = a1.length;
681            while (--i >= 0)
682              if (a1[i] != a2[i])
683                return false;
684            return true;
685          }
686        return false;
687      }
688    
689      /**
690       * Compare two byte arrays for equality.
691       *
692       * @param a1 the first array to compare
693       * @param a2 the second array to compare
694       * @return true if a1 and a2 are both null, or if a2 is of the same length
695       *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
696       */
697      public static boolean equals(byte[] a1, byte[] a2)
698      {
699        // Quick test which saves comparing elements of the same array, and also
700        // catches the case that both are null.
701        if (a1 == a2)
702          return true;
703    
704        if (null == a1 || null == a2)
705          return false;
706    
707        // If they're the same length, test each element
708        if (a1.length == a2.length)
709          {
710            int i = a1.length;
711            while (--i >= 0)
712              if (a1[i] != a2[i])
713                return false;
714            return true;
715          }
716        return false;
717      }
718    
719      /**
720       * Compare two char arrays for equality.
721       *
722       * @param a1 the first array to compare
723       * @param a2 the second array to compare
724       * @return true if a1 and a2 are both null, or if a2 is of the same length
725       *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
726       */
727      public static boolean equals(char[] a1, char[] a2)
728      {
729        // Quick test which saves comparing elements of the same array, and also
730        // catches the case that both are null.
731        if (a1 == a2)
732          return true;
733    
734        if (null == a1 || null == a2)
735          return false;
736        
737        // If they're the same length, test each element
738        if (a1.length == a2.length)
739          {
740            int i = a1.length;
741            while (--i >= 0)
742              if (a1[i] != a2[i])
743                return false;
744            return true;
745          }
746        return false;
747      }
748    
749      /**
750       * Compare two short arrays for equality.
751       *
752       * @param a1 the first array to compare
753       * @param a2 the second array to compare
754       * @return true if a1 and a2 are both null, or if a2 is of the same length
755       *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
756       */
757      public static boolean equals(short[] a1, short[] a2)
758      {
759        // Quick test which saves comparing elements of the same array, and also
760        // catches the case that both are null.
761        if (a1 == a2)
762          return true;
763    
764        if (null == a1 || null == a2)
765          return false;
766    
767        // If they're the same length, test each element
768        if (a1.length == a2.length)
769          {
770            int i = a1.length;
771            while (--i >= 0)
772              if (a1[i] != a2[i])
773                return false;
774            return true;
775          }
776        return false;
777      }
778    
779      /**
780       * Compare two int arrays for equality.
781       *
782       * @param a1 the first array to compare
783       * @param a2 the second array to compare
784       * @return true if a1 and a2 are both null, or if a2 is of the same length
785       *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
786       */
787      public static boolean equals(int[] a1, int[] a2)
788      {
789        // Quick test which saves comparing elements of the same array, and also
790        // catches the case that both are null.
791        if (a1 == a2)
792          return true;
793    
794        if (null == a1 || null == a2)
795          return false;
796    
797        // If they're the same length, test each element
798        if (a1.length == a2.length)
799          {
800            int i = a1.length;
801            while (--i >= 0)
802              if (a1[i] != a2[i])
803                return false;
804            return true;
805          }
806        return false;
807      }
808    
809      /**
810       * Compare two long arrays for equality.
811       *
812       * @param a1 the first array to compare
813       * @param a2 the second array to compare
814       * @return true if a1 and a2 are both null, or if a2 is of the same length
815       *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
816       */
817      public static boolean equals(long[] a1, long[] a2)
818      {
819        // Quick test which saves comparing elements of the same array, and also
820        // catches the case that both are null.
821        if (a1 == a2)
822          return true;
823    
824        if (null == a1 || null == a2)
825          return false;
826    
827        // If they're the same length, test each element
828        if (a1.length == a2.length)
829          {
830            int i = a1.length;
831            while (--i >= 0)
832              if (a1[i] != a2[i])
833                return false;
834            return true;
835          }
836        return false;
837      }
838    
839      /**
840       * Compare two float arrays for equality.
841       *
842       * @param a1 the first array to compare
843       * @param a2 the second array to compare
844       * @return true if a1 and a2 are both null, or if a2 is of the same length
845       *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
846       */
847      public static boolean equals(float[] a1, float[] a2)
848      {
849        // Quick test which saves comparing elements of the same array, and also
850        // catches the case that both are null.
851        if (a1 == a2)
852          return true;
853    
854        if (null == a1 || null == a2)
855          return false;
856    
857        // Must use Float.compare to take into account NaN, +-0.
858        // If they're the same length, test each element
859        if (a1.length == a2.length)
860          {
861            int i = a1.length;
862            while (--i >= 0)
863              if (Float.compare(a1[i], a2[i]) != 0)
864                return false;
865            return true;
866          }
867        return false;
868      }
869    
870      /**
871       * Compare two double arrays for equality.
872       *
873       * @param a1 the first array to compare
874       * @param a2 the second array to compare
875       * @return true if a1 and a2 are both null, or if a2 is of the same length
876       *         as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
877       */
878      public static boolean equals(double[] a1, double[] a2)
879      {
880        // Quick test which saves comparing elements of the same array, and also
881        // catches the case that both are null.
882        if (a1 == a2)
883          return true;
884    
885        if (null == a1 || null == a2)
886          return false;
887        
888        // Must use Double.compare to take into account NaN, +-0.
889        // If they're the same length, test each element
890        if (a1.length == a2.length)
891          {
892            int i = a1.length;
893            while (--i >= 0)
894              if (Double.compare(a1[i], a2[i]) != 0)
895                return false;
896            return true;
897          }
898        return false;
899      }
900    
901      /**
902       * Compare two Object arrays for equality.
903       *
904       * @param a1 the first array to compare
905       * @param a2 the second array to compare
906       * @return true if a1 and a2 are both null, or if a1 is of the same length
907       *         as a2, and for each 0 <= i < a.length, a1[i] == null ?
908       *         a2[i] == null : a1[i].equals(a2[i]).
909       */
910      public static boolean equals(Object[] a1, Object[] a2)
911      {
912        // Quick test which saves comparing elements of the same array, and also
913        // catches the case that both are null.
914        if (a1 == a2)
915          return true;
916    
917        if (null == a1 || null == a2)
918          return false;
919        
920        // If they're the same length, test each element
921        if (a1.length == a2.length)
922          {
923            int i = a1.length;
924            while (--i >= 0)
925              if (! AbstractCollection.equals(a1[i], a2[i]))
926                return false;
927            return true;
928          }
929        return false;
930      }
931    
932    
933    // fill
934      /**
935       * Fill an array with a boolean value.
936       *
937       * @param a the array to fill
938       * @param val the value to fill it with
939       */
940      public static void fill(boolean[] a, boolean val)
941      {
942        fill(a, 0, a.length, val);
943      }
944    
945      /**
946       * Fill a range of an array with a boolean value.
947       *
948       * @param a the array to fill
949       * @param fromIndex the index to fill from, inclusive
950       * @param toIndex the index to fill to, exclusive
951       * @param val the value to fill with
952       * @throws IllegalArgumentException if fromIndex &gt; toIndex
953       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
954       *         || toIndex &gt; a.length
955       */
956      public static void fill(boolean[] a, int fromIndex, int toIndex, boolean val)
957      {
958        if (fromIndex > toIndex)
959          throw new IllegalArgumentException();
960        for (int i = fromIndex; i < toIndex; i++)
961          a[i] = val;
962      }
963    
964      /**
965       * Fill an array with a byte value.
966       *
967       * @param a the array to fill
968       * @param val the value to fill it with
969       */
970      public static void fill(byte[] a, byte val)
971      {
972        fill(a, 0, a.length, val);
973      }
974    
975      /**
976       * Fill a range of an array with a byte value.
977       *
978       * @param a the array to fill
979       * @param fromIndex the index to fill from, inclusive
980       * @param toIndex the index to fill to, exclusive
981       * @param val the value to fill with
982       * @throws IllegalArgumentException if fromIndex &gt; toIndex
983       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
984       *         || toIndex &gt; a.length
985       */
986      public static void fill(byte[] a, int fromIndex, int toIndex, byte val)
987      {
988        if (fromIndex > toIndex)
989          throw new IllegalArgumentException();
990        for (int i = fromIndex; i < toIndex; i++)
991          a[i] = val;
992      }
993    
994      /**
995       * Fill an array with a char value.
996       *
997       * @param a the array to fill
998       * @param val the value to fill it with
999       */
1000      public static void fill(char[] a, char val)
1001      {
1002        fill(a, 0, a.length, val);
1003      }
1004    
1005      /**
1006       * Fill a range of an array with a char value.
1007       *
1008       * @param a the array to fill
1009       * @param fromIndex the index to fill from, inclusive
1010       * @param toIndex the index to fill to, exclusive
1011       * @param val the value to fill with
1012       * @throws IllegalArgumentException if fromIndex &gt; toIndex
1013       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1014       *         || toIndex &gt; a.length
1015       */
1016      public static void fill(char[] a, int fromIndex, int toIndex, char val)
1017      {
1018        if (fromIndex > toIndex)
1019          throw new IllegalArgumentException();
1020        for (int i = fromIndex; i < toIndex; i++)
1021          a[i] = val;
1022      }
1023    
1024      /**
1025       * Fill an array with a short value.
1026       *
1027       * @param a the array to fill
1028       * @param val the value to fill it with
1029       */
1030      public static void fill(short[] a, short val)
1031      {
1032        fill(a, 0, a.length, val);
1033      }
1034    
1035      /**
1036       * Fill a range of an array with a short value.
1037       *
1038       * @param a the array to fill
1039       * @param fromIndex the index to fill from, inclusive
1040       * @param toIndex the index to fill to, exclusive
1041       * @param val the value to fill with
1042       * @throws IllegalArgumentException if fromIndex &gt; toIndex
1043       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1044       *         || toIndex &gt; a.length
1045       */
1046      public static void fill(short[] a, int fromIndex, int toIndex, short val)
1047      {
1048        if (fromIndex > toIndex)
1049          throw new IllegalArgumentException();
1050        for (int i = fromIndex; i < toIndex; i++)
1051          a[i] = val;
1052      }
1053    
1054      /**
1055       * Fill an array with an int value.
1056       *
1057       * @param a the array to fill
1058       * @param val the value to fill it with
1059       */
1060      public static void fill(int[] a, int val)
1061      {
1062        fill(a, 0, a.length, val);
1063      }
1064    
1065      /**
1066       * Fill a range of an array with an int value.
1067       *
1068       * @param a the array to fill
1069       * @param fromIndex the index to fill from, inclusive
1070       * @param toIndex the index to fill to, exclusive
1071       * @param val the value to fill with
1072       * @throws IllegalArgumentException if fromIndex &gt; toIndex
1073       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1074       *         || toIndex &gt; a.length
1075       */
1076      public static void fill(int[] a, int fromIndex, int toIndex, int val)
1077      {
1078        if (fromIndex > toIndex)
1079          throw new IllegalArgumentException();
1080        for (int i = fromIndex; i < toIndex; i++)
1081          a[i] = val;
1082      }
1083    
1084      /**
1085       * Fill an array with a long value.
1086       *
1087       * @param a the array to fill
1088       * @param val the value to fill it with
1089       */
1090      public static void fill(long[] a, long val)
1091      {
1092        fill(a, 0, a.length, val);
1093      }
1094    
1095      /**
1096       * Fill a range of an array with a long value.
1097       *
1098       * @param a the array to fill
1099       * @param fromIndex the index to fill from, inclusive
1100       * @param toIndex the index to fill to, exclusive
1101       * @param val the value to fill with
1102       * @throws IllegalArgumentException if fromIndex &gt; toIndex
1103       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1104       *         || toIndex &gt; a.length
1105       */
1106      public static void fill(long[] a, int fromIndex, int toIndex, long val)
1107      {
1108        if (fromIndex > toIndex)
1109          throw new IllegalArgumentException();
1110        for (int i = fromIndex; i < toIndex; i++)
1111          a[i] = val;
1112      }
1113    
1114      /**
1115       * Fill an array with a float value.
1116       *
1117       * @param a the array to fill
1118       * @param val the value to fill it with
1119       */
1120      public static void fill(float[] a, float val)
1121      {
1122        fill(a, 0, a.length, val);
1123      }
1124    
1125      /**
1126       * Fill a range of an array with a float value.
1127       *
1128       * @param a the array to fill
1129       * @param fromIndex the index to fill from, inclusive
1130       * @param toIndex the index to fill to, exclusive
1131       * @param val the value to fill with
1132       * @throws IllegalArgumentException if fromIndex &gt; toIndex
1133       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1134       *         || toIndex &gt; a.length
1135       */
1136      public static void fill(float[] a, int fromIndex, int toIndex, float val)
1137      {
1138        if (fromIndex > toIndex)
1139          throw new IllegalArgumentException();
1140        for (int i = fromIndex; i < toIndex; i++)
1141          a[i] = val;
1142      }
1143    
1144      /**
1145       * Fill an array with a double value.
1146       *
1147       * @param a the array to fill
1148       * @param val the value to fill it with
1149       */
1150      public static void fill(double[] a, double val)
1151      {
1152        fill(a, 0, a.length, val);
1153      }
1154    
1155      /**
1156       * Fill a range of an array with a double value.
1157       *
1158       * @param a the array to fill
1159       * @param fromIndex the index to fill from, inclusive
1160       * @param toIndex the index to fill to, exclusive
1161       * @param val the value to fill with
1162       * @throws IllegalArgumentException if fromIndex &gt; toIndex
1163       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1164       *         || toIndex &gt; a.length
1165       */
1166      public static void fill(double[] a, int fromIndex, int toIndex, double val)
1167      {
1168        if (fromIndex > toIndex)
1169          throw new IllegalArgumentException();
1170        for (int i = fromIndex; i < toIndex; i++)
1171          a[i] = val;
1172      }
1173    
1174      /**
1175       * Fill an array with an Object value.
1176       *
1177       * @param a the array to fill
1178       * @param val the value to fill it with
1179       * @throws ClassCastException if val is not an instance of the element
1180       *         type of a.
1181       */
1182      public static void fill(Object[] a, Object val)
1183      {
1184        fill(a, 0, a.length, val);
1185      }
1186    
1187      /**
1188       * Fill a range of an array with an Object value.
1189       *
1190       * @param a the array to fill
1191       * @param fromIndex the index to fill from, inclusive
1192       * @param toIndex the index to fill to, exclusive
1193       * @param val the value to fill with
1194       * @throws ClassCastException if val is not an instance of the element
1195       *         type of a.
1196       * @throws IllegalArgumentException if fromIndex &gt; toIndex
1197       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1198       *         || toIndex &gt; a.length
1199       */
1200      public static void fill(Object[] a, int fromIndex, int toIndex, Object val)
1201      {
1202        if (fromIndex > toIndex)
1203          throw new IllegalArgumentException();
1204        for (int i = fromIndex; i < toIndex; i++)
1205          a[i] = val;
1206      }
1207    
1208    
1209    // sort
1210      // Thanks to Paul Fisher (rao@gnu.org) for finding this quicksort algorithm
1211      // as specified by Sun and porting it to Java. The algorithm is an optimised
1212      // quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
1213      // "Engineering a Sort Function", Software-Practice and Experience, Vol.
1214      // 23(11) P. 1249-1265 (November 1993). This algorithm gives n*log(n)
1215      // performance on many arrays that would take quadratic time with a standard
1216      // quicksort.
1217    
1218      /**
1219       * Performs a stable sort on the elements, arranging them according to their
1220       * natural order.
1221       *
1222       * @param a the byte array to sort
1223       */
1224      public static void sort(byte[] a)
1225      {
1226        qsort(a, 0, a.length);
1227      }
1228    
1229      /**
1230       * Performs a stable sort on the elements, arranging them according to their
1231       * natural order.
1232       *
1233       * @param a the byte array to sort
1234       * @param fromIndex the first index to sort (inclusive)
1235       * @param toIndex the last index to sort (exclusive)
1236       * @throws IllegalArgumentException if fromIndex &gt; toIndex
1237       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1238       *         || toIndex &gt; a.length
1239       */
1240      public static void sort(byte[] a, int fromIndex, int toIndex)
1241      {
1242        if (fromIndex > toIndex)
1243          throw new IllegalArgumentException();
1244        if (fromIndex < 0)
1245          throw new ArrayIndexOutOfBoundsException();
1246        qsort(a, fromIndex, toIndex - fromIndex);
1247      }
1248    
1249      /**
1250       * Finds the index of the median of three array elements.
1251       *
1252       * @param a the first index
1253       * @param b the second index
1254       * @param c the third index
1255       * @param d the array
1256       * @return the index (a, b, or c) which has the middle value of the three
1257       */
1258      private static int med3(int a, int b, int c, byte[] d)
1259      {
1260        return (d[a] < d[b]
1261                ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1262                : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1263      }
1264    
1265      /**
1266       * Swaps the elements at two locations of an array
1267       *
1268       * @param i the first index
1269       * @param j the second index
1270       * @param a the array
1271       */
1272      private static void swap(int i, int j, byte[] a)
1273      {
1274        byte c = a[i];
1275        a[i] = a[j];
1276        a[j] = c;
1277      }
1278    
1279      /**
1280       * Swaps two ranges of an array.
1281       *
1282       * @param i the first range start
1283       * @param j the second range start
1284       * @param n the element count
1285       * @param a the array
1286       */
1287      private static void vecswap(int i, int j, int n, byte[] a)
1288      {
1289        for ( ; n > 0; i++, j++, n--)
1290          swap(i, j, a);
1291      }
1292    
1293      /**
1294       * Performs a recursive modified quicksort.
1295       *
1296       * @param array the array to sort
1297       * @param from the start index (inclusive)
1298       * @param count the number of elements to sort
1299       */
1300      private static void qsort(byte[] array, int from, int count)
1301      {
1302        // Use an insertion sort on small arrays.
1303        if (count <= 7)
1304          {
1305            for (int i = from + 1; i < from + count; i++)
1306              for (int j = i; j > from && array[j - 1] > array[j]; j--)
1307                swap(j, j - 1, array);
1308            return;
1309          }
1310    
1311        // Determine a good median element.
1312        int mid = from + count / 2;
1313        int lo = from;
1314        int hi = from + count - 1;
1315    
1316        if (count > 40)
1317          { // big arrays, pseudomedian of 9
1318            int s = count / 8;
1319            lo = med3(lo, lo + s, lo + 2 * s, array);
1320            mid = med3(mid - s, mid, mid + s, array);
1321            hi = med3(hi - 2 * s, hi - s, hi, array);
1322          }
1323        mid = med3(lo, mid, hi, array);
1324    
1325        int a, b, c, d;
1326        int comp;
1327    
1328        // Pull the median element out of the fray, and use it as a pivot.
1329        swap(from, mid, array);
1330        a = b = from;
1331        c = d = from + count - 1;
1332    
1333        // Repeatedly move b and c to each other, swapping elements so
1334        // that all elements before index b are less than the pivot, and all
1335        // elements after index c are greater than the pivot. a and b track
1336        // the elements equal to the pivot.
1337        while (true)
1338          {
1339            while (b <= c && (comp = array[b] - array[from]) <= 0)
1340              {
1341                if (comp == 0)
1342                  {
1343                    swap(a, b, array);
1344                    a++;
1345                  }
1346                b++;
1347              }
1348            while (c >= b && (comp = array[c] - array[from]) >= 0)
1349              {
1350                if (comp == 0)
1351                  {
1352                    swap(c, d, array);
1353                    d--;
1354                  }
1355                c--;
1356              }
1357            if (b > c)
1358              break;
1359            swap(b, c, array);
1360            b++;
1361            c--;
1362          }
1363    
1364        // Swap pivot(s) back in place, the recurse on left and right sections.
1365        hi = from + count;
1366        int span;
1367        span = Math.min(a - from, b - a);
1368        vecswap(from, b - span, span, array);
1369    
1370        span = Math.min(d - c, hi - d - 1);
1371        vecswap(b, hi - span, span, array);
1372    
1373        span = b - a;
1374        if (span > 1)
1375          qsort(array, from, span);
1376    
1377        span = d - c;
1378        if (span > 1)
1379          qsort(array, hi - span, span);
1380      }
1381    
1382      /**
1383       * Performs a stable sort on the elements, arranging them according to their
1384       * natural order.
1385       *
1386       * @param a the char array to sort
1387       */
1388      public static void sort(char[] a)
1389      {
1390        qsort(a, 0, a.length);
1391      }
1392    
1393      /**
1394       * Performs a stable sort on the elements, arranging them according to their
1395       * natural order.
1396       *
1397       * @param a the char array to sort
1398       * @param fromIndex the first index to sort (inclusive)
1399       * @param toIndex the last index to sort (exclusive)
1400       * @throws IllegalArgumentException if fromIndex &gt; toIndex
1401       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1402       *         || toIndex &gt; a.length
1403       */
1404      public static void sort(char[] a, int fromIndex, int toIndex)
1405      {
1406        if (fromIndex > toIndex)
1407          throw new IllegalArgumentException();
1408        if (fromIndex < 0)
1409          throw new ArrayIndexOutOfBoundsException();
1410        qsort(a, fromIndex, toIndex - fromIndex);
1411      }
1412    
1413      /**
1414       * Finds the index of the median of three array elements.
1415       *
1416       * @param a the first index
1417       * @param b the second index
1418       * @param c the third index
1419       * @param d the array
1420       * @return the index (a, b, or c) which has the middle value of the three
1421       */
1422      private static int med3(int a, int b, int c, char[] d)
1423      {
1424        return (d[a] < d[b]
1425                ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1426                : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1427      }
1428    
1429      /**
1430       * Swaps the elements at two locations of an array
1431       *
1432       * @param i the first index
1433       * @param j the second index
1434       * @param a the array
1435       */
1436      private static void swap(int i, int j, char[] a)
1437      {
1438        char c = a[i];
1439        a[i] = a[j];
1440        a[j] = c;
1441      }
1442    
1443      /**
1444       * Swaps two ranges of an array.
1445       *
1446       * @param i the first range start
1447       * @param j the second range start
1448       * @param n the element count
1449       * @param a the array
1450       */
1451      private static void vecswap(int i, int j, int n, char[] a)
1452      {
1453        for ( ; n > 0; i++, j++, n--)
1454          swap(i, j, a);
1455      }
1456    
1457      /**
1458       * Performs a recursive modified quicksort.
1459       *
1460       * @param array the array to sort
1461       * @param from the start index (inclusive)
1462       * @param count the number of elements to sort
1463       */
1464      private static void qsort(char[] array, int from, int count)
1465      {
1466        // Use an insertion sort on small arrays.
1467        if (count <= 7)
1468          {
1469            for (int i = from + 1; i < from + count; i++)
1470              for (int j = i; j > from && array[j - 1] > array[j]; j--)
1471                swap(j, j - 1, array);
1472            return;
1473          }
1474    
1475        // Determine a good median element.
1476        int mid = from + count / 2;
1477        int lo = from;
1478        int hi = from + count - 1;
1479    
1480        if (count > 40)
1481          { // big arrays, pseudomedian of 9
1482            int s = count / 8;
1483            lo = med3(lo, lo + s, lo + 2 * s, array);
1484            mid = med3(mid - s, mid, mid + s, array);
1485            hi = med3(hi - 2 * s, hi - s, hi, array);
1486          }
1487        mid = med3(lo, mid, hi, array);
1488    
1489        int a, b, c, d;
1490        int comp;
1491    
1492        // Pull the median element out of the fray, and use it as a pivot.
1493        swap(from, mid, array);
1494        a = b = from;
1495        c = d = from + count - 1;
1496    
1497        // Repeatedly move b and c to each other, swapping elements so
1498        // that all elements before index b are less than the pivot, and all
1499        // elements after index c are greater than the pivot. a and b track
1500        // the elements equal to the pivot.
1501        while (true)
1502          {
1503            while (b <= c && (comp = array[b] - array[from]) <= 0)
1504              {
1505                if (comp == 0)
1506                  {
1507                    swap(a, b, array);
1508                    a++;
1509                  }
1510                b++;
1511              }
1512            while (c >= b && (comp = array[c] - array[from]) >= 0)
1513              {
1514                if (comp == 0)
1515                  {
1516                    swap(c, d, array);
1517                    d--;
1518                  }
1519                c--;
1520              }
1521            if (b > c)
1522              break;
1523            swap(b, c, array);
1524            b++;
1525            c--;
1526          }
1527    
1528        // Swap pivot(s) back in place, the recurse on left and right sections.
1529        hi = from + count;
1530        int span;
1531        span = Math.min(a - from, b - a);
1532        vecswap(from, b - span, span, array);
1533    
1534        span = Math.min(d - c, hi - d - 1);
1535        vecswap(b, hi - span, span, array);
1536    
1537        span = b - a;
1538        if (span > 1)
1539          qsort(array, from, span);
1540    
1541        span = d - c;
1542        if (span > 1)
1543          qsort(array, hi - span, span);
1544      }
1545    
1546      /**
1547       * Performs a stable sort on the elements, arranging them according to their
1548       * natural order.
1549       *
1550       * @param a the short array to sort
1551       */
1552      public static void sort(short[] a)
1553      {
1554        qsort(a, 0, a.length);
1555      }
1556    
1557      /**
1558       * Performs a stable sort on the elements, arranging them according to their
1559       * natural order.
1560       *
1561       * @param a the short array to sort
1562       * @param fromIndex the first index to sort (inclusive)
1563       * @param toIndex the last index to sort (exclusive)
1564       * @throws IllegalArgumentException if fromIndex &gt; toIndex
1565       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1566       *         || toIndex &gt; a.length
1567       */
1568      public static void sort(short[] a, int fromIndex, int toIndex)
1569      {
1570        if (fromIndex > toIndex)
1571          throw new IllegalArgumentException();
1572        if (fromIndex < 0)
1573          throw new ArrayIndexOutOfBoundsException();
1574        qsort(a, fromIndex, toIndex - fromIndex);
1575      }
1576    
1577      /**
1578       * Finds the index of the median of three array elements.
1579       *
1580       * @param a the first index
1581       * @param b the second index
1582       * @param c the third index
1583       * @param d the array
1584       * @return the index (a, b, or c) which has the middle value of the three
1585       */
1586      private static int med3(int a, int b, int c, short[] d)
1587      {
1588        return (d[a] < d[b]
1589                ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1590                : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1591      }
1592    
1593      /**
1594       * Swaps the elements at two locations of an array
1595       *
1596       * @param i the first index
1597       * @param j the second index
1598       * @param a the array
1599       */
1600      private static void swap(int i, int j, short[] a)
1601      {
1602        short c = a[i];
1603        a[i] = a[j];
1604        a[j] = c;
1605      }
1606    
1607      /**
1608       * Swaps two ranges of an array.
1609       *
1610       * @param i the first range start
1611       * @param j the second range start
1612       * @param n the element count
1613       * @param a the array
1614       */
1615      private static void vecswap(int i, int j, int n, short[] a)
1616      {
1617        for ( ; n > 0; i++, j++, n--)
1618          swap(i, j, a);
1619      }
1620    
1621      /**
1622       * Performs a recursive modified quicksort.
1623       *
1624       * @param array the array to sort
1625       * @param from the start index (inclusive)
1626       * @param count the number of elements to sort
1627       */
1628      private static void qsort(short[] array, int from, int count)
1629      {
1630        // Use an insertion sort on small arrays.
1631        if (count <= 7)
1632          {
1633            for (int i = from + 1; i < from + count; i++)
1634              for (int j = i; j > from && array[j - 1] > array[j]; j--)
1635                swap(j, j - 1, array);
1636            return;
1637          }
1638    
1639        // Determine a good median element.
1640        int mid = from + count / 2;
1641        int lo = from;
1642        int hi = from + count - 1;
1643    
1644        if (count > 40)
1645          { // big arrays, pseudomedian of 9
1646            int s = count / 8;
1647            lo = med3(lo, lo + s, lo + 2 * s, array);
1648            mid = med3(mid - s, mid, mid + s, array);
1649            hi = med3(hi - 2 * s, hi - s, hi, array);
1650          }
1651        mid = med3(lo, mid, hi, array);
1652    
1653        int a, b, c, d;
1654        int comp;
1655    
1656        // Pull the median element out of the fray, and use it as a pivot.
1657        swap(from, mid, array);
1658        a = b = from;
1659        c = d = from + count - 1;
1660    
1661        // Repeatedly move b and c to each other, swapping elements so
1662        // that all elements before index b are less than the pivot, and all
1663        // elements after index c are greater than the pivot. a and b track
1664        // the elements equal to the pivot.
1665        while (true)
1666          {
1667            while (b <= c && (comp = array[b] - array[from]) <= 0)
1668              {
1669                if (comp == 0)
1670                  {
1671                    swap(a, b, array);
1672                    a++;
1673                  }
1674                b++;
1675              }
1676            while (c >= b && (comp = array[c] - array[from]) >= 0)
1677              {
1678                if (comp == 0)
1679                  {
1680                    swap(c, d, array);
1681                    d--;
1682                  }
1683                c--;
1684              }
1685            if (b > c)
1686              break;
1687            swap(b, c, array);
1688            b++;
1689            c--;
1690          }
1691    
1692        // Swap pivot(s) back in place, the recurse on left and right sections.
1693        hi = from + count;
1694        int span;
1695        span = Math.min(a - from, b - a);
1696        vecswap(from, b - span, span, array);
1697    
1698        span = Math.min(d - c, hi - d - 1);
1699        vecswap(b, hi - span, span, array);
1700    
1701        span = b - a;
1702        if (span > 1)
1703          qsort(array, from, span);
1704    
1705        span = d - c;
1706        if (span > 1)
1707          qsort(array, hi - span, span);
1708      }
1709    
1710      /**
1711       * Performs a stable sort on the elements, arranging them according to their
1712       * natural order.
1713       *
1714       * @param a the int array to sort
1715       */
1716      public static void sort(int[] a)
1717      {
1718        qsort(a, 0, a.length);
1719      }
1720    
1721      /**
1722       * Performs a stable sort on the elements, arranging them according to their
1723       * natural order.
1724       *
1725       * @param a the int array to sort
1726       * @param fromIndex the first index to sort (inclusive)
1727       * @param toIndex the last index to sort (exclusive)
1728       * @throws IllegalArgumentException if fromIndex &gt; toIndex
1729       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1730       *         || toIndex &gt; a.length
1731       */
1732      public static void sort(int[] a, int fromIndex, int toIndex)
1733      {
1734        if (fromIndex > toIndex)
1735          throw new IllegalArgumentException();
1736        if (fromIndex < 0)
1737          throw new ArrayIndexOutOfBoundsException();
1738        qsort(a, fromIndex, toIndex - fromIndex);
1739      }
1740    
1741      /**
1742       * Finds the index of the median of three array elements.
1743       *
1744       * @param a the first index
1745       * @param b the second index
1746       * @param c the third index
1747       * @param d the array
1748       * @return the index (a, b, or c) which has the middle value of the three
1749       */
1750      private static int med3(int a, int b, int c, int[] d)
1751      {
1752        return (d[a] < d[b]
1753                ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1754                : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1755      }
1756    
1757      /**
1758       * Swaps the elements at two locations of an array
1759       *
1760       * @param i the first index
1761       * @param j the second index
1762       * @param a the array
1763       */
1764      private static void swap(int i, int j, int[] a)
1765      {
1766        int c = a[i];
1767        a[i] = a[j];
1768        a[j] = c;
1769      }
1770    
1771      /**
1772       * Swaps two ranges of an array.
1773       *
1774       * @param i the first range start
1775       * @param j the second range start
1776       * @param n the element count
1777       * @param a the array
1778       */
1779      private static void vecswap(int i, int j, int n, int[] a)
1780      {
1781        for ( ; n > 0; i++, j++, n--)
1782          swap(i, j, a);
1783      }
1784    
1785      /**
1786       * Compares two integers in natural order, since a - b is inadequate.
1787       *
1788       * @param a the first int
1789       * @param b the second int
1790       * @return &lt; 0, 0, or &gt; 0 accorting to the comparison
1791       */
1792      private static int compare(int a, int b)
1793      {
1794        return a < b ? -1 : a == b ? 0 : 1;
1795      }
1796    
1797      /**
1798       * Performs a recursive modified quicksort.
1799       *
1800       * @param array the array to sort
1801       * @param from the start index (inclusive)
1802       * @param count the number of elements to sort
1803       */
1804      private static void qsort(int[] array, int from, int count)
1805      {
1806        // Use an insertion sort on small arrays.
1807        if (count <= 7)
1808          {
1809            for (int i = from + 1; i < from + count; i++)
1810              for (int j = i; j > from && array[j - 1] > array[j]; j--)
1811                swap(j, j - 1, array);
1812            return;
1813          }
1814    
1815        // Determine a good median element.
1816        int mid = from + count / 2;
1817        int lo = from;
1818        int hi = from + count - 1;
1819    
1820        if (count > 40)
1821          { // big arrays, pseudomedian of 9
1822            int s = count / 8;
1823            lo = med3(lo, lo + s, lo + 2 * s, array);
1824            mid = med3(mid - s, mid, mid + s, array);
1825            hi = med3(hi - 2 * s, hi - s, hi, array);
1826          }
1827        mid = med3(lo, mid, hi, array);
1828    
1829        int a, b, c, d;
1830        int comp;
1831    
1832        // Pull the median element out of the fray, and use it as a pivot.
1833        swap(from, mid, array);
1834        a = b = from;
1835        c = d = from + count - 1;
1836    
1837        // Repeatedly move b and c to each other, swapping elements so
1838        // that all elements before index b are less than the pivot, and all
1839        // elements after index c are greater than the pivot. a and b track
1840        // the elements equal to the pivot.
1841        while (true)
1842          {
1843            while (b <= c && (comp = compare(array[b], array[from])) <= 0)
1844              {
1845                if (comp == 0)
1846                  {
1847                    swap(a, b, array);
1848                    a++;
1849                  }
1850                b++;
1851              }
1852            while (c >= b && (comp = compare(array[c], array[from])) >= 0)
1853              {
1854                if (comp == 0)
1855                  {
1856                    swap(c, d, array);
1857                    d--;
1858                  }
1859                c--;
1860              }
1861            if (b > c)
1862              break;
1863            swap(b, c, array);
1864            b++;
1865            c--;
1866          }
1867    
1868        // Swap pivot(s) back in place, the recurse on left and right sections.
1869        hi = from + count;
1870        int span;
1871        span = Math.min(a - from, b - a);
1872        vecswap(from, b - span, span, array);
1873    
1874        span = Math.min(d - c, hi - d - 1);
1875        vecswap(b, hi - span, span, array);
1876    
1877        span = b - a;
1878        if (span > 1)
1879          qsort(array, from, span);
1880    
1881        span = d - c;
1882        if (span > 1)
1883          qsort(array, hi - span, span);
1884      }
1885    
1886      /**
1887       * Performs a stable sort on the elements, arranging them according to their
1888       * natural order.
1889       *
1890       * @param a the long array to sort
1891       */
1892      public static void sort(long[] a)
1893      {
1894        qsort(a, 0, a.length);
1895      }
1896    
1897      /**
1898       * Performs a stable sort on the elements, arranging them according to their
1899       * natural order.
1900       *
1901       * @param a the long array to sort
1902       * @param fromIndex the first index to sort (inclusive)
1903       * @param toIndex the last index to sort (exclusive)
1904       * @throws IllegalArgumentException if fromIndex &gt; toIndex
1905       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
1906       *         || toIndex &gt; a.length
1907       */
1908      public static void sort(long[] a, int fromIndex, int toIndex)
1909      {
1910        if (fromIndex > toIndex)
1911          throw new IllegalArgumentException();
1912        if (fromIndex < 0)
1913          throw new ArrayIndexOutOfBoundsException();
1914        qsort(a, fromIndex, toIndex - fromIndex);
1915      }
1916    
1917      /**
1918       * Finds the index of the median of three array elements.
1919       *
1920       * @param a the first index
1921       * @param b the second index
1922       * @param c the third index
1923       * @param d the array
1924       * @return the index (a, b, or c) which has the middle value of the three
1925       */
1926      private static int med3(int a, int b, int c, long[] d)
1927      {
1928        return (d[a] < d[b]
1929                ? (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
1930                : (d[b] > d[c] ? b : d[a] > d[c] ? c : a));
1931      }
1932    
1933      /**
1934       * Swaps the elements at two locations of an array
1935       *
1936       * @param i the first index
1937       * @param j the second index
1938       * @param a the array
1939       */
1940      private static void swap(int i, int j, long[] a)
1941      {
1942        long c = a[i];
1943        a[i] = a[j];
1944        a[j] = c;
1945      }
1946    
1947      /**
1948       * Swaps two ranges of an array.
1949       *
1950       * @param i the first range start
1951       * @param j the second range start
1952       * @param n the element count
1953       * @param a the array
1954       */
1955      private static void vecswap(int i, int j, int n, long[] a)
1956      {
1957        for ( ; n > 0; i++, j++, n--)
1958          swap(i, j, a);
1959      }
1960    
1961      /**
1962       * Compares two longs in natural order, since a - b is inadequate.
1963       *
1964       * @param a the first long
1965       * @param b the second long
1966       * @return &lt; 0, 0, or &gt; 0 accorting to the comparison
1967       */
1968      private static int compare(long a, long b)
1969      {
1970        return a < b ? -1 : a == b ? 0 : 1;
1971      }
1972    
1973      /**
1974       * Performs a recursive modified quicksort.
1975       *
1976       * @param array the array to sort
1977       * @param from the start index (inclusive)
1978       * @param count the number of elements to sort
1979       */
1980      private static void qsort(long[] array, int from, int count)
1981      {
1982        // Use an insertion sort on small arrays.
1983        if (count <= 7)
1984          {
1985            for (int i = from + 1; i < from + count; i++)
1986              for (int j = i; j > from && array[j - 1] > array[j]; j--)
1987                swap(j, j - 1, array);
1988            return;
1989          }
1990    
1991        // Determine a good median element.
1992        int mid = from + count / 2;
1993        int lo = from;
1994        int hi = from + count - 1;
1995    
1996        if (count > 40)
1997          { // big arrays, pseudomedian of 9
1998            int s = count / 8;
1999            lo = med3(lo, lo + s, lo + 2 * s, array);
2000            mid = med3(mid - s, mid, mid + s, array);
2001            hi = med3(hi - 2 * s, hi - s, hi, array);
2002          }
2003        mid = med3(lo, mid, hi, array);
2004    
2005        int a, b, c, d;
2006        int comp;
2007    
2008        // Pull the median element out of the fray, and use it as a pivot.
2009        swap(from, mid, array);
2010        a = b = from;
2011        c = d = from + count - 1;
2012    
2013        // Repeatedly move b and c to each other, swapping elements so
2014        // that all elements before index b are less than the pivot, and all
2015        // elements after index c are greater than the pivot. a and b track
2016        // the elements equal to the pivot.
2017        while (true)
2018          {
2019            while (b <= c && (comp = compare(array[b], array[from])) <= 0)
2020              {
2021                if (comp == 0)
2022                  {
2023                    swap(a, b, array);
2024                    a++;
2025                  }
2026                b++;
2027              }
2028            while (c >= b && (comp = compare(array[c], array[from])) >= 0)
2029              {
2030                if (comp == 0)
2031                  {
2032                    swap(c, d, array);
2033                    d--;
2034                  }
2035                c--;
2036              }
2037            if (b > c)
2038              break;
2039            swap(b, c, array);
2040            b++;
2041            c--;
2042          }
2043    
2044        // Swap pivot(s) back in place, the recurse on left and right sections.
2045        hi = from + count;
2046        int span;
2047        span = Math.min(a - from, b - a);
2048        vecswap(from, b - span, span, array);
2049    
2050        span = Math.min(d - c, hi - d - 1);
2051        vecswap(b, hi - span, span, array);
2052    
2053        span = b - a;
2054        if (span > 1)
2055          qsort(array, from, span);
2056    
2057        span = d - c;
2058        if (span > 1)
2059          qsort(array, hi - span, span);
2060      }
2061    
2062      /**
2063       * Performs a stable sort on the elements, arranging them according to their
2064       * natural order.
2065       *
2066       * @param a the float array to sort
2067       */
2068      public static void sort(float[] a)
2069      {
2070        qsort(a, 0, a.length);
2071      }
2072    
2073      /**
2074       * Performs a stable sort on the elements, arranging them according to their
2075       * natural order.
2076       *
2077       * @param a the float array to sort
2078       * @param fromIndex the first index to sort (inclusive)
2079       * @param toIndex the last index to sort (exclusive)
2080       * @throws IllegalArgumentException if fromIndex &gt; toIndex
2081       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
2082       *         || toIndex &gt; a.length
2083       */
2084      public static void sort(float[] a, int fromIndex, int toIndex)
2085      {
2086        if (fromIndex > toIndex)
2087          throw new IllegalArgumentException();
2088        if (fromIndex < 0)
2089          throw new ArrayIndexOutOfBoundsException();
2090        qsort(a, fromIndex, toIndex - fromIndex);
2091      }
2092    
2093      /**
2094       * Finds the index of the median of three array elements.
2095       *
2096       * @param a the first index
2097       * @param b the second index
2098       * @param c the third index
2099       * @param d the array
2100       * @return the index (a, b, or c) which has the middle value of the three
2101       */
2102      private static int med3(int a, int b, int c, float[] d)
2103      {
2104        return (Float.compare(d[a], d[b]) < 0
2105                ? (Float.compare(d[b], d[c]) < 0 ? b
2106                   : Float.compare(d[a], d[c]) < 0 ? c : a)
2107                : (Float.compare(d[b], d[c]) > 0 ? b
2108                   : Float.compare(d[a], d[c]) > 0 ? c : a));
2109      }
2110    
2111      /**
2112       * Swaps the elements at two locations of an array
2113       *
2114       * @param i the first index
2115       * @param j the second index
2116       * @param a the array
2117       */
2118      private static void swap(int i, int j, float[] a)
2119      {
2120        float c = a[i];
2121        a[i] = a[j];
2122        a[j] = c;
2123      }
2124    
2125      /**
2126       * Swaps two ranges of an array.
2127       *
2128       * @param i the first range start
2129       * @param j the second range start
2130       * @param n the element count
2131       * @param a the array
2132       */
2133      private static void vecswap(int i, int j, int n, float[] a)
2134      {
2135        for ( ; n > 0; i++, j++, n--)
2136          swap(i, j, a);
2137      }
2138    
2139      /**
2140       * Performs a recursive modified quicksort.
2141       *
2142       * @param array the array to sort
2143       * @param from the start index (inclusive)
2144       * @param count the number of elements to sort
2145       */
2146      private static void qsort(float[] array, int from, int count)
2147      {
2148        // Use an insertion sort on small arrays.
2149        if (count <= 7)
2150          {
2151            for (int i = from + 1; i < from + count; i++)
2152              for (int j = i;
2153                   j > from && Float.compare(array[j - 1], array[j]) > 0;
2154                   j--)
2155                {
2156                  swap(j, j - 1, array);
2157                }
2158            return;
2159          }
2160    
2161        // Determine a good median element.
2162        int mid = from + count / 2;
2163        int lo = from;
2164        int hi = from + count - 1;
2165    
2166        if (count > 40)
2167          { // big arrays, pseudomedian of 9
2168            int s = count / 8;
2169            lo = med3(lo, lo + s, lo + 2 * s, array);
2170            mid = med3(mid - s, mid, mid + s, array);
2171            hi = med3(hi - 2 * s, hi - s, hi, array);
2172          }
2173        mid = med3(lo, mid, hi, array);
2174    
2175        int a, b, c, d;
2176        int comp;
2177    
2178        // Pull the median element out of the fray, and use it as a pivot.
2179        swap(from, mid, array);
2180        a = b = from;
2181        c = d = from + count - 1;
2182    
2183        // Repeatedly move b and c to each other, swapping elements so
2184        // that all elements before index b are less than the pivot, and all
2185        // elements after index c are greater than the pivot. a and b track
2186        // the elements equal to the pivot.
2187        while (true)
2188          {
2189            while (b <= c && (comp = Float.compare(array[b], array[from])) <= 0)
2190              {
2191                if (comp == 0)
2192                  {
2193                    swap(a, b, array);
2194                    a++;
2195                  }
2196                b++;
2197              }
2198            while (c >= b && (comp = Float.compare(array[c], array[from])) >= 0)
2199              {
2200                if (comp == 0)
2201                  {
2202                    swap(c, d, array);
2203                    d--;
2204                  }
2205                c--;
2206              }
2207            if (b > c)
2208              break;
2209            swap(b, c, array);
2210            b++;
2211            c--;
2212          }
2213    
2214        // Swap pivot(s) back in place, the recurse on left and right sections.
2215        hi = from + count;
2216        int span;
2217        span = Math.min(a - from, b - a);
2218        vecswap(from, b - span, span, array);
2219    
2220        span = Math.min(d - c, hi - d - 1);
2221        vecswap(b, hi - span, span, array);
2222    
2223        span = b - a;
2224        if (span > 1)
2225          qsort(array, from, span);
2226    
2227        span = d - c;
2228        if (span > 1)
2229          qsort(array, hi - span, span);
2230      }
2231    
2232      /**
2233       * Performs a stable sort on the elements, arranging them according to their
2234       * natural order.
2235       *
2236       * @param a the double array to sort
2237       */
2238      public static void sort(double[] a)
2239      {
2240        qsort(a, 0, a.length);
2241      }
2242    
2243      /**
2244       * Performs a stable sort on the elements, arranging them according to their
2245       * natural order.
2246       *
2247       * @param a the double array to sort
2248       * @param fromIndex the first index to sort (inclusive)
2249       * @param toIndex the last index to sort (exclusive)
2250       * @throws IllegalArgumentException if fromIndex &gt; toIndex
2251       * @throws ArrayIndexOutOfBoundsException if fromIndex &lt; 0
2252       *         || toIndex &gt; a.length
2253       */
2254      public static void sort(double[] a, int fromIndex, int toIndex)
2255      {
2256        if (fromIndex > toIndex)
2257          throw new IllegalArgumentException();
2258        if (fromIndex < 0)
2259          throw new ArrayIndexOutOfBoundsException();
2260        qsort(a, fromIndex, toIndex - fromIndex);
2261      }
2262    
2263      /**
2264       * Finds the index of the median of three array elements.
2265       *
2266       * @param a the first index
2267       * @param b the second index
2268       * @param c the third index
2269       * @param d the array
2270       * @return the index (a, b, or c) which has the middle value of the three
2271       */
2272      private static int med3(int a, int b, int c, double[] d)
2273      {
2274        return (Double.compare(d[a], d[b]) < 0
2275                ? (Double.compare(d[b], d[c]) < 0 ? b
2276                   : Double.compare(d[a], d[c]) < 0 ? c : a)
2277                : (Double.compare(d[b], d[c]) > 0 ? b
2278                   : Double.compare(d[a], d[c]) > 0 ? c : a));
2279      }
2280    
2281      /**
2282       * Swaps the elements at two locations of an array
2283       *
2284       * @param i the first index
2285       * @param j the second index
2286       * @param a the array
2287       */
2288      private static void swap(int i, int j, double[] a)
2289      {
2290        double c = a[i];
2291        a[i] = a[j];
2292        a[j] = c;
2293      }
2294    
2295      /**
2296       * Swaps two ranges of an array.
2297       *
2298       * @param i the first range start
2299       * @param j the second range start
2300       * @param n the element count
2301       * @param a the array
2302       */
2303      private static void vecswap(int i, int j, int n, double[] a)
2304      {
2305        for ( ; n > 0; i++, j++, n--)
2306          swap(i, j, a);
2307      }
2308    
2309      /**
2310       * Performs a recursive modified quicksort.
2311       *
2312       * @param array the array to sort
2313       * @param from the start index (inclusive)
2314       * @param count the number of elements to sort
2315       */
2316      private static void qsort(double[] array, int from, int count)
2317      {
2318        // Use an insertion sort on small arrays.
2319        if (count <= 7)
2320          {
2321            for (int i = from + 1; i < from + count; i++)
2322              for (int j = i;
2323                   j > from && Double.compare(array[j - 1], array[j]) > 0;
2324                   j--)
2325                {
2326                  swap(j, j - 1, array);
2327                }
2328            return;
2329          }
2330    
2331        // Determine a good median element.
2332        int mid = from + count / 2;
2333        int lo = from;
2334        int hi = from + count - 1;
2335    
2336        if (count > 40)
2337          { // big arrays, pseudomedian of 9
2338            int s = count / 8;
2339            lo = med3(lo, lo + s, lo + 2 * s, array);
2340            mid = med3(mid - s, mid, mid + s, array);
2341            hi = med3(hi - 2 * s, hi - s, hi, array);
2342          }
2343        mid = med3(lo, mid, hi, array);
2344    
2345        int a, b, c, d;
2346        int comp;
2347    
2348        // Pull the median element out of the fray, and use it as a pivot.
2349        swap(from, mid, array);
2350        a = b = from;
2351        c = d = from + count - 1;
2352    
2353        // Repeatedly move b and c to each other, swapping elements so
2354        // that all elements before index b are less than the pivot, and all
2355        // elements after index c are greater than the pivot. a and b track
2356        // the elements equal to the pivot.
2357        while (true)
2358          {
2359            while (b <= c && (comp = Double.compare(array[b], array[from])) <= 0)
2360              {
2361                if (comp == 0)
2362                  {
2363                    swap(a, b, array);
2364                    a++;
2365                  }
2366                b++;
2367              }
2368            while (c >= b && (comp = Double.compare(array[c], array[from])) >= 0)
2369              {
2370                if (comp == 0)
2371                  {
2372                    swap(c, d, array);
2373                    d--;
2374                  }
2375                c--;
2376              }
2377            if (b > c)
2378              break;
2379            swap(b, c, array);
2380            b++;
2381            c--;
2382          }
2383    
2384        // Swap pivot(s) back in place, the recurse on left and right sections.
2385        hi = from + count;
2386        int span;
2387        span = Math.min(a - from, b - a);
2388        vecswap(from, b - span, span, array);
2389    
2390        span = Math.min(d - c, hi - d - 1);
2391        vecswap(b, hi - span, span, array);
2392    
2393        span = b - a;
2394        if (span > 1)
2395          qsort(array, from, span);
2396    
2397        span = d - c;
2398        if (span > 1)
2399          qsort(array, hi - span, span);
2400      }
2401    
2402      /**
2403       * Sort an array of Objects according to their natural ordering. The sort is
2404       * guaranteed to be stable, that is, equal elements will not be reordered.
2405       * The sort algorithm is a mergesort with the merge omitted if the last
2406       * element of one half comes before the first element of the other half. This
2407       * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2408       * copy of the array.
2409       *
2410       * @param a the array to be sorted
2411       * @throws ClassCastException if any two elements are not mutually
2412       *         comparable
2413       * @throws NullPointerException if an element is null (since
2414       *         null.compareTo cannot work)
2415       * @see Comparable
2416       */
2417      public static void sort(Object[] a)
2418      {
2419        sort(a, 0, a.length, null);
2420      }
2421    
2422      /**
2423       * Sort an array of Objects according to a Comparator. The sort is
2424       * guaranteed to be stable, that is, equal elements will not be reordered.
2425       * The sort algorithm is a mergesort with the merge omitted if the last
2426       * element of one half comes before the first element of the other half. This
2427       * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2428       * copy of the array.
2429       *
2430       * @param a the array to be sorted
2431       * @param c a Comparator to use in sorting the array; or null to indicate
2432       *        the elements' natural order
2433       * @throws ClassCastException if any two elements are not mutually
2434       *         comparable by the Comparator provided
2435       * @throws NullPointerException if a null element is compared with natural
2436       *         ordering (only possible when c is null)
2437       */
2438      public static <T> void sort(T[] a, Comparator<? super T> c)
2439      {
2440        sort(a, 0, a.length, c);
2441      }
2442    
2443      /**
2444       * Sort an array of Objects according to their natural ordering. The sort is
2445       * guaranteed to be stable, that is, equal elements will not be reordered.
2446       * The sort algorithm is a mergesort with the merge omitted if the last
2447       * element of one half comes before the first element of the other half. This
2448       * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2449       * copy of the array.
2450       *
2451       * @param a the array to be sorted
2452       * @param fromIndex the index of the first element to be sorted
2453       * @param toIndex the index of the last element to be sorted plus one
2454       * @throws ClassCastException if any two elements are not mutually
2455       *         comparable
2456       * @throws NullPointerException if an element is null (since
2457       *         null.compareTo cannot work)
2458       * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex
2459       *         are not in range.
2460       * @throws IllegalArgumentException if fromIndex &gt; toIndex
2461       */
2462      public static void sort(Object[] a, int fromIndex, int toIndex)
2463      {
2464        sort(a, fromIndex, toIndex, null);
2465      }
2466    
2467      /**
2468       * Sort an array of Objects according to a Comparator. The sort is
2469       * guaranteed to be stable, that is, equal elements will not be reordered.
2470       * The sort algorithm is a mergesort with the merge omitted if the last
2471       * element of one half comes before the first element of the other half. This
2472       * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a
2473       * copy of the array.
2474       *
2475       * @param a the array to be sorted
2476       * @param fromIndex the index of the first element to be sorted
2477       * @param toIndex the index of the last element to be sorted plus one
2478       * @param c a Comparator to use in sorting the array; or null to indicate
2479       *        the elements' natural order
2480       * @throws ClassCastException if any two elements are not mutually
2481       *         comparable by the Comparator provided
2482       * @throws ArrayIndexOutOfBoundsException if fromIndex and toIndex
2483       *         are not in range.
2484       * @throws IllegalArgumentException if fromIndex &gt; toIndex
2485       * @throws NullPointerException if a null element is compared with natural
2486       *         ordering (only possible when c is null)
2487       */
2488      public static <T> void sort(T[] a, int fromIndex, int toIndex,
2489                                  Comparator<? super T> c)
2490      {
2491        if (fromIndex > toIndex)
2492          throw new IllegalArgumentException("fromIndex " + fromIndex
2493                                             + " > toIndex " + toIndex);
2494        if (fromIndex < 0)
2495          throw new ArrayIndexOutOfBoundsException();
2496    
2497        // In general, the code attempts to be simple rather than fast, the
2498        // idea being that a good optimising JIT will be able to optimise it
2499        // better than I can, and if I try it will make it more confusing for
2500        // the JIT. First presort the array in chunks of length 6 with insertion
2501        // sort. A mergesort would give too much overhead for this length.
2502        for (int chunk = fromIndex; chunk < toIndex; chunk += 6)
2503          {
2504            int end = Math.min(chunk + 6, toIndex);
2505            for (int i = chunk + 1; i < end; i++)
2506              {
2507                if (Collections.compare(a[i - 1], a[i], c) > 0)
2508                  {
2509                    // not already sorted
2510                    int j = i;
2511                    T elem = a[j];
2512                    do
2513                      {
2514                        a[j] = a[j - 1];
2515                        j--;
2516                      }
2517                    while (j > chunk
2518                           && Collections.compare(a[j - 1], elem, c) > 0);
2519                    a[j] = elem;
2520                  }
2521              }
2522          }
2523    
2524        int len = toIndex - fromIndex;
2525        // If length is smaller or equal 6 we are done.
2526        if (len <= 6)
2527          return;
2528    
2529        T[] src = a;
2530        T[] dest = (T[]) new Object[len];
2531        T[] t = null; // t is used for swapping src and dest
2532    
2533        // The difference of the fromIndex of the src and dest array.
2534        int srcDestDiff = -fromIndex;
2535    
2536        // The merges are done in this loop
2537        for (int size = 6; size < len; size <<= 1)
2538          {
2539            for (int start = fromIndex; start < toIndex; start += size << 1)
2540              {
2541                // mid is the start of the second sublist;
2542                // end the start of the next sublist (or end of array).
2543                int mid = start + size;
2544                int end = Math.min(toIndex, mid + size);
2545    
2546                // The second list is empty or the elements are already in
2547                // order - no need to merge
2548                if (mid >= end
2549                    || Collections.compare(src[mid - 1], src[mid], c) <= 0)
2550                  {
2551                    System.arraycopy(src, start,
2552                                     dest, start + srcDestDiff, end - start);
2553    
2554                    // The two halves just need swapping - no need to merge
2555                  }
2556                else if (Collections.compare(src[start], src[end - 1], c) > 0)
2557                  {
2558                    System.arraycopy(src, start,
2559                                     dest, end - size + srcDestDiff, size);
2560                    System.arraycopy(src, mid,
2561                                     dest, start + srcDestDiff, end - mid);
2562    
2563                  }
2564                else
2565                  {
2566                    // Declare a lot of variables to save repeating
2567                    // calculations.  Hopefully a decent JIT will put these
2568                    // in registers and make this fast
2569                    int p1 = start;
2570                    int p2 = mid;
2571                    int i = start + srcDestDiff;
2572    
2573                    // The main merge loop; terminates as soon as either
2574                    // half is ended
2575                    while (p1 < mid && p2 < end)
2576                      {
2577                        dest[i++] =
2578                          src[(Collections.compare(src[p1], src[p2], c) <= 0
2579                               ? p1++ : p2++)];
2580                      }
2581    
2582                    // Finish up by copying the remainder of whichever half
2583                    // wasn't finished.
2584                    if (p1 < mid)
2585                      System.arraycopy(src, p1, dest, i, mid - p1);
2586                    else
2587                      System.arraycopy(src, p2, dest, i, end - p2);
2588                  }
2589              }
2590            // swap src and dest ready for the next merge
2591            t = src;
2592            src = dest;
2593            dest = t;
2594            fromIndex += srcDestDiff;
2595            toIndex += srcDestDiff;
2596            srcDestDiff = -srcDestDiff;
2597          }
2598    
2599        // make sure the result ends up back in the right place.  Note
2600        // that src and dest may have been swapped above, so src
2601        // contains the sorted array.
2602        if (src != a)
2603          {
2604            // Note that fromIndex == 0.
2605            System.arraycopy(src, 0, a, srcDestDiff, toIndex);
2606          }
2607      }
2608    
2609      /**
2610       * Returns a list "view" of the specified array. This method is intended to
2611       * make it easy to use the Collections API with existing array-based APIs and
2612       * programs. Changes in the list or the array show up in both places. The
2613       * list does not support element addition or removal, but does permit
2614       * value modification. The returned list implements both Serializable and
2615       * RandomAccess.
2616       *
2617       * @param a the array to return a view of (<code>null</code> not permitted)
2618       * @return a fixed-size list, changes to which "write through" to the array
2619       * 
2620       * @throws NullPointerException if <code>a</code> is <code>null</code>.
2621       * @see Serializable
2622       * @see RandomAccess
2623       * @see Arrays.ArrayList
2624       */
2625      public static <T> List<T> asList(final T... a)
2626      {
2627        return new Arrays.ArrayList(a);
2628      }
2629    
2630      /** 
2631       * Returns the hashcode of an array of long numbers.  If two arrays
2632       * are equal, according to <code>equals()</code>, they should have the
2633       * same hashcode.  The hashcode returned by the method is equal to that
2634       * obtained by the corresponding <code>List</code> object.  This has the same
2635       * data, but represents longs in their wrapper class, <code>Long</code>.
2636       * For <code>null</code>, 0 is returned.
2637       *
2638       * @param v an array of long numbers for which the hash code should be
2639       *          computed.
2640       * @return the hash code of the array, or 0 if null was given.
2641       * @since 1.5 
2642       */
2643      public static int hashCode(long[] v)
2644      {
2645        if (v == null)
2646          return 0;
2647        int result = 1;
2648        for (int i = 0; i < v.length; ++i)
2649          {
2650            int elt = (int) (v[i] ^ (v[i] >>> 32));
2651            result = 31 * result + elt;
2652          }
2653        return result;
2654      }
2655    
2656      /** 
2657       * Returns the hashcode of an array of integer numbers.  If two arrays
2658       * are equal, according to <code>equals()</code>, they should have the
2659       * same hashcode.  The hashcode returned by the method is equal to that
2660       * obtained by the corresponding <code>List</code> object.  This has the same
2661       * data, but represents ints in their wrapper class, <code>Integer</code>.
2662       * For <code>null</code>, 0 is returned.
2663       *
2664       * @param v an array of integer numbers for which the hash code should be
2665       *          computed.
2666       * @return the hash code of the array, or 0 if null was given.
2667       * @since 1.5 
2668       */
2669      public static int hashCode(int[] v)
2670      {
2671        if (v == null)
2672          return 0;
2673        int result = 1;
2674        for (int i = 0; i < v.length; ++i)
2675          result = 31 * result + v[i];
2676        return result;
2677      }
2678    
2679      /** 
2680       * Returns the hashcode of an array of short numbers.  If two arrays
2681       * are equal, according to <code>equals()</code>, they should have the
2682       * same hashcode.  The hashcode returned by the method is equal to that
2683       * obtained by the corresponding <code>List</code> object.  This has the same
2684       * data, but represents shorts in their wrapper class, <code>Short</code>.
2685       * For <code>null</code>, 0 is returned.
2686       *
2687       * @param v an array of short numbers for which the hash code should be
2688       *          computed.
2689       * @return the hash code of the array, or 0 if null was given.
2690       * @since 1.5 
2691       */
2692      public static int hashCode(short[] v)
2693      {
2694        if (v == null)
2695          return 0;
2696        int result = 1;
2697        for (int i = 0; i < v.length; ++i)
2698          result = 31 * result + v[i];
2699        return result;
2700      }
2701    
2702      /** 
2703       * Returns the hashcode of an array of characters.  If two arrays
2704       * are equal, according to <code>equals()</code>, they should have the
2705       * same hashcode.  The hashcode returned by the method is equal to that
2706       * obtained by the corresponding <code>List</code> object.  This has the same
2707       * data, but represents chars in their wrapper class, <code>Character</code>.
2708       * For <code>null</code>, 0 is returned.
2709       *
2710       * @param v an array of characters for which the hash code should be
2711       *          computed.
2712       * @return the hash code of the array, or 0 if null was given.
2713       * @since 1.5 
2714       */
2715      public static int hashCode(char[] v)
2716      {
2717        if (v == null)
2718          return 0;
2719        int result = 1;
2720        for (int i = 0; i < v.length; ++i)
2721          result = 31 * result + v[i];
2722        return result;
2723      }
2724    
2725      /** 
2726       * Returns the hashcode of an array of bytes.  If two arrays
2727       * are equal, according to <code>equals()</code>, they should have the
2728       * same hashcode.  The hashcode returned by the method is equal to that
2729       * obtained by the corresponding <code>List</code> object.  This has the same
2730       * data, but represents bytes in their wrapper class, <code>Byte</code>.
2731       * For <code>null</code>, 0 is returned.
2732       *
2733       * @param v an array of bytes for which the hash code should be
2734       *          computed.
2735       * @return the hash code of the array, or 0 if null was given.
2736       * @since 1.5 
2737       */
2738      public static int hashCode(byte[] v)
2739      {
2740        if (v == null)
2741          return 0;
2742        int result = 1;
2743        for (int i = 0; i < v.length; ++i)
2744          result = 31 * result + v[i];
2745        return result;
2746      }
2747    
2748      /** 
2749       * Returns the hashcode of an array of booleans.  If two arrays
2750       * are equal, according to <code>equals()</code>, they should have the
2751       * same hashcode.  The hashcode returned by the method is equal to that
2752       * obtained by the corresponding <code>List</code> object.  This has the same
2753       * data, but represents booleans in their wrapper class,
2754       * <code>Boolean</code>.  For <code>null</code>, 0 is returned.
2755       *
2756       * @param v an array of booleans for which the hash code should be
2757       *          computed.
2758       * @return the hash code of the array, or 0 if null was given.
2759       * @since 1.5 
2760       */
2761      public static int hashCode(boolean[] v)
2762      {
2763        if (v == null)
2764          return 0;
2765        int result = 1;
2766        for (int i = 0; i < v.length; ++i)
2767          result = 31 * result + (v[i] ? 1231 : 1237);
2768        return result;
2769      }
2770    
2771      /** 
2772       * Returns the hashcode of an array of floats.  If two arrays
2773       * are equal, according to <code>equals()</code>, they should have the
2774       * same hashcode.  The hashcode returned by the method is equal to that
2775       * obtained by the corresponding <code>List</code> object.  This has the same
2776       * data, but represents floats in their wrapper class, <code>Float</code>.
2777       * For <code>null</code>, 0 is returned.
2778       *
2779       * @param v an array of floats for which the hash code should be
2780       *          computed.
2781       * @return the hash code of the array, or 0 if null was given.
2782       * @since 1.5 
2783       */
2784      public static int hashCode(float[] v)
2785      {
2786        if (v == null)
2787          return 0;
2788        int result = 1;
2789        for (int i = 0; i < v.length; ++i)
2790          result = 31 * result + Float.floatToIntBits(v[i]);
2791        return result;
2792      }
2793    
2794      /** 
2795       * Returns the hashcode of an array of doubles.  If two arrays
2796       * are equal, according to <code>equals()</code>, they should have the
2797       * same hashcode.  The hashcode returned by the method is equal to that
2798       * obtained by the corresponding <code>List</code> object.  This has the same
2799       * data, but represents doubles in their wrapper class, <code>Double</code>.
2800       * For <code>null</code>, 0 is returned.
2801       *
2802       * @param v an array of doubles for which the hash code should be
2803       *          computed.
2804       * @return the hash code of the array, or 0 if null was given.
2805       * @since 1.5 
2806       */
2807      public static int hashCode(double[] v)
2808      {
2809        if (v == null)
2810          return 0;
2811        int result = 1;
2812        for (int i = 0; i < v.length; ++i)
2813          {
2814            long l = Double.doubleToLongBits(v[i]);
2815            int elt = (int) (l ^ (l >>> 32));
2816            result = 31 * result + elt;
2817          }
2818        return result;
2819      }
2820    
2821      /** 
2822       * Returns the hashcode of an array of objects.  If two arrays
2823       * are equal, according to <code>equals()</code>, they should have the
2824       * same hashcode.  The hashcode returned by the method is equal to that
2825       * obtained by the corresponding <code>List</code> object.  
2826       * For <code>null</code>, 0 is returned.
2827       *
2828       * @param v an array of integer numbers for which the hash code should be
2829       *          computed.
2830       * @return the hash code of the array, or 0 if null was given.
2831       * @since 1.5 
2832       */
2833      public static int hashCode(Object[] v)
2834      {
2835        if (v == null)
2836          return 0;
2837        int result = 1;
2838        for (int i = 0; i < v.length; ++i)
2839          {
2840            int elt = v[i] == null ? 0 : v[i].hashCode();
2841            result = 31 * result + elt;
2842          }
2843        return result;
2844      }
2845    
2846      public static int deepHashCode(Object[] v)
2847      {
2848        if (v == null)
2849          return 0;
2850        int result = 1;
2851        for (int i = 0; i < v.length; ++i)
2852          {
2853            int elt;
2854            if (v[i] == null)
2855              elt = 0;
2856            else if (v[i] instanceof boolean[])
2857              elt = hashCode((boolean[]) v[i]);
2858            else if (v[i] instanceof byte[])
2859              elt = hashCode((byte[]) v[i]);
2860            else if (v[i] instanceof char[])
2861              elt = hashCode((char[]) v[i]);
2862            else if (v[i] instanceof short[])
2863              elt = hashCode((short[]) v[i]);
2864            else if (v[i] instanceof int[])
2865              elt = hashCode((int[]) v[i]);
2866            else if (v[i] instanceof long[])
2867              elt = hashCode((long[]) v[i]);
2868            else if (v[i] instanceof float[])
2869              elt = hashCode((float[]) v[i]);
2870            else if (v[i] instanceof double[])
2871              elt = hashCode((double[]) v[i]);
2872            else if (v[i] instanceof Object[])
2873              elt = hashCode((Object[]) v[i]);
2874            else
2875              elt = v[i].hashCode();
2876            result = 31 * result + elt;
2877          }
2878        return result;
2879      }
2880    
2881      /** @since 1.5 */
2882      public static boolean deepEquals(Object[] v1, Object[] v2)
2883      {
2884        if (v1 == null)
2885          return v2 == null;
2886        if (v2 == null || v1.length != v2.length)
2887          return false;
2888    
2889        for (int i = 0; i < v1.length; ++i)
2890          {
2891            Object e1 = v1[i];
2892            Object e2 = v2[i];
2893    
2894            if (e1 == e2)
2895              continue;
2896            if (e1 == null || e2 == null)
2897              return false;
2898    
2899            boolean check;
2900            if (e1 instanceof boolean[] && e2 instanceof boolean[])
2901              check = equals((boolean[]) e1, (boolean[]) e2);
2902            else if (e1 instanceof byte[] && e2 instanceof byte[])
2903              check = equals((byte[]) e1, (byte[]) e2);
2904            else if (e1 instanceof char[] && e2 instanceof char[])
2905              check = equals((char[]) e1, (char[]) e2);
2906            else if (e1 instanceof short[] && e2 instanceof short[])
2907              check = equals((short[]) e1, (short[]) e2);
2908            else if (e1 instanceof int[] && e2 instanceof int[])
2909              check = equals((int[]) e1, (int[]) e2);
2910            else if (e1 instanceof long[] && e2 instanceof long[])
2911              check = equals((long[]) e1, (long[]) e2);
2912            else if (e1 instanceof float[] && e2 instanceof float[])
2913              check = equals((float[]) e1, (float[]) e2);
2914            else if (e1 instanceof double[] && e2 instanceof double[])
2915              check = equals((double[]) e1, (double[]) e2);
2916            else if (e1 instanceof Object[] && e2 instanceof Object[])
2917              check = equals((Object[]) e1, (Object[]) e2);
2918            else
2919              check = e1.equals(e2);
2920            if (! check)
2921              return false;
2922          }
2923    
2924        return true;
2925      }
2926    
2927      /**
2928       * Returns a String representation of the argument array.  Returns "null"
2929       * if <code>a</code> is null.
2930       * @param v the array to represent
2931       * @return a String representing this array
2932       * @since 1.5
2933       */
2934      public static String toString(boolean[] v)
2935      {
2936        if (v == null)
2937          return "null";
2938        StringBuilder b = new StringBuilder("[");
2939        for (int i = 0; i < v.length; ++i)
2940          {
2941            if (i > 0)
2942              b.append(", ");
2943            b.append(v[i]);
2944          }
2945        b.append("]");
2946        return b.toString();
2947      }
2948    
2949      /**
2950       * Returns a String representation of the argument array.  Returns "null"
2951       * if <code>a</code> is null.
2952       * @param v the array to represent
2953       * @return a String representing this array
2954       * @since 1.5
2955       */
2956      public static String toString(byte[] v)
2957      {
2958        if (v == null)
2959          return "null";
2960        StringBuilder b = new StringBuilder("[");
2961        for (int i = 0; i < v.length; ++i)
2962          {
2963            if (i > 0)
2964              b.append(", ");
2965            b.append(v[i]);
2966          }
2967        b.append("]");
2968        return b.toString();
2969      }
2970    
2971      /**
2972       * Returns a String representation of the argument array.  Returns "null"
2973       * if <code>a</code> is null.
2974       * @param v the array to represent
2975       * @return a String representing this array
2976       * @since 1.5
2977       */
2978      public static String toString(char[] v)
2979      {
2980        if (v == null)
2981          return "null";
2982        StringBuilder b = new StringBuilder("[");
2983        for (int i = 0; i < v.length; ++i)
2984          {
2985            if (i > 0)
2986              b.append(", ");
2987            b.append(v[i]);
2988          }
2989        b.append("]");
2990        return b.toString();
2991      }
2992    
2993      /**
2994       * Returns a String representation of the argument array.  Returns "null"
2995       * if <code>a</code> is null.
2996       * @param v the array to represent
2997       * @return a String representing this array
2998       * @since 1.5
2999       */
3000      public static String toString(short[] v)
3001      {
3002        if (v == null)
3003          return "null";
3004        StringBuilder b = new StringBuilder("[");
3005        for (int i = 0; i < v.length; ++i)
3006          {
3007            if (i > 0)
3008              b.append(", ");
3009            b.append(v[i]);
3010          }
3011        b.append("]");
3012        return b.toString();
3013      }
3014    
3015      /**
3016       * Returns a String representation of the argument array.  Returns "null"
3017       * if <code>a</code> is null.
3018       * @param v the array to represent
3019       * @return a String representing this array
3020       * @since 1.5
3021       */
3022      public static String toString(int[] v)
3023      {
3024        if (v == null)
3025          return "null";
3026        StringBuilder b = new StringBuilder("[");
3027        for (int i = 0; i < v.length; ++i)
3028          {
3029            if (i > 0)
3030              b.append(", ");
3031            b.append(v[i]);
3032          }
3033        b.append("]");
3034        return b.toString();
3035      }
3036    
3037      /**
3038       * Returns a String representation of the argument array.  Returns "null"
3039       * if <code>a</code> is null.
3040       * @param v the array to represent
3041       * @return a String representing this array
3042       * @since 1.5
3043       */
3044      public static String toString(long[] v)
3045      {
3046        if (v == null)
3047          return "null";
3048        StringBuilder b = new StringBuilder("[");
3049        for (int i = 0; i < v.length; ++i)
3050          {
3051            if (i > 0)
3052              b.append(", ");
3053            b.append(v[i]);
3054          }
3055        b.append("]");
3056        return b.toString();
3057      }
3058    
3059      /**
3060       * Returns a String representation of the argument array.  Returns "null"
3061       * if <code>a</code> is null.
3062       * @param v the array to represent
3063       * @return a String representing this array
3064       * @since 1.5
3065       */
3066      public static String toString(float[] v)
3067      {
3068        if (v == null)
3069          return "null";
3070        StringBuilder b = new StringBuilder("[");
3071        for (int i = 0; i < v.length; ++i)
3072          {
3073            if (i > 0)
3074              b.append(", ");
3075            b.append(v[i]);
3076          }
3077        b.append("]");
3078        return b.toString();
3079      }
3080    
3081      /**
3082       * Returns a String representation of the argument array.  Returns "null"
3083       * if <code>a</code> is null.
3084       * @param v the array to represent
3085       * @return a String representing this array
3086       * @since 1.5
3087       */
3088      public static String toString(double[] v)
3089      {
3090        if (v == null)
3091          return "null";
3092        StringBuilder b = new StringBuilder("[");
3093        for (int i = 0; i < v.length; ++i)
3094          {
3095            if (i > 0)
3096              b.append(", ");
3097            b.append(v[i]);
3098          }
3099        b.append("]");
3100        return b.toString();
3101      }
3102    
3103      /**
3104       * Returns a String representation of the argument array.  Returns "null"
3105       * if <code>a</code> is null.
3106       * @param v the array to represent
3107       * @return a String representing this array
3108       * @since 1.5
3109       */
3110      public static String toString(Object[] v)
3111      {
3112        if (v == null)
3113          return "null";
3114        StringBuilder b = new StringBuilder("[");
3115        for (int i = 0; i < v.length; ++i)
3116          {
3117            if (i > 0)
3118              b.append(", ");
3119            b.append(v[i]);
3120          }
3121        b.append("]");
3122        return b.toString();
3123      }
3124    
3125      private static void deepToString(Object[] v, StringBuilder b, HashSet seen)
3126      {
3127        b.append("[");
3128        for (int i = 0; i < v.length; ++i)
3129          {
3130            if (i > 0)
3131              b.append(", ");
3132            Object elt = v[i];
3133            if (elt == null)
3134              b.append("null");
3135            else if (elt instanceof boolean[])
3136              b.append(toString((boolean[]) elt));
3137            else if (elt instanceof byte[])
3138              b.append(toString((byte[]) elt));
3139            else if (elt instanceof char[])
3140              b.append(toString((char[]) elt));
3141            else if (elt instanceof short[])
3142              b.append(toString((short[]) elt));
3143            else if (elt instanceof int[])
3144              b.append(toString((int[]) elt));
3145            else if (elt instanceof long[])
3146              b.append(toString((long[]) elt));
3147            else if (elt instanceof float[])
3148              b.append(toString((float[]) elt));
3149            else if (elt instanceof double[])
3150              b.append(toString((double[]) elt));
3151            else if (elt instanceof Object[])
3152              {
3153                Object[] os = (Object[]) elt;
3154                if (seen.contains(os))
3155                  b.append("[...]");
3156                else
3157                  {
3158                    seen.add(os);
3159                    deepToString(os, b, seen);
3160                  }
3161              }
3162            else
3163              b.append(elt);
3164          }
3165        b.append("]");
3166      }
3167    
3168      /** @since 1.5 */
3169      public static String deepToString(Object[] v)
3170      {
3171        if (v == null)
3172          return "null";
3173        HashSet seen = new HashSet();
3174        StringBuilder b = new StringBuilder();
3175        deepToString(v, b, seen);
3176        return b.toString();
3177      }
3178    
3179      /**
3180       * Inner class used by {@link #asList(Object[])} to provide a list interface
3181       * to an array. The name, though it clashes with java.util.ArrayList, is
3182       * Sun's choice for Serialization purposes. Element addition and removal
3183       * is prohibited, but values can be modified.
3184       *
3185       * @author Eric Blake (ebb9@email.byu.edu)
3186       * @status updated to 1.4
3187       */
3188      private static final class ArrayList<E> extends AbstractList<E>
3189        implements Serializable, RandomAccess
3190      {
3191        // We override the necessary methods, plus others which will be much
3192        // more efficient with direct iteration rather than relying on iterator().
3193    
3194        /**
3195         * Compatible with JDK 1.4.
3196         */
3197        private static final long serialVersionUID = -2764017481108945198L;
3198    
3199        /**
3200         * The array we are viewing.
3201         * @serial the array
3202         */
3203        private final E[] a;
3204    
3205        /**
3206         * Construct a list view of the array.
3207         * @param a the array to view
3208         * @throws NullPointerException if a is null
3209         */
3210        ArrayList(E[] a)
3211        {
3212          // We have to explicitly check.
3213          if (a == null)
3214            throw new NullPointerException();
3215          this.a = a;
3216        }
3217    
3218        /**
3219         * Returns the object at the specified index in
3220         * the array.
3221         *
3222         * @param index The index to retrieve an object from.
3223         * @return The object at the array index specified.
3224         */ 
3225        public E get(int index)
3226        {
3227          return a[index];
3228        }
3229    
3230        /**
3231         * Returns the size of the array.
3232         *
3233         * @return The size.
3234         */
3235        public int size()
3236        {
3237          return a.length;
3238        }
3239    
3240        /**
3241         * Replaces the object at the specified index
3242         * with the supplied element.
3243         *
3244         * @param index The index at which to place the new object.
3245         * @param element The new object.
3246         * @return The object replaced by this operation.
3247         */
3248        public E set(int index, E element)
3249        {
3250          E old = a[index];
3251          a[index] = element;
3252          return old;
3253        }
3254    
3255        /**
3256         * Returns true if the array contains the
3257         * supplied object.
3258         *
3259         * @param o The object to look for.
3260         * @return True if the object was found.
3261         */
3262        public boolean contains(Object o)
3263        {
3264          return lastIndexOf(o) >= 0;
3265        }
3266    
3267        /**
3268         * Returns the first index at which the
3269         * object, o, occurs in the array.
3270         *
3271         * @param o The object to search for.
3272         * @return The first relevant index.
3273         */
3274        public int indexOf(Object o)
3275        {
3276          int size = a.length;
3277          for (int i = 0; i < size; i++)
3278            if (ArrayList.equals(o, a[i]))
3279              return i;
3280          return -1;
3281        }
3282    
3283        /**
3284         * Returns the last index at which the
3285         * object, o, occurs in the array.
3286         *
3287         * @param o The object to search for.
3288         * @return The last relevant index.
3289         */
3290        public int lastIndexOf(Object o)
3291        {
3292          int i = a.length;
3293          while (--i >= 0)
3294            if (ArrayList.equals(o, a[i]))
3295              return i;
3296          return -1;
3297        }
3298    
3299        /**
3300         * Transforms the list into an array of
3301         * objects, by simplying cloning the array
3302         * wrapped by this list.
3303         *
3304         * @return A clone of the internal array.
3305         */
3306        public Object[] toArray()
3307        {
3308          return (Object[]) a.clone();
3309        }
3310    
3311        /**
3312         * Copies the objects from this list into
3313         * the supplied array.  The supplied array
3314         * is shrunk or enlarged to the size of the
3315         * internal array, and filled with its objects.
3316         *
3317         * @param array The array to fill with the objects in this list.
3318         * @return The array containing the objects in this list,
3319         *         which may or may not be == to array.
3320         */
3321        public <T> T[] toArray(T[] array)
3322        {
3323          int size = a.length;
3324          if (array.length < size)
3325            array = (T[]) Array.newInstance(array.getClass().getComponentType(),
3326                                            size);
3327          else if (array.length > size)
3328            array[size] = null;
3329    
3330          System.arraycopy(a, 0, array, 0, size);
3331          return array;
3332        }
3333      }
3334    
3335      /**
3336       * Returns a copy of the supplied array, truncating or padding as
3337       * necessary with <code>false</code> to obtain the specified length.
3338       * Indices that are valid for both arrays will return the same value.
3339       * Indices that only exist in the returned array (due to the new length
3340       * being greater than the original length) will return <code>false</code>.
3341       * This is equivalent to calling
3342       * <code>copyOfRange(original, 0, newLength)</code>.
3343       *
3344       * @param original the original array to be copied.
3345       * @param newLength the length of the returned array.
3346       * @return a copy of the original array, truncated or padded with
3347       *         <code>false</code> to obtain the required length.
3348       * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3349       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3350       * @since 1.6
3351       * @see #copyOfRange(boolean[],int,int)
3352       */
3353      public static boolean[] copyOf(boolean[] original, int newLength)
3354      {
3355        if (newLength < 0)
3356          throw new NegativeArraySizeException("The array size is negative.");
3357        return copyOfRange(original, 0, newLength);
3358      }
3359    
3360      /**
3361       * Copies the specified range of the supplied array to a new
3362       * array, padding as necessary with <code>false</code>
3363       * if <code>to</code> is greater than the length of the original
3364       * array.  <code>from</code> must be in the range zero to
3365       * <code>original.length</code> and can not be greater than
3366       * <code>to</code>.  The initial element of the
3367       * returned array will be equal to <code>original[from]</code>,
3368       * except where <code>from</code> is equal to <code>to</code>
3369       * (where a zero-length array will be returned) or <code>
3370       * <code>from</code> is equal to <code>original.length</code>
3371       * (where an array padded with <code>false</code> will be
3372       * returned).  The returned array is always of length
3373       * <code>to - from</code>.
3374       *
3375       * @param original the array from which to copy.
3376       * @param from the initial index of the range, inclusive.
3377       * @param to the final index of the range, exclusive.
3378       * @return a copy of the specified range, with padding to
3379       *         obtain the required length.
3380       * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3381       *                                        or <code>from > original.length</code>
3382       * @throws IllegalArgumentException if <code>from > to</code>
3383       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3384       * @since 1.6
3385       * @see #copyOf(boolean[],int)
3386       */
3387      public static boolean[] copyOfRange(boolean[] original, int from, int to)
3388      {
3389        if (from > to)
3390          throw new IllegalArgumentException("The initial index is after " +
3391                                             "the final index.");
3392        boolean[] newArray = new boolean[to - from];
3393        if (to > original.length)
3394          {
3395            System.arraycopy(original, from, newArray, 0,
3396                             original.length - from);
3397            fill(newArray, original.length, newArray.length, false);
3398          }
3399        else
3400          System.arraycopy(original, from, newArray, 0, to - from);
3401        return newArray;
3402      }
3403    
3404      /**
3405       * Returns a copy of the supplied array, truncating or padding as
3406       * necessary with <code>(byte)0</code> to obtain the specified length.
3407       * Indices that are valid for both arrays will return the same value.
3408       * Indices that only exist in the returned array (due to the new length
3409       * being greater than the original length) will return <code>(byte)0</code>.
3410       * This is equivalent to calling
3411       * <code>copyOfRange(original, 0, newLength)</code>.
3412       *
3413       * @param original the original array to be copied.
3414       * @param newLength the length of the returned array.
3415       * @return a copy of the original array, truncated or padded with
3416       *         <code>(byte)0</code> to obtain the required length.
3417       * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3418       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3419       * @since 1.6
3420       * @see #copyOfRange(byte[],int,int)
3421       */
3422      public static byte[] copyOf(byte[] original, int newLength)
3423      {
3424        if (newLength < 0)
3425          throw new NegativeArraySizeException("The array size is negative.");
3426        return copyOfRange(original, 0, newLength);
3427      }
3428    
3429      /**
3430       * Copies the specified range of the supplied array to a new
3431       * array, padding as necessary with <code>(byte)0</code>
3432       * if <code>to</code> is greater than the length of the original
3433       * array.  <code>from</code> must be in the range zero to
3434       * <code>original.length</code> and can not be greater than
3435       * <code>to</code>.  The initial element of the
3436       * returned array will be equal to <code>original[from]</code>,
3437       * except where <code>from</code> is equal to <code>to</code>
3438       * (where a zero-length array will be returned) or <code>
3439       * <code>from</code> is equal to <code>original.length</code>
3440       * (where an array padded with <code>(byte)0</code> will be
3441       * returned).  The returned array is always of length
3442       * <code>to - from</code>.
3443       *
3444       * @param original the array from which to copy.
3445       * @param from the initial index of the range, inclusive.
3446       * @param to the final index of the range, exclusive.
3447       * @return a copy of the specified range, with padding to
3448       *         obtain the required length.
3449       * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3450       *                                        or <code>from > original.length</code>
3451       * @throws IllegalArgumentException if <code>from > to</code>
3452       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3453       * @since 1.6
3454       * @see #copyOf(byte[],int)
3455       */
3456      public static byte[] copyOfRange(byte[] original, int from, int to)
3457      {
3458        if (from > to)
3459          throw new IllegalArgumentException("The initial index is after " +
3460                                             "the final index.");
3461        byte[] newArray = new byte[to - from];
3462        if (to > original.length)
3463          {
3464            System.arraycopy(original, from, newArray, 0,
3465                             original.length - from);
3466            fill(newArray, original.length, newArray.length, (byte)0);
3467          }
3468        else
3469          System.arraycopy(original, from, newArray, 0, to - from);
3470        return newArray;
3471      }
3472    
3473      /**
3474       * Returns a copy of the supplied array, truncating or padding as
3475       * necessary with <code>'\0'</code> to obtain the specified length.
3476       * Indices that are valid for both arrays will return the same value.
3477       * Indices that only exist in the returned array (due to the new length
3478       * being greater than the original length) will return <code>'\0'</code>.
3479       * This is equivalent to calling
3480       * <code>copyOfRange(original, 0, newLength)</code>.
3481       *
3482       * @param original the original array to be copied.
3483       * @param newLength the length of the returned array.
3484       * @return a copy of the original array, truncated or padded with
3485       *         <code>'\0'</code> to obtain the required length.
3486       * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3487       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3488       * @since 1.6
3489       * @see #copyOfRange(char[],int,int)
3490       */
3491      public static char[] copyOf(char[] original, int newLength)
3492      {
3493        if (newLength < 0)
3494          throw new NegativeArraySizeException("The array size is negative.");
3495        return copyOfRange(original, 0, newLength);
3496      }
3497    
3498      /**
3499       * Copies the specified range of the supplied array to a new
3500       * array, padding as necessary with <code>'\0'</code>
3501       * if <code>to</code> is greater than the length of the original
3502       * array.  <code>from</code> must be in the range zero to
3503       * <code>original.length</code> and can not be greater than
3504       * <code>to</code>.  The initial element of the
3505       * returned array will be equal to <code>original[from]</code>,
3506       * except where <code>from</code> is equal to <code>to</code>
3507       * (where a zero-length array will be returned) or <code>
3508       * <code>from</code> is equal to <code>original.length</code>
3509       * (where an array padded with <code>'\0'</code> will be
3510       * returned).  The returned array is always of length
3511       * <code>to - from</code>.
3512       *
3513       * @param original the array from which to copy.
3514       * @param from the initial index of the range, inclusive.
3515       * @param to the final index of the range, exclusive.
3516       * @return a copy of the specified range, with padding to
3517       *         obtain the required length.
3518       * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3519       *                                        or <code>from > original.length</code>
3520       * @throws IllegalArgumentException if <code>from > to</code>
3521       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3522       * @since 1.6
3523       * @see #copyOf(char[],int)
3524       */
3525      public static char[] copyOfRange(char[] original, int from, int to)
3526      {
3527        if (from > to)
3528          throw new IllegalArgumentException("The initial index is after " +
3529                                             "the final index.");
3530        char[] newArray = new char[to - from];
3531        if (to > original.length)
3532          {
3533            System.arraycopy(original, from, newArray, 0,
3534                             original.length - from);
3535            fill(newArray, original.length, newArray.length, '\0');
3536          }
3537        else
3538          System.arraycopy(original, from, newArray, 0, to - from);
3539        return newArray;
3540      }
3541    
3542      /**
3543       * Returns a copy of the supplied array, truncating or padding as
3544       * necessary with <code>0d</code> to obtain the specified length.
3545       * Indices that are valid for both arrays will return the same value.
3546       * Indices that only exist in the returned array (due to the new length
3547       * being greater than the original length) will return <code>0d</code>.
3548       * This is equivalent to calling
3549       * <code>copyOfRange(original, 0, newLength)</code>.
3550       *
3551       * @param original the original array to be copied.
3552       * @param newLength the length of the returned array.
3553       * @return a copy of the original array, truncated or padded with
3554       *         <code>0d</code> to obtain the required length.
3555       * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3556       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3557       * @since 1.6
3558       * @see #copyOfRange(double[],int,int)
3559       */
3560      public static double[] copyOf(double[] original, int newLength)
3561      {
3562        if (newLength < 0)
3563          throw new NegativeArraySizeException("The array size is negative.");
3564        return copyOfRange(original, 0, newLength);
3565      }
3566    
3567      /**
3568       * Copies the specified range of the supplied array to a new
3569       * array, padding as necessary with <code>0d</code>
3570       * if <code>to</code> is greater than the length of the original
3571       * array.  <code>from</code> must be in the range zero to
3572       * <code>original.length</code> and can not be greater than
3573       * <code>to</code>.  The initial element of the
3574       * returned array will be equal to <code>original[from]</code>,
3575       * except where <code>from</code> is equal to <code>to</code>
3576       * (where a zero-length array will be returned) or <code>
3577       * <code>from</code> is equal to <code>original.length</code>
3578       * (where an array padded with <code>0d</code> will be
3579       * returned).  The returned array is always of length
3580       * <code>to - from</code>.
3581       *
3582       * @param original the array from which to copy.
3583       * @param from the initial index of the range, inclusive.
3584       * @param to the final index of the range, exclusive.
3585       * @return a copy of the specified range, with padding to
3586       *         obtain the required length.
3587       * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3588       *                                        or <code>from > original.length</code>
3589       * @throws IllegalArgumentException if <code>from > to</code>
3590       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3591       * @since 1.6
3592       * @see #copyOf(double[],int)
3593       */
3594      public static double[] copyOfRange(double[] original, int from, int to)
3595      {
3596        if (from > to)
3597          throw new IllegalArgumentException("The initial index is after " +
3598                                             "the final index.");
3599        double[] newArray = new double[to - from];
3600        if (to > original.length)
3601          {
3602            System.arraycopy(original, from, newArray, 0,
3603                             original.length - from);
3604            fill(newArray, original.length, newArray.length, 0d);
3605          }
3606        else
3607          System.arraycopy(original, from, newArray, 0, to - from);
3608        return newArray;
3609      }
3610    
3611      /**
3612       * Returns a copy of the supplied array, truncating or padding as
3613       * necessary with <code>0f</code> to obtain the specified length.
3614       * Indices that are valid for both arrays will return the same value.
3615       * Indices that only exist in the returned array (due to the new length
3616       * being greater than the original length) will return <code>0f</code>.
3617       * This is equivalent to calling
3618       * <code>copyOfRange(original, 0, newLength)</code>.
3619       *
3620       * @param original the original array to be copied.
3621       * @param newLength the length of the returned array.
3622       * @return a copy of the original array, truncated or padded with
3623       *         <code>0f</code> to obtain the required length.
3624       * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3625       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3626       * @since 1.6
3627       * @see #copyOfRange(float[],int,int)
3628       */
3629      public static float[] copyOf(float[] original, int newLength)
3630      {
3631        if (newLength < 0)
3632          throw new NegativeArraySizeException("The array size is negative.");
3633        return copyOfRange(original, 0, newLength);
3634      }
3635    
3636      /**
3637       * Copies the specified range of the supplied array to a new
3638       * array, padding as necessary with <code>0f</code>
3639       * if <code>to</code> is greater than the length of the original
3640       * array.  <code>from</code> must be in the range zero to
3641       * <code>original.length</code> and can not be greater than
3642       * <code>to</code>.  The initial element of the
3643       * returned array will be equal to <code>original[from]</code>,
3644       * except where <code>from</code> is equal to <code>to</code>
3645       * (where a zero-length array will be returned) or <code>
3646       * <code>from</code> is equal to <code>original.length</code>
3647       * (where an array padded with <code>0f</code> will be
3648       * returned).  The returned array is always of length
3649       * <code>to - from</code>.
3650       *
3651       * @param original the array from which to copy.
3652       * @param from the initial index of the range, inclusive.
3653       * @param to the final index of the range, exclusive.
3654       * @return a copy of the specified range, with padding to
3655       *         obtain the required length.
3656       * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3657       *                                        or <code>from > original.length</code>
3658       * @throws IllegalArgumentException if <code>from > to</code>
3659       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3660       * @since 1.6
3661       * @see #copyOf(float[],int)
3662       */
3663      public static float[] copyOfRange(float[] original, int from, int to)
3664      {
3665        if (from > to)
3666          throw new IllegalArgumentException("The initial index is after " +
3667                                             "the final index.");
3668        float[] newArray = new float[to - from];
3669        if (to > original.length)
3670          {
3671            System.arraycopy(original, from, newArray, 0,
3672                             original.length - from);
3673            fill(newArray, original.length, newArray.length, 0f);
3674          }
3675        else
3676          System.arraycopy(original, from, newArray, 0, to - from);
3677        return newArray;
3678      }
3679    
3680      /**
3681       * Returns a copy of the supplied array, truncating or padding as
3682       * necessary with <code>0</code> to obtain the specified length.
3683       * Indices that are valid for both arrays will return the same value.
3684       * Indices that only exist in the returned array (due to the new length
3685       * being greater than the original length) will return <code>0</code>.
3686       * This is equivalent to calling
3687       * <code>copyOfRange(original, 0, newLength)</code>.
3688       *
3689       * @param original the original array to be copied.
3690       * @param newLength the length of the returned array.
3691       * @return a copy of the original array, truncated or padded with
3692       *         <code>0</code> to obtain the required length.
3693       * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3694       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3695       * @since 1.6
3696       * @see #copyOfRange(int[],int,int)
3697       */
3698      public static int[] copyOf(int[] original, int newLength)
3699      {
3700        if (newLength < 0)
3701          throw new NegativeArraySizeException("The array size is negative.");
3702        return copyOfRange(original, 0, newLength);
3703      }
3704    
3705      /**
3706       * Copies the specified range of the supplied array to a new
3707       * array, padding as necessary with <code>0</code>
3708       * if <code>to</code> is greater than the length of the original
3709       * array.  <code>from</code> must be in the range zero to
3710       * <code>original.length</code> and can not be greater than
3711       * <code>to</code>.  The initial element of the
3712       * returned array will be equal to <code>original[from]</code>,
3713       * except where <code>from</code> is equal to <code>to</code>
3714       * (where a zero-length array will be returned) or <code>
3715       * <code>from</code> is equal to <code>original.length</code>
3716       * (where an array padded with <code>0</code> will be
3717       * returned).  The returned array is always of length
3718       * <code>to - from</code>.
3719       *
3720       * @param original the array from which to copy.
3721       * @param from the initial index of the range, inclusive.
3722       * @param to the final index of the range, exclusive.
3723       * @return a copy of the specified range, with padding to
3724       *         obtain the required length.
3725       * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3726       *                                        or <code>from > original.length</code>
3727       * @throws IllegalArgumentException if <code>from > to</code>
3728       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3729       * @since 1.6
3730       * @see #copyOf(int[],int)
3731       */
3732      public static int[] copyOfRange(int[] original, int from, int to)
3733      {
3734        if (from > to)
3735          throw new IllegalArgumentException("The initial index is after " +
3736                                             "the final index.");
3737        int[] newArray = new int[to - from];
3738        if (to > original.length)
3739          {
3740            System.arraycopy(original, from, newArray, 0,
3741                             original.length - from);
3742            fill(newArray, original.length, newArray.length, 0);
3743          }
3744        else
3745          System.arraycopy(original, from, newArray, 0, to - from);
3746        return newArray;
3747      }
3748    
3749      /**
3750       * Returns a copy of the supplied array, truncating or padding as
3751       * necessary with <code>0L</code> to obtain the specified length.
3752       * Indices that are valid for both arrays will return the same value.
3753       * Indices that only exist in the returned array (due to the new length
3754       * being greater than the original length) will return <code>0L</code>.
3755       * This is equivalent to calling
3756       * <code>copyOfRange(original, 0, newLength)</code>.
3757       *
3758       * @param original the original array to be copied.
3759       * @param newLength the length of the returned array.
3760       * @return a copy of the original array, truncated or padded with
3761       *         <code>0L</code> to obtain the required length.
3762       * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3763       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3764       * @since 1.6
3765       * @see #copyOfRange(long[],int,int)
3766       */
3767      public static long[] copyOf(long[] original, int newLength)
3768      {
3769        if (newLength < 0)
3770          throw new NegativeArraySizeException("The array size is negative.");
3771        return copyOfRange(original, 0, newLength);
3772      }
3773    
3774      /**
3775       * Copies the specified range of the supplied array to a new
3776       * array, padding as necessary with <code>0L</code>
3777       * if <code>to</code> is greater than the length of the original
3778       * array.  <code>from</code> must be in the range zero to
3779       * <code>original.length</code> and can not be greater than
3780       * <code>to</code>.  The initial element of the
3781       * returned array will be equal to <code>original[from]</code>,
3782       * except where <code>from</code> is equal to <code>to</code>
3783       * (where a zero-length array will be returned) or <code>
3784       * <code>from</code> is equal to <code>original.length</code>
3785       * (where an array padded with <code>0L</code> will be
3786       * returned).  The returned array is always of length
3787       * <code>to - from</code>.
3788       *
3789       * @param original the array from which to copy.
3790       * @param from the initial index of the range, inclusive.
3791       * @param to the final index of the range, exclusive.
3792       * @return a copy of the specified range, with padding to
3793       *         obtain the required length.
3794       * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3795       *                                        or <code>from > original.length</code>
3796       * @throws IllegalArgumentException if <code>from > to</code>
3797       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3798       * @since 1.6
3799       * @see #copyOf(long[],int)
3800       */
3801      public static long[] copyOfRange(long[] original, int from, int to)
3802      {
3803        if (from > to)
3804          throw new IllegalArgumentException("The initial index is after " +
3805                                             "the final index.");
3806        long[] newArray = new long[to - from];
3807        if (to > original.length)
3808          {
3809            System.arraycopy(original, from, newArray, 0,
3810                             original.length - from);
3811            fill(newArray, original.length, newArray.length, 0L);
3812          }
3813        else
3814          System.arraycopy(original, from, newArray, 0, to - from);
3815        return newArray;
3816      }
3817    
3818      /**
3819       * Returns a copy of the supplied array, truncating or padding as
3820       * necessary with <code>(short)0</code> to obtain the specified length.
3821       * Indices that are valid for both arrays will return the same value.
3822       * Indices that only exist in the returned array (due to the new length
3823       * being greater than the original length) will return <code>(short)0</code>.
3824       * This is equivalent to calling
3825       * <code>copyOfRange(original, 0, newLength)</code>.
3826       *
3827       * @param original the original array to be copied.
3828       * @param newLength the length of the returned array.
3829       * @return a copy of the original array, truncated or padded with
3830       *         <code>(short)0</code> to obtain the required length.
3831       * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3832       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3833       * @since 1.6
3834       * @see #copyOfRange(short[],int,int)
3835       */
3836      public static short[] copyOf(short[] original, int newLength)
3837      {
3838        if (newLength < 0)
3839          throw new NegativeArraySizeException("The array size is negative.");
3840        return copyOfRange(original, 0, newLength);
3841      }
3842    
3843      /**
3844       * Copies the specified range of the supplied array to a new
3845       * array, padding as necessary with <code>(short)0</code>
3846       * if <code>to</code> is greater than the length of the original
3847       * array.  <code>from</code> must be in the range zero to
3848       * <code>original.length</code> and can not be greater than
3849       * <code>to</code>.  The initial element of the
3850       * returned array will be equal to <code>original[from]</code>,
3851       * except where <code>from</code> is equal to <code>to</code>
3852       * (where a zero-length array will be returned) or <code>
3853       * <code>from</code> is equal to <code>original.length</code>
3854       * (where an array padded with <code>(short)0</code> will be
3855       * returned).  The returned array is always of length
3856       * <code>to - from</code>.
3857       *
3858       * @param original the array from which to copy.
3859       * @param from the initial index of the range, inclusive.
3860       * @param to the final index of the range, exclusive.
3861       * @return a copy of the specified range, with padding to
3862       *         obtain the required length.
3863       * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3864       *                                        or <code>from > original.length</code>
3865       * @throws IllegalArgumentException if <code>from > to</code>
3866       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3867       * @since 1.6
3868       * @see #copyOf(short[],int)
3869       */
3870      public static short[] copyOfRange(short[] original, int from, int to)
3871      {
3872        if (from > to)
3873          throw new IllegalArgumentException("The initial index is after " +
3874                                             "the final index.");
3875        short[] newArray = new short[to - from];
3876        if (to > original.length)
3877          {
3878            System.arraycopy(original, from, newArray, 0,
3879                             original.length - from);
3880            fill(newArray, original.length, newArray.length, (short)0);
3881          }
3882        else
3883          System.arraycopy(original, from, newArray, 0, to - from);
3884        return newArray;
3885      }
3886    
3887      /**
3888       * Returns a copy of the supplied array, truncating or padding as
3889       * necessary with <code>null</code> to obtain the specified length.
3890       * Indices that are valid for both arrays will return the same value.
3891       * Indices that only exist in the returned array (due to the new length
3892       * being greater than the original length) will return <code>null</code>.
3893       * This is equivalent to calling
3894       * <code>copyOfRange(original, 0, newLength)</code>.
3895       *
3896       * @param original the original array to be copied.
3897       * @param newLength the length of the returned array.
3898       * @return a copy of the original array, truncated or padded with
3899       *         <code>null</code> to obtain the required length.
3900       * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3901       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3902       * @since 1.6
3903       * @see #copyOfRange(T[],int,int)
3904       */
3905      public static <T> T[] copyOf(T[] original, int newLength)
3906      {
3907        if (newLength < 0)
3908          throw new NegativeArraySizeException("The array size is negative.");
3909        return copyOfRange(original, 0, newLength);
3910      }
3911    
3912      /**
3913       * Copies the specified range of the supplied array to a new
3914       * array, padding as necessary with <code>null</code>
3915       * if <code>to</code> is greater than the length of the original
3916       * array.  <code>from</code> must be in the range zero to
3917       * <code>original.length</code> and can not be greater than
3918       * <code>to</code>.  The initial element of the
3919       * returned array will be equal to <code>original[from]</code>,
3920       * except where <code>from</code> is equal to <code>to</code>
3921       * (where a zero-length array will be returned) or <code>
3922       * <code>from</code> is equal to <code>original.length</code>
3923       * (where an array padded with <code>null</code> will be
3924       * returned).  The returned array is always of length
3925       * <code>to - from</code>.
3926       *
3927       * @param original the array from which to copy.
3928       * @param from the initial index of the range, inclusive.
3929       * @param to the final index of the range, exclusive.
3930       * @return a copy of the specified range, with padding to
3931       *         obtain the required length.
3932       * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
3933       *                                        or <code>from > original.length</code>
3934       * @throws IllegalArgumentException if <code>from > to</code>
3935       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3936       * @since 1.6
3937       * @see #copyOf(T[],int)
3938       */
3939      public static <T> T[] copyOfRange(T[] original, int from, int to)
3940      {
3941        if (from > to)
3942          throw new IllegalArgumentException("The initial index is after " +
3943                                             "the final index.");
3944        Class elemType = original.getClass().getComponentType();
3945        T[] newArray = (T[]) Array.newInstance(elemType, to - from);
3946        if (to > original.length)
3947          {
3948            System.arraycopy(original, from, newArray, 0,
3949                             original.length - from);
3950            fill(newArray, original.length, newArray.length, null);
3951          }
3952        else
3953          System.arraycopy(original, from, newArray, 0, to - from);
3954        return newArray;
3955      }
3956    
3957      /**
3958       * Returns a copy of the supplied array, truncating or padding as
3959       * necessary with <code>null</code> to obtain the specified length.
3960       * Indices that are valid for both arrays will return the same value.
3961       * Indices that only exist in the returned array (due to the new length
3962       * being greater than the original length) will return <code>null</code>.
3963       * This is equivalent to calling
3964       * <code>copyOfRange(original, 0, newLength, newType)</code>.  The returned
3965       * array will be of the specified type, <code>newType</code>.
3966       *
3967       * @param original the original array to be copied.
3968       * @param newLength the length of the returned array.
3969       * @param newType the type of the returned array.
3970       * @return a copy of the original array, truncated or padded with
3971       *         <code>null</code> to obtain the required length.
3972       * @throws NegativeArraySizeException if <code>newLength</code> is negative.
3973       * @throws NullPointerException if <code>original</code> is <code>null</code>.
3974       * @since 1.6
3975       * @see #copyOfRange(U[],int,int,Class)
3976       */
3977      public static <T,U> T[] copyOf(U[] original, int newLength,
3978                                     Class<? extends T[]> newType)
3979      {
3980        if (newLength < 0)
3981          throw new NegativeArraySizeException("The array size is negative.");
3982        return copyOfRange(original, 0, newLength, newType);
3983      }
3984    
3985      /**
3986       * Copies the specified range of the supplied array to a new
3987       * array, padding as necessary with <code>null</code>
3988       * if <code>to</code> is greater than the length of the original
3989       * array.  <code>from</code> must be in the range zero to
3990       * <code>original.length</code> and can not be greater than
3991       * <code>to</code>.  The initial element of the
3992       * returned array will be equal to <code>original[from]</code>,
3993       * except where <code>from</code> is equal to <code>to</code>
3994       * (where a zero-length array will be returned) or <code>
3995       * <code>from</code> is equal to <code>original.length</code>
3996       * (where an array padded with <code>null</code> will be
3997       * returned).  The returned array is always of length
3998       * <code>to - from</code> and will be of the specified type,
3999       * <code>newType</code>.
4000       *
4001       * @param original the array from which to copy.
4002       * @param from the initial index of the range, inclusive.
4003       * @param to the final index of the range, exclusive.
4004       * @param newType the type of the returned array.
4005       * @return a copy of the specified range, with padding to
4006       *         obtain the required length.
4007       * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
4008       *                                        or <code>from > original.length</code>
4009       * @throws IllegalArgumentException if <code>from > to</code>
4010       * @throws NullPointerException if <code>original</code> is <code>null</code>.
4011       * @since 1.6
4012       * @see #copyOf(T[],int)
4013       */
4014      public static <T,U> T[] copyOfRange(U[] original, int from, int to,
4015                                          Class<? extends T[]> newType)
4016      {
4017        if (from > to)
4018          throw new IllegalArgumentException("The initial index is after " +
4019                                             "the final index.");
4020        T[] newArray = (T[]) Array.newInstance(newType.getComponentType(),
4021                                               to - from);
4022        if (to > original.length)
4023          {
4024            System.arraycopy(original, from, newArray, 0,
4025                             original.length - from);
4026            fill(newArray, original.length, newArray.length, null);
4027          }
4028        else
4029          System.arraycopy(original, from, newArray, 0, to - from);
4030        return newArray;
4031      }
4032    }