| /* |
| * Copyright (c) 1995, 2007, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| package java.util; |
| |
| import java.io.*; |
| import java.nio.ByteBuffer; |
| import java.nio.ByteOrder; |
| import java.nio.LongBuffer; |
| |
| /** |
| * This class implements a vector of bits that grows as needed. Each |
| * component of the bit set has a {@code boolean} value. The |
| * bits of a {@code BitSet} are indexed by nonnegative integers. |
| * Individual indexed bits can be examined, set, or cleared. One |
| * {@code BitSet} may be used to modify the contents of another |
| * {@code BitSet} through logical AND, logical inclusive OR, and |
| * logical exclusive OR operations. |
| * |
| * <p>By default, all bits in the set initially have the value |
| * {@code false}. |
| * |
| * <p>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. |
| * |
| * <p>Unless otherwise noted, passing a null parameter to any of the |
| * methods in a {@code BitSet} will result in a |
| * {@code NullPointerException}. |
| * |
| * <p>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 BitSet implements Cloneable, java.io.Serializable { |
| /* |
| * BitSets are packed into arrays of "words." Currently a word is |
| * a long, which consists of 64 bits, requiring 6 address bits. |
| * The choice of word size is determined purely by performance concerns. |
| */ |
| private final static int ADDRESS_BITS_PER_WORD = 6; |
| private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD; |
| private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1; |
| |
| /* Used to shift left or right for a partial word mask */ |
| private static final long WORD_MASK = 0xffffffffffffffffL; |
| |
| /** |
| * @serialField bits long[] |
| * |
| * The bits in this BitSet. The ith bit is stored in bits[i/64] at |
| * bit position i % 64 (where bit position 0 refers to the least |
| * significant bit and 63 refers to the most significant bit). |
| */ |
| private static final ObjectStreamField[] serialPersistentFields = { |
| new ObjectStreamField("bits", long[].class), |
| }; |
| |
| /** |
| * The internal field corresponding to the serialField "bits". |
| */ |
| private long[] words; |
| |
| /** |
| * The number of words in the logical size of this BitSet. |
| */ |
| private 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. |
| */ |
| private static int wordIndex(int bitIndex) { |
| return bitIndex >> ADDRESS_BITS_PER_WORD; |
| } |
| |
| /** |
| * Every public method must preserve these invariants. |
| */ |
| private void checkInvariants() { |
| assert(wordsInUse == 0 || words[wordsInUse - 1] != 0); |
| assert(wordsInUse >= 0 && wordsInUse <= words.length); |
| assert(wordsInUse == words.length || words[wordsInUse] == 0); |
| } |
| |
| /** |
| * 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! |
| */ |
| private 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 BitSet() { |
| 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 |
| * @throws NegativeArraySizeException if the specified initial size |
| * is negative |
| */ |
| public BitSet(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 long[wordIndex(nbits-1) + 1]; |
| } |
| |
| /** |
| * Creates a bit set using words as the internal representation. |
| * The last word (if there is one) must be non-zero. |
| */ |
| private BitSet(long[] words) { |
| this.words = words; |
| this.wordsInUse = words.length; |
| checkInvariants(); |
| } |
| |
| /** |
| * Returns a new bit set containing all the bits in the given long array. |
| * |
| * <p>More precisely, |
| * <br>{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)} |
| * <br>for all {@code n < 64 * longs.length}. |
| * |
| * <p>This method is equivalent to |
| * {@code BitSet.valueOf(LongBuffer.wrap(longs))}. |
| * |
| * @param longs a long array containing a little-endian representation |
| * of a sequence of bits to be used as the initial bits of the |
| * new bit set |
| * @since 1.7 |
| */ |
| public static BitSet valueOf(long[] longs) { |
| int n; |
| for (n = longs.length; n > 0 && longs[n - 1] == 0; n--) |
| ; |
| return new BitSet(Arrays.copyOf(longs, n)); |
| } |
| |
| /** |
| * Returns a new bit set containing all the bits in the given long |
| * buffer between its position and limit. |
| * |
| * <p>More precisely, |
| * <br>{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)} |
| * <br>for all {@code n < 64 * lb.remaining()}. |
| * |
| * <p>The long buffer is not modified by this method, and no |
| * reference to the buffer is retained by the bit set. |
| * |
| * @param lb a long buffer containing a little-endian representation |
| * of a sequence of bits between its position and limit, to be |
| * used as the initial bits of the new bit set |
| * @since 1.7 |
| */ |
| public static BitSet valueOf(LongBuffer lb) { |
| lb = lb.slice(); |
| int n; |
| for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--) |
| ; |
| long[] words = new long[n]; |
| lb.get(words); |
| return new BitSet(words); |
| } |
| |
| /** |
| * Returns a new bit set containing all the bits in the given byte array. |
| * |
| * <p>More precisely, |
| * <br>{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)} |
| * <br>for all {@code n < 8 * bytes.length}. |
| * |
| * <p>This method is equivalent to |
| * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}. |
| * |
| * @param bytes a byte array containing a little-endian |
| * representation of a sequence of bits to be used as the |
| * initial bits of the new bit set |
| * @since 1.7 |
| */ |
| public static BitSet valueOf(byte[] bytes) { |
| return BitSet.valueOf(ByteBuffer.wrap(bytes)); |
| } |
| |
| /** |
| * Returns a new bit set containing all the bits in the given byte |
| * buffer between its position and limit. |
| * |
| * <p>More precisely, |
| * <br>{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)} |
| * <br>for all {@code n < 8 * bb.remaining()}. |
| * |
| * <p>The byte buffer is not modified by this method, and no |
| * reference to the buffer is retained by the bit set. |
| * |
| * @param bb a byte buffer containing a little-endian representation |
| * of a sequence of bits between its position and limit, to be |
| * used as the initial bits of the new bit set |
| * @since 1.7 |
| */ |
| public static BitSet valueOf(ByteBuffer bb) { |
| bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN); |
| int n; |
| for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--) |
| ; |
| long[] words = new long[(n + 7) / 8]; |
| bb.limit(n); |
| int i = 0; |
| while (bb.remaining() >= 8) |
| words[i++] = bb.getLong(); |
| for (int remaining = bb.remaining(), j = 0; j < remaining; j++) |
| words[i] |= (bb.get() & 0xffL) << (8 * j); |
| return new BitSet(words); |
| } |
| |
| /** |
| * Returns a new byte array containing all the bits in this bit set. |
| * |
| * <p>More precisely, if |
| * <br>{@code byte[] bytes = s.toByteArray();} |
| * <br>then {@code bytes.length == (s.length()+7)/8} and |
| * <br>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)} |
| * <br>for all {@code n < 8 * bytes.length}. |
| * |
| * @return a byte array containing a little-endian representation |
| * of all the bits in this bit set |
| * @since 1.7 |
| */ |
| public byte[] toByteArray() { |
| int n = wordsInUse; |
| if (n == 0) |
| return new byte[0]; |
| int len = 8 * (n-1); |
| for (long x = words[n - 1]; x != 0; x >>>= 8) |
| len++; |
| byte[] bytes = new byte[len]; |
| ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN); |
| for (int i = 0; i < n - 1; i++) |
| bb.putLong(words[i]); |
| for (long x = words[n - 1]; x != 0; x >>>= 8) |
| bb.put((byte) (x & 0xff)); |
| return bytes; |
| } |
| |
| /** |
| * Returns a new long array containing all the bits in this bit set. |
| * |
| * <p>More precisely, if |
| * <br>{@code long[] longs = s.toLongArray();} |
| * <br>then {@code longs.length == (s.length()+63)/64} and |
| * <br>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)} |
| * <br>for all {@code n < 64 * longs.length}. |
| * |
| * @return a long array containing a little-endian representation |
| * of all the bits in this bit set |
| * @since 1.7 |
| */ |
| public long[] toLongArray() { |
| return Arrays.copyOf(words, wordsInUse); |
| } |
| |
| /** |
| * 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); |
| words = Arrays.copyOf(words, 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. |
| */ |
| private void expandTo(int wordIndex) { |
| int wordsRequired = wordIndex+1; |
| if (wordsInUse < wordsRequired) { |
| ensureCapacity(wordsRequired); |
| wordsInUse = wordsRequired; |
| } |
| } |
| |
| /** |
| * Checks that fromIndex ... toIndex is a valid range of bit indices. |
| */ |
| private static void checkRange(int fromIndex, int toIndex) { |
| if (fromIndex < 0) |
| throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex); |
| if (toIndex < 0) |
| throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex); |
| if (fromIndex > toIndex) |
| throw new IndexOutOfBoundsException("fromIndex: " + fromIndex + |
| " > toIndex: " + toIndex); |
| } |
| |
| /** |
| * Sets the bit at the specified index to the complement of its |
| * current value. |
| * |
| * @param bitIndex the index of the bit to flip |
| * @throws IndexOutOfBoundsException if the specified index is negative |
| * @since 1.4 |
| */ |
| public void flip(int bitIndex) { |
| if (bitIndex < 0) |
| throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex); |
| |
| int wordIndex = wordIndex(bitIndex); |
| expandTo(wordIndex); |
| |
| words[wordIndex] ^= (1L << bitIndex); |
| |
| recalculateWordsInUse(); |
| checkInvariants(); |
| } |
| |
| /** |
| * Sets each bit from the specified {@code fromIndex} (inclusive) to the |
| * specified {@code toIndex} (exclusive) to the complement of its current |
| * value. |
| * |
| * @param fromIndex index of the first bit to flip |
| * @param toIndex index after the last bit to flip |
| * @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 flip(int fromIndex, int toIndex) { |
| checkRange(fromIndex, toIndex); |
| |
| if (fromIndex == toIndex) |
| return; |
| |
| int startWordIndex = wordIndex(fromIndex); |
| int endWordIndex = wordIndex(toIndex - 1); |
| expandTo(endWordIndex); |
| |
| long firstWordMask = WORD_MASK << fromIndex; |
| long 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 |
| words[endWordIndex] ^= lastWordMask; |
| } |
| |
| recalculateWordsInUse(); |
| checkInvariants(); |
| } |
| |
| /** |
| * 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] |= (1L << bitIndex); // Restores invariants |
| |
| checkInvariants(); |
| } |
| |
| /** |
| * 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 set(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 set(int fromIndex, int toIndex) { |
| checkRange(fromIndex, toIndex); |
| |
| if (fromIndex == toIndex) |
| return; |
| |
| // Increase capacity if necessary |
| int startWordIndex = wordIndex(fromIndex); |
| int endWordIndex = wordIndex(toIndex - 1); |
| expandTo(endWordIndex); |
| |
| long firstWordMask = WORD_MASK << fromIndex; |
| long 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; |
| } |
| |
| checkInvariants(); |
| } |
| |
| /** |
| * Sets the bits from the specified {@code fromIndex} (inclusive) to the |
| * specified {@code toIndex} (exclusive) to the specified value. |
| * |
| * @param fromIndex index of the first bit to be set |
| * @param toIndex index after the last bit to be set |
| * @param value value to set the selected bits to |
| * @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 set(int fromIndex, int toIndex, boolean value) { |
| if (value) |
| set(fromIndex, toIndex); |
| else |
| clear(fromIndex, toIndex); |
| } |
| |
| /** |
| * 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] &= ~(1L << bitIndex); |
| |
| recalculateWordsInUse(); |
| checkInvariants(); |
| } |
| |
| /** |
| * 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 clear(int fromIndex, int toIndex) { |
| checkRange(fromIndex, 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; |
| } |
| |
| long firstWordMask = WORD_MASK << fromIndex; |
| long 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(); |
| checkInvariants(); |
| } |
| |
| /** |
| * Sets all of the bits in this BitSet to {@code false}. |
| * |
| * @since 1.4 |
| */ |
| public void clear() { |
| 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); |
| |
| checkInvariants(); |
| |
| int wordIndex = wordIndex(bitIndex); |
| return (wordIndex < wordsInUse) |
| && ((words[wordIndex] & (1L << bitIndex)) != 0); |
| } |
| |
| /** |
| * Returns a new {@code BitSet} composed of bits from this {@code BitSet} |
| * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive). |
| * |
| * @param fromIndex index of the first bit to include |
| * @param toIndex index after the last bit to include |
| * @return a new {@code BitSet} from a range of this {@code BitSet} |
| * @throws IndexOutOfBoundsException if {@code fromIndex} is negative, |
| * or {@code toIndex} is negative, or {@code fromIndex} is |
| * larger than {@code toIndex} |
| * @since 1.4 |
| */ |
| public BitSet get(int fromIndex, int toIndex) { |
| checkRange(fromIndex, toIndex); |
| |
| checkInvariants(); |
| |
| int len = length(); |
| |
| // If no set bits in range return empty bitset |
| if (len <= fromIndex || fromIndex == toIndex) |
| return new BitSet(0); |
| |
| // An optimization |
| if (toIndex > len) |
| toIndex = len; |
| |
| BitSet result = new BitSet(toIndex - fromIndex); |
| int targetWords = wordIndex(toIndex - fromIndex - 1) + 1; |
| int sourceIndex = wordIndex(fromIndex); |
| boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0); |
| |
| // Process all words but the last word |
| for (int i = 0; i < targetWords - 1; i++, sourceIndex++) |
| result.words[i] = wordAligned ? words[sourceIndex] : |
| (words[sourceIndex] >>> fromIndex) | |
| (words[sourceIndex+1] << -fromIndex); |
| |
| // Process the last word |
| long lastWordMask = WORD_MASK >>> -toIndex; |
| result.words[targetWords - 1] = |
| ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK) |
| ? /* straddles source words */ |
| ((words[sourceIndex] >>> fromIndex) | |
| (words[sourceIndex+1] & lastWordMask) << -fromIndex) |
| : |
| ((words[sourceIndex] & lastWordMask) >>> fromIndex); |
| |
| // Set wordsInUse correctly |
| result.wordsInUse = targetWords; |
| result.recalculateWordsInUse(); |
| result.checkInvariants(); |
| |
| return result; |
| } |
| |
| /** |
| * 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. |
| * |
| * <p>To iterate over the {@code true} bits in a {@code BitSet}, |
| * use the following loop: |
| * |
| * <pre> {@code |
| * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) { |
| * // operate on index i here |
| * }}</pre> |
| * |
| * @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); |
| |
| checkInvariants(); |
| |
| int u = wordIndex(fromIndex); |
| if (u >= wordsInUse) |
| return -1; |
| |
| long word = words[u] & (WORD_MASK << fromIndex); |
| |
| while (true) { |
| if (word != 0) |
| return (u * BITS_PER_WORD) + Long.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); |
| |
| checkInvariants(); |
| |
| int u = wordIndex(fromIndex); |
| if (u >= wordsInUse) |
| return fromIndex; |
| |
| long word = ~words[u] & (WORD_MASK << fromIndex); |
| |
| while (true) { |
| if (word != 0) |
| return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word); |
| if (++u == wordsInUse) |
| return wordsInUse * BITS_PER_WORD; |
| word = ~words[u]; |
| } |
| } |
| |
| /** |
| * Returns the index of the nearest bit that is set to {@code true} |
| * that occurs on or before the specified starting index. |
| * If no such bit exists, or if {@code -1} is given as the |
| * starting index, then {@code -1} is returned. |
| * |
| * <p>To iterate over the {@code true} bits in a {@code BitSet}, |
| * use the following loop: |
| * |
| * <pre> {@code |
| * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) { |
| * // operate on index i here |
| * }}</pre> |
| * |
| * @param fromIndex the index to start checking from (inclusive) |
| * @return the index of the previous set bit, or {@code -1} if there |
| * is no such bit |
| * @throws IndexOutOfBoundsException if the specified index is less |
| * than {@code -1} |
| * @since 1.7 |
| */ |
| public int previousSetBit(int fromIndex) { |
| if (fromIndex < 0) { |
| if (fromIndex == -1) |
| return -1; |
| throw new IndexOutOfBoundsException( |
| "fromIndex < -1: " + fromIndex); |
| } |
| |
| checkInvariants(); |
| |
| int u = wordIndex(fromIndex); |
| if (u >= wordsInUse) |
| return length() - 1; |
| |
| long word = words[u] & (WORD_MASK >>> -(fromIndex+1)); |
| |
| while (true) { |
| if (word != 0) |
| return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word); |
| if (u-- == 0) |
| return -1; |
| word = words[u]; |
| } |
| } |
| |
| /** |
| * Returns the index of the nearest bit that is set to {@code false} |
| * that occurs on or before the specified starting index. |
| * If no such bit exists, or if {@code -1} is given as the |
| * starting index, then {@code -1} is returned. |
| * |
| * @param fromIndex the index to start checking from (inclusive) |
| * @return the index of the previous clear bit, or {@code -1} if there |
| * is no such bit |
| * @throws IndexOutOfBoundsException if the specified index is less |
| * than {@code -1} |
| * @since 1.7 |
| */ |
| public int previousClearBit(int fromIndex) { |
| if (fromIndex < 0) { |
| if (fromIndex == -1) |
| return -1; |
| throw new IndexOutOfBoundsException( |
| "fromIndex < -1: " + fromIndex); |
| } |
| |
| checkInvariants(); |
| |
| int u = wordIndex(fromIndex); |
| if (u >= wordsInUse) |
| return fromIndex; |
| |
| long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1)); |
| |
| while (true) { |
| if (word != 0) |
| return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word); |
| if (u-- == 0) |
| return -1; |
| 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 - Long.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(BitSet 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 += Long.bitCount(words[i]); |
| return sum; |
| } |
| |
| /** |
| * Performs a logical <b>AND</b> 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(BitSet 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(); |
| checkInvariants(); |
| } |
| |
| /** |
| * Performs a logical <b>OR</b> 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(BitSet 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); |
| |
| // recalculateWordsInUse() is unnecessary |
| checkInvariants(); |
| } |
| |
| /** |
| * Performs a logical <b>XOR</b> 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: |
| * <ul> |
| * <li>The bit initially has the value {@code true}, and the |
| * corresponding bit in the argument has the value {@code false}. |
| * <li>The bit initially has the value {@code false}, and the |
| * corresponding bit in the argument has the value {@code true}. |
| * </ul> |
| * |
| * @param set a bit set |
| */ |
| public void xor(BitSet set) { |
| int wordsInCommon = Math.min(wordsInUse, set.wordsInUse); |
| |
| if (wordsInUse < set.wordsInUse) { |
| ensureCapacity(set.wordsInUse); |
| wordsInUse = set.wordsInUse; |
| } |
| |
| // Perform logical XOR 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, |
| set.wordsInUse - wordsInCommon); |
| |
| recalculateWordsInUse(); |
| checkInvariants(); |
| } |
| |
| /** |
| * Clears all of the bits in this {@code BitSet} whose corresponding |
| * bit is set in the specified {@code BitSet}. |
| * |
| * @param set the {@code BitSet} with which to mask this |
| * {@code BitSet} |
| * @since 1.2 |
| */ |
| public void andNot(BitSet set) { |
| // Perform logical (a & !b) on words in common |
| for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--) |
| words[i] &= ~set.words[i]; |
| |
| recalculateWordsInUse(); |
| checkInvariants(); |
| } |
| |
| /** |
| * Returns the hash code value for this bit set. The hash code depends |
| * only on which bits are set within this {@code BitSet}. |
| * |
| * <p>The hash code is defined to be the result of the following |
| * calculation: |
| * <pre> {@code |
| * public int hashCode() { |
| * long h = 1234; |
| * long[] words = toLongArray(); |
| * for (int i = words.length; --i >= 0; ) |
| * h ^= words[i] * (i + 1); |
| * return (int)((h >> 32) ^ h); |
| * }}</pre> |
| * Note that the hash code changes if the set of bits is altered. |
| * |
| * @return the hash code value for this bit set |
| */ |
| 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}, |
| * <pre>((BitSet)obj).get(k) == this.get(k)</pre> |
| * 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() |
| */ |
| public boolean equals(Object obj) { |
| if (!(obj instanceof BitSet)) |
| return false; |
| if (this == obj) |
| return true; |
| |
| BitSet set = (BitSet) obj; |
| |
| checkInvariants(); |
| set.checkInvariants(); |
| |
| 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() |
| */ |
| public Object clone() { |
| if (! sizeIsSticky) |
| trimToSize(); |
| |
| try { |
| BitSet result = (BitSet) super.clone(); |
| result.words = words.clone(); |
| result.checkInvariants(); |
| return result; |
| } catch (CloneNotSupportedException e) { |
| throw new InternalError(); |
| } |
| } |
| |
| /** |
| * 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. |
| */ |
| private void trimToSize() { |
| if (wordsInUse != words.length) { |
| words = Arrays.copyOf(words, wordsInUse); |
| checkInvariants(); |
| } |
| } |
| |
| /** |
| * Save the state of the {@code BitSet} instance to a stream (i.e., |
| * serialize it). |
| */ |
| private void writeObject(ObjectOutputStream s) |
| throws IOException { |
| |
| checkInvariants(); |
| |
| if (! sizeIsSticky) |
| trimToSize(); |
| |
| ObjectOutputStream.PutField fields = s.putFields(); |
| fields.put("bits", words); |
| s.writeFields(); |
| } |
| |
| /** |
| * Reconstitute the {@code BitSet} instance from a stream (i.e., |
| * deserialize it). |
| */ |
| private void readObject(ObjectInputStream s) |
| throws IOException, ClassNotFoundException { |
| |
| ObjectInputStream.GetField fields = s.readFields(); |
| words = (long[]) fields.get("bits", null); |
| |
| // Assume maximum length then find real length |
| // because recalculateWordsInUse assumes maintenance |
| // or reduction in logical size |
| wordsInUse = words.length; |
| recalculateWordsInUse(); |
| sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic |
| checkInvariants(); |
| } |
| |
| /** |
| * 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. |
| * |
| * <p>Example: |
| * <pre> |
| * BitSet drPepper = new BitSet();</pre> |
| * Now {@code drPepper.toString()} returns "{@code {}}".<p> |
| * <pre> |
| * drPepper.set(2);</pre> |
| * Now {@code drPepper.toString()} returns "{@code {2}}".<p> |
| * <pre> |
| * drPepper.set(4); |
| * drPepper.set(10);</pre> |
| * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}". |
| * |
| * @return a string representation of this bit set |
| */ |
| public String toString() { |
| checkInvariants(); |
| |
| int numBits = (wordsInUse > 128) ? |
| cardinality() : wordsInUse * BITS_PER_WORD; |
| StringBuilder b = new StringBuilder(6*numBits + 2); |
| b.append('{'); |
| |
| int i = nextSetBit(0); |
| if (i != -1) { |
| b.append(i); |
| for (i = nextSetBit(i+1); i >= 0; i = nextSetBit(i+1)) { |
| int endOfRun = nextClearBit(i); |
| do { b.append(", ").append(i); } |
| while (++i < endOfRun); |
| } |
| } |
| |
| b.append('}'); |
| return b.toString(); |
| } |
| } |
