You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by ge...@apache.org on 2005/12/01 07:04:00 UTC
svn commit: r350181 [115/198] - in
/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core: ./ depends/
depends/files/ depends/jars/ depends/libs/ depends/libs/linux.IA32/
depends/libs/win.IA32/ depends/oss/ depends/oss/linux.IA32/
depends/oss/win....
Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Arrays.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Arrays.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Arrays.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/Arrays.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,1926 @@
+/* Copyright 1998, 2005 The Apache Software Foundation or its licensors, as applicable
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+import java.io.Serializable;
+import java.lang.reflect.Array;
+
+/**
+ * Arrays contains static methods which operate on arrays.
+ */
+public class Arrays {
+
+ private static class ArrayList extends AbstractList implements List,
+ Serializable, RandomAccess {
+
+ static final long serialVersionUID = -2764017481108945198L;
+
+ private Object[] a;
+
+ ArrayList(Object[] storage) {
+ if (storage == null) {
+ throw new NullPointerException();
+ }
+ a = storage;
+ }
+
+ public boolean contains(Object object) {
+ if (object != null) {
+ for (int i = 0; i < a.length; i++)
+ if (object.equals(a[i]))
+ return true;
+ } else {
+ for (int i = 0; i < a.length; i++)
+ if (a[i] == null)
+ return true;
+ }
+ return false;
+ }
+
+ public Object get(int location) {
+ try {
+ return a[location];
+ } catch (ArrayIndexOutOfBoundsException e) {
+ throw new IndexOutOfBoundsException();
+ }
+ }
+
+ public int indexOf(Object object) {
+ if (object != null) {
+ for (int i = 0; i < a.length; i++)
+ if (object.equals(a[i]))
+ return i;
+ } else {
+ for (int i = 0; i < a.length; i++)
+ if (a[i] == null)
+ return i;
+ }
+ return -1;
+ }
+
+ public int lastIndexOf(Object object) {
+ if (object != null) {
+ for (int i = a.length - 1; i >= 0; i--)
+ if (object.equals(a[i]))
+ return i;
+ } else {
+ for (int i = a.length - 1; i >= 0; i--)
+ if (a[i] == null)
+ return i;
+ }
+ return -1;
+ }
+
+ public Object set(int location, Object object) {
+ try {
+ Object result = a[location];
+ a[location] = object;
+ return result;
+ } catch (ArrayIndexOutOfBoundsException e) {
+ throw new IndexOutOfBoundsException();
+ } catch (ArrayStoreException e) {
+ throw new ClassCastException();
+ }
+ }
+
+ public int size() {
+ return a.length;
+ }
+
+ public Object[] toArray() {
+ return (Object[]) a.clone();
+ }
+
+ public Object[] toArray(Object[] contents) {
+ int size = size();
+ if (size > contents.length)
+ contents = (Object[]) Array.newInstance(contents.getClass()
+ .getComponentType(), size);
+ System.arraycopy(a, 0, contents, 0, size);
+ if (size < contents.length)
+ contents[size] = null;
+ return contents;
+ }
+ }
+
+ private Arrays() {
+ /*empty*/
+ }
+
+ /**
+ * Answers a List on the objects in the specified array. The size of the
+ * List cannot be modified, i.e. adding and removing are unsupported, but
+ * the elements can be set. Setting an element modifies the underlying
+ * array.
+ *
+ * @param array
+ * the array
+ * @return a List on the specified array
+ */
+ public static List asList(Object[] array) {
+ return new ArrayList(array);
+ }
+
+ /**
+ * Performs a binary search for the specified element in the specified
+ * sorted array.
+ *
+ * @param array
+ * the sorted byte array to search
+ * @param value
+ * the byte element to find
+ * @return the non-negative index of the element, or a negative index which
+ * is the -index - 1 where the element would be inserted
+ */
+ public static int binarySearch(byte[] array, byte value) {
+ int low = 0, mid = -1, high = array.length - 1;
+ while (low <= high) {
+ mid = (low + high) >> 1;
+ if (value > array[mid])
+ low = mid + 1;
+ else if (value == array[mid])
+ return mid;
+ else
+ high = mid - 1;
+ }
+ if (mid < 0)
+ return -1;
+
+ return -mid - (value < array[mid] ? 1 : 2);
+ }
+
+ /**
+ * Performs a binary search for the specified element in the specified
+ * sorted array.
+ *
+ * @param array
+ * the sorted char array to search
+ * @param value
+ * the char element to find
+ * @return the non-negative index of the element, or a negative index which
+ * is the -index - 1 where the element would be inserted
+ */
+ public static int binarySearch(char[] array, char value) {
+ int low = 0, mid = -1, high = array.length - 1;
+ while (low <= high) {
+ mid = (low + high) >> 1;
+ if (value > array[mid])
+ low = mid + 1;
+ else if (value == array[mid])
+ return mid;
+ else
+ high = mid - 1;
+ }
+ if (mid < 0)
+ return -1;
+ return -mid - (value < array[mid] ? 1 : 2);
+ }
+
+ /**
+ * Performs a binary search for the specified element in the specified
+ * sorted array.
+ *
+ * @param array
+ * the sorted double array to search
+ * @param value
+ * the double element to find
+ * @return the non-negative index of the element, or a negative index which
+ * is the -index - 1 where the element would be inserted
+ */
+ public static int binarySearch(double[] array, double value) {
+ int low = 0, mid = -1, high = array.length - 1;
+ while (low <= high) {
+ mid = (low + high) >> 1;
+ if (value > array[mid])
+ low = mid + 1;
+ else if (value == array[mid])
+ return mid;
+ else
+ high = mid - 1;
+ }
+ if (mid < 0)
+ return -1;
+ return -mid - (value < array[mid] ? 1 : 2);
+ }
+
+ /**
+ * Performs a binary search for the specified element in the specified
+ * sorted array.
+ *
+ * @param array
+ * the sorted float array to search
+ * @param value
+ * the float element to find
+ * @return the non-negative index of the element, or a negative index which
+ * is the -index - 1 where the element would be inserted
+ */
+ public static int binarySearch(float[] array, float value) {
+ int low = 0, mid = -1, high = array.length - 1;
+ while (low <= high) {
+ mid = (low + high) >> 1;
+ if (value > array[mid])
+ low = mid + 1;
+ else if (value == array[mid])
+ return mid;
+ else
+ high = mid - 1;
+ }
+ if (mid < 0)
+ return -1;
+ return -mid - (value < array[mid] ? 1 : 2);
+ }
+
+ /**
+ * Performs a binary search for the specified element in the specified
+ * sorted array.
+ *
+ * @param array
+ * the sorted int array to search
+ * @param value
+ * the int element to find
+ * @return the non-negative index of the element, or a negative index which
+ * is the -index - 1 where the element would be inserted
+ */
+ public static int binarySearch(int[] array, int value) {
+ int low = 0, mid = -1, high = array.length - 1;
+ while (low <= high) {
+ mid = (low + high) >> 1;
+ if (value > array[mid])
+ low = mid + 1;
+ else if (value == array[mid])
+ return mid;
+ else
+ high = mid - 1;
+ }
+ if (mid < 0)
+ return -1;
+ return -mid - (value < array[mid] ? 1 : 2);
+ }
+
+ /**
+ * Performs a binary search for the specified element in the specified
+ * sorted array.
+ *
+ * @param array
+ * the sorted long array to search
+ * @param value
+ * the long element to find
+ * @return the non-negative index of the element, or a negative index which
+ * is the -index - 1 where the element would be inserted
+ */
+ public static int binarySearch(long[] array, long value) {
+ int low = 0, mid = -1, high = array.length - 1;
+ while (low <= high) {
+ mid = (low + high) >> 1;
+ if (value > array[mid])
+ low = mid + 1;
+ else if (value == array[mid])
+ return mid;
+ else
+ high = mid - 1;
+ }
+ if (mid < 0)
+ return -1;
+ return -mid - (value < array[mid] ? 1 : 2);
+ }
+
+ /**
+ * Performs a binary search for the specified element in the specified
+ * sorted array.
+ *
+ * @param array
+ * the sorted Object array to search
+ * @param object
+ * the Object element to find
+ * @return the non-negative index of the element, or a negative index which
+ * is the -index - 1 where the element would be inserted
+ *
+ * @exception ClassCastException
+ * when an element in the array or the seach element does not
+ * implement Comparable, or cannot be compared to each other
+ */
+ public static int binarySearch(Object[] array, Object object) {
+ Comparable key = (Comparable) object;
+ int low = 0, mid = 0, high = array.length - 1, result = 0;
+ while (low <= high) {
+ mid = (low + high) >> 1;
+ if ((result = key.compareTo(array[mid])) > 0)
+ low = mid + 1;
+ else if (result == 0)
+ return mid;
+ else
+ high = mid - 1;
+ }
+ return -mid - (result <= 0 ? 1 : 2);
+ }
+
+ /**
+ * Performs a binary search for the specified element in the specified
+ * sorted array using the Comparator to compare elements.
+ *
+ * @param array
+ * the sorted char array to search
+ * @param object
+ * the char element to find
+ * @param comparator
+ * the Comparator
+ * @return the non-negative index of the element, or a negative index which
+ * is the -index - 1 where the element would be inserted
+ *
+ * @exception ClassCastException
+ * when an element in the array and the seach element cannot
+ * be compared to each other using the Comparator
+ */
+ public static int binarySearch(Object[] array, Object object,
+ Comparator comparator) {
+ int low = 0, mid = 0, high = array.length - 1, result = 0;
+ while (low <= high) {
+ mid = (low + high) >> 1;
+ if ((result = comparator.compare(array[mid], object)) < 0)
+ low = mid + 1;
+ else if (result == 0)
+ return mid;
+ else
+ high = mid - 1;
+ }
+ return -mid - (result >= 0 ? 1 : 2);
+ }
+
+ /**
+ * Performs a binary search for the specified element in the specified
+ * sorted array.
+ *
+ * @param array
+ * the sorted short array to search
+ * @param value
+ * the short element to find
+ * @return the non-negative index of the element, or a negative index which
+ * is the -index - 1 where the element would be inserted
+ */
+ public static int binarySearch(short[] array, short value) {
+ int low = 0, mid = -1, high = array.length - 1;
+ while (low <= high) {
+ mid = (low + high) >> 1;
+ if (value > array[mid])
+ low = mid + 1;
+ else if (value == array[mid])
+ return mid;
+ else
+ high = mid - 1;
+ }
+ if (mid < 0)
+ return -1;
+ return -mid - (value < array[mid] ? 1 : 2);
+ }
+
+ /**
+ * Fills the specified array with the specified element.
+ *
+ * @param array
+ * the byte array to fill
+ * @param value
+ * the byte element
+ */
+ public static void fill(byte[] array, byte value) {
+ for (int i = 0; i < array.length; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified range in the array with the specified element.
+ *
+ * @param array
+ * the byte array to fill
+ * @param start
+ * the first index to fill
+ * @param end
+ * the last + 1 index to fill
+ * @param value
+ * the byte element
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void fill(byte[] array, int start, int end, byte value) {
+ // Check for null first
+ int length = array.length;
+ if (start > end)
+ throw new IllegalArgumentException();
+ if (start < 0 || end > length)
+ throw new ArrayIndexOutOfBoundsException();
+ for (int i = start; i < end; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified array with the specified element.
+ *
+ * @param array
+ * the short array to fill
+ * @param value
+ * the short element
+ */
+ public static void fill(short[] array, short value) {
+ for (int i = 0; i < array.length; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified range in the array with the specified element.
+ *
+ * @param array
+ * the short array to fill
+ * @param start
+ * the first index to fill
+ * @param end
+ * the last + 1 index to fill
+ * @param value
+ * the short element
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void fill(short[] array, int start, int end, short value) {
+ // Check for null first
+ int length = array.length;
+ if (start > end)
+ throw new IllegalArgumentException();
+ if (start < 0 || end > length)
+ throw new ArrayIndexOutOfBoundsException();
+ for (int i = start; i < end; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified array with the specified element.
+ *
+ * @param array
+ * the char array to fill
+ * @param value
+ * the char element
+ */
+ public static void fill(char[] array, char value) {
+ for (int i = 0; i < array.length; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified range in the array with the specified element.
+ *
+ * @param array
+ * the char array to fill
+ * @param start
+ * the first index to fill
+ * @param end
+ * the last + 1 index to fill
+ * @param value
+ * the char element
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void fill(char[] array, int start, int end, char value) {
+ // Check for null first
+ int length = array.length;
+ if (start > end)
+ throw new IllegalArgumentException();
+ if (start < 0 || end > length)
+ throw new ArrayIndexOutOfBoundsException();
+ for (int i = start; i < end; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified array with the specified element.
+ *
+ * @param array
+ * the int array to fill
+ * @param value
+ * the int element
+ */
+ public static void fill(int[] array, int value) {
+ for (int i = 0; i < array.length; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified range in the array with the specified element.
+ *
+ * @param array
+ * the int array to fill
+ * @param start
+ * the first index to fill
+ * @param end
+ * the last + 1 index to fill
+ * @param value
+ * the int element
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void fill(int[] array, int start, int end, int value) {
+ // Check for null first
+ int length = array.length;
+ if (start > end)
+ throw new IllegalArgumentException();
+ if (start < 0 || end > length)
+ throw new ArrayIndexOutOfBoundsException();
+ for (int i = start; i < end; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified array with the specified element.
+ *
+ * @param array
+ * the long array to fill
+ * @param value
+ * the long element
+ */
+ public static void fill(long[] array, long value) {
+ for (int i = 0; i < array.length; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified range in the array with the specified element.
+ *
+ * @param array
+ * the long array to fill
+ * @param start
+ * the first index to fill
+ * @param end
+ * the last + 1 index to fill
+ * @param value
+ * the long element
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void fill(long[] array, int start, int end, long value) {
+ // Check for null first
+ int length = array.length;
+ if (start > end)
+ throw new IllegalArgumentException();
+ if (start < 0 || end > length)
+ throw new ArrayIndexOutOfBoundsException();
+ for (int i = start; i < end; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified array with the specified element.
+ *
+ * @param array
+ * the float array to fill
+ * @param value
+ * the float element
+ */
+ public static void fill(float[] array, float value) {
+ for (int i = 0; i < array.length; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified range in the array with the specified element.
+ *
+ * @param array
+ * the float array to fill
+ * @param start
+ * the first index to fill
+ * @param end
+ * the last + 1 index to fill
+ * @param value
+ * the float element
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void fill(float[] array, int start, int end, float value) {
+ // Check for null first
+ int length = array.length;
+ if (start > end)
+ throw new IllegalArgumentException();
+ if (start < 0 || end > length)
+ throw new ArrayIndexOutOfBoundsException();
+ for (int i = start; i < end; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified array with the specified element.
+ *
+ * @param array
+ * the float array to fill
+ * @param value
+ * the float element
+ */
+ public static void fill(double[] array, double value) {
+ for (int i = 0; i < array.length; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified range in the array with the specified element.
+ *
+ * @param array
+ * the double array to fill
+ * @param start
+ * the first index to fill
+ * @param end
+ * the last + 1 index to fill
+ * @param value
+ * the double element
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void fill(double[] array, int start, int end, double value) {
+ // Check for null first
+ int length = array.length;
+ if (start > end)
+ throw new IllegalArgumentException();
+ if (start < 0 || end > length)
+ throw new ArrayIndexOutOfBoundsException();
+ for (int i = start; i < end; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified array with the specified element.
+ *
+ * @param array
+ * the boolean array to fill
+ * @param value
+ * the boolean element
+ */
+ public static void fill(boolean[] array, boolean value) {
+ for (int i = 0; i < array.length; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified range in the array with the specified element.
+ *
+ * @param array
+ * the boolean array to fill
+ * @param start
+ * the first index to fill
+ * @param end
+ * the last + 1 index to fill
+ * @param value
+ * the boolean element
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void fill(boolean[] array, int start, int end, boolean value) {
+ // Check for null first
+ int length = array.length;
+ if (start > end)
+ throw new IllegalArgumentException();
+ if (start < 0 || end > length)
+ throw new ArrayIndexOutOfBoundsException();
+ for (int i = start; i < end; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified array with the specified element.
+ *
+ * @param array
+ * the Object array to fill
+ * @param value
+ * the Object element
+ */
+ public static void fill(Object[] array, Object value) {
+ for (int i = 0; i < array.length; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Fills the specified range in the array with the specified element.
+ *
+ * @param array
+ * the Object array to fill
+ * @param start
+ * the first index to fill
+ * @param end
+ * the last + 1 index to fill
+ * @param value
+ * the Object element
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void fill(Object[] array, int start, int end, Object value) {
+ // Check for null first
+ int length = array.length;
+ if (start > end)
+ throw new IllegalArgumentException();
+ if (start < 0 || end > length)
+ throw new ArrayIndexOutOfBoundsException();
+ for (int i = start; i < end; i++)
+ array[i] = value;
+ }
+
+ /**
+ * Compares the two arrays.
+ *
+ * @param array1
+ * the first byte array
+ * @param array2
+ * the second byte array
+ * @return true when the arrays have the same length and the elements at
+ * each index in the two arrays are equal, false otherwise
+ */
+ public static boolean equals(byte[] array1, byte[] array2) {
+ if (array1 == array2)
+ return true;
+ if (array1 == null || array2 == null || array1.length != array2.length)
+ return false;
+ for (int i = 0; i < array1.length; i++) {
+ if (array1[i] != array2[i])
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Compares the two arrays.
+ *
+ * @param array1
+ * the first short array
+ * @param array2
+ * the second short array
+ * @return true when the arrays have the same length and the elements at
+ * each index in the two arrays are equal, false otherwise
+ */
+ public static boolean equals(short[] array1, short[] array2) {
+ if (array1 == array2)
+ return true;
+ if (array1 == null || array2 == null || array1.length != array2.length)
+ return false;
+ for (int i = 0; i < array1.length; i++) {
+ if (array1[i] != array2[i])
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Compares the two arrays.
+ *
+ * @param array1
+ * the first char array
+ * @param array2
+ * the second char array
+ * @return true when the arrays have the same length and the elements at
+ * each index in the two arrays are equal, false otherwise
+ */
+ public static boolean equals(char[] array1, char[] array2) {
+ if (array1 == array2)
+ return true;
+ if (array1 == null || array2 == null || array1.length != array2.length)
+ return false;
+ for (int i = 0; i < array1.length; i++) {
+ if (array1[i] != array2[i])
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Compares the two arrays.
+ *
+ * @param array1
+ * the first int array
+ * @param array2
+ * the second int array
+ * @return true when the arrays have the same length and the elements at
+ * each index in the two arrays are equal, false otherwise
+ */
+ public static boolean equals(int[] array1, int[] array2) {
+ if (array1 == array2)
+ return true;
+ if (array1 == null || array2 == null || array1.length != array2.length)
+ return false;
+ for (int i = 0; i < array1.length; i++) {
+ if (array1[i] != array2[i])
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Compares the two arrays.
+ *
+ * @param array1
+ * the first long array
+ * @param array2
+ * the second long array
+ * @return true when the arrays have the same length and the elements at
+ * each index in the two arrays are equal, false otherwise
+ */
+ public static boolean equals(long[] array1, long[] array2) {
+ if (array1 == array2)
+ return true;
+ if (array1 == null || array2 == null || array1.length != array2.length)
+ return false;
+ for (int i = 0; i < array1.length; i++) {
+ if (array1[i] != array2[i])
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Compares the two arrays.
+ *
+ * @param array1
+ * the first float array
+ * @param array2
+ * the second float array
+ * @return true when the arrays have the same length and the elements at
+ * each index in the two arrays are equal, false otherwise
+ */
+ public static boolean equals(float[] array1, float[] array2) {
+ if (array1 == array2)
+ return true;
+ if (array1 == null || array2 == null || array1.length != array2.length)
+ return false;
+ for (int i = 0; i < array1.length; i++) {
+ if (array1[i] != array2[i])
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Compares the two arrays.
+ *
+ * @param array1
+ * the first double array
+ * @param array2
+ * the second double array
+ * @return true when the arrays have the same length and the elements at
+ * each index in the two arrays are equal, false otherwise
+ */
+ public static boolean equals(double[] array1, double[] array2) {
+ if (array1 == array2)
+ return true;
+ if (array1 == null || array2 == null || array1.length != array2.length)
+ return false;
+ for (int i = 0; i < array1.length; i++) {
+ if (array1[i] != array2[i])
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Compares the two arrays.
+ *
+ * @param array1
+ * the first boolean array
+ * @param array2
+ * the second boolean array
+ * @return true when the arrays have the same length and the elements at
+ * each index in the two arrays are equal, false otherwise
+ */
+ public static boolean equals(boolean[] array1, boolean[] array2) {
+ if (array1 == array2)
+ return true;
+ if (array1 == null || array2 == null || array1.length != array2.length)
+ return false;
+ for (int i = 0; i < array1.length; i++) {
+ if (array1[i] != array2[i])
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Compares the two arrays.
+ *
+ * @param array1
+ * the first Object array
+ * @param array2
+ * the second Object array
+ * @return true when the arrays have the same length and the elements at
+ * each index in the two arrays are equal, false otherwise
+ */
+ public static boolean equals(Object[] array1, Object[] array2) {
+ if (array1 == array2)
+ return true;
+ if (array1 == null || array2 == null || array1.length != array2.length)
+ return false;
+ for (int i = 0; i < array1.length; i++) {
+ Object e1 = array1[i], e2 = array2[i];
+ if (!(e1 == null ? e2 == null : e1.equals(e2)))
+ return false;
+ }
+ return true;
+ }
+
+ private static int med3(byte[] array, int a, int b, int c) {
+ byte x = array[a], y = array[b], z = array[c];
+ return x < y ? (y < z ? b : (x < z ? c : a)) : (y > z ? b : (x > z ? c
+ : a));
+ }
+
+ private static int med3(char[] array, int a, int b, int c) {
+ char x = array[a], y = array[b], z = array[c];
+ return x < y ? (y < z ? b : (x < z ? c : a)) : (y > z ? b : (x > z ? c
+ : a));
+ }
+
+ private static int med3(double[] array, int a, int b, int c) {
+ double x = array[a], y = array[b], z = array[c];
+ return x < y ? (y < z ? b : (x < z ? c : a)) : (y > z ? b : (x > z ? c
+ : a));
+ }
+
+ private static int med3(float[] array, int a, int b, int c) {
+ float x = array[a], y = array[b], z = array[c];
+ return x < y ? (y < z ? b : (x < z ? c : a)) : (y > z ? b : (x > z ? c
+ : a));
+ }
+
+ private static int med3(int[] array, int a, int b, int c) {
+ int x = array[a], y = array[b], z = array[c];
+ return x < y ? (y < z ? b : (x < z ? c : a)) : (y > z ? b : (x > z ? c
+ : a));
+ }
+
+ private static int med3(long[] array, int a, int b, int c) {
+ long x = array[a], y = array[b], z = array[c];
+ return x < y ? (y < z ? b : (x < z ? c : a)) : (y > z ? b : (x > z ? c
+ : a));
+ }
+
+ private static int med3(short[] array, int a, int b, int c) {
+ short x = array[a], y = array[b], z = array[c];
+ return x < y ? (y < z ? b : (x < z ? c : a)) : (y > z ? b : (x > z ? c
+ : a));
+ }
+
+ /**
+ * Sorts the specified array in ascending order.
+ *
+ * @param array
+ * the byte array to be sorted
+ */
+ public static void sort(byte[] array) {
+ sort(0, array.length, array);
+ }
+
+ /**
+ * Sorts the specified range in the array in ascending order.
+ *
+ * @param array
+ * the byte array to be sorted
+ * @param start
+ * the start index to sort
+ * @param end
+ * the last + 1 index to sort
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void sort(byte[] array, int start, int end) {
+ if (start >= 0 && end <= array.length) {
+ if (start <= end)
+ sort(start, end, array);
+ else
+ throw new IllegalArgumentException();
+ } else
+ throw new ArrayIndexOutOfBoundsException();
+ }
+
+ private static void sort(int start, int end, byte[] array) {
+ byte temp;
+ int length = end - start;
+ if (length < 7) {
+ for (int i = start + 1; i < end; i++)
+ for (int j = i; j > start && array[j - 1] > array[j]; j--) {
+ temp = array[j];
+ array[j] = array[j - 1];
+ array[j - 1] = temp;
+ }
+ return;
+ }
+ int middle = (start + end) / 2;
+ if (length > 7) {
+ int bottom = start;
+ int top = end - 1;
+ if (length > 40) {
+ length /= 8;
+ bottom = med3(array, bottom, bottom + length, bottom
+ + (2 * length));
+ middle = med3(array, middle - length, middle, middle + length);
+ top = med3(array, top - (2 * length), top - length, top);
+ }
+ middle = med3(array, bottom, middle, top);
+ }
+ byte partionValue = array[middle];
+ int a, b, c, d;
+ a = b = start;
+ c = d = end - 1;
+ while (true) {
+ while (b <= c && array[b] <= partionValue) {
+ if (array[b] == partionValue) {
+ temp = array[a];
+ array[a++] = array[b];
+ array[b] = temp;
+ }
+ b++;
+ }
+ while (c >= b && array[c] >= partionValue) {
+ if (array[c] == partionValue) {
+ temp = array[c];
+ array[c] = array[d];
+ array[d--] = temp;
+ }
+ c--;
+ }
+ if (b > c)
+ break;
+ temp = array[b];
+ array[b++] = array[c];
+ array[c--] = temp;
+ }
+ length = a - start < b - a ? a - start : b - a;
+ int l = start;
+ int h = b - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ length = d - c < end - 1 - d ? d - c : end - 1 - d;
+ l = b;
+ h = end - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ if ((length = b - a) > 0)
+ sort(start, start + length, array);
+ if ((length = d - c) > 0)
+ sort(end - length, end, array);
+ }
+
+ /**
+ * Sorts the specified array in ascending order.
+ *
+ * @param array
+ * the char array to be sorted
+ */
+ public static void sort(char[] array) {
+ sort(0, array.length, array);
+ }
+
+ /**
+ * Sorts the specified range in the array in ascending order.
+ *
+ * @param array
+ * the char array to be sorted
+ * @param start
+ * the start index to sort
+ * @param end
+ * the last + 1 index to sort
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void sort(char[] array, int start, int end) {
+ if (start >= 0 && end <= array.length) {
+ if (start <= end)
+ sort(start, end, array);
+ else
+ throw new IllegalArgumentException();
+ } else
+ throw new ArrayIndexOutOfBoundsException();
+ }
+
+ private static void sort(int start, int end, char[] array) {
+ char temp;
+ int length = end - start;
+ if (length < 7) {
+ for (int i = start + 1; i < end; i++)
+ for (int j = i; j > start && array[j - 1] > array[j]; j--) {
+ temp = array[j];
+ array[j] = array[j - 1];
+ array[j - 1] = temp;
+ }
+ return;
+ }
+ int middle = (start + end) / 2;
+ if (length > 7) {
+ int bottom = start;
+ int top = end - 1;
+ if (length > 40) {
+ length /= 8;
+ bottom = med3(array, bottom, bottom + length, bottom
+ + (2 * length));
+ middle = med3(array, middle - length, middle, middle + length);
+ top = med3(array, top - (2 * length), top - length, top);
+ }
+ middle = med3(array, bottom, middle, top);
+ }
+ char partionValue = array[middle];
+ int a, b, c, d;
+ a = b = start;
+ c = d = end - 1;
+ while (true) {
+ while (b <= c && array[b] <= partionValue) {
+ if (array[b] == partionValue) {
+ temp = array[a];
+ array[a++] = array[b];
+ array[b] = temp;
+ }
+ b++;
+ }
+ while (c >= b && array[c] >= partionValue) {
+ if (array[c] == partionValue) {
+ temp = array[c];
+ array[c] = array[d];
+ array[d--] = temp;
+ }
+ c--;
+ }
+ if (b > c)
+ break;
+ temp = array[b];
+ array[b++] = array[c];
+ array[c--] = temp;
+ }
+ length = a - start < b - a ? a - start : b - a;
+ int l = start;
+ int h = b - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ length = d - c < end - 1 - d ? d - c : end - 1 - d;
+ l = b;
+ h = end - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ if ((length = b - a) > 0)
+ sort(start, start + length, array);
+ if ((length = d - c) > 0)
+ sort(end - length, end, array);
+ }
+
+ /**
+ * Sorts the specified array in ascending order.
+ *
+ * @param array
+ * the double array to be sorted
+ */
+ public static void sort(double[] array) {
+ sort(0, array.length, array);
+ }
+
+ /**
+ * Sorts the specified range in the array in ascending order.
+ *
+ * @param array
+ * the double array to be sorted
+ * @param start
+ * the start index to sort
+ * @param end
+ * the last + 1 index to sort
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void sort(double[] array, int start, int end) {
+ if (start >= 0 && end <= array.length) {
+ if (start <= end)
+ sort(start, end, array);
+ else
+ throw new IllegalArgumentException();
+ } else
+ throw new ArrayIndexOutOfBoundsException();
+ }
+
+ private static void sort(int start, int end, double[] array) {
+ double temp;
+ int length = end - start;
+ if (length < 7) {
+ for (int i = start + 1; i < end; i++)
+ for (int j = i; j > start && array[j - 1] > array[j]; j--) {
+ temp = array[j];
+ array[j] = array[j - 1];
+ array[j - 1] = temp;
+ }
+ return;
+ }
+ int middle = (start + end) / 2;
+ if (length > 7) {
+ int bottom = start;
+ int top = end - 1;
+ if (length > 40) {
+ length /= 8;
+ bottom = med3(array, bottom, bottom + length, bottom
+ + (2 * length));
+ middle = med3(array, middle - length, middle, middle + length);
+ top = med3(array, top - (2 * length), top - length, top);
+ }
+ middle = med3(array, bottom, middle, top);
+ }
+ double partionValue = array[middle];
+ int a, b, c, d;
+ a = b = start;
+ c = d = end - 1;
+ while (true) {
+ while (b <= c && array[b] <= partionValue) {
+ if (array[b] == partionValue) {
+ temp = array[a];
+ array[a++] = array[b];
+ array[b] = temp;
+ }
+ b++;
+ }
+ while (c >= b && array[c] >= partionValue) {
+ if (array[c] == partionValue) {
+ temp = array[c];
+ array[c] = array[d];
+ array[d--] = temp;
+ }
+ c--;
+ }
+ if (b > c)
+ break;
+ temp = array[b];
+ array[b++] = array[c];
+ array[c--] = temp;
+ }
+ length = a - start < b - a ? a - start : b - a;
+ int l = start;
+ int h = b - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ length = d - c < end - 1 - d ? d - c : end - 1 - d;
+ l = b;
+ h = end - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ if ((length = b - a) > 0)
+ sort(start, start + length, array);
+ if ((length = d - c) > 0)
+ sort(end - length, end, array);
+ }
+
+ /**
+ * Sorts the specified array in ascending order.
+ *
+ * @param array
+ * the float array to be sorted
+ */
+ public static void sort(float[] array) {
+ sort(0, array.length, array);
+ }
+
+ /**
+ * Sorts the specified range in the array in ascending order.
+ *
+ * @param array
+ * the float array to be sorted
+ * @param start
+ * the start index to sort
+ * @param end
+ * the last + 1 index to sort
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void sort(float[] array, int start, int end) {
+ if (start >= 0 && end <= array.length) {
+ if (start <= end)
+ sort(start, end, array);
+ else
+ throw new IllegalArgumentException();
+ } else
+ throw new ArrayIndexOutOfBoundsException();
+ }
+
+ private static void sort(int start, int end, float[] array) {
+ float temp;
+ int length = end - start;
+ if (length < 7) {
+ for (int i = start + 1; i < end; i++)
+ for (int j = i; j > start && array[j - 1] > array[j]; j--) {
+ temp = array[j];
+ array[j] = array[j - 1];
+ array[j - 1] = temp;
+ }
+ return;
+ }
+ int middle = (start + end) / 2;
+ if (length > 7) {
+ int bottom = start;
+ int top = end - 1;
+ if (length > 40) {
+ length /= 8;
+ bottom = med3(array, bottom, bottom + length, bottom
+ + (2 * length));
+ middle = med3(array, middle - length, middle, middle + length);
+ top = med3(array, top - (2 * length), top - length, top);
+ }
+ middle = med3(array, bottom, middle, top);
+ }
+ float partionValue = array[middle];
+ int a, b, c, d;
+ a = b = start;
+ c = d = end - 1;
+ while (true) {
+ while (b <= c && array[b] <= partionValue) {
+ if (array[b] == partionValue) {
+ temp = array[a];
+ array[a++] = array[b];
+ array[b] = temp;
+ }
+ b++;
+ }
+ while (c >= b && array[c] >= partionValue) {
+ if (array[c] == partionValue) {
+ temp = array[c];
+ array[c] = array[d];
+ array[d--] = temp;
+ }
+ c--;
+ }
+ if (b > c)
+ break;
+ temp = array[b];
+ array[b++] = array[c];
+ array[c--] = temp;
+ }
+ length = a - start < b - a ? a - start : b - a;
+ int l = start;
+ int h = b - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ length = d - c < end - 1 - d ? d - c : end - 1 - d;
+ l = b;
+ h = end - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ if ((length = b - a) > 0)
+ sort(start, start + length, array);
+ if ((length = d - c) > 0)
+ sort(end - length, end, array);
+ }
+
+ /**
+ * Sorts the specified array in ascending order.
+ *
+ * @param array
+ * the int array to be sorted
+ */
+ public static void sort(int[] array) {
+ sort(0, array.length, array);
+ }
+
+ /**
+ * Sorts the specified range in the array in ascending order.
+ *
+ * @param array
+ * the int array to be sorted
+ * @param start
+ * the start index to sort
+ * @param end
+ * the last + 1 index to sort
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void sort(int[] array, int start, int end) {
+ if (start >= 0 && end <= array.length) {
+ if (start <= end)
+ sort(start, end, array);
+ else
+ throw new IllegalArgumentException();
+ } else
+ throw new ArrayIndexOutOfBoundsException();
+ }
+
+ private static void sort(int start, int end, int[] array) {
+ int temp;
+ int length = end - start;
+ if (length < 7) {
+ for (int i = start + 1; i < end; i++)
+ for (int j = i; j > start && array[j - 1] > array[j]; j--) {
+ temp = array[j];
+ array[j] = array[j - 1];
+ array[j - 1] = temp;
+ }
+ return;
+ }
+ int middle = (start + end) / 2;
+ if (length > 7) {
+ int bottom = start;
+ int top = end - 1;
+ if (length > 40) {
+ length /= 8;
+ bottom = med3(array, bottom, bottom + length, bottom
+ + (2 * length));
+ middle = med3(array, middle - length, middle, middle + length);
+ top = med3(array, top - (2 * length), top - length, top);
+ }
+ middle = med3(array, bottom, middle, top);
+ }
+ int partionValue = array[middle];
+ int a, b, c, d;
+ a = b = start;
+ c = d = end - 1;
+ while (true) {
+ while (b <= c && array[b] <= partionValue) {
+ if (array[b] == partionValue) {
+ temp = array[a];
+ array[a++] = array[b];
+ array[b] = temp;
+ }
+ b++;
+ }
+ while (c >= b && array[c] >= partionValue) {
+ if (array[c] == partionValue) {
+ temp = array[c];
+ array[c] = array[d];
+ array[d--] = temp;
+ }
+ c--;
+ }
+ if (b > c)
+ break;
+ temp = array[b];
+ array[b++] = array[c];
+ array[c--] = temp;
+ }
+ length = a - start < b - a ? a - start : b - a;
+ int l = start;
+ int h = b - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ length = d - c < end - 1 - d ? d - c : end - 1 - d;
+ l = b;
+ h = end - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ if ((length = b - a) > 0)
+ sort(start, start + length, array);
+ if ((length = d - c) > 0)
+ sort(end - length, end, array);
+ }
+
+ /**
+ * Sorts the specified array in ascending order.
+ *
+ * @param array
+ * the long array to be sorted
+ */
+ public static void sort(long[] array) {
+ sort(0, array.length, array);
+ }
+
+ /**
+ * Sorts the specified range in the array in ascending order.
+ *
+ * @param array
+ * the long array to be sorted
+ * @param start
+ * the start index to sort
+ * @param end
+ * the last + 1 index to sort
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void sort(long[] array, int start, int end) {
+ if (start >= 0 && end <= array.length) {
+ if (start <= end)
+ sort(start, end, array);
+ else
+ throw new IllegalArgumentException();
+ } else
+ throw new ArrayIndexOutOfBoundsException();
+ }
+
+ private static void sort(int start, int end, long[] array) {
+ long temp;
+ int length = end - start;
+ if (length < 7) {
+ for (int i = start + 1; i < end; i++)
+ for (int j = i; j > start && array[j - 1] > array[j]; j--) {
+ temp = array[j];
+ array[j] = array[j - 1];
+ array[j - 1] = temp;
+ }
+ return;
+ }
+ int middle = (start + end) / 2;
+ if (length > 7) {
+ int bottom = start;
+ int top = end - 1;
+ if (length > 40) {
+ length /= 8;
+ bottom = med3(array, bottom, bottom + length, bottom
+ + (2 * length));
+ middle = med3(array, middle - length, middle, middle + length);
+ top = med3(array, top - (2 * length), top - length, top);
+ }
+ middle = med3(array, bottom, middle, top);
+ }
+ long partionValue = array[middle];
+ int a, b, c, d;
+ a = b = start;
+ c = d = end - 1;
+ while (true) {
+ while (b <= c && array[b] <= partionValue) {
+ if (array[b] == partionValue) {
+ temp = array[a];
+ array[a++] = array[b];
+ array[b] = temp;
+ }
+ b++;
+ }
+ while (c >= b && array[c] >= partionValue) {
+ if (array[c] == partionValue) {
+ temp = array[c];
+ array[c] = array[d];
+ array[d--] = temp;
+ }
+ c--;
+ }
+ if (b > c)
+ break;
+ temp = array[b];
+ array[b++] = array[c];
+ array[c--] = temp;
+ }
+ length = a - start < b - a ? a - start : b - a;
+ int l = start;
+ int h = b - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ length = d - c < end - 1 - d ? d - c : end - 1 - d;
+ l = b;
+ h = end - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ if ((length = b - a) > 0)
+ sort(start, start + length, array);
+ if ((length = d - c) > 0)
+ sort(end - length, end, array);
+ }
+
+ /**
+ * Sorts the specified array in ascending order.
+ *
+ * @param array
+ * the Object array to be sorted
+ *
+ * @exception ClassCastException
+ * when an element in the array does not implement Comparable
+ * or elements cannot be compared to each other
+ */
+ public static void sort(Object[] array) {
+ sort(0, array.length, array);
+ }
+
+ /**
+ * Sorts the specified range in the array in ascending order.
+ *
+ * @param array
+ * the Object array to be sorted
+ * @param start
+ * the start index to sort
+ * @param end
+ * the last + 1 index to sort
+ *
+ * @exception ClassCastException
+ * when an element in the array does not implement Comparable
+ * or elements cannot be compared to each other
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void sort(Object[] array, int start, int end) {
+ if (start >= 0 && end <= array.length) {
+ if (start <= end)
+ sort(start, end, array);
+ else
+ throw new IllegalArgumentException();
+ } else
+ throw new ArrayIndexOutOfBoundsException();
+ }
+
+ private static void sort(int start, int end, Object[] array) {
+ int middle = (start + end) / 2;
+ if (start + 1 < middle)
+ sort(start, middle, array);
+ if (middle + 1 < end)
+ sort(middle, end, array);
+ if (start + 1 >= end)
+ return; // this case can only happen when this method is called by
+ // the user
+ if (((Comparable) array[middle - 1]).compareTo(array[middle]) <= 0)
+ return;
+ if (start + 2 == end) {
+ Object temp = array[start];
+ array[start] = array[middle];
+ array[middle] = temp;
+ return;
+ }
+ int i1 = start, i2 = middle, i3 = 0;
+ Object[] merge = new Object[end - start];
+ while (i1 < middle && i2 < end) {
+ merge[i3++] = ((Comparable) array[i1]).compareTo(array[i2]) <= 0 ? array[i1++]
+ : array[i2++];
+ }
+ if (i1 < middle)
+ System.arraycopy(array, i1, merge, i3, middle - i1);
+ System.arraycopy(merge, 0, array, start, i2 - start);
+ }
+
+ /**
+ * Sorts the specified range in the array using the specified Comparator.
+ *
+ * @param array
+ * the Object array to be sorted
+ * @param start
+ * the start index to sort
+ * @param end
+ * the last + 1 index to sort
+ * @param comparator
+ * the Comparator
+ *
+ * @exception ClassCastException
+ * when elements in the array cannot be compared to each
+ * other using the Comparator
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void sort(Object[] array, int start, int end,
+ Comparator comparator) {
+ if (start >= 0 && end <= array.length) {
+ if (start <= end)
+ sort(start, end, array, comparator);
+ else
+ throw new IllegalArgumentException();
+ } else
+ throw new ArrayIndexOutOfBoundsException();
+ }
+
+ private static void sort(int start, int end, Object[] array,
+ Comparator comparator) {
+ int middle = (start + end) / 2;
+ if (start + 1 < middle)
+ sort(start, middle, array, comparator);
+ if (middle + 1 < end)
+ sort(middle, end, array, comparator);
+ if (start + 1 >= end)
+ return; // this case can only happen when this method is called by
+ // the user
+ if (comparator.compare(array[middle - 1], array[middle]) <= 0)
+ return;
+ if (start + 2 == end) {
+ Object temp = array[start];
+ array[start] = array[middle];
+ array[middle] = temp;
+ return;
+ }
+ int i1 = start, i2 = middle, i3 = 0;
+ Object[] merge = new Object[end - start];
+ while (i1 < middle && i2 < end) {
+ merge[i3++] = comparator.compare(array[i1], array[i2]) <= 0 ? array[i1++]
+ : array[i2++];
+ }
+ if (i1 < middle)
+ System.arraycopy(array, i1, merge, i3, middle - i1);
+ System.arraycopy(merge, 0, array, start, i2 - start);
+ }
+
+ /**
+ * Sorts the specified array using the specified Comparator.
+ *
+ * @param array
+ * the Object array to be sorted
+ * @param comparator
+ * the Comparator
+ *
+ * @exception ClassCastException
+ * when elements in the array cannot be compared to each
+ * other using the Comparator
+ */
+ public static void sort(Object[] array, Comparator comparator) {
+ sort(0, array.length, array, comparator);
+ }
+
+ /**
+ * Sorts the specified array in ascending order.
+ *
+ * @param array
+ * the short array to be sorted
+ */
+ public static void sort(short[] array) {
+ sort(0, array.length, array);
+ }
+
+ /**
+ * Sorts the specified range in the array in ascending order.
+ *
+ * @param array
+ * the short array to be sorted
+ * @param start
+ * the start index to sort
+ * @param end
+ * the last + 1 index to sort
+ *
+ * @exception IllegalArgumentException
+ * when <code>start > end</code>
+ * @exception ArrayIndexOutOfBoundsException
+ * when <code>start < 0</code> or
+ * <code>end > array.size()</code>
+ */
+ public static void sort(short[] array, int start, int end) {
+ if (start >= 0 && end <= array.length) {
+ if (start <= end)
+ sort(start, end, array);
+ else
+ throw new IllegalArgumentException();
+ } else
+ throw new ArrayIndexOutOfBoundsException();
+ }
+
+ private static void sort(int start, int end, short[] array) {
+ short temp;
+ int length = end - start;
+ if (length < 7) {
+ for (int i = start + 1; i < end; i++)
+ for (int j = i; j > start && array[j - 1] > array[j]; j--) {
+ temp = array[j];
+ array[j] = array[j - 1];
+ array[j - 1] = temp;
+ }
+ return;
+ }
+ int middle = (start + end) / 2;
+ if (length > 7) {
+ int bottom = start;
+ int top = end - 1;
+ if (length > 40) {
+ length /= 8;
+ bottom = med3(array, bottom, bottom + length, bottom
+ + (2 * length));
+ middle = med3(array, middle - length, middle, middle + length);
+ top = med3(array, top - (2 * length), top - length, top);
+ }
+ middle = med3(array, bottom, middle, top);
+ }
+ short partionValue = array[middle];
+ int a, b, c, d;
+ a = b = start;
+ c = d = end - 1;
+ while (true) {
+ while (b <= c && array[b] <= partionValue) {
+ if (array[b] == partionValue) {
+ temp = array[a];
+ array[a++] = array[b];
+ array[b] = temp;
+ }
+ b++;
+ }
+ while (c >= b && array[c] >= partionValue) {
+ if (array[c] == partionValue) {
+ temp = array[c];
+ array[c] = array[d];
+ array[d--] = temp;
+ }
+ c--;
+ }
+ if (b > c)
+ break;
+ temp = array[b];
+ array[b++] = array[c];
+ array[c--] = temp;
+ }
+ length = a - start < b - a ? a - start : b - a;
+ int l = start;
+ int h = b - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ length = d - c < end - 1 - d ? d - c : end - 1 - d;
+ l = b;
+ h = end - length;
+ while (length-- > 0) {
+ temp = array[l];
+ array[l++] = array[h];
+ array[h++] = temp;
+ }
+ if ((length = b - a) > 0)
+ sort(start, start + length, array);
+ if ((length = d - c) > 0)
+ sort(end - length, end, array);
+ }
+}
Added: incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/BitSet.java
URL: http://svn.apache.org/viewcvs/incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/BitSet.java?rev=350181&view=auto
==============================================================================
--- incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/BitSet.java (added)
+++ incubator/harmony/enhanced/trunk/sandbox/contribs/ibm_core/java-src/luni/src/java/util/BitSet.java Wed Nov 30 21:29:27 2005
@@ -0,0 +1,756 @@
+/* Copyright 1998, 2004 The Apache Software Foundation or its licensors, as applicable
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+
+import java.io.Serializable;
+
+/**
+ * The BitSet class implements a bit field. Each element in a BitSet can be
+ * on(1) or off(0). A BitSet is created with a given size and grows when this
+ * size is exceeded. Growth is always rounded to a 64 bit boundary.
+ */
+public class BitSet implements Serializable, Cloneable {
+ static final long serialVersionUID = 7997698588986878753L;
+
+ private long[] bits;
+
+ private static final int ELM_SIZE = 64; // Size in bits of the data type
+
+ // being used in the bits array
+
+ /**
+ * Create a new BitSet with size equal to 64 bits
+ *
+ * @see #clear(int)
+ * @see #set(int)
+ * @see #clear()
+ * @see #clear(int, int)
+ * @see #set(int, boolean)
+ * @see #set(int, int)
+ * @see #set(int, int, boolean)
+ */
+ public BitSet() {
+ this(64);
+ }
+
+ /**
+ * Create a new BitSet with size equal to nbits. If nbits is not a multiple
+ * of 64, then create a BitSet with size nbits rounded to the next closest
+ * multiple of 64.
+ *
+ * @param nbits
+ * the size of the bit set
+ * @throws NegativeArraySizeException
+ * if nbits < 0.
+ *
+ * @see #clear(int)
+ * @see #set(int)
+ * @see #clear()
+ * @see #clear(int, int)
+ * @see #set(int, boolean)
+ * @see #set(int, int)
+ * @see #set(int, int, boolean)
+ */
+ public BitSet(int nbits) {
+ if (nbits >= 0)
+ bits = new long[(nbits / ELM_SIZE) + (nbits % ELM_SIZE > 0 ? 1 : 0)];
+ else
+ throw new NegativeArraySizeException();
+ }
+
+ /***************************************************************************
+ * Private constructor called from get(int, int) method
+ *
+ * @param bits
+ * the size of the bit set
+ */
+ private BitSet(long[] bits) {
+ this.bits = bits;
+ }
+
+ /**
+ * Create a copy of this BitSet
+ *
+ * @return A copy of this BitSet.
+ */
+ public Object clone() {
+ BitSet bs = new BitSet(this.size());
+ System.arraycopy(bits, 0, bs.bits, 0, bits.length);
+ return bs;
+ }
+
+ /**
+ * Compares the argument to this BitSet and answer if they are equal. The
+ * object must be an instance of BitSet with the same bits set.
+ *
+ * @param obj
+ * the <code>BitSet</code> object to compare
+ * @return A boolean indicating whther or not this BitSet and obj are equal
+ *
+ * @see #hashCode
+ */
+ public boolean equals(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj instanceof BitSet) {
+ long[] bsBits = ((BitSet) obj).bits;
+ int length1 = bits.length, length2 = bsBits.length;
+ // If one of the BitSets is larger than the other, check to see if
+ // any of
+ // its extra bits are set. If so return false.
+ if (length1 <= length2) {
+ for (int i = 0; i < length1; i++)
+ if (bits[i] != bsBits[i])
+ return false;
+ for (int i = length1; i < length2; i++)
+ if (bsBits[i] != 0)
+ return false;
+ } else {
+ for (int i = 0; i < length2; i++)
+ if (bits[i] != bsBits[i])
+ return false;
+ for (int i = length2; i < length1; i++)
+ if (bits[i] != 0)
+ return false;
+ }
+ return true;
+ }
+ return false;
+ }
+
+ /**
+ * Increase the size of the internal array to accomodate pos bits. The new
+ * array max index will be a multiple of 64
+ *
+ * @param pos
+ * the index the new array needs to be able to access
+ */
+ private void growBits(int pos) {
+ pos++; // Inc to get correct bit count
+ long[] tempBits = new long[(pos / ELM_SIZE)
+ + (pos % ELM_SIZE > 0 ? 1 : 0)];
+ System.arraycopy(bits, 0, tempBits, 0, bits.length);
+ bits = tempBits;
+ }
+
+ /**
+ * Computes the hash code for this BitSet.
+ *
+ * @return The <code>int</code> representing the hash code for this bit
+ * set.
+ *
+ * @see #equals
+ * @see java.util.Hashtable
+ */
+ public int hashCode() {
+ long x = 1234;
+ // for (int i = 0, length = bits.length; i < length; i+=2)
+ // x ^= (bits[i] + ((long)bits[i+1] << 32)) * (i/2 + 1);
+ for (int i = 0, length = bits.length; i < length; i++)
+ x ^= bits[i] * (i + 1);
+ return (int) ((x >> 32) ^ x);
+ }
+
+ /**
+ * Retrieve the bit at index pos. Grows the BitSet if pos > size.
+ *
+ * @param pos
+ * the index of the bit to be retrieved
+ * @return <code>true</code> if the bit at <code>pos</code> is set,
+ * <code>false</code> otherwise
+ * @throws IndexOutOfBoundsException
+ * when <code>pos</code> < 0
+ *
+ * @see #clear(int)
+ * @see #set(int)
+ * @see #clear()
+ * @see #clear(int, int)
+ * @see #set(int, boolean)
+ * @see #set(int, int)
+ * @see #set(int, int, boolean)
+ */
+ public boolean get(int pos) {
+ if (pos >= 0) {
+ if (pos < bits.length * ELM_SIZE)
+ return (bits[pos / ELM_SIZE] & (1L << (pos % ELM_SIZE))) != 0;
+ return false;
+ } else
+ throw new IndexOutOfBoundsException(com.ibm.oti.util.Msg
+ .getString("K0006")); //$NON-NLS-1$
+ }
+
+ /**
+ * Retrieves the bits starting from pos1 to pos2 and answers back a new
+ * bitset made of these bits. Grows the BitSet if pos2 > size.
+ *
+ * @param pos1
+ * beginning position
+ * @param pos2
+ * ending position
+ * @return new bitset
+ * @throws IndexOutOfBoundsException
+ * when pos1 or pos2 is negative, or when pos2 is not smaller
+ * than pos1
+ *
+ * @see #get(int)
+ */
+ public BitSet get(int pos1, int pos2) {
+ if (pos1 >= 0 && pos2 > 0 && pos2 > pos1) {
+ if (pos2 >= bits.length * ELM_SIZE)
+ growBits(pos2);
+
+ int idx1 = pos1 / ELM_SIZE;
+ int idx2 = pos2 / ELM_SIZE;
+ long factor1 = (~0L) << (pos1 % ELM_SIZE);
+ long factor2 = Long.MAX_VALUE >> (ELM_SIZE - (pos2 % ELM_SIZE) - 1);
+
+ if (idx1 == idx2) {
+ long result = (bits[idx1] & (factor1 & factor2)) >>> (pos1 % ELM_SIZE);
+ return new BitSet(new long[] { result });
+ } else {
+ long[] newbits = new long[idx2 - idx1 + 1];
+ // first fill in the first and last indexes in the new bitset
+ newbits[0] = bits[idx1] & factor1;
+ newbits[newbits.length - 1] = bits[idx2] & factor2;
+
+ // fill in the in between elements of the new bitset
+ for (int i = 1; i < idx2 - idx1; i++)
+ newbits[i] = bits[idx1 + i];
+
+ // shift all the elements in the new bitset to the right by pos1
+ // % ELM_SIZE
+ int numBitsToShift = pos1 % ELM_SIZE;
+ if (numBitsToShift != 0) {
+ for (int i = 0; i < newbits.length; i++) {
+ // shift the current element to the right regardless of
+ // sign
+ newbits[i] = newbits[i] >>> (numBitsToShift);
+
+ // apply the last x bits of newbits[i+1] to the current
+ // element
+ if (i != newbits.length - 1)
+ newbits[i] |= newbits[i + 1] << (ELM_SIZE - (numBitsToShift));
+ }
+ }
+ return new BitSet(newbits);
+ }
+ } else
+ throw new IndexOutOfBoundsException(com.ibm.oti.util.Msg
+ .getString("K0006")); //$NON-NLS-1$
+ }
+
+ /**
+ * Sets the bit at index pos to 1. Grows the BitSet if pos > size.
+ *
+ * @param pos
+ * the index of the bit to set
+ * @throws IndexOutOfBoundsException
+ * when pos < 0
+ *
+ * @see #clear(int)
+ * @see #clear()
+ * @see #clear(int, int)
+ */
+ public void set(int pos) {
+ if (pos >= 0) {
+ if (pos >= bits.length * ELM_SIZE)
+ growBits(pos);
+ bits[pos / ELM_SIZE] |= 1L << (pos % ELM_SIZE);
+ } else
+ throw new IndexOutOfBoundsException(com.ibm.oti.util.Msg
+ .getString("K0006")); //$NON-NLS-1$
+ }
+
+ /**
+ * Sets the bit at index pos to the value. Grows the BitSet if pos > size.
+ *
+ * @param pos
+ * the index of the bit to set
+ * @param val
+ * value to set the bit
+ * @throws IndexOutOfBoundsException
+ * when pos < 0
+ *
+ * @see #set(int)
+ */
+ public void set(int pos, boolean val) {
+ if (val)
+ set(pos);
+ else
+ clear(pos);
+ }
+
+ /**
+ * Sets the bits starting from pos1 to pos2. Grows the BitSet if pos2 >
+ * size.
+ *
+ * @param pos1
+ * beginning position
+ * @param pos2
+ * ending position
+ * @throws IndexOutOfBoundsException
+ * when pos1 or pos2 is negative, or when pos2 is not smaller
+ * than pos1
+ *
+ * @see #set(int)
+ */
+ public void set(int pos1, int pos2) {
+ if (pos1 >= 0 && pos2 > 0 && pos2 > pos1) {
+ if (pos2 >= bits.length * ELM_SIZE)
+ growBits(pos2);
+
+ int idx1 = pos1 / ELM_SIZE;
+ int idx2 = pos2 / ELM_SIZE;
+ long factor1 = (~0L) << (pos1 % ELM_SIZE);
+ long factor2 = Long.MAX_VALUE >> (ELM_SIZE - (pos2 % ELM_SIZE) - 1);
+
+ if (idx1 == idx2)
+ bits[idx1] |= (factor1 & factor2);
+ else {
+ bits[idx1] |= factor1;
+ bits[idx2] |= factor2;
+ for (int i = idx1 + 1; i < idx2; i++)
+ bits[i] |= (~0L);
+ }
+ } else
+ throw new IndexOutOfBoundsException(com.ibm.oti.util.Msg
+ .getString("K0006")); //$NON-NLS-1$
+ }
+
+ /**
+ * Sets the bits starting from pos1 to pos2 to the given boolean value.
+ * Grows the BitSet if pos2 > size.
+ *
+ * @param pos1
+ * beginning position
+ * @param pos2
+ * ending position
+ * @param val
+ * value to set these bits
+ *
+ * @throws IndexOutOfBoundsException
+ * when pos1 or pos2 is negative, or when pos2 is not smaller
+ * than pos1
+ * @see #set(int,int)
+ */
+ public void set(int pos1, int pos2, boolean val) {
+ if (val)
+ set(pos1, pos2);
+ else
+ clear(pos1, pos2);
+ }
+
+ /**
+ * Clears all the bits in this bitset.
+ *
+ * @see #clear(int)
+ * @see #clear(int, int)
+ */
+ public void clear() {
+ for (int i = 0; i < bits.length; i++) {
+ bits[i] = 0L;
+ }
+ }
+
+ /**
+ * Clears the bit at index pos. Grows the BitSet if pos > size.
+ *
+ * @param pos
+ * the index of the bit to clear
+ * @throws IndexOutOfBoundsException
+ * when pos < 0
+ *
+ * @see #clear(int, int)
+ */
+ public void clear(int pos) {
+ if (pos >= 0) {
+ if (pos < bits.length * ELM_SIZE)
+ bits[pos / ELM_SIZE] &= ~(1L << (pos % ELM_SIZE));
+ else
+ growBits(pos); // Bit is cleared for free if we have to grow
+ } else
+ throw new IndexOutOfBoundsException(com.ibm.oti.util.Msg
+ .getString("K0006")); //$NON-NLS-1$
+ }
+
+ /**
+ * Clears the bits starting from pos1 to pos2. Grows the BitSet if pos2 >
+ * size.
+ *
+ * @param pos1
+ * beginning position
+ * @param pos2
+ * ending position
+ * @throws IndexOutOfBoundsException
+ * when pos1 or pos2 is negative, or when pos2 is not smaller
+ * than pos1
+ *
+ * @see #clear(int)
+ */
+ public void clear(int pos1, int pos2) {
+ if (pos1 >= 0 && pos2 > 0 && pos2 > pos1) {
+ if (pos2 >= bits.length * ELM_SIZE)
+ growBits(pos2);
+
+ int idx1 = pos1 / ELM_SIZE;
+ int idx2 = pos2 / ELM_SIZE;
+ long factor1 = (~0L) << (pos1 % ELM_SIZE);
+ long factor2 = Long.MAX_VALUE >> (ELM_SIZE - (pos2 % ELM_SIZE) - 1);
+
+ if (idx1 == idx2)
+ bits[idx1] &= ~(factor1 & factor2);
+ else {
+ bits[idx1] &= ~factor1;
+ bits[idx2] &= ~factor2;
+ for (int i = idx1 + 1; i < idx2; i++)
+ bits[i] = 0L;
+ }
+ } else
+ throw new IndexOutOfBoundsException(com.ibm.oti.util.Msg
+ .getString("K0006")); //$NON-NLS-1$
+ }
+
+ /**
+ * Flips the bit at index pos. Grows the BitSet if pos > size.
+ *
+ * @param pos
+ * the index of the bit to flip
+ *
+ * @throws IndexOutOfBoundsException
+ * when pos < 0
+ * @see #flip(int, int)
+ */
+ public void flip(int pos) {
+ if (pos >= 0) {
+ if (pos >= bits.length * ELM_SIZE)
+ growBits(pos);
+ bits[pos / ELM_SIZE] ^= 1L << (pos % ELM_SIZE);
+ } else
+ throw new IndexOutOfBoundsException(com.ibm.oti.util.Msg
+ .getString("K0006")); //$NON-NLS-1$
+ }
+
+ /**
+ * Flips the bits starting from pos1 to pos2. Grows the BitSet if pos2 >
+ * size.
+ *
+ * @param pos1
+ * beginning position
+ * @param pos2
+ * ending position
+ * @throws IndexOutOfBoundsException
+ * when pos1 or pos2 is negative, or when pos2 is not smaller
+ * than pos1
+ *
+ * @see #flip(int)
+ */
+ public void flip(int pos1, int pos2) {
+ if (pos1 >= 0 && pos2 > 0 && pos2 > pos1) {
+ if (pos2 >= bits.length * ELM_SIZE)
+ growBits(pos2);
+
+ int idx1 = pos1 / ELM_SIZE;
+ int idx2 = pos2 / ELM_SIZE;
+ long factor1 = (~0L) << (pos1 % ELM_SIZE);
+ long factor2 = Long.MAX_VALUE >> (ELM_SIZE - (pos2 % ELM_SIZE) - 1);
+
+ if (idx1 == idx2)
+ bits[idx1] ^= (factor1 & factor2);
+ else {
+ bits[idx1] ^= factor1;
+ bits[idx2] ^= factor2;
+ for (int i = idx1 + 1; i < idx2; i++)
+ bits[i] ^= (~0L);
+ }
+ } else
+ throw new IndexOutOfBoundsException(com.ibm.oti.util.Msg
+ .getString("K0006")); //$NON-NLS-1$
+ }
+
+ /**
+ * Checks if these two bitsets have at least one bit set to true in the same
+ * position.
+ *
+ * @param bs
+ * BitSet used to calculate intersect
+ * @return <code>true</code> if bs intersects with this BitSet,
+ * <code>false</code> otherwise
+ */
+ public boolean intersects(BitSet bs) {
+ long[] bsBits = bs.bits;
+ int length1 = bits.length, length2 = bsBits.length;
+
+ if (length1 <= length2) {
+ for (int i = 0; i < length1; i++)
+ if ((bits[i] & bsBits[i]) != 0L)
+ return true;
+ } else {
+ for (int i = 0; i < length2; i++)
+ if ((bits[i] & bsBits[i]) != 0L)
+ return true;
+ }
+
+ return false;
+ }
+
+ /**
+ * Performs the logical AND of this BitSet with another BitSet.
+ *
+ * @param bs
+ * BitSet to AND with
+ *
+ * @see #or
+ * @see #xor
+ */
+
+ public void and(BitSet bs) {
+ long[] bsBits = bs.bits;
+ int length1 = bits.length, length2 = bsBits.length;
+ if (length1 <= length2) {
+ for (int i = 0; i < length1; i++)
+ bits[i] &= bsBits[i];
+ } else {
+ for (int i = 0; i < length2; i++)
+ bits[i] &= bsBits[i];
+ for (int i = length2; i < length1; i++)
+ bits[i] = 0;
+ }
+ }
+
+ /**
+ * Clears all bits in the receiver which are also set in the parameter
+ * BitSet.
+ *
+ * @param bs
+ * BitSet to ANDNOT with
+ */
+ public void andNot(BitSet bs) {
+ long[] bsBits = bs.bits;
+ int range = bits.length < bsBits.length ? bits.length : bsBits.length;
+ for (int i = 0; i < range; i++)
+ bits[i] &= ~bsBits[i];
+ }
+
+ /**
+ * Performs the logical OR of this BitSet with another BitSet.
+ *
+ * @param bs
+ * BitSet to OR with
+ *
+ * @see #xor
+ * @see #and
+ */
+ public void or(BitSet bs) {
+ int nbits = bs.length();
+ int length = nbits / ELM_SIZE + (nbits % ELM_SIZE > 0 ? 1 : 0);
+ if (length > bits.length)
+ growBits(nbits - 1);
+ long[] bsBits = bs.bits;
+ for (int i = 0; i < length; i++)
+ bits[i] |= bsBits[i];
+ }
+
+ /**
+ * Performs the logical XOR of this BitSet with another BitSet.
+ *
+ * @param bs
+ * BitSet to XOR with
+ *
+ * @see #or
+ * @see #and
+ */
+ public void xor(BitSet bs) {
+ int nbits = bs.length();
+ int length = nbits / ELM_SIZE + (nbits % ELM_SIZE > 0 ? 1 : 0);
+ if (length > bits.length)
+ growBits(nbits - 1);
+ long[] bsBits = bs.bits;
+ for (int i = 0; i < length; i++)
+ bits[i] ^= bsBits[i];
+
+ }
+
+ /**
+ * Answers the number of bits this bitset has.
+ *
+ * @return The number of bits contained in this BitSet.
+ *
+ * @see #length
+ */
+ public int size() {
+ return bits.length * ELM_SIZE;
+ }
+
+ /**
+ * Returns the number of bits up to and including the highest bit set.
+ *
+ * @return the length of the BitSet
+ */
+ public int length() {
+ int idx = bits.length - 1;
+ while (idx >= 0 && bits[idx] == 0)
+ --idx;
+ if (idx == -1)
+ return 0;
+ int i = ELM_SIZE - 1;
+ long val = bits[idx];
+ while ((val & (1L << i)) == 0 && i > 0)
+ i--;
+ return idx * ELM_SIZE + i + 1;
+ }
+
+ /**
+ * Answers a string containing a concise, human-readable description of the
+ * receiver.
+ *
+ * @return A comma delimited list of the indices of all bits that are set.
+ */
+ public String toString() {
+ StringBuffer sb = new StringBuffer(bits.length / 2);
+ int bitCount = 0;
+ sb.append('{');
+ boolean comma = false;
+ for (int i = 0; i < bits.length; i++) {
+ if (bits[i] == 0) {
+ bitCount += ELM_SIZE;
+ continue;
+ }
+ for (int j = 0; j < ELM_SIZE; j++) {
+ if (((bits[i] & (1L << j)) != 0)) {
+ if (comma)
+ sb.append(", "); //$NON-NLS-1$
+ sb.append(bitCount);
+ comma = true;
+ }
+ bitCount++;
+ }
+ }
+ sb.append('}');
+ return sb.toString();
+ }
+
+ /**
+ * Answers the position of the first bit that is true on or after pos
+ *
+ * @param pos
+ * the starting position (inclusive)
+ * @return -1 if there is no bits that are set to true on or after pos.
+ */
+ public int nextSetBit(int pos) {
+ if (pos >= 0) {
+ if (pos >= bits.length * ELM_SIZE)
+ return -1;
+
+ int idx = pos / ELM_SIZE;
+ // first check in the same bit set element
+ if (bits[idx] != 0L) {
+ for (int j = pos % ELM_SIZE; j < ELM_SIZE; j++)
+ if (((bits[idx] & (1L << j)) != 0))
+ return idx * ELM_SIZE + j;
+
+ }
+ idx++;
+ while (idx < bits.length && bits[idx] == 0L)
+ idx++;
+ if (idx == bits.length)
+ return -1;
+
+ // we know for sure there is a bit set to true in this element
+ // since the bitset value is not 0L
+ for (int j = 0; j < ELM_SIZE; j++)
+ if (((bits[idx] & (1L << j)) != 0))
+ return idx * ELM_SIZE + j;
+
+ return -1;
+ } else
+ throw new IndexOutOfBoundsException(com.ibm.oti.util.Msg
+ .getString("K0006")); //$NON-NLS-1$
+ }
+
+ /**
+ * Answers the position of the first bit that is false on or after pos
+ *
+ * @param pos
+ * the starting position (inclusive)
+ * @return the position of the next bit set to false, even if it is further
+ * than this bitset's size.
+ */
+ public int nextClearBit(int pos) {
+ if (pos >= 0) {
+ int bssize = bits.length * ELM_SIZE;
+ if (pos >= bssize)
+ return pos;
+
+ int idx = pos / ELM_SIZE;
+ // first check in the same bit set element
+ if (bits[idx] != (~0L)) {
+ for (int j = pos % ELM_SIZE; j < ELM_SIZE; j++)
+ if (((bits[idx] & (1L << j)) == 0))
+ return idx * ELM_SIZE + j;
+
+ }
+ idx++;
+ while (idx < bits.length && bits[idx] == (~0L))
+ idx++;
+ if (idx == bits.length)
+ return bssize;
+
+ // we know for sure there is a bit set to true in this element
+ // since the bitset value is not 0L
+ for (int j = 0; j < ELM_SIZE; j++)
+ if (((bits[idx] & (1L << j)) == 0))
+ return idx * ELM_SIZE + j;
+
+ return bssize;
+ } else
+ throw new IndexOutOfBoundsException(com.ibm.oti.util.Msg
+ .getString("K0006")); //$NON-NLS-1$
+ }
+
+ /**
+ * Answers true if all the bits in this bitset are set to false.
+ *
+ * @return <code>true</code> if the BitSet is empty, <code>false</code>
+ * otherwise
+ */
+ public boolean isEmpty() {
+ for (int idx = 0; idx < bits.length; idx++)
+ if (bits[idx] != 0L)
+ return false;
+
+ return true;
+ }
+
+ /**
+ * Answers the number of bits that are true in this bitset.
+ *
+ * @return the number of true bits in the set
+ */
+ public int cardinality() {
+ int count = 0;
+ for (int idx = 0; idx < bits.length; idx++) {
+ long temp = bits[idx];
+ if (temp != 0L) {
+ for (int i = 0; i < ELM_SIZE; i++) {
+ if ((temp & (1L << i)) != 0L)
+ count++;
+ }
+ }
+ }
+ return count;
+ }
+}