+ * By default, all bits in the set initially have the value {@code + * false}. + * + *
+ * Every bit set has a current size, which is the number of bits of + * space currently in use by the bit set. Note that the size is related + * to the implementation of a bit set, so it may change with + * implementation. The length of a bit set relates to logical length of + * a bit set and is defined independently of implementation. + * + *
+ * Unless otherwise noted, passing a null parameter to any of the + * methods in a {@code BitSet} will result in a {@code + * NullPointerException}. + * + *
+ * A {@code BitSet} is not safe for multithreaded use without external + * synchronization. + * + * @author Arthur van Hoff + * @author Michael McCloskey + * @author Martin Buchholz + * @since JDK1.0 + */ +public class BS implements Cloneable, JSONEncodable { + /* + * BitSets are packed into arrays of "words." + * + * An int, which consists of 32 bits, requiring 5 address bits, is used for + * the JavaScript port. + */ + private final static int ADDRESS_BITS_PER_WORD = 5; + private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD; + protected final static int BIT_INDEX_MASK = BITS_PER_WORD - 1; + + /* Used to shift left or right for a partial word mask */ + protected static final int WORD_MASK = 0xffffffff; + + + /** + * The internal field corresponding to the serialField "bits". + */ + protected int[] words; + + /** + * The number of words in the logical size of this BitSet. + */ + protected transient int wordsInUse = 0; + + /** + * Whether the size of "words" is user-specified. If so, we assume the user + * knows what he's doing and try harder to preserve it. + */ + private transient boolean sizeIsSticky = false; + + /* use serialVersionUID from JDK 1.0.2 for interoperability */ + //private static final long serialVersionUID = 7997698588986878753L; + + /** + * Given a bit index, return word index containing it. + * @param bitIndex + * @return b + */ + protected static int wordIndex(int bitIndex) { + return bitIndex >> ADDRESS_BITS_PER_WORD; + } + + /** + * Sets the field wordsInUse to the logical size in words of the bit set. + * WARNING:This method assumes that the number of words actually in use is + * less than or equal to the current value of wordsInUse! + */ + protected void recalculateWordsInUse() { + // Traverse the bitset until a used word is found + int i; + for (i = wordsInUse - 1; i >= 0; i--) + if (words[i] != 0) + break; + + wordsInUse = i + 1; // The new logical size + } + + /** + * Creates a new bit set. All bits are initially {@code false}. + */ + public BS() { + initWords(BITS_PER_WORD); + sizeIsSticky = false; + } + + /** + * Creates a bit set whose initial size is large enough to explicitly + * represent bits with indices in the range {@code 0} through {@code nbits-1}. + * All bits are initially {@code false}. + * + * @param nbits + * the initial size of the bit set + * @return bs + * @throws NegativeArraySizeException + * if the specified initial size is negative + */ + public static BS newN(int nbits) { + BS bs = new BS(); + bs.init(nbits); + return bs; + } + + protected void init(int nbits) { + // nbits can't be negative; size 0 is OK + if (nbits < 0) + throw new NegativeArraySizeException("nbits < 0: " + nbits); + initWords(nbits); + sizeIsSticky = true; + } + + private void initWords(int nbits) { + words = new int[wordIndex(nbits - 1) + 1]; + } + + /** + * Ensures that the BitSet can hold enough words. + * + * @param wordsRequired + * the minimum acceptable number of words. + */ + private void ensureCapacity(int wordsRequired) { + if (words.length < wordsRequired) { + // Allocate larger of doubled size or required size + int request = Math.max(2 * words.length, wordsRequired); + setLength(request); + sizeIsSticky = false; + } + } + + /** + * Ensures that the BitSet can accommodate a given wordIndex, temporarily + * violating the invariants. The caller must restore the invariants before + * returning to the user, possibly using recalculateWordsInUse(). + * + * @param wordIndex + * the index to be accommodated. + */ + protected void expandTo(int wordIndex) { + int wordsRequired = wordIndex + 1; + if (wordsInUse < wordsRequired) { + ensureCapacity(wordsRequired); + wordsInUse = wordsRequired; + } + } + + + /** + * Sets the bit at the specified index to {@code true}. + * + * @param bitIndex + * a bit index + * @throws IndexOutOfBoundsException + * if the specified index is negative + * @since JDK1.0 + */ + public void set(int bitIndex) { + if (bitIndex < 0) + throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex); + + int wordIndex = wordIndex(bitIndex); + expandTo(wordIndex); + + words[wordIndex] |= (1 << bitIndex); // Restores invariants + + } + + /** + * Sets the bit at the specified index to the specified value. + * + * @param bitIndex + * a bit index + * @param value + * a boolean value to set + * @throws IndexOutOfBoundsException + * if the specified index is negative + * @since 1.4 + */ + public void setBitTo(int bitIndex, boolean value) { + if (value) + set(bitIndex); + else + clear(bitIndex); + } + + /** + * Sets the bits from the specified {@code fromIndex} (inclusive) to the + * specified {@code toIndex} (exclusive) to {@code true}. + * + * @param fromIndex + * index of the first bit to be set + * @param toIndex + * index after the last bit to be set + * @throws IndexOutOfBoundsException + * if {@code fromIndex} is negative, or {@code toIndex} is negative, + * or {@code fromIndex} is larger than {@code toIndex} + * @since 1.4 + */ + public void setBits(int fromIndex, int toIndex) { + + if (fromIndex == toIndex) + return; + + // Increase capacity if necessary + int startWordIndex = wordIndex(fromIndex); + int endWordIndex = wordIndex(toIndex - 1); + expandTo(endWordIndex); + + int firstWordMask = WORD_MASK << fromIndex; + int lastWordMask = WORD_MASK >>> -toIndex; + if (startWordIndex == endWordIndex) { + // Case 1: One word + words[startWordIndex] |= (firstWordMask & lastWordMask); + } else { + // Case 2: Multiple words + // Handle first word + words[startWordIndex] |= firstWordMask; + + // Handle intermediate words, if any + for (int i = startWordIndex + 1; i < endWordIndex; i++) + words[i] = WORD_MASK; + + // Handle last word (restores invariants) + words[endWordIndex] |= lastWordMask; + } + } + + /** + * Sets the bit specified by the index to {@code false}. + * + * @param bitIndex + * the index of the bit to be cleared + * @throws IndexOutOfBoundsException + * if the specified index is negative + * @since JDK1.0 + */ + public void clear(int bitIndex) { + if (bitIndex < 0) + throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex); + + int wordIndex = wordIndex(bitIndex); + if (wordIndex >= wordsInUse) + return; + + words[wordIndex] &= ~(1 << bitIndex); + + recalculateWordsInUse(); + } + + /** + * Sets the bits from the specified {@code fromIndex} (inclusive) to the + * specified {@code toIndex} (exclusive) to {@code false}. + * + * @param fromIndex + * index of the first bit to be cleared + * @param toIndex + * index after the last bit to be cleared + * @throws IndexOutOfBoundsException + * if {@code fromIndex} is negative, or {@code toIndex} is negative, + * or {@code fromIndex} is larger than {@code toIndex} + * @since 1.4 + */ + public void clearBits(int fromIndex, int toIndex) { + if (fromIndex == toIndex) + return; + + int startWordIndex = wordIndex(fromIndex); + if (startWordIndex >= wordsInUse) + return; + + int endWordIndex = wordIndex(toIndex - 1); + if (endWordIndex >= wordsInUse) { + toIndex = length(); + endWordIndex = wordsInUse - 1; + } + + int firstWordMask = WORD_MASK << fromIndex; + int lastWordMask = WORD_MASK >>> -toIndex; + if (startWordIndex == endWordIndex) { + // Case 1: One word + words[startWordIndex] &= ~(firstWordMask & lastWordMask); + } else { + // Case 2: Multiple words + // Handle first word + words[startWordIndex] &= ~firstWordMask; + + // Handle intermediate words, if any + for (int i = startWordIndex + 1; i < endWordIndex; i++) + words[i] = 0; + + // Handle last word + words[endWordIndex] &= ~lastWordMask; + } + + recalculateWordsInUse(); + } + + /** + * Sets all of the bits in this BitSet to {@code false}. + * + * @since 1.4 + */ + public void clearAll() { + while (wordsInUse > 0) + words[--wordsInUse] = 0; + } + + /** + * Returns the value of the bit with the specified index. The value is {@code + * true} if the bit with the index {@code bitIndex} is currently set in this + * {@code BitSet}; otherwise, the result is {@code false}. + * + * @param bitIndex + * the bit index + * @return the value of the bit with the specified index + * @throws IndexOutOfBoundsException + * if the specified index is negative + */ + public boolean get(int bitIndex) { + if (bitIndex < 0) + throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex); + + int wordIndex = wordIndex(bitIndex); + return (wordIndex < wordsInUse) + && ((words[wordIndex] & (1 << bitIndex)) != 0); + } + + /** + * Returns the index of the first bit that is set to {@code true} that occurs + * on or after the specified starting index. If no such bit exists then + * {@code -1} is returned. + * + *
+ * To iterate over the {@code true} bits in a {@code BitSet}, use the + * following loop: + * + *
+ * @code
+ * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
+ * // operate on index i here
+ * }}
+ *
+ *
+ * @param fromIndex
+ * the index to start checking from (inclusive)
+ * @return the index of the next set bit, or {@code -1} if there is no such
+ * bit
+ * @throws IndexOutOfBoundsException
+ * if the specified index is negative
+ * @since 1.4
+ */
+ public int nextSetBit(int fromIndex) {
+ if (fromIndex < 0)
+ throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
+
+ int u = wordIndex(fromIndex);
+ if (u >= wordsInUse)
+ return -1;
+
+ int word = words[u] & (WORD_MASK << fromIndex);
+
+ while (true) {
+ if (word != 0)
+ return (u * BITS_PER_WORD) + Integer.numberOfTrailingZeros(word);
+ if (++u == wordsInUse)
+ return -1;
+ word = words[u];
+ }
+ }
+
+ /**
+ * Returns the index of the first bit that is set to {@code false} that occurs
+ * on or after the specified starting index.
+ *
+ * @param fromIndex
+ * the index to start checking from (inclusive)
+ * @return the index of the next clear bit
+ * @throws IndexOutOfBoundsException
+ * if the specified index is negative
+ * @since 1.4
+ */
+ public int nextClearBit(int fromIndex) {
+ // Neither spec nor implementation handle bitsets of maximal length.
+ // See 4816253.
+ if (fromIndex < 0)
+ throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
+
+ int u = wordIndex(fromIndex);
+ if (u >= wordsInUse)
+ return fromIndex;
+
+ int word = ~words[u] & (WORD_MASK << fromIndex);
+
+ while (true) {
+ if (word != 0)
+ return (u * BITS_PER_WORD) + Integer.numberOfTrailingZeros(word);
+ if (++u == wordsInUse)
+ return wordsInUse * BITS_PER_WORD;
+ word = ~words[u];
+ }
+ }
+
+ /**
+ * Returns the "logical size" of this {@code BitSet}: the index of the highest
+ * set bit in the {@code BitSet} plus one. Returns zero if the {@code BitSet}
+ * contains no set bits.
+ *
+ * @return the logical size of this {@code BitSet}
+ * @since 1.2
+ */
+ public int length() {
+ if (wordsInUse == 0)
+ return 0;
+
+ return BITS_PER_WORD * (wordsInUse - 1)
+ + (BITS_PER_WORD - Integer.numberOfLeadingZeros(words[wordsInUse - 1]));
+ }
+
+ /**
+ * Returns true if this {@code BitSet} contains no bits that are set to
+ * {@code true}.
+ *
+ * @return boolean indicating whether this {@code BitSet} is empty
+ * @since 1.4
+ */
+ public boolean isEmpty() {
+ return wordsInUse == 0;
+ }
+
+ /**
+ * Returns true if the specified {@code BitSet} has any bits set to {@code
+ * true} that are also set to {@code true} in this {@code BitSet}.
+ *
+ * @param set
+ * {@code BitSet} to intersect with
+ * @return boolean indicating whether this {@code BitSet} intersects the
+ * specified {@code BitSet}
+ * @since 1.4
+ */
+ public boolean intersects(BS set) {
+ for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
+ if ((words[i] & set.words[i]) != 0)
+ return true;
+ return false;
+ }
+
+ /**
+ * Returns the number of bits set to {@code true} in this {@code BitSet}.
+ *
+ * @return the number of bits set to {@code true} in this {@code BitSet}
+ * @since 1.4
+ */
+ public int cardinality() {
+ int sum = 0;
+ for (int i = 0; i < wordsInUse; i++)
+ sum += Integer.bitCount(words[i]);
+ return sum;
+ }
+
+ /**
+ * Performs a logical AND of this target bit set with the argument bit
+ * set. This bit set is modified so that each bit in it has the value {@code
+ * true} if and only if it both initially had the value {@code true} and the
+ * corresponding bit in the bit set argument also had the value {@code true}.
+ *
+ * @param set
+ * a bit set
+ */
+ public void and(BS set) {
+ if (this == set)
+ return;
+
+ while (wordsInUse > set.wordsInUse)
+ words[--wordsInUse] = 0;
+
+ // Perform logical AND on words in common
+ for (int i = 0; i < wordsInUse; i++)
+ words[i] &= set.words[i];
+
+ recalculateWordsInUse();
+ }
+
+ /**
+ * Performs a logical OR of this bit set with the bit set argument.
+ * This bit set is modified so that a bit in it has the value {@code true} if
+ * and only if it either already had the value {@code true} or the
+ * corresponding bit in the bit set argument has the value {@code true}.
+ *
+ * @param set
+ * a bit set
+ */
+ public void or(BS set) {
+ if (this == set)
+ return;
+
+ int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
+
+ if (wordsInUse < set.wordsInUse) {
+ ensureCapacity(set.wordsInUse);
+ wordsInUse = set.wordsInUse;
+ }
+
+ // Perform logical OR on words in common
+ for (int i = 0; i < wordsInCommon; i++)
+ words[i] |= set.words[i];
+
+ // Copy any remaining words
+ if (wordsInCommon < set.wordsInUse)
+ System.arraycopy(set.words, wordsInCommon, words, wordsInCommon,
+ wordsInUse - wordsInCommon);
+
+ }
+
+ /**
+ * Performs a logical XOR of this bit set with the bit set argument.
+ * This bit set is modified so that a bit in it has the value {@code true} if
+ * and only if one of the following statements holds:
+ * BitSet. The algorithm
+ * used to compute it may be described as follows.
+ *
+ * Suppose the bits in the BitSet were to be stored in an array
+ * of long integers called, say, words, in such a
+ * manner that bit k is set in the BitSet (for
+ * nonnegative values of k) if and only if the expression
+ *
+ *
+ * ((k >> 6) < words.length) && ((words[k >> 6] & (1 << (bit & 0x3F))) != 0) + *+ * + * is true. Then the following definition of the
hashCode method
+ * would be a correct implementation of the actual algorithm:
+ *
+ *
+ * public int hashCode() {
+ * long h = 1234;
+ * for (int i = words.length; --i >= 0;) {
+ * h ˆ= words[i] * (i + 1);
+ * }
+ * return (int) ((h >> 32) ˆ h);
+ * }
+ *
+ *
+ * Note that the hash code values change if the set of bits is altered.
+ *
+ * Overrides the hashCode method of Object.
+ *
+ * @return a hash code value for this bit set.
+ */
+ @Override
+ public int hashCode() {
+ long h = 1234;
+ for (int i = wordsInUse; --i >= 0;)
+ h ^= words[i] * (i + 1);
+
+ return (int) ((h >> 32) ^ h);
+ }
+
+ /**
+ * Returns the number of bits of space actually in use by this {@code BitSet}
+ * to represent bit values. The maximum element in the set is the size - 1st
+ * element.
+ *
+ * @return the number of bits currently in this bit set
+ */
+ public int size() {
+ return words.length * BITS_PER_WORD;
+ }
+
+ /**
+ * Compares this object against the specified object. The result is {@code
+ * true} if and only if the argument is not {@code null} and is a {@code
+ * Bitset} object that has exactly the same set of bits set to {@code true} as
+ * this bit set. That is, for every nonnegative {@code int} index {@code k},
+ *
+ *
+ * ((BitSet) obj).get(k) == this.get(k) + *+ * + * must be true. The current sizes of the two bit sets are not compared. + * + * @param obj + * the object to compare with + * @return {@code true} if the objects are the same; {@code false} otherwise + * @see #size() + */ + @Override + public boolean equals(Object obj) { + if (!(obj instanceof BS)) + return false; + if (this == obj) + return true; + + BS set = (BS) obj; + + if (wordsInUse != set.wordsInUse) + return false; + + // Check words in use by both BitSets + for (int i = 0; i < wordsInUse; i++) + if (words[i] != set.words[i]) + return false; + + return true; + } + + /** + * Cloning this {@code BitSet} produces a new {@code BitSet} that is equal to + * it. The clone of the bit set is another bit set that has exactly the same + * bits set to {@code true} as this bit set. + * + * @return a clone of this bit set + * @see #size() + */ + @Override + public Object clone() { + if (!sizeIsSticky && wordsInUse != words.length) + setLength(wordsInUse); + return copy(this); + } + + /** + * Attempts to reduce internal storage used for the bits in this bit set. + * Calling this method may, but is not required to, affect the value returned + * by a subsequent call to the {@link #size()} method. + * @param n + */ + private void setLength(int n) { + /** + * @j2sNative + * if (n == this.words.length) return; + * if (n == this.wordsInUse) { + * this.words = Clazz.array(-1, this.words, 0, n); + * return; + * } + */ + {} + int[] a = new int[n]; + System.arraycopy(words, 0, a, 0, wordsInUse); + words = a; + } + + /** + * Returns a string representation of this bit set. For every index for which + * this {@code BitSet} contains a bit in the set state, the decimal + * representation of that index is included in the result. Such indices are + * listed in order from lowest to highest, separated by ", " (a comma and + * a space) and surrounded by braces, resulting in the usual mathematical + * notation for a set of integers. + * + *
+ * Example: + * + *
+ * BitSet drPepper = new BitSet(); + *+ * + * Now {@code drPepper.toString()} returns "{}". + *
+ * + *
+ * drPepper.set(2); + *+ * + * Now {@code drPepper.toString()} returns "{2}". + *
+ * + *
+ * drPepper.set(4); + * drPepper.set(10); + *+ * + * Now {@code drPepper.toString()} returns "{2, 4, 10}". + * + * @return a string representation of this bit set + */ + @Override + public String toString() { + return escape(this, '(', ')'); + } + + private final static int[] emptyBitmap = new int[0]; + + /** + * fast copy + * + * @param bitsetToCopy + * @return bs + */ + public static BS copy(BS bitsetToCopy) { + BS bs; + /** + * Clazz.clone will copy wordsInUse and sizeIsSticky, + * but just a pointer to the words array. + * + * @j2sNative + * + * bs = Clazz.clone(bitsetToCopy); + * + */ + { + bs = new BS(); + } + int wordCount = bitsetToCopy.wordsInUse; + if (wordCount == 0) { + bs.words = emptyBitmap; + } else { + + /** + * Clazz.clone will copy wordsInUse and sizeIsSticky, + * but just a pointer to the words array. + * + * @j2sNative + * + * bs.words = Clazz.array(-1, bitsetToCopy.words, 0, bs.wordsInUse = wordCount); + * + */ + { + bs.words = new int[bs.wordsInUse = wordCount]; + System.arraycopy(bitsetToCopy.words, 0, bs.words, 0, wordCount); + } + + } + return bs; + } + + /** + * + * @param max + * @return n bits below max + */ + public int cardinalityN(int max) { + int n = cardinality(); + for (int i = length(); --i >= max;) + if (get(i)) + n--; + return n; + } + + @Override + public String toJSON() { + + int numBits = (wordsInUse > 128 ? cardinality() : wordsInUse + * BITS_PER_WORD); + SB b = SB.newN(6 * numBits + 2); + b.appendC('['); + + int i = nextSetBit(0); + if (i != -1) { + b.appendI(i); + for (i = nextSetBit(i + 1); i >= 0; i = nextSetBit(i + 1)) { + int endOfRun = nextClearBit(i); + do { + b.append(", ").appendI(i); + } while (++i < endOfRun); + } + } + + b.appendC(']'); + return b.toString(); + } + + public static String escape(BS bs, char chOpen, char chClose) { + if (bs == null) + return chOpen + "{}" + chClose; + SB s = new SB(); + s.append(chOpen + "{"); + int imax = bs.length(); + int iLast = -1; + int iFirst = -2; + int i = -1; + while (++i <= imax) { + boolean isSet = bs.get(i); + if (i == imax || iLast >= 0 && !isSet) { + if (iLast >= 0 && iFirst != iLast) + s.append((iFirst == iLast - 1 ? " " : ":") + iLast); + if (i == imax) + break; + iLast = -1; + } + if (bs.get(i)) { + if (iLast < 0) { + s.append((iFirst == -2 ? "" : " ") + i); + iFirst = i; + } + iLast = i; + } + } + s.append("}").appendC(chClose); + return s.toString(); + } + + public static BS unescape(String str) { + char ch; + int len; + if (str == null || (len = (str = str.trim()).length()) < 4 + || str.equalsIgnoreCase("({null})") + || (ch = str.charAt(0)) != '(' && ch != '[' + || str.charAt(len - 1) != (ch == '(' ? ')' : ']') + || str.charAt(1) != '{' || str.indexOf('}') != len - 2) + return null; + len -= 2; + for (int i = len; --i >= 2;) + if (((ch = str.charAt(i)) < 48 || ch > 57) && ch != ' ' && ch != '\t' + && ch != ':') + return null; + int lastN = len; + while (48 <= (ch = str.charAt(--lastN)) && ch <= 57) { + // loop + } + if (++lastN == len) + lastN = 0; + else + try { + lastN = Integer.parseInt(str.substring(lastN, len)); + } catch (NumberFormatException e) { + return null; + } + BS bs = BS.newN(lastN); + lastN = -1; + int iPrev = -1; + int iThis = -2; + for (int i = 2; i <= len; i++) { + switch (ch = str.charAt(i)) { + case '\t': + case ' ': + case '}': + if (iThis < 0) + break; + if (iThis < lastN) + return null; + lastN = iThis; + if (iPrev < 0) + iPrev = iThis; + bs.setBits(iPrev, iThis + 1); + iPrev = -1; + iThis = -2; + break; + case ':': + iPrev = lastN = iThis; + iThis = -2; + break; + default: + if (48 <= ch && ch <= 57) { + if (iThis < 0) + iThis = 0; + iThis = (iThis * 10) + (ch - 48); + } + } + } + return (iPrev >= 0 ? null : bs); + } + +}