# HG changeset patch # User Jaroslav Tulach # Date 1383215812 -3600 # Node ID 9aeb2a41e009bc86bb3445a929e91c8641c1c781 # Parent a0690c970a4d86191dae2937e508bdc8b02d4099 Basic emulation of BitSet for NetBeans Javac 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: - * - * - * @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}. - * - *

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(); - } -} diff -r a0690c970a4d -r 9aeb2a41e009 rt/emul/compact/src/main/java/java/util/BitSet.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/rt/emul/compact/src/main/java/java/util/BitSet.java Thu Oct 31 11:36:52 2013 +0100 @@ -0,0 +1,1188 @@ +/* + * 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.*; + +/** + * 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: + * + * + * @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}. + * + *

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(); + } +}