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 -}