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