diff -r a0690c970a4d -r 9aeb2a41e009 emul/compact/src/main/java/java/util/BitSet.java --- a/emul/compact/src/main/java/java/util/BitSet.java Thu Oct 31 11:30:50 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1191 +0,0 @@ -/* - * 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. - * - *
By default, all bits in the set initially have the value - * {@code false}. - * - *
Every bit set has a current size, which is the number of bits - * of space currently in use by the bit set. Note that the size is - * related to the implementation of a bit set, so it may change with - * implementation. The length of a bit set relates to logical length - * of a bit set and is defined independently of implementation. - * - *
Unless otherwise noted, passing a null parameter to any of the - * methods in a {@code BitSet} will result in a - * {@code NullPointerException}. - * - *
A {@code BitSet} is not safe for multithreaded use without - * external synchronization. - * - * @author Arthur van Hoff - * @author Michael McCloskey - * @author Martin Buchholz - * @since JDK1.0 - */ -public class 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. - * - *
More precisely,
- *
{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
- *
for all {@code n < 64 * longs.length}.
- *
- *
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. - * - *
More precisely,
- *
{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)}
- *
for all {@code n < 64 * lb.remaining()}.
- *
- *
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. - * - *
More precisely,
- *
{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
- *
for all {@code n < 8 * bytes.length}.
- *
- *
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. - * - *
More precisely,
- *
{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)}
- *
for all {@code n < 8 * bb.remaining()}.
- *
- *
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. - * - *
More precisely, if
- *
{@code byte[] bytes = s.toByteArray();}
- *
then {@code bytes.length == (s.length()+7)/8} and
- *
{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
- *
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.
- *
- *
More precisely, if
- *
{@code long[] longs = s.toLongArray();}
- *
then {@code longs.length == (s.length()+63)/64} and
- *
{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
- *
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.
- *
- *
To iterate over the {@code true} bits in a {@code BitSet}, - * use the following loop: - * - *
{@code - * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) { - * // operate on index i here - * }}- * - * @param fromIndex the index to start checking from (inclusive) - * @return the index of the next set bit, or {@code -1} if there - * is no such bit - * @throws IndexOutOfBoundsException if the specified index is negative - * @since 1.4 - */ - public int nextSetBit(int fromIndex) { - if (fromIndex < 0) - throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex); - - 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. - * - *
To iterate over the {@code true} bits in a {@code BitSet}, - * use the following loop: - * - *
{@code - * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) { - * // operate on index i here - * }}- * - * @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 AND of this target bit set with the - * argument bit set. This bit set is modified so that each bit in it - * has the value {@code true} if and only if it both initially - * had the value {@code true} and the corresponding bit in the - * bit set argument also had the value {@code true}. - * - * @param set a bit set - */ - public void and(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 OR of this bit set with the bit set - * argument. This bit set is modified so that a bit in it has the - * value {@code true} if and only if it either already had the - * value {@code true} or the corresponding bit in the bit set - * argument has the value {@code true}. - * - * @param set a bit set - */ - public void or(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 XOR of this bit set with the bit set - * argument. This bit set is modified so that a bit in it has the - * value {@code true} if and only if one of the following - * statements holds: - *
The hash code is defined to be the result of the following - * calculation: - *
{@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); - * }}- * 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}, - *
((BitSet)obj).get(k) == this.get(k)- * must be true. The current sizes of the two bit sets are not compared. - * - * @param obj the object to compare with - * @return {@code true} if the objects are the same; - * {@code false} otherwise - * @see #size() - */ - 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. - * - *
Example: - *
- * BitSet drPepper = new BitSet();- * Now {@code drPepper.toString()} returns "{@code {}}".
- *
- * drPepper.set(2);- * Now {@code drPepper.toString()} returns "{@code {2}}".
- *
- * drPepper.set(4); - * drPepper.set(10);- * 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(); - } -}