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