Emulate java.util.BitSet
This emulation and its pretty thorough unit tests were originally
authored by Danny Daemonic <dannydaemonic@gmail.com> more than seven
years ago.
Many parts of the emulation have since been rewritten. It now uses a
dense int[] array instead of a sparse array to improve performance on
most modern JavaScript engines. Instead of full 32-bit integers, the
array holds 31-bit integers, which makes V8 treat them as "tagged small
integers" on 32-bit machines and improves performance dramatically.
The class does not have JSNI methods any more.
Most of the BitSet methods have been emulated. The two unimplemented
ones are:
public static BitSet valueOf(ByteBuffer)
public static BitSet valueOf(LongBuffer)
They rely on java.nio.ByteBuffer and java.nio.LongBuffer, which are not
implemented yet.
The unit tests are mostly kept as-is, besides small formatting fixes.
Authors: Danny Daemonic, Daniel Kurka, Michael Zhou, Andrei Korzhevskii
Bug: #3285
Bug-Link: https://github.com/gwtproject/gwt/issues/3285
Change-Id: I5569676ca5d3aaffe631d716b0ae2878374fc974
Review-Link: https://gwt-review.googlesource.com/#/c/5771/
diff --git a/user/super/com/google/gwt/emul/java/util/BitSet.java b/user/super/com/google/gwt/emul/java/util/BitSet.java
new file mode 100644
index 0000000..417850d
--- /dev/null
+++ b/user/super/com/google/gwt/emul/java/util/BitSet.java
@@ -0,0 +1,882 @@
+/*
+ * Copyright 2009 Google Inc.
+ *
+ * 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 static javaemul.internal.Coercions.ensureInt;
+import static javaemul.internal.InternalPreconditions.checkArraySize;
+
+import javaemul.internal.ArrayHelper;
+
+/**
+ * This implementation uses a dense array holding bit groups of size 31 to keep track of when bits
+ * are set to true or false. Using 31 bits keeps our implementation within the range of V8's
+ * "tagged small integer" and improves performance. Using a dense array also makes access faster on
+ * V8.
+ *
+ * Not yet implemented:
+ * public static BitSet valueOf(ByteBuffer)
+ * public static BitSet valueOf(LongBuffer)
+ */
+public class BitSet {
+ private static final int WORD_MASK = 0x7fffffff;
+ private static final int BITS_PER_WORD = 31;
+
+ private final int[] array;
+
+ public BitSet() {
+ array = new int[0];
+ }
+
+ public BitSet(int nbits) {
+ checkArraySize(nbits);
+ int length = wordIndex(nbits - 1) + 1;
+ array = new int[0];
+ ArrayHelper.setLength(array, length);
+ }
+
+ private BitSet(int[] array) {
+ this.array = array;
+ }
+
+ private static void checkIndex(int bitIndex) {
+ if (bitIndex < 0) {
+ throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
+ }
+ }
+
+ private static void checkRange(int fromIndex, int toIndex) {
+ if (fromIndex < 0 || toIndex < 0 || fromIndex > toIndex) {
+ throw new IndexOutOfBoundsException("fromIndex: " + fromIndex + ", toIndex: " + toIndex);
+ }
+ }
+
+ /**
+ * Converts from a bit index to a word index.
+ *
+ * @param bitIndex The bit index.
+ * @return The index of the word (array entry) holding that bit.
+ */
+ private static int wordIndex(int bitIndex) {
+ return bitIndex / BITS_PER_WORD;
+ }
+
+ /**
+ * Converts from a word index to the lowest index of the bit stored in that word.
+ *
+ * @param wordIndex The word index.
+ * @return The lowest index of the bit stored in that word.
+ */
+ private static int bitIndex(int wordIndex) {
+ return wordIndex * BITS_PER_WORD;
+ }
+
+ /**
+ * Computes the offset within a word for a bit index. Within a word, the offset counts from
+ * right to left and caps at 31. This helps leaving the highest bit as zero to ensure that
+ * each word is a tagged small integer in V8.
+ *
+ * @param bitIndex The bit index.
+ * @return The offset of the bit within a word, counting from right to left.
+ */
+ private static int bitOffset(int bitIndex) {
+ return bitIndex % BITS_PER_WORD;
+ }
+
+ /**
+ * Sets all bits to true within the given range.
+ *
+ * @param fromIndex The lower bit index.
+ * @param toIndex The upper bit index.
+ */
+ private static void setInternal(int[] array, int fromIndex, int toIndex) {
+ int first = wordIndex(fromIndex);
+ int last = wordIndex(toIndex);
+
+ maybeGrowArrayToIndex(array, last);
+
+ int startBit = bitOffset(fromIndex);
+ int endBit = bitOffset(toIndex);
+
+ if (first == last) {
+ // Set the bits in between first and last.
+ maskInWord(array, first, startBit, endBit);
+ } else {
+ // Set the bits from fromIndex to the next 31 bit boundary.
+ maskInWord(array, first, startBit, BITS_PER_WORD);
+
+ // Set the bits from the last 31 bit boundary to toIndex.
+ maskInWord(array, last, 0, endBit);
+
+ // Set everything in between.
+ for (int i = first + 1; i < last; i++) {
+ array[i] = WORD_MASK;
+ }
+ }
+ }
+
+ private static void maybeGrowArrayToIndex(int[] array, int newMaxIndex) {
+ // TODO: This code has a potential problem:
+ // If we grow the array more than 1024 places the array will degenerate into a map,
+ // we can work around this by adding 0 to the arrays.
+ int newLength = newMaxIndex + 1;
+ if (newLength > array.length) {
+ ArrayHelper.setLength(array, newLength);
+ }
+ }
+
+ /**
+ * Returns the index of the last word containing a true bit in an array, or -1 if none.
+ *
+ * @param array The array.
+ * @return The index of the last word containing a true bit, or -1 if none.
+ */
+ private static int lastSetWordIndex(int[] array) {
+ int i = array.length - 1;
+ for (; i >= 0 && wordAt(array, i) == 0; --i) { }
+ return i;
+ }
+
+ /**
+ * Flips all bits in a word within the given range.
+ *
+ * @param array The array.
+ * @param index The word index.
+ * @param from The lower bit index.
+ * @param to The upper bit index.
+ */
+ private static void flipMaskedWord(int[] array, int index, int from, int to) {
+ if (from == to) {
+ return;
+ }
+
+ to = 32 - to;
+ int word = wordAt(array, index);
+ word ^= ((0xffffffff >>> from) << (from + to)) >>> to;
+ array[index] = word & WORD_MASK;
+ }
+
+ /**
+ * Sets all bits to true in a word within the given bit range.
+ *
+ * @param array The array.
+ * @param index The word index.
+ * @param from The lower bit index.
+ * @param to The upper bit index.
+ */
+ private static void maskInWord(int[] array, int index, int from, int to) {
+ if (from == to) {
+ return;
+ }
+
+ to = 32 - to;
+ int word = wordAt(array, index);
+ word |= ((0xffffffff >>> from) << (from + to)) >>> to;
+ array[index] = word & WORD_MASK;
+ }
+
+ /**
+ * Sets all bits to false in a word within the given bit range.
+ *
+ * @param array The array.
+ * @param index The word index.
+ * @param from The lower bit index.
+ * @param to The upper bit index.
+ */
+ private static void maskOutWord(int[] array, int index, int from, int to) {
+ if (from == to) {
+ return;
+ }
+
+ int word = wordAt(array, index);
+ if (word == 0) {
+ return;
+ }
+
+ int mask;
+ if (from != 0) {
+ mask = 0xffffffff >>> (32 - from);
+ } else {
+ mask = 0;
+ }
+ // Shifting by 32 is the same as shifting by 0.
+ if (to != 32) {
+ mask |= 0xffffffff << to;
+ }
+
+ word &= mask;
+ array[index] = word & WORD_MASK;
+ }
+
+ private static int wordAt(int[] array, int index) {
+ return ensureInt(array[index]);
+ }
+
+ // GWT emulates integer with double and doesn't overflow. Enfore it by a integer mask.
+ private static int enforceOverflow(int value) {
+ return value & 0xffffffff;
+ }
+
+ public void and(BitSet set) {
+ // a & a is just a.
+ if (this == set) {
+ return;
+ }
+
+ // Truth table
+ //
+ // Case | a | b | a & b | Change?
+ // 1 | false | false | false | a is already false
+ // 2 | false | true | false | a is already false
+ // 3 | true | false | false | set a to false
+ // 4 | true | true | true | a is already true
+ //
+ // We only need to change something in case 3, so iterate over set a.
+ int limit = Math.min(array.length, set.array.length);
+ int index = 0;
+ for (; index < limit; index++) {
+ int word = wordAt(array, index);
+ if (word != 0) {
+ array[index] = word & wordAt(set.array, index);
+ }
+ }
+ Arrays.fill(array, index, array.length, 0);
+ }
+
+ public void andNot(BitSet set) {
+ // a & !a is false, and all falses result in an empty BitSet.
+ if (this == set) {
+ clear();
+ return;
+ }
+
+ // Truth table
+ //
+ // Case | a | b | !b | a & !b | Change?
+ // 1 | false | false | true | false | a is already false
+ // 2 | false | true | false | false | a is already false
+ // 3 | true | false | true | true | a is already true
+ // 4 | true | true | false | false | set a to false
+ //
+ // We only need to change something in case 4. Whenever b is true, a should be false, so
+ // iterate over set b.
+ int limit = Math.min(array.length, set.array.length);
+ for (int index = 0; index < limit; index++) {
+ int otherWord = wordAt(set.array, index);
+ if (otherWord != 0) {
+ int word = wordAt(array, index);
+ if (word != 0) {
+ array[index] = word & (~otherWord & WORD_MASK);
+ }
+ }
+ }
+ }
+
+ public int cardinality() {
+ int count = 0;
+ for (int i = 0; i < array.length; i++) {
+ count += Integer.bitCount(wordAt(array, i));
+ }
+ return count;
+ }
+
+ public void clear() {
+ ArrayHelper.setLength(array, 0);
+ }
+
+ public void clear(int bitIndex) {
+ checkIndex(bitIndex);
+
+ int index = wordIndex(bitIndex);
+ if (index >= array.length) {
+ return;
+ }
+
+ int word = wordAt(array, index);
+ if (word != 0) {
+ array[index] = word & ~(1 << bitOffset(bitIndex)) & WORD_MASK;
+ }
+ }
+
+ public void clear(int fromIndex, int toIndex) {
+ checkRange(fromIndex, toIndex);
+
+ if (fromIndex == toIndex) {
+ return;
+ }
+
+ int first = wordIndex(fromIndex);
+ if (first >= array.length) {
+ return;
+ }
+
+ int last = wordIndex(toIndex);
+ if (last >= array.length) {
+ toIndex = length();
+ last = wordIndex(toIndex);
+ }
+
+ int startBit = bitOffset(fromIndex);
+ int endBit = bitOffset(toIndex);
+
+ if (first == last) {
+ // Clear the bits in between first and last.
+ maskOutWord(array, first, startBit, endBit);
+ } else {
+ // Clear the bits from fromIndex to the next 31 bit boundary.
+ maskOutWord(array, first, startBit, BITS_PER_WORD);
+
+ // Clear the bits from the last 31 bit boundary to the toIndex.
+ maskOutWord(array, last, 0, endBit);
+
+ Arrays.fill(array, first + 1, last, 0);
+ }
+ }
+
+ public Object clone() {
+ return new BitSet(Arrays.copyOf(array, array.length));
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+
+ if (!(obj instanceof BitSet)) {
+ return false;
+ }
+
+ BitSet other = (BitSet) obj;
+
+ int lastIndex = lastSetWordIndex(array);
+ if (lastIndex != lastSetWordIndex(other.array)) {
+ return false;
+ }
+
+ for (int index = 0; index <= lastIndex; index++) {
+ if (wordAt(array, index) != wordAt(other.array, index)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ public void flip(int bitIndex) {
+ checkIndex(bitIndex);
+
+ int index = wordIndex(bitIndex);
+ int offset = bitOffset(bitIndex);
+
+ maybeGrowArrayToIndex(array, index);
+
+ int word = wordAt(array, index);
+ if (((word >>> offset) & 1) == 1) {
+ word = word & ~(1 << offset);
+ } else {
+ word = (word | (1 << offset));
+ }
+ array[index] = word & WORD_MASK;
+ }
+
+ public void flip(int fromIndex, int toIndex) {
+ checkRange(fromIndex, toIndex);
+
+ if (fromIndex == toIndex) {
+ return;
+ }
+
+ // If we are flipping bits beyond our length, we are setting them to true.
+ int length = length();
+ if (fromIndex >= length) {
+ setInternal(array, fromIndex, toIndex);
+ return;
+ }
+
+ if (toIndex >= length) {
+ setInternal(array, length, toIndex);
+ toIndex = length;
+ }
+
+ int first = wordIndex(fromIndex);
+ int last = wordIndex(toIndex);
+ int startBit = bitOffset(fromIndex);
+ int endBit = bitOffset(toIndex);
+
+ if (first == last) {
+ // Flip the bits in between first and last.
+ flipMaskedWord(array, first, startBit, endBit);
+
+ } else {
+ // Flip the bits from fromIndex to the next 31 bit boundary.
+ flipMaskedWord(array, first, startBit, BITS_PER_WORD);
+
+ // Flip the bits from the last 31 bit boundary to the toIndex.
+ flipMaskedWord(array, last, 0, endBit);
+
+ // Flip everything in between.
+ for (int i = first + 1; i < last; i++) {
+ array[i] = ~wordAt(array, i) & WORD_MASK;
+ }
+ }
+ }
+
+ public boolean get(int bitIndex) {
+ checkIndex(bitIndex);
+
+ int index = wordIndex(bitIndex);
+ // Shift and mask the bit out
+ return index < array.length && ((wordAt(array, index) >>> bitOffset(bitIndex)) & 1) == 1;
+ }
+
+ public BitSet get(int fromIndex, int toIndex) {
+ checkRange(fromIndex, toIndex);
+
+ int length = length();
+ if (length <= fromIndex || fromIndex == toIndex) {
+ return new BitSet(0);
+ }
+
+ toIndex = Math.min(toIndex, length);
+
+ // The bit shift offset for each group of bits
+ int rightShift = bitOffset(fromIndex);
+
+ if (rightShift == 0) {
+ int subFrom = wordIndex(fromIndex);
+ int subTo = wordIndex(toIndex + BITS_PER_WORD);
+ int[] subArray = Arrays.copyOfRange(array, subFrom, subTo);
+ int leftOvers = bitOffset(toIndex);
+ maskOutWord(subArray, subTo - subFrom - 1, leftOvers, BITS_PER_WORD);
+ return new BitSet(subArray);
+ }
+
+ int first = wordIndex(fromIndex);
+ int last = wordIndex(toIndex);
+
+ int[] subArray = new int[last - first + 1];
+ if (first == last) {
+ // Number of bits to cut from the end
+ int end = 32 - bitOffset(toIndex);
+ int word = wordAt(array, first);
+ subArray[0] = (word << end) >>> (rightShift + end);
+ } else {
+ // Fence post, carry over initial bits.
+ int word = wordAt(array, first);
+
+ // This holds the newly packed bits.
+ int current = word >>> rightShift;
+
+ // The raw index into the subset
+ int subIndex = 0;
+
+ // A left shift will be used to shift our bits to the top of "current".
+ int leftShift = BITS_PER_WORD - rightShift;
+
+ // Loop through everything in the middle.
+ for (int i = first + 1; i <= last; i++) {
+ word = wordAt(array, i);
+
+ // Shift out the bits from the top, OR them into current bits.
+ current |= word << leftShift;
+ subArray[subIndex++] = current & WORD_MASK;
+
+ // Carry over the unused bits.
+ current = word >>> rightShift;
+ }
+
+ // Fence post, flush out the extra bits, but don't go past the "end".
+ int end = 32 - bitOffset(toIndex);
+ current = (current << (rightShift + end)) >>> (rightShift + end);
+ subArray[subIndex] = current & WORD_MASK;
+ }
+
+ return new BitSet(subArray);
+ }
+
+ /**
+ * This hash is different than the one described in Sun's documentation. The
+ * described hash uses 64 bit integers and that's not practical in JavaScript.
+ */
+ @Override
+ public int hashCode() {
+ // FNV constants
+ final int fnvOffset = 0x811c9dc5;
+ final int fnvPrime = 0x1000193;
+
+ final int lastIndex = lastSetWordIndex(array);
+ int hash = fnvOffset ^ lastIndex;
+
+ for (int i = 0; i <= lastIndex; i++) {
+ int value = wordAt(array, i);
+ // Hash one byte at a time using FNV1 and make sure we don't overflow 32 bit int.
+ hash = enforceOverflow(hash * fnvPrime) ^ (value & 0xff);
+ hash = enforceOverflow(hash * fnvPrime) ^ ((value >>> 8) & 0xff);
+ hash = enforceOverflow(hash * fnvPrime) ^ ((value >>> 16) & 0xff);
+ hash = enforceOverflow(hash * fnvPrime) ^ (value >>> 24);
+ }
+
+ return hash;
+ }
+
+ public boolean intersects(BitSet set) {
+ if (this == set) {
+ // If it has any set bits then it intersects itself.
+ return length() > 0;
+ }
+
+ int limit = Math.min(array.length, set.array.length);
+ for (int index = 0; index < limit; index++) {
+ int word = wordAt(array, index);
+ if (word != 0 && (word & wordAt(set.array, index)) != 0) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public boolean isEmpty() {
+ return length() == 0;
+ }
+
+ public int length() {
+ int lastIndex = lastSetWordIndex(array);
+ if (lastIndex == -1) {
+ return 0;
+ }
+
+ // Compute the bit index of the leftmost bit.
+ int word = wordAt(array, lastIndex);
+ return bitIndex(lastIndex) + (32 - Integer.numberOfLeadingZeros(word));
+ }
+
+ public int nextClearBit(int fromIndex) {
+ checkIndex(fromIndex);
+
+ int index = wordIndex(fromIndex);
+ int length = array.length;
+ if (index >= length) {
+ return fromIndex;
+ }
+
+ // Special case for the first word.
+ int word = ~wordAt(array, index) & WORD_MASK;
+ word &= (WORD_MASK << bitOffset(fromIndex));
+ while (word == 0) {
+ if (++index >= length) {
+ return bitIndex(index);
+ }
+ word = ~wordAt(array, index) & WORD_MASK;
+ }
+ return bitIndex(index) + Integer.numberOfTrailingZeros(word);
+ }
+
+ public int nextSetBit(int fromIndex) {
+ checkIndex(fromIndex);
+
+ int index = wordIndex(fromIndex);
+ int length = array.length;
+ if (index >= length) {
+ return -1;
+ }
+
+ // Special case for the first word.
+ int word = wordAt(array, index) & (WORD_MASK << bitOffset(fromIndex));
+ while (word == 0) {
+ if (++index >= length) {
+ return -1;
+ }
+ word = wordAt(array, index);
+ }
+ return bitIndex(index) + Integer.numberOfTrailingZeros(word);
+ }
+
+ public int previousClearBit(int fromIndex) {
+ if (fromIndex == -1) {
+ return -1;
+ }
+ checkIndex(fromIndex);
+
+ int index = wordIndex(fromIndex);
+ if (index >= array.length) {
+ return fromIndex;
+ }
+
+ // Special case for the first word.
+ int word = ~wordAt(array, index) & WORD_MASK;
+ word &= (WORD_MASK >>> (BITS_PER_WORD - bitOffset(fromIndex) - 1));
+ while (word == 0) {
+ if (--index < 0) {
+ return -1;
+ }
+ word = ~wordAt(array, index) & WORD_MASK;
+ }
+ return bitIndex(index) + (32 - Integer.numberOfLeadingZeros(word)) - 1;
+ }
+
+ public int previousSetBit(int fromIndex) {
+ if (fromIndex == -1) {
+ return -1;
+ }
+ checkIndex(fromIndex);
+
+ int index = wordIndex(fromIndex);
+ if (index >= array.length) {
+ return length() - 1;
+ }
+
+ // Special case for the first word.
+ int word = wordAt(array, index) & (WORD_MASK >>> (BITS_PER_WORD - bitOffset(fromIndex) - 1));
+ while (word == 0) {
+ if (--index < 0) {
+ return -1;
+ }
+ word = wordAt(array, index);
+ }
+ return bitIndex(index) + (32 - Integer.numberOfLeadingZeros(word)) - 1;
+ }
+
+ public void or(BitSet set) {
+ // a | a is just a.
+ if (this == set) {
+ return;
+ }
+
+ maybeGrowArrayToIndex(array, set.array.length - 1);
+
+ // Truth table
+ //
+ // Case | a | b | a | b | Change?
+ // 1 | false | false | false | a is already false
+ // 2 | false | true | true | set a to true
+ // 3 | true | false | true | a is already true
+ // 4 | true | true | true | a is already true
+ //
+ // We only need to change something in case 2. Case 2 only happens when b is true, so iterate
+ // over set b
+ for (int index = 0; index < set.array.length; index++) {
+ int word = wordAt(set.array, index);
+ if (word != 0) {
+ array[index] = wordAt(array, index) | word;
+ }
+ }
+ }
+
+ public void set(int bitIndex) {
+ checkIndex(bitIndex);
+ int index = wordIndex(bitIndex);
+ maybeGrowArrayToIndex(array, index);
+ array[index] = wordAt(array, index) | (1 << bitOffset(bitIndex));
+ }
+
+ public void set(int bitIndex, boolean value) {
+ if (value) {
+ set(bitIndex);
+ } else {
+ clear(bitIndex);
+ }
+ }
+
+ public void set(int fromIndex, int toIndex) {
+ checkRange(fromIndex, toIndex);
+ if (fromIndex != toIndex) {
+ setInternal(array, fromIndex, toIndex);
+ }
+ }
+
+ public void set(int fromIndex, int toIndex, boolean value) {
+ if (value) {
+ set(fromIndex, toIndex);
+ } else {
+ clear(fromIndex, toIndex);
+ }
+ }
+
+ public int size() {
+ return array.length * 32;
+ }
+
+ @Override
+ public String toString() {
+ if (isEmpty()) {
+ return "{}";
+ }
+
+ StringBuilder sb = new StringBuilder("{");
+ int next = nextSetBit(0);
+ sb.append(next);
+
+ while ((next = nextSetBit(next + 1)) != -1) {
+ sb.append(", ");
+ sb.append(next);
+ }
+
+ sb.append("}");
+ return sb.toString();
+ }
+
+ public void xor(BitSet set) {
+ // a ^ a is all false, so return an empty BitSet.
+ if (this == set) {
+ clear();
+ return;
+ }
+
+ maybeGrowArrayToIndex(array, set.array.length - 1);
+
+ // Truth table
+ //
+ // Case | a | b | a ^ b | Change?
+ // 1 | false | false | false | a is already false
+ // 2 | false | true | true | set a to true
+ // 3 | true | false | true | a is already true
+ // 4 | true | true | false | set a to false
+ //
+ // We need to change something in cases 2 and 4. Cases 2 and 4 only happen when b is true,
+ // so iterate over set b.
+ for (int index = 0; index < set.array.length; index++) {
+ int word = wordAt(set.array, index);
+ if (word != 0) {
+ array[index] = wordAt(array, index) ^ word;
+ }
+ }
+ }
+
+ public byte[] toByteArray() {
+ int nbits = length();
+ int nbytes = nbits / Byte.SIZE;
+ if (nbits % Byte.SIZE != 0) {
+ nbytes++;
+ }
+ byte[] bytes = new byte[nbytes];
+ int bitOffset = 0;
+ for (int i = 0; i < nbytes; i++) {
+ bytes[i] = getByte(array, bitOffset);
+ bitOffset += Byte.SIZE;
+ }
+ return bytes;
+ }
+
+ public long[] toLongArray() {
+ int nbits = length();
+ int nlongs = nbits / Long.SIZE;
+ if (nbits % Long.SIZE != 0) {
+ nlongs++;
+ }
+ long[] longs = new long[nlongs];
+ int bitOffset = 0;
+ for (int i = 0; i < nlongs; i++) {
+ longs[i] = getLong(array, bitOffset);
+ bitOffset += Long.SIZE;
+ }
+ return longs;
+ }
+
+ private static byte getByte(int[] words, int bitIndex) {
+ int wordIndex = wordIndex(bitIndex);
+ if (wordIndex >= words.length) {
+ return 0;
+ }
+ int bitOffset = bitOffset(bitIndex);
+ int word = wordAt(words, wordIndex);
+ int b = (word >>> bitOffset);
+ int leftBits = Byte.SIZE - BITS_PER_WORD + bitOffset;
+ if (leftBits > 0 && wordIndex + 1 < words.length) {
+ word = wordAt(words, wordIndex + 1);
+ if (word != 0) {
+ word &= ~(WORD_MASK << leftBits);
+ word <<= (Byte.SIZE - leftBits);
+ b |= word;
+ }
+ }
+ return (byte) (b & 0xff);
+ }
+
+ private static int getInt(int[] words, int bitIndex) {
+ byte b1 = getByte(words, bitIndex);
+ byte b2 = getByte(words, bitIndex + 8);
+ byte b3 = getByte(words, bitIndex + 16);
+ byte b4 = getByte(words, bitIndex + 24);
+ return (b1 & 0xff) | ((b2 & 0xff) << 8) | ((b3 & 0xff) << 16) | ((b4 & 0xff) << 24);
+ }
+
+ private static long getLong(int[] words, int bitIndex) {
+ int low = getInt(words, bitIndex);
+ int high = getInt(words, bitIndex + 32);
+ return ((long) high << 32) | (low & 0xffff_ffffL);
+ }
+
+ public static BitSet valueOf(byte[] words) {
+ int len = words.length;
+ while (len > 0 && words[len - 1] == 0) {
+ len--;
+ }
+ int[] array = new int[len * Byte.SIZE];
+ int bitIndex = 0;
+ for (int i = 0; i < len; i++) {
+ addByte(array, words[i], bitIndex);
+ bitIndex += Byte.SIZE;
+ }
+ return new BitSet(array);
+ }
+
+ public static BitSet valueOf(long[] words) {
+ int len = words.length;
+ while (len > 0 && words[len - 1] == 0) {
+ len--;
+ }
+ int[] array = new int[len * Long.SIZE];
+ int bitIndex = 0;
+ for (int i = 0; i < len; i++) {
+ addLong(array, words[i], bitIndex);
+ bitIndex += Long.SIZE;
+ }
+ return new BitSet(array);
+ }
+
+ private static void addByte(int[] words, byte bits, int bitIndex) {
+ if (bits != 0) {
+ int wordIndex = wordIndex(bitIndex);
+ int bitOffset = bitOffset(bitIndex);
+ int first = ((bits & 0xff) << bitOffset) & WORD_MASK;
+ if (first != 0) {
+ words[wordIndex] = wordAt(words, wordIndex) | first;
+ }
+ int second = bitOffset == 0 ? 0 : (bits & 0xff) >>> (BITS_PER_WORD - bitOffset);
+ if (second != 0) {
+ words[wordIndex + 1] = wordAt(words, wordIndex + 1) | second;
+ }
+ }
+ }
+
+ private static void addInt(int[] words, int bits, int bitIndex) {
+ if (bits != 0) {
+ addByte(words, (byte) (bits & 0xff), bitIndex);
+ addByte(words, (byte) ((bits >> 8) & 0xff), bitIndex + Byte.SIZE);
+ addByte(words, (byte) ((bits >> 16) & 0xff), bitIndex + 2 * Byte.SIZE);
+ addByte(words, (byte) ((bits >> 24) & 0xff), bitIndex + 3 * Byte.SIZE);
+ }
+ }
+
+ private static void addLong(int[] words, long bits, int bitIndex) {
+ if (bits != 0) {
+ int low = (int) bits;
+ addInt(words, low, bitIndex);
+ int high = (int) (bits >>> 32);
+ addInt(words, high, bitIndex + Integer.SIZE);
+ }
+ }
+}
diff --git a/user/test/com/google/gwt/emultest/CollectionsSuite.java b/user/test/com/google/gwt/emultest/CollectionsSuite.java
index 5f5e694..6ab5bfa 100644
--- a/user/test/com/google/gwt/emultest/CollectionsSuite.java
+++ b/user/test/com/google/gwt/emultest/CollectionsSuite.java
@@ -17,6 +17,7 @@
import com.google.gwt.emultest.java.util.ArrayListTest;
import com.google.gwt.emultest.java.util.ArraysTest;
+import com.google.gwt.emultest.java.util.BitSetTest;
import com.google.gwt.emultest.java.util.CollectionsTest;
import com.google.gwt.emultest.java.util.ComparatorTest;
import com.google.gwt.emultest.java.util.DateTest;
@@ -49,6 +50,7 @@
// $JUnit-BEGIN$
suite.addTestSuite(ArrayListTest.class);
suite.addTestSuite(ArraysTest.class);
+ suite.addTestSuite(BitSetTest.class);
suite.addTestSuite(CollectionsTest.class);
suite.addTestSuite(ComparatorTest.class);
suite.addTestSuite(DateTest.class);
diff --git a/user/test/com/google/gwt/emultest/java/util/BitSetTest.java b/user/test/com/google/gwt/emultest/java/util/BitSetTest.java
new file mode 100644
index 0000000..071288e
--- /dev/null
+++ b/user/test/com/google/gwt/emultest/java/util/BitSetTest.java
@@ -0,0 +1,1424 @@
+/*
+ * Copyright 2009 Google Inc.
+ *
+ * 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 com.google.gwt.emultest.java.util;
+
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.HashSet;
+
+/**
+ * Tests BitSet class.
+ */
+public class BitSetTest extends EmulTestBase {
+
+ /**
+ * This class is used to describe numerical patterns.
+ */
+ private interface Pattern {
+ boolean contains(int i);
+ }
+
+ // count used for looping tests
+ private static final int TEST_SIZE = 509;
+
+ // this number has to be bigger than 100
+ private static final int BIG_NUMBER = (TEST_SIZE) * 10 + 101;
+
+ private static void assertTrue(BitSet set, int index) {
+ assertTrue("expected=true set[" + index + "]=false", set.get(index));
+ }
+
+ private static void assertFalse(BitSet set, int index) {
+ assertFalse("expected=false set[" + index + "]=true", set.get(index));
+ }
+
+ private static BitSet createSetOfMultiples(int multiple) {
+ BitSet set = new BitSet(TEST_SIZE);
+ for (int i = 0; i < TEST_SIZE; i += multiple) {
+ set.set(i);
+ }
+ return set;
+ }
+
+ // this checks to see the values given are true, and the others around are not
+ private static void checkValues(BitSet set, int... values) {
+ assertEquals(values.length, set.cardinality());
+
+ int highestIndex = values[values.length - 1];
+ boolean[] bits = new boolean[highestIndex + 1];
+ for (int value : values) {
+ bits[value] = true;
+ }
+
+ for (int index = 0; index < bits.length; index++) {
+ assertEquals(bits[index], set.get(index));
+ }
+ }
+
+ private static void checkEqualityTrue(BitSet setA, BitSet setB) {
+ assertTrue(setA.equals(setB));
+ assertTrue(setB.equals(setA));
+ assertTrue(setA.equals(setA));
+ assertTrue(setB.equals(setB));
+ }
+
+ private static void checkEqualityFalse(BitSet setA, BitSet setB) {
+ assertFalse(setA.equals(setB));
+ assertFalse(setB.equals(setA));
+ }
+
+ // Checks that the values in the given range are the only true values
+ private static void checkRange(BitSet set, int fromIndex, int toIndex) {
+ for (int i = fromIndex; i < toIndex; i++) {
+ assertTrue(set, i);
+ }
+ assertEquals(toIndex - fromIndex, set.cardinality());
+ }
+
+ // Checks that the values in the given range are the only true values
+ private static void checkRange(BitSet set, int fromIndex1, int toIndex1,
+ int fromIndex2, int toIndex2) {
+ for (int i = fromIndex1; i < toIndex1; i++) {
+ assertTrue(set, i);
+ }
+ for (int i = fromIndex2; i < toIndex2; i++) {
+ assertTrue(set, i);
+ }
+ assertEquals(toIndex1 - fromIndex1 + toIndex2 - fromIndex2,
+ set.cardinality());
+ }
+
+ private static void checkPattern(BitSet set, Pattern pattern) {
+ for (int i = 0; i < TEST_SIZE; i++) {
+ boolean contained = pattern.contains(i);
+ if (contained != set.get(i)) {
+ fail("expected=" + contained + " set[" + i + "]=" + !contained);
+ }
+ }
+ }
+
+ public void testConstructor() {
+ BitSet set = new BitSet();
+
+ // test what we know to be true of a new BitSet
+ assertTrue(set.isEmpty());
+ assertEquals(0, set.length());
+ assertEquals(0, set.cardinality());
+
+ // test exceptions
+ try {
+ set = new BitSet(-1);
+ fail("exception expected");
+ } catch (NegativeArraySizeException expected) {
+ }
+
+ set = new BitSet(0);
+ set = new BitSet(BIG_NUMBER);
+ }
+
+ public void testAnd() {
+ Pattern multiplesOf6 = new Pattern() {
+ @Override
+ public boolean contains(int i) {
+ return i % 6 == 0;
+ }
+ };
+
+ // setA will contain all multiples of 2
+ BitSet setA = createSetOfMultiples(2);
+
+ // setB will contain all multiples of 3
+ BitSet setB = createSetOfMultiples(3);
+
+ // and()ing the sets should give multiples of 6
+ setA.and(setB);
+
+ // verify by checking multiples of 6
+ checkPattern(setA, multiplesOf6);
+
+ // and()ing a set to itself should do nothing
+ setA.and(setA);
+
+ // verify by checking multiples of 6
+ checkPattern(setA, multiplesOf6);
+
+ // and()ing with a set identical to itself should do nothing
+ setA.and((BitSet) setA.clone());
+
+ // verify by checking multiples of 6
+ checkPattern(setA, multiplesOf6);
+
+ // and()ing with all trues should do nothing
+ BitSet trueSet = new BitSet(TEST_SIZE);
+ trueSet.set(0, TEST_SIZE);
+ setA.and(trueSet);
+
+ // verify by checking multiples of 6
+ checkPattern(setA, multiplesOf6);
+
+ // and()ing with all trues in a larger set should do nothing
+ trueSet.set(TEST_SIZE, TEST_SIZE * 2);
+ setA.and(trueSet);
+
+ // verify by checking multiples of 6
+ checkPattern(setA, multiplesOf6);
+ // there were "TEST_SIZE" extra trues, so lets verify those came out false
+ for (int i = TEST_SIZE; i < TEST_SIZE * 2; i++) {
+ assertFalse(setA.get(i));
+ }
+
+ // and()ing with an empty set should result in an empty set
+ setA.and(new BitSet());
+ assertEquals(0, setA.length());
+
+ // these close bits should not intersect
+ setB = new BitSet();
+ setA.set(0);
+ setB.set(1);
+ setA.and(setB);
+ assertTrue(setA.isEmpty());
+
+ // these bits should not intersect
+ setB = new BitSet();
+ setA.set(0);
+ setB.set(BIG_NUMBER);
+ setA.and(setB);
+ assertTrue(setA.isEmpty());
+ setA.set(0);
+ setB.and(setA);
+ assertTrue(setB.isEmpty());
+
+ setA = new BitSet();
+ setA.set(1);
+ setA.set(5);
+ setB = new BitSet();
+ setB.set(2);
+ setA.and(setB);
+ assertTrue(setA.isEmpty());
+
+ setA = new BitSet();
+ setA.set(1);
+ setA.set(5);
+ setB = new BitSet();
+ setB.set(5);
+ setA.and(setB);
+ assertTrue(setA.get(5));
+ assertEquals(1, setA.cardinality());
+
+ setA = new BitSet();
+ setA.set(2);
+ setB = new BitSet();
+ setB.set(1);
+ setB.set(3);
+ setA.and(setB);
+ assertEquals(0, setA.cardinality());
+ }
+
+ public void testAndNot() {
+ Pattern multiplesOf2Not3 = new Pattern() {
+ @Override
+ public boolean contains(int i) {
+ return i % 2 == 0 && i % 3 != 0;
+ }
+ };
+
+ // setA will contain all multiples of 2
+ BitSet setA = createSetOfMultiples(2);
+
+ // setB will contain all multiples of 3
+ BitSet setB = createSetOfMultiples(3);
+
+ // andNot() the sets
+ setA.andNot(setB);
+
+ // verify by checking for multiples of 2 that are not multiples of 3
+ checkPattern(setA, multiplesOf2Not3);
+
+ // andNot()ing with an empty set should do nothing
+ setA.andNot(new BitSet());
+
+ // verify by checking for multiples of 2 that are not multiples of 3
+ checkPattern(setA, multiplesOf2Not3);
+
+ // andNot()ing with all trues should result in an empty set
+ BitSet trueSet = new BitSet(TEST_SIZE * 2);
+ trueSet.set(0, TEST_SIZE * 2);
+ setA.andNot(trueSet);
+ assertTrue(setA.isEmpty());
+
+ // save setB in setA
+ setA = (BitSet) setB.clone();
+
+ // andNot()ing a set to itself should result in an empty set
+ setB.andNot(setB);
+ assertTrue(setB.isEmpty());
+
+ // andNot()ing a set identical to itself should result in an empty set
+ setA.andNot((BitSet) setA.clone());
+ assertTrue(setA.isEmpty());
+
+ setA = new BitSet();
+ setA.set(2);
+ setB = new BitSet();
+ setB.set(1);
+ setB.set(3);
+ setA.andNot(setB);
+ assertTrue(setA.get(2));
+ assertEquals(1, setA.cardinality());
+ }
+
+ public void testCardinality() {
+ BitSet set = new BitSet(TEST_SIZE);
+
+ // test the empty count
+ assertEquals(0, set.cardinality());
+
+ // test a count of 1
+ set.set(0);
+ assertEquals(1, set.cardinality());
+
+ // test a count of 2
+ set.set(BIG_NUMBER);
+ assertEquals(2, set.cardinality());
+
+ // clear them both and test again
+ set.clear(0);
+ set.clear(BIG_NUMBER);
+ assertEquals(0, set.cardinality());
+
+ // test different multiples
+ for (int multiple = 1; multiple < 33; multiple++) {
+ set = new BitSet();
+ set.set(BIG_NUMBER + multiple);
+ for (int i = 1; i < 33; i++) {
+ set.set(i * multiple);
+ assertEquals(i + 1, set.cardinality());
+ }
+ }
+
+ // test powers of 2
+ set = new BitSet();
+ int count = 0;
+ for (int i = 1; i < TEST_SIZE; i += i) {
+ set.set(i);
+ count++;
+ }
+ assertEquals(count, set.cardinality());
+
+ // test a long run
+ set = new BitSet();
+ for (int i = 0; i < TEST_SIZE; i++) {
+ set.set(i);
+ assertEquals(i + 1, set.cardinality());
+ }
+ }
+
+ public void testClear() {
+ BitSet set = new BitSet(TEST_SIZE);
+ for (int i = 0; i < TEST_SIZE; i++) {
+ set.set(i);
+ }
+
+ set.clear();
+ assertTrue(set.isEmpty());
+
+ set = new BitSet();
+ set.set(BIG_NUMBER);
+ set.clear();
+ assertFalse(set.get(BIG_NUMBER));
+ }
+
+ public void testClearInt() {
+ BitSet set = new BitSet();
+ set.set(0);
+ set.clear(0);
+ assertFalse(set.get(0));
+ set.set(BIG_NUMBER);
+ checkValues(set, BIG_NUMBER);
+ set.clear(BIG_NUMBER);
+ assertFalse(set.get(BIG_NUMBER));
+
+ set = new BitSet();
+ set.set(1);
+ set.set(2);
+ set.set(3);
+ set.set(18);
+ set.set(40);
+ set.clear(2);
+ checkValues(set, 1, 3, 18, 40);
+ set.clear(9);
+ checkValues(set, 1, 3, 18, 40);
+ set.clear(18);
+ checkValues(set, 1, 3, 40);
+ set.clear(7);
+ set.clear(6);
+ checkValues(set, 1, 3, 40);
+ set.clear(3);
+ checkValues(set, 1, 40);
+ set.clear(40);
+ checkValues(set, 1);
+ set.clear(1);
+ assertTrue(set.isEmpty());
+
+ // test exceptions
+ try {
+ set.clear(-1, 2);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ try {
+ set.clear(3, 1);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ set.clear(2, 2);
+ }
+
+ public void testClearIntIntAndSetIntInt() {
+ BitSet set = new BitSet();
+
+ set.set(7);
+ set.set(50);
+ set.set(BIG_NUMBER);
+ set.clear(0, BIG_NUMBER);
+ checkValues(set, BIG_NUMBER);
+ set.clear(0, BIG_NUMBER + 1);
+ assertTrue(set.isEmpty());
+
+ set.set(0, 65);
+ checkRange(set, 0, 65);
+ set.clear(0, 63);
+ checkRange(set, 63, 65);
+ set.clear(63, 65);
+ assertTrue(set.isEmpty());
+
+ set.set(0, 128);
+ set.clear(0, 64);
+ checkRange(set, 64, 128);
+ set.clear(0, 129);
+ assertTrue(set.isEmpty());
+
+ set.set(0, 65);
+ checkRange(set, 0, 65);
+
+ set.clear(0, 16);
+ checkRange(set, 16, 65);
+
+ set.set(0, 16);
+ checkRange(set, 0, 65);
+ set.clear(5, 5);
+ set.clear(7, 14);
+ set.clear(15, 42);
+ set.clear(43, 55);
+ set.clear(58, 62);
+ set.clear(BIG_NUMBER, BIG_NUMBER);
+ set.clear(BIG_NUMBER, BIG_NUMBER + 1);
+ checkValues(set, 0, 1, 2, 3, 4, 5, 6, 14, 42, 55, 56, 57, 62, 63, 64);
+ set.clear(0, 65);
+ assertTrue(set.isEmpty());
+
+ set.set(0, 33);
+ checkRange(set, 0, 33);
+ set.clear(0, 8);
+ checkRange(set, 8, 33);
+
+ for (int i = 0; i < 33; i++) {
+ // this shouldn't change anything
+ set.clear(i, i);
+ assertEquals(25, set.cardinality());
+ // nor should this
+ set.set(i, i);
+ assertEquals(25, set.cardinality());
+ }
+
+ for (int i = 0; i < 65; i++) {
+ set.set(0, 128);
+ set.clear(i, 128 - i);
+ checkRange(set, 0, i, 128 - i, 128);
+ }
+ set.clear(0, 128);
+ assertTrue(set.isEmpty());
+
+ set.set(7, 100);
+ checkRange(set, 7, 100);
+
+ set = new BitSet();
+ set.set(BIG_NUMBER, BIG_NUMBER);
+ assertEquals(0, set.cardinality());
+ set.set(BIG_NUMBER, BIG_NUMBER + 1);
+ checkRange(set, BIG_NUMBER, BIG_NUMBER + 1);
+ set.clear(BIG_NUMBER, BIG_NUMBER);
+ checkValues(set, BIG_NUMBER);
+ set.clear(BIG_NUMBER, BIG_NUMBER + 1);
+ assertEquals(0, set.cardinality());
+
+ set = new BitSet();
+ set.set(10, 12);
+ set.clear(11, 1000);
+ checkValues(set, 10);
+
+ set = new BitSet();
+ set.set(10, 12);
+ set.clear(0, 10);
+ set.set(BIG_NUMBER, BIG_NUMBER);
+ checkValues(set, 10, 11);
+ set.clear(10, 12);
+ assertTrue(set.isEmpty());
+
+ set = new BitSet();
+ set.set(1, 20);
+ set.clear(5, 10);
+ checkRange(set, 1, 5, 10, 20);
+
+ set = new BitSet();
+ set.set(1, 10);
+ set.clear(5, 15);
+ checkRange(set, 1, 5);
+
+ // test clear(int, int) exceptions
+ try {
+ set.clear(-1, 2);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ try {
+ set.clear(3, 1);
+ fail("expected exception");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ set.clear(2, 2);
+
+ // test set(int, int) exceptions
+ try {
+ set.set(-1, 2);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ try {
+ set.set(3, 1);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ set.set(2, 2);
+ }
+
+ public void testClone() {
+ BitSet set = new BitSet();
+ set.set(2);
+ set.set(4);
+ set.set(32);
+ set.set(BIG_NUMBER);
+ BitSet clone = (BitSet) set.clone();
+ checkValues(clone, 2, 4, 32, BIG_NUMBER);
+ assertTrue(set.equals(clone));
+ assertEquals(4, clone.cardinality());
+ }
+
+ public void testEquals() {
+ BitSet setA = new BitSet();
+ BitSet setB = new BitSet();
+ checkEqualityTrue(setA, setB);
+
+ setA.set(0);
+ setB.set(0);
+ checkEqualityTrue(setA, setB);
+
+ setA.set(BIG_NUMBER);
+ setB.set(BIG_NUMBER);
+ checkEqualityTrue(setA, setB);
+
+ setA.clear(0);
+ setB.clear(0);
+ checkEqualityTrue(setA, setB);
+
+ setA.clear(BIG_NUMBER);
+ setB.clear(BIG_NUMBER);
+ checkEqualityTrue(setA, setB);
+
+ setA.set(0);
+ setB.set(1);
+ checkEqualityFalse(setA, setB);
+
+ setA.set(2);
+ setB.set(2);
+ checkEqualityFalse(setA, setB);
+
+ setA = new BitSet();
+ setB = new BitSet();
+ setA.set(Math.max(0, BIG_NUMBER - 8));
+ setB.set(BIG_NUMBER + 1);
+ checkEqualityFalse(setA, setB);
+
+ BitSet set1 = new BitSet();
+ set1.set(40);
+ BitSet set2 = new BitSet();
+ set2.set(1);
+ set2.set(40);
+ assertFalse(set1.equals(set2));
+
+ setA = new BitSet();
+ setA.set(2);
+ setB = new BitSet();
+ setB.set(1);
+ setB.set(3);
+ checkEqualityFalse(setA, setB);
+ }
+
+ public void testFlipInt() {
+ BitSet set = new BitSet();
+ set.flip(0);
+ assertTrue(set.get(0));
+ set.flip(0);
+ assertFalse(set.get(0));
+ set.flip(BIG_NUMBER);
+ assertTrue(set.get(BIG_NUMBER));
+ set.flip(BIG_NUMBER);
+ assertFalse(set.get(BIG_NUMBER));
+
+ set = new BitSet();
+ set.flip(1);
+ set.flip(2);
+ set.flip(3);
+ set.flip(4);
+ set.flip(6);
+ set.flip(4);
+ set.flip(6);
+ set.flip(6);
+ set.flip(6);
+ set.flip(8);
+ set.flip(10);
+ set.flip(8);
+ set.flip(2);
+ set.flip(8);
+ checkValues(set, 1, 3, 8, 10);
+ set.flip(8);
+ checkValues(set, 1, 3, 10);
+ set.flip(3);
+ checkValues(set, 1, 10);
+ set.flip(10);
+ set.flip(11);
+ checkValues(set, 1, 11);
+ set.flip(1);
+ checkValues(set, 11);
+ set.flip(11);
+ assertTrue(set.isEmpty());
+
+ // test exceptions
+ try {
+ set.flip(-1);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ set.flip(BIG_NUMBER);
+ set.flip(BIG_NUMBER);
+ }
+
+ public void testFlipIntInt() {
+ BitSet set = new BitSet();
+ set.flip(0, BIG_NUMBER);
+ checkRange(set, 0, BIG_NUMBER);
+ set.flip(0, BIG_NUMBER - 1);
+ checkValues(set, BIG_NUMBER - 1);
+ set.clear(0, BIG_NUMBER);
+ assertTrue(set.isEmpty());
+
+ set.flip(0, 33);
+ set.flip(0, 8);
+ checkRange(set, 8, 33);
+
+ // current state is set.set(8,33)
+ for (int i = 0; i < 33; i++) {
+ // this shouldn't change anything
+ set.flip(i, i);
+ assertEquals(25, set.cardinality());
+ }
+
+ // current state is set.set(8,33)
+ set.flip(0, 8);
+ set.flip(7, 21);
+ set.flip(22, 27);
+ checkValues(set, 0, 1, 2, 3, 4, 5, 6, 21, 27, 28, 29, 30, 31, 32);
+
+ set = new BitSet();
+ set.flip(10, 12);
+ set.flip(11, 1000);
+ checkRange(set, 10, 11, 12, 1000);
+
+ set = new BitSet();
+ set.flip(10, 12);
+ set.flip(0, 10);
+ checkRange(set, 0, 12);
+ set.flip(0, 12);
+ assertTrue(set.isEmpty());
+
+ set.flip(0, 64);
+ set.flip(0, 63);
+ checkValues(set, 63);
+ set.flip(63, 64);
+ assertTrue(set.isEmpty());
+
+ set.flip(0, 130);
+ checkRange(set, 0, 130);
+ set.flip(0, 66);
+ checkRange(set, 66, 130);
+ set.flip(65, 131);
+ checkRange(set, 65, 66, 130, 131);
+
+ set = new BitSet();
+ set.flip(1, 20);
+ set.flip(5, 10);
+ checkRange(set, 1, 5, 10, 20);
+
+ set = new BitSet();
+ set.flip(1, 10);
+ set.flip(5, 15);
+ checkRange(set, 1, 5, 10, 15);
+
+ // test exceptions
+ try {
+ set.flip(-1, 2);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ try {
+ set.flip(3, 1);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ set.flip(2, 2);
+ }
+
+ public void testGetIntAndSetInt() {
+ BitSet set = new BitSet();
+ set.set(0);
+ assertTrue(set.get(0));
+ assertFalse(set.get(1));
+ assertFalse(set.get(2));
+ assertFalse(set.get(100));
+
+ set.set(BIG_NUMBER);
+ assertFalse(set.get(BIG_NUMBER - 1));
+ assertTrue(set.get(BIG_NUMBER));
+ assertFalse(set.get(BIG_NUMBER + 1));
+
+ set = new BitSet();
+ set.set(0);
+ set.set(4);
+ set.set(7);
+ set.set(10);
+ set.set(31);
+ set.set(32);
+ set.set(33);
+ set.set(69);
+ checkValues(set, 0, 4, 7, 10, 31, 32, 33, 69);
+
+ // test get() exceptions
+ try {
+ set.get(-1);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ set.get(BIG_NUMBER);
+
+ // test set() exceptions
+ try {
+ set.set(-1);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ set.set(BIG_NUMBER);
+ }
+
+ public void testGetIntInt() {
+ BitSet set = new BitSet();
+
+ set.set(1);
+ assertFalse(set.get(1, 1).get(0));
+ assertTrue(set.get(1, 2).get(0));
+ assertTrue(set.get(0, 2).get(1));
+
+ set.set(32);
+ set.set(50);
+ set.set(BIG_NUMBER);
+
+ BitSet subSet = set.get(0, BIG_NUMBER);
+ checkValues(subSet, 1, 32, 50);
+
+ subSet = set.get(1, BIG_NUMBER);
+ checkValues(subSet, 0, 31, 49);
+
+ subSet = set.get(2, BIG_NUMBER + 1);
+ checkValues(subSet, 30, 48, BIG_NUMBER - 2);
+
+ subSet = set.get(32, BIG_NUMBER * 2);
+ checkValues(subSet, 0, 18, BIG_NUMBER - 32);
+ assertEquals(3, subSet.cardinality());
+
+ subSet = set.get(0, BIG_NUMBER + 1);
+ assertEquals(set, subSet);
+
+ set = new BitSet();
+ for (int i = 8; i < 33; i++) {
+ set.set(i);
+ }
+ for (int i = 0; i < 33; i++) {
+ assertTrue(set.get(i, i).isEmpty());
+ }
+
+ // test exceptions
+ try {
+ set.get(-1, 2);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ try {
+ set.get(3, 1);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ set.get(2, 2);
+ }
+
+ public void testHashCode() {
+ // Note: Oracle's hashCode() implementation creates many collisions when
+ // testSize is big, causing this test to fail in development mode.
+ // Since this is an "unimportant test" as suggested by the original author,
+ // we can just test with a small number.
+ int testSize = 25;
+
+ HashSet<Integer> hashValues = new HashSet<>();
+
+ // count the collisions
+ int collisions = 0;
+
+ // hash an empty set
+ hashValues.add(new BitSet().hashCode());
+
+ // hash the set of {TEST_SIZE + 1}
+ BitSet set = new BitSet();
+ set.set(testSize + 1);
+ assertTrue(hashValues.add(set.hashCode()));
+
+ // hash the set of {0, TEST_SIZE + 1}
+ set.set(0);
+ assertTrue(hashValues.add(set.hashCode()));
+
+ // hash the set of {0}
+ set = new BitSet();
+ set.set(0);
+ assertTrue(hashValues.add(set.hashCode()));
+
+ for (int multiple = 1; multiple < 33; multiple++) {
+ set = new BitSet();
+ set.set(0);
+
+ // fill a set with multiples
+ for (int i = multiple; i < testSize; i += multiple) {
+ set.set(i);
+ // hash the current set, except in the case of {0}
+ if (i != 0) {
+ if (hashValues.add(set.hashCode()) == false) {
+ collisions++;
+ }
+ set.set(testSize + 1);
+ if (hashValues.add(set.hashCode()) == false) {
+ collisions++;
+ }
+ set.clear(testSize + 1);
+ }
+ }
+ }
+
+ assertEquals(0, collisions);
+ }
+
+ public void testIntersects() {
+ final int prime = 37;
+ for (int multiple = 1; multiple < prime; multiple++) {
+ int size = prime * multiple + 1;
+
+ // setA will contain all multiples of "multiple" up to "size"
+ BitSet setA = new BitSet(size);
+ for (int i = multiple; i < size; i += multiple) {
+ setA.set(i);
+ }
+
+ // setB will contain all multiples of "prime" up to "size"
+ BitSet setB = new BitSet();
+ for (int i = prime; i < size; i += prime) {
+ setB.set(i);
+ }
+
+ // the two sets should only intersect on the very last bit
+ assertTrue(setA.intersects(setB));
+ setA.clear(size - 1);
+ assertFalse(setA.intersects(setB));
+
+ // the inverse of a set should not intersect itself
+ setB = new BitSet();
+ for (int i = 0; i < prime; i++) {
+ setB.set(i, !setA.get(i));
+ }
+ assertFalse(setA.intersects(setB));
+
+ // a set intersects itself if it has any bits set
+ assertTrue(setA.intersects(setA));
+ setA = new BitSet();
+ assertFalse(setA.intersects(setA));
+
+ // an empty set doesn't intersect itself
+ assertFalse(new BitSet().intersects(new BitSet()));
+ }
+
+ BitSet setA = new BitSet();
+ setA.set(2);
+ BitSet setB = new BitSet();
+ setB.set(1);
+ setB.set(3);
+ assertFalse(setA.intersects(setB));
+ }
+
+ public void testIsEmpty() {
+ BitSet set = new BitSet();
+ assertTrue(set.isEmpty());
+ set.set(0);
+ assertFalse(set.isEmpty());
+ set = new BitSet();
+ set.set(BIG_NUMBER);
+ assertFalse(set.isEmpty());
+ }
+
+ public void testLength() {
+ BitSet set = new BitSet();
+ assertEquals(0, set.length());
+
+ set.set(30);
+ assertEquals(31, set.length());
+ set.clear(30);
+ set.set(31);
+ assertEquals(32, set.length());
+ set.clear(31);
+ set.set(100);
+ set.set(BIG_NUMBER);
+ assertEquals(BIG_NUMBER + 1, set.length());
+ set.clear(BIG_NUMBER);
+ assertEquals(101, set.length());
+ set.clear(100);
+ assertEquals(0, set.length());
+ set.set(0);
+ assertEquals(1, set.length());
+
+ set = new BitSet();
+ for (int i = 0; i < 640; i++) {
+ set.set(i);
+ assertEquals(i + 1, set.length());
+ }
+ for (int i = 0; i < 639; i++) {
+ set.clear(i);
+ assertEquals(640, set.length());
+ }
+ set.clear(639);
+ assertEquals(0, set.length());
+ }
+
+ public void testNextClearBit() {
+ BitSet set = new BitSet(10);
+
+ assertEquals(BIG_NUMBER, set.nextClearBit(BIG_NUMBER));
+
+ for (int i = 0; i < 10; i++) {
+ assertEquals(i, set.nextClearBit(i));
+ }
+ for (int i = 10; i < 100; i++) {
+ assertEquals(i, set.nextClearBit(i));
+ }
+
+ set.set(0, 9);
+ set.set(10, 50);
+ for (int i = 0; i <= 9; i++) {
+ assertEquals(9, set.nextClearBit(i));
+ }
+ for (int i = 10; i < 50; i++) {
+ assertEquals(50, set.nextClearBit(i));
+ }
+ for (int i = 50; i < 100; i++) {
+ assertEquals(i, set.nextClearBit(i));
+ }
+
+ set = new BitSet();
+ set.set(61);
+ for (int i = 0; i < 60; i++) {
+ set.set(i);
+ assertEquals(i + 1, set.nextClearBit(0));
+ }
+ set.clear(61);
+ for (int i = 60; i < 100; i++) {
+ set.set(i);
+ assertEquals(i + 1, set.nextClearBit(0));
+ }
+ assertEquals(BIG_NUMBER, set.nextClearBit(BIG_NUMBER));
+
+ try {
+ set.nextClearBit(-1);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+ }
+
+ public void testNextSetBit() {
+ BitSet set = new BitSet();
+
+ assertEquals(-1, set.nextSetBit(0));
+ assertEquals(-1, set.nextSetBit(BIG_NUMBER));
+
+ set.set(0);
+ set.set(1);
+ set.set(3);
+ set.set(31);
+ set.set(32);
+ set.set(33);
+ assertEquals(0, set.nextSetBit(0));
+ assertEquals(1, set.nextSetBit(1));
+ assertEquals(3, set.nextSetBit(2));
+ assertEquals(3, set.nextSetBit(3));
+ assertEquals(31, set.nextSetBit(4));
+ assertEquals(31, set.nextSetBit(31));
+ assertEquals(32, set.nextSetBit(32));
+ assertEquals(33, set.nextSetBit(33));
+ assertEquals(-1, set.nextSetBit(34));
+
+ set = new BitSet();
+ set.set(BIG_NUMBER);
+ assertEquals(BIG_NUMBER, set.nextSetBit(0));
+ assertEquals(BIG_NUMBER, set.nextSetBit(BIG_NUMBER));
+ assertEquals(-1, set.nextSetBit(BIG_NUMBER + 1));
+
+ for (int i = 0; i < TEST_SIZE; i++) {
+ set.set(BIG_NUMBER + i);
+ }
+ set.set(TEST_SIZE / 2);
+ assertEquals(TEST_SIZE / 2, set.nextSetBit(0));
+
+ try {
+ set.nextSetBit(-1);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+ }
+
+ public void testPreviousClearBit() {
+ BitSet set = new BitSet();
+
+ assertEquals(-1, set.previousClearBit(-1));
+ assertEquals(0, set.previousClearBit(0));
+ assertEquals(100, set.previousClearBit(100));
+
+ set.set(0, 9);
+ set.set(10, 50);
+ for (int i = 100; i >= 50; i--) {
+ assertEquals(i, set.previousClearBit(i));
+ }
+ for (int i = 49; i >= 9; i--) {
+ assertEquals(9, set.previousClearBit(i));
+ }
+ for (int i = 8; i >= 0; i--) {
+ assertEquals(-1, set.previousClearBit(i));
+ }
+
+ try {
+ set.previousClearBit(-100);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+ }
+
+ public void testPreviousSetBit() {
+ BitSet set = new BitSet();
+
+ assertEquals(-1, set.previousSetBit(-1));
+ assertEquals(-1, set.previousSetBit(0));
+ assertEquals(-1, set.previousSetBit(100));
+
+ set.set(0, 9);
+ set.set(10, 50);
+ for (int i = 100; i >= 50; i--) {
+ assertEquals(49, set.previousSetBit(i));
+ }
+ for (int i = 49; i >= 10; i--) {
+ assertEquals(i, set.previousSetBit(i));
+ }
+ assertEquals(8, set.previousSetBit(9));
+ for (int i = 8; i >= 0; i--) {
+ assertEquals(i, set.previousSetBit(i));
+ }
+
+ try {
+ set.previousSetBit(-100);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+ }
+
+ public void testOr() {
+ Pattern multiplesOf2And5 = new Pattern() {
+ @Override
+ public boolean contains(int i) {
+ return i % 2 == 0 || i % 5 == 0;
+ }
+ };
+
+ // setA will contain all multiples of 2
+ BitSet setA = createSetOfMultiples(2);
+
+ // setB will contain all multiples of 5
+ BitSet setB = createSetOfMultiples(5);
+
+ // or() the two sets to get both multiples of 2 and 5
+ setA.or(setB);
+
+ // verify multiples of 2 and 5
+ checkPattern(setA, multiplesOf2And5);
+
+ // or()ing a set to itself should do nothing
+ setA.or(setA);
+
+ // verify multiples of 2 and 5
+ checkPattern(setA, multiplesOf2And5);
+
+ // or()ing with set identical to itself should do nothing
+ setA.or((BitSet) setA.clone());
+
+ // verify multiples of 2 and 5
+ checkPattern(setA, multiplesOf2And5);
+
+ // or()ing with an empty set (all falses) should do nothing
+ setA.or(new BitSet());
+
+ // verify multiples of 2 and 5
+ checkPattern(setA, multiplesOf2And5);
+
+ // or()ing with all trues should result in all trues
+ BitSet trueSet = new BitSet(TEST_SIZE * 2);
+ trueSet.set(0, TEST_SIZE * 2);
+ setA.or(trueSet);
+ assertEquals(TEST_SIZE * 2, setA.cardinality());
+
+ setA = new BitSet();
+ setA.set(2);
+ setB = new BitSet();
+ setB.set(1);
+ setB.set(3);
+ setA.or(setB);
+ checkRange(setA, 1, 4);
+ }
+
+ public void testSetIntBoolean() {
+ BitSet set = new BitSet();
+ set.set(0, true);
+ assertTrue(set.get(0));
+ set.set(0, false);
+ assertFalse(set.get(0));
+ set.set(BIG_NUMBER, true);
+ assertTrue(set.get(BIG_NUMBER));
+ set.set(BIG_NUMBER, false);
+ assertFalse(set.get(BIG_NUMBER));
+
+ set = new BitSet();
+ set.set(1, true);
+ set.set(2, true);
+ set.set(3, true);
+ set.set(4, true);
+ set.set(6, true);
+ set.set(4, false);
+ set.set(6, true);
+ set.set(6, false);
+ set.set(6, false);
+ set.set(8, true);
+ set.set(10, true);
+ set.set(8, false);
+ set.set(2, false);
+ set.set(8, true);
+ checkValues(set, 1, 3, 8, 10);
+ set.set(8, false);
+ checkValues(set, 1, 3, 10);
+ set.set(3, false);
+ checkValues(set, 1, 10);
+ set.set(10, false);
+ set.set(11, true);
+ checkValues(set, 1, 11);
+ set.set(1, false);
+ checkValues(set, 11);
+ set.set(11, false);
+ assertTrue(set.isEmpty());
+ }
+
+ public void testSetIntIntBoolean() {
+ BitSet set = new BitSet();
+ set.set(0, BIG_NUMBER, true);
+ assertEquals(BIG_NUMBER, set.cardinality());
+ set.set(0, BIG_NUMBER - 1, false);
+ assertEquals(1, set.cardinality());
+ set.set(0, BIG_NUMBER, false);
+ assertTrue(set.isEmpty());
+
+ set.set(0, 32, true);
+ checkRange(set, 0, 32);
+ set.set(0, 8, false);
+ checkRange(set, 8, 32);
+ set.set(0, 8, true);
+ checkRange(set, 0, 32);
+ set.set(7, 21, false);
+ checkValues(set, 0, 1, 2, 3, 4, 5, 6, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31);
+ set.set(22, 27, false);
+ checkValues(set, 0, 1, 2, 3, 4, 5, 6, 21, 27, 28, 29, 30, 31);
+
+ set = new BitSet();
+ set.set(11, 1000, true);
+ set.set(10, 12, false);
+ checkRange(set, 12, 1000);
+ assertEquals(988, set.cardinality());
+
+ set = new BitSet();
+ set.set(10, 12, true);
+ set.set(0, 10, true);
+ checkRange(set, 0, 12);
+ set.set(0, 12, false);
+ assertTrue(set.isEmpty());
+
+ set = new BitSet();
+ set.set(1, 20, true);
+ set.set(5, 10, false);
+ checkRange(set, 1, 5, 10, 20);
+
+ set = new BitSet();
+ set.set(1, 10, true);
+ set.set(5, 10, false);
+ set.set(10, 15, true);
+ checkRange(set, 1, 5, 10, 15);
+
+ // test exceptions
+ try {
+ set.set(-1, 2, true);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ try {
+ set.set(3, 1, true);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ set.set(2, 2, true);
+
+ try {
+ set.set(-1, 2, false);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ try {
+ set.set(3, 1, false);
+ fail("exception expected");
+ } catch (IndexOutOfBoundsException expected) {
+ }
+
+ set.set(2, 2, false);
+ }
+
+ public void testSize() {
+ // this is an unimportant test
+
+ BitSet set = new BitSet(7);
+ assertTrue(set.size() >= 7);
+ set = new BitSet(BIG_NUMBER);
+ assertTrue(set.size() >= BIG_NUMBER);
+ }
+
+ public void testToString() {
+ BitSet set = new BitSet();
+ assertEquals("{}", set.toString());
+
+ set.set(32);
+ assertEquals("{32}", set.toString());
+
+ set.set(BIG_NUMBER);
+ assertEquals("{32, " + BIG_NUMBER + "}", set.toString());
+
+ set.set(1);
+ assertEquals("{1, 32, " + BIG_NUMBER + "}", set.toString());
+
+ set.set(2);
+ assertEquals("{1, 2, 32, " + BIG_NUMBER + "}", set.toString());
+ }
+
+ public void testXor() {
+ Pattern exclusiveMultiples = new Pattern() {
+ @Override
+ public boolean contains(int i) {
+ return (i % 2 == 0) ^ (i % 3 == 0);
+ }
+ };
+
+ // setA will contain all multiples of 2
+ BitSet setA = createSetOfMultiples(2);
+
+ // setB will contain all multiples of 3
+ BitSet setB = createSetOfMultiples(3);
+
+ // xor()ing the sets should give exclusive multiples of 2 and 3
+ setA.xor(setB);
+
+ // verify by checking for exclusive multiples of 2 and 3
+ checkPattern(setA, exclusiveMultiples);
+
+ // xor()ing a set to an empty set should do nothing
+ setA.xor(new BitSet());
+
+ // verify by checking for exclusive multiples of 2 and 3
+ checkPattern(setA, exclusiveMultiples);
+
+ // xor()ing a set with all trues should flip each bit
+ BitSet trueSet = new BitSet(TEST_SIZE * 2);
+ trueSet.set(0, TEST_SIZE * 2);
+ setA.xor(trueSet);
+
+ // verify by checking for !(exclusive multiples of 2 and 3)
+ checkPattern(setA, new Pattern() {
+ @Override
+ public boolean contains(int i) {
+ return !((i % 2 == 0) ^ (i % 3 == 0));
+ }
+ });
+ // there were "TEST_SIZE" extra trues, so verify those came out as true
+ for (int i = TEST_SIZE; i < TEST_SIZE * 2; i++) {
+ assertTrue(setA.get(i));
+ }
+
+ // xor()ing a set to itself should result in an empty set
+ setA.xor(setA);
+ assertTrue(setA.isEmpty());
+
+ // xor()ing a set identical to itself should result in an empty set
+ setB.xor((BitSet) setB.clone());
+ assertTrue(setB.isEmpty());
+
+ setA = new BitSet();
+ setA.set(2);
+ setB = new BitSet();
+ setB.set(1);
+ setB.set(3);
+ setA.xor(setB);
+ checkRange(setA, 1, 4);
+ }
+
+ public void testToByteArray() {
+ BitSet set = new BitSet();
+ assertEquals(0, set.toByteArray().length);
+
+ int[] bits = {7, 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 32, 33, 34, 35, 36, 37, 38,
+ 47, 49, 51, 52, 53, 54, 55};
+ for (int bit : bits) {
+ set.set(bit);
+ }
+ byte[] expected = {(byte) -128, (byte) -1, (byte) 0, (byte) 31,
+ (byte) 127, (byte) 128, (byte) 250};
+ assertTrue(Arrays.equals(expected, set.toByteArray()));
+
+ set.clear();
+ assertEquals(0, set.toByteArray().length);
+ }
+
+ public void testToLongArray() {
+ BitSet set = new BitSet();
+ assertEquals(0, set.toLongArray().length);
+
+ int[] bits = {63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82,
+ 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103,
+ 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121,
+ 122, 123, 124, 125, 126, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140,
+ 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158,
+ 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176,
+ 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 287, 288, 289,
+ 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307,
+ 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325,
+ 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343,
+ 344, 345, 346, 347, 348, 349, 350, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394,
+ 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412,
+ 413, 414, 450, 453, 454, 514, 515, 516, 519, 520, 521, 522, 523, 524, 525, 526, 527, 528,
+ 529, 530, 531, 532, 533, 534, 535, 536, 537, 538, 539, 540, 541, 542, 543, 544, 545, 546,
+ 547, 548, 549, 550, 551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564,
+ 565, 566, 567, 568, 569, 570, 571, 572, 573, 574, 575, 584, 640, 641, 642, 643, 644, 645,
+ 646, 711};
+ for (int bit : bits) {
+ set.set(bit);
+ }
+ long[] expected = {Long.MIN_VALUE, Long.MAX_VALUE, -1, 0, Integer.MIN_VALUE,
+ Integer.MAX_VALUE, 0x7fffffff, 100, -100, 256, 127, 128};
+ assertTrue(Arrays.equals(expected, set.toLongArray()));
+
+ set.clear();
+ assertEquals(0, set.toLongArray().length);
+ }
+
+ public void testValueOfBytes() {
+ BitSet set = BitSet.valueOf(new byte[0]);
+ assertTrue(set.isEmpty());
+
+ set = BitSet.valueOf(new byte[]{(byte) -128, (byte) -1, (byte) 0, (byte) 31,
+ (byte) 127, (byte) 128, (byte) 250});
+ assertEquals("{7, 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 32, 33, 34, 35, 36, 37, 38, " +
+ "47, 49, 51, 52, 53, 54, 55}", set.toString());
+ }
+
+ public void testValueOfLongs() {
+ BitSet set = BitSet.valueOf(new long[0]);
+ assertTrue(set.isEmpty());
+
+ set = BitSet.valueOf(new long[]{Long.MIN_VALUE, Long.MAX_VALUE, -1, 0, Integer.MIN_VALUE,
+ Integer.MAX_VALUE, 0x7fffffff, 100, -100, 256, 127, 128});
+ assertEquals("{63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, " +
+ "83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, " +
+ "104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, " +
+ "122, 123, 124, 125, 126, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, " +
+ "141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, " +
+ "159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, " +
+ "177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 287, 288, 289, " +
+ "290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, " +
+ "308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, " +
+ "326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, " +
+ "344, 345, 346, 347, 348, 349, 350, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, " +
+ "395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, " +
+ "413, 414, 450, 453, 454, 514, 515, 516, 519, 520, 521, 522, 523, 524, 525, 526, 527, 528, " +
+ "529, 530, 531, 532, 533, 534, 535, 536, 537, 538, 539, 540, 541, 542, 543, 544, 545, 546, " +
+ "547, 548, 549, 550, 551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564, " +
+ "565, 566, 567, 568, 569, 570, 571, 572, 573, 574, 575, 584, 640, 641, 642, 643, 644, 645, " +
+ "646, 711}", set.toString());
+ }
+}
