1.1 --- a/emul/compact/src/main/java/java/util/BitSet.java Thu Oct 31 11:30:50 2013 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1191 +0,0 @@
1.4 -/*
1.5 - * Copyright (c) 1995, 2007, Oracle and/or its affiliates. All rights reserved.
1.6 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 - *
1.8 - * This code is free software; you can redistribute it and/or modify it
1.9 - * under the terms of the GNU General Public License version 2 only, as
1.10 - * published by the Free Software Foundation. Oracle designates this
1.11 - * particular file as subject to the "Classpath" exception as provided
1.12 - * by Oracle in the LICENSE file that accompanied this code.
1.13 - *
1.14 - * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 - * version 2 for more details (a copy is included in the LICENSE file that
1.18 - * accompanied this code).
1.19 - *
1.20 - * You should have received a copy of the GNU General Public License version
1.21 - * 2 along with this work; if not, write to the Free Software Foundation,
1.22 - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 - *
1.24 - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 - * or visit www.oracle.com if you need additional information or have any
1.26 - * questions.
1.27 - */
1.28 -
1.29 -package java.util;
1.30 -
1.31 -import java.io.*;
1.32 -import java.nio.ByteBuffer;
1.33 -import java.nio.ByteOrder;
1.34 -import java.nio.LongBuffer;
1.35 -
1.36 -/**
1.37 - * This class implements a vector of bits that grows as needed. Each
1.38 - * component of the bit set has a {@code boolean} value. The
1.39 - * bits of a {@code BitSet} are indexed by nonnegative integers.
1.40 - * Individual indexed bits can be examined, set, or cleared. One
1.41 - * {@code BitSet} may be used to modify the contents of another
1.42 - * {@code BitSet} through logical AND, logical inclusive OR, and
1.43 - * logical exclusive OR operations.
1.44 - *
1.45 - * <p>By default, all bits in the set initially have the value
1.46 - * {@code false}.
1.47 - *
1.48 - * <p>Every bit set has a current size, which is the number of bits
1.49 - * of space currently in use by the bit set. Note that the size is
1.50 - * related to the implementation of a bit set, so it may change with
1.51 - * implementation. The length of a bit set relates to logical length
1.52 - * of a bit set and is defined independently of implementation.
1.53 - *
1.54 - * <p>Unless otherwise noted, passing a null parameter to any of the
1.55 - * methods in a {@code BitSet} will result in a
1.56 - * {@code NullPointerException}.
1.57 - *
1.58 - * <p>A {@code BitSet} is not safe for multithreaded use without
1.59 - * external synchronization.
1.60 - *
1.61 - * @author Arthur van Hoff
1.62 - * @author Michael McCloskey
1.63 - * @author Martin Buchholz
1.64 - * @since JDK1.0
1.65 - */
1.66 -public class BitSet implements Cloneable, java.io.Serializable {
1.67 - /*
1.68 - * BitSets are packed into arrays of "words." Currently a word is
1.69 - * a long, which consists of 64 bits, requiring 6 address bits.
1.70 - * The choice of word size is determined purely by performance concerns.
1.71 - */
1.72 - private final static int ADDRESS_BITS_PER_WORD = 6;
1.73 - private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
1.74 - private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
1.75 -
1.76 - /* Used to shift left or right for a partial word mask */
1.77 - private static final long WORD_MASK = 0xffffffffffffffffL;
1.78 -
1.79 - /**
1.80 - * @serialField bits long[]
1.81 - *
1.82 - * The bits in this BitSet. The ith bit is stored in bits[i/64] at
1.83 - * bit position i % 64 (where bit position 0 refers to the least
1.84 - * significant bit and 63 refers to the most significant bit).
1.85 - */
1.86 - private static final ObjectStreamField[] serialPersistentFields = {
1.87 - new ObjectStreamField("bits", long[].class),
1.88 - };
1.89 -
1.90 - /**
1.91 - * The internal field corresponding to the serialField "bits".
1.92 - */
1.93 - private long[] words;
1.94 -
1.95 - /**
1.96 - * The number of words in the logical size of this BitSet.
1.97 - */
1.98 - private transient int wordsInUse = 0;
1.99 -
1.100 - /**
1.101 - * Whether the size of "words" is user-specified. If so, we assume
1.102 - * the user knows what he's doing and try harder to preserve it.
1.103 - */
1.104 - private transient boolean sizeIsSticky = false;
1.105 -
1.106 - /* use serialVersionUID from JDK 1.0.2 for interoperability */
1.107 - private static final long serialVersionUID = 7997698588986878753L;
1.108 -
1.109 - /**
1.110 - * Given a bit index, return word index containing it.
1.111 - */
1.112 - private static int wordIndex(int bitIndex) {
1.113 - return bitIndex >> ADDRESS_BITS_PER_WORD;
1.114 - }
1.115 -
1.116 - /**
1.117 - * Every public method must preserve these invariants.
1.118 - */
1.119 - private void checkInvariants() {
1.120 - assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
1.121 - assert(wordsInUse >= 0 && wordsInUse <= words.length);
1.122 - assert(wordsInUse == words.length || words[wordsInUse] == 0);
1.123 - }
1.124 -
1.125 - /**
1.126 - * Sets the field wordsInUse to the logical size in words of the bit set.
1.127 - * WARNING:This method assumes that the number of words actually in use is
1.128 - * less than or equal to the current value of wordsInUse!
1.129 - */
1.130 - private void recalculateWordsInUse() {
1.131 - // Traverse the bitset until a used word is found
1.132 - int i;
1.133 - for (i = wordsInUse-1; i >= 0; i--)
1.134 - if (words[i] != 0)
1.135 - break;
1.136 -
1.137 - wordsInUse = i+1; // The new logical size
1.138 - }
1.139 -
1.140 - /**
1.141 - * Creates a new bit set. All bits are initially {@code false}.
1.142 - */
1.143 - public BitSet() {
1.144 - initWords(BITS_PER_WORD);
1.145 - sizeIsSticky = false;
1.146 - }
1.147 -
1.148 - /**
1.149 - * Creates a bit set whose initial size is large enough to explicitly
1.150 - * represent bits with indices in the range {@code 0} through
1.151 - * {@code nbits-1}. All bits are initially {@code false}.
1.152 - *
1.153 - * @param nbits the initial size of the bit set
1.154 - * @throws NegativeArraySizeException if the specified initial size
1.155 - * is negative
1.156 - */
1.157 - public BitSet(int nbits) {
1.158 - // nbits can't be negative; size 0 is OK
1.159 - if (nbits < 0)
1.160 - throw new NegativeArraySizeException("nbits < 0: " + nbits);
1.161 -
1.162 - initWords(nbits);
1.163 - sizeIsSticky = true;
1.164 - }
1.165 -
1.166 - private void initWords(int nbits) {
1.167 - words = new long[wordIndex(nbits-1) + 1];
1.168 - }
1.169 -
1.170 - /**
1.171 - * Creates a bit set using words as the internal representation.
1.172 - * The last word (if there is one) must be non-zero.
1.173 - */
1.174 - private BitSet(long[] words) {
1.175 - this.words = words;
1.176 - this.wordsInUse = words.length;
1.177 - checkInvariants();
1.178 - }
1.179 -
1.180 - /**
1.181 - * Returns a new bit set containing all the bits in the given long array.
1.182 - *
1.183 - * <p>More precisely,
1.184 - * <br>{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
1.185 - * <br>for all {@code n < 64 * longs.length}.
1.186 - *
1.187 - * <p>This method is equivalent to
1.188 - * {@code BitSet.valueOf(LongBuffer.wrap(longs))}.
1.189 - *
1.190 - * @param longs a long array containing a little-endian representation
1.191 - * of a sequence of bits to be used as the initial bits of the
1.192 - * new bit set
1.193 - * @since 1.7
1.194 - */
1.195 - public static BitSet valueOf(long[] longs) {
1.196 - int n;
1.197 - for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)
1.198 - ;
1.199 - return new BitSet(Arrays.copyOf(longs, n));
1.200 - }
1.201 -
1.202 - /**
1.203 - * Returns a new bit set containing all the bits in the given long
1.204 - * buffer between its position and limit.
1.205 - *
1.206 - * <p>More precisely,
1.207 - * <br>{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)}
1.208 - * <br>for all {@code n < 64 * lb.remaining()}.
1.209 - *
1.210 - * <p>The long buffer is not modified by this method, and no
1.211 - * reference to the buffer is retained by the bit set.
1.212 - *
1.213 - * @param lb a long buffer containing a little-endian representation
1.214 - * of a sequence of bits between its position and limit, to be
1.215 - * used as the initial bits of the new bit set
1.216 - * @since 1.7
1.217 - */
1.218 - public static BitSet valueOf(LongBuffer lb) {
1.219 - lb = lb.slice();
1.220 - int n;
1.221 - for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)
1.222 - ;
1.223 - long[] words = new long[n];
1.224 - lb.get(words);
1.225 - return new BitSet(words);
1.226 - }
1.227 -
1.228 - /**
1.229 - * Returns a new bit set containing all the bits in the given byte array.
1.230 - *
1.231 - * <p>More precisely,
1.232 - * <br>{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
1.233 - * <br>for all {@code n < 8 * bytes.length}.
1.234 - *
1.235 - * <p>This method is equivalent to
1.236 - * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}.
1.237 - *
1.238 - * @param bytes a byte array containing a little-endian
1.239 - * representation of a sequence of bits to be used as the
1.240 - * initial bits of the new bit set
1.241 - * @since 1.7
1.242 - */
1.243 - public static BitSet valueOf(byte[] bytes) {
1.244 - return BitSet.valueOf(ByteBuffer.wrap(bytes));
1.245 - }
1.246 -
1.247 - /**
1.248 - * Returns a new bit set containing all the bits in the given byte
1.249 - * buffer between its position and limit.
1.250 - *
1.251 - * <p>More precisely,
1.252 - * <br>{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)}
1.253 - * <br>for all {@code n < 8 * bb.remaining()}.
1.254 - *
1.255 - * <p>The byte buffer is not modified by this method, and no
1.256 - * reference to the buffer is retained by the bit set.
1.257 - *
1.258 - * @param bb a byte buffer containing a little-endian representation
1.259 - * of a sequence of bits between its position and limit, to be
1.260 - * used as the initial bits of the new bit set
1.261 - * @since 1.7
1.262 - */
1.263 - public static BitSet valueOf(ByteBuffer bb) {
1.264 - bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);
1.265 - int n;
1.266 - for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--)
1.267 - ;
1.268 - long[] words = new long[(n + 7) / 8];
1.269 - bb.limit(n);
1.270 - int i = 0;
1.271 - while (bb.remaining() >= 8)
1.272 - words[i++] = bb.getLong();
1.273 - for (int remaining = bb.remaining(), j = 0; j < remaining; j++)
1.274 - words[i] |= (bb.get() & 0xffL) << (8 * j);
1.275 - return new BitSet(words);
1.276 - }
1.277 -
1.278 - /**
1.279 - * Returns a new byte array containing all the bits in this bit set.
1.280 - *
1.281 - * <p>More precisely, if
1.282 - * <br>{@code byte[] bytes = s.toByteArray();}
1.283 - * <br>then {@code bytes.length == (s.length()+7)/8} and
1.284 - * <br>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
1.285 - * <br>for all {@code n < 8 * bytes.length}.
1.286 - *
1.287 - * @return a byte array containing a little-endian representation
1.288 - * of all the bits in this bit set
1.289 - * @since 1.7
1.290 - */
1.291 - public byte[] toByteArray() {
1.292 - int n = wordsInUse;
1.293 - if (n == 0)
1.294 - return new byte[0];
1.295 - int len = 8 * (n-1);
1.296 - for (long x = words[n - 1]; x != 0; x >>>= 8)
1.297 - len++;
1.298 - byte[] bytes = new byte[len];
1.299 - ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);
1.300 - for (int i = 0; i < n - 1; i++)
1.301 - bb.putLong(words[i]);
1.302 - for (long x = words[n - 1]; x != 0; x >>>= 8)
1.303 - bb.put((byte) (x & 0xff));
1.304 - return bytes;
1.305 - }
1.306 -
1.307 - /**
1.308 - * Returns a new long array containing all the bits in this bit set.
1.309 - *
1.310 - * <p>More precisely, if
1.311 - * <br>{@code long[] longs = s.toLongArray();}
1.312 - * <br>then {@code longs.length == (s.length()+63)/64} and
1.313 - * <br>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
1.314 - * <br>for all {@code n < 64 * longs.length}.
1.315 - *
1.316 - * @return a long array containing a little-endian representation
1.317 - * of all the bits in this bit set
1.318 - * @since 1.7
1.319 - */
1.320 - public long[] toLongArray() {
1.321 - return Arrays.copyOf(words, wordsInUse);
1.322 - }
1.323 -
1.324 - /**
1.325 - * Ensures that the BitSet can hold enough words.
1.326 - * @param wordsRequired the minimum acceptable number of words.
1.327 - */
1.328 - private void ensureCapacity(int wordsRequired) {
1.329 - if (words.length < wordsRequired) {
1.330 - // Allocate larger of doubled size or required size
1.331 - int request = Math.max(2 * words.length, wordsRequired);
1.332 - words = Arrays.copyOf(words, request);
1.333 - sizeIsSticky = false;
1.334 - }
1.335 - }
1.336 -
1.337 - /**
1.338 - * Ensures that the BitSet can accommodate a given wordIndex,
1.339 - * temporarily violating the invariants. The caller must
1.340 - * restore the invariants before returning to the user,
1.341 - * possibly using recalculateWordsInUse().
1.342 - * @param wordIndex the index to be accommodated.
1.343 - */
1.344 - private void expandTo(int wordIndex) {
1.345 - int wordsRequired = wordIndex+1;
1.346 - if (wordsInUse < wordsRequired) {
1.347 - ensureCapacity(wordsRequired);
1.348 - wordsInUse = wordsRequired;
1.349 - }
1.350 - }
1.351 -
1.352 - /**
1.353 - * Checks that fromIndex ... toIndex is a valid range of bit indices.
1.354 - */
1.355 - private static void checkRange(int fromIndex, int toIndex) {
1.356 - if (fromIndex < 0)
1.357 - throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
1.358 - if (toIndex < 0)
1.359 - throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
1.360 - if (fromIndex > toIndex)
1.361 - throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
1.362 - " > toIndex: " + toIndex);
1.363 - }
1.364 -
1.365 - /**
1.366 - * Sets the bit at the specified index to the complement of its
1.367 - * current value.
1.368 - *
1.369 - * @param bitIndex the index of the bit to flip
1.370 - * @throws IndexOutOfBoundsException if the specified index is negative
1.371 - * @since 1.4
1.372 - */
1.373 - public void flip(int bitIndex) {
1.374 - if (bitIndex < 0)
1.375 - throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
1.376 -
1.377 - int wordIndex = wordIndex(bitIndex);
1.378 - expandTo(wordIndex);
1.379 -
1.380 - words[wordIndex] ^= (1L << bitIndex);
1.381 -
1.382 - recalculateWordsInUse();
1.383 - checkInvariants();
1.384 - }
1.385 -
1.386 - /**
1.387 - * Sets each bit from the specified {@code fromIndex} (inclusive) to the
1.388 - * specified {@code toIndex} (exclusive) to the complement of its current
1.389 - * value.
1.390 - *
1.391 - * @param fromIndex index of the first bit to flip
1.392 - * @param toIndex index after the last bit to flip
1.393 - * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
1.394 - * or {@code toIndex} is negative, or {@code fromIndex} is
1.395 - * larger than {@code toIndex}
1.396 - * @since 1.4
1.397 - */
1.398 - public void flip(int fromIndex, int toIndex) {
1.399 - checkRange(fromIndex, toIndex);
1.400 -
1.401 - if (fromIndex == toIndex)
1.402 - return;
1.403 -
1.404 - int startWordIndex = wordIndex(fromIndex);
1.405 - int endWordIndex = wordIndex(toIndex - 1);
1.406 - expandTo(endWordIndex);
1.407 -
1.408 - long firstWordMask = WORD_MASK << fromIndex;
1.409 - long lastWordMask = WORD_MASK >>> -toIndex;
1.410 - if (startWordIndex == endWordIndex) {
1.411 - // Case 1: One word
1.412 - words[startWordIndex] ^= (firstWordMask & lastWordMask);
1.413 - } else {
1.414 - // Case 2: Multiple words
1.415 - // Handle first word
1.416 - words[startWordIndex] ^= firstWordMask;
1.417 -
1.418 - // Handle intermediate words, if any
1.419 - for (int i = startWordIndex+1; i < endWordIndex; i++)
1.420 - words[i] ^= WORD_MASK;
1.421 -
1.422 - // Handle last word
1.423 - words[endWordIndex] ^= lastWordMask;
1.424 - }
1.425 -
1.426 - recalculateWordsInUse();
1.427 - checkInvariants();
1.428 - }
1.429 -
1.430 - /**
1.431 - * Sets the bit at the specified index to {@code true}.
1.432 - *
1.433 - * @param bitIndex a bit index
1.434 - * @throws IndexOutOfBoundsException if the specified index is negative
1.435 - * @since JDK1.0
1.436 - */
1.437 - public void set(int bitIndex) {
1.438 - if (bitIndex < 0)
1.439 - throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
1.440 -
1.441 - int wordIndex = wordIndex(bitIndex);
1.442 - expandTo(wordIndex);
1.443 -
1.444 - words[wordIndex] |= (1L << bitIndex); // Restores invariants
1.445 -
1.446 - checkInvariants();
1.447 - }
1.448 -
1.449 - /**
1.450 - * Sets the bit at the specified index to the specified value.
1.451 - *
1.452 - * @param bitIndex a bit index
1.453 - * @param value a boolean value to set
1.454 - * @throws IndexOutOfBoundsException if the specified index is negative
1.455 - * @since 1.4
1.456 - */
1.457 - public void set(int bitIndex, boolean value) {
1.458 - if (value)
1.459 - set(bitIndex);
1.460 - else
1.461 - clear(bitIndex);
1.462 - }
1.463 -
1.464 - /**
1.465 - * Sets the bits from the specified {@code fromIndex} (inclusive) to the
1.466 - * specified {@code toIndex} (exclusive) to {@code true}.
1.467 - *
1.468 - * @param fromIndex index of the first bit to be set
1.469 - * @param toIndex index after the last bit to be set
1.470 - * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
1.471 - * or {@code toIndex} is negative, or {@code fromIndex} is
1.472 - * larger than {@code toIndex}
1.473 - * @since 1.4
1.474 - */
1.475 - public void set(int fromIndex, int toIndex) {
1.476 - checkRange(fromIndex, toIndex);
1.477 -
1.478 - if (fromIndex == toIndex)
1.479 - return;
1.480 -
1.481 - // Increase capacity if necessary
1.482 - int startWordIndex = wordIndex(fromIndex);
1.483 - int endWordIndex = wordIndex(toIndex - 1);
1.484 - expandTo(endWordIndex);
1.485 -
1.486 - long firstWordMask = WORD_MASK << fromIndex;
1.487 - long lastWordMask = WORD_MASK >>> -toIndex;
1.488 - if (startWordIndex == endWordIndex) {
1.489 - // Case 1: One word
1.490 - words[startWordIndex] |= (firstWordMask & lastWordMask);
1.491 - } else {
1.492 - // Case 2: Multiple words
1.493 - // Handle first word
1.494 - words[startWordIndex] |= firstWordMask;
1.495 -
1.496 - // Handle intermediate words, if any
1.497 - for (int i = startWordIndex+1; i < endWordIndex; i++)
1.498 - words[i] = WORD_MASK;
1.499 -
1.500 - // Handle last word (restores invariants)
1.501 - words[endWordIndex] |= lastWordMask;
1.502 - }
1.503 -
1.504 - checkInvariants();
1.505 - }
1.506 -
1.507 - /**
1.508 - * Sets the bits from the specified {@code fromIndex} (inclusive) to the
1.509 - * specified {@code toIndex} (exclusive) to the specified value.
1.510 - *
1.511 - * @param fromIndex index of the first bit to be set
1.512 - * @param toIndex index after the last bit to be set
1.513 - * @param value value to set the selected bits to
1.514 - * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
1.515 - * or {@code toIndex} is negative, or {@code fromIndex} is
1.516 - * larger than {@code toIndex}
1.517 - * @since 1.4
1.518 - */
1.519 - public void set(int fromIndex, int toIndex, boolean value) {
1.520 - if (value)
1.521 - set(fromIndex, toIndex);
1.522 - else
1.523 - clear(fromIndex, toIndex);
1.524 - }
1.525 -
1.526 - /**
1.527 - * Sets the bit specified by the index to {@code false}.
1.528 - *
1.529 - * @param bitIndex the index of the bit to be cleared
1.530 - * @throws IndexOutOfBoundsException if the specified index is negative
1.531 - * @since JDK1.0
1.532 - */
1.533 - public void clear(int bitIndex) {
1.534 - if (bitIndex < 0)
1.535 - throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
1.536 -
1.537 - int wordIndex = wordIndex(bitIndex);
1.538 - if (wordIndex >= wordsInUse)
1.539 - return;
1.540 -
1.541 - words[wordIndex] &= ~(1L << bitIndex);
1.542 -
1.543 - recalculateWordsInUse();
1.544 - checkInvariants();
1.545 - }
1.546 -
1.547 - /**
1.548 - * Sets the bits from the specified {@code fromIndex} (inclusive) to the
1.549 - * specified {@code toIndex} (exclusive) to {@code false}.
1.550 - *
1.551 - * @param fromIndex index of the first bit to be cleared
1.552 - * @param toIndex index after the last bit to be cleared
1.553 - * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
1.554 - * or {@code toIndex} is negative, or {@code fromIndex} is
1.555 - * larger than {@code toIndex}
1.556 - * @since 1.4
1.557 - */
1.558 - public void clear(int fromIndex, int toIndex) {
1.559 - checkRange(fromIndex, toIndex);
1.560 -
1.561 - if (fromIndex == toIndex)
1.562 - return;
1.563 -
1.564 - int startWordIndex = wordIndex(fromIndex);
1.565 - if (startWordIndex >= wordsInUse)
1.566 - return;
1.567 -
1.568 - int endWordIndex = wordIndex(toIndex - 1);
1.569 - if (endWordIndex >= wordsInUse) {
1.570 - toIndex = length();
1.571 - endWordIndex = wordsInUse - 1;
1.572 - }
1.573 -
1.574 - long firstWordMask = WORD_MASK << fromIndex;
1.575 - long lastWordMask = WORD_MASK >>> -toIndex;
1.576 - if (startWordIndex == endWordIndex) {
1.577 - // Case 1: One word
1.578 - words[startWordIndex] &= ~(firstWordMask & lastWordMask);
1.579 - } else {
1.580 - // Case 2: Multiple words
1.581 - // Handle first word
1.582 - words[startWordIndex] &= ~firstWordMask;
1.583 -
1.584 - // Handle intermediate words, if any
1.585 - for (int i = startWordIndex+1; i < endWordIndex; i++)
1.586 - words[i] = 0;
1.587 -
1.588 - // Handle last word
1.589 - words[endWordIndex] &= ~lastWordMask;
1.590 - }
1.591 -
1.592 - recalculateWordsInUse();
1.593 - checkInvariants();
1.594 - }
1.595 -
1.596 - /**
1.597 - * Sets all of the bits in this BitSet to {@code false}.
1.598 - *
1.599 - * @since 1.4
1.600 - */
1.601 - public void clear() {
1.602 - while (wordsInUse > 0)
1.603 - words[--wordsInUse] = 0;
1.604 - }
1.605 -
1.606 - /**
1.607 - * Returns the value of the bit with the specified index. The value
1.608 - * is {@code true} if the bit with the index {@code bitIndex}
1.609 - * is currently set in this {@code BitSet}; otherwise, the result
1.610 - * is {@code false}.
1.611 - *
1.612 - * @param bitIndex the bit index
1.613 - * @return the value of the bit with the specified index
1.614 - * @throws IndexOutOfBoundsException if the specified index is negative
1.615 - */
1.616 - public boolean get(int bitIndex) {
1.617 - if (bitIndex < 0)
1.618 - throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
1.619 -
1.620 - checkInvariants();
1.621 -
1.622 - int wordIndex = wordIndex(bitIndex);
1.623 - return (wordIndex < wordsInUse)
1.624 - && ((words[wordIndex] & (1L << bitIndex)) != 0);
1.625 - }
1.626 -
1.627 - /**
1.628 - * Returns a new {@code BitSet} composed of bits from this {@code BitSet}
1.629 - * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).
1.630 - *
1.631 - * @param fromIndex index of the first bit to include
1.632 - * @param toIndex index after the last bit to include
1.633 - * @return a new {@code BitSet} from a range of this {@code BitSet}
1.634 - * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
1.635 - * or {@code toIndex} is negative, or {@code fromIndex} is
1.636 - * larger than {@code toIndex}
1.637 - * @since 1.4
1.638 - */
1.639 - public BitSet get(int fromIndex, int toIndex) {
1.640 - checkRange(fromIndex, toIndex);
1.641 -
1.642 - checkInvariants();
1.643 -
1.644 - int len = length();
1.645 -
1.646 - // If no set bits in range return empty bitset
1.647 - if (len <= fromIndex || fromIndex == toIndex)
1.648 - return new BitSet(0);
1.649 -
1.650 - // An optimization
1.651 - if (toIndex > len)
1.652 - toIndex = len;
1.653 -
1.654 - BitSet result = new BitSet(toIndex - fromIndex);
1.655 - int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;
1.656 - int sourceIndex = wordIndex(fromIndex);
1.657 - boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);
1.658 -
1.659 - // Process all words but the last word
1.660 - for (int i = 0; i < targetWords - 1; i++, sourceIndex++)
1.661 - result.words[i] = wordAligned ? words[sourceIndex] :
1.662 - (words[sourceIndex] >>> fromIndex) |
1.663 - (words[sourceIndex+1] << -fromIndex);
1.664 -
1.665 - // Process the last word
1.666 - long lastWordMask = WORD_MASK >>> -toIndex;
1.667 - result.words[targetWords - 1] =
1.668 - ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)
1.669 - ? /* straddles source words */
1.670 - ((words[sourceIndex] >>> fromIndex) |
1.671 - (words[sourceIndex+1] & lastWordMask) << -fromIndex)
1.672 - :
1.673 - ((words[sourceIndex] & lastWordMask) >>> fromIndex);
1.674 -
1.675 - // Set wordsInUse correctly
1.676 - result.wordsInUse = targetWords;
1.677 - result.recalculateWordsInUse();
1.678 - result.checkInvariants();
1.679 -
1.680 - return result;
1.681 - }
1.682 -
1.683 - /**
1.684 - * Returns the index of the first bit that is set to {@code true}
1.685 - * that occurs on or after the specified starting index. If no such
1.686 - * bit exists then {@code -1} is returned.
1.687 - *
1.688 - * <p>To iterate over the {@code true} bits in a {@code BitSet},
1.689 - * use the following loop:
1.690 - *
1.691 - * <pre> {@code
1.692 - * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
1.693 - * // operate on index i here
1.694 - * }}</pre>
1.695 - *
1.696 - * @param fromIndex the index to start checking from (inclusive)
1.697 - * @return the index of the next set bit, or {@code -1} if there
1.698 - * is no such bit
1.699 - * @throws IndexOutOfBoundsException if the specified index is negative
1.700 - * @since 1.4
1.701 - */
1.702 - public int nextSetBit(int fromIndex) {
1.703 - if (fromIndex < 0)
1.704 - throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
1.705 -
1.706 - checkInvariants();
1.707 -
1.708 - int u = wordIndex(fromIndex);
1.709 - if (u >= wordsInUse)
1.710 - return -1;
1.711 -
1.712 - long word = words[u] & (WORD_MASK << fromIndex);
1.713 -
1.714 - while (true) {
1.715 - if (word != 0)
1.716 - return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
1.717 - if (++u == wordsInUse)
1.718 - return -1;
1.719 - word = words[u];
1.720 - }
1.721 - }
1.722 -
1.723 - /**
1.724 - * Returns the index of the first bit that is set to {@code false}
1.725 - * that occurs on or after the specified starting index.
1.726 - *
1.727 - * @param fromIndex the index to start checking from (inclusive)
1.728 - * @return the index of the next clear bit
1.729 - * @throws IndexOutOfBoundsException if the specified index is negative
1.730 - * @since 1.4
1.731 - */
1.732 - public int nextClearBit(int fromIndex) {
1.733 - // Neither spec nor implementation handle bitsets of maximal length.
1.734 - // See 4816253.
1.735 - if (fromIndex < 0)
1.736 - throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
1.737 -
1.738 - checkInvariants();
1.739 -
1.740 - int u = wordIndex(fromIndex);
1.741 - if (u >= wordsInUse)
1.742 - return fromIndex;
1.743 -
1.744 - long word = ~words[u] & (WORD_MASK << fromIndex);
1.745 -
1.746 - while (true) {
1.747 - if (word != 0)
1.748 - return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
1.749 - if (++u == wordsInUse)
1.750 - return wordsInUse * BITS_PER_WORD;
1.751 - word = ~words[u];
1.752 - }
1.753 - }
1.754 -
1.755 - /**
1.756 - * Returns the index of the nearest bit that is set to {@code true}
1.757 - * that occurs on or before the specified starting index.
1.758 - * If no such bit exists, or if {@code -1} is given as the
1.759 - * starting index, then {@code -1} is returned.
1.760 - *
1.761 - * <p>To iterate over the {@code true} bits in a {@code BitSet},
1.762 - * use the following loop:
1.763 - *
1.764 - * <pre> {@code
1.765 - * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
1.766 - * // operate on index i here
1.767 - * }}</pre>
1.768 - *
1.769 - * @param fromIndex the index to start checking from (inclusive)
1.770 - * @return the index of the previous set bit, or {@code -1} if there
1.771 - * is no such bit
1.772 - * @throws IndexOutOfBoundsException if the specified index is less
1.773 - * than {@code -1}
1.774 - * @since 1.7
1.775 - */
1.776 - public int previousSetBit(int fromIndex) {
1.777 - if (fromIndex < 0) {
1.778 - if (fromIndex == -1)
1.779 - return -1;
1.780 - throw new IndexOutOfBoundsException(
1.781 - "fromIndex < -1: " + fromIndex);
1.782 - }
1.783 -
1.784 - checkInvariants();
1.785 -
1.786 - int u = wordIndex(fromIndex);
1.787 - if (u >= wordsInUse)
1.788 - return length() - 1;
1.789 -
1.790 - long word = words[u] & (WORD_MASK >>> -(fromIndex+1));
1.791 -
1.792 - while (true) {
1.793 - if (word != 0)
1.794 - return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
1.795 - if (u-- == 0)
1.796 - return -1;
1.797 - word = words[u];
1.798 - }
1.799 - }
1.800 -
1.801 - /**
1.802 - * Returns the index of the nearest bit that is set to {@code false}
1.803 - * that occurs on or before the specified starting index.
1.804 - * If no such bit exists, or if {@code -1} is given as the
1.805 - * starting index, then {@code -1} is returned.
1.806 - *
1.807 - * @param fromIndex the index to start checking from (inclusive)
1.808 - * @return the index of the previous clear bit, or {@code -1} if there
1.809 - * is no such bit
1.810 - * @throws IndexOutOfBoundsException if the specified index is less
1.811 - * than {@code -1}
1.812 - * @since 1.7
1.813 - */
1.814 - public int previousClearBit(int fromIndex) {
1.815 - if (fromIndex < 0) {
1.816 - if (fromIndex == -1)
1.817 - return -1;
1.818 - throw new IndexOutOfBoundsException(
1.819 - "fromIndex < -1: " + fromIndex);
1.820 - }
1.821 -
1.822 - checkInvariants();
1.823 -
1.824 - int u = wordIndex(fromIndex);
1.825 - if (u >= wordsInUse)
1.826 - return fromIndex;
1.827 -
1.828 - long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1));
1.829 -
1.830 - while (true) {
1.831 - if (word != 0)
1.832 - return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);
1.833 - if (u-- == 0)
1.834 - return -1;
1.835 - word = ~words[u];
1.836 - }
1.837 - }
1.838 -
1.839 - /**
1.840 - * Returns the "logical size" of this {@code BitSet}: the index of
1.841 - * the highest set bit in the {@code BitSet} plus one. Returns zero
1.842 - * if the {@code BitSet} contains no set bits.
1.843 - *
1.844 - * @return the logical size of this {@code BitSet}
1.845 - * @since 1.2
1.846 - */
1.847 - public int length() {
1.848 - if (wordsInUse == 0)
1.849 - return 0;
1.850 -
1.851 - return BITS_PER_WORD * (wordsInUse - 1) +
1.852 - (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
1.853 - }
1.854 -
1.855 - /**
1.856 - * Returns true if this {@code BitSet} contains no bits that are set
1.857 - * to {@code true}.
1.858 - *
1.859 - * @return boolean indicating whether this {@code BitSet} is empty
1.860 - * @since 1.4
1.861 - */
1.862 - public boolean isEmpty() {
1.863 - return wordsInUse == 0;
1.864 - }
1.865 -
1.866 - /**
1.867 - * Returns true if the specified {@code BitSet} has any bits set to
1.868 - * {@code true} that are also set to {@code true} in this {@code BitSet}.
1.869 - *
1.870 - * @param set {@code BitSet} to intersect with
1.871 - * @return boolean indicating whether this {@code BitSet} intersects
1.872 - * the specified {@code BitSet}
1.873 - * @since 1.4
1.874 - */
1.875 - public boolean intersects(BitSet set) {
1.876 - for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
1.877 - if ((words[i] & set.words[i]) != 0)
1.878 - return true;
1.879 - return false;
1.880 - }
1.881 -
1.882 - /**
1.883 - * Returns the number of bits set to {@code true} in this {@code BitSet}.
1.884 - *
1.885 - * @return the number of bits set to {@code true} in this {@code BitSet}
1.886 - * @since 1.4
1.887 - */
1.888 - public int cardinality() {
1.889 - int sum = 0;
1.890 - for (int i = 0; i < wordsInUse; i++)
1.891 - sum += Long.bitCount(words[i]);
1.892 - return sum;
1.893 - }
1.894 -
1.895 - /**
1.896 - * Performs a logical <b>AND</b> of this target bit set with the
1.897 - * argument bit set. This bit set is modified so that each bit in it
1.898 - * has the value {@code true} if and only if it both initially
1.899 - * had the value {@code true} and the corresponding bit in the
1.900 - * bit set argument also had the value {@code true}.
1.901 - *
1.902 - * @param set a bit set
1.903 - */
1.904 - public void and(BitSet set) {
1.905 - if (this == set)
1.906 - return;
1.907 -
1.908 - while (wordsInUse > set.wordsInUse)
1.909 - words[--wordsInUse] = 0;
1.910 -
1.911 - // Perform logical AND on words in common
1.912 - for (int i = 0; i < wordsInUse; i++)
1.913 - words[i] &= set.words[i];
1.914 -
1.915 - recalculateWordsInUse();
1.916 - checkInvariants();
1.917 - }
1.918 -
1.919 - /**
1.920 - * Performs a logical <b>OR</b> of this bit set with the bit set
1.921 - * argument. This bit set is modified so that a bit in it has the
1.922 - * value {@code true} if and only if it either already had the
1.923 - * value {@code true} or the corresponding bit in the bit set
1.924 - * argument has the value {@code true}.
1.925 - *
1.926 - * @param set a bit set
1.927 - */
1.928 - public void or(BitSet set) {
1.929 - if (this == set)
1.930 - return;
1.931 -
1.932 - int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
1.933 -
1.934 - if (wordsInUse < set.wordsInUse) {
1.935 - ensureCapacity(set.wordsInUse);
1.936 - wordsInUse = set.wordsInUse;
1.937 - }
1.938 -
1.939 - // Perform logical OR on words in common
1.940 - for (int i = 0; i < wordsInCommon; i++)
1.941 - words[i] |= set.words[i];
1.942 -
1.943 - // Copy any remaining words
1.944 - if (wordsInCommon < set.wordsInUse)
1.945 - System.arraycopy(set.words, wordsInCommon,
1.946 - words, wordsInCommon,
1.947 - wordsInUse - wordsInCommon);
1.948 -
1.949 - // recalculateWordsInUse() is unnecessary
1.950 - checkInvariants();
1.951 - }
1.952 -
1.953 - /**
1.954 - * Performs a logical <b>XOR</b> of this bit set with the bit set
1.955 - * argument. This bit set is modified so that a bit in it has the
1.956 - * value {@code true} if and only if one of the following
1.957 - * statements holds:
1.958 - * <ul>
1.959 - * <li>The bit initially has the value {@code true}, and the
1.960 - * corresponding bit in the argument has the value {@code false}.
1.961 - * <li>The bit initially has the value {@code false}, and the
1.962 - * corresponding bit in the argument has the value {@code true}.
1.963 - * </ul>
1.964 - *
1.965 - * @param set a bit set
1.966 - */
1.967 - public void xor(BitSet set) {
1.968 - int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
1.969 -
1.970 - if (wordsInUse < set.wordsInUse) {
1.971 - ensureCapacity(set.wordsInUse);
1.972 - wordsInUse = set.wordsInUse;
1.973 - }
1.974 -
1.975 - // Perform logical XOR on words in common
1.976 - for (int i = 0; i < wordsInCommon; i++)
1.977 - words[i] ^= set.words[i];
1.978 -
1.979 - // Copy any remaining words
1.980 - if (wordsInCommon < set.wordsInUse)
1.981 - System.arraycopy(set.words, wordsInCommon,
1.982 - words, wordsInCommon,
1.983 - set.wordsInUse - wordsInCommon);
1.984 -
1.985 - recalculateWordsInUse();
1.986 - checkInvariants();
1.987 - }
1.988 -
1.989 - /**
1.990 - * Clears all of the bits in this {@code BitSet} whose corresponding
1.991 - * bit is set in the specified {@code BitSet}.
1.992 - *
1.993 - * @param set the {@code BitSet} with which to mask this
1.994 - * {@code BitSet}
1.995 - * @since 1.2
1.996 - */
1.997 - public void andNot(BitSet set) {
1.998 - // Perform logical (a & !b) on words in common
1.999 - for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
1.1000 - words[i] &= ~set.words[i];
1.1001 -
1.1002 - recalculateWordsInUse();
1.1003 - checkInvariants();
1.1004 - }
1.1005 -
1.1006 - /**
1.1007 - * Returns the hash code value for this bit set. The hash code depends
1.1008 - * only on which bits are set within this {@code BitSet}.
1.1009 - *
1.1010 - * <p>The hash code is defined to be the result of the following
1.1011 - * calculation:
1.1012 - * <pre> {@code
1.1013 - * public int hashCode() {
1.1014 - * long h = 1234;
1.1015 - * long[] words = toLongArray();
1.1016 - * for (int i = words.length; --i >= 0; )
1.1017 - * h ^= words[i] * (i + 1);
1.1018 - * return (int)((h >> 32) ^ h);
1.1019 - * }}</pre>
1.1020 - * Note that the hash code changes if the set of bits is altered.
1.1021 - *
1.1022 - * @return the hash code value for this bit set
1.1023 - */
1.1024 - public int hashCode() {
1.1025 - long h = 1234;
1.1026 - for (int i = wordsInUse; --i >= 0; )
1.1027 - h ^= words[i] * (i + 1);
1.1028 -
1.1029 - return (int)((h >> 32) ^ h);
1.1030 - }
1.1031 -
1.1032 - /**
1.1033 - * Returns the number of bits of space actually in use by this
1.1034 - * {@code BitSet} to represent bit values.
1.1035 - * The maximum element in the set is the size - 1st element.
1.1036 - *
1.1037 - * @return the number of bits currently in this bit set
1.1038 - */
1.1039 - public int size() {
1.1040 - return words.length * BITS_PER_WORD;
1.1041 - }
1.1042 -
1.1043 - /**
1.1044 - * Compares this object against the specified object.
1.1045 - * The result is {@code true} if and only if the argument is
1.1046 - * not {@code null} and is a {@code Bitset} object that has
1.1047 - * exactly the same set of bits set to {@code true} as this bit
1.1048 - * set. That is, for every nonnegative {@code int} index {@code k},
1.1049 - * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
1.1050 - * must be true. The current sizes of the two bit sets are not compared.
1.1051 - *
1.1052 - * @param obj the object to compare with
1.1053 - * @return {@code true} if the objects are the same;
1.1054 - * {@code false} otherwise
1.1055 - * @see #size()
1.1056 - */
1.1057 - public boolean equals(Object obj) {
1.1058 - if (!(obj instanceof BitSet))
1.1059 - return false;
1.1060 - if (this == obj)
1.1061 - return true;
1.1062 -
1.1063 - BitSet set = (BitSet) obj;
1.1064 -
1.1065 - checkInvariants();
1.1066 - set.checkInvariants();
1.1067 -
1.1068 - if (wordsInUse != set.wordsInUse)
1.1069 - return false;
1.1070 -
1.1071 - // Check words in use by both BitSets
1.1072 - for (int i = 0; i < wordsInUse; i++)
1.1073 - if (words[i] != set.words[i])
1.1074 - return false;
1.1075 -
1.1076 - return true;
1.1077 - }
1.1078 -
1.1079 - /**
1.1080 - * Cloning this {@code BitSet} produces a new {@code BitSet}
1.1081 - * that is equal to it.
1.1082 - * The clone of the bit set is another bit set that has exactly the
1.1083 - * same bits set to {@code true} as this bit set.
1.1084 - *
1.1085 - * @return a clone of this bit set
1.1086 - * @see #size()
1.1087 - */
1.1088 - public Object clone() {
1.1089 - if (! sizeIsSticky)
1.1090 - trimToSize();
1.1091 -
1.1092 - try {
1.1093 - BitSet result = (BitSet) super.clone();
1.1094 - result.words = words.clone();
1.1095 - result.checkInvariants();
1.1096 - return result;
1.1097 - } catch (CloneNotSupportedException e) {
1.1098 - throw new InternalError();
1.1099 - }
1.1100 - }
1.1101 -
1.1102 - /**
1.1103 - * Attempts to reduce internal storage used for the bits in this bit set.
1.1104 - * Calling this method may, but is not required to, affect the value
1.1105 - * returned by a subsequent call to the {@link #size()} method.
1.1106 - */
1.1107 - private void trimToSize() {
1.1108 - if (wordsInUse != words.length) {
1.1109 - words = Arrays.copyOf(words, wordsInUse);
1.1110 - checkInvariants();
1.1111 - }
1.1112 - }
1.1113 -
1.1114 - /**
1.1115 - * Save the state of the {@code BitSet} instance to a stream (i.e.,
1.1116 - * serialize it).
1.1117 - */
1.1118 - private void writeObject(ObjectOutputStream s)
1.1119 - throws IOException {
1.1120 -
1.1121 - checkInvariants();
1.1122 -
1.1123 - if (! sizeIsSticky)
1.1124 - trimToSize();
1.1125 -
1.1126 - ObjectOutputStream.PutField fields = s.putFields();
1.1127 - fields.put("bits", words);
1.1128 - s.writeFields();
1.1129 - }
1.1130 -
1.1131 - /**
1.1132 - * Reconstitute the {@code BitSet} instance from a stream (i.e.,
1.1133 - * deserialize it).
1.1134 - */
1.1135 - private void readObject(ObjectInputStream s)
1.1136 - throws IOException, ClassNotFoundException {
1.1137 -
1.1138 - ObjectInputStream.GetField fields = s.readFields();
1.1139 - words = (long[]) fields.get("bits", null);
1.1140 -
1.1141 - // Assume maximum length then find real length
1.1142 - // because recalculateWordsInUse assumes maintenance
1.1143 - // or reduction in logical size
1.1144 - wordsInUse = words.length;
1.1145 - recalculateWordsInUse();
1.1146 - sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic
1.1147 - checkInvariants();
1.1148 - }
1.1149 -
1.1150 - /**
1.1151 - * Returns a string representation of this bit set. For every index
1.1152 - * for which this {@code BitSet} contains a bit in the set
1.1153 - * state, the decimal representation of that index is included in
1.1154 - * the result. Such indices are listed in order from lowest to
1.1155 - * highest, separated by ", " (a comma and a space) and
1.1156 - * surrounded by braces, resulting in the usual mathematical
1.1157 - * notation for a set of integers.
1.1158 - *
1.1159 - * <p>Example:
1.1160 - * <pre>
1.1161 - * BitSet drPepper = new BitSet();</pre>
1.1162 - * Now {@code drPepper.toString()} returns "{@code {}}".<p>
1.1163 - * <pre>
1.1164 - * drPepper.set(2);</pre>
1.1165 - * Now {@code drPepper.toString()} returns "{@code {2}}".<p>
1.1166 - * <pre>
1.1167 - * drPepper.set(4);
1.1168 - * drPepper.set(10);</pre>
1.1169 - * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
1.1170 - *
1.1171 - * @return a string representation of this bit set
1.1172 - */
1.1173 - public String toString() {
1.1174 - checkInvariants();
1.1175 -
1.1176 - int numBits = (wordsInUse > 128) ?
1.1177 - cardinality() : wordsInUse * BITS_PER_WORD;
1.1178 - StringBuilder b = new StringBuilder(6*numBits + 2);
1.1179 - b.append('{');
1.1180 -
1.1181 - int i = nextSetBit(0);
1.1182 - if (i != -1) {
1.1183 - b.append(i);
1.1184 - for (i = nextSetBit(i+1); i >= 0; i = nextSetBit(i+1)) {
1.1185 - int endOfRun = nextClearBit(i);
1.1186 - do { b.append(", ").append(i); }
1.1187 - while (++i < endOfRun);
1.1188 - }
1.1189 - }
1.1190 -
1.1191 - b.append('}');
1.1192 - return b.toString();
1.1193 - }
1.1194 -}
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/rt/emul/compact/src/main/java/java/util/BitSet.java Thu Oct 31 11:36:52 2013 +0100
2.3 @@ -0,0 +1,1188 @@
2.4 +/*
2.5 + * Copyright (c) 1995, 2007, Oracle and/or its affiliates. All rights reserved.
2.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
2.7 + *
2.8 + * This code is free software; you can redistribute it and/or modify it
2.9 + * under the terms of the GNU General Public License version 2 only, as
2.10 + * published by the Free Software Foundation. Oracle designates this
2.11 + * particular file as subject to the "Classpath" exception as provided
2.12 + * by Oracle in the LICENSE file that accompanied this code.
2.13 + *
2.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
2.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
2.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
2.17 + * version 2 for more details (a copy is included in the LICENSE file that
2.18 + * accompanied this code).
2.19 + *
2.20 + * You should have received a copy of the GNU General Public License version
2.21 + * 2 along with this work; if not, write to the Free Software Foundation,
2.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
2.23 + *
2.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2.25 + * or visit www.oracle.com if you need additional information or have any
2.26 + * questions.
2.27 + */
2.28 +
2.29 +package java.util;
2.30 +
2.31 +import java.io.*;
2.32 +
2.33 +/**
2.34 + * This class implements a vector of bits that grows as needed. Each
2.35 + * component of the bit set has a {@code boolean} value. The
2.36 + * bits of a {@code BitSet} are indexed by nonnegative integers.
2.37 + * Individual indexed bits can be examined, set, or cleared. One
2.38 + * {@code BitSet} may be used to modify the contents of another
2.39 + * {@code BitSet} through logical AND, logical inclusive OR, and
2.40 + * logical exclusive OR operations.
2.41 + *
2.42 + * <p>By default, all bits in the set initially have the value
2.43 + * {@code false}.
2.44 + *
2.45 + * <p>Every bit set has a current size, which is the number of bits
2.46 + * of space currently in use by the bit set. Note that the size is
2.47 + * related to the implementation of a bit set, so it may change with
2.48 + * implementation. The length of a bit set relates to logical length
2.49 + * of a bit set and is defined independently of implementation.
2.50 + *
2.51 + * <p>Unless otherwise noted, passing a null parameter to any of the
2.52 + * methods in a {@code BitSet} will result in a
2.53 + * {@code NullPointerException}.
2.54 + *
2.55 + * <p>A {@code BitSet} is not safe for multithreaded use without
2.56 + * external synchronization.
2.57 + *
2.58 + * @author Arthur van Hoff
2.59 + * @author Michael McCloskey
2.60 + * @author Martin Buchholz
2.61 + * @since JDK1.0
2.62 + */
2.63 +public class BitSet implements Cloneable, java.io.Serializable {
2.64 + /*
2.65 + * BitSets are packed into arrays of "words." Currently a word is
2.66 + * a long, which consists of 64 bits, requiring 6 address bits.
2.67 + * The choice of word size is determined purely by performance concerns.
2.68 + */
2.69 + private final static int ADDRESS_BITS_PER_WORD = 6;
2.70 + private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
2.71 + private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
2.72 +
2.73 + /* Used to shift left or right for a partial word mask */
2.74 + private static final long WORD_MASK = 0xffffffffffffffffL;
2.75 +
2.76 + /**
2.77 + * @serialField bits long[]
2.78 + *
2.79 + * The bits in this BitSet. The ith bit is stored in bits[i/64] at
2.80 + * bit position i % 64 (where bit position 0 refers to the least
2.81 + * significant bit and 63 refers to the most significant bit).
2.82 + */
2.83 + private static final ObjectStreamField[] serialPersistentFields = {
2.84 + new ObjectStreamField("bits", long[].class),
2.85 + };
2.86 +
2.87 + /**
2.88 + * The internal field corresponding to the serialField "bits".
2.89 + */
2.90 + private long[] words;
2.91 +
2.92 + /**
2.93 + * The number of words in the logical size of this BitSet.
2.94 + */
2.95 + private transient int wordsInUse = 0;
2.96 +
2.97 + /**
2.98 + * Whether the size of "words" is user-specified. If so, we assume
2.99 + * the user knows what he's doing and try harder to preserve it.
2.100 + */
2.101 + private transient boolean sizeIsSticky = false;
2.102 +
2.103 + /* use serialVersionUID from JDK 1.0.2 for interoperability */
2.104 + private static final long serialVersionUID = 7997698588986878753L;
2.105 +
2.106 + /**
2.107 + * Given a bit index, return word index containing it.
2.108 + */
2.109 + private static int wordIndex(int bitIndex) {
2.110 + return bitIndex >> ADDRESS_BITS_PER_WORD;
2.111 + }
2.112 +
2.113 + /**
2.114 + * Every public method must preserve these invariants.
2.115 + */
2.116 + private void checkInvariants() {
2.117 + assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
2.118 + assert(wordsInUse >= 0 && wordsInUse <= words.length);
2.119 + assert(wordsInUse == words.length || words[wordsInUse] == 0);
2.120 + }
2.121 +
2.122 + /**
2.123 + * Sets the field wordsInUse to the logical size in words of the bit set.
2.124 + * WARNING:This method assumes that the number of words actually in use is
2.125 + * less than or equal to the current value of wordsInUse!
2.126 + */
2.127 + private void recalculateWordsInUse() {
2.128 + // Traverse the bitset until a used word is found
2.129 + int i;
2.130 + for (i = wordsInUse-1; i >= 0; i--)
2.131 + if (words[i] != 0)
2.132 + break;
2.133 +
2.134 + wordsInUse = i+1; // The new logical size
2.135 + }
2.136 +
2.137 + /**
2.138 + * Creates a new bit set. All bits are initially {@code false}.
2.139 + */
2.140 + public BitSet() {
2.141 + initWords(BITS_PER_WORD);
2.142 + sizeIsSticky = false;
2.143 + }
2.144 +
2.145 + /**
2.146 + * Creates a bit set whose initial size is large enough to explicitly
2.147 + * represent bits with indices in the range {@code 0} through
2.148 + * {@code nbits-1}. All bits are initially {@code false}.
2.149 + *
2.150 + * @param nbits the initial size of the bit set
2.151 + * @throws NegativeArraySizeException if the specified initial size
2.152 + * is negative
2.153 + */
2.154 + public BitSet(int nbits) {
2.155 + // nbits can't be negative; size 0 is OK
2.156 + if (nbits < 0)
2.157 + throw new NegativeArraySizeException("nbits < 0: " + nbits);
2.158 +
2.159 + initWords(nbits);
2.160 + sizeIsSticky = true;
2.161 + }
2.162 +
2.163 + private void initWords(int nbits) {
2.164 + words = new long[wordIndex(nbits-1) + 1];
2.165 + }
2.166 +
2.167 + /**
2.168 + * Creates a bit set using words as the internal representation.
2.169 + * The last word (if there is one) must be non-zero.
2.170 + */
2.171 + private BitSet(long[] words) {
2.172 + this.words = words;
2.173 + this.wordsInUse = words.length;
2.174 + checkInvariants();
2.175 + }
2.176 +
2.177 + /**
2.178 + * Returns a new bit set containing all the bits in the given long array.
2.179 + *
2.180 + * <p>More precisely,
2.181 + * <br>{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
2.182 + * <br>for all {@code n < 64 * longs.length}.
2.183 + *
2.184 + * <p>This method is equivalent to
2.185 + * {@code BitSet.valueOf(LongBuffer.wrap(longs))}.
2.186 + *
2.187 + * @param longs a long array containing a little-endian representation
2.188 + * of a sequence of bits to be used as the initial bits of the
2.189 + * new bit set
2.190 + * @since 1.7
2.191 + */
2.192 + public static BitSet valueOf(long[] longs) {
2.193 + int n;
2.194 + for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)
2.195 + ;
2.196 + return new BitSet(Arrays.copyOf(longs, n));
2.197 + }
2.198 +
2.199 + /**
2.200 + * Returns a new bit set containing all the bits in the given long
2.201 + * buffer between its position and limit.
2.202 + *
2.203 + * <p>More precisely,
2.204 + * <br>{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)}
2.205 + * <br>for all {@code n < 64 * lb.remaining()}.
2.206 + *
2.207 + * <p>The long buffer is not modified by this method, and no
2.208 + * reference to the buffer is retained by the bit set.
2.209 + *
2.210 + * @param lb a long buffer containing a little-endian representation
2.211 + * of a sequence of bits between its position and limit, to be
2.212 + * used as the initial bits of the new bit set
2.213 + * @since 1.7
2.214 + */
2.215 +// public static BitSet valueOf(LongBuffer lb) {
2.216 +// lb = lb.slice();
2.217 +// int n;
2.218 +// for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)
2.219 +// ;
2.220 +// long[] words = new long[n];
2.221 +// lb.get(words);
2.222 +// return new BitSet(words);
2.223 +// }
2.224 +
2.225 + /**
2.226 + * Returns a new bit set containing all the bits in the given byte array.
2.227 + *
2.228 + * <p>More precisely,
2.229 + * <br>{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
2.230 + * <br>for all {@code n < 8 * bytes.length}.
2.231 + *
2.232 + * <p>This method is equivalent to
2.233 + * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}.
2.234 + *
2.235 + * @param bytes a byte array containing a little-endian
2.236 + * representation of a sequence of bits to be used as the
2.237 + * initial bits of the new bit set
2.238 + * @since 1.7
2.239 + */
2.240 +// public static BitSet valueOf(byte[] bytes) {
2.241 +// return BitSet.valueOf(ByteBuffer.wrap(bytes));
2.242 +// }
2.243 +
2.244 + /**
2.245 + * Returns a new bit set containing all the bits in the given byte
2.246 + * buffer between its position and limit.
2.247 + *
2.248 + * <p>More precisely,
2.249 + * <br>{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)}
2.250 + * <br>for all {@code n < 8 * bb.remaining()}.
2.251 + *
2.252 + * <p>The byte buffer is not modified by this method, and no
2.253 + * reference to the buffer is retained by the bit set.
2.254 + *
2.255 + * @param bb a byte buffer containing a little-endian representation
2.256 + * of a sequence of bits between its position and limit, to be
2.257 + * used as the initial bits of the new bit set
2.258 + * @since 1.7
2.259 + */
2.260 +// public static BitSet valueOf(ByteBuffer bb) {
2.261 +// bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);
2.262 +// int n;
2.263 +// for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--)
2.264 +// ;
2.265 +// long[] words = new long[(n + 7) / 8];
2.266 +// bb.limit(n);
2.267 +// int i = 0;
2.268 +// while (bb.remaining() >= 8)
2.269 +// words[i++] = bb.getLong();
2.270 +// for (int remaining = bb.remaining(), j = 0; j < remaining; j++)
2.271 +// words[i] |= (bb.get() & 0xffL) << (8 * j);
2.272 +// return new BitSet(words);
2.273 +// }
2.274 +
2.275 + /**
2.276 + * Returns a new byte array containing all the bits in this bit set.
2.277 + *
2.278 + * <p>More precisely, if
2.279 + * <br>{@code byte[] bytes = s.toByteArray();}
2.280 + * <br>then {@code bytes.length == (s.length()+7)/8} and
2.281 + * <br>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
2.282 + * <br>for all {@code n < 8 * bytes.length}.
2.283 + *
2.284 + * @return a byte array containing a little-endian representation
2.285 + * of all the bits in this bit set
2.286 + * @since 1.7
2.287 + */
2.288 +// public byte[] toByteArray() {
2.289 +// int n = wordsInUse;
2.290 +// if (n == 0)
2.291 +// return new byte[0];
2.292 +// int len = 8 * (n-1);
2.293 +// for (long x = words[n - 1]; x != 0; x >>>= 8)
2.294 +// len++;
2.295 +// byte[] bytes = new byte[len];
2.296 +// ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);
2.297 +// for (int i = 0; i < n - 1; i++)
2.298 +// bb.putLong(words[i]);
2.299 +// for (long x = words[n - 1]; x != 0; x >>>= 8)
2.300 +// bb.put((byte) (x & 0xff));
2.301 +// return bytes;
2.302 +// }
2.303 +
2.304 + /**
2.305 + * Returns a new long array containing all the bits in this bit set.
2.306 + *
2.307 + * <p>More precisely, if
2.308 + * <br>{@code long[] longs = s.toLongArray();}
2.309 + * <br>then {@code longs.length == (s.length()+63)/64} and
2.310 + * <br>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
2.311 + * <br>for all {@code n < 64 * longs.length}.
2.312 + *
2.313 + * @return a long array containing a little-endian representation
2.314 + * of all the bits in this bit set
2.315 + * @since 1.7
2.316 + */
2.317 + public long[] toLongArray() {
2.318 + return Arrays.copyOf(words, wordsInUse);
2.319 + }
2.320 +
2.321 + /**
2.322 + * Ensures that the BitSet can hold enough words.
2.323 + * @param wordsRequired the minimum acceptable number of words.
2.324 + */
2.325 + private void ensureCapacity(int wordsRequired) {
2.326 + if (words.length < wordsRequired) {
2.327 + // Allocate larger of doubled size or required size
2.328 + int request = Math.max(2 * words.length, wordsRequired);
2.329 + words = Arrays.copyOf(words, request);
2.330 + sizeIsSticky = false;
2.331 + }
2.332 + }
2.333 +
2.334 + /**
2.335 + * Ensures that the BitSet can accommodate a given wordIndex,
2.336 + * temporarily violating the invariants. The caller must
2.337 + * restore the invariants before returning to the user,
2.338 + * possibly using recalculateWordsInUse().
2.339 + * @param wordIndex the index to be accommodated.
2.340 + */
2.341 + private void expandTo(int wordIndex) {
2.342 + int wordsRequired = wordIndex+1;
2.343 + if (wordsInUse < wordsRequired) {
2.344 + ensureCapacity(wordsRequired);
2.345 + wordsInUse = wordsRequired;
2.346 + }
2.347 + }
2.348 +
2.349 + /**
2.350 + * Checks that fromIndex ... toIndex is a valid range of bit indices.
2.351 + */
2.352 + private static void checkRange(int fromIndex, int toIndex) {
2.353 + if (fromIndex < 0)
2.354 + throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
2.355 + if (toIndex < 0)
2.356 + throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
2.357 + if (fromIndex > toIndex)
2.358 + throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
2.359 + " > toIndex: " + toIndex);
2.360 + }
2.361 +
2.362 + /**
2.363 + * Sets the bit at the specified index to the complement of its
2.364 + * current value.
2.365 + *
2.366 + * @param bitIndex the index of the bit to flip
2.367 + * @throws IndexOutOfBoundsException if the specified index is negative
2.368 + * @since 1.4
2.369 + */
2.370 + public void flip(int bitIndex) {
2.371 + if (bitIndex < 0)
2.372 + throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
2.373 +
2.374 + int wordIndex = wordIndex(bitIndex);
2.375 + expandTo(wordIndex);
2.376 +
2.377 + words[wordIndex] ^= (1L << bitIndex);
2.378 +
2.379 + recalculateWordsInUse();
2.380 + checkInvariants();
2.381 + }
2.382 +
2.383 + /**
2.384 + * Sets each bit from the specified {@code fromIndex} (inclusive) to the
2.385 + * specified {@code toIndex} (exclusive) to the complement of its current
2.386 + * value.
2.387 + *
2.388 + * @param fromIndex index of the first bit to flip
2.389 + * @param toIndex index after the last bit to flip
2.390 + * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
2.391 + * or {@code toIndex} is negative, or {@code fromIndex} is
2.392 + * larger than {@code toIndex}
2.393 + * @since 1.4
2.394 + */
2.395 + public void flip(int fromIndex, int toIndex) {
2.396 + checkRange(fromIndex, toIndex);
2.397 +
2.398 + if (fromIndex == toIndex)
2.399 + return;
2.400 +
2.401 + int startWordIndex = wordIndex(fromIndex);
2.402 + int endWordIndex = wordIndex(toIndex - 1);
2.403 + expandTo(endWordIndex);
2.404 +
2.405 + long firstWordMask = WORD_MASK << fromIndex;
2.406 + long lastWordMask = WORD_MASK >>> -toIndex;
2.407 + if (startWordIndex == endWordIndex) {
2.408 + // Case 1: One word
2.409 + words[startWordIndex] ^= (firstWordMask & lastWordMask);
2.410 + } else {
2.411 + // Case 2: Multiple words
2.412 + // Handle first word
2.413 + words[startWordIndex] ^= firstWordMask;
2.414 +
2.415 + // Handle intermediate words, if any
2.416 + for (int i = startWordIndex+1; i < endWordIndex; i++)
2.417 + words[i] ^= WORD_MASK;
2.418 +
2.419 + // Handle last word
2.420 + words[endWordIndex] ^= lastWordMask;
2.421 + }
2.422 +
2.423 + recalculateWordsInUse();
2.424 + checkInvariants();
2.425 + }
2.426 +
2.427 + /**
2.428 + * Sets the bit at the specified index to {@code true}.
2.429 + *
2.430 + * @param bitIndex a bit index
2.431 + * @throws IndexOutOfBoundsException if the specified index is negative
2.432 + * @since JDK1.0
2.433 + */
2.434 + public void set(int bitIndex) {
2.435 + if (bitIndex < 0)
2.436 + throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
2.437 +
2.438 + int wordIndex = wordIndex(bitIndex);
2.439 + expandTo(wordIndex);
2.440 +
2.441 + words[wordIndex] |= (1L << bitIndex); // Restores invariants
2.442 +
2.443 + checkInvariants();
2.444 + }
2.445 +
2.446 + /**
2.447 + * Sets the bit at the specified index to the specified value.
2.448 + *
2.449 + * @param bitIndex a bit index
2.450 + * @param value a boolean value to set
2.451 + * @throws IndexOutOfBoundsException if the specified index is negative
2.452 + * @since 1.4
2.453 + */
2.454 + public void set(int bitIndex, boolean value) {
2.455 + if (value)
2.456 + set(bitIndex);
2.457 + else
2.458 + clear(bitIndex);
2.459 + }
2.460 +
2.461 + /**
2.462 + * Sets the bits from the specified {@code fromIndex} (inclusive) to the
2.463 + * specified {@code toIndex} (exclusive) to {@code true}.
2.464 + *
2.465 + * @param fromIndex index of the first bit to be set
2.466 + * @param toIndex index after the last bit to be set
2.467 + * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
2.468 + * or {@code toIndex} is negative, or {@code fromIndex} is
2.469 + * larger than {@code toIndex}
2.470 + * @since 1.4
2.471 + */
2.472 + public void set(int fromIndex, int toIndex) {
2.473 + checkRange(fromIndex, toIndex);
2.474 +
2.475 + if (fromIndex == toIndex)
2.476 + return;
2.477 +
2.478 + // Increase capacity if necessary
2.479 + int startWordIndex = wordIndex(fromIndex);
2.480 + int endWordIndex = wordIndex(toIndex - 1);
2.481 + expandTo(endWordIndex);
2.482 +
2.483 + long firstWordMask = WORD_MASK << fromIndex;
2.484 + long lastWordMask = WORD_MASK >>> -toIndex;
2.485 + if (startWordIndex == endWordIndex) {
2.486 + // Case 1: One word
2.487 + words[startWordIndex] |= (firstWordMask & lastWordMask);
2.488 + } else {
2.489 + // Case 2: Multiple words
2.490 + // Handle first word
2.491 + words[startWordIndex] |= firstWordMask;
2.492 +
2.493 + // Handle intermediate words, if any
2.494 + for (int i = startWordIndex+1; i < endWordIndex; i++)
2.495 + words[i] = WORD_MASK;
2.496 +
2.497 + // Handle last word (restores invariants)
2.498 + words[endWordIndex] |= lastWordMask;
2.499 + }
2.500 +
2.501 + checkInvariants();
2.502 + }
2.503 +
2.504 + /**
2.505 + * Sets the bits from the specified {@code fromIndex} (inclusive) to the
2.506 + * specified {@code toIndex} (exclusive) to the specified value.
2.507 + *
2.508 + * @param fromIndex index of the first bit to be set
2.509 + * @param toIndex index after the last bit to be set
2.510 + * @param value value to set the selected bits to
2.511 + * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
2.512 + * or {@code toIndex} is negative, or {@code fromIndex} is
2.513 + * larger than {@code toIndex}
2.514 + * @since 1.4
2.515 + */
2.516 + public void set(int fromIndex, int toIndex, boolean value) {
2.517 + if (value)
2.518 + set(fromIndex, toIndex);
2.519 + else
2.520 + clear(fromIndex, toIndex);
2.521 + }
2.522 +
2.523 + /**
2.524 + * Sets the bit specified by the index to {@code false}.
2.525 + *
2.526 + * @param bitIndex the index of the bit to be cleared
2.527 + * @throws IndexOutOfBoundsException if the specified index is negative
2.528 + * @since JDK1.0
2.529 + */
2.530 + public void clear(int bitIndex) {
2.531 + if (bitIndex < 0)
2.532 + throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
2.533 +
2.534 + int wordIndex = wordIndex(bitIndex);
2.535 + if (wordIndex >= wordsInUse)
2.536 + return;
2.537 +
2.538 + words[wordIndex] &= ~(1L << bitIndex);
2.539 +
2.540 + recalculateWordsInUse();
2.541 + checkInvariants();
2.542 + }
2.543 +
2.544 + /**
2.545 + * Sets the bits from the specified {@code fromIndex} (inclusive) to the
2.546 + * specified {@code toIndex} (exclusive) to {@code false}.
2.547 + *
2.548 + * @param fromIndex index of the first bit to be cleared
2.549 + * @param toIndex index after the last bit to be cleared
2.550 + * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
2.551 + * or {@code toIndex} is negative, or {@code fromIndex} is
2.552 + * larger than {@code toIndex}
2.553 + * @since 1.4
2.554 + */
2.555 + public void clear(int fromIndex, int toIndex) {
2.556 + checkRange(fromIndex, toIndex);
2.557 +
2.558 + if (fromIndex == toIndex)
2.559 + return;
2.560 +
2.561 + int startWordIndex = wordIndex(fromIndex);
2.562 + if (startWordIndex >= wordsInUse)
2.563 + return;
2.564 +
2.565 + int endWordIndex = wordIndex(toIndex - 1);
2.566 + if (endWordIndex >= wordsInUse) {
2.567 + toIndex = length();
2.568 + endWordIndex = wordsInUse - 1;
2.569 + }
2.570 +
2.571 + long firstWordMask = WORD_MASK << fromIndex;
2.572 + long lastWordMask = WORD_MASK >>> -toIndex;
2.573 + if (startWordIndex == endWordIndex) {
2.574 + // Case 1: One word
2.575 + words[startWordIndex] &= ~(firstWordMask & lastWordMask);
2.576 + } else {
2.577 + // Case 2: Multiple words
2.578 + // Handle first word
2.579 + words[startWordIndex] &= ~firstWordMask;
2.580 +
2.581 + // Handle intermediate words, if any
2.582 + for (int i = startWordIndex+1; i < endWordIndex; i++)
2.583 + words[i] = 0;
2.584 +
2.585 + // Handle last word
2.586 + words[endWordIndex] &= ~lastWordMask;
2.587 + }
2.588 +
2.589 + recalculateWordsInUse();
2.590 + checkInvariants();
2.591 + }
2.592 +
2.593 + /**
2.594 + * Sets all of the bits in this BitSet to {@code false}.
2.595 + *
2.596 + * @since 1.4
2.597 + */
2.598 + public void clear() {
2.599 + while (wordsInUse > 0)
2.600 + words[--wordsInUse] = 0;
2.601 + }
2.602 +
2.603 + /**
2.604 + * Returns the value of the bit with the specified index. The value
2.605 + * is {@code true} if the bit with the index {@code bitIndex}
2.606 + * is currently set in this {@code BitSet}; otherwise, the result
2.607 + * is {@code false}.
2.608 + *
2.609 + * @param bitIndex the bit index
2.610 + * @return the value of the bit with the specified index
2.611 + * @throws IndexOutOfBoundsException if the specified index is negative
2.612 + */
2.613 + public boolean get(int bitIndex) {
2.614 + if (bitIndex < 0)
2.615 + throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
2.616 +
2.617 + checkInvariants();
2.618 +
2.619 + int wordIndex = wordIndex(bitIndex);
2.620 + return (wordIndex < wordsInUse)
2.621 + && ((words[wordIndex] & (1L << bitIndex)) != 0);
2.622 + }
2.623 +
2.624 + /**
2.625 + * Returns a new {@code BitSet} composed of bits from this {@code BitSet}
2.626 + * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).
2.627 + *
2.628 + * @param fromIndex index of the first bit to include
2.629 + * @param toIndex index after the last bit to include
2.630 + * @return a new {@code BitSet} from a range of this {@code BitSet}
2.631 + * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
2.632 + * or {@code toIndex} is negative, or {@code fromIndex} is
2.633 + * larger than {@code toIndex}
2.634 + * @since 1.4
2.635 + */
2.636 + public BitSet get(int fromIndex, int toIndex) {
2.637 + checkRange(fromIndex, toIndex);
2.638 +
2.639 + checkInvariants();
2.640 +
2.641 + int len = length();
2.642 +
2.643 + // If no set bits in range return empty bitset
2.644 + if (len <= fromIndex || fromIndex == toIndex)
2.645 + return new BitSet(0);
2.646 +
2.647 + // An optimization
2.648 + if (toIndex > len)
2.649 + toIndex = len;
2.650 +
2.651 + BitSet result = new BitSet(toIndex - fromIndex);
2.652 + int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;
2.653 + int sourceIndex = wordIndex(fromIndex);
2.654 + boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);
2.655 +
2.656 + // Process all words but the last word
2.657 + for (int i = 0; i < targetWords - 1; i++, sourceIndex++)
2.658 + result.words[i] = wordAligned ? words[sourceIndex] :
2.659 + (words[sourceIndex] >>> fromIndex) |
2.660 + (words[sourceIndex+1] << -fromIndex);
2.661 +
2.662 + // Process the last word
2.663 + long lastWordMask = WORD_MASK >>> -toIndex;
2.664 + result.words[targetWords - 1] =
2.665 + ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)
2.666 + ? /* straddles source words */
2.667 + ((words[sourceIndex] >>> fromIndex) |
2.668 + (words[sourceIndex+1] & lastWordMask) << -fromIndex)
2.669 + :
2.670 + ((words[sourceIndex] & lastWordMask) >>> fromIndex);
2.671 +
2.672 + // Set wordsInUse correctly
2.673 + result.wordsInUse = targetWords;
2.674 + result.recalculateWordsInUse();
2.675 + result.checkInvariants();
2.676 +
2.677 + return result;
2.678 + }
2.679 +
2.680 + /**
2.681 + * Returns the index of the first bit that is set to {@code true}
2.682 + * that occurs on or after the specified starting index. If no such
2.683 + * bit exists then {@code -1} is returned.
2.684 + *
2.685 + * <p>To iterate over the {@code true} bits in a {@code BitSet},
2.686 + * use the following loop:
2.687 + *
2.688 + * <pre> {@code
2.689 + * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
2.690 + * // operate on index i here
2.691 + * }}</pre>
2.692 + *
2.693 + * @param fromIndex the index to start checking from (inclusive)
2.694 + * @return the index of the next set bit, or {@code -1} if there
2.695 + * is no such bit
2.696 + * @throws IndexOutOfBoundsException if the specified index is negative
2.697 + * @since 1.4
2.698 + */
2.699 + public int nextSetBit(int fromIndex) {
2.700 + if (fromIndex < 0)
2.701 + throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
2.702 +
2.703 + checkInvariants();
2.704 +
2.705 + int u = wordIndex(fromIndex);
2.706 + if (u >= wordsInUse)
2.707 + return -1;
2.708 +
2.709 + long word = words[u] & (WORD_MASK << fromIndex);
2.710 +
2.711 + while (true) {
2.712 + if (word != 0)
2.713 + return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
2.714 + if (++u == wordsInUse)
2.715 + return -1;
2.716 + word = words[u];
2.717 + }
2.718 + }
2.719 +
2.720 + /**
2.721 + * Returns the index of the first bit that is set to {@code false}
2.722 + * that occurs on or after the specified starting index.
2.723 + *
2.724 + * @param fromIndex the index to start checking from (inclusive)
2.725 + * @return the index of the next clear bit
2.726 + * @throws IndexOutOfBoundsException if the specified index is negative
2.727 + * @since 1.4
2.728 + */
2.729 + public int nextClearBit(int fromIndex) {
2.730 + // Neither spec nor implementation handle bitsets of maximal length.
2.731 + // See 4816253.
2.732 + if (fromIndex < 0)
2.733 + throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
2.734 +
2.735 + checkInvariants();
2.736 +
2.737 + int u = wordIndex(fromIndex);
2.738 + if (u >= wordsInUse)
2.739 + return fromIndex;
2.740 +
2.741 + long word = ~words[u] & (WORD_MASK << fromIndex);
2.742 +
2.743 + while (true) {
2.744 + if (word != 0)
2.745 + return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
2.746 + if (++u == wordsInUse)
2.747 + return wordsInUse * BITS_PER_WORD;
2.748 + word = ~words[u];
2.749 + }
2.750 + }
2.751 +
2.752 + /**
2.753 + * Returns the index of the nearest bit that is set to {@code true}
2.754 + * that occurs on or before the specified starting index.
2.755 + * If no such bit exists, or if {@code -1} is given as the
2.756 + * starting index, then {@code -1} is returned.
2.757 + *
2.758 + * <p>To iterate over the {@code true} bits in a {@code BitSet},
2.759 + * use the following loop:
2.760 + *
2.761 + * <pre> {@code
2.762 + * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
2.763 + * // operate on index i here
2.764 + * }}</pre>
2.765 + *
2.766 + * @param fromIndex the index to start checking from (inclusive)
2.767 + * @return the index of the previous set bit, or {@code -1} if there
2.768 + * is no such bit
2.769 + * @throws IndexOutOfBoundsException if the specified index is less
2.770 + * than {@code -1}
2.771 + * @since 1.7
2.772 + */
2.773 + public int previousSetBit(int fromIndex) {
2.774 + if (fromIndex < 0) {
2.775 + if (fromIndex == -1)
2.776 + return -1;
2.777 + throw new IndexOutOfBoundsException(
2.778 + "fromIndex < -1: " + fromIndex);
2.779 + }
2.780 +
2.781 + checkInvariants();
2.782 +
2.783 + int u = wordIndex(fromIndex);
2.784 + if (u >= wordsInUse)
2.785 + return length() - 1;
2.786 +
2.787 + long word = words[u] & (WORD_MASK >>> -(fromIndex+1));
2.788 +
2.789 + while (true) {
2.790 + if (word != 0)
2.791 + return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
2.792 + if (u-- == 0)
2.793 + return -1;
2.794 + word = words[u];
2.795 + }
2.796 + }
2.797 +
2.798 + /**
2.799 + * Returns the index of the nearest bit that is set to {@code false}
2.800 + * that occurs on or before the specified starting index.
2.801 + * If no such bit exists, or if {@code -1} is given as the
2.802 + * starting index, then {@code -1} is returned.
2.803 + *
2.804 + * @param fromIndex the index to start checking from (inclusive)
2.805 + * @return the index of the previous clear bit, or {@code -1} if there
2.806 + * is no such bit
2.807 + * @throws IndexOutOfBoundsException if the specified index is less
2.808 + * than {@code -1}
2.809 + * @since 1.7
2.810 + */
2.811 + public int previousClearBit(int fromIndex) {
2.812 + if (fromIndex < 0) {
2.813 + if (fromIndex == -1)
2.814 + return -1;
2.815 + throw new IndexOutOfBoundsException(
2.816 + "fromIndex < -1: " + fromIndex);
2.817 + }
2.818 +
2.819 + checkInvariants();
2.820 +
2.821 + int u = wordIndex(fromIndex);
2.822 + if (u >= wordsInUse)
2.823 + return fromIndex;
2.824 +
2.825 + long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1));
2.826 +
2.827 + while (true) {
2.828 + if (word != 0)
2.829 + return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);
2.830 + if (u-- == 0)
2.831 + return -1;
2.832 + word = ~words[u];
2.833 + }
2.834 + }
2.835 +
2.836 + /**
2.837 + * Returns the "logical size" of this {@code BitSet}: the index of
2.838 + * the highest set bit in the {@code BitSet} plus one. Returns zero
2.839 + * if the {@code BitSet} contains no set bits.
2.840 + *
2.841 + * @return the logical size of this {@code BitSet}
2.842 + * @since 1.2
2.843 + */
2.844 + public int length() {
2.845 + if (wordsInUse == 0)
2.846 + return 0;
2.847 +
2.848 + return BITS_PER_WORD * (wordsInUse - 1) +
2.849 + (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
2.850 + }
2.851 +
2.852 + /**
2.853 + * Returns true if this {@code BitSet} contains no bits that are set
2.854 + * to {@code true}.
2.855 + *
2.856 + * @return boolean indicating whether this {@code BitSet} is empty
2.857 + * @since 1.4
2.858 + */
2.859 + public boolean isEmpty() {
2.860 + return wordsInUse == 0;
2.861 + }
2.862 +
2.863 + /**
2.864 + * Returns true if the specified {@code BitSet} has any bits set to
2.865 + * {@code true} that are also set to {@code true} in this {@code BitSet}.
2.866 + *
2.867 + * @param set {@code BitSet} to intersect with
2.868 + * @return boolean indicating whether this {@code BitSet} intersects
2.869 + * the specified {@code BitSet}
2.870 + * @since 1.4
2.871 + */
2.872 + public boolean intersects(BitSet set) {
2.873 + for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
2.874 + if ((words[i] & set.words[i]) != 0)
2.875 + return true;
2.876 + return false;
2.877 + }
2.878 +
2.879 + /**
2.880 + * Returns the number of bits set to {@code true} in this {@code BitSet}.
2.881 + *
2.882 + * @return the number of bits set to {@code true} in this {@code BitSet}
2.883 + * @since 1.4
2.884 + */
2.885 + public int cardinality() {
2.886 + int sum = 0;
2.887 + for (int i = 0; i < wordsInUse; i++)
2.888 + sum += Long.bitCount(words[i]);
2.889 + return sum;
2.890 + }
2.891 +
2.892 + /**
2.893 + * Performs a logical <b>AND</b> of this target bit set with the
2.894 + * argument bit set. This bit set is modified so that each bit in it
2.895 + * has the value {@code true} if and only if it both initially
2.896 + * had the value {@code true} and the corresponding bit in the
2.897 + * bit set argument also had the value {@code true}.
2.898 + *
2.899 + * @param set a bit set
2.900 + */
2.901 + public void and(BitSet set) {
2.902 + if (this == set)
2.903 + return;
2.904 +
2.905 + while (wordsInUse > set.wordsInUse)
2.906 + words[--wordsInUse] = 0;
2.907 +
2.908 + // Perform logical AND on words in common
2.909 + for (int i = 0; i < wordsInUse; i++)
2.910 + words[i] &= set.words[i];
2.911 +
2.912 + recalculateWordsInUse();
2.913 + checkInvariants();
2.914 + }
2.915 +
2.916 + /**
2.917 + * Performs a logical <b>OR</b> of this bit set with the bit set
2.918 + * argument. This bit set is modified so that a bit in it has the
2.919 + * value {@code true} if and only if it either already had the
2.920 + * value {@code true} or the corresponding bit in the bit set
2.921 + * argument has the value {@code true}.
2.922 + *
2.923 + * @param set a bit set
2.924 + */
2.925 + public void or(BitSet set) {
2.926 + if (this == set)
2.927 + return;
2.928 +
2.929 + int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
2.930 +
2.931 + if (wordsInUse < set.wordsInUse) {
2.932 + ensureCapacity(set.wordsInUse);
2.933 + wordsInUse = set.wordsInUse;
2.934 + }
2.935 +
2.936 + // Perform logical OR on words in common
2.937 + for (int i = 0; i < wordsInCommon; i++)
2.938 + words[i] |= set.words[i];
2.939 +
2.940 + // Copy any remaining words
2.941 + if (wordsInCommon < set.wordsInUse)
2.942 + System.arraycopy(set.words, wordsInCommon,
2.943 + words, wordsInCommon,
2.944 + wordsInUse - wordsInCommon);
2.945 +
2.946 + // recalculateWordsInUse() is unnecessary
2.947 + checkInvariants();
2.948 + }
2.949 +
2.950 + /**
2.951 + * Performs a logical <b>XOR</b> of this bit set with the bit set
2.952 + * argument. This bit set is modified so that a bit in it has the
2.953 + * value {@code true} if and only if one of the following
2.954 + * statements holds:
2.955 + * <ul>
2.956 + * <li>The bit initially has the value {@code true}, and the
2.957 + * corresponding bit in the argument has the value {@code false}.
2.958 + * <li>The bit initially has the value {@code false}, and the
2.959 + * corresponding bit in the argument has the value {@code true}.
2.960 + * </ul>
2.961 + *
2.962 + * @param set a bit set
2.963 + */
2.964 + public void xor(BitSet set) {
2.965 + int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
2.966 +
2.967 + if (wordsInUse < set.wordsInUse) {
2.968 + ensureCapacity(set.wordsInUse);
2.969 + wordsInUse = set.wordsInUse;
2.970 + }
2.971 +
2.972 + // Perform logical XOR on words in common
2.973 + for (int i = 0; i < wordsInCommon; i++)
2.974 + words[i] ^= set.words[i];
2.975 +
2.976 + // Copy any remaining words
2.977 + if (wordsInCommon < set.wordsInUse)
2.978 + System.arraycopy(set.words, wordsInCommon,
2.979 + words, wordsInCommon,
2.980 + set.wordsInUse - wordsInCommon);
2.981 +
2.982 + recalculateWordsInUse();
2.983 + checkInvariants();
2.984 + }
2.985 +
2.986 + /**
2.987 + * Clears all of the bits in this {@code BitSet} whose corresponding
2.988 + * bit is set in the specified {@code BitSet}.
2.989 + *
2.990 + * @param set the {@code BitSet} with which to mask this
2.991 + * {@code BitSet}
2.992 + * @since 1.2
2.993 + */
2.994 + public void andNot(BitSet set) {
2.995 + // Perform logical (a & !b) on words in common
2.996 + for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
2.997 + words[i] &= ~set.words[i];
2.998 +
2.999 + recalculateWordsInUse();
2.1000 + checkInvariants();
2.1001 + }
2.1002 +
2.1003 + /**
2.1004 + * Returns the hash code value for this bit set. The hash code depends
2.1005 + * only on which bits are set within this {@code BitSet}.
2.1006 + *
2.1007 + * <p>The hash code is defined to be the result of the following
2.1008 + * calculation:
2.1009 + * <pre> {@code
2.1010 + * public int hashCode() {
2.1011 + * long h = 1234;
2.1012 + * long[] words = toLongArray();
2.1013 + * for (int i = words.length; --i >= 0; )
2.1014 + * h ^= words[i] * (i + 1);
2.1015 + * return (int)((h >> 32) ^ h);
2.1016 + * }}</pre>
2.1017 + * Note that the hash code changes if the set of bits is altered.
2.1018 + *
2.1019 + * @return the hash code value for this bit set
2.1020 + */
2.1021 + public int hashCode() {
2.1022 + long h = 1234;
2.1023 + for (int i = wordsInUse; --i >= 0; )
2.1024 + h ^= words[i] * (i + 1);
2.1025 +
2.1026 + return (int)((h >> 32) ^ h);
2.1027 + }
2.1028 +
2.1029 + /**
2.1030 + * Returns the number of bits of space actually in use by this
2.1031 + * {@code BitSet} to represent bit values.
2.1032 + * The maximum element in the set is the size - 1st element.
2.1033 + *
2.1034 + * @return the number of bits currently in this bit set
2.1035 + */
2.1036 + public int size() {
2.1037 + return words.length * BITS_PER_WORD;
2.1038 + }
2.1039 +
2.1040 + /**
2.1041 + * Compares this object against the specified object.
2.1042 + * The result is {@code true} if and only if the argument is
2.1043 + * not {@code null} and is a {@code Bitset} object that has
2.1044 + * exactly the same set of bits set to {@code true} as this bit
2.1045 + * set. That is, for every nonnegative {@code int} index {@code k},
2.1046 + * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
2.1047 + * must be true. The current sizes of the two bit sets are not compared.
2.1048 + *
2.1049 + * @param obj the object to compare with
2.1050 + * @return {@code true} if the objects are the same;
2.1051 + * {@code false} otherwise
2.1052 + * @see #size()
2.1053 + */
2.1054 + public boolean equals(Object obj) {
2.1055 + if (!(obj instanceof BitSet))
2.1056 + return false;
2.1057 + if (this == obj)
2.1058 + return true;
2.1059 +
2.1060 + BitSet set = (BitSet) obj;
2.1061 +
2.1062 + checkInvariants();
2.1063 + set.checkInvariants();
2.1064 +
2.1065 + if (wordsInUse != set.wordsInUse)
2.1066 + return false;
2.1067 +
2.1068 + // Check words in use by both BitSets
2.1069 + for (int i = 0; i < wordsInUse; i++)
2.1070 + if (words[i] != set.words[i])
2.1071 + return false;
2.1072 +
2.1073 + return true;
2.1074 + }
2.1075 +
2.1076 + /**
2.1077 + * Cloning this {@code BitSet} produces a new {@code BitSet}
2.1078 + * that is equal to it.
2.1079 + * The clone of the bit set is another bit set that has exactly the
2.1080 + * same bits set to {@code true} as this bit set.
2.1081 + *
2.1082 + * @return a clone of this bit set
2.1083 + * @see #size()
2.1084 + */
2.1085 + public Object clone() {
2.1086 + if (! sizeIsSticky)
2.1087 + trimToSize();
2.1088 +
2.1089 + try {
2.1090 + BitSet result = (BitSet) super.clone();
2.1091 + result.words = words.clone();
2.1092 + result.checkInvariants();
2.1093 + return result;
2.1094 + } catch (CloneNotSupportedException e) {
2.1095 + throw new InternalError();
2.1096 + }
2.1097 + }
2.1098 +
2.1099 + /**
2.1100 + * Attempts to reduce internal storage used for the bits in this bit set.
2.1101 + * Calling this method may, but is not required to, affect the value
2.1102 + * returned by a subsequent call to the {@link #size()} method.
2.1103 + */
2.1104 + private void trimToSize() {
2.1105 + if (wordsInUse != words.length) {
2.1106 + words = Arrays.copyOf(words, wordsInUse);
2.1107 + checkInvariants();
2.1108 + }
2.1109 + }
2.1110 +
2.1111 + /**
2.1112 + * Save the state of the {@code BitSet} instance to a stream (i.e.,
2.1113 + * serialize it).
2.1114 + */
2.1115 + private void writeObject(ObjectOutputStream s)
2.1116 + throws IOException {
2.1117 +
2.1118 + checkInvariants();
2.1119 +
2.1120 + if (! sizeIsSticky)
2.1121 + trimToSize();
2.1122 +
2.1123 + ObjectOutputStream.PutField fields = s.putFields();
2.1124 + fields.put("bits", words);
2.1125 + s.writeFields();
2.1126 + }
2.1127 +
2.1128 + /**
2.1129 + * Reconstitute the {@code BitSet} instance from a stream (i.e.,
2.1130 + * deserialize it).
2.1131 + */
2.1132 + private void readObject(ObjectInputStream s)
2.1133 + throws IOException, ClassNotFoundException {
2.1134 +
2.1135 + ObjectInputStream.GetField fields = s.readFields();
2.1136 + words = (long[]) fields.get("bits", null);
2.1137 +
2.1138 + // Assume maximum length then find real length
2.1139 + // because recalculateWordsInUse assumes maintenance
2.1140 + // or reduction in logical size
2.1141 + wordsInUse = words.length;
2.1142 + recalculateWordsInUse();
2.1143 + sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic
2.1144 + checkInvariants();
2.1145 + }
2.1146 +
2.1147 + /**
2.1148 + * Returns a string representation of this bit set. For every index
2.1149 + * for which this {@code BitSet} contains a bit in the set
2.1150 + * state, the decimal representation of that index is included in
2.1151 + * the result. Such indices are listed in order from lowest to
2.1152 + * highest, separated by ", " (a comma and a space) and
2.1153 + * surrounded by braces, resulting in the usual mathematical
2.1154 + * notation for a set of integers.
2.1155 + *
2.1156 + * <p>Example:
2.1157 + * <pre>
2.1158 + * BitSet drPepper = new BitSet();</pre>
2.1159 + * Now {@code drPepper.toString()} returns "{@code {}}".<p>
2.1160 + * <pre>
2.1161 + * drPepper.set(2);</pre>
2.1162 + * Now {@code drPepper.toString()} returns "{@code {2}}".<p>
2.1163 + * <pre>
2.1164 + * drPepper.set(4);
2.1165 + * drPepper.set(10);</pre>
2.1166 + * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
2.1167 + *
2.1168 + * @return a string representation of this bit set
2.1169 + */
2.1170 + public String toString() {
2.1171 + checkInvariants();
2.1172 +
2.1173 + int numBits = (wordsInUse > 128) ?
2.1174 + cardinality() : wordsInUse * BITS_PER_WORD;
2.1175 + StringBuilder b = new StringBuilder(6*numBits + 2);
2.1176 + b.append('{');
2.1177 +
2.1178 + int i = nextSetBit(0);
2.1179 + if (i != -1) {
2.1180 + b.append(i);
2.1181 + for (i = nextSetBit(i+1); i >= 0; i = nextSetBit(i+1)) {
2.1182 + int endOfRun = nextClearBit(i);
2.1183 + do { b.append(", ").append(i); }
2.1184 + while (++i < endOfRun);
2.1185 + }
2.1186 + }
2.1187 +
2.1188 + b.append('}');
2.1189 + return b.toString();
2.1190 + }
2.1191 +}