diff options
Diffstat (limited to 'libjava/java/util/Arrays.java')
| -rw-r--r-- | libjava/java/util/Arrays.java | 2913 |
1 files changed, 1629 insertions, 1284 deletions
diff --git a/libjava/java/util/Arrays.java b/libjava/java/util/Arrays.java index 87a40e3..d52431b 100644 --- a/libjava/java/util/Arrays.java +++ b/libjava/java/util/Arrays.java @@ -1,5 +1,5 @@ /* Arrays.java -- Utility class with methods to operate on arrays - Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc. + Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -25,16 +25,33 @@ 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; +import java.io.Serializable; +import java.lang.reflect.Array; + /** * 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. + * using arrays with Collection-based APIs. All methods throw a + * {@link NullPointerException} if the parameter array is null. + * <p> + * + * Implementations may use their own algorithms, but must obey the general + * properties; for example, the sort must be stable and n*log(n) complexity. + * Sun's implementation of sort, and therefore ours, is a tuned quicksort, + * adapted from 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 offers n*log(n) performance on many data + * sets that cause other quicksorts to degrade to quadratic performance. + * + * @author Original author unknown + * @author Bryce McKinlay + * @author Eric Blake <ebb9@email.byu.edu> + * @see Comparable + * @see Comparator + * @since 1.2 + * @status updated to 1.4 */ public class Arrays { @@ -45,14 +62,8 @@ public class Arrays { } - private static Comparator defaultComparator = new Comparator() - { - public int compare(Object o1, Object o2) - { - return ((Comparable) o1).compareTo(o2); - } - }; - + +// binarySearch /** * 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 @@ -63,32 +74,26 @@ public class Arrays * * @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. + * @return 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) + 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 - { - // This gets the insertion point right on the last loop - low = ++mid; - } + mid = (low + hi) >> 1; + final byte d = a[mid]; + if (d == key) + return mid; + else if (d > key) + hi = mid - 1; + else + // This gets the insertion point right on the last loop. + low = ++mid; } return -mid - 1; } @@ -103,38 +108,32 @@ public class Arrays * * @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. + * @return 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) + 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 - { - // This gets the insertion point right on the last loop - low = ++mid; - } + mid = (low + hi) >> 1; + final char d = a[mid]; + if (d == key) + return mid; + else if (d > key) + hi = mid - 1; + else + // This gets the insertion point right on the last loop. + low = ++mid; } return -mid - 1; } /** - * Perform a binary search of a double array for a key. The array must be + * 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 @@ -143,38 +142,32 @@ public class Arrays * * @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. + * @return 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) + 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 double d = a[mid]; - if (d == key) - { - return mid; - } - else if (d > key) - { - hi = mid - 1; - } - else - { - // This gets the insertion point right on the last loop - low = ++mid; - } + mid = (low + hi) >> 1; + final short d = a[mid]; + if (d == key) + return mid; + else if (d > key) + hi = mid - 1; + else + // This gets the insertion point right on the last loop. + low = ++mid; } return -mid - 1; } /** - * Perform a binary search of a float array for a key. The array must be + * 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 @@ -183,38 +176,32 @@ public class Arrays * * @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. + * @return 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) + 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 float d = a[mid]; - if (d == key) - { - return mid; - } - else if (d > key) - { - hi = mid - 1; - } - else - { - // This gets the insertion point right on the last loop - low = ++mid; - } + mid = (low + hi) >> 1; + final int d = a[mid]; + if (d == key) + return mid; + else if (d > key) + hi = mid - 1; + else + // This gets the insertion point right on the last loop. + low = ++mid; } return -mid - 1; } /** - * Perform a binary search of an int array for a key. The array must be + * 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 @@ -223,38 +210,32 @@ public class Arrays * * @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. + * @return 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) + 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 int d = a[mid]; - if (d == key) - { - return mid; - } - else if (d > key) - { - hi = mid - 1; - } - else - { - // This gets the insertion point right on the last loop - low = ++mid; - } + mid = (low + hi) >> 1; + final long d = a[mid]; + if (d == key) + return mid; + else if (d > key) + hi = mid - 1; + else + // This gets the insertion point right on the last loop. + low = ++mid; } return -mid - 1; } /** - * Perform a binary search of a long array for a key. The array must be + * 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 @@ -263,38 +244,33 @@ public class Arrays * * @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. + * @return 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) + public static int binarySearch(float[] a, float key) { + // Must use Float.compare to take into account NaN, +-0. 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 - { - // This gets the insertion point right on the last loop - low = ++mid; - } + mid = (low + hi) >> 1; + final int r = Float.compare(a[mid], key); + if (r == 0) + return mid; + else if (r > 0) + hi = mid - 1; + else + // This gets the insertion point right on the last loop + low = ++mid; } return -mid - 1; } /** - * Perform a binary search of a short array for a key. The array must be + * 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 @@ -303,63 +279,27 @@ public class Arrays * * @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 - { - // This gets the insertion point right on the last loop - low = ++mid; - } - } - 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. + * @return 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. */ - private static int objectSearch(Object[]a, Object key, final Comparator c) + public static int binarySearch(double[] a, double key) { + // Must use Double.compare to take into account NaN, +-0. 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 - { - // This gets the insertion point right on the last loop - low = ++mid; - } + mid = (low + hi) >> 1; + final int r = Double.compare(a[mid], key); + if (r == 0) + return mid; + else if (r > 0) + hi = mid - 1; + else + // This gets the insertion point right on the last loop + low = ++mid; } return -mid - 1; } @@ -376,16 +316,16 @@ public class Arrays * * @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 + * @return 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. + * @throws ClassCastException if key could not be compared with one of the + * elements of a + * @throws NullPointerException if a null element in a is compared */ - public static int binarySearch(Object[]a, Object key) + public static int binarySearch(Object[] a, Object key) { - return objectSearch(a, key, defaultComparator); + return binarySearch(a, key, null); } /** @@ -400,343 +340,310 @@ public class Arrays * * @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 + * @param c the comparator by which the array is sorted; or null to + * use the elements' natural order + * @return 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. + * @throws ClassCastException if key could not be compared with one of the + * elements of a + * @throws NullPointerException if a null element is compared with natural + * ordering (only possible when c is null) */ - public static int binarySearch(Object[]a, Object key, Comparator c) + public static int binarySearch(Object[] a, Object key, Comparator c) { - return objectSearch(a, key, c); + int low = 0; + int hi = a.length - 1; + int mid = 0; + while (low <= hi) + { + mid = (low + hi) >> 1; + final int d = Collections.compare(key, a[mid], c); + if (d == 0) + return mid; + else if (d < 0) + hi = mid - 1; + else + // This gets the insertion point right on the last loop + low = ++mid; + } + return -mid - 1; } + +// equals /** - * Compare two byte arrays for equality. + * 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] + * @return 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) + 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; - } - + 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 + // If they're the same length, test each element + if (a1.length == a2.length) + { + int i = a1.length; + while (--i >= 0) + if (a1[i] != a2[i]) + return false; + return true; + } } catch (NullPointerException e) { + // If one is null, we get a harmless NullPointerException } return false; } /** - * Compare two char arrays for equality. + * 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] + * @return 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) + 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; - } - + 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 + // If they're the same length, test each element + if (a1.length == a2.length) + { + int i = a1.length; + while (--i >= 0) + if (a1[i] != a2[i]) + return false; + return true; + } } catch (NullPointerException e) { + // If one is null, we get a harmless NullPointerException } - return false; } /** - * Compare two double arrays for equality. + * 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] + * @return 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) + 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; - } - + 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 + // If they're the same length, test each element + if (a1.length == a2.length) + { + int i = a1.length; + while (--i >= 0) + if (a1[i] != a2[i]) + return false; + return true; + } } catch (NullPointerException e) { + // If one is null, we get a harmless NullPointerException } - return false; } /** - * Compare two float arrays for equality. + * 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] + * @return 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) + 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; - } - + 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 + // If they're the same length, test each element + if (a1.length == a2.length) + { + int i = a1.length; + while (--i >= 0) + if (a1[i] != a2[i]) + return false; + return true; + } } catch (NullPointerException e) { + // If one is null, we get a harmless NullPointerException } - return false; } /** - * Compare two long arrays for equality. + * 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] + * @return 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) + 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; - } - + 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 + // If they're the same length, test each element + if (a1.length == a2.length) + { + int i = a1.length; + while (--i >= 0) + if (a1[i] != a2[i]) + return false; + return true; + } } catch (NullPointerException e) { + // If one is null, we get a harmless NullPointerException } - return false; } /** - * Compare two short arrays for equality. + * 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] + * @return 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) + 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; - } - + 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 + // If they're the same length, test each element + if (a1.length == a2.length) + { + int i = a1.length; + while (--i >= 0) + if (a1[i] != a2[i]) + return false; + return true; + } } catch (NullPointerException e) { + // If one is null, we get a harmless NullPointerException } - return false; } /** - * Compare two boolean arrays for equality. + * 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] + * @return 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) + 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; - } - + return true; + + // Must use Float.compare to take into account NaN, +-0. 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 + // If they're the same length, test each element + if (a1.length == a2.length) + { + int i = a1.length; + while (--i >= 0) + if (Float.compare(a1[i], a2[i]) != 0) + return false; + return true; + } } catch (NullPointerException e) { + // If one is null, we get a harmless NullPointerException } - return false; } /** - * Compare two int arrays for equality. + * 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] + * @return 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) + 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; - } - + return true; + + // Must use Double.compare to take into account NaN, +-0. 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 + // If they're the same length, test each element + if (a1.length == a2.length) + { + int i = a1.length; + while (--i >= 0) + if (Double.compare(a1[i], a2[i]) != 0) + return false; + return true; + } } catch (NullPointerException e) { + // If one is null, we get a harmless NullPointerException } - return false; } @@ -745,54 +652,46 @@ public class Arrays * * @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]). + * @return 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) + 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; - } - + 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 + // If they're the same length, test each element + if (a1.length == a2.length) + { + int i = a1.length; + while (--i >= 0) + if (! AbstractCollection.equals(a1[i], a2[i])) + return false; + return true; + } } catch (NullPointerException e) { + // If one is null, we get a harmless NullPointerException } - return false; } + +// fill /** * 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) + 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); } @@ -803,13 +702,16 @@ public class Arrays * @param fromIndex the index to fill from, inclusive * @param toIndex the index to fill to, exclusive * @param val the value to fill with + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length */ - public static void fill(boolean[]a, int fromIndex, int toIndex, boolean val) + public static void fill(boolean[] a, int fromIndex, int toIndex, boolean val) { + if (fromIndex > toIndex) + throw new IllegalArgumentException(); for (int i = fromIndex; i < toIndex; i++) - { - a[i] = val; - } + a[i] = val; } /** @@ -818,11 +720,8 @@ public class Arrays * @param a the array to fill * @param val the value to fill it with */ - public static void fill(byte[]a, byte val) + 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); } @@ -833,13 +732,16 @@ public class Arrays * @param fromIndex the index to fill from, inclusive * @param toIndex the index to fill to, exclusive * @param val the value to fill with + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length */ - public static void fill(byte[]a, int fromIndex, int toIndex, byte val) + public static void fill(byte[] a, int fromIndex, int toIndex, byte val) { + if (fromIndex > toIndex) + throw new IllegalArgumentException(); for (int i = fromIndex; i < toIndex; i++) - { - a[i] = val; - } + a[i] = val; } /** @@ -848,11 +750,8 @@ public class Arrays * @param a the array to fill * @param val the value to fill it with */ - public static void fill(char[]a, char val) + 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); } @@ -863,163 +762,166 @@ public class Arrays * @param fromIndex the index to fill from, inclusive * @param toIndex the index to fill to, exclusive * @param val the value to fill with + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length */ - public static void fill(char[]a, int fromIndex, int toIndex, char val) + public static void fill(char[] a, int fromIndex, int toIndex, char val) { + if (fromIndex > toIndex) + throw new IllegalArgumentException(); for (int i = fromIndex; i < toIndex; i++) - { - a[i] = val; - } + a[i] = val; } /** - * Fill an array with a double value. + * 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(double[]a, double val) + 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 double value. + * 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 + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length */ - public static void fill(double[]a, int fromIndex, int toIndex, double val) + public static void fill(short[] a, int fromIndex, int toIndex, short val) { + if (fromIndex > toIndex) + throw new IllegalArgumentException(); for (int i = fromIndex; i < toIndex; i++) - { - a[i] = val; - } + a[i] = val; } /** - * Fill an array with a float value. + * 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(float[]a, float val) + 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 a float value. + * 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 + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length */ - public static void fill(float[]a, int fromIndex, int toIndex, float val) + public static void fill(int[] a, int fromIndex, int toIndex, int val) { + if (fromIndex > toIndex) + throw new IllegalArgumentException(); for (int i = fromIndex; i < toIndex; i++) - { - a[i] = val; - } + a[i] = val; } /** - * Fill an array with an int value. + * 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(int[]a, int val) + 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 an int value. + * 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 + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length */ - public static void fill(int[]a, int fromIndex, int toIndex, int val) + public static void fill(long[] a, int fromIndex, int toIndex, long val) { + if (fromIndex > toIndex) + throw new IllegalArgumentException(); for (int i = fromIndex; i < toIndex; i++) - { - a[i] = val; - } + a[i] = val; } /** - * Fill an array with a long value. + * 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(long[]a, long val) + 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 long value. + * 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 + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length */ - public static void fill(long[]a, int fromIndex, int toIndex, long val) + public static void fill(float[] a, int fromIndex, int toIndex, float val) { + if (fromIndex > toIndex) + throw new IllegalArgumentException(); for (int i = fromIndex; i < toIndex; i++) - { - a[i] = val; - } + a[i] = val; } /** - * Fill an array with a short value. + * 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(short[]a, short val) + 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 short value. + * 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 + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length */ - public static void fill(short[]a, int fromIndex, int toIndex, short val) + public static void fill(double[] a, int fromIndex, int toIndex, double val) { + if (fromIndex > toIndex) + throw new IllegalArgumentException(); for (int i = fromIndex; i < toIndex; i++) - { - a[i] = val; - } + a[i] = val; } /** @@ -1027,14 +929,11 @@ public class Arrays * * @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. + * @throws ClassCastException if val is not an instance of the element + * type of a. */ - public static void fill(Object[]a, Object val) + 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); } @@ -1045,926 +944,1191 @@ public class Arrays * @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. + * @throws ClassCastException if val is not an instance of the element + * type of a. + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length */ - public static void fill(Object[]a, int fromIndex, int toIndex, Object val) + public static void fill(Object[] a, int fromIndex, int toIndex, Object val) { + if (fromIndex > toIndex) + throw new IllegalArgumentException(); for (int i = fromIndex; i < toIndex; i++) - { - a[i] = val; - } + a[i] = val; } + +// sort // Thanks to Paul Fisher <rao@gnu.org> for finding this quicksort algorithm - // as specified by Sun and porting it to Java. + // as specified by Sun and porting it to Java. The 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 n*log(n) + // performance on many arrays that would take quadratic time with a standard + // quicksort. /** - * 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. + * Performs a stable sort on the elements, arranging them according to their + * natural order. * - * @param a the array to sort + * @param a the byte array to sort */ - public static void sort(byte[]a) + public static void sort(byte[] a) { qsort(a, 0, a.length); } + /** + * Performs a stable sort on the elements, arranging them according to their + * natural order. + * + * @param a the byte array to sort + * @param fromIndex the first index to sort (inclusive) + * @param toIndex the last index to sort (exclusive) + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length + */ public static void sort(byte[] a, int fromIndex, int toIndex) { - qsort(a, fromIndex, toIndex); + if (fromIndex > toIndex) + throw new IllegalArgumentException(); + qsort(a, fromIndex, toIndex - fromIndex); } - private static int med3(int a, int b, int c, byte[]d) + /** + * Finds the index of the median of three array elements. + * + * @param a the first index + * @param b the second index + * @param c the third index + * @param d the array + * @return the index (a, b, or c) which has the middle value of the three + */ + private static int med3(int a, int b, int c, byte[] 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); + 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, byte[]a) + /** + * Swaps the elements at two locations of an array + * + * @param i the first index + * @param j the second index + * @param a the array + */ + 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 && 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; - int r; - - pv = start; - swap(pv, pm, a); - pa = pb = start; - pc = pd = start + n - 1; - - for (;;) - { - while (pb <= pc && (r = a[pb] - a[pv]) <= 0) - { - if (r == 0) - { - swap(pa, pb, a); - pa++; - } - pb++; - } - while (pc >= pb && (r = 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) + /** + * Swaps two ranges of an array. + * + * @param i the first range start + * @param j the second range start + * @param n the element count + * @param a the array + */ + private static void vecswap(int i, int j, int n, byte[] a) { - for (; n > 0; i++, j++, n--) + 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. + * Performs a recursive modified quicksort. * * @param a the array to sort + * @param from the start index (inclusive) + * @param count the number of elements to sort + */ + private static void qsort(byte[] array, int from, int count) + { + // Use an insertion sort on small arrays. + if (count <= 7) + { + for (int i = from + 1; i < from + count; i++) + for (int j = i; j > 0 && array[j - 1] > array[j]; j--) + swap(j, j - 1, array); + return; + } + + // Determine a good median element. + int mid = count / 2; + int lo = from; + int hi = from + count - 1; + + if (count > 40) + { // big arrays, pseudomedian of 9 + int s = count / 8; + lo = med3(lo, lo + s, lo + s + s, array); + mid = med3(mid - s, mid, mid + s, array); + hi = med3(hi - s - s, hi - s, hi, array); + } + mid = med3(lo, mid, hi, array); + + int a, b, c, d; + int comp; + + // Pull the median element out of the fray, and use it as a pivot. + swap(from, mid, array); + a = b = from + 1; + c = d = hi; + + // Repeatedly move b and c to each other, swapping elements so + // that all elements before index b are less than the pivot, and all + // elements after index c are greater than the pivot. a and b track + // the elements equal to the pivot. + while (true) + { + while (b <= c && (comp = array[b] - array[from]) <= 0) + { + if (comp == 0) + { + swap(a, b, array); + a++; + } + b++; + } + while (c >= b && (comp = array[c] - array[from]) >= 0) + { + if (comp == 0) + { + swap(c, d, array); + d--; + } + c--; + } + if (b > c) + break; + swap(b, c, array); + b++; + c--; + } + + // Swap pivot(s) back in place, the recurse on left and right sections. + int span; + span = Math.min(a - from, b - a); + vecswap(from, b - span, span, array); + + span = Math.min(d - c, hi - d - 1); + vecswap(b, hi - span + 1, span, array); + + span = b - a; + if (span > 1) + qsort(array, from, span); + + span = d - c; + if (span > 1) + qsort(array, hi - span + 1, span); + } + + /** + * Performs a stable sort on the elements, arranging them according to their + * natural order. + * + * @param a the char array to sort */ - public static void sort(char[]a) + public static void sort(char[] a) { qsort(a, 0, a.length); } + /** + * Performs a stable sort on the elements, arranging them according to their + * natural order. + * + * @param a the char array to sort + * @param fromIndex the first index to sort (inclusive) + * @param toIndex the last index to sort (exclusive) + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length + */ public static void sort(char[] a, int fromIndex, int toIndex) { - qsort(a, fromIndex, toIndex); + if (fromIndex > toIndex) + throw new IllegalArgumentException(); + qsort(a, fromIndex, toIndex - fromIndex); } - private static int med3(int a, int b, int c, char[]d) + /** + * Finds the index of the median of three array elements. + * + * @param a the first index + * @param b the second index + * @param c the third index + * @param d the array + * @return the index (a, b, or c) which has the middle value of the three + */ + private static int med3(int a, int b, int c, char[] 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); + 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, char[]a) + /** + * Swaps the elements at two locations of an array + * + * @param i the first index + * @param j the second index + * @param a the array + */ + 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 && 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; - int r; - - pv = start; - swap(pv, pm, a); - pa = pb = start; - pc = pd = start + n - 1; - - for (;;) - { - while (pb <= pc && (r = a[pb] - a[pv]) <= 0) - { - if (r == 0) - { - swap(pa, pb, a); - pa++; - } - pb++; - } - while (pc >= pb && (r = 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) + /** + * Swaps two ranges of an array. + * + * @param i the first range start + * @param j the second range start + * @param n the element count + * @param a the array + */ + private static void vecswap(int i, int j, int n, char[] a) { - for (; n > 0; i++, j++, n--) + 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. + * Performs a recursive modified quicksort. * * @param a the array to sort + * @param from the start index (inclusive) + * @param count the number of elements to sort + */ + private static void qsort(char[] array, int from, int count) + { + // Use an insertion sort on small arrays. + if (count <= 7) + { + for (int i = from + 1; i < from + count; i++) + for (int j = i; j > 0 && array[j - 1] > array[j]; j--) + swap(j, j - 1, array); + return; + } + + // Determine a good median element. + int mid = count / 2; + int lo = from; + int hi = from + count - 1; + + if (count > 40) + { // big arrays, pseudomedian of 9 + int s = count / 8; + lo = med3(lo, lo + s, lo + s + s, array); + mid = med3(mid - s, mid, mid + s, array); + hi = med3(hi - s - s, hi - s, hi, array); + } + mid = med3(lo, mid, hi, array); + + int a, b, c, d; + int comp; + + // Pull the median element out of the fray, and use it as a pivot. + swap(from, mid, array); + a = b = from + 1; + c = d = hi; + + // Repeatedly move b and c to each other, swapping elements so + // that all elements before index b are less than the pivot, and all + // elements after index c are greater than the pivot. a and b track + // the elements equal to the pivot. + while (true) + { + while (b <= c && (comp = array[b] - array[from]) <= 0) + { + if (comp == 0) + { + swap(a, b, array); + a++; + } + b++; + } + while (c >= b && (comp = array[c] - array[from]) >= 0) + { + if (comp == 0) + { + swap(c, d, array); + d--; + } + c--; + } + if (b > c) + break; + swap(b, c, array); + b++; + c--; + } + + // Swap pivot(s) back in place, the recurse on left and right sections. + int span; + span = Math.min(a - from, b - a); + vecswap(from, b - span, span, array); + + span = Math.min(d - c, hi - d - 1); + vecswap(b, hi - span + 1, span, array); + + span = b - a; + if (span > 1) + qsort(array, from, span); + + span = d - c; + if (span > 1) + qsort(array, hi - span + 1, span); + } + + /** + * Performs a stable sort on the elements, arranging them according to their + * natural order. + * + * @param a the short array to sort */ - public static void sort(double[]a) + public static void sort(short[] a) { qsort(a, 0, a.length); } - public static void sort(double[] a, int fromIndex, int toIndex) + /** + * Performs a stable sort on the elements, arranging them according to their + * natural order. + * + * @param a the short array to sort + * @param fromIndex the first index to sort (inclusive) + * @param toIndex the last index to sort (exclusive) + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length + */ + public static void sort(short[] a, int fromIndex, int toIndex) { - qsort(a, fromIndex, toIndex); + if (fromIndex > toIndex) + throw new IllegalArgumentException(); + qsort(a, fromIndex, toIndex - fromIndex); } - private static int med3(int a, int b, int c, double[]d) + /** + * Finds the index of the median of three array elements. + * + * @param a the first index + * @param b the second index + * @param c the third index + * @param d the array + * @return the index (a, b, or c) which has the middle value of the three + */ + private static int med3(int a, int b, int c, short[] 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); + 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, double[]a) + /** + * Swaps the elements at two locations of an array + * + * @param i the first index + * @param j the second index + * @param a the array + */ + private static void swap(int i, int j, short[] a) { - double c = a[i]; + short 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 && 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; - double r; - - pv = start; - swap(pv, pm, a); - pa = pb = start; - pc = pd = start + n - 1; - - for (;;) - { - while (pb <= pc && (r = a[pb] - a[pv]) <= 0) - { - if (r == 0) - { - swap(pa, pb, a); - pa++; - } - pb++; - } - while (pc >= pb && (r = 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) + /** + * Swaps two ranges of an array. + * + * @param i the first range start + * @param j the second range start + * @param n the element count + * @param a the array + */ + private static void vecswap(int i, int j, int n, short[] a) { - for (; n > 0; i++, j++, n--) + 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. + * Performs a recursive modified quicksort. * * @param a the array to sort + * @param from the start index (inclusive) + * @param count the number of elements to sort */ - public static void sort(float[]a) + private static void qsort(short[] array, int from, int count) + { + // Use an insertion sort on small arrays. + if (count <= 7) + { + for (int i = from + 1; i < from + count; i++) + for (int j = i; j > 0 && array[j - 1] > array[j]; j--) + swap(j, j - 1, array); + return; + } + + // Determine a good median element. + int mid = count / 2; + int lo = from; + int hi = from + count - 1; + + if (count > 40) + { // big arrays, pseudomedian of 9 + int s = count / 8; + lo = med3(lo, lo + s, lo + s + s, array); + mid = med3(mid - s, mid, mid + s, array); + hi = med3(hi - s - s, hi - s, hi, array); + } + mid = med3(lo, mid, hi, array); + + int a, b, c, d; + int comp; + + // Pull the median element out of the fray, and use it as a pivot. + swap(from, mid, array); + a = b = from + 1; + c = d = hi; + + // Repeatedly move b and c to each other, swapping elements so + // that all elements before index b are less than the pivot, and all + // elements after index c are greater than the pivot. a and b track + // the elements equal to the pivot. + while (true) + { + while (b <= c && (comp = array[b] - array[from]) <= 0) + { + if (comp == 0) + { + swap(a, b, array); + a++; + } + b++; + } + while (c >= b && (comp = array[c] - array[from]) >= 0) + { + if (comp == 0) + { + swap(c, d, array); + d--; + } + c--; + } + if (b > c) + break; + swap(b, c, array); + b++; + c--; + } + + // Swap pivot(s) back in place, the recurse on left and right sections. + int span; + span = Math.min(a - from, b - a); + vecswap(from, b - span, span, array); + + span = Math.min(d - c, hi - d - 1); + vecswap(b, hi - span + 1, span, array); + + span = b - a; + if (span > 1) + qsort(array, from, span); + + span = d - c; + if (span > 1) + qsort(array, hi - span + 1, span); + } + + /** + * Performs a stable sort on the elements, arranging them according to their + * natural order. + * + * @param a the int array to sort + */ + public static void sort(int[] a) { qsort(a, 0, a.length); } - public static void sort(float[] a, int fromIndex, int toIndex) + /** + * Performs a stable sort on the elements, arranging them according to their + * natural order. + * + * @param a the int array to sort + * @param fromIndex the first index to sort (inclusive) + * @param toIndex the last index to sort (exclusive) + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length + */ + public static void sort(int[] a, int fromIndex, int toIndex) { - qsort(a, fromIndex, toIndex); + if (fromIndex > toIndex) + throw new IllegalArgumentException(); + qsort(a, fromIndex, toIndex - fromIndex); } - private static int med3(int a, int b, int c, float[]d) + /** + * Finds the index of the median of three array elements. + * + * @param a the first index + * @param b the second index + * @param c the third index + * @param d the array + * @return the index (a, b, or c) which has the middle value of the three + */ + private static int med3(int a, int b, int c, int[] 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); + 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, float[]a) + /** + * Swaps the elements at two locations of an array + * + * @param i the first index + * @param j the second index + * @param a the array + */ + private static void swap(int i, int j, int[] a) { - float c = a[i]; + int c = a[i]; a[i] = a[j]; a[j] = c; } - private static void qsort(float[]a, int start, int n) + /** + * Swaps two ranges of an array. + * + * @param i the first range start + * @param j the second range start + * @param n the element count + * @param a the array + */ + private static void vecswap(int i, int j, int n, int[] a) { - // 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; - float r; - - pv = start; - swap(pv, pm, a); - pa = pb = start; - pc = pd = start + n - 1; - - for (;;) - { - while (pb <= pc && (r = a[pb] - a[pv]) <= 0) - { - if (r == 0) - { - swap(pa, pb, a); - pa++; - } - pb++; - } - while (pc >= pb && (r = 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); + for ( ; n > 0; i++, j++, n--) + swap(i, j, a); } - private static void vecswap(int i, int j, int n, float[]a) + /** + * Compares two integers in natural order, since a - b is inadequate. + * + * @param a the first int + * @param b the second int + * @return < 0, 0, or > 0 accorting to the comparison + */ + private static int compare(int a, int b) { - for (; n > 0; i++, j++, n--) - swap(i, j, a); + return a < b ? -1 : a == b ? 0 : 1; } /** - * 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. + * Performs a recursive modified quicksort. * * @param a the array to sort + * @param from the start index (inclusive) + * @param count the number of elements to sort */ - public static void sort(int[]a) + private static void qsort(int[] array, int from, int count) + { + // Use an insertion sort on small arrays. + if (count <= 7) + { + for (int i = from + 1; i < from + count; i++) + for (int j = i; j > 0 && array[j - 1] > array[j]; j--) + swap(j, j - 1, array); + return; + } + + // Determine a good median element. + int mid = count / 2; + int lo = from; + int hi = from + count - 1; + + if (count > 40) + { // big arrays, pseudomedian of 9 + int s = count / 8; + lo = med3(lo, lo + s, lo + s + s, array); + mid = med3(mid - s, mid, mid + s, array); + hi = med3(hi - s - s, hi - s, hi, array); + } + mid = med3(lo, mid, hi, array); + + int a, b, c, d; + int comp; + + // Pull the median element out of the fray, and use it as a pivot. + swap(from, mid, array); + a = b = from + 1; + c = d = hi; + + // Repeatedly move b and c to each other, swapping elements so + // that all elements before index b are less than the pivot, and all + // elements after index c are greater than the pivot. a and b track + // the elements equal to the pivot. + while (true) + { + while (b <= c && (comp = compare(array[b], array[from])) <= 0) + { + if (comp == 0) + { + swap(a, b, array); + a++; + } + b++; + } + while (c >= b && (comp = compare(array[c], array[from])) >= 0) + { + if (comp == 0) + { + swap(c, d, array); + d--; + } + c--; + } + if (b > c) + break; + swap(b, c, array); + b++; + c--; + } + + // Swap pivot(s) back in place, the recurse on left and right sections. + int span; + span = Math.min(a - from, b - a); + vecswap(from, b - span, span, array); + + span = Math.min(d - c, hi - d - 1); + vecswap(b, hi - span + 1, span, array); + + span = b - a; + if (span > 1) + qsort(array, from, span); + + span = d - c; + if (span > 1) + qsort(array, hi - span + 1, span); + } + + /** + * Performs a stable sort on the elements, arranging them according to their + * natural order. + * + * @param a the long array to sort + */ + public static void sort(long[] a) { qsort(a, 0, a.length); } - public static void sort(int[] a, int fromIndex, int toIndex) + /** + * Performs a stable sort on the elements, arranging them according to their + * natural order. + * + * @param a the long array to sort + * @param fromIndex the first index to sort (inclusive) + * @param toIndex the last index to sort (exclusive) + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length + */ + public static void sort(long[] a, int fromIndex, int toIndex) { - qsort(a, fromIndex, toIndex); + if (fromIndex > toIndex) + throw new IllegalArgumentException(); + qsort(a, fromIndex, toIndex - fromIndex); } - private static int med3(int a, int b, int c, int[]d) + /** + * Finds the index of the median of three array elements. + * + * @param a the first index + * @param b the second index + * @param c the third index + * @param d the array + * @return the index (a, b, or c) which has the middle value of the three + */ + 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); + 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, int[]a) + /** + * Swaps the elements at two locations of an array + * + * @param i the first index + * @param j the second index + * @param a the array + */ + private static void swap(int i, int j, long[] a) { - int c = a[i]; + long c = a[i]; a[i] = a[j]; a[j] = c; } - private static void qsort(int[]a, int start, int n) + /** + * Swaps two ranges of an array. + * + * @param i the first range start + * @param j the second range start + * @param n the element count + * @param a the array + */ + private static void vecswap(int i, int j, int n, long[] a) { - // 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; - int r; - - pv = start; - swap(pv, pm, a); - pa = pb = start; - pc = pd = start + n - 1; - - for (;;) - { - while (pb <= pc && (r = a[pb] - a[pv]) <= 0) - { - if (r == 0) - { - swap(pa, pb, a); - pa++; - } - pb++; - } - while (pc >= pb && (r = 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); + for ( ; n > 0; i++, j++, n--) + swap(i, j, a); } - private static void vecswap(int i, int j, int n, int[]a) + /** + * Compares two longs in natural order, since a - b is inadequate. + * + * @param a the first long + * @param b the second long + * @return < 0, 0, or > 0 accorting to the comparison + */ + private static int compare(long a, long b) { - for (; n > 0; i++, j++, n--) - swap(i, j, a); + return a < b ? -1 : a == b ? 0 : 1; } /** - * 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. + * Performs a recursive modified quicksort. * * @param a the array to sort + * @param from the start index (inclusive) + * @param count the number of elements to sort + */ + private static void qsort(long[] array, int from, int count) + { + // Use an insertion sort on small arrays. + if (count <= 7) + { + for (int i = from + 1; i < from + count; i++) + for (int j = i; j > 0 && array[j - 1] > array[j]; j--) + swap(j, j - 1, array); + return; + } + + // Determine a good median element. + int mid = count / 2; + int lo = from; + int hi = from + count - 1; + + if (count > 40) + { // big arrays, pseudomedian of 9 + int s = count / 8; + lo = med3(lo, lo + s, lo + s + s, array); + mid = med3(mid - s, mid, mid + s, array); + hi = med3(hi - s - s, hi - s, hi, array); + } + mid = med3(lo, mid, hi, array); + + int a, b, c, d; + int comp; + + // Pull the median element out of the fray, and use it as a pivot. + swap(from, mid, array); + a = b = from + 1; + c = d = hi; + + // Repeatedly move b and c to each other, swapping elements so + // that all elements before index b are less than the pivot, and all + // elements after index c are greater than the pivot. a and b track + // the elements equal to the pivot. + while (true) + { + while (b <= c && (comp = compare(array[b], array[from])) <= 0) + { + if (comp == 0) + { + swap(a, b, array); + a++; + } + b++; + } + while (c >= b && (comp = compare(array[c], array[from])) >= 0) + { + if (comp == 0) + { + swap(c, d, array); + d--; + } + c--; + } + if (b > c) + break; + swap(b, c, array); + b++; + c--; + } + + // Swap pivot(s) back in place, the recurse on left and right sections. + int span; + span = Math.min(a - from, b - a); + vecswap(from, b - span, span, array); + + span = Math.min(d - c, hi - d - 1); + vecswap(b, hi - span + 1, span, array); + + span = b - a; + if (span > 1) + qsort(array, from, span); + + span = d - c; + if (span > 1) + qsort(array, hi - span + 1, span); + } + + /** + * Performs a stable sort on the elements, arranging them according to their + * natural order. + * + * @param a the float array to sort */ - public static void sort(long[]a) + public static void sort(float[] a) { qsort(a, 0, a.length); } - public static void sort(long[] a, int fromIndex, int toIndex) + /** + * Performs a stable sort on the elements, arranging them according to their + * natural order. + * + * @param a the float array to sort + * @param fromIndex the first index to sort (inclusive) + * @param toIndex the last index to sort (exclusive) + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length + */ + public static void sort(float[] a, int fromIndex, int toIndex) { - qsort(a, fromIndex, toIndex); + if (fromIndex > toIndex) + throw new IllegalArgumentException(); + qsort(a, fromIndex, toIndex - fromIndex); } - private static int med3(int a, int b, int c, long[]d) + /** + * Finds the index of the median of three array elements. + * + * @param a the first index + * @param b the second index + * @param c the third index + * @param d the array + * @return the index (a, b, or c) which has the middle value of the three + */ + private static int med3(int a, int b, int c, float[] 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); + return (Float.compare(d[a], d[b]) < 0 + ? (Float.compare(d[b], d[c]) < 0 ? b + : Float.compare(d[a], d[c]) < 0 ? c : a) + : (Float.compare(d[b], d[c]) > 0 ? b + : Float.compare(d[a], d[c]) > 0 ? c : a)); } - private static void swap(int i, int j, long[]a) + /** + * Swaps the elements at two locations of an array + * + * @param i the first index + * @param j the second index + * @param a the array + */ + private static void swap(int i, int j, float[] a) { - long c = a[i]; + float 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 r; - - pv = start; - swap(pv, pm, a); - pa = pb = start; - pc = pd = start + n - 1; - - for (;;) - { - while (pb <= pc && (r = a[pb] - a[pv]) <= 0) - { - if (r == 0) - { - swap(pa, pb, a); - pa++; - } - pb++; - } - while (pc >= pb && (r = 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, long[]a) + /** + * Swaps two ranges of an array. + * + * @param i the first range start + * @param j the second range start + * @param n the element count + * @param a the array + */ + private static void vecswap(int i, int j, int n, float[] a) { - for (; n > 0; i++, j++, n--) + 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. + * Performs a recursive modified quicksort. * * @param a the array to sort + * @param from the start index (inclusive) + * @param count the number of elements to sort */ - public static void sort(short[]a) + private static void qsort(float[] array, int from, int count) + { + // Use an insertion sort on small arrays. + if (count <= 7) + { + for (int i = from + 1; i < from + count; i++) + for (int j = i; + j > 0 && Float.compare(array[j - 1], array[j]) > 0; + j--) + { + swap(j, j - 1, array); + } + return; + } + + // Determine a good median element. + int mid = count / 2; + int lo = from; + int hi = from + count - 1; + + if (count > 40) + { // big arrays, pseudomedian of 9 + int s = count / 8; + lo = med3(lo, lo + s, lo + s + s, array); + mid = med3(mid - s, mid, mid + s, array); + hi = med3(hi - s - s, hi - s, hi, array); + } + mid = med3(lo, mid, hi, array); + + int a, b, c, d; + int comp; + + // Pull the median element out of the fray, and use it as a pivot. + swap(from, mid, array); + a = b = from + 1; + c = d = hi; + + // Repeatedly move b and c to each other, swapping elements so + // that all elements before index b are less than the pivot, and all + // elements after index c are greater than the pivot. a and b track + // the elements equal to the pivot. + while (true) + { + while (b <= c && (comp = Float.compare(array[b], array[from])) <= 0) + { + if (comp == 0) + { + swap(a, b, array); + a++; + } + b++; + } + while (c >= b && (comp = Float.compare(array[c], array[from])) >= 0) + { + if (comp == 0) + { + swap(c, d, array); + d--; + } + c--; + } + if (b > c) + break; + swap(b, c, array); + b++; + c--; + } + + // Swap pivot(s) back in place, the recurse on left and right sections. + int span; + span = Math.min(a - from, b - a); + vecswap(from, b - span, span, array); + + span = Math.min(d - c, hi - d - 1); + vecswap(b, hi - span + 1, span, array); + + span = b - a; + if (span > 1) + qsort(array, from, span); + + span = d - c; + if (span > 1) + qsort(array, hi - span + 1, span); + } + + /** + * Performs a stable sort on the elements, arranging them according to their + * natural order. + * + * @param a the double array to sort + */ + public static void sort(double[] a) { qsort(a, 0, a.length); } - public static void sort(short[] a, int fromIndex, int toIndex) + /** + * Performs a stable sort on the elements, arranging them according to their + * natural order. + * + * @param a the double array to sort + * @param fromIndex the first index to sort (inclusive) + * @param toIndex the last index to sort (exclusive) + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 + * || toIndex > a.length + */ + public static void sort(double[] a, int fromIndex, int toIndex) { - qsort(a, fromIndex, toIndex); + if (fromIndex > toIndex) + throw new IllegalArgumentException(); + qsort(a, fromIndex, toIndex - fromIndex); } - private static int med3(int a, int b, int c, short[]d) + /** + * Finds the index of the median of three array elements. + * + * @param a the first index + * @param b the second index + * @param c the third index + * @param d the array + * @return the index (a, b, or c) which has the middle value of the three + */ + private static int med3(int a, int b, int c, double[] 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); + return (Double.compare(d[a], d[b]) < 0 + ? (Double.compare(d[b], d[c]) < 0 ? b + : Double.compare(d[a], d[c]) < 0 ? c : a) + : (Double.compare(d[b], d[c]) > 0 ? b + : Double.compare(d[a], d[c]) > 0 ? c : a)); } - private static void swap(int i, int j, short[]a) + /** + * Swaps the elements at two locations of an array + * + * @param i the first index + * @param j the second index + * @param a the array + */ + private static void swap(int i, int j, double[] a) { - short c = a[i]; + double 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 && 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; - int r; - - pv = start; - swap(pv, pm, a); - pa = pb = start; - pc = pd = start + n - 1; - - for (;;) - { - while (pb <= pc && (r = a[pb] - a[pv]) <= 0) - { - if (r == 0) - { - swap(pa, pb, a); - pa++; - } - pb++; - } - while (pc >= pb && (r = 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) + /** + * Swaps two ranges of an array. + * + * @param i the first range start + * @param j the second range start + * @param n the element count + * @param a the array + */ + private static void vecswap(int i, int j, int n, double[] a) { - for (; n > 0; i++, j++, n--) + 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. + * Performs a recursive modified quicksort. + * + * @param a the array to sort + * @param from the start index (inclusive) + * @param count the number of elements to sort */ - 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); - } + private static void qsort(double[] array, int from, int count) + { + // Use an insertion sort on small arrays. + if (count <= 7) + { + for (int i = from + 1; i < from + count; i++) + for (int j = i; + j > 0 && Double.compare(array[j - 1], array[j]) > 0; + j--) + { + swap(j, j - 1, array); + } + return; + } + + // Determine a good median element. + int mid = count / 2; + int lo = from; + int hi = from + count - 1; + + if (count > 40) + { // big arrays, pseudomedian of 9 + int s = count / 8; + lo = med3(lo, lo + s, lo + s + s, array); + mid = med3(mid - s, mid, mid + s, array); + hi = med3(hi - s - s, hi - s, hi, array); + } + mid = med3(lo, mid, hi, array); + + int a, b, c, d; + int comp; + + // Pull the median element out of the fray, and use it as a pivot. + swap(from, mid, array); + a = b = from + 1; + c = d = hi; + + // Repeatedly move b and c to each other, swapping elements so + // that all elements before index b are less than the pivot, and all + // elements after index c are greater than the pivot. a and b track + // the elements equal to the pivot. + while (true) + { + while (b <= c && (comp = Double.compare(array[b], array[from])) <= 0) + { + if (comp == 0) + { + swap(a, b, array); + a++; + } + b++; + } + while (c >= b && (comp = Double.compare(array[c], array[from])) >= 0) + { + if (comp == 0) + { + swap(c, d, array); + d--; + } + c--; + } + if (b > c) + break; + swap(b, c, array); + b++; + c--; + } + + // Swap pivot(s) back in place, the recurse on left and right sections. + int span; + span = Math.min(a - from, b - a); + vecswap(from, b - span, span, array); + + span = Math.min(d - c, hi - d - 1); + vecswap(b, hi - span + 1, span, array); + + span = b - a; + if (span > 1) + qsort(array, from, span); + + span = d - c; + if (span > 1) + qsort(array, hi - span + 1, span); } /** @@ -1972,18 +2136,19 @@ public class Arrays * 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 + * algorithm gives guaranteed O(n*log(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) + * @throws ClassCastException if any two elements are not mutually + * comparable + * @throws NullPointerException if an element is null (since + * null.compareTo cannot work) + * @see Comparable */ - public static void sort(Object[]a) + public static void sort(Object[] a) { - mergeSort(a, 0, a.length, defaultComparator); + sort(a, 0, a.length, null); } /** @@ -1991,17 +2156,20 @@ public class Arrays * 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 + * algorithm gives guaranteed O(n*log(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 + * @param c a Comparator to use in sorting the array; or null to indicate + * the elements' natural order + * @throws ClassCastException if any two elements are not mutually + * comparable by the Comparator provided + * @throws NullPointerException if a null element is compared with natural + * ordering (only possible when c is null) */ - public static void sort(Object[]a, Comparator c) + public static void sort(Object[] a, Comparator c) { - mergeSort(a, 0, a.length, c); + sort(a, 0, a.length, c); } /** @@ -2009,24 +2177,23 @@ public class Arrays * 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 + * algorithm gives guaranteed O(n*log(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 + * @param fromIndex the index of the first element to be sorted + * @param toIndex the index of the last element to be sorted plus one + * @throws ClassCastException if any two elements are not mutually + * comparable + * @throws NullPointerException if an element is null (since + * null.compareTo cannot work) + * @throws ArrayIndexOutOfBoundsException, if fromIndex and toIndex + * are not in range. + * @throws IllegalArgumentException if fromIndex > toIndex */ - public static void sort(Object[]a, int fromIndex, int 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(a, fromIndex, toIndex, null); } /** @@ -2034,56 +2201,195 @@ public class Arrays * 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 + * algorithm gives guaranteed O(n*log(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 + * @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; or null to indicate + * the elements' natural order + * @throws ClassCastException if any two elements are not mutually + * comparable by the Comparator provided + * @throws ArrayIndexOutOfBoundsException, if fromIndex and toIndex + * are not in range. + * @throws IllegalArgumentException if fromIndex > toIndex + * @throws NullPointerException if a null element is compared with natural + * ordering (only possible when c is null) */ - public static void sort(Object[]a, int fromIndex, int toIndex, Comparator c) + 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); + + " > toIndex " + toIndex); + + // 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. First presort the array in chunks of length 6 with insertion + // sort. A mergesort would give too much overhead for this length. + for (int chunk = fromIndex; chunk < toIndex; chunk += 6) + { + int end = Math.min(chunk + 6, toIndex); + for (int i = chunk + 1; i < end; i++) + { + if (Collections.compare(a[i - 1], a[i], c) > 0) + { + // not already sorted + int j = i; + Object elem = a[j]; + do + { + a[j] = a[j - 1]; + j--; + } + while (j > chunk + && Collections.compare(a[j - 1], elem, c) > 0); + a[j] = elem; + } + } + } + + int len = toIndex - fromIndex; + // 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 = -fromIndex; + + // The merges are done in this loop + for (int size = 6; size < len; size <<= 1) + { + for (int start = fromIndex; start < toIndex; start += size << 1) + { + // mid is 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(toIndex, mid + size); + + // The second list is empty or the elements are already in + // order - no need to merge + if (mid >= end + || Collections.compare(src[mid - 1], src[mid], c) <= 0) + { + System.arraycopy(src, start, + dest, start + srcDestDiff, end - start); + + // The two halves just need swapping - no need to merge + } + else if (Collections.compare(src[start], src[end - 1], c) > 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[(Collections.compare(src[p1], src[p2], c) <= 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; + fromIndex += srcDestDiff; + toIndex += 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 fromIndex == 0. + System.arraycopy(src, 0, a, srcDestDiff, toIndex); + } } /** * 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. + * programs. Changes in the list or the array show up in both places. The + * list does not support element addition or removal, but does permit + * value modification. The returned list implements both Serializable and + * RandomAccess. * * @param a the array to return a view of - * @returns a fixed-size list, changes to which "write through" to the array + * @return a fixed-size list, changes to which "write through" to the array + * @see Serializable + * @see RandomAccess + * @see Arrays.ArrayList */ - public static List asList(final Object[]a) + public static List asList(final Object[] a) { - if (a == null) - { - throw new NullPointerException(); - } - - return new ListImpl(a); + return new Arrays.ArrayList(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. + * Inner class used by {@link #asList(Object[])} to provide a list interface + * to an array. The name, though it clashes with java.util.ArrayList, is + * Sun's choice for Serialization purposes. Element addition and removal + * is prohibited, but values can be modified. + * + * @author Eric Blake <ebb9@email.byu.edu> + * @status updated to 1.4 */ - private static class ListImpl extends AbstractList - { - ListImpl(Object[]a) + private static final class ArrayList extends AbstractList + implements Serializable, RandomAccess + { + // We override the necessary methods, plus others which will be much + // more efficient with direct iteration rather than relying on iterator(). + + /** + * Compatible with JDK 1.4. + */ + private static final long serialVersionUID = -2764017481108945198L; + + /** + * The array we are viewing. + * @serial the array + */ + private final Object[] a; + + /** + * Construct a list view of the array. + * @param a the array to view + * @throws NullPointerException if a is null + */ + ArrayList(Object[] a) { + // We have to explicitly check. + if (a == null) + throw new NullPointerException(); this.a = a; } @@ -2104,6 +2410,45 @@ public class Arrays return old; } - private Object[] a; + public boolean contains(Object o) + { + return lastIndexOf(o) >= 0; + } + + public int indexOf(Object o) + { + int size = a.length; + for (int i = 0; i < size; i++) + if (equals(o, a[i])) + return i; + return -1; + } + + public int lastIndexOf(Object o) + { + int i = a.length; + while (--i >= 0) + if (equals(o, a[i])) + return i; + return -1; + } + + public Object[] toArray() + { + return (Object[]) a.clone(); + } + + public Object[] toArray(Object[] array) + { + int size = a.length; + if (array.length < size) + array = (Object[]) + Array.newInstance(array.getClass().getComponentType(), size); + else if (array.length > size) + array[size] = null; + + System.arraycopy(a, 0, array, 0, size); + return array; + } } } |