diff options
Diffstat (limited to 'libjava/java/util/Arrays.java')
| -rw-r--r-- | libjava/java/util/Arrays.java | 2510 |
1 files changed, 0 insertions, 2510 deletions
diff --git a/libjava/java/util/Arrays.java b/libjava/java/util/Arrays.java deleted file mode 100644 index 15c1a5f..0000000 --- a/libjava/java/util/Arrays.java +++ /dev/null @@ -1,2510 +0,0 @@ -/* Arrays.java -- Utility class with methods to operate on arrays - Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 - Free Software Foundation, Inc. - -This file is part of GNU Classpath. - -GNU Classpath is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) -any later version. - -GNU Classpath is distributed in the hope that it will be useful, but -WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -General Public License for more details. - -You should have received a copy of the GNU General Public License -along with GNU Classpath; see the file COPYING. If not, write to the -Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301 USA. - -Linking this library statically or dynamically with other modules is -making a combined work based on this library. Thus, the terms and -conditions of the GNU General Public License cover the whole -combination. - -As a special exception, the copyright holders of this library give you -permission to link this library with independent modules to produce an -executable, regardless of the license terms of these independent -modules, and to copy and distribute the resulting executable under -terms of your choice, provided that you also meet, for each linked -independent module, the terms and conditions of the license of that -module. An independent module is a module which is not derived from -or based on this library. If you modify this library, you may extend -this exception to your version of the library, but you are not -obligated to do so. If you do not wish to do so, delete this -exception statement from your version. */ - - -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. 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 -{ - /** - * This class is non-instantiable. - */ - private Arrays() - { - } - - -// 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 - * method is undefined, and may be an infinite loop. If the array contains - * the key more than once, any one of them may be found. Note: although the - * specification allows for an infinite loop if the array is unsorted, it - * will not happen in this implementation. - * - * @param a the array to search (must be sorted) - * @param key the value to search for - * @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) - { - 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; - } - return -mid - 1; - } - - /** - * Perform a binary search of a char array for a key. The array must be - * sorted (as by the sort() method) - if it is not, the behaviour of this - * method is undefined, and may be an infinite loop. If the array contains - * the key more than once, any one of them may be found. Note: although the - * specification allows for an infinite loop if the array is unsorted, it - * will not happen in this implementation. - * - * @param a the array to search (must be sorted) - * @param key the value to search for - * @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) - { - 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; - } - return -mid - 1; - } - - /** - * Perform a binary search of a short array for a key. The array must be - * sorted (as by the sort() method) - if it is not, the behaviour of this - * method is undefined, and may be an infinite loop. If the array contains - * the key more than once, any one of them may be found. Note: although the - * specification allows for an infinite loop if the array is unsorted, it - * will not happen in this implementation. - * - * @param a the array to search (must be sorted) - * @param key the value to search for - * @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(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; - } - - /** - * Perform a binary search of an int array for a key. The array must be - * sorted (as by the sort() method) - if it is not, the behaviour of this - * method is undefined, and may be an infinite loop. If the array contains - * the key more than once, any one of them may be found. Note: although the - * specification allows for an infinite loop if the array is unsorted, it - * will not happen in this implementation. - * - * @param a the array to search (must be sorted) - * @param key the value to search for - * @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) - { - 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; - } - return -mid - 1; - } - - /** - * Perform a binary search of a long array for a key. The array must be - * sorted (as by the sort() method) - if it is not, the behaviour of this - * method is undefined, and may be an infinite loop. If the array contains - * the key more than once, any one of them may be found. Note: although the - * specification allows for an infinite loop if the array is unsorted, it - * will not happen in this implementation. - * - * @param a the array to search (must be sorted) - * @param key the value to search for - * @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) - { - 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; - } - return -mid - 1; - } - - /** - * Perform a binary search of a float array for a key. The array must be - * sorted (as by the sort() method) - if it is not, the behaviour of this - * method is undefined, and may be an infinite loop. If the array contains - * the key more than once, any one of them may be found. Note: although the - * specification allows for an infinite loop if the array is unsorted, it - * will not happen in this implementation. - * - * @param a the array to search (must be sorted) - * @param key the value to search for - * @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) - { - // 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 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 double array for a key. The array must be - * sorted (as by the sort() method) - if it is not, the behaviour of this - * method is undefined, and may be an infinite loop. If the array contains - * the key more than once, any one of them may be found. Note: although the - * specification allows for an infinite loop if the array is unsorted, it - * will not happen in this implementation. - * - * @param a the array to search (must be sorted) - * @param key the value to search for - * @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) - { - // 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 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; - } - - /** - * Perform a binary search of an Object array for a key, using the natural - * ordering of the elements. The array must be sorted (as by the sort() - * method) - if it is not, the behaviour of this method is undefined, and may - * be an infinite loop. Further, the key must be comparable with every item - * in the array. If the array contains the key more than once, any one of - * them may be found. Note: although the specification allows for an infinite - * loop if the array is unsorted, it will not happen in this (JCL) - * implementation. - * - * @param a the array to search (must be sorted) - * @param key the value to search for - * @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) - { - return binarySearch(a, key, null); - } - - /** - * Perform a binary search of an Object array for a key, using a supplied - * Comparator. The array must be sorted (as by the sort() method with the - * same Comparator) - if it is not, the behaviour of this method is - * undefined, and may be an infinite loop. Further, the key must be - * comparable with every item in the array. If the array contains the key - * more than once, any one of them may be found. Note: although the - * specification allows for an infinite loop if the array is unsorted, it - * will not happen in this (JCL) implementation. - * - * @param a the array to search (must be sorted) - * @param key the value to search for - * @param c the comparator by which the array is sorted; 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) - { - 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 boolean arrays for equality. - * - * @param a1 the first array to compare - * @param a2 the second array to compare - * @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) - { - // Quick test which saves comparing elements of the same array, and also - // catches the case that both are null. - if (a1 == a2) - return true; - - if (null == a1 || null == a2) - return false; - - // 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; - } - return false; - } - - /** - * Compare two byte arrays for equality. - * - * @param a1 the first array to compare - * @param a2 the second array to compare - * @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) - { - // Quick test which saves comparing elements of the same array, and also - // catches the case that both are null. - if (a1 == a2) - return true; - - if (null == a1 || null == a2) - return false; - - // 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; - } - return false; - } - - /** - * Compare two char arrays for equality. - * - * @param a1 the first array to compare - * @param a2 the second array to compare - * @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) - { - // Quick test which saves comparing elements of the same array, and also - // catches the case that both are null. - if (a1 == a2) - return true; - - if (null == a1 || null == a2) - return false; - - // 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; - } - return false; - } - - /** - * Compare two short arrays for equality. - * - * @param a1 the first array to compare - * @param a2 the second array to compare - * @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) - { - // Quick test which saves comparing elements of the same array, and also - // catches the case that both are null. - if (a1 == a2) - return true; - - if (null == a1 || null == a2) - return false; - - // 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; - } - return false; - } - - /** - * Compare two int arrays for equality. - * - * @param a1 the first array to compare - * @param a2 the second array to compare - * @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) - { - // Quick test which saves comparing elements of the same array, and also - // catches the case that both are null. - if (a1 == a2) - return true; - - if (null == a1 || null == a2) - return false; - - // 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; - } - return false; - } - - /** - * Compare two long arrays for equality. - * - * @param a1 the first array to compare - * @param a2 the second array to compare - * @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) - { - // Quick test which saves comparing elements of the same array, and also - // catches the case that both are null. - if (a1 == a2) - return true; - - if (null == a1 || null == a2) - return false; - - // 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; - } - return false; - } - - /** - * Compare two float arrays for equality. - * - * @param a1 the first array to compare - * @param a2 the second array to compare - * @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) - { - // Quick test which saves comparing elements of the same array, and also - // catches the case that both are null. - if (a1 == a2) - return true; - - if (null == a1 || null == a2) - return false; - - // Must use Float.compare to take into account NaN, +-0. - // 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; - } - return false; - } - - /** - * Compare two double arrays for equality. - * - * @param a1 the first array to compare - * @param a2 the second array to compare - * @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) - { - // Quick test which saves comparing elements of the same array, and also - // catches the case that both are null. - if (a1 == a2) - return true; - - if (null == a1 || null == a2) - return false; - - // Must use Double.compare to take into account NaN, +-0. - // 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; - } - return false; - } - - /** - * Compare two Object arrays for equality. - * - * @param a1 the first array to compare - * @param a2 the second array to compare - * @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) - { - // Quick test which saves comparing elements of the same array, and also - // catches the case that both are null. - if (a1 == a2) - return true; - - if (null == a1 || null == a2) - return false; - - // 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; - } - 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) - { - fill(a, 0, a.length, val); - } - - /** - * Fill a range of an array with a boolean value. - * - * @param a the array to fill - * @param fromIndex the index to fill from, inclusive - * @param toIndex the index to fill to, exclusive - * @param val the value to fill with - * @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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - for (int i = fromIndex; i < toIndex; i++) - a[i] = val; - } - - /** - * Fill an array with a byte value. - * - * @param a the array to fill - * @param val the value to fill it with - */ - public static void fill(byte[] a, byte val) - { - fill(a, 0, a.length, val); - } - - /** - * Fill a range of an array with a byte value. - * - * @param a the array to fill - * @param fromIndex the index to fill from, inclusive - * @param toIndex the index to fill to, exclusive - * @param val the value to fill with - * @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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - for (int i = fromIndex; i < toIndex; i++) - a[i] = val; - } - - /** - * Fill an array with a char value. - * - * @param a the array to fill - * @param val the value to fill it with - */ - public static void fill(char[] a, char val) - { - fill(a, 0, a.length, val); - } - - /** - * Fill a range of an array with a char value. - * - * @param a the array to fill - * @param fromIndex the index to fill from, inclusive - * @param toIndex the index to fill to, exclusive - * @param val the value to fill with - * @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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - for (int i = fromIndex; i < toIndex; i++) - a[i] = val; - } - - /** - * Fill an array with a short value. - * - * @param a the array to fill - * @param val the value to fill it with - */ - public static void fill(short[] a, short val) - { - fill(a, 0, a.length, val); - } - - /** - * Fill a range of an array with a short value. - * - * @param a the array to fill - * @param fromIndex the index to fill from, inclusive - * @param toIndex the index to fill to, exclusive - * @param val the value to fill with - * @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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - for (int i = fromIndex; i < toIndex; i++) - a[i] = val; - } - - /** - * Fill an array with an int value. - * - * @param a the array to fill - * @param val the value to fill it with - */ - public static void fill(int[] a, int val) - { - fill(a, 0, a.length, val); - } - - /** - * Fill a range of an array with an int value. - * - * @param a the array to fill - * @param fromIndex the index to fill from, inclusive - * @param toIndex the index to fill to, exclusive - * @param val the value to fill with - * @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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - for (int i = fromIndex; i < toIndex; i++) - a[i] = val; - } - - /** - * Fill an array with a long value. - * - * @param a the array to fill - * @param val the value to fill it with - */ - public static void fill(long[] a, long val) - { - fill(a, 0, a.length, val); - } - - /** - * Fill a range of an array with a long value. - * - * @param a the array to fill - * @param fromIndex the index to fill from, inclusive - * @param toIndex the index to fill to, exclusive - * @param val the value to fill with - * @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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - for (int i = fromIndex; i < toIndex; i++) - a[i] = val; - } - - /** - * Fill an array with a float value. - * - * @param a the array to fill - * @param val the value to fill it with - */ - public static void fill(float[] a, float val) - { - fill(a, 0, a.length, val); - } - - /** - * Fill a range of an array with a float value. - * - * @param a the array to fill - * @param fromIndex the index to fill from, inclusive - * @param toIndex the index to fill to, exclusive - * @param val the value to fill with - * @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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - for (int i = fromIndex; i < toIndex; i++) - a[i] = val; - } - - /** - * Fill an array with a double value. - * - * @param a the array to fill - * @param val the value to fill it with - */ - public static void fill(double[] a, double val) - { - fill(a, 0, a.length, val); - } - - /** - * Fill a range of an array with a double value. - * - * @param a the array to fill - * @param fromIndex the index to fill from, inclusive - * @param toIndex the index to fill to, exclusive - * @param val the value to fill with - * @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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - for (int i = fromIndex; i < toIndex; i++) - a[i] = val; - } - - /** - * Fill an array with an Object value. - * - * @param a the array to fill - * @param val the value to fill it with - * @throws ClassCastException if val is not an instance of the element - * type of a. - */ - public static void fill(Object[] a, Object val) - { - fill(a, 0, a.length, val); - } - - /** - * Fill a range of an array with an Object value. - * - * @param a the array to fill - * @param fromIndex the index to fill from, inclusive - * @param toIndex the index to fill to, exclusive - * @param val the value to fill with - * @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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - for (int i = fromIndex; i < toIndex; i++) - 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. 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. - - /** - * Performs a stable sort on the elements, arranging them according to their - * natural order. - * - * @param a the byte array to sort - */ - 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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - if (fromIndex < 0) - throw new ArrayIndexOutOfBoundsException(); - qsort(a, fromIndex, toIndex - fromIndex); - } - - /** - * 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)); - } - - /** - * 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; - } - - /** - * 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--) - swap(i, j, a); - } - - /** - * Performs a recursive modified quicksort. - * - * @param array 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 > from && 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 + 2 * s, array); - mid = med3(mid - s, mid, mid + s, array); - hi = med3(hi - 2 * 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; - c = d = from + count - 1; - - // 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. - hi = from + count; - 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, span, array); - - span = b - a; - if (span > 1) - qsort(array, from, span); - - span = d - c; - if (span > 1) - qsort(array, hi - span, 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) - { - 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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - if (fromIndex < 0) - throw new ArrayIndexOutOfBoundsException(); - qsort(a, fromIndex, toIndex - fromIndex); - } - - /** - * 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)); - } - - /** - * 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; - } - - /** - * 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--) - swap(i, j, a); - } - - /** - * Performs a recursive modified quicksort. - * - * @param array 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 > from && 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 + 2 * s, array); - mid = med3(mid - s, mid, mid + s, array); - hi = med3(hi - 2 * 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; - c = d = from + count - 1; - - // 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. - hi = from + count; - 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, span, array); - - span = b - a; - if (span > 1) - qsort(array, from, span); - - span = d - c; - if (span > 1) - qsort(array, hi - span, 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(short[] a) - { - qsort(a, 0, a.length); - } - - /** - * 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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - if (fromIndex < 0) - throw new ArrayIndexOutOfBoundsException(); - qsort(a, fromIndex, toIndex - fromIndex); - } - - /** - * 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)); - } - - /** - * 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) - { - short c = a[i]; - a[i] = a[j]; - a[j] = c; - } - - /** - * 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--) - swap(i, j, a); - } - - /** - * Performs a recursive modified quicksort. - * - * @param array the array to sort - * @param from the start index (inclusive) - * @param count the number of elements to sort - */ - 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 > from && 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 + 2 * s, array); - mid = med3(mid - s, mid, mid + s, array); - hi = med3(hi - 2 * 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; - c = d = from + count - 1; - - // 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. - hi = from + count; - 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, span, array); - - span = b - a; - if (span > 1) - qsort(array, from, span); - - span = d - c; - if (span > 1) - qsort(array, hi - span, 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); - } - - /** - * 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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - if (fromIndex < 0) - throw new ArrayIndexOutOfBoundsException(); - qsort(a, fromIndex, toIndex - fromIndex); - } - - /** - * 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)); - } - - /** - * 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) - { - int c = a[i]; - a[i] = a[j]; - a[j] = c; - } - - /** - * 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) - { - for ( ; n > 0; i++, j++, n--) - swap(i, j, 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) - { - return a < b ? -1 : a == b ? 0 : 1; - } - - /** - * Performs a recursive modified quicksort. - * - * @param array the array to sort - * @param from the start index (inclusive) - * @param count the number of elements to sort - */ - 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 > from && 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 + 2 * s, array); - mid = med3(mid - s, mid, mid + s, array); - hi = med3(hi - 2 * 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; - c = d = from + count - 1; - - // 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. - hi = from + count; - 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, span, array); - - span = b - a; - if (span > 1) - qsort(array, from, span); - - span = d - c; - if (span > 1) - qsort(array, hi - span, 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); - } - - /** - * 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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - if (fromIndex < 0) - throw new ArrayIndexOutOfBoundsException(); - qsort(a, fromIndex, toIndex - fromIndex); - } - - /** - * 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)); - } - - /** - * 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) - { - long c = a[i]; - a[i] = a[j]; - a[j] = c; - } - - /** - * 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) - { - for ( ; n > 0; i++, j++, n--) - swap(i, j, 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) - { - return a < b ? -1 : a == b ? 0 : 1; - } - - /** - * Performs a recursive modified quicksort. - * - * @param array 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 > from && 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 + 2 * s, array); - mid = med3(mid - s, mid, mid + s, array); - hi = med3(hi - 2 * 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; - c = d = from + count - 1; - - // 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. - hi = from + count; - 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, span, array); - - span = b - a; - if (span > 1) - qsort(array, from, span); - - span = d - c; - if (span > 1) - qsort(array, hi - span, 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(float[] a) - { - qsort(a, 0, a.length); - } - - /** - * 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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - if (fromIndex < 0) - throw new ArrayIndexOutOfBoundsException(); - qsort(a, fromIndex, toIndex - fromIndex); - } - - /** - * 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 (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)); - } - - /** - * 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) - { - float c = a[i]; - a[i] = a[j]; - a[j] = c; - } - - /** - * 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--) - swap(i, j, a); - } - - /** - * Performs a recursive modified quicksort. - * - * @param array the array to sort - * @param from the start index (inclusive) - * @param count the number of elements to sort - */ - 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 > from && 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 + 2 * s, array); - mid = med3(mid - s, mid, mid + s, array); - hi = med3(hi - 2 * 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; - c = d = from + count - 1; - - // 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. - hi = from + count; - 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, span, array); - - span = b - a; - if (span > 1) - qsort(array, from, span); - - span = d - c; - if (span > 1) - qsort(array, hi - span, 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); - } - - /** - * 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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException(); - if (fromIndex < 0) - throw new ArrayIndexOutOfBoundsException(); - qsort(a, fromIndex, toIndex - fromIndex); - } - - /** - * 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 (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)); - } - - /** - * 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) - { - double c = a[i]; - a[i] = a[j]; - a[j] = c; - } - - /** - * 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--) - swap(i, j, a); - } - - /** - * Performs a recursive modified quicksort. - * - * @param array the array to sort - * @param from the start index (inclusive) - * @param count the number of elements to sort - */ - 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 > from && 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 + 2 * s, array); - mid = med3(mid - s, mid, mid + s, array); - hi = med3(hi - 2 * 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; - c = d = from + count - 1; - - // 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. - hi = from + count; - 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, span, array); - - span = b - a; - if (span > 1) - qsort(array, from, span); - - span = d - c; - if (span > 1) - qsort(array, hi - span, span); - } - - /** - * Sort an array of Objects according to their natural ordering. The sort is - * guaranteed to be stable, that is, equal elements will not be reordered. - * The sort algorithm is a mergesort with the merge omitted if the last - * element of one half comes before the first element of the other half. This - * algorithm gives guaranteed O(n*log(n)) time, at the expense of making a - * copy of the array. - * - * @param a the array to be sorted - * @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) - { - sort(a, 0, a.length, null); - } - - /** - * Sort an array of Objects according to a Comparator. The sort is - * guaranteed to be stable, that is, equal elements will not be reordered. - * The sort algorithm is a mergesort with the merge omitted if the last - * element of one half comes before the first element of the other half. This - * algorithm gives guaranteed O(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; 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) - { - sort(a, 0, a.length, c); - } - - /** - * Sort an array of Objects according to their natural ordering. The sort is - * guaranteed to be stable, that is, equal elements will not be reordered. - * The sort algorithm is a mergesort with the merge omitted if the last - * element of one half comes before the first element of the other half. This - * algorithm gives guaranteed O(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 - * @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) - { - sort(a, fromIndex, toIndex, null); - } - - /** - * Sort an array of Objects according to a Comparator. The sort is - * guaranteed to be stable, that is, equal elements will not be reordered. - * The sort algorithm is a mergesort with the merge omitted if the last - * element of one half comes before the first element of the other half. This - * algorithm gives guaranteed O(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; 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) - { - if (fromIndex > toIndex) - throw new IllegalArgumentException("fromIndex " + fromIndex - + " > toIndex " + toIndex); - if (fromIndex < 0) - throw new ArrayIndexOutOfBoundsException(); - - // 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. 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 - * @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) - { - return new Arrays.ArrayList(a); - } - - /** - * 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 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; - } - - /** - * Returns the object at the specified index in - * the array. - * - * @param index The index to retrieve an object from. - * @return The object at the array index specified. - */ - public Object get(int index) - { - return a[index]; - } - - /** - * Returns the size of the array. - * - * @return The size. - */ - public int size() - { - return a.length; - } - - /** - * Replaces the object at the specified index - * with the supplied element. - * - * @param index The index at which to place the new object. - * @param element The new object. - * @return The object replaced by this operation. - */ - public Object set(int index, Object element) - { - Object old = a[index]; - a[index] = element; - return old; - } - - /** - * Returns true if the array contains the - * supplied object. - * - * @param o The object to look for. - * @return True if the object was found. - */ - public boolean contains(Object o) - { - return lastIndexOf(o) >= 0; - } - - /** - * Returns the first index at which the - * object, o, occurs in the array. - * - * @param o The object to search for. - * @return The first relevant index. - */ - public int indexOf(Object o) - { - int size = a.length; - for (int i = 0; i < size; i++) - if (ArrayList.equals(o, a[i])) - return i; - return -1; - } - - /** - * Returns the last index at which the - * object, o, occurs in the array. - * - * @param o The object to search for. - * @return The last relevant index. - */ - public int lastIndexOf(Object o) - { - int i = a.length; - while (--i >= 0) - if (ArrayList.equals(o, a[i])) - return i; - return -1; - } - - /** - * Transforms the list into an array of - * objects, by simplying cloning the array - * wrapped by this list. - * - * @return A clone of the internal array. - */ - public Object[] toArray() - { - return (Object[]) a.clone(); - } - - /** - * Copies the objects from this list into - * the supplied array. The supplied array - * is shrunk or enlarged to the size of the - * internal array, and filled with its objects. - * - * @param array The array to fill with the objects in this list. - * @return The array containing the objects in this list, - * which may or may not be == to array. - */ - 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; - } - } -} |