Jumbo patch:

* Imported beans and serialization
* Updated IA-64 port
* Miscellaneous bug fixes

From-SVN: r34028

1 files changed, 1757 insertions, 0 deletions

diff --git a/libjava/java/util/Arrays.java b/libjava/java/util/Arrays.java
new file mode 100644
index 0000000..fc51d38
--- /dev/null
+++ b/libjava/java/util/Arrays.java
@@ -0,0 +1,1757 @@
+/* Arrays.java -- Utility class with methods to operate on arrays
+   Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+ 
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+// TO DO:
+// ~ Fix the behaviour of sort and binarySearch as applied to float and double
+//   arrays containing NaN values. See the JDC, bug ID 4143272.
+
+package java.util;
+
+/**
+ * This class contains various static utility methods performing operations on
+ * arrays, and a method to provide a List "view" of an array to facilitate
+ * using arrays with Collection-based APIs.
+ */
+public class Arrays {
+
+  /**
+   * This class is non-instantiable.
+   */
+  private Arrays() {
+  }
+
+  private static Comparator defaultComparator = new Comparator() {
+    public int compare(Object o1, Object o2) {
+      return ((Comparable)o1).compareTo(o2);
+    }
+  };
+
+  /**
+   * Perform a binary search of a byte array for a key. The array must be
+   * sorted (as by the sort() method) - if it is not, the behaviour of this
+   * method is undefined, and may be an infinite loop. If the array contains
+   * the key more than once, any one of them may be found. Note: although the
+   * specification allows for an infinite loop if the array is unsorted, it
+   * will not happen in this implementation.
+   *
+   * @param a the array to search (must be sorted)
+   * @param key the value to search for
+   * @returns the index at which the key was found, or -n-1 if it was not
+   *   found, where n is the index of the first value higher than key or
+   *   a.length if there is no such value.
+   */
+  public static int binarySearch(byte[] a, byte key) {
+    int low = 0;
+    int hi = a.length - 1;
+    int mid = 0;
+    while (low <= hi) {
+      mid = (low + hi) >> 1;
+      final byte d = a[mid];
+      if (d == key) {
+        return mid;
+      } else if (d > key) {
+        hi = mid - 1;
+      } else {
+        low = ++mid; // This gets the insertion point right on the last loop
+      }
+    }
+    return -mid - 1;
+  }
+
+  /**
+   * Perform a binary search of a char array for a key. The array must be
+   * sorted (as by the sort() method) - if it is not, the behaviour of this
+   * method is undefined, and may be an infinite loop. If the array contains
+   * the key more than once, any one of them may be found. Note: although the
+   * specification allows for an infinite loop if the array is unsorted, it
+   * will not happen in this implementation.
+   *
+   * @param a the array to search (must be sorted)
+   * @param key the value to search for
+   * @returns the index at which the key was found, or -n-1 if it was not
+   *   found, where n is the index of the first value higher than key or
+   *   a.length if there is no such value.
+   */
+  public static int binarySearch(char[] a, char key) {
+    int low = 0;
+    int hi = a.length - 1;
+    int mid = 0;
+    while (low <= hi) {
+      mid = (low + hi) >> 1;
+      final char d = a[mid];
+      if (d == key) {
+        return mid;
+      } else if (d > key) {
+        hi = mid - 1;
+      } else {
+        low = ++mid; // This gets the insertion point right on the last loop
+      }
+    }
+    return -mid - 1;
+  }
+
+  /**
+   * Perform a binary search of a double array for a key. The array must be
+   * sorted (as by the sort() method) - if it is not, the behaviour of this
+   * method is undefined, and may be an infinite loop. If the array contains
+   * the key more than once, any one of them may be found. Note: although the
+   * specification allows for an infinite loop if the array is unsorted, it
+   * will not happen in this implementation.
+   *
+   * @param a the array to search (must be sorted)
+   * @param key the value to search for
+   * @returns the index at which the key was found, or -n-1 if it was not
+   *   found, where n is the index of the first value higher than key or
+   *   a.length if there is no such value.
+   */
+  public static int binarySearch(double[] a, double key) {
+    int low = 0;
+    int hi = a.length - 1;
+    int mid = 0;
+    while (low <= hi) {
+      mid = (low + hi) >> 1;
+      final double d = a[mid];
+      if (d == key) {
+        return mid;
+      } else if (d > key) {
+        hi = mid - 1;
+      } else {
+        low = ++mid; // This gets the insertion point right on the last loop
+      }
+    }
+    return -mid - 1;
+  }
+
+  /**
+   * Perform a binary search of a float array for a key. The array must be
+   * sorted (as by the sort() method) - if it is not, the behaviour of this
+   * method is undefined, and may be an infinite loop. If the array contains
+   * the key more than once, any one of them may be found. Note: although the
+   * specification allows for an infinite loop if the array is unsorted, it
+   * will not happen in this implementation.
+   *
+   * @param a the array to search (must be sorted)
+   * @param key the value to search for
+   * @returns the index at which the key was found, or -n-1 if it was not
+   *   found, where n is the index of the first value higher than key or
+   *   a.length if there is no such value.
+   */
+  public static int binarySearch(float[] a, float key) {
+    int low = 0;
+    int hi = a.length - 1;
+    int mid = 0;
+    while (low <= hi) {
+      mid = (low + hi) >> 1;
+      final float d = a[mid];
+      if (d == key) {
+        return mid;
+      } else if (d > key) {
+        hi = mid - 1;
+      } else {
+        low = ++mid; // This gets the insertion point right on the last loop
+      }
+    }
+    return -mid - 1;
+  }
+
+  /**
+   * Perform a binary search of an int array for a key. The array must be
+   * sorted (as by the sort() method) - if it is not, the behaviour of this
+   * method is undefined, and may be an infinite loop. If the array contains
+   * the key more than once, any one of them may be found. Note: although the
+   * specification allows for an infinite loop if the array is unsorted, it
+   * will not happen in this implementation.
+   *
+   * @param a the array to search (must be sorted)
+   * @param key the value to search for
+   * @returns the index at which the key was found, or -n-1 if it was not
+   *   found, where n is the index of the first value higher than key or
+   *   a.length if there is no such value.
+   */
+  public static int binarySearch(int[] a, int key) {
+    int low = 0;
+    int hi = a.length - 1;
+    int mid = 0;
+    while (low <= hi) {
+      mid = (low + hi) >> 1;
+      final int d = a[mid];
+      if (d == key) {
+        return mid;
+      } else if (d > key) {
+        hi = mid - 1;
+      } else {
+        low = ++mid; // This gets the insertion point right on the last loop
+      }
+    }
+    return -mid - 1;
+  }
+
+  /**
+   * Perform a binary search of a long array for a key. The array must be
+   * sorted (as by the sort() method) - if it is not, the behaviour of this
+   * method is undefined, and may be an infinite loop. If the array contains
+   * the key more than once, any one of them may be found. Note: although the
+   * specification allows for an infinite loop if the array is unsorted, it
+   * will not happen in this implementation.
+   *
+   * @param a the array to search (must be sorted)
+   * @param key the value to search for
+   * @returns the index at which the key was found, or -n-1 if it was not
+   *   found, where n is the index of the first value higher than key or
+   *   a.length if there is no such value.
+   */
+  public static int binarySearch(long[] a, long key) {
+    int low = 0;
+    int hi = a.length - 1;
+    int mid = 0;
+    while (low <= hi) {
+      mid = (low + hi) >> 1;
+      final long d = a[mid];
+      if (d == key) {
+        return mid;
+      } else if (d > key) {
+        hi = mid - 1;
+      } else {
+        low = ++mid; // This gets the insertion point right on the last loop
+      }
+    }
+    return -mid - 1;
+  }
+
+  /**
+   * Perform a binary search of a short array for a key. The array must be
+   * sorted (as by the sort() method) - if it is not, the behaviour of this
+   * method is undefined, and may be an infinite loop. If the array contains
+   * the key more than once, any one of them may be found. Note: although the
+   * specification allows for an infinite loop if the array is unsorted, it
+   * will not happen in this implementation.
+   *
+   * @param a the array to search (must be sorted)
+   * @param key the value to search for
+   * @returns the index at which the key was found, or -n-1 if it was not
+   *   found, where n is the index of the first value higher than key or
+   *   a.length if there is no such value.
+   */
+  public static int binarySearch(short[] a, short key) {
+    int low = 0;
+    int hi = a.length - 1;
+    int mid = 0;
+    while (low <= hi) {
+      mid = (low + hi) >> 1;
+      final short d = a[mid];
+      if (d == key) {
+        return mid;
+      } else if (d > key) {
+        hi = mid - 1;
+      } else {
+        low = ++mid; // This gets the insertion point right on the last loop
+      }
+    }
+    return -mid - 1;
+  }
+
+  /**
+   * This method does the work for the Object binary search methods. 
+   * @exception NullPointerException if the specified comparator is null.
+   * @exception ClassCastException if the objects are not comparable by c.
+   */
+  private static int objectSearch(Object[] a, Object key, final Comparator c) {
+    int low = 0;
+    int hi = a.length - 1;
+    int mid = 0;
+    while (low <= hi) {
+      mid = (low + hi) >> 1;
+      final int d = c.compare(key, a[mid]);
+      if (d == 0) {
+        return mid;
+      } else if (d < 0) {
+        hi = mid - 1;
+      } else {
+        low = ++mid; // This gets the insertion point right on the last loop
+      }
+    }
+    return -mid - 1;
+  }
+
+  /**
+   * Perform a binary search of an Object array for a key, using the natural
+   * ordering of the elements. The array must be sorted (as by the sort()
+   * method) - if it is not, the behaviour of this method is undefined, and may
+   * be an infinite loop. Further, the key must be comparable with every item
+   * in the array. If the array contains the key more than once, any one of
+   * them may be found. Note: although the specification allows for an infinite
+   * loop if the array is unsorted, it will not happen in this (JCL)
+   * implementation.
+   *
+   * @param a the array to search (must be sorted)
+   * @param key the value to search for
+   * @returns the index at which the key was found, or -n-1 if it was not
+   *   found, where n is the index of the first value higher than key or
+   *   a.length if there is no such value.
+   * @exception ClassCastException if key could not be compared with one of the
+   *   elements of a
+   * @exception NullPointerException if a null element has compareTo called
+   */
+  public static int binarySearch(Object[] a, Object key) {
+    return objectSearch(a, key, defaultComparator);
+  }
+
+  /**
+   * Perform a binary search of an Object array for a key, using a supplied
+   * Comparator. The array must be sorted (as by the sort() method with the
+   * same Comparator) - if it is not, the behaviour of this method is
+   * undefined, and may be an infinite loop. Further, the key must be
+   * comparable with every item in the array. If the array contains the key
+   * more than once, any one of them may be found. Note: although the
+   * specification allows for an infinite loop if the array is unsorted, it
+   * will not happen in this (JCL) implementation.
+   *
+   * @param a the array to search (must be sorted)
+   * @param key the value to search for
+   * @param c the comparator by which the array is sorted
+   * @returns the index at which the key was found, or -n-1 if it was not
+   *   found, where n is the index of the first value higher than key or
+   *   a.length if there is no such value.
+   * @exception ClassCastException if key could not be compared with one of the
+   *   elements of a
+   */
+  public static int binarySearch(Object[] a, Object key, Comparator c) {
+    return objectSearch(a, key, c);
+  }
+
+  /**
+   * Compare two byte arrays for equality.
+   *
+   * @param a1 the first array to compare
+   * @param a2 the second array to compare
+   * @returns true if a1 and a2 are both null, or if a2 is of the same length
+   *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
+   */
+  public static boolean equals(byte[] a1, byte[] a2) {
+
+    // Quick test which saves comparing elements of the same array, and also
+    // catches the case that both are null.
+    if (a1 == a2) {
+      return true;
+    }
+    try {
+
+      // If they're the same length, test each element
+      if (a1.length == a2.length) {
+        for (int i = 0; i < a1.length; i++) {
+          if (a1[i] != a2[i]) {
+            return false;
+          }
+        }
+        return true;
+      }
+
+    // If a1 == null or a2 == null but not both then we will get a NullPointer
+    } catch (NullPointerException e) {
+    }
+
+    return false;
+  }
+
+  /**
+   * Compare two char arrays for equality.
+   *
+   * @param a1 the first array to compare
+   * @param a2 the second array to compare
+   * @returns true if a1 and a2 are both null, or if a2 is of the same length
+   *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
+   */
+  public static boolean equals(char[] a1, char[] a2) {
+
+    // Quick test which saves comparing elements of the same array, and also
+    // catches the case that both are null.
+    if (a1 == a2) {
+      return true;
+    }
+    try {
+
+      // If they're the same length, test each element
+      if (a1.length == a2.length) {
+        for (int i = 0; i < a1.length; i++) {
+          if (a1[i] != a2[i]) {
+            return false;
+          }
+        }
+        return true;
+      }
+
+    // If a1 == null or a2 == null but not both then we will get a NullPointer
+    } catch (NullPointerException e) {
+    }
+
+    return false;
+  }
+
+  /**
+   * Compare two double arrays for equality.
+   *
+   * @param a1 the first array to compare
+   * @param a2 the second array to compare
+   * @returns true if a1 and a2 are both null, or if a2 is of the same length
+   *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
+   */
+  public static boolean equals(double[] a1, double[] a2) {
+
+    // Quick test which saves comparing elements of the same array, and also
+    // catches the case that both are null.
+    if (a1 == a2) {
+      return true;
+    }
+    try {
+
+      // If they're the same length, test each element
+      if (a1.length == a2.length) {
+        for (int i = 0; i < a1.length; i++) {
+          if (a1[i] != a2[i]) {
+            return false;
+          }
+        }
+        return true;
+      }
+
+    // If a1 == null or a2 == null but not both then we will get a NullPointer
+    } catch (NullPointerException e) {
+    }
+
+    return false;
+  }
+
+  /**
+   * Compare two float arrays for equality.
+   *
+   * @param a1 the first array to compare
+   * @param a2 the second array to compare
+   * @returns true if a1 and a2 are both null, or if a2 is of the same length
+   *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
+   */
+  public static boolean equals(float[] a1, float[] a2) {
+
+    // Quick test which saves comparing elements of the same array, and also
+    // catches the case that both are null.
+    if (a1 == a2) {
+      return true;
+    }
+    try {
+
+      // If they're the same length, test each element
+      if (a1.length == a2.length) {
+        for (int i = 0; i < a1.length; i++) {
+          if (a1[i] != a2[i]) {
+            return false;
+          }
+        }
+        return true;
+      }
+
+    // If a1 == null or a2 == null but not both then we will get a NullPointer
+    } catch (NullPointerException e) {
+    }
+
+    return false;
+  }
+
+  /**
+   * Compare two long arrays for equality.
+   *
+   * @param a1 the first array to compare
+   * @param a2 the second array to compare
+   * @returns true if a1 and a2 are both null, or if a2 is of the same length
+   *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
+   */
+  public static boolean equals(long[] a1, long[] a2) {
+
+    // Quick test which saves comparing elements of the same array, and also
+    // catches the case that both are null.
+    if (a1 == a2) {
+      return true;
+    }
+    try {
+
+      // If they're the same length, test each element
+      if (a1.length == a2.length) {
+        for (int i = 0; i < a1.length; i++) {
+          if (a1[i] != a2[i]) {
+            return false;
+          }
+        }
+        return true;
+      }
+
+    // If a1 == null or a2 == null but not both then we will get a NullPointer
+    } catch (NullPointerException e) {
+    }
+
+    return false;
+  }
+
+  /**
+   * Compare two short arrays for equality.
+   *
+   * @param a1 the first array to compare
+   * @param a2 the second array to compare
+   * @returns true if a1 and a2 are both null, or if a2 is of the same length
+   *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
+   */
+  public static boolean equals(short[] a1, short[] a2) {
+
+    // Quick test which saves comparing elements of the same array, and also
+    // catches the case that both are null.
+    if (a1 == a2) {
+      return true;
+    }
+    try {
+
+      // If they're the same length, test each element
+      if (a1.length == a2.length) {
+        for (int i = 0; i < a1.length; i++) {
+          if (a1[i] != a2[i]) {
+            return false;
+          }
+        }
+        return true;
+      }
+
+    // If a1 == null or a2 == null but not both then we will get a NullPointer
+    } catch (NullPointerException e) {
+    }
+
+    return false;
+  }
+
+  /**
+   * Compare two boolean arrays for equality.
+   *
+   * @param a1 the first array to compare
+   * @param a2 the second array to compare
+   * @returns true if a1 and a2 are both null, or if a2 is of the same length
+   *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
+   */
+  public static boolean equals(boolean[] a1, boolean[] a2) {
+
+    // Quick test which saves comparing elements of the same array, and also
+    // catches the case that both are null.
+    if (a1 == a2) {
+      return true;
+    }
+    try {
+
+      // If they're the same length, test each element
+      if (a1.length == a2.length) {
+        for (int i = 0; i < a1.length; i++) {
+          if (a1[i] != a2[i]) {
+            return false;
+          }
+        }
+        return true;
+      }
+
+    // If a1 == null or a2 == null but not both then we will get a NullPointer
+    } catch (NullPointerException e) {
+    }
+
+    return false;
+  }
+
+  /**
+   * Compare two int arrays for equality.
+   *
+   * @param a1 the first array to compare
+   * @param a2 the second array to compare
+   * @returns true if a1 and a2 are both null, or if a2 is of the same length
+   *   as a1, and for each 0 <= i < a1.length, a1[i] == a2[i]
+   */
+  public static boolean equals(int[] a1, int[] a2) {
+
+    // Quick test which saves comparing elements of the same array, and also
+    // catches the case that both are null.
+    if (a1 == a2) {
+      return true;
+    }
+    try {
+
+      // If they're the same length, test each element
+      if (a1.length == a2.length) {
+        for (int i = 0; i < a1.length; i++) {
+          if (a1[i] != a2[i]) {
+            return false;
+          }
+        }
+        return true;
+      }
+
+    // If a1 == null or a2 == null but not both then we will get a NullPointer
+    } catch (NullPointerException e) {
+    }
+
+    return false;
+  }
+
+  /**
+   * Compare two Object arrays for equality.
+   *
+   * @param a1 the first array to compare
+   * @param a2 the second array to compare
+   * @returns true if a1 and a2 are both null, or if a1 is of the same length
+   *   as a2, and for each 0 <= i < a.length, a1[i] == null ? a2[i] == null :
+   *   a1[i].equals(a2[i]).
+   */
+  public static boolean equals(Object[] a1, Object[] a2) {
+
+    // Quick test which saves comparing elements of the same array, and also
+    // catches the case that both are null.
+    if (a1 == a2) {
+      return true;
+    }
+    try {
+
+      // If they're the same length, test each element
+      if (a1.length == a2.length) {
+        for (int i = 0; i < a1.length; i++) {
+          if (!(a1[i] == null ? a2[i] == null : a1[i].equals(a2[i]))) {
+            return false;
+          }
+        }
+        return true;
+      }
+
+    // If a1 == null or a2 == null but not both then we will get a NullPointer
+    } catch (NullPointerException e) {
+    }
+
+    return false;
+  }
+
+  /**
+   * Fill an array with a boolean value.
+   *
+   * @param a the array to fill
+   * @param val the value to fill it with
+   */
+  public static void fill(boolean[] a, boolean val) {
+    // This implementation is slightly inefficient timewise, but the extra
+    // effort over inlining it is O(1) and small, and I refuse to repeat code
+    // if it can be helped.
+    fill(a, 0, a.length, val);
+  }
+
+  /**
+   * Fill a range of an array with a boolean value.
+   *
+   * @param a the array to fill
+   * @param fromIndex the index to fill from, inclusive
+   * @param toIndex the index to fill to, exclusive
+   * @param val the value to fill with
+   */
+  public static void fill(boolean[] a, int fromIndex, int toIndex,
+                          boolean val) {
+    for (int i = fromIndex; i < toIndex; i++) {
+      a[i] = val;
+    }
+  }
+
+  /**
+   * Fill an array with a byte value.
+   *
+   * @param a the array to fill
+   * @param val the value to fill it with
+   */
+  public static void fill(byte[] a, byte val) {
+    // This implementation is slightly inefficient timewise, but the extra
+    // effort over inlining it is O(1) and small, and I refuse to repeat code
+    // if it can be helped.
+    fill(a, 0, a.length, val);
+  }
+
+  /**
+   * Fill a range of an array with a byte value.
+   *
+   * @param a the array to fill
+   * @param fromIndex the index to fill from, inclusive
+   * @param toIndex the index to fill to, exclusive
+   * @param val the value to fill with
+   */
+  public static void fill(byte[] a, int fromIndex, int toIndex, byte val) {
+    for (int i = fromIndex; i < toIndex; i++) {
+      a[i] = val;
+    }
+  }
+
+  /**
+   * Fill an array with a char value.
+   *
+   * @param a the array to fill
+   * @param val the value to fill it with
+   */
+  public static void fill(char[] a, char val) {
+    // This implementation is slightly inefficient timewise, but the extra
+    // effort over inlining it is O(1) and small, and I refuse to repeat code
+    // if it can be helped.
+    fill(a, 0, a.length, val);
+  }
+
+  /**
+   * Fill a range of an array with a char value.
+   *
+   * @param a the array to fill
+   * @param fromIndex the index to fill from, inclusive
+   * @param toIndex the index to fill to, exclusive
+   * @param val the value to fill with
+   */
+  public static void fill(char[] a, int fromIndex, int toIndex, char val) {
+    for (int i = fromIndex; i < toIndex; i++) {
+      a[i] = val;
+    }
+  }
+
+  /**
+   * Fill an array with a double value.
+   *
+   * @param a the array to fill
+   * @param val the value to fill it with
+   */
+  public static void fill(double[] a, double val) {
+    // This implementation is slightly inefficient timewise, but the extra
+    // effort over inlining it is O(1) and small, and I refuse to repeat code
+    // if it can be helped.
+    fill(a, 0, a.length, val);
+  }
+
+  /**
+   * Fill a range of an array with a double value.
+   *
+   * @param a the array to fill
+   * @param fromIndex the index to fill from, inclusive
+   * @param toIndex the index to fill to, exclusive
+   * @param val the value to fill with
+   */
+  public static void fill(double[] a, int fromIndex, int toIndex, double val) {
+    for (int i = fromIndex; i < toIndex; i++) {
+      a[i] = val;
+    }
+  }
+
+  /**
+   * Fill an array with a float value.
+   *
+   * @param a the array to fill
+   * @param val the value to fill it with
+   */
+  public static void fill(float[] a, float val) {
+    // This implementation is slightly inefficient timewise, but the extra
+    // effort over inlining it is O(1) and small, and I refuse to repeat code
+    // if it can be helped.
+    fill(a, 0, a.length, val);
+  }
+
+  /**
+   * Fill a range of an array with a float value.
+   *
+   * @param a the array to fill
+   * @param fromIndex the index to fill from, inclusive
+   * @param toIndex the index to fill to, exclusive
+   * @param val the value to fill with
+   */
+  public static void fill(float[] a, int fromIndex, int toIndex, float val) {
+    for (int i = fromIndex; i < toIndex; i++) {
+      a[i] = val;
+    }
+  }
+
+  /**
+   * Fill an array with an int value.
+   *
+   * @param a the array to fill
+   * @param val the value to fill it with
+   */
+  public static void fill(int[] a, int val) {
+    // This implementation is slightly inefficient timewise, but the extra
+    // effort over inlining it is O(1) and small, and I refuse to repeat code
+    // if it can be helped.
+    fill(a, 0, a.length, val);
+  }
+
+  /**
+   * Fill a range of an array with an int value.
+   *
+   * @param a the array to fill
+   * @param fromIndex the index to fill from, inclusive
+   * @param toIndex the index to fill to, exclusive
+   * @param val the value to fill with
+   */
+  public static void fill(int[] a, int fromIndex, int toIndex, int val) {
+    for (int i = fromIndex; i < toIndex; i++) {
+      a[i] = val;
+    }
+  }
+
+  /**
+   * Fill an array with a long value.
+   *
+   * @param a the array to fill
+   * @param val the value to fill it with
+   */
+  public static void fill(long[] a, long val) {
+    // This implementation is slightly inefficient timewise, but the extra
+    // effort over inlining it is O(1) and small, and I refuse to repeat code
+    // if it can be helped.
+    fill(a, 0, a.length, val);
+  }
+
+  /**
+   * Fill a range of an array with a long value.
+   *
+   * @param a the array to fill
+   * @param fromIndex the index to fill from, inclusive
+   * @param toIndex the index to fill to, exclusive
+   * @param val the value to fill with
+   */
+  public static void fill(long[] a, int fromIndex, int toIndex, long val) {
+    for (int i = fromIndex; i < toIndex; i++) {
+      a[i] = val;
+    }
+  }
+
+  /**
+   * Fill an array with a short value.
+   *
+   * @param a the array to fill
+   * @param val the value to fill it with
+   */
+  public static void fill(short[] a, short val) {
+    // This implementation is slightly inefficient timewise, but the extra
+    // effort over inlining it is O(1) and small, and I refuse to repeat code
+    // if it can be helped.
+    fill(a, 0, a.length, val);
+  }
+
+  /**
+   * Fill a range of an array with a short value.
+   *
+   * @param a the array to fill
+   * @param fromIndex the index to fill from, inclusive
+   * @param toIndex the index to fill to, exclusive
+   * @param val the value to fill with
+   */
+  public static void fill(short[] a, int fromIndex, int toIndex, short val) {
+    for (int i = fromIndex; i < toIndex; i++) {
+      a[i] = val;
+    }
+  }
+
+  /**
+   * Fill an array with an Object value.
+   *
+   * @param a the array to fill
+   * @param val the value to fill it with
+   * @exception ClassCastException if val is not an instance of the element
+   *   type of a.
+   */
+  public static void fill(Object[] a, Object val) {
+    // This implementation is slightly inefficient timewise, but the extra
+    // effort over inlining it is O(1) and small, and I refuse to repeat code
+    // if it can be helped.
+    fill(a, 0, a.length, val);
+  }
+
+  /**
+   * Fill a range of an array with an Object value.
+   *
+   * @param a the array to fill
+   * @param fromIndex the index to fill from, inclusive
+   * @param toIndex the index to fill to, exclusive
+   * @param val the value to fill with
+   * @exception ClassCastException if val is not an instance of the element
+   *   type of a.
+   */
+  public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
+    for (int i = fromIndex; i < toIndex; i++) {
+      a[i] = val;
+    }
+  }
+
+  // Thanks to Paul Fisher <rao@gnu.org> for finding this quicksort algorithm
+  // as specified by Sun and porting it to Java.
+
+  /**
+   * Sort a byte array into ascending order. The sort algorithm is an optimised
+   * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
+   * "Engineering a Sort Function", Software-Practice and Experience, Vol.
+   * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
+   * performance on many arrays that would take quadratic time with a standard
+   * quicksort.
+   *
+   * @param a the array to sort
+   */
+  public static void sort(byte[] a) {
+    qsort(a, 0, a.length);
+  }
+
+  private static short cmp(byte i, byte j) {
+    return (short)(i-j);
+  }
+
+  private static int med3(int a, int b, int c, byte[] d) {
+    return cmp(d[a], d[b]) < 0 ? 
+      (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
+    : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
+  }
+  
+  private static void swap(int i, int j, byte[] a) {
+    byte c = a[i];
+    a[i] = a[j];
+    a[j] = c;
+  }
+
+  private static void qsort(byte[] a, int start, int n) {
+    // use an insertion sort on small arrays
+    if (n < 7) {
+      for (int i = start + 1; i < start + n; i++)
+        for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--)
+          swap(j, j-1, a);
+      return;
+    }
+
+    int pm = n/2;       // small arrays, middle element
+    if (n > 7) {
+      int pl = start;
+      int pn = start + n-1;
+
+      if (n > 40) {     // big arrays, pseudomedian of 9
+        int s = n/8;
+        pl = med3(pl, pl+s, pl+2*s, a);
+        pm = med3(pm-s, pm, pm+s, a);
+        pn = med3(pn-2*s, pn-s, pn, a);
+      }
+      pm = med3(pl, pm, pn, a); // mid-size, med of 3
+    }
+
+    int pa, pb, pc, pd, pv;
+    short r;
+
+    pv = start; swap(pv, pm, a);
+    pa = pb = start;
+    pc = pd = start + n-1;
+    
+    for (;;) {
+      while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) {
+        if (r == 0) { swap(pa, pb, a); pa++; }
+        pb++;
+      }
+      while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) {
+        if (r == 0) { swap(pc, pd, a); pd--; }
+        pc--;
+      }
+      if (pb > pc) break;
+      swap(pb, pc, a);
+      pb++;
+      pc--;
+    }
+    int pn = start + n;
+    int s;
+    s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
+    s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
+    if ((s = pb-pa) > 1) qsort(a, start, s);
+    if ((s = pd-pc) > 1) qsort(a, pn-s, s);
+  }
+
+  private static void vecswap(int i, int j, int n, byte[] a) {
+    for (; n > 0; i++, j++, n--)
+      swap(i, j, a);
+  }
+
+  /**
+   * Sort a char array into ascending order. The sort algorithm is an optimised
+   * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
+   * "Engineering a Sort Function", Software-Practice and Experience, Vol.
+   * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
+   * performance on many arrays that would take quadratic time with a standard
+   * quicksort.
+   *
+   * @param a the array to sort
+   */
+  public static void sort(char[] a) {
+    qsort(a, 0, a.length);
+  }
+
+  private static int cmp(char i, char j) {
+    return i-j;
+  }
+
+  private static int med3(int a, int b, int c, char[] d) {
+    return cmp(d[a], d[b]) < 0 ? 
+      (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
+    : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
+  }
+  
+  private static void swap(int i, int j, char[] a) {
+    char c = a[i];
+    a[i] = a[j];
+    a[j] = c;
+  }
+
+  private static void qsort(char[] a, int start, int n) {
+    // use an insertion sort on small arrays
+    if (n < 7) {
+      for (int i = start + 1; i < start + n; i++)
+        for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--)
+          swap(j, j-1, a);
+      return;
+    }
+
+    int pm = n/2;       // small arrays, middle element
+    if (n > 7) {
+      int pl = start;
+      int pn = start + n-1;
+
+      if (n > 40) {     // big arrays, pseudomedian of 9
+        int s = n/8;
+        pl = med3(pl, pl+s, pl+2*s, a);
+        pm = med3(pm-s, pm, pm+s, a);
+        pn = med3(pn-2*s, pn-s, pn, a);
+      }
+      pm = med3(pl, pm, pn, a); // mid-size, med of 3
+    }
+
+    int pa, pb, pc, pd, pv;
+    int r;
+
+    pv = start; swap(pv, pm, a);
+    pa = pb = start;
+    pc = pd = start + n-1;
+    
+    for (;;) {
+      while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) {
+        if (r == 0) { swap(pa, pb, a); pa++; }
+        pb++;
+      }
+      while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) {
+        if (r == 0) { swap(pc, pd, a); pd--; }
+        pc--;
+      }
+      if (pb > pc) break;
+      swap(pb, pc, a);
+      pb++;
+      pc--;
+    }
+    int pn = start + n;
+    int s;
+    s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
+    s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
+    if ((s = pb-pa) > 1) qsort(a, start, s);
+    if ((s = pd-pc) > 1) qsort(a, pn-s, s);
+  }
+
+  private static void vecswap(int i, int j, int n, char[] a) {
+    for (; n > 0; i++, j++, n--)
+      swap(i, j, a);
+  }
+
+  /**
+   * Sort a double array into ascending order. The sort algorithm is an
+   * optimised quicksort, as described in Jon L. Bentley and M. Douglas
+   * McIlroy's "Engineering a Sort Function", Software-Practice and Experience,
+   * Vol. 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
+   * performance on many arrays that would take quadratic time with a standard
+   * quicksort. Note that this implementation, like Sun's, has undefined
+   * behaviour if the array contains any NaN values.
+   *
+   * @param a the array to sort
+   */
+  public static void sort(double[] a) {
+    qsort(a, 0, a.length);
+  }
+
+  private static double cmp(double i, double j) {
+    return i-j;
+  }
+
+  private static int med3(int a, int b, int c, double[] d) {
+    return cmp(d[a], d[b]) < 0 ? 
+      (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
+    : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
+  }
+  
+  private static void swap(int i, int j, double[] a) {
+    double c = a[i];
+    a[i] = a[j];
+    a[j] = c;
+  }
+
+  private static void qsort(double[] a, int start, int n) {
+    // use an insertion sort on small arrays
+    if (n < 7) {
+      for (int i = start + 1; i < start + n; i++)
+        for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--)
+          swap(j, j-1, a);
+      return;
+    }
+
+    int pm = n/2;       // small arrays, middle element
+    if (n > 7) {
+      int pl = start;
+      int pn = start + n-1;
+
+      if (n > 40) {     // big arrays, pseudomedian of 9
+        int s = n/8;
+        pl = med3(pl, pl+s, pl+2*s, a);
+        pm = med3(pm-s, pm, pm+s, a);
+        pn = med3(pn-2*s, pn-s, pn, a);
+      }
+      pm = med3(pl, pm, pn, a); // mid-size, med of 3
+    }
+
+    int pa, pb, pc, pd, pv;
+    double r;
+
+    pv = start; swap(pv, pm, a);
+    pa = pb = start;
+    pc = pd = start + n-1;
+    
+    for (;;) {
+      while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) {
+        if (r == 0) { swap(pa, pb, a); pa++; }
+        pb++;
+      }
+      while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) {
+        if (r == 0) { swap(pc, pd, a); pd--; }
+        pc--;
+      }
+      if (pb > pc) break;
+      swap(pb, pc, a);
+      pb++;
+      pc--;
+    }
+    int pn = start + n;
+    int s;
+    s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
+    s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
+    if ((s = pb-pa) > 1) qsort(a, start, s);
+    if ((s = pd-pc) > 1) qsort(a, pn-s, s);
+  }
+
+  private static void vecswap(int i, int j, int n, double[] a) {
+    for (; n > 0; i++, j++, n--)
+      swap(i, j, a);
+  }
+
+  /**
+   * Sort a float array into ascending order. The sort algorithm is an
+   * optimised quicksort, as described in Jon L. Bentley and M. Douglas
+   * McIlroy's "Engineering a Sort Function", Software-Practice and Experience,
+   * Vol. 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
+   * performance on many arrays that would take quadratic time with a standard
+   * quicksort. Note that this implementation, like Sun's, has undefined
+   * behaviour if the array contains any NaN values.
+   *
+   * @param a the array to sort
+   */
+  public static void sort(float[] a) {
+    qsort(a, 0, a.length);
+  }
+
+  private static float cmp(float i, float j) {
+    return i-j;
+  }
+
+  private static int med3(int a, int b, int c, float[] d) {
+    return cmp(d[a], d[b]) < 0 ? 
+      (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
+    : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
+  }
+
+  private static void swap(int i, int j, float[] a) {
+    float c = a[i];
+    a[i] = a[j];
+    a[j] = c;
+  }
+
+  private static void qsort(float[] a, int start, int n) {
+    // use an insertion sort on small arrays
+    if (n < 7) {
+      for (int i = start + 1; i < start + n; i++)
+        for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--)
+          swap(j, j-1, a);
+      return;
+    }
+
+    int pm = n/2;       // small arrays, middle element
+    if (n > 7) {
+      int pl = start;
+      int pn = start + n-1;
+
+      if (n > 40) {     // big arrays, pseudomedian of 9
+        int s = n/8;
+        pl = med3(pl, pl+s, pl+2*s, a);
+        pm = med3(pm-s, pm, pm+s, a);
+        pn = med3(pn-2*s, pn-s, pn, a);
+      }
+      pm = med3(pl, pm, pn, a); // mid-size, med of 3
+    }
+
+    int pa, pb, pc, pd, pv;
+    float r;
+
+    pv = start; swap(pv, pm, a);
+    pa = pb = start;
+    pc = pd = start + n-1;
+    
+    for (;;) {
+      while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) {
+        if (r == 0) { swap(pa, pb, a); pa++; }
+        pb++;
+      }
+      while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) {
+        if (r == 0) { swap(pc, pd, a); pd--; }
+        pc--;
+      }
+      if (pb > pc) break;
+      swap(pb, pc, a);
+      pb++;
+      pc--;
+    }
+    int pn = start + n;
+    int s;
+    s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
+    s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
+    if ((s = pb-pa) > 1) qsort(a, start, s);
+    if ((s = pd-pc) > 1) qsort(a, pn-s, s);
+  }
+
+  private static void vecswap(int i, int j, int n, float[] a) {
+    for (; n > 0; i++, j++, n--)
+      swap(i, j, a);
+  }
+
+  /**
+   * Sort an int array into ascending order. The sort algorithm is an optimised
+   * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
+   * "Engineering a Sort Function", Software-Practice and Experience, Vol.
+   * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
+   * performance on many arrays that would take quadratic time with a standard
+   * quicksort.
+   *
+   * @param a the array to sort
+   */
+  public static void sort(int[] a) {
+    qsort(a, 0, a.length);
+  }
+
+  private static long cmp(int i, int j) {
+    return (long)i-(long)j;
+  }
+
+  private static int med3(int a, int b, int c, int[] d) {
+    return cmp(d[a], d[b]) < 0 ? 
+      (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
+    : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
+  }
+  
+  private static void swap(int i, int j, int[] a) {
+    int c = a[i];
+    a[i] = a[j];
+    a[j] = c;
+  }
+
+  private static void qsort(int[] a, int start, int n) {
+    // use an insertion sort on small arrays
+    if (n < 7) {
+      for (int i = start + 1; i < start + n; i++)
+        for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--)
+          swap(j, j-1, a);
+      return;
+    }
+
+    int pm = n/2;       // small arrays, middle element
+    if (n > 7) {
+      int pl = start;
+      int pn = start + n-1;
+
+      if (n > 40) {     // big arrays, pseudomedian of 9
+        int s = n/8;
+        pl = med3(pl, pl+s, pl+2*s, a);
+        pm = med3(pm-s, pm, pm+s, a);
+        pn = med3(pn-2*s, pn-s, pn, a);
+      }
+      pm = med3(pl, pm, pn, a); // mid-size, med of 3
+    }
+
+    int pa, pb, pc, pd, pv;
+    long r;
+
+    pv = start; swap(pv, pm, a);
+    pa = pb = start;
+    pc = pd = start + n-1;
+    
+    for (;;) {
+      while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) {
+        if (r == 0) { swap(pa, pb, a); pa++; }
+        pb++;
+      }
+      while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) {
+        if (r == 0) { swap(pc, pd, a); pd--; }
+        pc--;
+      }
+      if (pb > pc) break;
+      swap(pb, pc, a);
+      pb++;
+      pc--;
+    }
+    int pn = start + n;
+    int s;
+    s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
+    s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
+    if ((s = pb-pa) > 1) qsort(a, start, s);
+    if ((s = pd-pc) > 1) qsort(a, pn-s, s);
+  }
+
+  private static void vecswap(int i, int j, int n, int[] a) {
+    for (; n > 0; i++, j++, n--)
+      swap(i, j, a);
+  }
+
+  /**
+   * Sort a long array into ascending order. The sort algorithm is an optimised
+   * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's
+   * "Engineering a Sort Function", Software-Practice and Experience, Vol.
+   * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
+   * performance on many arrays that would take quadratic time with a standard
+   * quicksort.
+   *
+   * @param a the array to sort
+   */
+  public static void sort(long[] a) {
+    qsort(a, 0, a.length);
+  }
+
+  // The "cmp" method has been removed from here and replaced with direct
+  // compares in situ, to avoid problems with overflow if the difference
+  // between two numbers is bigger than a long will hold.
+  // One particular change as a result is the use of r1 and r2 in qsort
+
+  private static int med3(int a, int b, int c, long[] d) {
+    return d[a] < d[b] ? 
+      (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
+    : (d[b] > d[c] ? b : d[a] > d[c] ? c : a);
+  }
+  
+  private static void swap(int i, int j, long[] a) {
+    long c = a[i];
+    a[i] = a[j];
+    a[j] = c;
+  }
+
+  private static void qsort(long[] a, int start, int n) {
+    // use an insertion sort on small arrays
+    if (n < 7) {
+      for (int i = start + 1; i < start + n; i++)
+        for (int j = i; j > 0 && a[j-1] > a[j]; j--)
+          swap(j, j-1, a);
+      return;
+    }
+
+    int pm = n/2;       // small arrays, middle element
+    if (n > 7) {
+      int pl = start;
+      int pn = start + n-1;
+
+      if (n > 40) {     // big arrays, pseudomedian of 9
+        int s = n/8;
+        pl = med3(pl, pl+s, pl+2*s, a);
+        pm = med3(pm-s, pm, pm+s, a);
+        pn = med3(pn-2*s, pn-s, pn, a);
+      }
+      pm = med3(pl, pm, pn, a); // mid-size, med of 3
+    }
+
+    int pa, pb, pc, pd, pv;
+    long r1, r2;
+
+    pv = start; swap(pv, pm, a);
+    pa = pb = start;
+    pc = pd = start + n-1;
+    
+    for (;;) {
+      while (pb <= pc && (r1 = a[pb]) <= (r2 = a[pv])) {
+        if (r1 == r2) { swap(pa, pb, a); pa++; }
+        pb++;
+      }
+      while (pc >= pb && (r1 = a[pc]) >= (r2 = a[pv])) {
+        if (r1 == r2) { swap(pc, pd, a); pd--; }
+        pc--;
+      }
+      if (pb > pc) break;
+      swap(pb, pc, a);
+      pb++;
+      pc--;
+    }
+    int pn = start + n;
+    int s;
+    s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
+    s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
+    if ((s = pb-pa) > 1) qsort(a, start, s);
+    if ((s = pd-pc) > 1) qsort(a, pn-s, s);
+  }
+
+  private static void vecswap(int i, int j, int n, long[] a) {
+    for (; n > 0; i++, j++, n--)
+      swap(i, j, a);
+  }
+
+  /**
+   * Sort a short array into ascending order. The sort algorithm is an
+   * optimised quicksort, as described in Jon L. Bentley and M. Douglas
+   * McIlroy's "Engineering a Sort Function", Software-Practice and Experience,
+   * Vol. 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n)
+   * performance on many arrays that would take quadratic time with a standard
+   * quicksort.
+   *
+   * @param a the array to sort
+   */
+  public static void sort(short[] a) {
+    qsort(a, 0, a.length);
+  }
+
+  private static int cmp(short i, short j) {
+    return i-j;
+  }
+
+  private static int med3(int a, int b, int c, short[] d) {
+    return cmp(d[a], d[b]) < 0 ? 
+      (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
+    : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
+  }
+  
+  private static void swap(int i, int j, short[] a) {
+    short c = a[i];
+    a[i] = a[j];
+    a[j] = c;
+  }
+
+  private static void qsort(short[] a, int start, int n) {
+    // use an insertion sort on small arrays
+    if (n < 7) {
+      for (int i = start + 1; i < start + n; i++)
+        for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--)
+          swap(j, j-1, a);
+      return;
+    }
+
+    int pm = n/2;       // small arrays, middle element
+    if (n > 7) {
+      int pl = start;
+      int pn = start + n-1;
+
+      if (n > 40) {     // big arrays, pseudomedian of 9
+        int s = n/8;
+        pl = med3(pl, pl+s, pl+2*s, a);
+        pm = med3(pm-s, pm, pm+s, a);
+        pn = med3(pn-2*s, pn-s, pn, a);
+      }
+      pm = med3(pl, pm, pn, a); // mid-size, med of 3
+    }
+
+    int pa, pb, pc, pd, pv;
+    int r;
+
+    pv = start; swap(pv, pm, a);
+    pa = pb = start;
+    pc = pd = start + n-1;
+    
+    for (;;) {
+      while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) {
+        if (r == 0) { swap(pa, pb, a); pa++; }
+        pb++;
+      }
+      while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) {
+        if (r == 0) { swap(pc, pd, a); pd--; }
+        pc--;
+      }
+      if (pb > pc) break;
+      swap(pb, pc, a);
+      pb++;
+      pc--;
+    }
+    int pn = start + n;
+    int s;
+    s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a);
+    s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a);
+    if ((s = pb-pa) > 1) qsort(a, start, s);
+    if ((s = pd-pc) > 1) qsort(a, pn-s, s);
+  }
+
+  private static void vecswap(int i, int j, int n, short[] a) {
+    for (; n > 0; i++, j++, n--)
+      swap(i, j, a);
+  }
+
+  /**
+   * The bulk of the work for the object sort routines.  In general,
+   * the code attempts to be simple rather than fast, the idea being
+   * that a good optimising JIT will be able to optimise it better
+   * than I can, and if I try it will make it more confusing for the
+   * JIT.  
+   */
+  private static void mergeSort(Object[] a, int from, int to, Comparator c)
+  {
+    // First presort the array in chunks of length 6 with insertion sort. 
+    // mergesort would give too much overhead for this length.
+    for (int chunk = from; chunk < to; chunk += 6)
+      {
+	int end = Math.min(chunk+6, to);
+	for (int i = chunk + 1; i < end; i++)
+	  {
+	    if (c.compare(a[i-1], a[i]) > 0)
+	      {
+		// not already sorted
+		int j=i;
+		Object elem = a[j];
+		do 
+		  {
+		    a[j] = a[j-1];
+		    j--;
+		  } 
+		while (j>chunk && c.compare(a[j-1], elem) > 0);
+		a[j] = elem;
+	      }
+	  }
+      }
+    
+    int len = to - from;
+    // If length is smaller or equal 6 we are done.
+    if (len <= 6)
+      return;
+
+    Object[] src = a;
+    Object[] dest = new Object[len];
+    Object[] t = null; // t is used for swapping src and dest
+
+    // The difference of the fromIndex of the src and dest array.
+    int srcDestDiff = -from;
+
+    // The merges are done in this loop
+    for (int size = 6; size < len; size <<= 1) 
+      {
+	for (int start = from; start < to; start += size << 1)
+	  {
+	    // mid ist the start of the second sublist;
+	    // end the start of the next sublist (or end of array).
+	    int mid = start + size;
+	    int end = Math.min(to, mid + size);
+	    
+	    // The second list is empty or the elements are already in
+	    // order - no need to merge
+	    if (mid >= end || c.compare(src[mid - 1], src[mid]) <= 0) {
+	      System.arraycopy(src, start, 
+			       dest, start + srcDestDiff, end - start);
+	      
+	      // The two halves just need swapping - no need to merge
+	    } else if (c.compare(src[start], src[end - 1]) > 0) {
+	      System.arraycopy(src, start, 
+			       dest, end - size + srcDestDiff, size);
+	      System.arraycopy(src, mid, 
+			       dest, start + srcDestDiff, end - mid);
+	      
+	    } else {
+	      // Declare a lot of variables to save repeating
+	      // calculations.  Hopefully a decent JIT will put these
+	      // in registers and make this fast
+	      int p1 = start;
+	      int p2 = mid;
+	      int i = start + srcDestDiff;
+	      
+	      // The main merge loop; terminates as soon as either
+	      // half is ended
+	      while (p1 < mid && p2 < end)
+		{
+		  dest[i++] = 
+		    src[c.compare(src[p1], src[p2]) <= 0 ? p1++ : p2++];
+		}
+	      
+	      // Finish up by copying the remainder of whichever half
+	      // wasn't finished.
+	      if (p1 < mid)
+		System.arraycopy(src, p1, dest, i, mid - p1);
+	      else
+		System.arraycopy(src, p2, dest, i, end - p2);
+	    } 
+	  }
+	// swap src and dest ready for the next merge
+	t = src; src = dest; dest = t; 
+	from += srcDestDiff;
+	to   += srcDestDiff;
+	srcDestDiff = -srcDestDiff;
+      }
+
+    // make sure the result ends up back in the right place.  Note
+    // that src and dest may have been swapped above, so src 
+    // contains the sorted array.
+    if (src != a)
+      {
+	// Note that from == 0.
+	System.arraycopy(src, 0, a, srcDestDiff, to);
+      }
+  }
+
+  /**
+   * Sort an array of Objects according to their natural ordering. The sort is
+   * guaranteed to be stable, that is, equal elements will not be reordered.
+   * The sort algorithm is a mergesort with the merge omitted if the last
+   * element of one half comes before the first element of the other half. This
+   * algorithm gives guaranteed O(nlog(n)) time, at the expense of making a
+   * copy of the array.
+   *
+   * @param a the array to be sorted
+   * @exception ClassCastException if any two elements are not mutually
+   *   comparable
+   * @exception NullPointerException if an element is null (since
+   *   null.compareTo cannot work)
+   */
+  public static void sort(Object[] a) {
+    mergeSort(a, 0, a.length, defaultComparator);
+  }
+
+  /**
+   * Sort an array of Objects according to a Comparator. The sort is
+   * guaranteed to be stable, that is, equal elements will not be reordered.
+   * The sort algorithm is a mergesort with the merge omitted if the last
+   * element of one half comes before the first element of the other half. This
+   * algorithm gives guaranteed O(nlog(n)) time, at the expense of making a
+   * copy of the array.
+   *
+   * @param a the array to be sorted
+   * @param c a Comparator to use in sorting the array
+   * @exception ClassCastException if any two elements are not mutually
+   *   comparable by the Comparator provided
+   */
+  public static void sort(Object[] a, Comparator c) {
+    mergeSort(a, 0, a.length, c);
+  }
+
+  /**
+   * Sort an array of Objects according to their natural ordering. The sort is
+   * guaranteed to be stable, that is, equal elements will not be reordered.
+   * The sort algorithm is a mergesort with the merge omitted if the last
+   * element of one half comes before the first element of the other half. This
+   * algorithm gives guaranteed O(nlog(n)) time, at the expense of making a
+   * copy of the array.
+   *
+   * @param a the array to be sorted
+   * @param fromIndex the index of the first element to be sorted.
+   * @param toIndex the index of the last element to be sorted plus one.
+   * @exception ClassCastException if any two elements are not mutually
+   *   comparable by the Comparator provided
+   * @exception ArrayIndexOutOfBoundsException, if fromIndex and toIndex
+   *   are not in range.
+   * @exception IllegalArgumentException if fromIndex > toIndex
+   */
+  public static void sort(Object[] a, int fromIndex, 
+			  int toIndex) {
+    if (fromIndex > toIndex)
+      throw new IllegalArgumentException("fromIndex "+fromIndex
+					 +" > toIndex "+toIndex);
+    mergeSort(a, fromIndex, toIndex, defaultComparator);
+  }
+
+  /**
+   * Sort an array of Objects according to a Comparator. The sort is
+   * guaranteed to be stable, that is, equal elements will not be reordered.
+   * The sort algorithm is a mergesort with the merge omitted if the last
+   * element of one half comes before the first element of the other half. This
+   * algorithm gives guaranteed O(nlog(n)) time, at the expense of making a
+   * copy of the array.
+   *
+   * @param a the array to be sorted
+   * @param fromIndex the index of the first element to be sorted.
+   * @param toIndex the index of the last element to be sorted plus one.
+   * @param c a Comparator to use in sorting the array
+   * @exception ClassCastException if any two elements are not mutually
+   *   comparable by the Comparator provided
+   * @exception ArrayIndexOutOfBoundsException, if fromIndex and toIndex
+   *   are not in range.
+   * @exception IllegalArgumentException if fromIndex > toIndex
+   */
+  public static void sort(Object[] a, int fromIndex, 
+			  int toIndex, Comparator c) {
+    if (fromIndex > toIndex)
+      throw new IllegalArgumentException("fromIndex "+fromIndex
+					 +" > toIndex "+toIndex);
+    mergeSort(a, fromIndex, toIndex, c);
+  }
+
+  /**
+   * Returns a list "view" of the specified array. This method is intended to
+   * make it easy to use the Collections API with existing array-based APIs and
+   * programs.
+   *
+   * @param a the array to return a view of
+   * @returns a fixed-size list, changes to which "write through" to the array
+   */
+  public static List asList(final Object[] a) {
+
+    if (a == null) {
+      throw new NullPointerException();
+    }
+
+    return new ListImpl( a );
+  }
+
+
+  /**
+   * Inner class used by asList(Object[]) to provide a list interface
+   * to an array. The methods are all simple enough to be self documenting.
+   * Note: When Sun fully specify serialized forms, this class will have to
+   * be renamed.
+   */
+  private static class ListImpl extends AbstractList {
+
+    ListImpl(Object[] a) {
+      this.a = a;
+    }
+
+    public Object get(int index) {
+      return a[index];
+    }
+
+    public int size() {
+      return a.length;
+    }
+
+    public Object set(int index, Object element) {
+      Object old = a[index];
+      a[index] = element;
+      return old;
+    }
+
+    private Object[] a;
+  }
+    
+}