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
005This file is part of GNU Classpath.
006
007GNU Classpath is free software; you can redistribute it and/or modify
008it under the terms of the GNU General Public License as published by
009the Free Software Foundation; either version 2, or (at your option)
010any later version.
011
012GNU Classpath is distributed in the hope that it will be useful, but
013WITHOUT ANY WARRANTY; without even the implied warranty of
014MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
015General Public License for more details.
016
017You should have received a copy of the GNU General Public License
018along with GNU Classpath; see the file COPYING.  If not, write to the
019Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02002110-1301 USA.
021
022Linking this library statically or dynamically with other modules is
023making a combined work based on this library.  Thus, the terms and
024conditions of the GNU General Public License cover the whole
025combination.
026
027As a special exception, the copyright holders of this library give you
028permission to link this library with independent modules to produce an
029executable, regardless of the license terms of these independent
030modules, and to copy and distribute the resulting executable under
031terms of your choice, provided that you also meet, for each linked
032independent module, the terms and conditions of the license of that
033module.  An independent module is a module which is not derived from
034or based on this library.  If you modify this library, you may extend
035this exception to your version of the library, but you are not
036obligated to do so.  If you do not wish to do so, delete this
037exception statement from your version. */
038
039
040package java.util;
041
042import gnu.java.lang.CPStringBuilder;
043
044import java.io.Serializable;
045import 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 */
070public 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}