0001 /*
0002 * Copyright 1995-2007 Sun Microsystems, Inc. All Rights Reserved.
0003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0004 *
0005 * This code is free software; you can redistribute it and/or modify it
0006 * under the terms of the GNU General Public License version 2 only, as
0007 * published by the Free Software Foundation. Sun designates this
0008 * particular file as subject to the "Classpath" exception as provided
0009 * by Sun in the LICENSE file that accompanied this code.
0010 *
0011 * This code is distributed in the hope that it will be useful, but WITHOUT
0012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0014 * version 2 for more details (a copy is included in the LICENSE file that
0015 * accompanied this code).
0016 *
0017 * You should have received a copy of the GNU General Public License version
0018 * 2 along with this work; if not, write to the Free Software Foundation,
0019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0020 *
0021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0022 * CA 95054 USA or visit www.sun.com if you need additional information or
0023 * have any questions.
0024 */
0025
0026 package java.util;
0027
0028 import java.io.*;
0029 import java.nio.ByteBuffer;
0030 import java.nio.ByteOrder;
0031 import java.nio.LongBuffer;
0032
0033 /**
0034 * This class implements a vector of bits that grows as needed. Each
0035 * component of the bit set has a {@code boolean} value. The
0036 * bits of a {@code BitSet} are indexed by nonnegative integers.
0037 * Individual indexed bits can be examined, set, or cleared. One
0038 * {@code BitSet} may be used to modify the contents of another
0039 * {@code BitSet} through logical AND, logical inclusive OR, and
0040 * logical exclusive OR operations.
0041 *
0042 * <p>By default, all bits in the set initially have the value
0043 * {@code false}.
0044 *
0045 * <p>Every bit set has a current size, which is the number of bits
0046 * of space currently in use by the bit set. Note that the size is
0047 * related to the implementation of a bit set, so it may change with
0048 * implementation. The length of a bit set relates to logical length
0049 * of a bit set and is defined independently of implementation.
0050 *
0051 * <p>Unless otherwise noted, passing a null parameter to any of the
0052 * methods in a {@code BitSet} will result in a
0053 * {@code NullPointerException}.
0054 *
0055 * <p>A {@code BitSet} is not safe for multithreaded use without
0056 * external synchronization.
0057 *
0058 * @author Arthur van Hoff
0059 * @author Michael McCloskey
0060 * @author Martin Buchholz
0061 * @version 1.74, 06/12/07
0062 * @since JDK1.0
0063 */
0064 public class BitSet implements Cloneable, java.io.Serializable {
0065 /*
0066 * BitSets are packed into arrays of "words." Currently a word is
0067 * a long, which consists of 64 bits, requiring 6 address bits.
0068 * The choice of word size is determined purely by performance concerns.
0069 */
0070 private final static int ADDRESS_BITS_PER_WORD = 6;
0071 private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
0072 private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
0073
0074 /* Used to shift left or right for a partial word mask */
0075 private static final long WORD_MASK = 0xffffffffffffffffL;
0076
0077 /**
0078 * @serialField bits long[]
0079 *
0080 * The bits in this BitSet. The ith bit is stored in bits[i/64] at
0081 * bit position i % 64 (where bit position 0 refers to the least
0082 * significant bit and 63 refers to the most significant bit).
0083 */
0084 private static final ObjectStreamField[] serialPersistentFields = { new ObjectStreamField(
0085 "bits", long[].class), };
0086
0087 /**
0088 * The internal field corresponding to the serialField "bits".
0089 */
0090 private long[] words;
0091
0092 /**
0093 * The number of words in the logical size of this BitSet.
0094 */
0095 private transient int wordsInUse = 0;
0096
0097 /**
0098 * Whether the size of "words" is user-specified. If so, we assume
0099 * the user knows what he's doing and try harder to preserve it.
0100 */
0101 private transient boolean sizeIsSticky = false;
0102
0103 /* use serialVersionUID from JDK 1.0.2 for interoperability */
0104 private static final long serialVersionUID = 7997698588986878753L;
0105
0106 /**
0107 * Given a bit index, return word index containing it.
0108 */
0109 private static int wordIndex(int bitIndex) {
0110 return bitIndex >> ADDRESS_BITS_PER_WORD;
0111 }
0112
0113 /**
0114 * Every public method must preserve these invariants.
0115 */
0116 private void checkInvariants() {
0117 assert (wordsInUse == 0 || words[wordsInUse - 1] != 0);
0118 assert (wordsInUse >= 0 && wordsInUse <= words.length);
0119 assert (wordsInUse == words.length || words[wordsInUse] == 0);
0120 }
0121
0122 /**
0123 * Sets the field wordsInUse to the logical size in words of the bit set.
0124 * WARNING:This method assumes that the number of words actually in use is
0125 * less than or equal to the current value of wordsInUse!
0126 */
0127 private void recalculateWordsInUse() {
0128 // Traverse the bitset until a used word is found
0129 int i;
0130 for (i = wordsInUse - 1; i >= 0; i--)
0131 if (words[i] != 0)
0132 break;
0133
0134 wordsInUse = i + 1; // The new logical size
0135 }
0136
0137 /**
0138 * Creates a new bit set. All bits are initially {@code false}.
0139 */
0140 public BitSet() {
0141 initWords(BITS_PER_WORD);
0142 sizeIsSticky = false;
0143 }
0144
0145 /**
0146 * Creates a bit set whose initial size is large enough to explicitly
0147 * represent bits with indices in the range {@code 0} through
0148 * {@code nbits-1}. All bits are initially {@code false}.
0149 *
0150 * @param nbits the initial size of the bit set
0151 * @throws NegativeArraySizeException if the specified initial size
0152 * is negative
0153 */
0154 public BitSet(int nbits) {
0155 // nbits can't be negative; size 0 is OK
0156 if (nbits < 0)
0157 throw new NegativeArraySizeException("nbits < 0: " + nbits);
0158
0159 initWords(nbits);
0160 sizeIsSticky = true;
0161 }
0162
0163 private void initWords(int nbits) {
0164 words = new long[wordIndex(nbits - 1) + 1];
0165 }
0166
0167 /**
0168 * Creates a bit set using words as the internal representation.
0169 * The last word (if there is one) must be non-zero.
0170 */
0171 private BitSet(long[] words) {
0172 this .words = words;
0173 this .wordsInUse = words.length;
0174 checkInvariants();
0175 }
0176
0177 /**
0178 * Returns a new bit set containing all the bits in the given long array.
0179 *
0180 * <p>More precisely,
0181 * <br>{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
0182 * <br>for all {@code n < 64 * longs.length}.
0183 *
0184 * <p>This method is equivalent to
0185 * {@code BitSet.valueOf(LongBuffer.wrap(longs))}.
0186 *
0187 * @param longs a long array containing a little-endian representation
0188 * of a sequence of bits to be used as the initial bits of the
0189 * new bit set
0190 * @since 1.7
0191 */
0192 public static BitSet valueOf(long[] longs) {
0193 int n;
0194 for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)
0195 ;
0196 return new BitSet(Arrays.copyOf(longs, n));
0197 }
0198
0199 /**
0200 * Returns a new bit set containing all the bits in the given long
0201 * buffer between its position and limit.
0202 *
0203 * <p>More precisely,
0204 * <br>{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)}
0205 * <br>for all {@code n < 64 * lb.remaining()}.
0206 *
0207 * <p>The long buffer is not modified by this method, and no
0208 * reference to the buffer is retained by the bit set.
0209 *
0210 * @param lb a long buffer containing a little-endian representation
0211 * of a sequence of bits between its position and limit, to be
0212 * used as the initial bits of the new bit set
0213 * @since 1.7
0214 */
0215 public static BitSet valueOf(LongBuffer lb) {
0216 lb = lb.slice();
0217 int n;
0218 for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)
0219 ;
0220 long[] words = new long[n];
0221 lb.get(words);
0222 return new BitSet(words);
0223 }
0224
0225 /**
0226 * Returns a new bit set containing all the bits in the given byte array.
0227 *
0228 * <p>More precisely,
0229 * <br>{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
0230 * <br>for all {@code n < 8 * bytes.length}.
0231 *
0232 * <p>This method is equivalent to
0233 * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}.
0234 *
0235 * @param bytes a byte array containing a little-endian
0236 * representation of a sequence of bits to be used as the
0237 * initial bits of the new bit set
0238 * @since 1.7
0239 */
0240 public static BitSet valueOf(byte[] bytes) {
0241 return BitSet.valueOf(ByteBuffer.wrap(bytes));
0242 }
0243
0244 /**
0245 * Returns a new bit set containing all the bits in the given byte
0246 * buffer between its position and limit.
0247 *
0248 * <p>More precisely,
0249 * <br>{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)}
0250 * <br>for all {@code n < 8 * bb.remaining()}.
0251 *
0252 * <p>The byte buffer is not modified by this method, and no
0253 * reference to the buffer is retained by the bit set.
0254 *
0255 * @param bb a byte buffer containing a little-endian representation
0256 * of a sequence of bits between its position and limit, to be
0257 * used as the initial bits of the new bit set
0258 * @since 1.7
0259 */
0260 public static BitSet valueOf(ByteBuffer bb) {
0261 bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);
0262 int n;
0263 for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--)
0264 ;
0265 long[] words = new long[(n + 7) / 8];
0266 bb.limit(n);
0267 int i = 0;
0268 while (bb.remaining() >= 8)
0269 words[i++] = bb.getLong();
0270 for (int remaining = bb.remaining(), j = 0; j < remaining; j++)
0271 words[i] |= (bb.get() & 0xffL) << (8 * j);
0272 return new BitSet(words);
0273 }
0274
0275 /**
0276 * Returns a new byte array containing all the bits in this bit set.
0277 *
0278 * <p>More precisely, if
0279 * <br>{@code byte[] bytes = s.toByteArray();}
0280 * <br>then {@code bytes.length == (s.length()+7)/8} and
0281 * <br>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
0282 * <br>for all {@code n < 8 * bytes.length}.
0283 *
0284 * @return a byte array containing a little-endian representation
0285 * of all the bits in this bit set
0286 * @since 1.7
0287 */
0288 public byte[] toByteArray() {
0289 int n = wordsInUse;
0290 if (n == 0)
0291 return new byte[0];
0292 int len = 8 * (n - 1);
0293 for (long x = words[n - 1]; x != 0; x >>>= 8)
0294 len++;
0295 byte[] bytes = new byte[len];
0296 ByteBuffer bb = ByteBuffer.wrap(bytes).order(
0297 ByteOrder.LITTLE_ENDIAN);
0298 for (int i = 0; i < n - 1; i++)
0299 bb.putLong(words[i]);
0300 for (long x = words[n - 1]; x != 0; x >>>= 8)
0301 bb.put((byte) (x & 0xff));
0302 return bytes;
0303 }
0304
0305 /**
0306 * Returns a new long array containing all the bits in this bit set.
0307 *
0308 * <p>More precisely, if
0309 * <br>{@code long[] longs = s.toLongArray();}
0310 * <br>then {@code longs.length == (s.length()+63)/64} and
0311 * <br>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
0312 * <br>for all {@code n < 64 * longs.length}.
0313 *
0314 * @return a long array containing a little-endian representation
0315 * of all the bits in this bit set
0316 * @since 1.7
0317 */
0318 public long[] toLongArray() {
0319 return Arrays.copyOf(words, wordsInUse);
0320 }
0321
0322 /**
0323 * Ensures that the BitSet can hold enough words.
0324 * @param wordsRequired the minimum acceptable number of words.
0325 */
0326 private void ensureCapacity(int wordsRequired) {
0327 if (words.length < wordsRequired) {
0328 // Allocate larger of doubled size or required size
0329 int request = Math.max(2 * words.length, wordsRequired);
0330 words = Arrays.copyOf(words, request);
0331 sizeIsSticky = false;
0332 }
0333 }
0334
0335 /**
0336 * Ensures that the BitSet can accommodate a given wordIndex,
0337 * temporarily violating the invariants. The caller must
0338 * restore the invariants before returning to the user,
0339 * possibly using recalculateWordsInUse().
0340 * @param wordIndex the index to be accommodated.
0341 */
0342 private void expandTo(int wordIndex) {
0343 int wordsRequired = wordIndex + 1;
0344 if (wordsInUse < wordsRequired) {
0345 ensureCapacity(wordsRequired);
0346 wordsInUse = wordsRequired;
0347 }
0348 }
0349
0350 /**
0351 * Checks that fromIndex ... toIndex is a valid range of bit indices.
0352 */
0353 private static void checkRange(int fromIndex, int toIndex) {
0354 if (fromIndex < 0)
0355 throw new IndexOutOfBoundsException("fromIndex < 0: "
0356 + fromIndex);
0357 if (toIndex < 0)
0358 throw new IndexOutOfBoundsException("toIndex < 0: "
0359 + toIndex);
0360 if (fromIndex > toIndex)
0361 throw new IndexOutOfBoundsException("fromIndex: "
0362 + fromIndex + " > toIndex: " + toIndex);
0363 }
0364
0365 /**
0366 * Sets the bit at the specified index to the complement of its
0367 * current value.
0368 *
0369 * @param bitIndex the index of the bit to flip
0370 * @throws IndexOutOfBoundsException if the specified index is negative
0371 * @since 1.4
0372 */
0373 public void flip(int bitIndex) {
0374 if (bitIndex < 0)
0375 throw new IndexOutOfBoundsException("bitIndex < 0: "
0376 + bitIndex);
0377
0378 int wordIndex = wordIndex(bitIndex);
0379 expandTo(wordIndex);
0380
0381 words[wordIndex] ^= (1L << bitIndex);
0382
0383 recalculateWordsInUse();
0384 checkInvariants();
0385 }
0386
0387 /**
0388 * Sets each bit from the specified {@code fromIndex} (inclusive) to the
0389 * specified {@code toIndex} (exclusive) to the complement of its current
0390 * value.
0391 *
0392 * @param fromIndex index of the first bit to flip
0393 * @param toIndex index after the last bit to flip
0394 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
0395 * or {@code toIndex} is negative, or {@code fromIndex} is
0396 * larger than {@code toIndex}
0397 * @since 1.4
0398 */
0399 public void flip(int fromIndex, int toIndex) {
0400 checkRange(fromIndex, toIndex);
0401
0402 if (fromIndex == toIndex)
0403 return;
0404
0405 int startWordIndex = wordIndex(fromIndex);
0406 int endWordIndex = wordIndex(toIndex - 1);
0407 expandTo(endWordIndex);
0408
0409 long firstWordMask = WORD_MASK << fromIndex;
0410 long lastWordMask = WORD_MASK >>> -toIndex;
0411 if (startWordIndex == endWordIndex) {
0412 // Case 1: One word
0413 words[startWordIndex] ^= (firstWordMask & lastWordMask);
0414 } else {
0415 // Case 2: Multiple words
0416 // Handle first word
0417 words[startWordIndex] ^= firstWordMask;
0418
0419 // Handle intermediate words, if any
0420 for (int i = startWordIndex + 1; i < endWordIndex; i++)
0421 words[i] ^= WORD_MASK;
0422
0423 // Handle last word
0424 words[endWordIndex] ^= lastWordMask;
0425 }
0426
0427 recalculateWordsInUse();
0428 checkInvariants();
0429 }
0430
0431 /**
0432 * Sets the bit at the specified index to {@code true}.
0433 *
0434 * @param bitIndex a bit index
0435 * @throws IndexOutOfBoundsException if the specified index is negative
0436 * @since JDK1.0
0437 */
0438 public void set(int bitIndex) {
0439 if (bitIndex < 0)
0440 throw new IndexOutOfBoundsException("bitIndex < 0: "
0441 + bitIndex);
0442
0443 int wordIndex = wordIndex(bitIndex);
0444 expandTo(wordIndex);
0445
0446 words[wordIndex] |= (1L << bitIndex); // Restores invariants
0447
0448 checkInvariants();
0449 }
0450
0451 /**
0452 * Sets the bit at the specified index to the specified value.
0453 *
0454 * @param bitIndex a bit index
0455 * @param value a boolean value to set
0456 * @throws IndexOutOfBoundsException if the specified index is negative
0457 * @since 1.4
0458 */
0459 public void set(int bitIndex, boolean value) {
0460 if (value)
0461 set(bitIndex);
0462 else
0463 clear(bitIndex);
0464 }
0465
0466 /**
0467 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
0468 * specified {@code toIndex} (exclusive) to {@code true}.
0469 *
0470 * @param fromIndex index of the first bit to be set
0471 * @param toIndex index after the last bit to be set
0472 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
0473 * or {@code toIndex} is negative, or {@code fromIndex} is
0474 * larger than {@code toIndex}
0475 * @since 1.4
0476 */
0477 public void set(int fromIndex, int toIndex) {
0478 checkRange(fromIndex, toIndex);
0479
0480 if (fromIndex == toIndex)
0481 return;
0482
0483 // Increase capacity if necessary
0484 int startWordIndex = wordIndex(fromIndex);
0485 int endWordIndex = wordIndex(toIndex - 1);
0486 expandTo(endWordIndex);
0487
0488 long firstWordMask = WORD_MASK << fromIndex;
0489 long lastWordMask = WORD_MASK >>> -toIndex;
0490 if (startWordIndex == endWordIndex) {
0491 // Case 1: One word
0492 words[startWordIndex] |= (firstWordMask & lastWordMask);
0493 } else {
0494 // Case 2: Multiple words
0495 // Handle first word
0496 words[startWordIndex] |= firstWordMask;
0497
0498 // Handle intermediate words, if any
0499 for (int i = startWordIndex + 1; i < endWordIndex; i++)
0500 words[i] = WORD_MASK;
0501
0502 // Handle last word (restores invariants)
0503 words[endWordIndex] |= lastWordMask;
0504 }
0505
0506 checkInvariants();
0507 }
0508
0509 /**
0510 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
0511 * specified {@code toIndex} (exclusive) to the specified value.
0512 *
0513 * @param fromIndex index of the first bit to be set
0514 * @param toIndex index after the last bit to be set
0515 * @param value value to set the selected bits to
0516 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
0517 * or {@code toIndex} is negative, or {@code fromIndex} is
0518 * larger than {@code toIndex}
0519 * @since 1.4
0520 */
0521 public void set(int fromIndex, int toIndex, boolean value) {
0522 if (value)
0523 set(fromIndex, toIndex);
0524 else
0525 clear(fromIndex, toIndex);
0526 }
0527
0528 /**
0529 * Sets the bit specified by the index to {@code false}.
0530 *
0531 * @param bitIndex the index of the bit to be cleared
0532 * @throws IndexOutOfBoundsException if the specified index is negative
0533 * @since JDK1.0
0534 */
0535 public void clear(int bitIndex) {
0536 if (bitIndex < 0)
0537 throw new IndexOutOfBoundsException("bitIndex < 0: "
0538 + bitIndex);
0539
0540 int wordIndex = wordIndex(bitIndex);
0541 if (wordIndex >= wordsInUse)
0542 return;
0543
0544 words[wordIndex] &= ~(1L << bitIndex);
0545
0546 recalculateWordsInUse();
0547 checkInvariants();
0548 }
0549
0550 /**
0551 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
0552 * specified {@code toIndex} (exclusive) to {@code false}.
0553 *
0554 * @param fromIndex index of the first bit to be cleared
0555 * @param toIndex index after the last bit to be cleared
0556 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
0557 * or {@code toIndex} is negative, or {@code fromIndex} is
0558 * larger than {@code toIndex}
0559 * @since 1.4
0560 */
0561 public void clear(int fromIndex, int toIndex) {
0562 checkRange(fromIndex, toIndex);
0563
0564 if (fromIndex == toIndex)
0565 return;
0566
0567 int startWordIndex = wordIndex(fromIndex);
0568 if (startWordIndex >= wordsInUse)
0569 return;
0570
0571 int endWordIndex = wordIndex(toIndex - 1);
0572 if (endWordIndex >= wordsInUse) {
0573 toIndex = length();
0574 endWordIndex = wordsInUse - 1;
0575 }
0576
0577 long firstWordMask = WORD_MASK << fromIndex;
0578 long lastWordMask = WORD_MASK >>> -toIndex;
0579 if (startWordIndex == endWordIndex) {
0580 // Case 1: One word
0581 words[startWordIndex] &= ~(firstWordMask & lastWordMask);
0582 } else {
0583 // Case 2: Multiple words
0584 // Handle first word
0585 words[startWordIndex] &= ~firstWordMask;
0586
0587 // Handle intermediate words, if any
0588 for (int i = startWordIndex + 1; i < endWordIndex; i++)
0589 words[i] = 0;
0590
0591 // Handle last word
0592 words[endWordIndex] &= ~lastWordMask;
0593 }
0594
0595 recalculateWordsInUse();
0596 checkInvariants();
0597 }
0598
0599 /**
0600 * Sets all of the bits in this BitSet to {@code false}.
0601 *
0602 * @since 1.4
0603 */
0604 public void clear() {
0605 while (wordsInUse > 0)
0606 words[--wordsInUse] = 0;
0607 }
0608
0609 /**
0610 * Returns the value of the bit with the specified index. The value
0611 * is {@code true} if the bit with the index {@code bitIndex}
0612 * is currently set in this {@code BitSet}; otherwise, the result
0613 * is {@code false}.
0614 *
0615 * @param bitIndex the bit index
0616 * @return the value of the bit with the specified index
0617 * @throws IndexOutOfBoundsException if the specified index is negative
0618 */
0619 public boolean get(int bitIndex) {
0620 if (bitIndex < 0)
0621 throw new IndexOutOfBoundsException("bitIndex < 0: "
0622 + bitIndex);
0623
0624 checkInvariants();
0625
0626 int wordIndex = wordIndex(bitIndex);
0627 return (wordIndex < wordsInUse)
0628 && ((words[wordIndex] & (1L << bitIndex)) != 0);
0629 }
0630
0631 /**
0632 * Returns a new {@code BitSet} composed of bits from this {@code BitSet}
0633 * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).
0634 *
0635 * @param fromIndex index of the first bit to include
0636 * @param toIndex index after the last bit to include
0637 * @return a new {@code BitSet} from a range of this {@code BitSet}
0638 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
0639 * or {@code toIndex} is negative, or {@code fromIndex} is
0640 * larger than {@code toIndex}
0641 * @since 1.4
0642 */
0643 public BitSet get(int fromIndex, int toIndex) {
0644 checkRange(fromIndex, toIndex);
0645
0646 checkInvariants();
0647
0648 int len = length();
0649
0650 // If no set bits in range return empty bitset
0651 if (len <= fromIndex || fromIndex == toIndex)
0652 return new BitSet(0);
0653
0654 // An optimization
0655 if (toIndex > len)
0656 toIndex = len;
0657
0658 BitSet result = new BitSet(toIndex - fromIndex);
0659 int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;
0660 int sourceIndex = wordIndex(fromIndex);
0661 boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);
0662
0663 // Process all words but the last word
0664 for (int i = 0; i < targetWords - 1; i++, sourceIndex++)
0665 result.words[i] = wordAligned ? words[sourceIndex]
0666 : (words[sourceIndex] >>> fromIndex)
0667 | (words[sourceIndex + 1] << -fromIndex);
0668
0669 // Process the last word
0670 long lastWordMask = WORD_MASK >>> -toIndex;
0671 result.words[targetWords - 1] = ((toIndex - 1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK) ? /* straddles source words */
0672 ((words[sourceIndex] >>> fromIndex) | (words[sourceIndex + 1] & lastWordMask) << -fromIndex)
0673 : ((words[sourceIndex] & lastWordMask) >>> fromIndex);
0674
0675 // Set wordsInUse correctly
0676 result.wordsInUse = targetWords;
0677 result.recalculateWordsInUse();
0678 result.checkInvariants();
0679
0680 return result;
0681 }
0682
0683 /**
0684 * Returns the index of the first bit that is set to {@code true}
0685 * that occurs on or after the specified starting index. If no such
0686 * bit exists then -1 is returned.
0687 *
0688 * To iterate over the {@code true} bits in a {@code BitSet},
0689 * use the following loop:
0690 *
0691 * <pre>
0692 * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
0693 * // operate on index i here
0694 * }</pre>
0695 *
0696 * @param fromIndex the index to start checking from (inclusive)
0697 * @return the index of the next set bit
0698 * @throws IndexOutOfBoundsException if the specified index is negative
0699 * @since 1.4
0700 */
0701 public int nextSetBit(int fromIndex) {
0702 if (fromIndex < 0)
0703 throw new IndexOutOfBoundsException("fromIndex < 0: "
0704 + fromIndex);
0705
0706 checkInvariants();
0707
0708 int u = wordIndex(fromIndex);
0709 if (u >= wordsInUse)
0710 return -1;
0711
0712 long word = words[u] & (WORD_MASK << fromIndex);
0713
0714 while (true) {
0715 if (word != 0)
0716 return (u * BITS_PER_WORD)
0717 + Long.numberOfTrailingZeros(word);
0718 if (++u == wordsInUse)
0719 return -1;
0720 word = words[u];
0721 }
0722 }
0723
0724 /**
0725 * Returns the index of the first bit that is set to {@code false}
0726 * that occurs on or after the specified starting index.
0727 *
0728 * @param fromIndex the index to start checking from (inclusive)
0729 * @return the index of the next clear bit
0730 * @throws IndexOutOfBoundsException if the specified index is negative
0731 * @since 1.4
0732 */
0733 public int nextClearBit(int fromIndex) {
0734 // Neither spec nor implementation handle bitsets of maximal length.
0735 // See 4816253.
0736 if (fromIndex < 0)
0737 throw new IndexOutOfBoundsException("fromIndex < 0: "
0738 + fromIndex);
0739
0740 checkInvariants();
0741
0742 int u = wordIndex(fromIndex);
0743 if (u >= wordsInUse)
0744 return fromIndex;
0745
0746 long word = ~words[u] & (WORD_MASK << fromIndex);
0747
0748 while (true) {
0749 if (word != 0)
0750 return (u * BITS_PER_WORD)
0751 + Long.numberOfTrailingZeros(word);
0752 if (++u == wordsInUse)
0753 return wordsInUse * BITS_PER_WORD;
0754 word = ~words[u];
0755 }
0756 }
0757
0758 /**
0759 * Returns the "logical size" of this {@code BitSet}: the index of
0760 * the highest set bit in the {@code BitSet} plus one. Returns zero
0761 * if the {@code BitSet} contains no set bits.
0762 *
0763 * @return the logical size of this {@code BitSet}
0764 * @since 1.2
0765 */
0766 public int length() {
0767 if (wordsInUse == 0)
0768 return 0;
0769
0770 return BITS_PER_WORD
0771 * (wordsInUse - 1)
0772 + (BITS_PER_WORD - Long
0773 .numberOfLeadingZeros(words[wordsInUse - 1]));
0774 }
0775
0776 /**
0777 * Returns true if this {@code BitSet} contains no bits that are set
0778 * to {@code true}.
0779 *
0780 * @return boolean indicating whether this {@code BitSet} is empty
0781 * @since 1.4
0782 */
0783 public boolean isEmpty() {
0784 return wordsInUse == 0;
0785 }
0786
0787 /**
0788 * Returns true if the specified {@code BitSet} has any bits set to
0789 * {@code true} that are also set to {@code true} in this {@code BitSet}.
0790 *
0791 * @param set {@code BitSet} to intersect with
0792 * @return boolean indicating whether this {@code BitSet} intersects
0793 * the specified {@code BitSet}
0794 * @since 1.4
0795 */
0796 public boolean intersects(BitSet set) {
0797 for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
0798 if ((words[i] & set.words[i]) != 0)
0799 return true;
0800 return false;
0801 }
0802
0803 /**
0804 * Returns the number of bits set to {@code true} in this {@code BitSet}.
0805 *
0806 * @return the number of bits set to {@code true} in this {@code BitSet}
0807 * @since 1.4
0808 */
0809 public int cardinality() {
0810 int sum = 0;
0811 for (int i = 0; i < wordsInUse; i++)
0812 sum += Long.bitCount(words[i]);
0813 return sum;
0814 }
0815
0816 /**
0817 * Performs a logical <b>AND</b> of this target bit set with the
0818 * argument bit set. This bit set is modified so that each bit in it
0819 * has the value {@code true} if and only if it both initially
0820 * had the value {@code true} and the corresponding bit in the
0821 * bit set argument also had the value {@code true}.
0822 *
0823 * @param set a bit set
0824 */
0825 public void and(BitSet set) {
0826 if (this == set)
0827 return;
0828
0829 while (wordsInUse > set.wordsInUse)
0830 words[--wordsInUse] = 0;
0831
0832 // Perform logical AND on words in common
0833 for (int i = 0; i < wordsInUse; i++)
0834 words[i] &= set.words[i];
0835
0836 recalculateWordsInUse();
0837 checkInvariants();
0838 }
0839
0840 /**
0841 * Performs a logical <b>OR</b> of this bit set with the bit set
0842 * argument. This bit set is modified so that a bit in it has the
0843 * value {@code true} if and only if it either already had the
0844 * value {@code true} or the corresponding bit in the bit set
0845 * argument has the value {@code true}.
0846 *
0847 * @param set a bit set
0848 */
0849 public void or(BitSet set) {
0850 if (this == set)
0851 return;
0852
0853 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
0854
0855 if (wordsInUse < set.wordsInUse) {
0856 ensureCapacity(set.wordsInUse);
0857 wordsInUse = set.wordsInUse;
0858 }
0859
0860 // Perform logical OR on words in common
0861 for (int i = 0; i < wordsInCommon; i++)
0862 words[i] |= set.words[i];
0863
0864 // Copy any remaining words
0865 if (wordsInCommon < set.wordsInUse)
0866 System.arraycopy(set.words, wordsInCommon, words,
0867 wordsInCommon, wordsInUse - wordsInCommon);
0868
0869 // recalculateWordsInUse() is unnecessary
0870 checkInvariants();
0871 }
0872
0873 /**
0874 * Performs a logical <b>XOR</b> of this bit set with the bit set
0875 * argument. This bit set is modified so that a bit in it has the
0876 * value {@code true} if and only if one of the following
0877 * statements holds:
0878 * <ul>
0879 * <li>The bit initially has the value {@code true}, and the
0880 * corresponding bit in the argument has the value {@code false}.
0881 * <li>The bit initially has the value {@code false}, and the
0882 * corresponding bit in the argument has the value {@code true}.
0883 * </ul>
0884 *
0885 * @param set a bit set
0886 */
0887 public void xor(BitSet set) {
0888 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
0889
0890 if (wordsInUse < set.wordsInUse) {
0891 ensureCapacity(set.wordsInUse);
0892 wordsInUse = set.wordsInUse;
0893 }
0894
0895 // Perform logical XOR on words in common
0896 for (int i = 0; i < wordsInCommon; i++)
0897 words[i] ^= set.words[i];
0898
0899 // Copy any remaining words
0900 if (wordsInCommon < set.wordsInUse)
0901 System.arraycopy(set.words, wordsInCommon, words,
0902 wordsInCommon, set.wordsInUse - wordsInCommon);
0903
0904 recalculateWordsInUse();
0905 checkInvariants();
0906 }
0907
0908 /**
0909 * Clears all of the bits in this {@code BitSet} whose corresponding
0910 * bit is set in the specified {@code BitSet}.
0911 *
0912 * @param set the {@code BitSet} with which to mask this
0913 * {@code BitSet}
0914 * @since 1.2
0915 */
0916 public void andNot(BitSet set) {
0917 // Perform logical (a & !b) on words in common
0918 for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
0919 words[i] &= ~set.words[i];
0920
0921 recalculateWordsInUse();
0922 checkInvariants();
0923 }
0924
0925 /**
0926 * Returns a hash code value for this bit set. The hash code
0927 * depends only on which bits have been set within this
0928 * {@code BitSet}. The algorithm used to compute it may
0929 * be described as follows.
0930 *
0931 * <p>Suppose the bits in the {@code BitSet} were to be stored
0932 * in an array of {@code long} integers called, say,
0933 * {@code words}, in such a manner that bit {@code k} is
0934 * set in the {@code BitSet} (for nonnegative values of
0935 * {@code k}) if and only if the expression
0936 * <pre>{@code ((k>>6) < words.length) && ((words[k>>6] & (1L << (bit & 0x3F))) != 0)}</pre>
0937 * is true. Then the following definition of the {@code hashCode}
0938 * method would be a correct implementation of the actual algorithm:
0939 * <pre> {@code
0940 * public int hashCode() {
0941 * long h = 1234;
0942 * for (int i = words.length; --i >= 0; ) {
0943 * h ^= words[i] * (i + 1);
0944 * }
0945 * return (int)((h >> 32) ^ h);
0946 * }}</pre>
0947 * Note that the hash code values change if the set of bits is altered.
0948 *
0949 * @return a hash code value for this bit set
0950 */
0951 public int hashCode() {
0952 long h = 1234;
0953 for (int i = wordsInUse; --i >= 0;)
0954 h ^= words[i] * (i + 1);
0955
0956 return (int) ((h >> 32) ^ h);
0957 }
0958
0959 /**
0960 * Returns the number of bits of space actually in use by this
0961 * {@code BitSet} to represent bit values.
0962 * The maximum element in the set is the size - 1st element.
0963 *
0964 * @return the number of bits currently in this bit set
0965 */
0966 public int size() {
0967 return words.length * BITS_PER_WORD;
0968 }
0969
0970 /**
0971 * Compares this object against the specified object.
0972 * The result is {@code true} if and only if the argument is
0973 * not {@code null} and is a {@code Bitset} object that has
0974 * exactly the same set of bits set to {@code true} as this bit
0975 * set. That is, for every nonnegative {@code int} index {@code k},
0976 * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
0977 * must be true. The current sizes of the two bit sets are not compared.
0978 *
0979 * @param obj the object to compare with
0980 * @return {@code true} if the objects are the same;
0981 * {@code false} otherwise
0982 * @see #size()
0983 */
0984 public boolean equals(Object obj) {
0985 if (!(obj instanceof BitSet))
0986 return false;
0987 if (this == obj)
0988 return true;
0989
0990 BitSet set = (BitSet) obj;
0991
0992 checkInvariants();
0993 set.checkInvariants();
0994
0995 if (wordsInUse != set.wordsInUse)
0996 return false;
0997
0998 // Check words in use by both BitSets
0999 for (int i = 0; i < wordsInUse; i++)
1000 if (words[i] != set.words[i])
1001 return false;
1002
1003 return true;
1004 }
1005
1006 /**
1007 * Cloning this {@code BitSet} produces a new {@code BitSet}
1008 * that is equal to it.
1009 * The clone of the bit set is another bit set that has exactly the
1010 * same bits set to {@code true} as this bit set.
1011 *
1012 * @return a clone of this bit set
1013 * @see #size()
1014 */
1015 public Object clone() {
1016 if (!sizeIsSticky)
1017 trimToSize();
1018
1019 try {
1020 BitSet result = (BitSet) super .clone();
1021 result.words = words.clone();
1022 result.checkInvariants();
1023 return result;
1024 } catch (CloneNotSupportedException e) {
1025 throw new InternalError();
1026 }
1027 }
1028
1029 /**
1030 * Attempts to reduce internal storage used for the bits in this bit set.
1031 * Calling this method may, but is not required to, affect the value
1032 * returned by a subsequent call to the {@link #size()} method.
1033 */
1034 private void trimToSize() {
1035 if (wordsInUse != words.length) {
1036 words = Arrays.copyOf(words, wordsInUse);
1037 checkInvariants();
1038 }
1039 }
1040
1041 /**
1042 * Save the state of the {@code BitSet} instance to a stream (i.e.,
1043 * serialize it).
1044 */
1045 private void writeObject(ObjectOutputStream s) throws IOException {
1046
1047 checkInvariants();
1048
1049 if (!sizeIsSticky)
1050 trimToSize();
1051
1052 ObjectOutputStream.PutField fields = s.putFields();
1053 fields.put("bits", words);
1054 s.writeFields();
1055 }
1056
1057 /**
1058 * Reconstitute the {@code BitSet} instance from a stream (i.e.,
1059 * deserialize it).
1060 */
1061 private void readObject(ObjectInputStream s) throws IOException,
1062 ClassNotFoundException {
1063
1064 ObjectInputStream.GetField fields = s.readFields();
1065 words = (long[]) fields.get("bits", null);
1066
1067 // Assume maximum length then find real length
1068 // because recalculateWordsInUse assumes maintenance
1069 // or reduction in logical size
1070 wordsInUse = words.length;
1071 recalculateWordsInUse();
1072 sizeIsSticky = (words.length > 0 && words[words.length - 1] == 0L); // heuristic
1073 checkInvariants();
1074 }
1075
1076 /**
1077 * Returns a string representation of this bit set. For every index
1078 * for which this {@code BitSet} contains a bit in the set
1079 * state, the decimal representation of that index is included in
1080 * the result. Such indices are listed in order from lowest to
1081 * highest, separated by ", " (a comma and a space) and
1082 * surrounded by braces, resulting in the usual mathematical
1083 * notation for a set of integers.
1084 *
1085 * <p>Example:
1086 * <pre>
1087 * BitSet drPepper = new BitSet();</pre>
1088 * Now {@code drPepper.toString()} returns "{@code {}}".<p>
1089 * <pre>
1090 * drPepper.set(2);</pre>
1091 * Now {@code drPepper.toString()} returns "{@code {2}}".<p>
1092 * <pre>
1093 * drPepper.set(4);
1094 * drPepper.set(10);</pre>
1095 * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
1096 *
1097 * @return a string representation of this bit set
1098 */
1099 public String toString() {
1100 checkInvariants();
1101
1102 int numBits = (wordsInUse > 128) ? cardinality() : wordsInUse
1103 * BITS_PER_WORD;
1104 StringBuilder b = new StringBuilder(6 * numBits + 2);
1105 b.append('{');
1106
1107 int i = nextSetBit(0);
1108 if (i != -1) {
1109 b.append(i);
1110 for (i = nextSetBit(i + 1); i >= 0; i = nextSetBit(i + 1)) {
1111 int endOfRun = nextClearBit(i);
1112 do {
1113 b.append(", ").append(i);
1114 } while (++i < endOfRun);
1115 }
1116 }
1117
1118 b.append('}');
1119 return b.toString();
1120 }
1121 }
|