You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by te...@apache.org on 2007/01/02 17:22:07 UTC
svn commit: r491834 [2/7] - in
/harmony/enhanced/classlib/trunk/modules/luni/src/main/java: java/net/
java/util/ org/apache/harmony/luni/internal/nls/
org/apache/harmony/luni/internal/reflect/ org/apache/harmony/luni/net/
Modified: harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/Arrays.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/Arrays.java?view=diff&rev=491834&r1=491833&r2=491834
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/Arrays.java (original)
+++ harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/Arrays.java Tue Jan 2 08:22:05 2007
@@ -27,8 +27,8 @@
*/
public class Arrays {
- /* Specifies when to switch to insertion sort */
- private static final int SIMPLE_LENGTH = 7;
+ /* Specifies when to switch to insertion sort */
+ private static final int SIMPLE_LENGTH = 7;
private static class ArrayList<E> extends AbstractList<E> implements
List<E>, Serializable, RandomAccess {
@@ -360,8 +360,8 @@
@SuppressWarnings("unchecked")
public static int binarySearch(Object[] array, Object object) {
if (array.length == 0) {
- return -1;
- }
+ return -1;
+ }
Comparable<Object> key = (Comparable<Object>) object;
int low = 0, mid = 0, high = array.length - 1, result = 0;
while (low <= high) {
@@ -864,8 +864,9 @@
*
* The value returned by this method is the same value as the
* {@link List#hashCode()}} method which is invoked on a {@link List}}
- * containing a sequence of {@link Boolean}} instances representing the elements of
- * array in the same order. If the array is null, the return value is 0.
+ * containing a sequence of {@link Boolean}} instances representing the
+ * elements of array in the same order. If the array is null, the return
+ * value is 0.
*
* @param array
* the array whose hash code to compute
@@ -991,7 +992,7 @@
}
return hashCode;
}
-
+
/**
* Answers a hash code based on the contents of the given array. For any two
* long arrays a and b, if Arrays.equals(a, b) returns true, it means that
@@ -1446,14 +1447,15 @@
* or if they refer to arrays that have the same length and the elements at
* each index in the two arrays are equal.
*
- * Two null elements element1 and element2 are possibly deeply equal if any of the
- * following conditions satisfied:
+ * Two null elements element1 and element2 are possibly deeply equal if any
+ * of the following conditions satisfied:
*
* element1 and element2 are both arrays of object reference types, and
* Arrays.deepEquals(element1, element2) would return true.
*
- * element1 and element2 are arrays of the same primitive type, and the appropriate
- * overloading of Arrays.equals(element1, element2) would return true.
+ * element1 and element2 are arrays of the same primitive type, and the
+ * appropriate overloading of Arrays.equals(element1, element2) would return
+ * true.
*
* element1 == element2
*
@@ -1657,14 +1659,14 @@
private static void checkBounds(int arrLength, int start, int end) {
if (start > end) {
- throw new IllegalArgumentException("fromIndex(" + start
- + ") > toIndex(" + end + ")");
+ throw new IllegalArgumentException("fromIndex(" + start //$NON-NLS-1$
+ + ") > toIndex(" + end + ")"); //$NON-NLS-1$ //$NON-NLS-2$
}
if (start < 0 || end > arrLength) {
- throw new ArrayIndexOutOfBoundsException();
+ throw new ArrayIndexOutOfBoundsException();
}
}
-
+
private static void sort(int start, int end, byte[] array) {
byte temp;
int length = end - start;
@@ -2369,467 +2371,478 @@
}
/**
- * Swaps the elements at the specified positions in the specified array.
- *
- * @param a -
- * the index of one element to be swapped.
- * @param b -
- * the index of the other element to be swapped.
- * @param arr -
- * the array in which to swap elements.
- */
- private static void swap(int a, int b, Object[] arr) {
- Object tmp = arr[a];
- arr[a] = arr[b];
- arr[b] = tmp;
- }
-
- /**
- * Sorts the specified range of the specified array of objects. The range to
- * be sorted extends from index fromIndex, inclusive, to index toIndex,
- * exclusive. (If fromIndex==toIndex, the range to be sorted is empty.) This
- * sort is guaranteed to be stable: equal elements will not be reordered as
- * a result of the sort.
- *
- * The sorting algorithm is a mergesort with exponential search (in which
- * the merge is performed by exponential search). This algorithm offers
- * guaranteed n*log(n) performance and in average case faster then any
- * mergesort in which the merge is performed by linear search.
- *
- * @param in -
- * the array for sorting.
- * @param out -
- * the result, sorted array.
- * @param fromIndex -
- * the index of the first element (inclusive) to be sorted.
- * @param toIndex -
- * the index of the last element (exclusive) to be sorted.
- */
- @SuppressWarnings("unchecked")
+ * Swaps the elements at the specified positions in the specified array.
+ *
+ * @param a -
+ * the index of one element to be swapped.
+ * @param b -
+ * the index of the other element to be swapped.
+ * @param arr -
+ * the array in which to swap elements.
+ */
+ private static void swap(int a, int b, Object[] arr) {
+ Object tmp = arr[a];
+ arr[a] = arr[b];
+ arr[b] = tmp;
+ }
+
+ /**
+ * Sorts the specified range of the specified array of objects. The range to
+ * be sorted extends from index fromIndex, inclusive, to index toIndex,
+ * exclusive. (If fromIndex==toIndex, the range to be sorted is empty.) This
+ * sort is guaranteed to be stable: equal elements will not be reordered as
+ * a result of the sort.
+ *
+ * The sorting algorithm is a mergesort with exponential search (in which
+ * the merge is performed by exponential search). This algorithm offers
+ * guaranteed n*log(n) performance and in average case faster then any
+ * mergesort in which the merge is performed by linear search.
+ *
+ * @param in -
+ * the array for sorting.
+ * @param out -
+ * the result, sorted array.
+ * @param fromIndex -
+ * the index of the first element (inclusive) to be sorted.
+ * @param toIndex -
+ * the index of the last element (exclusive) to be sorted.
+ */
+ @SuppressWarnings("unchecked")
private static void mergeSort(Object[] in, Object[] out, int fromIndex,
- int toIndex) {
- int len = toIndex - fromIndex;
- //use insertion sort for small arrays
- if (len <= SIMPLE_LENGTH) {
- for (int i = fromIndex + 1; i < toIndex; i++) {
- Comparable<Object> current = (Comparable<Object>)out[i];
- Object prev = out[i - 1];
- if (current.compareTo(prev) < 0) {
- int j = i;
- do {
+ int toIndex) {
+ int len = toIndex - fromIndex;
+ // use insertion sort for small arrays
+ if (len <= SIMPLE_LENGTH) {
+ for (int i = fromIndex + 1; i < toIndex; i++) {
+ Comparable<Object> current = (Comparable<Object>) out[i];
+ Object prev = out[i - 1];
+ if (current.compareTo(prev) < 0) {
+ int j = i;
+ do {
out[j--] = prev;
- } while (j > fromIndex
- && current.compareTo(prev = out[j - 1]) < 0);
- out[j] = current;
- }
- }
- return;
- }
- int med = (toIndex + fromIndex) >> 1;
- mergeSort(out, in, fromIndex, med);
- mergeSort(out, in, med, toIndex);
-
- // merging
-
- //if arrays are already sorted - no merge
- if (((Comparable<Object>)in[med]).compareTo(in[med - 1]) >= 0) {
- System.arraycopy(in, fromIndex, out, fromIndex, len);
- return;
- }
- int r = med, i = fromIndex;
-
- // use merging with exponential search
- do {
- Comparable<Object> fromVal = (Comparable<Object>)in[fromIndex];
- Comparable<Object> rVal = (Comparable<Object>) in[r];
- if (fromVal.compareTo(rVal) <= 0) {
- int l_1 = find(in,rVal,-1,fromIndex+1,med-1);
- int toCopy = l_1 - fromIndex + 1;
- System.arraycopy(in, fromIndex, out, i, toCopy);
- i += toCopy;
- out[i++] = rVal;
- r++;
- fromIndex = l_1+1;
- } else {
- int r_1 = find(in,fromVal,0,r+1,toIndex-1);
- int toCopy = r_1 - r + 1;
- System.arraycopy(in, r, out, i, toCopy);
- i += toCopy;
- out[i++] = fromVal;
- fromIndex++;
- r = r_1+1;
- }
- } while ((toIndex - r) > 0 && (med - fromIndex) > 0);
+ } while (j > fromIndex
+ && current.compareTo(prev = out[j - 1]) < 0);
+ out[j] = current;
+ }
+ }
+ return;
+ }
+ int med = (toIndex + fromIndex) >> 1;
+ mergeSort(out, in, fromIndex, med);
+ mergeSort(out, in, med, toIndex);
+
+ // merging
+
+ // if arrays are already sorted - no merge
+ if (((Comparable<Object>) in[med]).compareTo(in[med - 1]) >= 0) {
+ System.arraycopy(in, fromIndex, out, fromIndex, len);
+ return;
+ }
+ int r = med, i = fromIndex;
+
+ // use merging with exponential search
+ do {
+ Comparable<Object> fromVal = (Comparable<Object>) in[fromIndex];
+ Comparable<Object> rVal = (Comparable<Object>) in[r];
+ if (fromVal.compareTo(rVal) <= 0) {
+ int l_1 = find(in, rVal, -1, fromIndex + 1, med - 1);
+ int toCopy = l_1 - fromIndex + 1;
+ System.arraycopy(in, fromIndex, out, i, toCopy);
+ i += toCopy;
+ out[i++] = rVal;
+ r++;
+ fromIndex = l_1 + 1;
+ } else {
+ int r_1 = find(in, fromVal, 0, r + 1, toIndex - 1);
+ int toCopy = r_1 - r + 1;
+ System.arraycopy(in, r, out, i, toCopy);
+ i += toCopy;
+ out[i++] = fromVal;
+ fromIndex++;
+ r = r_1 + 1;
+ }
+ } while ((toIndex - r) > 0 && (med - fromIndex) > 0);
// copy rest of array
- if ((toIndex - r) <= 0) {
- System.arraycopy(in, fromIndex, out, i, med - fromIndex);
- } else {
- System.arraycopy(in, r, out, i, toIndex - r);
- }
- }
-
- /**
- * Sorts the specified range of the specified array of objects. The range to
- * be sorted extends from index fromIndex, inclusive, to index toIndex,
- * exclusive. (If fromIndex==toIndex, the range to be sorted is empty.) This
- * sort is guaranteed to be stable: equal elements will not be reordered as
- * a result of the sort.
- *
- * The sorting algorithm is a mergesort with exponential search (in which
- * the merge is performed by exponential search). This algorithm offers
- * guaranteed n*log(n) performance and in average case faster then any
- * mergesort in which the merge is performed by linear search.
- *
- * @param in -
- * the array for sorting.
- * @param out -
- * the result, sorted array.
- * @param fromIndex -
- * the index of the first element (inclusive) to be sorted.
- * @param toIndex -
- * the index of the last element (exclusive) to be sorted.
- * @param c -
- * the comparator to determine the order of the array.
- */
- @SuppressWarnings("unchecked")
+ if ((toIndex - r) <= 0) {
+ System.arraycopy(in, fromIndex, out, i, med - fromIndex);
+ } else {
+ System.arraycopy(in, r, out, i, toIndex - r);
+ }
+ }
+
+ /**
+ * Sorts the specified range of the specified array of objects. The range to
+ * be sorted extends from index fromIndex, inclusive, to index toIndex,
+ * exclusive. (If fromIndex==toIndex, the range to be sorted is empty.) This
+ * sort is guaranteed to be stable: equal elements will not be reordered as
+ * a result of the sort.
+ *
+ * The sorting algorithm is a mergesort with exponential search (in which
+ * the merge is performed by exponential search). This algorithm offers
+ * guaranteed n*log(n) performance and in average case faster then any
+ * mergesort in which the merge is performed by linear search.
+ *
+ * @param in -
+ * the array for sorting.
+ * @param out -
+ * the result, sorted array.
+ * @param fromIndex -
+ * the index of the first element (inclusive) to be sorted.
+ * @param toIndex -
+ * the index of the last element (exclusive) to be sorted.
+ * @param c -
+ * the comparator to determine the order of the array.
+ */
+ @SuppressWarnings("unchecked")
private static void mergeSort(Object[] in, Object[] out, int fromIndex,
- int toIndex, Comparator c) {
- int len = toIndex - fromIndex;
- //use insertion sort for small arrays
- if (len <= SIMPLE_LENGTH) {
- for (int i = fromIndex + 1; i < toIndex; i++) {
- Object current = out[i];
- Object prev = out[i - 1];
- if (c.compare(prev, current) > 0) {
- int j = i;
- do {
+ int toIndex, Comparator c) {
+ int len = toIndex - fromIndex;
+ // use insertion sort for small arrays
+ if (len <= SIMPLE_LENGTH) {
+ for (int i = fromIndex + 1; i < toIndex; i++) {
+ Object current = out[i];
+ Object prev = out[i - 1];
+ if (c.compare(prev, current) > 0) {
+ int j = i;
+ do {
out[j--] = prev;
- } while (j > fromIndex
- && (c.compare(prev = out[j - 1], current) > 0));
- out[j] = current;
- }
- }
- return;
- }
- int med = (toIndex + fromIndex) >> 1;
- mergeSort(out, in, fromIndex, med,c);
- mergeSort(out, in, med, toIndex,c);
-
- // merging
-
- //if arrays are already sorted - no merge
- if (c.compare(in[med],in[med - 1]) >= 0) {
- System.arraycopy(in, fromIndex, out, fromIndex, len);
- return;
- }
- int r = med, i = fromIndex;
-
- // use merging with exponential search
- do {
- Object fromVal = in[fromIndex];
- Object rVal = in[r];
- if (c.compare(fromVal,rVal) <= 0) {
- int l_1 = find(in,rVal,-1,fromIndex+1,med-1,c);
- int toCopy = l_1 - fromIndex + 1;
- System.arraycopy(in, fromIndex, out, i, toCopy);
- i += toCopy;
- out[i++] = rVal;
- r++;
- fromIndex = l_1+1;
- } else {
- int r_1 = find(in,fromVal,0,r+1,toIndex-1,c);
- int toCopy = r_1 - r + 1;
- System.arraycopy(in, r, out, i, toCopy);
- i += toCopy;
- out[i++] = fromVal;
- fromIndex++;
- r = r_1+1;
- }
- } while ((toIndex - r) > 0 && (med - fromIndex) > 0);
+ } while (j > fromIndex
+ && (c.compare(prev = out[j - 1], current) > 0));
+ out[j] = current;
+ }
+ }
+ return;
+ }
+ int med = (toIndex + fromIndex) >> 1;
+ mergeSort(out, in, fromIndex, med, c);
+ mergeSort(out, in, med, toIndex, c);
+
+ // merging
+
+ // if arrays are already sorted - no merge
+ if (c.compare(in[med], in[med - 1]) >= 0) {
+ System.arraycopy(in, fromIndex, out, fromIndex, len);
+ return;
+ }
+ int r = med, i = fromIndex;
+
+ // use merging with exponential search
+ do {
+ Object fromVal = in[fromIndex];
+ Object rVal = in[r];
+ if (c.compare(fromVal, rVal) <= 0) {
+ int l_1 = find(in, rVal, -1, fromIndex + 1, med - 1, c);
+ int toCopy = l_1 - fromIndex + 1;
+ System.arraycopy(in, fromIndex, out, i, toCopy);
+ i += toCopy;
+ out[i++] = rVal;
+ r++;
+ fromIndex = l_1 + 1;
+ } else {
+ int r_1 = find(in, fromVal, 0, r + 1, toIndex - 1, c);
+ int toCopy = r_1 - r + 1;
+ System.arraycopy(in, r, out, i, toCopy);
+ i += toCopy;
+ out[i++] = fromVal;
+ fromIndex++;
+ r = r_1 + 1;
+ }
+ } while ((toIndex - r) > 0 && (med - fromIndex) > 0);
// copy rest of array
- if ((toIndex - r) <= 0) {
- System.arraycopy(in, fromIndex, out, i, med - fromIndex);
- } else {
- System.arraycopy(in, r, out, i, toIndex - r);
- }
- }
-
- /**
- * Finds the place of specified range of specified sorted array, where the
- * element should be inserted for getting sorted array. Uses exponential
- * search algorithm.
- *
- * @param arr - the array with already sorted range
- *
- * @param val - object to be inserted
- *
- * @param l - the index of the first element (inclusive)
- *
- * @param r - the index of the last element (inclusive)
- *
- * @param bnd - possible values 0,-1. "-1" - val is located at index more
- * then elements equals to val. "0" - val is located at index less then
- * elements equals to val.
- *
- */
- @SuppressWarnings("unchecked")
- private static int find(Object[] arr, Comparable val, int bnd, int l, int r){
- int m = l ;
- int d = 1;
- while (m <= r) {
- if (val.compareTo(arr[m]) > bnd) {
- l=m+1;
- } else {
- r=m-1;
+ if ((toIndex - r) <= 0) {
+ System.arraycopy(in, fromIndex, out, i, med - fromIndex);
+ } else {
+ System.arraycopy(in, r, out, i, toIndex - r);
+ }
+ }
+
+ /**
+ * Finds the place of specified range of specified sorted array, where the
+ * element should be inserted for getting sorted array. Uses exponential
+ * search algorithm.
+ *
+ * @param arr -
+ * the array with already sorted range
+ *
+ * @param val -
+ * object to be inserted
+ *
+ * @param l -
+ * the index of the first element (inclusive)
+ *
+ * @param r -
+ * the index of the last element (inclusive)
+ *
+ * @param bnd -
+ * possible values 0,-1. "-1" - val is located at index more then
+ * elements equals to val. "0" - val is located at index less
+ * then elements equals to val.
+ *
+ */
+ @SuppressWarnings("unchecked")
+ private static int find(Object[] arr, Comparable val, int bnd, int l, int r) {
+ int m = l;
+ int d = 1;
+ while (m <= r) {
+ if (val.compareTo(arr[m]) > bnd) {
+ l = m + 1;
+ } else {
+ r = m - 1;
break;
- }
- m+=d;
- d<<=1;
- }
- while (l <= r) {
- m = (l + r) >> 1;
- if (val.compareTo(arr[m]) > bnd) {
- l = m+1;
- } else {
- r = m-1;
- }
- }
- return l-1;
- }
-
- /**
- * Finds the place of specified range of specified sorted array, where the
- * element should be inserted for getting sorted array. Uses expionential
- * search algorithm.
- *
- * @param arr - the array with already sorted range
- *
- * @param val - object to be inserted
- *
- * @param l - the index of the first element (inclusive)
- *
- * @param r - the index of the last element (inclusive)
- *
- * @param bnd - possible values 0,-1. "-1" - val is located at index more
- * then elements equals to val. "0" - val is located at index less then
- * elements equals to val.
- *
- * @param c -
- * the comparator to determine the order of the array.
- */
- @SuppressWarnings("unchecked")
- private static int find(Object[] arr, Object val, int bnd, int l,
- int r, Comparator c){
- int m = l ;
- int d = 1;
- while (m <= r) {
- if (c.compare(val,arr[m]) > bnd) {
- l=m+1;
- } else {
- r=m-1;
+ }
+ m += d;
+ d <<= 1;
+ }
+ while (l <= r) {
+ m = (l + r) >> 1;
+ if (val.compareTo(arr[m]) > bnd) {
+ l = m + 1;
+ } else {
+ r = m - 1;
+ }
+ }
+ return l - 1;
+ }
+
+ /**
+ * Finds the place of specified range of specified sorted array, where the
+ * element should be inserted for getting sorted array. Uses expionential
+ * search algorithm.
+ *
+ * @param arr -
+ * the array with already sorted range
+ *
+ * @param val -
+ * object to be inserted
+ *
+ * @param l -
+ * the index of the first element (inclusive)
+ *
+ * @param r -
+ * the index of the last element (inclusive)
+ *
+ * @param bnd -
+ * possible values 0,-1. "-1" - val is located at index more then
+ * elements equals to val. "0" - val is located at index less
+ * then elements equals to val.
+ *
+ * @param c -
+ * the comparator to determine the order of the array.
+ */
+ @SuppressWarnings("unchecked")
+ private static int find(Object[] arr, Object val, int bnd, int l, int r,
+ Comparator c) {
+ int m = l;
+ int d = 1;
+ while (m <= r) {
+ if (c.compare(val, arr[m]) > bnd) {
+ l = m + 1;
+ } else {
+ r = m - 1;
break;
- }
- m+=d;
- d<<=1;
- }
- while (l <= r) {
- m = (l + r) >> 1;
- if (c.compare(val,arr[m]) > bnd) {
- l = m+1;
- } else {
- r = m-1;
- }
- }
- return l-1;
- }
-
- /*
- * returns the median index.
- */
- private static int medChar(int a, int b, int c, String[] arr, int id) {
- int ac = charAt(arr[a], id);
- int bc = charAt(arr[b], id);
- int cc = charAt(arr[c], id);
- return ac < bc ? (bc < cc ? b : (ac < cc ? c : a))
- : (bc < cc ? (ac < cc ? a : c) : b);
-
- }
-
- /*
- * Returns the char value at the specified index of string or -1 if the
- * index more than the length of this string.
- */
+ }
+ m += d;
+ d <<= 1;
+ }
+ while (l <= r) {
+ m = (l + r) >> 1;
+ if (c.compare(val, arr[m]) > bnd) {
+ l = m + 1;
+ } else {
+ r = m - 1;
+ }
+ }
+ return l - 1;
+ }
+
+ /*
+ * returns the median index.
+ */
+ private static int medChar(int a, int b, int c, String[] arr, int id) {
+ int ac = charAt(arr[a], id);
+ int bc = charAt(arr[b], id);
+ int cc = charAt(arr[c], id);
+ return ac < bc ? (bc < cc ? b : (ac < cc ? c : a))
+ : (bc < cc ? (ac < cc ? a : c) : b);
+
+ }
+
+ /*
+ * Returns the char value at the specified index of string or -1 if the
+ * index more than the length of this string.
+ */
private static int charAt(String str, int i) {
- if (i >= str.length()) {
- return -1;
- }
- return str.charAt(i);
- }
-
- /**
- * Copies object from one array to another array with reverse of objects
- * order. Source and destination arrays may be the same.
- *
- * @param src -
- * the source array.
- * @param from -
- * starting position in the source array.
- * @param dst -
- * the destination array.
- * @param to -
- * starting position in the destination array.
- * @param len -
- * the number of array elements to be copied.
- */
+ if (i >= str.length()) {
+ return -1;
+ }
+ return str.charAt(i);
+ }
+
+ /**
+ * Copies object from one array to another array with reverse of objects
+ * order. Source and destination arrays may be the same.
+ *
+ * @param src -
+ * the source array.
+ * @param from -
+ * starting position in the source array.
+ * @param dst -
+ * the destination array.
+ * @param to -
+ * starting position in the destination array.
+ * @param len -
+ * the number of array elements to be copied.
+ */
private static void copySwap(Object[] src, int from, Object[] dst, int to,
- int len) {
- if (src == dst && from + len > to) {
- int new_to = to + len - 1;
- for (; from < to; from++, new_to--, len--) {
- dst[new_to] = src[from];
- }
- for (; len > 1; from++, new_to--, len -= 2) {
- swap(from, new_to, dst);
- }
-
- } else {
- to = to + len - 1;
- for (; len > 0; from++, to--, len--) {
- dst[to] = src[from];
- }
- }
- }
-
- /**
- * Sorts the specified range of the specified array of String.
- *
- * @param arr -
- * the array to be sorted
- * @param fromIndex -
- * the index of the first element (inclusive) to be sorted.
- * @param toIndex -
- * the index of the last element (exclusive) to be sorted.
- */
- private static void stableStringSort(String[] arr, int fromIndex,
- int toIndex) {
- stableStringSort(arr, arr, new String[toIndex], fromIndex, toIndex, 0);
- }
-
- /**
- * Sorts the specified range of the specified array of String. Use stable
- * ternary quick sort algorithm.
- *
- * @param arr -
- * the array to be sorted
- * @param src -
- * auxiliary array
- * @param dst -
- * auxiliary array
- * @param fromIndex -
- * the index of the first element (inclusive) to be sorted.
- * @param toIndex -
- * the index of the last element (exclusive) to be sorted.
- * @param chId -
- * index of char for current sorting
- */
- private static void stableStringSort(String[] arr, String[] src,
- String[] dst, int fromIndex, int toIndex, int chId) {
- int length = toIndex - fromIndex;
- //use insertion sort for small arrays
- if (length < SIMPLE_LENGTH) {
- if (src == arr) {
- for (int i = fromIndex + 1; i < toIndex; i++) {
- String current = arr[i];
- String prev = arr[i - 1];
- if (current.compareTo(prev) < 0) {
- int j = i;
- do {
- arr[j--] = prev;
- } while (j > fromIndex
- && current.compareTo(prev = arr[j - 1]) < 0);
- arr[j] = current;
- }
- }
- } else {
- int end = toIndex - 1;
- dst[fromIndex] = src[end--];
- for (int i = fromIndex + 1; i < toIndex; i++, end--) {
- String current = src[end];
- String prev;
- int j = i;
- while (j > fromIndex && current.compareTo(prev = dst[j - 1]) < 0) {
- dst[j--] = prev;
- }
- dst[j] = current;
- }
- }
- return;
- }
- // Approximate median
- int s;
- int mid = fromIndex + length / 2;
- int lo = fromIndex;
- int hi = toIndex - 1;
- if (length > 40) {
- s = length / 8;
- lo = medChar(lo, lo + s, lo + s * 2, src, chId);
- mid = medChar(mid - s, mid, mid + s, src, chId);
- hi = medChar(hi, hi - s, hi - s * 2, src, chId);
- }
- mid = medChar(lo, mid, hi, src, chId);
- // median found
- // create 4 pointers <a (in star of src) ,
- // =b(in start of dst), >c (in end of dst)
- // i - current element;
- int midVal = charAt(src[mid], chId);
- int a, b, c;
- a = b = fromIndex;
- c = toIndex - 1;
- int cmp;
-
- for (int i = fromIndex; i < toIndex; i++) {
- String el = src[i];
- cmp = charAt(el, chId) - midVal;
- if (cmp < 0) {
- src[a] = el;
- a++;
- } else if (cmp > 0) {
- dst[c] = el;
- c--;
- } else {
- dst[b] = el;
- b++;
- }
- }
-
- s = b - fromIndex;
- if (s > 0) {
- if (arr == src) {
- System.arraycopy(dst, fromIndex, arr, a, s);
- } else {
- copySwap(dst, fromIndex, arr, a, s);
- }
-
- if (b >= toIndex && midVal == -1) {
- return;
- }
- stableStringSort(arr, arr, arr == dst ? src : dst, a, a + s,
- chId + 1);
- }
-
- s = a - fromIndex;
- if (s > 0) {
- stableStringSort(arr, src, dst, fromIndex, a, chId);
- }
-
- c++;
- s = toIndex - c;
- if (s > 0) {
- stableStringSort(arr, dst, src, c, toIndex, chId);
- }
- }
+ int len) {
+ if (src == dst && from + len > to) {
+ int new_to = to + len - 1;
+ for (; from < to; from++, new_to--, len--) {
+ dst[new_to] = src[from];
+ }
+ for (; len > 1; from++, new_to--, len -= 2) {
+ swap(from, new_to, dst);
+ }
+
+ } else {
+ to = to + len - 1;
+ for (; len > 0; from++, to--, len--) {
+ dst[to] = src[from];
+ }
+ }
+ }
+
+ /**
+ * Sorts the specified range of the specified array of String.
+ *
+ * @param arr -
+ * the array to be sorted
+ * @param fromIndex -
+ * the index of the first element (inclusive) to be sorted.
+ * @param toIndex -
+ * the index of the last element (exclusive) to be sorted.
+ */
+ private static void stableStringSort(String[] arr, int fromIndex,
+ int toIndex) {
+ stableStringSort(arr, arr, new String[toIndex], fromIndex, toIndex, 0);
+ }
+
+ /**
+ * Sorts the specified range of the specified array of String. Use stable
+ * ternary quick sort algorithm.
+ *
+ * @param arr -
+ * the array to be sorted
+ * @param src -
+ * auxiliary array
+ * @param dst -
+ * auxiliary array
+ * @param fromIndex -
+ * the index of the first element (inclusive) to be sorted.
+ * @param toIndex -
+ * the index of the last element (exclusive) to be sorted.
+ * @param chId -
+ * index of char for current sorting
+ */
+ private static void stableStringSort(String[] arr, String[] src,
+ String[] dst, int fromIndex, int toIndex, int chId) {
+ int length = toIndex - fromIndex;
+ // use insertion sort for small arrays
+ if (length < SIMPLE_LENGTH) {
+ if (src == arr) {
+ for (int i = fromIndex + 1; i < toIndex; i++) {
+ String current = arr[i];
+ String prev = arr[i - 1];
+ if (current.compareTo(prev) < 0) {
+ int j = i;
+ do {
+ arr[j--] = prev;
+ } while (j > fromIndex
+ && current.compareTo(prev = arr[j - 1]) < 0);
+ arr[j] = current;
+ }
+ }
+ } else {
+ int end = toIndex - 1;
+ dst[fromIndex] = src[end--];
+ for (int i = fromIndex + 1; i < toIndex; i++, end--) {
+ String current = src[end];
+ String prev;
+ int j = i;
+ while (j > fromIndex
+ && current.compareTo(prev = dst[j - 1]) < 0) {
+ dst[j--] = prev;
+ }
+ dst[j] = current;
+ }
+ }
+ return;
+ }
+ // Approximate median
+ int s;
+ int mid = fromIndex + length / 2;
+ int lo = fromIndex;
+ int hi = toIndex - 1;
+ if (length > 40) {
+ s = length / 8;
+ lo = medChar(lo, lo + s, lo + s * 2, src, chId);
+ mid = medChar(mid - s, mid, mid + s, src, chId);
+ hi = medChar(hi, hi - s, hi - s * 2, src, chId);
+ }
+ mid = medChar(lo, mid, hi, src, chId);
+ // median found
+ // create 4 pointers <a (in star of src) ,
+ // =b(in start of dst), >c (in end of dst)
+ // i - current element;
+ int midVal = charAt(src[mid], chId);
+ int a, b, c;
+ a = b = fromIndex;
+ c = toIndex - 1;
+ int cmp;
+
+ for (int i = fromIndex; i < toIndex; i++) {
+ String el = src[i];
+ cmp = charAt(el, chId) - midVal;
+ if (cmp < 0) {
+ src[a] = el;
+ a++;
+ } else if (cmp > 0) {
+ dst[c] = el;
+ c--;
+ } else {
+ dst[b] = el;
+ b++;
+ }
+ }
+
+ s = b - fromIndex;
+ if (s > 0) {
+ if (arr == src) {
+ System.arraycopy(dst, fromIndex, arr, a, s);
+ } else {
+ copySwap(dst, fromIndex, arr, a, s);
+ }
+
+ if (b >= toIndex && midVal == -1) {
+ return;
+ }
+ stableStringSort(arr, arr, arr == dst ? src : dst, a, a + s,
+ chId + 1);
+ }
+
+ s = a - fromIndex;
+ if (s > 0) {
+ stableStringSort(arr, src, dst, fromIndex, a, chId);
+ }
+
+ c++;
+ s = toIndex - c;
+ if (s > 0) {
+ stableStringSort(arr, dst, src, c, toIndex, chId);
+ }
+ }
/**
* Sorts the specified range in the array using the specified Comparator.
@@ -2864,12 +2877,12 @@
private static <T> void sort(int start, int end, T[] array,
Comparator<? super T> comparator) {
if (comparator == null) {
- sort(start, end, array);
+ sort(start, end, array);
} else {
- int length = end - start;
- Object[] out = new Object[end];
- System.arraycopy(array, start, out, start, length);
- mergeSort(out, array, start, end, comparator);
+ int length = end - start;
+ Object[] out = new Object[end];
+ System.arraycopy(array, start, out, start, length);
+ mergeSort(out, array, start, end, comparator);
}
}
@@ -3018,16 +3031,16 @@
*/
public static String toString(boolean[] array) {
if (array == null) {
- return "null";
+ return "null"; //$NON-NLS-1$
}
if (array.length == 0) {
- return "[]";
+ return "[]"; //$NON-NLS-1$
}
StringBuilder sb = new StringBuilder(2 + array.length * 5);
sb.append('[');
sb.append(array[0]);
for (int i = 1; i < array.length; i++) {
- sb.append(", ");
+ sb.append(", "); //$NON-NLS-1$
sb.append(array[i]);
}
sb.append(']');
@@ -3051,16 +3064,16 @@
*/
public static String toString(byte[] array) {
if (array == null) {
- return "null";
+ return "null"; //$NON-NLS-1$
}
if (array.length == 0) {
- return "[]";
+ return "[]"; //$NON-NLS-1$
}
StringBuilder sb = new StringBuilder(2 + array.length * 3);
sb.append('[');
sb.append(array[0]);
for (int i = 1; i < array.length; i++) {
- sb.append(", ");
+ sb.append(", "); //$NON-NLS-1$
sb.append(array[i]);
}
sb.append(']');
@@ -3084,16 +3097,16 @@
*/
public static String toString(char[] array) {
if (array == null) {
- return "null";
+ return "null"; //$NON-NLS-1$
}
if (array.length == 0) {
- return "[]";
+ return "[]"; //$NON-NLS-1$
}
StringBuilder sb = new StringBuilder(2 + array.length * 2);
sb.append('[');
sb.append(array[0]);
for (int i = 1; i < array.length; i++) {
- sb.append(", ");
+ sb.append(", "); //$NON-NLS-1$
sb.append(array[i]);
}
sb.append(']');
@@ -3117,16 +3130,16 @@
*/
public static String toString(double[] array) {
if (array == null) {
- return "null";
+ return "null"; //$NON-NLS-1$
}
if (array.length == 0) {
- return "[]";
+ return "[]"; //$NON-NLS-1$
}
StringBuilder sb = new StringBuilder(2 + array.length * 5);
sb.append('[');
sb.append(array[0]);
for (int i = 1; i < array.length; i++) {
- sb.append(", ");
+ sb.append(", "); //$NON-NLS-1$
sb.append(array[i]);
}
sb.append(']');
@@ -3150,16 +3163,16 @@
*/
public static String toString(float[] array) {
if (array == null) {
- return "null";
+ return "null"; //$NON-NLS-1$
}
if (array.length == 0) {
- return "[]";
+ return "[]"; //$NON-NLS-1$
}
StringBuilder sb = new StringBuilder(2 + array.length * 5);
sb.append('[');
sb.append(array[0]);
for (int i = 1; i < array.length; i++) {
- sb.append(", ");
+ sb.append(", "); //$NON-NLS-1$
sb.append(array[i]);
}
sb.append(']');
@@ -3183,16 +3196,16 @@
*/
public static String toString(int[] array) {
if (array == null) {
- return "null";
+ return "null"; //$NON-NLS-1$
}
if (array.length == 0) {
- return "[]";
+ return "[]"; //$NON-NLS-1$
}
StringBuilder sb = new StringBuilder(2 + array.length * 4);
sb.append('[');
sb.append(array[0]);
for (int i = 1; i < array.length; i++) {
- sb.append(", ");
+ sb.append(", "); //$NON-NLS-1$
sb.append(array[i]);
}
sb.append(']');
@@ -3216,16 +3229,16 @@
*/
public static String toString(long[] array) {
if (array == null) {
- return "null";
+ return "null"; //$NON-NLS-1$
}
if (array.length == 0) {
- return "[]";
+ return "[]"; //$NON-NLS-1$
}
StringBuilder sb = new StringBuilder(2 + array.length * 4);
sb.append('[');
sb.append(array[0]);
for (int i = 1; i < array.length; i++) {
- sb.append(", ");
+ sb.append(", "); //$NON-NLS-1$
sb.append(array[i]);
}
sb.append(']');
@@ -3249,16 +3262,16 @@
*/
public static String toString(short[] array) {
if (array == null) {
- return "null";
+ return "null"; //$NON-NLS-1$
}
if (array.length == 0) {
- return "[]";
+ return "[]"; //$NON-NLS-1$
}
StringBuilder sb = new StringBuilder(2 + array.length * 4);
sb.append('[');
sb.append(array[0]);
for (int i = 1; i < array.length; i++) {
- sb.append(", ");
+ sb.append(", "); //$NON-NLS-1$
sb.append(array[i]);
}
sb.append(']');
@@ -3282,16 +3295,16 @@
*/
public static String toString(Object[] array) {
if (array == null) {
- return "null";
+ return "null"; //$NON-NLS-1$
}
if (array.length == 0) {
- return "[]";
+ return "[]"; //$NON-NLS-1$
}
StringBuilder sb = new StringBuilder(2 + array.length * 5);
sb.append('[');
sb.append(array[0]);
for (int i = 1; i < array.length; i++) {
- sb.append(", ");
+ sb.append(", "); //$NON-NLS-1$
sb.append(array[i]);
}
sb.append(']');
@@ -3344,10 +3357,10 @@
private static String deepToStringImpl(Object[] array, Object[] origArrays,
StringBuilder sb) {
if (array == null) {
- return "null";
+ return "null"; //$NON-NLS-1$
}
if (array.length == 0) {
- return "[]";
+ return "[]"; //$NON-NLS-1$
}
if (sb == null) {
@@ -3357,13 +3370,13 @@
for (int i = 0; i < array.length; i++) {
if (i != 0) {
- sb.append(", ");
+ sb.append(", "); //$NON-NLS-1$
}
// establish current element
Object elem = array[i];
if (elem == null) {
// element is null
- sb.append("null");
+ sb.append("null"); //$NON-NLS-1$
} else {
// get the Class of the current element
Class<?> elemClass = elem.getClass();
@@ -3398,7 +3411,7 @@
// element is an Object[], so we assert that
assert elem instanceof Object[];
if (deepToStringImplContains(origArrays, elem)) {
- sb.append("[...]");
+ sb.append("[...]"); //$NON-NLS-1$
} else {
Object[] newArray = (Object[]) elem;
Object[] newOrigArrays = new Object[origArrays.length + 1];
Modified: harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/BitSet.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/BitSet.java?view=diff&rev=491834&r1=491833&r2=491834
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/BitSet.java (original)
+++ harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/BitSet.java Tue Jan 2 08:22:05 2007
@@ -17,7 +17,6 @@
package java.util;
-
import java.io.Serializable;
import org.apache.harmony.luni.util.Msg;
@@ -28,227 +27,227 @@
* size is exceeded. Growth is always rounded to a 64 bit boundary.
*/
public class BitSet implements Serializable, Cloneable {
- private static final long serialVersionUID = 7997698588986878753L;
+ private static final long serialVersionUID = 7997698588986878753L;
- //Size in bits of the data type being used in the bits array
+ // Size in bits of the data type being used in the bits array
private static final int ELM_SIZE = 64;
-
- private long[] bits;
- /**
- * 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) {
+ private long[] bits;
+
+ /**
+ * 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.
- */
- @Override
+ /**
+ * 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.
+ */
+ @Override
public Object clone() {
- try {
- BitSet clone = (BitSet) super.clone();
- clone.bits = bits.clone();
- return clone;
- } catch (CloneNotSupportedException e) {
- return null;
- }
- }
-
- /**
- * 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 whether or not this BitSet and obj are equal
- *
- * @see #hashCode
- */
- @Override
+ try {
+ BitSet clone = (BitSet) super.clone();
+ clone.bits = bits.clone();
+ return clone;
+ } catch (CloneNotSupportedException e) {
+ return null;
+ }
+ }
+
+ /**
+ * 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 whether or not this BitSet and obj are equal
+ *
+ * @see #hashCode
+ */
+ @Override
public boolean equals(Object obj) {
- if (this == 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 (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++) {
+ for (int i = length1; i < length2; i++) {
if (bsBits[i] != 0) {
return false;
}
}
- } else {
- for (int i = 0; i < length2; i++) {
+ } else {
+ for (int i = 0; i < length2; i++) {
if (bits[i] != bsBits[i]) {
return false;
}
}
- for (int i = length2; i < length1; i++) {
+ 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 accommodate 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
- */
- @Override
+ }
+ return true;
+ }
+ return false;
+ }
+
+ /**
+ * Increase the size of the internal array to accommodate 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
+ */
+ @Override
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++) {
+ 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);
- }
+ 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) {
+ /**
+ * 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;
- }
+ }
// Negative index specified
- throw new IndexOutOfBoundsException(Msg.getString("K0006"));
- }
+ throw new IndexOutOfBoundsException(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) {
- int last = (bits.length * ELM_SIZE);
- if (pos1 >= last || pos1 == pos2) {
+ /**
+ * 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) {
+ int last = (bits.length * ELM_SIZE);
+ if (pos1 >= last || pos1 == pos2) {
return new BitSet(0);
}
- if (pos2 > last) {
+ if (pos2 > last) {
pos2 = last;
}
- int idx1 = pos1 / ELM_SIZE;
- int idx2 = (pos2 - 1) / ELM_SIZE;
- long factor1 = (~0L) << (pos1 % ELM_SIZE);
- long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
-
- if (idx1 == idx2) {
- long result = (bits[idx1] & (factor1 & factor2)) >>> (pos1 % ELM_SIZE);
- return new BitSet(new long[] { result });
- }
+ int idx1 = pos1 / ELM_SIZE;
+ int idx2 = (pos2 - 1) / ELM_SIZE;
+ long factor1 = (~0L) << (pos1 % ELM_SIZE);
+ long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
+
+ if (idx1 == idx2) {
+ long result = (bits[idx1] & (factor1 & factor2)) >>> (pos1 % ELM_SIZE);
+ return new BitSet(new long[] { result });
+ }
long[] newbits = new long[idx2 - idx1 + 1];
// first fill in the first and last indexes in the new bitset
newbits[0] = bits[idx1] & factor1;
@@ -263,573 +262,573 @@
// % 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) {
+ 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);
- }
- throw new IndexOutOfBoundsException(Msg.getString("K0006"));
- }
-
- /**
- * 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) {
+ }
+ throw new IndexOutOfBoundsException(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 {
+ bits[pos / ELM_SIZE] |= 1L << (pos % ELM_SIZE);
+ } else {
throw new IndexOutOfBoundsException(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) {
+ /**
+ * 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 (pos1 == pos2) {
+ /**
+ * 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 (pos1 == pos2) {
return;
}
- if (pos2 >= bits.length * ELM_SIZE) {
+ if (pos2 >= bits.length * ELM_SIZE) {
growBits(pos2);
}
- int idx1 = pos1 / ELM_SIZE;
- int idx2 = (pos2 - 1) / ELM_SIZE;
- long factor1 = (~0L) << (pos1 % ELM_SIZE);
- long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
+ int idx1 = pos1 / ELM_SIZE;
+ int idx2 = (pos2 - 1) / ELM_SIZE;
+ long factor1 = (~0L) << (pos1 % ELM_SIZE);
+ long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
- if (idx1 == idx2) {
+ if (idx1 == idx2) {
bits[idx1] |= (factor1 & factor2);
} else {
- bits[idx1] |= factor1;
- bits[idx2] |= factor2;
- for (int i = idx1 + 1; i < idx2; i++) {
+ bits[idx1] |= factor1;
+ bits[idx2] |= factor2;
+ for (int i = idx1 + 1; i < idx2; i++) {
bits[i] |= (~0L);
}
- }
- } else {
- throw new IndexOutOfBoundsException(Msg.getString("K0006"));
- }
- }
-
- /**
- * 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) {
+ }
+ } else {
+ throw new IndexOutOfBoundsException(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) {
+ /**
+ * 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 {
+ } else {
// Negative index specified
- throw new IndexOutOfBoundsException(Msg.getString("K0006"));
+ throw new IndexOutOfBoundsException(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) {
- int last = (bits.length * ELM_SIZE);
- if (pos1 >= last || pos1 == pos2) {
+ /**
+ * 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) {
+ int last = (bits.length * ELM_SIZE);
+ if (pos1 >= last || pos1 == pos2) {
return;
}
- if (pos2 > last) {
+ if (pos2 > last) {
pos2 = last;
}
- int idx1 = pos1 / ELM_SIZE;
- int idx2 = (pos2 - 1) / ELM_SIZE;
- long factor1 = (~0L) << (pos1 % ELM_SIZE);
- long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
+ int idx1 = pos1 / ELM_SIZE;
+ int idx2 = (pos2 - 1) / ELM_SIZE;
+ long factor1 = (~0L) << (pos1 % ELM_SIZE);
+ long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
- if (idx1 == idx2) {
+ if (idx1 == idx2) {
bits[idx1] &= ~(factor1 & factor2);
} else {
- bits[idx1] &= ~factor1;
- bits[idx2] &= ~factor2;
- for (int i = idx1 + 1; i < idx2; i++) {
+ bits[idx1] &= ~factor1;
+ bits[idx2] &= ~factor2;
+ for (int i = idx1 + 1; i < idx2; i++) {
bits[i] = 0L;
}
- }
- } else {
- throw new IndexOutOfBoundsException(Msg.getString("K0006"));
- }
-}
-
- /**
- * 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) {
+ }
+ } else {
+ throw new IndexOutOfBoundsException(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 {
+ bits[pos / ELM_SIZE] ^= 1L << (pos % ELM_SIZE);
+ } else {
throw new IndexOutOfBoundsException(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 (pos1 == pos2) {
+ /**
+ * 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 (pos1 == pos2) {
return;
}
- if (pos2 >= bits.length * ELM_SIZE) {
+ if (pos2 >= bits.length * ELM_SIZE) {
growBits(pos2);
}
- int idx1 = pos1 / ELM_SIZE;
- int idx2 = (pos2 - 1) / ELM_SIZE;
- long factor1 = (~0L) << (pos1 % ELM_SIZE);
- long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
+ int idx1 = pos1 / ELM_SIZE;
+ int idx2 = (pos2 - 1) / ELM_SIZE;
+ long factor1 = (~0L) << (pos1 % ELM_SIZE);
+ long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
- if (idx1 == idx2) {
+ if (idx1 == idx2) {
bits[idx1] ^= (factor1 & factor2);
} else {
- bits[idx1] ^= factor1;
- bits[idx2] ^= factor2;
- for (int i = idx1 + 1; i < idx2; i++) {
+ bits[idx1] ^= factor1;
+ bits[idx2] ^= factor2;
+ for (int i = idx1 + 1; i < idx2; i++) {
bits[i] ^= (~0L);
}
- }
- } else {
- throw new IndexOutOfBoundsException(Msg.getString("K0006"));
- }
- }
-
- /**
- * 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;
+ }
+ } else {
+ throw new IndexOutOfBoundsException(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 (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++) {
+ } else {
+ for (int i = 0; i < length2; i++) {
if ((bits[i] & bsBits[i]) != 0L) {
return true;
}
}
- }
+ }
- return false;
- }
+ 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++) {
+ /**
+ * 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++) {
+ } else {
+ for (int i = 0; i < length2; i++) {
bits[i] &= bsBits[i];
}
- for (int i = length2; i < length1; 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++) {
+ /**
+ * 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) {
+ /**
+ * 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++) {
+ 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) {
+ /**
+ * 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++) {
+ 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) {
+ /**
+ * 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) {
+ if (idx == -1) {
return 0;
}
- int i = ELM_SIZE - 1;
- long val = bits[idx];
- while ((val & (1L << i)) == 0 && i > 0) {
+ int i = ELM_SIZE - 1;
+ long val = bits[idx];
+ while ((val & (1L << i)) == 0 && i > 0) {
i--;
}
- return idx * ELM_SIZE + i + 1;
- }
+ 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.
- */
- @Override
+ /**
+ * 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.
+ */
+ @Override
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) {
+ 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) {
+ 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++) {
+ 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++;
+ while (idx < bits.length && bits[idx] == 0L) {
idx++;
}
- if (idx == bits.length) {
+ 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++) {
+ // 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;
- }
+ return -1;
+ }
throw new IndexOutOfBoundsException(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) {
+ /**
+ * 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++) {
+ 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++;
+ while (idx < bits.length && bits[idx] == (~0L)) {
idx++;
}
- if (idx == bits.length) {
+ 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++) {
+ // 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;
- }
+ return bssize;
+ }
throw new IndexOutOfBoundsException(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++) {
+ /**
+ * 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;
- }
+ 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) {
+ /**
+ * 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;
- }
+ }
+ }
+ }
+ return count;
+ }
}