1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/emul/compact/src/main/java/java/util/BitSet.java Thu Oct 31 11:30:29 2013 +0100
1.3 @@ -0,0 +1,1191 @@
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 +}