exception statement from your version. */
-package java.util;
-
-import gnu.java.lang.CPStringBuilder;
+//package java.util;
+//
+//import gnu.java.lang.CPStringBuilder;
import java.io.Serializable;
import java.lang.reflect.Array;
* 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)
- {
- if (a.length == 0)
- return -1;
- return binarySearch(a, 0, a.length - 1, key);
- }
-
- /**
- * Perform a binary search of a range of a byte array for a key. The range
- * must be sorted (as by the <code>sort(byte[], int, int)</code> 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 low the lowest index to search from.
- * @param hi the highest index to search to.
- * @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 IllegalArgumentException if <code>low > hi</code>
- * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
- * <code>hi > a.length</code>.
- */
- public static int binarySearch(byte[] a, int low, int hi, byte key)
- {
- if (low > hi)
- throw new IllegalArgumentException("The start index is higher than " +
- "the finish index.");
- if (low < 0 || hi > a.length)
- throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
- "of bounds.");
- 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)
- {
- if (a.length == 0)
- return -1;
- return binarySearch(a, 0, a.length - 1, key);
- }
-
- /**
- * Perform a binary search of a range of a char array for a key. The range
- * must be sorted (as by the <code>sort(char[], int, int)</code> 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 low the lowest index to search from.
- * @param hi the highest index to search to.
- * @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 IllegalArgumentException if <code>low > hi</code>
- * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
- * <code>hi > a.length</code>.
- */
- public static int binarySearch(char[] a, int low, int hi, char key)
- {
- if (low > hi)
- throw new IllegalArgumentException("The start index is higher than " +
- "the finish index.");
- if (low < 0 || hi > a.length)
- throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
- "of bounds.");
- 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)
- {
- if (a.length == 0)
- return -1;
- return binarySearch(a, 0, a.length - 1, key);
- }
-
- /**
- * Perform a binary search of a range of a short array for a key. The range
- * must be sorted (as by the <code>sort(short[], int, int)</code> 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 low the lowest index to search from.
- * @param hi the highest index to search to.
- * @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 IllegalArgumentException if <code>low > hi</code>
- * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
- * <code>hi > a.length</code>.
- */
- public static int binarySearch(short[] a, int low, int hi, short key)
- {
- if (low > hi)
- throw new IllegalArgumentException("The start index is higher than " +
- "the finish index.");
- if (low < 0 || hi > a.length)
- throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
- "of bounds.");
- 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)
- {
- if (a.length == 0)
- return -1;
- return binarySearch(a, 0, a.length - 1, key);
- }
-
- /**
- * Perform a binary search of a range of an integer array for a key. The range
- * must be sorted (as by the <code>sort(int[], int, int)</code> 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 low the lowest index to search from.
- * @param hi the highest index to search to.
- * @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 IllegalArgumentException if <code>low > hi</code>
- * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
- * <code>hi > a.length</code>.
- */
- public static int binarySearch(int[] a, int low, int hi, int key)
- {
- if (low > hi)
- throw new IllegalArgumentException("The start index is higher than " +
- "the finish index.");
- if (low < 0 || hi > a.length)
- throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
- "of bounds.");
- 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)
- {
- if (a.length == 0)
- return -1;
- return binarySearch(a, 0, a.length - 1, key);
- }
-
- /**
- * Perform a binary search of a range of a long array for a key. The range
- * must be sorted (as by the <code>sort(long[], int, int)</code> 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 low the lowest index to search from.
- * @param hi the highest index to search to.
- * @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 IllegalArgumentException if <code>low > hi</code>
- * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
- * <code>hi > a.length</code>.
- */
- public static int binarySearch(long[] a, int low, int hi, long key)
- {
- if (low > hi)
- throw new IllegalArgumentException("The start index is higher than " +
- "the finish index.");
- if (low < 0 || hi > a.length)
- throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
- "of bounds.");
- 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)
- {
- if (a.length == 0)
- return -1;
- return binarySearch(a, 0, a.length - 1, key);
- }
-
- /**
- * Perform a binary search of a range of a float array for a key. The range
- * must be sorted (as by the <code>sort(float[], int, int)</code> 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 low the lowest index to search from.
- * @param hi the highest index to search to.
- * @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 IllegalArgumentException if <code>low > hi</code>
- * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
- * <code>hi > a.length</code>.
- */
- public static int binarySearch(float[] a, int low, int hi, float key)
- {
- if (low > hi)
- throw new IllegalArgumentException("The start index is higher than " +
- "the finish index.");
- if (low < 0 || hi > a.length)
- throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
- "of bounds.");
- // Must use Float.compare to take into account NaN, +-0.
- 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)
- {
- if (a.length == 0)
- return -1;
- return binarySearch(a, 0, a.length - 1, key);
- }
-
- /**
- * Perform a binary search of a range of a double array for a key. The range
- * must be sorted (as by the <code>sort(double[], int, int)</code> 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 low the lowest index to search from.
- * @param hi the highest index to search to.
- * @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 IllegalArgumentException if <code>low > hi</code>
- * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
- * <code>hi > a.length</code>.
- */
- public static int binarySearch(double[] a, int low, int hi, double key)
- {
- if (low > hi)
- throw new IllegalArgumentException("The start index is higher than " +
- "the finish index.");
- if (low < 0 || hi > a.length)
- throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
- "of bounds.");
- // Must use Double.compare to take into account NaN, +-0.
- 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)
- {
- if (a.length == 0)
- return -1;
- return binarySearch(a, key, null);
- }
-
- /**
- * Perform a binary search of a range of an Object array for a key. The range
- * must be sorted (as by the <code>sort(Object[], int, int)</code> 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 low the lowest index to search from.
- * @param hi the highest index to search to.
- * @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(Object[] a, int low, int hi, Object key)
- {
- return binarySearch(a, low, hi, 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 <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
- {
- if (a.length == 0)
- return -1;
- return binarySearch(a, 0, a.length - 1, key, c);
- }
-
- /**
- * Perform a binary search of a range of an Object array for a key using
- * a {@link Comparator}. The range must be sorted (as by the
- * <code>sort(Object[], int, int)</code> 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 low the lowest index to search from.
- * @param hi the highest index to search to.
- * @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 IllegalArgumentException if <code>low > hi</code>
- * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
- * <code>hi > a.length</code>.
- */
- public static <T> int binarySearch(T[] a, int low, int hi, T key,
- Comparator<? super T> c)
- {
- if (low > hi)
- throw new IllegalArgumentException("The start index is higher than " +
- "the finish index.");
- if (low < 0 || hi > a.length)
- throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
- "of bounds.");
- int mid = 0;
- while (low <= hi)
- {
- mid = (low + hi) >>> 1;
- // NOTE: Please keep the order of a[mid] and key. Although
- // not required by the specs, the RI has it in this order as
- // well, and real programs (erroneously) depend on it.
- final int d = Collections.compare(a[mid], key, 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;
- }
+// public static int binarySearch(byte[] a, byte key)
+// {
+// if (a.length == 0)
+// return -1;
+// return binarySearch(a, 0, a.length - 1, key);
+// }
+//
+// /**
+// * Perform a binary search of a range of a byte array for a key. The range
+// * must be sorted (as by the <code>sort(byte[], int, int)</code> 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 low the lowest index to search from.
+// * @param hi the highest index to search to.
+// * @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 IllegalArgumentException if <code>low > hi</code>
+// * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
+// * <code>hi > a.length</code>.
+// */
+// public static int binarySearch(byte[] a, int low, int hi, byte key)
+// {
+// if (low > hi)
+// throw new IllegalArgumentException("The start index is higher than " +
+// "the finish index.");
+// if (low < 0 || hi > a.length)
+// throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
+// "of bounds.");
+// 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)
+// {
+// if (a.length == 0)
+// return -1;
+// return binarySearch(a, 0, a.length - 1, key);
+// }
+//
+// /**
+// * Perform a binary search of a range of a char array for a key. The range
+// * must be sorted (as by the <code>sort(char[], int, int)</code> 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 low the lowest index to search from.
+// * @param hi the highest index to search to.
+// * @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 IllegalArgumentException if <code>low > hi</code>
+// * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
+// * <code>hi > a.length</code>.
+// */
+// public static int binarySearch(char[] a, int low, int hi, char key)
+// {
+// if (low > hi)
+// throw new IllegalArgumentException("The start index is higher than " +
+// "the finish index.");
+// if (low < 0 || hi > a.length)
+// throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
+// "of bounds.");
+// 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)
+// {
+// if (a.length == 0)
+// return -1;
+// return binarySearch(a, 0, a.length - 1, key);
+// }
+//
+// /**
+// * Perform a binary search of a range of a short array for a key. The range
+// * must be sorted (as by the <code>sort(short[], int, int)</code> 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 low the lowest index to search from.
+// * @param hi the highest index to search to.
+// * @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 IllegalArgumentException if <code>low > hi</code>
+// * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
+// * <code>hi > a.length</code>.
+// */
+// public static int binarySearch(short[] a, int low, int hi, short key)
+// {
+// if (low > hi)
+// throw new IllegalArgumentException("The start index is higher than " +
+// "the finish index.");
+// if (low < 0 || hi > a.length)
+// throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
+// "of bounds.");
+// 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)
+// {
+// if (a.length == 0)
+// return -1;
+// return binarySearch(a, 0, a.length - 1, key);
+// }
+//
+// /**
+// * Perform a binary search of a range of an integer array for a key. The range
+// * must be sorted (as by the <code>sort(int[], int, int)</code> 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 low the lowest index to search from.
+// * @param hi the highest index to search to.
+// * @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 IllegalArgumentException if <code>low > hi</code>
+// * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
+// * <code>hi > a.length</code>.
+// */
+// public static int binarySearch(int[] a, int low, int hi, int key)
+// {
+// if (low > hi)
+// throw new IllegalArgumentException("The start index is higher than " +
+// "the finish index.");
+// if (low < 0 || hi > a.length)
+// throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
+// "of bounds.");
+// 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)
+// {
+// if (a.length == 0)
+// return -1;
+// return binarySearch(a, 0, a.length - 1, key);
+// }
+//
+// /**
+// * Perform a binary search of a range of a long array for a key. The range
+// * must be sorted (as by the <code>sort(long[], int, int)</code> 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 low the lowest index to search from.
+// * @param hi the highest index to search to.
+// * @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 IllegalArgumentException if <code>low > hi</code>
+// * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
+// * <code>hi > a.length</code>.
+// */
+// public static int binarySearch(long[] a, int low, int hi, long key)
+// {
+// if (low > hi)
+// throw new IllegalArgumentException("The start index is higher than " +
+// "the finish index.");
+// if (low < 0 || hi > a.length)
+// throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
+// "of bounds.");
+// 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)
+// {
+// if (a.length == 0)
+// return -1;
+// return binarySearch(a, 0, a.length - 1, key);
+// }
+//
+// /**
+// * Perform a binary search of a range of a float array for a key. The range
+// * must be sorted (as by the <code>sort(float[], int, int)</code> 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 low the lowest index to search from.
+// * @param hi the highest index to search to.
+// * @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 IllegalArgumentException if <code>low > hi</code>
+// * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
+// * <code>hi > a.length</code>.
+// */
+// public static int binarySearch(float[] a, int low, int hi, float key)
+// {
+// if (low > hi)
+// throw new IllegalArgumentException("The start index is higher than " +
+// "the finish index.");
+// if (low < 0 || hi > a.length)
+// throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
+// "of bounds.");
+// // Must use Float.compare to take into account NaN, +-0.
+// 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)
+// {
+// if (a.length == 0)
+// return -1;
+// return binarySearch(a, 0, a.length - 1, key);
+// }
+//
+// /**
+// * Perform a binary search of a range of a double array for a key. The range
+// * must be sorted (as by the <code>sort(double[], int, int)</code> 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 low the lowest index to search from.
+// * @param hi the highest index to search to.
+// * @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 IllegalArgumentException if <code>low > hi</code>
+// * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
+// * <code>hi > a.length</code>.
+// */
+// public static int binarySearch(double[] a, int low, int hi, double key)
+// {
+// if (low > hi)
+// throw new IllegalArgumentException("The start index is higher than " +
+// "the finish index.");
+// if (low < 0 || hi > a.length)
+// throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
+// "of bounds.");
+// // Must use Double.compare to take into account NaN, +-0.
+// 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)
+// {
+// if (a.length == 0)
+// return -1;
+// return binarySearch(a, key, null);
+// }
+//
+// /**
+// * Perform a binary search of a range of an Object array for a key. The range
+// * must be sorted (as by the <code>sort(Object[], int, int)</code> 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 low the lowest index to search from.
+// * @param hi the highest index to search to.
+// * @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(Object[] a, int low, int hi, Object key)
+// {
+// return binarySearch(a, low, hi, 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 <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
+// {
+// if (a.length == 0)
+// return -1;
+// return binarySearch(a, 0, a.length - 1, key, c);
+// }
+//
+// /**
+// * Perform a binary search of a range of an Object array for a key using
+// * a {@link Comparator}. The range must be sorted (as by the
+// * <code>sort(Object[], int, int)</code> 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 low the lowest index to search from.
+// * @param hi the highest index to search to.
+// * @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 IllegalArgumentException if <code>low > hi</code>
+// * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or
+// * <code>hi > a.length</code>.
+// */
+// public static <T> int binarySearch(T[] a, int low, int hi, T key,
+// Comparator<? super T> c)
+// {
+// if (low > hi)
+// throw new IllegalArgumentException("The start index is higher than " +
+// "the finish index.");
+// if (low < 0 || hi > a.length)
+// throw new ArrayIndexOutOfBoundsException("One of the indices is out " +
+// "of bounds.");
+// int mid = 0;
+// while (low <= hi)
+// {
+// mid = (low + hi) >>> 1;
+// // NOTE: Please keep the order of a[mid] and key. Although
+// // not required by the specs, the RI has it in this order as
+// // well, and real programs (erroneously) depend on it.
+// final int d = Collections.compare(a[mid], key, 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;
+// }
+//
+//\f
+//// 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;
+// }
+//
+//\f
+//// 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;
+// }
+//
+//\f
+//// 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 = from + 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);
+// }
-\f
-// equals
/**
- * Compare two boolean arrays for equality.
+ * Performs a stable sort on the elements, arranging them according to their
+ * natural order.
*
- * @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]
+ * @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 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;
- }
+// 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 = from + 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 = from + 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 = from + 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 = from + 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 = from + 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 = from + 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 <T> void sort(T[] a, Comparator<? super T> 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 <T> void sort(T[] a, int fromIndex, int toIndex,
+// Comparator<? super T> 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;
+// T 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;
+//
+// T[] src = a;
+// T[] dest = (T[]) new Object[len];
+// T[] 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);
+// }
+// }
/**
- * 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;
- }
-
-\f
-// 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;
- }
-
-\f
-// 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 = from + 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 = from + 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 = from + 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 = from + 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 = from + 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 = from + 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 = from + 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 <T> void sort(T[] a, Comparator<? super T> 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 <T> void sort(T[] a, int fromIndex, int toIndex,
- Comparator<? super T> 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;
- T 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;
-
- T[] src = a;
- T[] dest = (T[]) new Object[len];
- T[] 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.
+ * 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 (<code>null</code> not permitted)
* @return a fixed-size list, changes to which "write through" to the array
* @throws NullPointerException if <code>a</code> is <code>null</code>.
* @see Serializable
* @see RandomAccess
- * @see Arrays.ArrayList
- */
- public static <T> List<T> asList(final T... a)
- {
- return new Arrays.ArrayList(a);
- }
-
- /**
- * Returns the hashcode of an array of long numbers. If two arrays
- * are equal, according to <code>equals()</code>, they should have the
- * same hashcode. The hashcode returned by the method is equal to that
- * obtained by the corresponding <code>List</code> object. This has the same
- * data, but represents longs in their wrapper class, <code>Long</code>.
- * For <code>null</code>, 0 is returned.
- *
- * @param v an array of long numbers for which the hash code should be
- * computed.
- * @return the hash code of the array, or 0 if null was given.
- * @since 1.5
- */
- public static int hashCode(long[] v)
- {
- if (v == null)
- return 0;
- int result = 1;
- for (int i = 0; i < v.length; ++i)
- {
- int elt = (int) (v[i] ^ (v[i] >>> 32));
- result = 31 * result + elt;
- }
- return result;
- }
-
- /**
- * Returns the hashcode of an array of integer numbers. If two arrays
- * are equal, according to <code>equals()</code>, they should have the
- * same hashcode. The hashcode returned by the method is equal to that
- * obtained by the corresponding <code>List</code> object. This has the same
- * data, but represents ints in their wrapper class, <code>Integer</code>.
- * For <code>null</code>, 0 is returned.
- *
- * @param v an array of integer numbers for which the hash code should be
- * computed.
- * @return the hash code of the array, or 0 if null was given.
- * @since 1.5
- */
- public static int hashCode(int[] v)
- {
- if (v == null)
- return 0;
- int result = 1;
- for (int i = 0; i < v.length; ++i)
- result = 31 * result + v[i];
- return result;
- }
-
- /**
- * Returns the hashcode of an array of short numbers. If two arrays
- * are equal, according to <code>equals()</code>, they should have the
- * same hashcode. The hashcode returned by the method is equal to that
- * obtained by the corresponding <code>List</code> object. This has the same
- * data, but represents shorts in their wrapper class, <code>Short</code>.
- * For <code>null</code>, 0 is returned.
- *
- * @param v an array of short numbers for which the hash code should be
- * computed.
- * @return the hash code of the array, or 0 if null was given.
- * @since 1.5
- */
- public static int hashCode(short[] v)
- {
- if (v == null)
- return 0;
- int result = 1;
- for (int i = 0; i < v.length; ++i)
- result = 31 * result + v[i];
- return result;
- }
-
- /**
- * Returns the hashcode of an array of characters. If two arrays
- * are equal, according to <code>equals()</code>, they should have the
- * same hashcode. The hashcode returned by the method is equal to that
- * obtained by the corresponding <code>List</code> object. This has the same
- * data, but represents chars in their wrapper class, <code>Character</code>.
- * For <code>null</code>, 0 is returned.
- *
- * @param v an array of characters for which the hash code should be
- * computed.
- * @return the hash code of the array, or 0 if null was given.
- * @since 1.5
- */
- public static int hashCode(char[] v)
- {
- if (v == null)
- return 0;
- int result = 1;
- for (int i = 0; i < v.length; ++i)
- result = 31 * result + v[i];
- return result;
- }
-
- /**
- * Returns the hashcode of an array of bytes. If two arrays
- * are equal, according to <code>equals()</code>, they should have the
- * same hashcode. The hashcode returned by the method is equal to that
- * obtained by the corresponding <code>List</code> object. This has the same
- * data, but represents bytes in their wrapper class, <code>Byte</code>.
- * For <code>null</code>, 0 is returned.
- *
- * @param v an array of bytes for which the hash code should be
- * computed.
- * @return the hash code of the array, or 0 if null was given.
- * @since 1.5
- */
- public static int hashCode(byte[] v)
- {
- if (v == null)
- return 0;
- int result = 1;
- for (int i = 0; i < v.length; ++i)
- result = 31 * result + v[i];
- return result;
- }
-
- /**
- * Returns the hashcode of an array of booleans. If two arrays
- * are equal, according to <code>equals()</code>, they should have the
- * same hashcode. The hashcode returned by the method is equal to that
- * obtained by the corresponding <code>List</code> object. This has the same
- * data, but represents booleans in their wrapper class,
- * <code>Boolean</code>. For <code>null</code>, 0 is returned.
- *
- * @param v an array of booleans for which the hash code should be
- * computed.
- * @return the hash code of the array, or 0 if null was given.
- * @since 1.5
- */
- public static int hashCode(boolean[] v)
- {
- if (v == null)
- return 0;
- int result = 1;
- for (int i = 0; i < v.length; ++i)
- result = 31 * result + (v[i] ? 1231 : 1237);
- return result;
- }
-
- /**
- * Returns the hashcode of an array of floats. If two arrays
- * are equal, according to <code>equals()</code>, they should have the
- * same hashcode. The hashcode returned by the method is equal to that
- * obtained by the corresponding <code>List</code> object. This has the same
- * data, but represents floats in their wrapper class, <code>Float</code>.
- * For <code>null</code>, 0 is returned.
- *
- * @param v an array of floats for which the hash code should be
- * computed.
- * @return the hash code of the array, or 0 if null was given.
- * @since 1.5
- */
- public static int hashCode(float[] v)
- {
- if (v == null)
- return 0;
- int result = 1;
- for (int i = 0; i < v.length; ++i)
- result = 31 * result + Float.floatToIntBits(v[i]);
- return result;
- }
-
- /**
- * Returns the hashcode of an array of doubles. If two arrays
- * are equal, according to <code>equals()</code>, they should have the
- * same hashcode. The hashcode returned by the method is equal to that
- * obtained by the corresponding <code>List</code> object. This has the same
- * data, but represents doubles in their wrapper class, <code>Double</code>.
- * For <code>null</code>, 0 is returned.
- *
- * @param v an array of doubles for which the hash code should be
- * computed.
- * @return the hash code of the array, or 0 if null was given.
- * @since 1.5
- */
- public static int hashCode(double[] v)
- {
- if (v == null)
- return 0;
- int result = 1;
- for (int i = 0; i < v.length; ++i)
- {
- long l = Double.doubleToLongBits(v[i]);
- int elt = (int) (l ^ (l >>> 32));
- result = 31 * result + elt;
- }
- return result;
- }
-
- /**
- * Returns the hashcode of an array of objects. If two arrays
- * are equal, according to <code>equals()</code>, they should have the
- * same hashcode. The hashcode returned by the method is equal to that
- * obtained by the corresponding <code>List</code> object.
- * For <code>null</code>, 0 is returned.
- *
- * @param v an array of integer numbers for which the hash code should be
- * computed.
- * @return the hash code of the array, or 0 if null was given.
- * @since 1.5
- */
- public static int hashCode(Object[] v)
- {
- if (v == null)
- return 0;
- int result = 1;
- for (int i = 0; i < v.length; ++i)
- {
- int elt = v[i] == null ? 0 : v[i].hashCode();
- result = 31 * result + elt;
- }
- return result;
- }
-
- public static int deepHashCode(Object[] v)
- {
- if (v == null)
- return 0;
- int result = 1;
- for (int i = 0; i < v.length; ++i)
- {
- int elt;
- if (v[i] == null)
- elt = 0;
- else if (v[i] instanceof boolean[])
- elt = hashCode((boolean[]) v[i]);
- else if (v[i] instanceof byte[])
- elt = hashCode((byte[]) v[i]);
- else if (v[i] instanceof char[])
- elt = hashCode((char[]) v[i]);
- else if (v[i] instanceof short[])
- elt = hashCode((short[]) v[i]);
- else if (v[i] instanceof int[])
- elt = hashCode((int[]) v[i]);
- else if (v[i] instanceof long[])
- elt = hashCode((long[]) v[i]);
- else if (v[i] instanceof float[])
- elt = hashCode((float[]) v[i]);
- else if (v[i] instanceof double[])
- elt = hashCode((double[]) v[i]);
- else if (v[i] instanceof Object[])
- elt = hashCode((Object[]) v[i]);
- else
- elt = v[i].hashCode();
- result = 31 * result + elt;
- }
- return result;
- }
-
- /** @since 1.5 */
- public static boolean deepEquals(Object[] v1, Object[] v2)
- {
- if (v1 == null)
- return v2 == null;
- if (v2 == null || v1.length != v2.length)
- return false;
-
- for (int i = 0; i < v1.length; ++i)
- {
- Object e1 = v1[i];
- Object e2 = v2[i];
-
- if (e1 == e2)
- continue;
- if (e1 == null || e2 == null)
- return false;
-
- boolean check;
- if (e1 instanceof boolean[] && e2 instanceof boolean[])
- check = equals((boolean[]) e1, (boolean[]) e2);
- else if (e1 instanceof byte[] && e2 instanceof byte[])
- check = equals((byte[]) e1, (byte[]) e2);
- else if (e1 instanceof char[] && e2 instanceof char[])
- check = equals((char[]) e1, (char[]) e2);
- else if (e1 instanceof short[] && e2 instanceof short[])
- check = equals((short[]) e1, (short[]) e2);
- else if (e1 instanceof int[] && e2 instanceof int[])
- check = equals((int[]) e1, (int[]) e2);
- else if (e1 instanceof long[] && e2 instanceof long[])
- check = equals((long[]) e1, (long[]) e2);
- else if (e1 instanceof float[] && e2 instanceof float[])
- check = equals((float[]) e1, (float[]) e2);
- else if (e1 instanceof double[] && e2 instanceof double[])
- check = equals((double[]) e1, (double[]) e2);
- else if (e1 instanceof Object[] && e2 instanceof Object[])
- check = equals((Object[]) e1, (Object[]) e2);
- else
- check = e1.equals(e2);
- if (! check)
- return false;
- }
-
- return true;
- }
-
- /**
- * Returns a String representation of the argument array. Returns "null"
- * if <code>a</code> is null.
- * @param v the array to represent
- * @return a String representing this array
- * @since 1.5
- */
- public static String toString(boolean[] v)
- {
- if (v == null)
- return "null";
- CPStringBuilder b = new CPStringBuilder("[");
- for (int i = 0; i < v.length; ++i)
- {
- if (i > 0)
- b.append(", ");
- b.append(v[i]);
- }
- b.append("]");
- return b.toString();
- }
-
- /**
- * Returns a String representation of the argument array. Returns "null"
- * if <code>a</code> is null.
- * @param v the array to represent
- * @return a String representing this array
- * @since 1.5
- */
- public static String toString(byte[] v)
- {
- if (v == null)
- return "null";
- CPStringBuilder b = new CPStringBuilder("[");
- for (int i = 0; i < v.length; ++i)
- {
- if (i > 0)
- b.append(", ");
- b.append(v[i]);
- }
- b.append("]");
- return b.toString();
- }
-
- /**
- * Returns a String representation of the argument array. Returns "null"
- * if <code>a</code> is null.
- * @param v the array to represent
- * @return a String representing this array
- * @since 1.5
- */
- public static String toString(char[] v)
- {
- if (v == null)
- return "null";
- CPStringBuilder b = new CPStringBuilder("[");
- for (int i = 0; i < v.length; ++i)
- {
- if (i > 0)
- b.append(", ");
- b.append(v[i]);
- }
- b.append("]");
- return b.toString();
- }
-
- /**
- * Returns a String representation of the argument array. Returns "null"
- * if <code>a</code> is null.
- * @param v the array to represent
- * @return a String representing this array
- * @since 1.5
- */
- public static String toString(short[] v)
- {
- if (v == null)
- return "null";
- CPStringBuilder b = new CPStringBuilder("[");
- for (int i = 0; i < v.length; ++i)
- {
- if (i > 0)
- b.append(", ");
- b.append(v[i]);
- }
- b.append("]");
- return b.toString();
- }
-
- /**
- * Returns a String representation of the argument array. Returns "null"
- * if <code>a</code> is null.
- * @param v the array to represent
- * @return a String representing this array
- * @since 1.5
- */
- public static String toString(int[] v)
- {
- if (v == null)
- return "null";
- CPStringBuilder b = new CPStringBuilder("[");
- for (int i = 0; i < v.length; ++i)
- {
- if (i > 0)
- b.append(", ");
- b.append(v[i]);
- }
- b.append("]");
- return b.toString();
- }
-
- /**
- * Returns a String representation of the argument array. Returns "null"
- * if <code>a</code> is null.
- * @param v the array to represent
- * @return a String representing this array
- * @since 1.5
- */
- public static String toString(long[] v)
- {
- if (v == null)
- return "null";
- CPStringBuilder b = new CPStringBuilder("[");
- for (int i = 0; i < v.length; ++i)
- {
- if (i > 0)
- b.append(", ");
- b.append(v[i]);
- }
- b.append("]");
- return b.toString();
- }
-
- /**
- * Returns a String representation of the argument array. Returns "null"
- * if <code>a</code> is null.
- * @param v the array to represent
- * @return a String representing this array
- * @since 1.5
- */
- public static String toString(float[] v)
- {
- if (v == null)
- return "null";
- CPStringBuilder b = new CPStringBuilder("[");
- for (int i = 0; i < v.length; ++i)
- {
- if (i > 0)
- b.append(", ");
- b.append(v[i]);
- }
- b.append("]");
- return b.toString();
- }
-
- /**
- * Returns a String representation of the argument array. Returns "null"
- * if <code>a</code> is null.
- * @param v the array to represent
- * @return a String representing this array
- * @since 1.5
- */
- public static String toString(double[] v)
- {
- if (v == null)
- return "null";
- CPStringBuilder b = new CPStringBuilder("[");
- for (int i = 0; i < v.length; ++i)
- {
- if (i > 0)
- b.append(", ");
- b.append(v[i]);
- }
- b.append("]");
- return b.toString();
- }
-
- /**
- * Returns a String representation of the argument array. Returns "null"
- * if <code>a</code> is null.
- * @param v the array to represent
- * @return a String representing this array
- * @since 1.5
+ * @see Arrays.ArrayList
*/
- public static String toString(Object[] v)
- {
- if (v == null)
- return "null";
- CPStringBuilder b = new CPStringBuilder("[");
- for (int i = 0; i < v.length; ++i)
- {
- if (i > 0)
- b.append(", ");
- b.append(v[i]);
- }
- b.append("]");
- return b.toString();
- }
-
- private static void deepToString(Object[] v, CPStringBuilder b, HashSet seen)
+ public static /*<T>*/ List/*<T>*/ asList(final /*T...*/Object[] a)
{
- b.append("[");
- for (int i = 0; i < v.length; ++i)
- {
- if (i > 0)
- b.append(", ");
- Object elt = v[i];
- if (elt == null)
- b.append("null");
- else if (elt instanceof boolean[])
- b.append(toString((boolean[]) elt));
- else if (elt instanceof byte[])
- b.append(toString((byte[]) elt));
- else if (elt instanceof char[])
- b.append(toString((char[]) elt));
- else if (elt instanceof short[])
- b.append(toString((short[]) elt));
- else if (elt instanceof int[])
- b.append(toString((int[]) elt));
- else if (elt instanceof long[])
- b.append(toString((long[]) elt));
- else if (elt instanceof float[])
- b.append(toString((float[]) elt));
- else if (elt instanceof double[])
- b.append(toString((double[]) elt));
- else if (elt instanceof Object[])
- {
- Object[] os = (Object[]) elt;
- if (seen.contains(os))
- b.append("[...]");
- else
- {
- seen.add(os);
- deepToString(os, b, seen);
- }
- }
- else
- b.append(elt);
- }
- b.append("]");
+ return new Arrays.ArrayList(a);
}
- /** @since 1.5 */
- public static String deepToString(Object[] v)
- {
- if (v == null)
- return "null";
- HashSet seen = new HashSet();
- CPStringBuilder b = new CPStringBuilder();
- deepToString(v, b, seen);
- return b.toString();
- }
+ /**
+ * Returns the hashcode of an array of long numbers. If two arrays
+ * are equal, according to <code>equals()</code>, they should have the
+ * same hashcode. The hashcode returned by the method is equal to that
+ * obtained by the corresponding <code>List</code> object. This has the same
+ * data, but represents longs in their wrapper class, <code>Long</code>.
+ * For <code>null</code>, 0 is returned.
+ *
+ * @param v an array of long numbers for which the hash code should be
+ * computed.
+ * @return the hash code of the array, or 0 if null was given.
+ * @since 1.5
+ */
+// public static int hashCode(long[] v)
+// {
+// if (v == null)
+// return 0;
+// int result = 1;
+// for (int i = 0; i < v.length; ++i)
+// {
+// int elt = (int) (v[i] ^ (v[i] >>> 32));
+// result = 31 * result + elt;
+// }
+// return result;
+// }
+//
+// /**
+// * Returns the hashcode of an array of integer numbers. If two arrays
+// * are equal, according to <code>equals()</code>, they should have the
+// * same hashcode. The hashcode returned by the method is equal to that
+// * obtained by the corresponding <code>List</code> object. This has the same
+// * data, but represents ints in their wrapper class, <code>Integer</code>.
+// * For <code>null</code>, 0 is returned.
+// *
+// * @param v an array of integer numbers for which the hash code should be
+// * computed.
+// * @return the hash code of the array, or 0 if null was given.
+// * @since 1.5
+// */
+// public static int hashCode(int[] v)
+// {
+// if (v == null)
+// return 0;
+// int result = 1;
+// for (int i = 0; i < v.length; ++i)
+// result = 31 * result + v[i];
+// return result;
+// }
+//
+// /**
+// * Returns the hashcode of an array of short numbers. If two arrays
+// * are equal, according to <code>equals()</code>, they should have the
+// * same hashcode. The hashcode returned by the method is equal to that
+// * obtained by the corresponding <code>List</code> object. This has the same
+// * data, but represents shorts in their wrapper class, <code>Short</code>.
+// * For <code>null</code>, 0 is returned.
+// *
+// * @param v an array of short numbers for which the hash code should be
+// * computed.
+// * @return the hash code of the array, or 0 if null was given.
+// * @since 1.5
+// */
+// public static int hashCode(short[] v)
+// {
+// if (v == null)
+// return 0;
+// int result = 1;
+// for (int i = 0; i < v.length; ++i)
+// result = 31 * result + v[i];
+// return result;
+// }
+//
+// /**
+// * Returns the hashcode of an array of characters. If two arrays
+// * are equal, according to <code>equals()</code>, they should have the
+// * same hashcode. The hashcode returned by the method is equal to that
+// * obtained by the corresponding <code>List</code> object. This has the same
+// * data, but represents chars in their wrapper class, <code>Character</code>.
+// * For <code>null</code>, 0 is returned.
+// *
+// * @param v an array of characters for which the hash code should be
+// * computed.
+// * @return the hash code of the array, or 0 if null was given.
+// * @since 1.5
+// */
+// public static int hashCode(char[] v)
+// {
+// if (v == null)
+// return 0;
+// int result = 1;
+// for (int i = 0; i < v.length; ++i)
+// result = 31 * result + v[i];
+// return result;
+// }
+//
+// /**
+// * Returns the hashcode of an array of bytes. If two arrays
+// * are equal, according to <code>equals()</code>, they should have the
+// * same hashcode. The hashcode returned by the method is equal to that
+// * obtained by the corresponding <code>List</code> object. This has the same
+// * data, but represents bytes in their wrapper class, <code>Byte</code>.
+// * For <code>null</code>, 0 is returned.
+// *
+// * @param v an array of bytes for which the hash code should be
+// * computed.
+// * @return the hash code of the array, or 0 if null was given.
+// * @since 1.5
+// */
+// public static int hashCode(byte[] v)
+// {
+// if (v == null)
+// return 0;
+// int result = 1;
+// for (int i = 0; i < v.length; ++i)
+// result = 31 * result + v[i];
+// return result;
+// }
+//
+// /**
+// * Returns the hashcode of an array of booleans. If two arrays
+// * are equal, according to <code>equals()</code>, they should have the
+// * same hashcode. The hashcode returned by the method is equal to that
+// * obtained by the corresponding <code>List</code> object. This has the same
+// * data, but represents booleans in their wrapper class,
+// * <code>Boolean</code>. For <code>null</code>, 0 is returned.
+// *
+// * @param v an array of booleans for which the hash code should be
+// * computed.
+// * @return the hash code of the array, or 0 if null was given.
+// * @since 1.5
+// */
+// public static int hashCode(boolean[] v)
+// {
+// if (v == null)
+// return 0;
+// int result = 1;
+// for (int i = 0; i < v.length; ++i)
+// result = 31 * result + (v[i] ? 1231 : 1237);
+// return result;
+// }
+//
+// /**
+// * Returns the hashcode of an array of floats. If two arrays
+// * are equal, according to <code>equals()</code>, they should have the
+// * same hashcode. The hashcode returned by the method is equal to that
+// * obtained by the corresponding <code>List</code> object. This has the same
+// * data, but represents floats in their wrapper class, <code>Float</code>.
+// * For <code>null</code>, 0 is returned.
+// *
+// * @param v an array of floats for which the hash code should be
+// * computed.
+// * @return the hash code of the array, or 0 if null was given.
+// * @since 1.5
+// */
+// public static int hashCode(float[] v)
+// {
+// if (v == null)
+// return 0;
+// int result = 1;
+// for (int i = 0; i < v.length; ++i)
+// result = 31 * result + Float.floatToIntBits(v[i]);
+// return result;
+// }
+//
+// /**
+// * Returns the hashcode of an array of doubles. If two arrays
+// * are equal, according to <code>equals()</code>, they should have the
+// * same hashcode. The hashcode returned by the method is equal to that
+// * obtained by the corresponding <code>List</code> object. This has the same
+// * data, but represents doubles in their wrapper class, <code>Double</code>.
+// * For <code>null</code>, 0 is returned.
+// *
+// * @param v an array of doubles for which the hash code should be
+// * computed.
+// * @return the hash code of the array, or 0 if null was given.
+// * @since 1.5
+// */
+// public static int hashCode(double[] v)
+// {
+// if (v == null)
+// return 0;
+// int result = 1;
+// for (int i = 0; i < v.length; ++i)
+// {
+// long l = Double.doubleToLongBits(v[i]);
+// int elt = (int) (l ^ (l >>> 32));
+// result = 31 * result + elt;
+// }
+// return result;
+// }
+//
+// /**
+// * Returns the hashcode of an array of objects. If two arrays
+// * are equal, according to <code>equals()</code>, they should have the
+// * same hashcode. The hashcode returned by the method is equal to that
+// * obtained by the corresponding <code>List</code> object.
+// * For <code>null</code>, 0 is returned.
+// *
+// * @param v an array of integer numbers for which the hash code should be
+// * computed.
+// * @return the hash code of the array, or 0 if null was given.
+// * @since 1.5
+// */
+// public static int hashCode(Object[] v)
+// {
+// if (v == null)
+// return 0;
+// int result = 1;
+// for (int i = 0; i < v.length; ++i)
+// {
+// int elt = v[i] == null ? 0 : v[i].hashCode();
+// result = 31 * result + elt;
+// }
+// return result;
+// }
+//
+// public static int deepHashCode(Object[] v)
+// {
+// if (v == null)
+// return 0;
+// int result = 1;
+// for (int i = 0; i < v.length; ++i)
+// {
+// int elt;
+// if (v[i] == null)
+// elt = 0;
+// else if (v[i] instanceof boolean[])
+// elt = hashCode((boolean[]) v[i]);
+// else if (v[i] instanceof byte[])
+// elt = hashCode((byte[]) v[i]);
+// else if (v[i] instanceof char[])
+// elt = hashCode((char[]) v[i]);
+// else if (v[i] instanceof short[])
+// elt = hashCode((short[]) v[i]);
+// else if (v[i] instanceof int[])
+// elt = hashCode((int[]) v[i]);
+// else if (v[i] instanceof long[])
+// elt = hashCode((long[]) v[i]);
+// else if (v[i] instanceof float[])
+// elt = hashCode((float[]) v[i]);
+// else if (v[i] instanceof double[])
+// elt = hashCode((double[]) v[i]);
+// else if (v[i] instanceof Object[])
+// elt = hashCode((Object[]) v[i]);
+// else
+// elt = v[i].hashCode();
+// result = 31 * result + elt;
+// }
+// return result;
+// }
+//
+// /** @since 1.5 */
+// public static boolean deepEquals(Object[] v1, Object[] v2)
+// {
+// if (v1 == null)
+// return v2 == null;
+// if (v2 == null || v1.length != v2.length)
+// return false;
+//
+// for (int i = 0; i < v1.length; ++i)
+// {
+// Object e1 = v1[i];
+// Object e2 = v2[i];
+//
+// if (e1 == e2)
+// continue;
+// if (e1 == null || e2 == null)
+// return false;
+//
+// boolean check;
+// if (e1 instanceof boolean[] && e2 instanceof boolean[])
+// check = equals((boolean[]) e1, (boolean[]) e2);
+// else if (e1 instanceof byte[] && e2 instanceof byte[])
+// check = equals((byte[]) e1, (byte[]) e2);
+// else if (e1 instanceof char[] && e2 instanceof char[])
+// check = equals((char[]) e1, (char[]) e2);
+// else if (e1 instanceof short[] && e2 instanceof short[])
+// check = equals((short[]) e1, (short[]) e2);
+// else if (e1 instanceof int[] && e2 instanceof int[])
+// check = equals((int[]) e1, (int[]) e2);
+// else if (e1 instanceof long[] && e2 instanceof long[])
+// check = equals((long[]) e1, (long[]) e2);
+// else if (e1 instanceof float[] && e2 instanceof float[])
+// check = equals((float[]) e1, (float[]) e2);
+// else if (e1 instanceof double[] && e2 instanceof double[])
+// check = equals((double[]) e1, (double[]) e2);
+// else if (e1 instanceof Object[] && e2 instanceof Object[])
+// check = equals((Object[]) e1, (Object[]) e2);
+// else
+// check = e1.equals(e2);
+// if (! check)
+// return false;
+// }
+//
+// return true;
+// }
+//
+// /**
+// * Returns a String representation of the argument array. Returns "null"
+// * if <code>a</code> is null.
+// * @param v the array to represent
+// * @return a String representing this array
+// * @since 1.5
+// */
+// public static String toString(boolean[] v)
+// {
+// if (v == null)
+// return "null";
+// CPStringBuilder b = new CPStringBuilder("[");
+// for (int i = 0; i < v.length; ++i)
+// {
+// if (i > 0)
+// b.append(", ");
+// b.append(v[i]);
+// }
+// b.append("]");
+// return b.toString();
+// }
+//
+// /**
+// * Returns a String representation of the argument array. Returns "null"
+// * if <code>a</code> is null.
+// * @param v the array to represent
+// * @return a String representing this array
+// * @since 1.5
+// */
+// public static String toString(byte[] v)
+// {
+// if (v == null)
+// return "null";
+// CPStringBuilder b = new CPStringBuilder("[");
+// for (int i = 0; i < v.length; ++i)
+// {
+// if (i > 0)
+// b.append(", ");
+// b.append(v[i]);
+// }
+// b.append("]");
+// return b.toString();
+// }
+//
+// /**
+// * Returns a String representation of the argument array. Returns "null"
+// * if <code>a</code> is null.
+// * @param v the array to represent
+// * @return a String representing this array
+// * @since 1.5
+// */
+// public static String toString(char[] v)
+// {
+// if (v == null)
+// return "null";
+// CPStringBuilder b = new CPStringBuilder("[");
+// for (int i = 0; i < v.length; ++i)
+// {
+// if (i > 0)
+// b.append(", ");
+// b.append(v[i]);
+// }
+// b.append("]");
+// return b.toString();
+// }
+//
+// /**
+// * Returns a String representation of the argument array. Returns "null"
+// * if <code>a</code> is null.
+// * @param v the array to represent
+// * @return a String representing this array
+// * @since 1.5
+// */
+// public static String toString(short[] v)
+// {
+// if (v == null)
+// return "null";
+// CPStringBuilder b = new CPStringBuilder("[");
+// for (int i = 0; i < v.length; ++i)
+// {
+// if (i > 0)
+// b.append(", ");
+// b.append(v[i]);
+// }
+// b.append("]");
+// return b.toString();
+// }
+//
+// /**
+// * Returns a String representation of the argument array. Returns "null"
+// * if <code>a</code> is null.
+// * @param v the array to represent
+// * @return a String representing this array
+// * @since 1.5
+// */
+// public static String toString(int[] v)
+// {
+// if (v == null)
+// return "null";
+// CPStringBuilder b = new CPStringBuilder("[");
+// for (int i = 0; i < v.length; ++i)
+// {
+// if (i > 0)
+// b.append(", ");
+// b.append(v[i]);
+// }
+// b.append("]");
+// return b.toString();
+// }
+//
+// /**
+// * Returns a String representation of the argument array. Returns "null"
+// * if <code>a</code> is null.
+// * @param v the array to represent
+// * @return a String representing this array
+// * @since 1.5
+// */
+// public static String toString(long[] v)
+// {
+// if (v == null)
+// return "null";
+// CPStringBuilder b = new CPStringBuilder("[");
+// for (int i = 0; i < v.length; ++i)
+// {
+// if (i > 0)
+// b.append(", ");
+// b.append(v[i]);
+// }
+// b.append("]");
+// return b.toString();
+// }
+//
+// /**
+// * Returns a String representation of the argument array. Returns "null"
+// * if <code>a</code> is null.
+// * @param v the array to represent
+// * @return a String representing this array
+// * @since 1.5
+// */
+// public static String toString(float[] v)
+// {
+// if (v == null)
+// return "null";
+// CPStringBuilder b = new CPStringBuilder("[");
+// for (int i = 0; i < v.length; ++i)
+// {
+// if (i > 0)
+// b.append(", ");
+// b.append(v[i]);
+// }
+// b.append("]");
+// return b.toString();
+// }
+//
+// /**
+// * Returns a String representation of the argument array. Returns "null"
+// * if <code>a</code> is null.
+// * @param v the array to represent
+// * @return a String representing this array
+// * @since 1.5
+// */
+// public static String toString(double[] v)
+// {
+// if (v == null)
+// return "null";
+// CPStringBuilder b = new CPStringBuilder("[");
+// for (int i = 0; i < v.length; ++i)
+// {
+// if (i > 0)
+// b.append(", ");
+// b.append(v[i]);
+// }
+// b.append("]");
+// return b.toString();
+// }
+//
+// /**
+// * Returns a String representation of the argument array. Returns "null"
+// * if <code>a</code> is null.
+// * @param v the array to represent
+// * @return a String representing this array
+// * @since 1.5
+// */
+// public static String toString(Object[] v)
+// {
+// if (v == null)
+// return "null";
+// CPStringBuilder b = new CPStringBuilder("[");
+// for (int i = 0; i < v.length; ++i)
+// {
+// if (i > 0)
+// b.append(", ");
+// b.append(v[i]);
+// }
+// b.append("]");
+// return b.toString();
+// }
+//
+// private static void deepToString(Object[] v, CPStringBuilder b, HashSet seen)
+// {
+// b.append("[");
+// for (int i = 0; i < v.length; ++i)
+// {
+// if (i > 0)
+// b.append(", ");
+// Object elt = v[i];
+// if (elt == null)
+// b.append("null");
+// else if (elt instanceof boolean[])
+// b.append(toString((boolean[]) elt));
+// else if (elt instanceof byte[])
+// b.append(toString((byte[]) elt));
+// else if (elt instanceof char[])
+// b.append(toString((char[]) elt));
+// else if (elt instanceof short[])
+// b.append(toString((short[]) elt));
+// else if (elt instanceof int[])
+// b.append(toString((int[]) elt));
+// else if (elt instanceof long[])
+// b.append(toString((long[]) elt));
+// else if (elt instanceof float[])
+// b.append(toString((float[]) elt));
+// else if (elt instanceof double[])
+// b.append(toString((double[]) elt));
+// else if (elt instanceof Object[])
+// {
+// Object[] os = (Object[]) elt;
+// if (seen.contains(os))
+// b.append("[...]");
+// else
+// {
+// seen.add(os);
+// deepToString(os, b, seen);
+// }
+// }
+// else
+// b.append(elt);
+// }
+// b.append("]");
+// }
+//
+// /** @since 1.5 */
+// public static String deepToString(Object[] v)
+// {
+// if (v == null)
+// return "null";
+// HashSet seen = new HashSet();
+// CPStringBuilder b = new CPStringBuilder();
+// deepToString(v, b, seen);
+// return b.toString();
+// }
/**
* Inner class used by {@link #asList(Object[])} to provide a list interface
* @author Eric Blake (ebb9@email.byu.edu)
* @status updated to 1.4
*/
- private static final class ArrayList<E> extends AbstractList<E>
- implements Serializable, RandomAccess
+ private static final class ArrayList/*<E>*/ extends AbstractList/*<E>*/
+ implements Serializable//, RandomAccess
{
// We override the necessary methods, plus others which will be much
// more efficient with direct iteration rather than relying on iterator().
* The array we are viewing.
* @serial the array
*/
- private final E[] a;
+ private final Object/*E*/[] a;
/**
* Construct a list view of the array.
* @param a the array to view
* @throws NullPointerException if a is null
*/
- ArrayList(E[] a)
+ ArrayList(Object/*E*/[] a)
{
// We have to explicitly check.
if (a == null)
* @param index The index to retrieve an object from.
* @return The object at the array index specified.
*/
- public E get(int index)
+ public Object/*E*/ get(int index)
{
return a[index];
}
* @param element The new object.
* @return The object replaced by this operation.
*/
- public E set(int index, E element)
+ public Object/*E*/ set(int index, Object/*E*/ element)
{
E old = a[index];
a[index] = element;
* @return The array containing the objects in this list,
* which may or may not be == to array.
*/
- public <T> T[] toArray(T[] array)
+ public /*<T> T*/Object[] toArray(Objkect/*T*/[] array)
{
int size = a.length;
if (array.length < size)
- array = (T[]) Array.newInstance(array.getClass().getComponentType(),
- size);
+ array = new Object[size];//(T[]) Array.newInstance(array.getClass().getComponentType(),
+ // size);
else if (array.length > size)
array[size] = null;
System.arraycopy(a, 0, array, 0, size);
return array;
}
+
+ List/*<E>*/ subList(int fromIndex, int toIndex) {
+ Object[] sl = new Object[toIndex-fromIndex];
+ for(int i = 0 ; i < sl.length; i++) {
+ sl[i] = a[fromIndex+1];
+ }
+ return new Arrays.ArrayList(sl);
+ }
}
/**
* @since 1.6
* @see #copyOfRange(boolean[],int,int)
*/
- public static boolean[] copyOf(boolean[] original, int newLength)
- {
- if (newLength < 0)
- throw new NegativeArraySizeException("The array size is negative.");
- return copyOfRange(original, 0, newLength);
- }
-
- /**
- * Copies the specified range of the supplied array to a new
- * array, padding as necessary with <code>false</code>
- * if <code>to</code> is greater than the length of the original
- * array. <code>from</code> must be in the range zero to
- * <code>original.length</code> and can not be greater than
- * <code>to</code>. The initial element of the
- * returned array will be equal to <code>original[from]</code>,
- * except where <code>from</code> is equal to <code>to</code>
- * (where a zero-length array will be returned) or <code>
- * <code>from</code> is equal to <code>original.length</code>
- * (where an array padded with <code>false</code> will be
- * returned). The returned array is always of length
- * <code>to - from</code>.
- *
- * @param original the array from which to copy.
- * @param from the initial index of the range, inclusive.
- * @param to the final index of the range, exclusive.
- * @return a copy of the specified range, with padding to
- * obtain the required length.
- * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
- * or <code>from > original.length</code>
- * @throws IllegalArgumentException if <code>from > to</code>
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOf(boolean[],int)
- */
- public static boolean[] copyOfRange(boolean[] original, int from, int to)
- {
- if (from > to)
- throw new IllegalArgumentException("The initial index is after " +
- "the final index.");
- boolean[] newArray = new boolean[to - from];
- if (to > original.length)
- {
- System.arraycopy(original, from, newArray, 0,
- original.length - from);
- fill(newArray, original.length, newArray.length, false);
- }
- else
- System.arraycopy(original, from, newArray, 0, to - from);
- return newArray;
- }
-
- /**
- * Returns a copy of the supplied array, truncating or padding as
- * necessary with <code>(byte)0</code> to obtain the specified length.
- * Indices that are valid for both arrays will return the same value.
- * Indices that only exist in the returned array (due to the new length
- * being greater than the original length) will return <code>(byte)0</code>.
- * This is equivalent to calling
- * <code>copyOfRange(original, 0, newLength)</code>.
- *
- * @param original the original array to be copied.
- * @param newLength the length of the returned array.
- * @return a copy of the original array, truncated or padded with
- * <code>(byte)0</code> to obtain the required length.
- * @throws NegativeArraySizeException if <code>newLength</code> is negative.
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOfRange(byte[],int,int)
- */
- public static byte[] copyOf(byte[] original, int newLength)
- {
- if (newLength < 0)
- throw new NegativeArraySizeException("The array size is negative.");
- return copyOfRange(original, 0, newLength);
- }
-
- /**
- * Copies the specified range of the supplied array to a new
- * array, padding as necessary with <code>(byte)0</code>
- * if <code>to</code> is greater than the length of the original
- * array. <code>from</code> must be in the range zero to
- * <code>original.length</code> and can not be greater than
- * <code>to</code>. The initial element of the
- * returned array will be equal to <code>original[from]</code>,
- * except where <code>from</code> is equal to <code>to</code>
- * (where a zero-length array will be returned) or <code>
- * <code>from</code> is equal to <code>original.length</code>
- * (where an array padded with <code>(byte)0</code> will be
- * returned). The returned array is always of length
- * <code>to - from</code>.
- *
- * @param original the array from which to copy.
- * @param from the initial index of the range, inclusive.
- * @param to the final index of the range, exclusive.
- * @return a copy of the specified range, with padding to
- * obtain the required length.
- * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
- * or <code>from > original.length</code>
- * @throws IllegalArgumentException if <code>from > to</code>
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOf(byte[],int)
- */
- public static byte[] copyOfRange(byte[] original, int from, int to)
- {
- if (from > to)
- throw new IllegalArgumentException("The initial index is after " +
- "the final index.");
- byte[] newArray = new byte[to - from];
- if (to > original.length)
- {
- System.arraycopy(original, from, newArray, 0,
- original.length - from);
- fill(newArray, original.length, newArray.length, (byte)0);
- }
- else
- System.arraycopy(original, from, newArray, 0, to - from);
- return newArray;
- }
-
- /**
- * Returns a copy of the supplied array, truncating or padding as
- * necessary with <code>'\0'</code> to obtain the specified length.
- * Indices that are valid for both arrays will return the same value.
- * Indices that only exist in the returned array (due to the new length
- * being greater than the original length) will return <code>'\0'</code>.
- * This is equivalent to calling
- * <code>copyOfRange(original, 0, newLength)</code>.
- *
- * @param original the original array to be copied.
- * @param newLength the length of the returned array.
- * @return a copy of the original array, truncated or padded with
- * <code>'\0'</code> to obtain the required length.
- * @throws NegativeArraySizeException if <code>newLength</code> is negative.
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOfRange(char[],int,int)
- */
- public static char[] copyOf(char[] original, int newLength)
- {
- if (newLength < 0)
- throw new NegativeArraySizeException("The array size is negative.");
- return copyOfRange(original, 0, newLength);
- }
-
- /**
- * Copies the specified range of the supplied array to a new
- * array, padding as necessary with <code>'\0'</code>
- * if <code>to</code> is greater than the length of the original
- * array. <code>from</code> must be in the range zero to
- * <code>original.length</code> and can not be greater than
- * <code>to</code>. The initial element of the
- * returned array will be equal to <code>original[from]</code>,
- * except where <code>from</code> is equal to <code>to</code>
- * (where a zero-length array will be returned) or <code>
- * <code>from</code> is equal to <code>original.length</code>
- * (where an array padded with <code>'\0'</code> will be
- * returned). The returned array is always of length
- * <code>to - from</code>.
- *
- * @param original the array from which to copy.
- * @param from the initial index of the range, inclusive.
- * @param to the final index of the range, exclusive.
- * @return a copy of the specified range, with padding to
- * obtain the required length.
- * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
- * or <code>from > original.length</code>
- * @throws IllegalArgumentException if <code>from > to</code>
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOf(char[],int)
- */
- public static char[] copyOfRange(char[] original, int from, int to)
- {
- if (from > to)
- throw new IllegalArgumentException("The initial index is after " +
- "the final index.");
- char[] newArray = new char[to - from];
- if (to > original.length)
- {
- System.arraycopy(original, from, newArray, 0,
- original.length - from);
- fill(newArray, original.length, newArray.length, '\0');
- }
- else
- System.arraycopy(original, from, newArray, 0, to - from);
- return newArray;
- }
-
- /**
- * Returns a copy of the supplied array, truncating or padding as
- * necessary with <code>0d</code> to obtain the specified length.
- * Indices that are valid for both arrays will return the same value.
- * Indices that only exist in the returned array (due to the new length
- * being greater than the original length) will return <code>0d</code>.
- * This is equivalent to calling
- * <code>copyOfRange(original, 0, newLength)</code>.
- *
- * @param original the original array to be copied.
- * @param newLength the length of the returned array.
- * @return a copy of the original array, truncated or padded with
- * <code>0d</code> to obtain the required length.
- * @throws NegativeArraySizeException if <code>newLength</code> is negative.
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOfRange(double[],int,int)
- */
- public static double[] copyOf(double[] original, int newLength)
- {
- if (newLength < 0)
- throw new NegativeArraySizeException("The array size is negative.");
- return copyOfRange(original, 0, newLength);
- }
-
- /**
- * Copies the specified range of the supplied array to a new
- * array, padding as necessary with <code>0d</code>
- * if <code>to</code> is greater than the length of the original
- * array. <code>from</code> must be in the range zero to
- * <code>original.length</code> and can not be greater than
- * <code>to</code>. The initial element of the
- * returned array will be equal to <code>original[from]</code>,
- * except where <code>from</code> is equal to <code>to</code>
- * (where a zero-length array will be returned) or <code>
- * <code>from</code> is equal to <code>original.length</code>
- * (where an array padded with <code>0d</code> will be
- * returned). The returned array is always of length
- * <code>to - from</code>.
- *
- * @param original the array from which to copy.
- * @param from the initial index of the range, inclusive.
- * @param to the final index of the range, exclusive.
- * @return a copy of the specified range, with padding to
- * obtain the required length.
- * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
- * or <code>from > original.length</code>
- * @throws IllegalArgumentException if <code>from > to</code>
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOf(double[],int)
- */
- public static double[] copyOfRange(double[] original, int from, int to)
- {
- if (from > to)
- throw new IllegalArgumentException("The initial index is after " +
- "the final index.");
- double[] newArray = new double[to - from];
- if (to > original.length)
- {
- System.arraycopy(original, from, newArray, 0,
- original.length - from);
- fill(newArray, original.length, newArray.length, 0d);
- }
- else
- System.arraycopy(original, from, newArray, 0, to - from);
- return newArray;
- }
-
- /**
- * Returns a copy of the supplied array, truncating or padding as
- * necessary with <code>0f</code> to obtain the specified length.
- * Indices that are valid for both arrays will return the same value.
- * Indices that only exist in the returned array (due to the new length
- * being greater than the original length) will return <code>0f</code>.
- * This is equivalent to calling
- * <code>copyOfRange(original, 0, newLength)</code>.
- *
- * @param original the original array to be copied.
- * @param newLength the length of the returned array.
- * @return a copy of the original array, truncated or padded with
- * <code>0f</code> to obtain the required length.
- * @throws NegativeArraySizeException if <code>newLength</code> is negative.
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOfRange(float[],int,int)
- */
- public static float[] copyOf(float[] original, int newLength)
- {
- if (newLength < 0)
- throw new NegativeArraySizeException("The array size is negative.");
- return copyOfRange(original, 0, newLength);
- }
-
- /**
- * Copies the specified range of the supplied array to a new
- * array, padding as necessary with <code>0f</code>
- * if <code>to</code> is greater than the length of the original
- * array. <code>from</code> must be in the range zero to
- * <code>original.length</code> and can not be greater than
- * <code>to</code>. The initial element of the
- * returned array will be equal to <code>original[from]</code>,
- * except where <code>from</code> is equal to <code>to</code>
- * (where a zero-length array will be returned) or <code>
- * <code>from</code> is equal to <code>original.length</code>
- * (where an array padded with <code>0f</code> will be
- * returned). The returned array is always of length
- * <code>to - from</code>.
- *
- * @param original the array from which to copy.
- * @param from the initial index of the range, inclusive.
- * @param to the final index of the range, exclusive.
- * @return a copy of the specified range, with padding to
- * obtain the required length.
- * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
- * or <code>from > original.length</code>
- * @throws IllegalArgumentException if <code>from > to</code>
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOf(float[],int)
- */
- public static float[] copyOfRange(float[] original, int from, int to)
- {
- if (from > to)
- throw new IllegalArgumentException("The initial index is after " +
- "the final index.");
- float[] newArray = new float[to - from];
- if (to > original.length)
- {
- System.arraycopy(original, from, newArray, 0,
- original.length - from);
- fill(newArray, original.length, newArray.length, 0f);
- }
- else
- System.arraycopy(original, from, newArray, 0, to - from);
- return newArray;
- }
-
- /**
- * Returns a copy of the supplied array, truncating or padding as
- * necessary with <code>0</code> to obtain the specified length.
- * Indices that are valid for both arrays will return the same value.
- * Indices that only exist in the returned array (due to the new length
- * being greater than the original length) will return <code>0</code>.
- * This is equivalent to calling
- * <code>copyOfRange(original, 0, newLength)</code>.
- *
- * @param original the original array to be copied.
- * @param newLength the length of the returned array.
- * @return a copy of the original array, truncated or padded with
- * <code>0</code> to obtain the required length.
- * @throws NegativeArraySizeException if <code>newLength</code> is negative.
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOfRange(int[],int,int)
- */
- public static int[] copyOf(int[] original, int newLength)
- {
- if (newLength < 0)
- throw new NegativeArraySizeException("The array size is negative.");
- return copyOfRange(original, 0, newLength);
- }
-
- /**
- * Copies the specified range of the supplied array to a new
- * array, padding as necessary with <code>0</code>
- * if <code>to</code> is greater than the length of the original
- * array. <code>from</code> must be in the range zero to
- * <code>original.length</code> and can not be greater than
- * <code>to</code>. The initial element of the
- * returned array will be equal to <code>original[from]</code>,
- * except where <code>from</code> is equal to <code>to</code>
- * (where a zero-length array will be returned) or <code>
- * <code>from</code> is equal to <code>original.length</code>
- * (where an array padded with <code>0</code> will be
- * returned). The returned array is always of length
- * <code>to - from</code>.
- *
- * @param original the array from which to copy.
- * @param from the initial index of the range, inclusive.
- * @param to the final index of the range, exclusive.
- * @return a copy of the specified range, with padding to
- * obtain the required length.
- * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
- * or <code>from > original.length</code>
- * @throws IllegalArgumentException if <code>from > to</code>
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOf(int[],int)
- */
- public static int[] copyOfRange(int[] original, int from, int to)
- {
- if (from > to)
- throw new IllegalArgumentException("The initial index is after " +
- "the final index.");
- int[] newArray = new int[to - from];
- if (to > original.length)
- {
- System.arraycopy(original, from, newArray, 0,
- original.length - from);
- fill(newArray, original.length, newArray.length, 0);
- }
- else
- System.arraycopy(original, from, newArray, 0, to - from);
- return newArray;
- }
-
- /**
- * Returns a copy of the supplied array, truncating or padding as
- * necessary with <code>0L</code> to obtain the specified length.
- * Indices that are valid for both arrays will return the same value.
- * Indices that only exist in the returned array (due to the new length
- * being greater than the original length) will return <code>0L</code>.
- * This is equivalent to calling
- * <code>copyOfRange(original, 0, newLength)</code>.
- *
- * @param original the original array to be copied.
- * @param newLength the length of the returned array.
- * @return a copy of the original array, truncated or padded with
- * <code>0L</code> to obtain the required length.
- * @throws NegativeArraySizeException if <code>newLength</code> is negative.
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOfRange(long[],int,int)
- */
- public static long[] copyOf(long[] original, int newLength)
- {
- if (newLength < 0)
- throw new NegativeArraySizeException("The array size is negative.");
- return copyOfRange(original, 0, newLength);
- }
-
- /**
- * Copies the specified range of the supplied array to a new
- * array, padding as necessary with <code>0L</code>
- * if <code>to</code> is greater than the length of the original
- * array. <code>from</code> must be in the range zero to
- * <code>original.length</code> and can not be greater than
- * <code>to</code>. The initial element of the
- * returned array will be equal to <code>original[from]</code>,
- * except where <code>from</code> is equal to <code>to</code>
- * (where a zero-length array will be returned) or <code>
- * <code>from</code> is equal to <code>original.length</code>
- * (where an array padded with <code>0L</code> will be
- * returned). The returned array is always of length
- * <code>to - from</code>.
- *
- * @param original the array from which to copy.
- * @param from the initial index of the range, inclusive.
- * @param to the final index of the range, exclusive.
- * @return a copy of the specified range, with padding to
- * obtain the required length.
- * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
- * or <code>from > original.length</code>
- * @throws IllegalArgumentException if <code>from > to</code>
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOf(long[],int)
- */
- public static long[] copyOfRange(long[] original, int from, int to)
- {
- if (from > to)
- throw new IllegalArgumentException("The initial index is after " +
- "the final index.");
- long[] newArray = new long[to - from];
- if (to > original.length)
- {
- System.arraycopy(original, from, newArray, 0,
- original.length - from);
- fill(newArray, original.length, newArray.length, 0L);
- }
- else
- System.arraycopy(original, from, newArray, 0, to - from);
- return newArray;
- }
-
- /**
- * Returns a copy of the supplied array, truncating or padding as
- * necessary with <code>(short)0</code> to obtain the specified length.
- * Indices that are valid for both arrays will return the same value.
- * Indices that only exist in the returned array (due to the new length
- * being greater than the original length) will return <code>(short)0</code>.
- * This is equivalent to calling
- * <code>copyOfRange(original, 0, newLength)</code>.
- *
- * @param original the original array to be copied.
- * @param newLength the length of the returned array.
- * @return a copy of the original array, truncated or padded with
- * <code>(short)0</code> to obtain the required length.
- * @throws NegativeArraySizeException if <code>newLength</code> is negative.
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOfRange(short[],int,int)
- */
- public static short[] copyOf(short[] original, int newLength)
- {
- if (newLength < 0)
- throw new NegativeArraySizeException("The array size is negative.");
- return copyOfRange(original, 0, newLength);
- }
-
- /**
- * Copies the specified range of the supplied array to a new
- * array, padding as necessary with <code>(short)0</code>
- * if <code>to</code> is greater than the length of the original
- * array. <code>from</code> must be in the range zero to
- * <code>original.length</code> and can not be greater than
- * <code>to</code>. The initial element of the
- * returned array will be equal to <code>original[from]</code>,
- * except where <code>from</code> is equal to <code>to</code>
- * (where a zero-length array will be returned) or <code>
- * <code>from</code> is equal to <code>original.length</code>
- * (where an array padded with <code>(short)0</code> will be
- * returned). The returned array is always of length
- * <code>to - from</code>.
- *
- * @param original the array from which to copy.
- * @param from the initial index of the range, inclusive.
- * @param to the final index of the range, exclusive.
- * @return a copy of the specified range, with padding to
- * obtain the required length.
- * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
- * or <code>from > original.length</code>
- * @throws IllegalArgumentException if <code>from > to</code>
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOf(short[],int)
- */
- public static short[] copyOfRange(short[] original, int from, int to)
- {
- if (from > to)
- throw new IllegalArgumentException("The initial index is after " +
- "the final index.");
- short[] newArray = new short[to - from];
- if (to > original.length)
- {
- System.arraycopy(original, from, newArray, 0,
- original.length - from);
- fill(newArray, original.length, newArray.length, (short)0);
- }
- else
- System.arraycopy(original, from, newArray, 0, to - from);
- return newArray;
- }
-
- /**
- * Returns a copy of the supplied array, truncating or padding as
- * necessary with <code>null</code> to obtain the specified length.
- * Indices that are valid for both arrays will return the same value.
- * Indices that only exist in the returned array (due to the new length
- * being greater than the original length) will return <code>null</code>.
- * This is equivalent to calling
- * <code>copyOfRange(original, 0, newLength)</code>.
- *
- * @param original the original array to be copied.
- * @param newLength the length of the returned array.
- * @return a copy of the original array, truncated or padded with
- * <code>null</code> to obtain the required length.
- * @throws NegativeArraySizeException if <code>newLength</code> is negative.
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOfRange(T[],int,int)
- */
- public static <T> T[] copyOf(T[] original, int newLength)
- {
- if (newLength < 0)
- throw new NegativeArraySizeException("The array size is negative.");
- return copyOfRange(original, 0, newLength);
- }
-
- /**
- * Copies the specified range of the supplied array to a new
- * array, padding as necessary with <code>null</code>
- * if <code>to</code> is greater than the length of the original
- * array. <code>from</code> must be in the range zero to
- * <code>original.length</code> and can not be greater than
- * <code>to</code>. The initial element of the
- * returned array will be equal to <code>original[from]</code>,
- * except where <code>from</code> is equal to <code>to</code>
- * (where a zero-length array will be returned) or <code>
- * <code>from</code> is equal to <code>original.length</code>
- * (where an array padded with <code>null</code> will be
- * returned). The returned array is always of length
- * <code>to - from</code>.
- *
- * @param original the array from which to copy.
- * @param from the initial index of the range, inclusive.
- * @param to the final index of the range, exclusive.
- * @return a copy of the specified range, with padding to
- * obtain the required length.
- * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
- * or <code>from > original.length</code>
- * @throws IllegalArgumentException if <code>from > to</code>
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOf(T[],int)
- */
- public static <T> T[] copyOfRange(T[] original, int from, int to)
- {
- if (from > to)
- throw new IllegalArgumentException("The initial index is after " +
- "the final index.");
- Class elemType = original.getClass().getComponentType();
- T[] newArray = (T[]) Array.newInstance(elemType, to - from);
- if (to > original.length)
- {
- System.arraycopy(original, from, newArray, 0,
- original.length - from);
- fill(newArray, original.length, newArray.length, null);
- }
- else
- System.arraycopy(original, from, newArray, 0, to - from);
- return newArray;
- }
-
- /**
- * Returns a copy of the supplied array, truncating or padding as
- * necessary with <code>null</code> to obtain the specified length.
- * Indices that are valid for both arrays will return the same value.
- * Indices that only exist in the returned array (due to the new length
- * being greater than the original length) will return <code>null</code>.
- * This is equivalent to calling
- * <code>copyOfRange(original, 0, newLength, newType)</code>. The returned
- * array will be of the specified type, <code>newType</code>.
- *
- * @param original the original array to be copied.
- * @param newLength the length of the returned array.
- * @param newType the type of the returned array.
- * @return a copy of the original array, truncated or padded with
- * <code>null</code> to obtain the required length.
- * @throws NegativeArraySizeException if <code>newLength</code> is negative.
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOfRange(U[],int,int,Class)
- */
- public static <T,U> T[] copyOf(U[] original, int newLength,
- Class<? extends T[]> newType)
- {
- if (newLength < 0)
- throw new NegativeArraySizeException("The array size is negative.");
- return copyOfRange(original, 0, newLength, newType);
- }
-
- /**
- * Copies the specified range of the supplied array to a new
- * array, padding as necessary with <code>null</code>
- * if <code>to</code> is greater than the length of the original
- * array. <code>from</code> must be in the range zero to
- * <code>original.length</code> and can not be greater than
- * <code>to</code>. The initial element of the
- * returned array will be equal to <code>original[from]</code>,
- * except where <code>from</code> is equal to <code>to</code>
- * (where a zero-length array will be returned) or <code>
- * <code>from</code> is equal to <code>original.length</code>
- * (where an array padded with <code>null</code> will be
- * returned). The returned array is always of length
- * <code>to - from</code> and will be of the specified type,
- * <code>newType</code>.
- *
- * @param original the array from which to copy.
- * @param from the initial index of the range, inclusive.
- * @param to the final index of the range, exclusive.
- * @param newType the type of the returned array.
- * @return a copy of the specified range, with padding to
- * obtain the required length.
- * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
- * or <code>from > original.length</code>
- * @throws IllegalArgumentException if <code>from > to</code>
- * @throws NullPointerException if <code>original</code> is <code>null</code>.
- * @since 1.6
- * @see #copyOf(T[],int)
- */
- public static <T,U> T[] copyOfRange(U[] original, int from, int to,
- Class<? extends T[]> newType)
- {
- if (from > to)
- throw new IllegalArgumentException("The initial index is after " +
- "the final index.");
- T[] newArray = (T[]) Array.newInstance(newType.getComponentType(),
- to - from);
- if (to > original.length)
- {
- System.arraycopy(original, from, newArray, 0,
- original.length - from);
- fill(newArray, original.length, newArray.length, null);
- }
- else
- System.arraycopy(original, from, newArray, 0, to - from);
- return newArray;
- }
+// public static boolean[] copyOf(boolean[] original, int newLength)
+// {
+// if (newLength < 0)
+// throw new NegativeArraySizeException("The array size is negative.");
+// return copyOfRange(original, 0, newLength);
+// }
+//
+// /**
+// * Copies the specified range of the supplied array to a new
+// * array, padding as necessary with <code>false</code>
+// * if <code>to</code> is greater than the length of the original
+// * array. <code>from</code> must be in the range zero to
+// * <code>original.length</code> and can not be greater than
+// * <code>to</code>. The initial element of the
+// * returned array will be equal to <code>original[from]</code>,
+// * except where <code>from</code> is equal to <code>to</code>
+// * (where a zero-length array will be returned) or <code>
+// * <code>from</code> is equal to <code>original.length</code>
+// * (where an array padded with <code>false</code> will be
+// * returned). The returned array is always of length
+// * <code>to - from</code>.
+// *
+// * @param original the array from which to copy.
+// * @param from the initial index of the range, inclusive.
+// * @param to the final index of the range, exclusive.
+// * @return a copy of the specified range, with padding to
+// * obtain the required length.
+// * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
+// * or <code>from > original.length</code>
+// * @throws IllegalArgumentException if <code>from > to</code>
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOf(boolean[],int)
+// */
+// public static boolean[] copyOfRange(boolean[] original, int from, int to)
+// {
+// if (from > to)
+// throw new IllegalArgumentException("The initial index is after " +
+// "the final index.");
+// boolean[] newArray = new boolean[to - from];
+// if (to > original.length)
+// {
+// System.arraycopy(original, from, newArray, 0,
+// original.length - from);
+// fill(newArray, original.length, newArray.length, false);
+// }
+// else
+// System.arraycopy(original, from, newArray, 0, to - from);
+// return newArray;
+// }
+//
+// /**
+// * Returns a copy of the supplied array, truncating or padding as
+// * necessary with <code>(byte)0</code> to obtain the specified length.
+// * Indices that are valid for both arrays will return the same value.
+// * Indices that only exist in the returned array (due to the new length
+// * being greater than the original length) will return <code>(byte)0</code>.
+// * This is equivalent to calling
+// * <code>copyOfRange(original, 0, newLength)</code>.
+// *
+// * @param original the original array to be copied.
+// * @param newLength the length of the returned array.
+// * @return a copy of the original array, truncated or padded with
+// * <code>(byte)0</code> to obtain the required length.
+// * @throws NegativeArraySizeException if <code>newLength</code> is negative.
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOfRange(byte[],int,int)
+// */
+// public static byte[] copyOf(byte[] original, int newLength)
+// {
+// if (newLength < 0)
+// throw new NegativeArraySizeException("The array size is negative.");
+// return copyOfRange(original, 0, newLength);
+// }
+//
+// /**
+// * Copies the specified range of the supplied array to a new
+// * array, padding as necessary with <code>(byte)0</code>
+// * if <code>to</code> is greater than the length of the original
+// * array. <code>from</code> must be in the range zero to
+// * <code>original.length</code> and can not be greater than
+// * <code>to</code>. The initial element of the
+// * returned array will be equal to <code>original[from]</code>,
+// * except where <code>from</code> is equal to <code>to</code>
+// * (where a zero-length array will be returned) or <code>
+// * <code>from</code> is equal to <code>original.length</code>
+// * (where an array padded with <code>(byte)0</code> will be
+// * returned). The returned array is always of length
+// * <code>to - from</code>.
+// *
+// * @param original the array from which to copy.
+// * @param from the initial index of the range, inclusive.
+// * @param to the final index of the range, exclusive.
+// * @return a copy of the specified range, with padding to
+// * obtain the required length.
+// * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
+// * or <code>from > original.length</code>
+// * @throws IllegalArgumentException if <code>from > to</code>
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOf(byte[],int)
+// */
+// public static byte[] copyOfRange(byte[] original, int from, int to)
+// {
+// if (from > to)
+// throw new IllegalArgumentException("The initial index is after " +
+// "the final index.");
+// byte[] newArray = new byte[to - from];
+// if (to > original.length)
+// {
+// System.arraycopy(original, from, newArray, 0,
+// original.length - from);
+// fill(newArray, original.length, newArray.length, (byte)0);
+// }
+// else
+// System.arraycopy(original, from, newArray, 0, to - from);
+// return newArray;
+// }
+//
+// /**
+// * Returns a copy of the supplied array, truncating or padding as
+// * necessary with <code>'\0'</code> to obtain the specified length.
+// * Indices that are valid for both arrays will return the same value.
+// * Indices that only exist in the returned array (due to the new length
+// * being greater than the original length) will return <code>'\0'</code>.
+// * This is equivalent to calling
+// * <code>copyOfRange(original, 0, newLength)</code>.
+// *
+// * @param original the original array to be copied.
+// * @param newLength the length of the returned array.
+// * @return a copy of the original array, truncated or padded with
+// * <code>'\0'</code> to obtain the required length.
+// * @throws NegativeArraySizeException if <code>newLength</code> is negative.
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOfRange(char[],int,int)
+// */
+// public static char[] copyOf(char[] original, int newLength)
+// {
+// if (newLength < 0)
+// throw new NegativeArraySizeException("The array size is negative.");
+// return copyOfRange(original, 0, newLength);
+// }
+//
+// /**
+// * Copies the specified range of the supplied array to a new
+// * array, padding as necessary with <code>'\0'</code>
+// * if <code>to</code> is greater than the length of the original
+// * array. <code>from</code> must be in the range zero to
+// * <code>original.length</code> and can not be greater than
+// * <code>to</code>. The initial element of the
+// * returned array will be equal to <code>original[from]</code>,
+// * except where <code>from</code> is equal to <code>to</code>
+// * (where a zero-length array will be returned) or <code>
+// * <code>from</code> is equal to <code>original.length</code>
+// * (where an array padded with <code>'\0'</code> will be
+// * returned). The returned array is always of length
+// * <code>to - from</code>.
+// *
+// * @param original the array from which to copy.
+// * @param from the initial index of the range, inclusive.
+// * @param to the final index of the range, exclusive.
+// * @return a copy of the specified range, with padding to
+// * obtain the required length.
+// * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
+// * or <code>from > original.length</code>
+// * @throws IllegalArgumentException if <code>from > to</code>
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOf(char[],int)
+// */
+// public static char[] copyOfRange(char[] original, int from, int to)
+// {
+// if (from > to)
+// throw new IllegalArgumentException("The initial index is after " +
+// "the final index.");
+// char[] newArray = new char[to - from];
+// if (to > original.length)
+// {
+// System.arraycopy(original, from, newArray, 0,
+// original.length - from);
+// fill(newArray, original.length, newArray.length, '\0');
+// }
+// else
+// System.arraycopy(original, from, newArray, 0, to - from);
+// return newArray;
+// }
+//
+// /**
+// * Returns a copy of the supplied array, truncating or padding as
+// * necessary with <code>0d</code> to obtain the specified length.
+// * Indices that are valid for both arrays will return the same value.
+// * Indices that only exist in the returned array (due to the new length
+// * being greater than the original length) will return <code>0d</code>.
+// * This is equivalent to calling
+// * <code>copyOfRange(original, 0, newLength)</code>.
+// *
+// * @param original the original array to be copied.
+// * @param newLength the length of the returned array.
+// * @return a copy of the original array, truncated or padded with
+// * <code>0d</code> to obtain the required length.
+// * @throws NegativeArraySizeException if <code>newLength</code> is negative.
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOfRange(double[],int,int)
+// */
+// public static double[] copyOf(double[] original, int newLength)
+// {
+// if (newLength < 0)
+// throw new NegativeArraySizeException("The array size is negative.");
+// return copyOfRange(original, 0, newLength);
+// }
+//
+// /**
+// * Copies the specified range of the supplied array to a new
+// * array, padding as necessary with <code>0d</code>
+// * if <code>to</code> is greater than the length of the original
+// * array. <code>from</code> must be in the range zero to
+// * <code>original.length</code> and can not be greater than
+// * <code>to</code>. The initial element of the
+// * returned array will be equal to <code>original[from]</code>,
+// * except where <code>from</code> is equal to <code>to</code>
+// * (where a zero-length array will be returned) or <code>
+// * <code>from</code> is equal to <code>original.length</code>
+// * (where an array padded with <code>0d</code> will be
+// * returned). The returned array is always of length
+// * <code>to - from</code>.
+// *
+// * @param original the array from which to copy.
+// * @param from the initial index of the range, inclusive.
+// * @param to the final index of the range, exclusive.
+// * @return a copy of the specified range, with padding to
+// * obtain the required length.
+// * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
+// * or <code>from > original.length</code>
+// * @throws IllegalArgumentException if <code>from > to</code>
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOf(double[],int)
+// */
+// public static double[] copyOfRange(double[] original, int from, int to)
+// {
+// if (from > to)
+// throw new IllegalArgumentException("The initial index is after " +
+// "the final index.");
+// double[] newArray = new double[to - from];
+// if (to > original.length)
+// {
+// System.arraycopy(original, from, newArray, 0,
+// original.length - from);
+// fill(newArray, original.length, newArray.length, 0d);
+// }
+// else
+// System.arraycopy(original, from, newArray, 0, to - from);
+// return newArray;
+// }
+//
+// /**
+// * Returns a copy of the supplied array, truncating or padding as
+// * necessary with <code>0f</code> to obtain the specified length.
+// * Indices that are valid for both arrays will return the same value.
+// * Indices that only exist in the returned array (due to the new length
+// * being greater than the original length) will return <code>0f</code>.
+// * This is equivalent to calling
+// * <code>copyOfRange(original, 0, newLength)</code>.
+// *
+// * @param original the original array to be copied.
+// * @param newLength the length of the returned array.
+// * @return a copy of the original array, truncated or padded with
+// * <code>0f</code> to obtain the required length.
+// * @throws NegativeArraySizeException if <code>newLength</code> is negative.
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOfRange(float[],int,int)
+// */
+// public static float[] copyOf(float[] original, int newLength)
+// {
+// if (newLength < 0)
+// throw new NegativeArraySizeException("The array size is negative.");
+// return copyOfRange(original, 0, newLength);
+// }
+//
+// /**
+// * Copies the specified range of the supplied array to a new
+// * array, padding as necessary with <code>0f</code>
+// * if <code>to</code> is greater than the length of the original
+// * array. <code>from</code> must be in the range zero to
+// * <code>original.length</code> and can not be greater than
+// * <code>to</code>. The initial element of the
+// * returned array will be equal to <code>original[from]</code>,
+// * except where <code>from</code> is equal to <code>to</code>
+// * (where a zero-length array will be returned) or <code>
+// * <code>from</code> is equal to <code>original.length</code>
+// * (where an array padded with <code>0f</code> will be
+// * returned). The returned array is always of length
+// * <code>to - from</code>.
+// *
+// * @param original the array from which to copy.
+// * @param from the initial index of the range, inclusive.
+// * @param to the final index of the range, exclusive.
+// * @return a copy of the specified range, with padding to
+// * obtain the required length.
+// * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
+// * or <code>from > original.length</code>
+// * @throws IllegalArgumentException if <code>from > to</code>
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOf(float[],int)
+// */
+// public static float[] copyOfRange(float[] original, int from, int to)
+// {
+// if (from > to)
+// throw new IllegalArgumentException("The initial index is after " +
+// "the final index.");
+// float[] newArray = new float[to - from];
+// if (to > original.length)
+// {
+// System.arraycopy(original, from, newArray, 0,
+// original.length - from);
+// fill(newArray, original.length, newArray.length, 0f);
+// }
+// else
+// System.arraycopy(original, from, newArray, 0, to - from);
+// return newArray;
+// }
+//
+// /**
+// * Returns a copy of the supplied array, truncating or padding as
+// * necessary with <code>0</code> to obtain the specified length.
+// * Indices that are valid for both arrays will return the same value.
+// * Indices that only exist in the returned array (due to the new length
+// * being greater than the original length) will return <code>0</code>.
+// * This is equivalent to calling
+// * <code>copyOfRange(original, 0, newLength)</code>.
+// *
+// * @param original the original array to be copied.
+// * @param newLength the length of the returned array.
+// * @return a copy of the original array, truncated or padded with
+// * <code>0</code> to obtain the required length.
+// * @throws NegativeArraySizeException if <code>newLength</code> is negative.
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOfRange(int[],int,int)
+// */
+// public static int[] copyOf(int[] original, int newLength)
+// {
+// if (newLength < 0)
+// throw new NegativeArraySizeException("The array size is negative.");
+// return copyOfRange(original, 0, newLength);
+// }
+//
+// /**
+// * Copies the specified range of the supplied array to a new
+// * array, padding as necessary with <code>0</code>
+// * if <code>to</code> is greater than the length of the original
+// * array. <code>from</code> must be in the range zero to
+// * <code>original.length</code> and can not be greater than
+// * <code>to</code>. The initial element of the
+// * returned array will be equal to <code>original[from]</code>,
+// * except where <code>from</code> is equal to <code>to</code>
+// * (where a zero-length array will be returned) or <code>
+// * <code>from</code> is equal to <code>original.length</code>
+// * (where an array padded with <code>0</code> will be
+// * returned). The returned array is always of length
+// * <code>to - from</code>.
+// *
+// * @param original the array from which to copy.
+// * @param from the initial index of the range, inclusive.
+// * @param to the final index of the range, exclusive.
+// * @return a copy of the specified range, with padding to
+// * obtain the required length.
+// * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
+// * or <code>from > original.length</code>
+// * @throws IllegalArgumentException if <code>from > to</code>
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOf(int[],int)
+// */
+// public static int[] copyOfRange(int[] original, int from, int to)
+// {
+// if (from > to)
+// throw new IllegalArgumentException("The initial index is after " +
+// "the final index.");
+// int[] newArray = new int[to - from];
+// if (to > original.length)
+// {
+// System.arraycopy(original, from, newArray, 0,
+// original.length - from);
+// fill(newArray, original.length, newArray.length, 0);
+// }
+// else
+// System.arraycopy(original, from, newArray, 0, to - from);
+// return newArray;
+// }
+//
+// /**
+// * Returns a copy of the supplied array, truncating or padding as
+// * necessary with <code>0L</code> to obtain the specified length.
+// * Indices that are valid for both arrays will return the same value.
+// * Indices that only exist in the returned array (due to the new length
+// * being greater than the original length) will return <code>0L</code>.
+// * This is equivalent to calling
+// * <code>copyOfRange(original, 0, newLength)</code>.
+// *
+// * @param original the original array to be copied.
+// * @param newLength the length of the returned array.
+// * @return a copy of the original array, truncated or padded with
+// * <code>0L</code> to obtain the required length.
+// * @throws NegativeArraySizeException if <code>newLength</code> is negative.
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOfRange(long[],int,int)
+// */
+// public static long[] copyOf(long[] original, int newLength)
+// {
+// if (newLength < 0)
+// throw new NegativeArraySizeException("The array size is negative.");
+// return copyOfRange(original, 0, newLength);
+// }
+//
+// /**
+// * Copies the specified range of the supplied array to a new
+// * array, padding as necessary with <code>0L</code>
+// * if <code>to</code> is greater than the length of the original
+// * array. <code>from</code> must be in the range zero to
+// * <code>original.length</code> and can not be greater than
+// * <code>to</code>. The initial element of the
+// * returned array will be equal to <code>original[from]</code>,
+// * except where <code>from</code> is equal to <code>to</code>
+// * (where a zero-length array will be returned) or <code>
+// * <code>from</code> is equal to <code>original.length</code>
+// * (where an array padded with <code>0L</code> will be
+// * returned). The returned array is always of length
+// * <code>to - from</code>.
+// *
+// * @param original the array from which to copy.
+// * @param from the initial index of the range, inclusive.
+// * @param to the final index of the range, exclusive.
+// * @return a copy of the specified range, with padding to
+// * obtain the required length.
+// * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
+// * or <code>from > original.length</code>
+// * @throws IllegalArgumentException if <code>from > to</code>
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOf(long[],int)
+// */
+// public static long[] copyOfRange(long[] original, int from, int to)
+// {
+// if (from > to)
+// throw new IllegalArgumentException("The initial index is after " +
+// "the final index.");
+// long[] newArray = new long[to - from];
+// if (to > original.length)
+// {
+// System.arraycopy(original, from, newArray, 0,
+// original.length - from);
+// fill(newArray, original.length, newArray.length, 0L);
+// }
+// else
+// System.arraycopy(original, from, newArray, 0, to - from);
+// return newArray;
+// }
+//
+// /**
+// * Returns a copy of the supplied array, truncating or padding as
+// * necessary with <code>(short)0</code> to obtain the specified length.
+// * Indices that are valid for both arrays will return the same value.
+// * Indices that only exist in the returned array (due to the new length
+// * being greater than the original length) will return <code>(short)0</code>.
+// * This is equivalent to calling
+// * <code>copyOfRange(original, 0, newLength)</code>.
+// *
+// * @param original the original array to be copied.
+// * @param newLength the length of the returned array.
+// * @return a copy of the original array, truncated or padded with
+// * <code>(short)0</code> to obtain the required length.
+// * @throws NegativeArraySizeException if <code>newLength</code> is negative.
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOfRange(short[],int,int)
+// */
+// public static short[] copyOf(short[] original, int newLength)
+// {
+// if (newLength < 0)
+// throw new NegativeArraySizeException("The array size is negative.");
+// return copyOfRange(original, 0, newLength);
+// }
+//
+// /**
+// * Copies the specified range of the supplied array to a new
+// * array, padding as necessary with <code>(short)0</code>
+// * if <code>to</code> is greater than the length of the original
+// * array. <code>from</code> must be in the range zero to
+// * <code>original.length</code> and can not be greater than
+// * <code>to</code>. The initial element of the
+// * returned array will be equal to <code>original[from]</code>,
+// * except where <code>from</code> is equal to <code>to</code>
+// * (where a zero-length array will be returned) or <code>
+// * <code>from</code> is equal to <code>original.length</code>
+// * (where an array padded with <code>(short)0</code> will be
+// * returned). The returned array is always of length
+// * <code>to - from</code>.
+// *
+// * @param original the array from which to copy.
+// * @param from the initial index of the range, inclusive.
+// * @param to the final index of the range, exclusive.
+// * @return a copy of the specified range, with padding to
+// * obtain the required length.
+// * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
+// * or <code>from > original.length</code>
+// * @throws IllegalArgumentException if <code>from > to</code>
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOf(short[],int)
+// */
+// public static short[] copyOfRange(short[] original, int from, int to)
+// {
+// if (from > to)
+// throw new IllegalArgumentException("The initial index is after " +
+// "the final index.");
+// short[] newArray = new short[to - from];
+// if (to > original.length)
+// {
+// System.arraycopy(original, from, newArray, 0,
+// original.length - from);
+// fill(newArray, original.length, newArray.length, (short)0);
+// }
+// else
+// System.arraycopy(original, from, newArray, 0, to - from);
+// return newArray;
+// }
+//
+// /**
+// * Returns a copy of the supplied array, truncating or padding as
+// * necessary with <code>null</code> to obtain the specified length.
+// * Indices that are valid for both arrays will return the same value.
+// * Indices that only exist in the returned array (due to the new length
+// * being greater than the original length) will return <code>null</code>.
+// * This is equivalent to calling
+// * <code>copyOfRange(original, 0, newLength)</code>.
+// *
+// * @param original the original array to be copied.
+// * @param newLength the length of the returned array.
+// * @return a copy of the original array, truncated or padded with
+// * <code>null</code> to obtain the required length.
+// * @throws NegativeArraySizeException if <code>newLength</code> is negative.
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOfRange(T[],int,int)
+// */
+// public static <T> T[] copyOf(T[] original, int newLength)
+// {
+// if (newLength < 0)
+// throw new NegativeArraySizeException("The array size is negative.");
+// return copyOfRange(original, 0, newLength);
+// }
+//
+// /**
+// * Copies the specified range of the supplied array to a new
+// * array, padding as necessary with <code>null</code>
+// * if <code>to</code> is greater than the length of the original
+// * array. <code>from</code> must be in the range zero to
+// * <code>original.length</code> and can not be greater than
+// * <code>to</code>. The initial element of the
+// * returned array will be equal to <code>original[from]</code>,
+// * except where <code>from</code> is equal to <code>to</code>
+// * (where a zero-length array will be returned) or <code>
+// * <code>from</code> is equal to <code>original.length</code>
+// * (where an array padded with <code>null</code> will be
+// * returned). The returned array is always of length
+// * <code>to - from</code>.
+// *
+// * @param original the array from which to copy.
+// * @param from the initial index of the range, inclusive.
+// * @param to the final index of the range, exclusive.
+// * @return a copy of the specified range, with padding to
+// * obtain the required length.
+// * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
+// * or <code>from > original.length</code>
+// * @throws IllegalArgumentException if <code>from > to</code>
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOf(T[],int)
+// */
+// public static <T> T[] copyOfRange(T[] original, int from, int to)
+// {
+// if (from > to)
+// throw new IllegalArgumentException("The initial index is after " +
+// "the final index.");
+// Class elemType = original.getClass().getComponentType();
+// T[] newArray = (T[]) Array.newInstance(elemType, to - from);
+// if (to > original.length)
+// {
+// System.arraycopy(original, from, newArray, 0,
+// original.length - from);
+// fill(newArray, original.length, newArray.length, null);
+// }
+// else
+// System.arraycopy(original, from, newArray, 0, to - from);
+// return newArray;
+// }
+//
+// /**
+// * Returns a copy of the supplied array, truncating or padding as
+// * necessary with <code>null</code> to obtain the specified length.
+// * Indices that are valid for both arrays will return the same value.
+// * Indices that only exist in the returned array (due to the new length
+// * being greater than the original length) will return <code>null</code>.
+// * This is equivalent to calling
+// * <code>copyOfRange(original, 0, newLength, newType)</code>. The returned
+// * array will be of the specified type, <code>newType</code>.
+// *
+// * @param original the original array to be copied.
+// * @param newLength the length of the returned array.
+// * @param newType the type of the returned array.
+// * @return a copy of the original array, truncated or padded with
+// * <code>null</code> to obtain the required length.
+// * @throws NegativeArraySizeException if <code>newLength</code> is negative.
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOfRange(U[],int,int,Class)
+// */
+// public static <T,U> T[] copyOf(U[] original, int newLength,
+// Class<? extends T[]> newType)
+// {
+// if (newLength < 0)
+// throw new NegativeArraySizeException("The array size is negative.");
+// return copyOfRange(original, 0, newLength, newType);
+// }
+//
+// /**
+// * Copies the specified range of the supplied array to a new
+// * array, padding as necessary with <code>null</code>
+// * if <code>to</code> is greater than the length of the original
+// * array. <code>from</code> must be in the range zero to
+// * <code>original.length</code> and can not be greater than
+// * <code>to</code>. The initial element of the
+// * returned array will be equal to <code>original[from]</code>,
+// * except where <code>from</code> is equal to <code>to</code>
+// * (where a zero-length array will be returned) or <code>
+// * <code>from</code> is equal to <code>original.length</code>
+// * (where an array padded with <code>null</code> will be
+// * returned). The returned array is always of length
+// * <code>to - from</code> and will be of the specified type,
+// * <code>newType</code>.
+// *
+// * @param original the array from which to copy.
+// * @param from the initial index of the range, inclusive.
+// * @param to the final index of the range, exclusive.
+// * @param newType the type of the returned array.
+// * @return a copy of the specified range, with padding to
+// * obtain the required length.
+// * @throws ArrayIndexOutOfBoundsException if <code>from < 0</code>
+// * or <code>from > original.length</code>
+// * @throws IllegalArgumentException if <code>from > to</code>
+// * @throws NullPointerException if <code>original</code> is <code>null</code>.
+// * @since 1.6
+// * @see #copyOf(T[],int)
+// */
+// public static <T,U> T[] copyOfRange(U[] original, int from, int to,
+// Class<? extends T[]> newType)
+// {
+// if (from > to)
+// throw new IllegalArgumentException("The initial index is after " +
+// "the final index.");
+// T[] newArray = (T[]) Array.newInstance(newType.getComponentType(),
+// to - from);
+// if (to > original.length)
+// {
+// System.arraycopy(original, from, newArray, 0,
+// original.length - from);
+// fill(newArray, original.length, newArray.length, null);
+// }
+// else
+// System.arraycopy(original, from, newArray, 0, to - from);
+// return newArray;
+// }
}
projects / IRC.git / commitdiff