harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ge...@apache.org
Subject 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....
Date Thu, 01 Dec 2005 06:04:00 GMT
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;
+	}
+}



Mime
View raw message