1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/BitSet.java Thu Oct 31 11:36:52 2013 +0100
1.3 @@ -0,0 +1,1188 @@
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 +
1.33 +/**
1.34 + * This class implements a vector of bits that grows as needed. Each
1.35 + * component of the bit set has a {@code boolean} value. The
1.36 + * bits of a {@code BitSet} are indexed by nonnegative integers.
1.37 + * Individual indexed bits can be examined, set, or cleared. One
1.38 + * {@code BitSet} may be used to modify the contents of another
1.39 + * {@code BitSet} through logical AND, logical inclusive OR, and
1.40 + * logical exclusive OR operations.
1.41 + *
1.42 + * <p>By default, all bits in the set initially have the value
1.43 + * {@code false}.
1.44 + *
1.45 + * <p>Every bit set has a current size, which is the number of bits
1.46 + * of space currently in use by the bit set. Note that the size is
1.47 + * related to the implementation of a bit set, so it may change with
1.48 + * implementation. The length of a bit set relates to logical length
1.49 + * of a bit set and is defined independently of implementation.
1.50 + *
1.51 + * <p>Unless otherwise noted, passing a null parameter to any of the
1.52 + * methods in a {@code BitSet} will result in a
1.53 + * {@code NullPointerException}.
1.54 + *
1.55 + * <p>A {@code BitSet} is not safe for multithreaded use without
1.56 + * external synchronization.
1.57 + *
1.58 + * @author Arthur van Hoff
1.59 + * @author Michael McCloskey
1.60 + * @author Martin Buchholz
1.61 + * @since JDK1.0
1.62 + */
1.63 +public class BitSet implements Cloneable, java.io.Serializable {
1.64 + /*
1.65 + * BitSets are packed into arrays of "words." Currently a word is
1.66 + * a long, which consists of 64 bits, requiring 6 address bits.
1.67 + * The choice of word size is determined purely by performance concerns.
1.68 + */
1.69 + private final static int ADDRESS_BITS_PER_WORD = 6;
1.70 + private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
1.71 + private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
1.72 +
1.73 + /* Used to shift left or right for a partial word mask */
1.74 + private static final long WORD_MASK = 0xffffffffffffffffL;
1.75 +
1.76 + /**
1.77 + * @serialField bits long[]
1.78 + *
1.79 + * The bits in this BitSet. The ith bit is stored in bits[i/64] at
1.80 + * bit position i % 64 (where bit position 0 refers to the least
1.81 + * significant bit and 63 refers to the most significant bit).
1.82 + */
1.83 + private static final ObjectStreamField[] serialPersistentFields = {
1.84 + new ObjectStreamField("bits", long[].class),
1.85 + };
1.86 +
1.87 + /**
1.88 + * The internal field corresponding to the serialField "bits".
1.89 + */
1.90 + private long[] words;
1.91 +
1.92 + /**
1.93 + * The number of words in the logical size of this BitSet.
1.94 + */
1.95 + private transient int wordsInUse = 0;
1.96 +
1.97 + /**
1.98 + * Whether the size of "words" is user-specified. If so, we assume
1.99 + * the user knows what he's doing and try harder to preserve it.
1.100 + */
1.101 + private transient boolean sizeIsSticky = false;
1.102 +
1.103 + /* use serialVersionUID from JDK 1.0.2 for interoperability */
1.104 + private static final long serialVersionUID = 7997698588986878753L;
1.105 +
1.106 + /**
1.107 + * Given a bit index, return word index containing it.
1.108 + */
1.109 + private static int wordIndex(int bitIndex) {
1.110 + return bitIndex >> ADDRESS_BITS_PER_WORD;
1.111 + }
1.112 +
1.113 + /**
1.114 + * Every public method must preserve these invariants.
1.115 + */
1.116 + private void checkInvariants() {
1.117 + assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
1.118 + assert(wordsInUse >= 0 && wordsInUse <= words.length);
1.119 + assert(wordsInUse == words.length || words[wordsInUse] == 0);
1.120 + }
1.121 +
1.122 + /**
1.123 + * Sets the field wordsInUse to the logical size in words of the bit set.
1.124 + * WARNING:This method assumes that the number of words actually in use is
1.125 + * less than or equal to the current value of wordsInUse!
1.126 + */
1.127 + private void recalculateWordsInUse() {
1.128 + // Traverse the bitset until a used word is found
1.129 + int i;
1.130 + for (i = wordsInUse-1; i >= 0; i--)
1.131 + if (words[i] != 0)
1.132 + break;
1.133 +
1.134 + wordsInUse = i+1; // The new logical size
1.135 + }
1.136 +
1.137 + /**
1.138 + * Creates a new bit set. All bits are initially {@code false}.
1.139 + */
1.140 + public BitSet() {
1.141 + initWords(BITS_PER_WORD);
1.142 + sizeIsSticky = false;
1.143 + }
1.144 +
1.145 + /**
1.146 + * Creates a bit set whose initial size is large enough to explicitly
1.147 + * represent bits with indices in the range {@code 0} through
1.148 + * {@code nbits-1}. All bits are initially {@code false}.
1.149 + *
1.150 + * @param nbits the initial size of the bit set
1.151 + * @throws NegativeArraySizeException if the specified initial size
1.152 + * is negative
1.153 + */
1.154 + public BitSet(int nbits) {
1.155 + // nbits can't be negative; size 0 is OK
1.156 + if (nbits < 0)
1.157 + throw new NegativeArraySizeException("nbits < 0: " + nbits);
1.158 +
1.159 + initWords(nbits);
1.160 + sizeIsSticky = true;
1.161 + }
1.162 +
1.163 + private void initWords(int nbits) {
1.164 + words = new long[wordIndex(nbits-1) + 1];
1.165 + }
1.166 +
1.167 + /**
1.168 + * Creates a bit set using words as the internal representation.
1.169 + * The last word (if there is one) must be non-zero.
1.170 + */
1.171 + private BitSet(long[] words) {
1.172 + this.words = words;
1.173 + this.wordsInUse = words.length;
1.174 + checkInvariants();
1.175 + }
1.176 +
1.177 + /**
1.178 + * Returns a new bit set containing all the bits in the given long array.
1.179 + *
1.180 + * <p>More precisely,
1.181 + * <br>{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
1.182 + * <br>for all {@code n < 64 * longs.length}.
1.183 + *
1.184 + * <p>This method is equivalent to
1.185 + * {@code BitSet.valueOf(LongBuffer.wrap(longs))}.
1.186 + *
1.187 + * @param longs a long array containing a little-endian representation
1.188 + * of a sequence of bits to be used as the initial bits of the
1.189 + * new bit set
1.190 + * @since 1.7
1.191 + */
1.192 + public static BitSet valueOf(long[] longs) {
1.193 + int n;
1.194 + for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)
1.195 + ;
1.196 + return new BitSet(Arrays.copyOf(longs, n));
1.197 + }
1.198 +
1.199 + /**
1.200 + * Returns a new bit set containing all the bits in the given long
1.201 + * buffer between its position and limit.
1.202 + *
1.203 + * <p>More precisely,
1.204 + * <br>{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)}
1.205 + * <br>for all {@code n < 64 * lb.remaining()}.
1.206 + *
1.207 + * <p>The long buffer is not modified by this method, and no
1.208 + * reference to the buffer is retained by the bit set.
1.209 + *
1.210 + * @param lb a long buffer containing a little-endian representation
1.211 + * of a sequence of bits between its position and limit, to be
1.212 + * used as the initial bits of the new bit set
1.213 + * @since 1.7
1.214 + */
1.215 +// public static BitSet valueOf(LongBuffer lb) {
1.216 +// lb = lb.slice();
1.217 +// int n;
1.218 +// for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)
1.219 +// ;
1.220 +// long[] words = new long[n];
1.221 +// lb.get(words);
1.222 +// return new BitSet(words);
1.223 +// }
1.224 +
1.225 + /**
1.226 + * Returns a new bit set containing all the bits in the given byte array.
1.227 + *
1.228 + * <p>More precisely,
1.229 + * <br>{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
1.230 + * <br>for all {@code n < 8 * bytes.length}.
1.231 + *
1.232 + * <p>This method is equivalent to
1.233 + * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}.
1.234 + *
1.235 + * @param bytes a byte array containing a little-endian
1.236 + * representation of a sequence of bits to be used as the
1.237 + * initial bits of the new bit set
1.238 + * @since 1.7
1.239 + */
1.240 +// public static BitSet valueOf(byte[] bytes) {
1.241 +// return BitSet.valueOf(ByteBuffer.wrap(bytes));
1.242 +// }
1.243 +
1.244 + /**
1.245 + * Returns a new bit set containing all the bits in the given byte
1.246 + * buffer between its position and limit.
1.247 + *
1.248 + * <p>More precisely,
1.249 + * <br>{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)}
1.250 + * <br>for all {@code n < 8 * bb.remaining()}.
1.251 + *
1.252 + * <p>The byte buffer is not modified by this method, and no
1.253 + * reference to the buffer is retained by the bit set.
1.254 + *
1.255 + * @param bb a byte buffer containing a little-endian representation
1.256 + * of a sequence of bits between its position and limit, to be
1.257 + * used as the initial bits of the new bit set
1.258 + * @since 1.7
1.259 + */
1.260 +// public static BitSet valueOf(ByteBuffer bb) {
1.261 +// bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);
1.262 +// int n;
1.263 +// for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--)
1.264 +// ;
1.265 +// long[] words = new long[(n + 7) / 8];
1.266 +// bb.limit(n);
1.267 +// int i = 0;
1.268 +// while (bb.remaining() >= 8)
1.269 +// words[i++] = bb.getLong();
1.270 +// for (int remaining = bb.remaining(), j = 0; j < remaining; j++)
1.271 +// words[i] |= (bb.get() & 0xffL) << (8 * j);
1.272 +// return new BitSet(words);
1.273 +// }
1.274 +
1.275 + /**
1.276 + * Returns a new byte array containing all the bits in this bit set.
1.277 + *
1.278 + * <p>More precisely, if
1.279 + * <br>{@code byte[] bytes = s.toByteArray();}
1.280 + * <br>then {@code bytes.length == (s.length()+7)/8} and
1.281 + * <br>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
1.282 + * <br>for all {@code n < 8 * bytes.length}.
1.283 + *
1.284 + * @return a byte array containing a little-endian representation
1.285 + * of all the bits in this bit set
1.286 + * @since 1.7
1.287 + */
1.288 +// public byte[] toByteArray() {
1.289 +// int n = wordsInUse;
1.290 +// if (n == 0)
1.291 +// return new byte[0];
1.292 +// int len = 8 * (n-1);
1.293 +// for (long x = words[n - 1]; x != 0; x >>>= 8)
1.294 +// len++;
1.295 +// byte[] bytes = new byte[len];
1.296 +// ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);
1.297 +// for (int i = 0; i < n - 1; i++)
1.298 +// bb.putLong(words[i]);
1.299 +// for (long x = words[n - 1]; x != 0; x >>>= 8)
1.300 +// bb.put((byte) (x & 0xff));
1.301 +// return bytes;
1.302 +// }
1.303 +
1.304 + /**
1.305 + * Returns a new long array containing all the bits in this bit set.
1.306 + *
1.307 + * <p>More precisely, if
1.308 + * <br>{@code long[] longs = s.toLongArray();}
1.309 + * <br>then {@code longs.length == (s.length()+63)/64} and
1.310 + * <br>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
1.311 + * <br>for all {@code n < 64 * longs.length}.
1.312 + *
1.313 + * @return a long array containing a little-endian representation
1.314 + * of all the bits in this bit set
1.315 + * @since 1.7
1.316 + */
1.317 + public long[] toLongArray() {
1.318 + return Arrays.copyOf(words, wordsInUse);
1.319 + }
1.320 +
1.321 + /**
1.322 + * Ensures that the BitSet can hold enough words.
1.323 + * @param wordsRequired the minimum acceptable number of words.
1.324 + */
1.325 + private void ensureCapacity(int wordsRequired) {
1.326 + if (words.length < wordsRequired) {
1.327 + // Allocate larger of doubled size or required size
1.328 + int request = Math.max(2 * words.length, wordsRequired);
1.329 + words = Arrays.copyOf(words, request);
1.330 + sizeIsSticky = false;
1.331 + }
1.332 + }
1.333 +
1.334 + /**
1.335 + * Ensures that the BitSet can accommodate a given wordIndex,
1.336 + * temporarily violating the invariants. The caller must
1.337 + * restore the invariants before returning to the user,
1.338 + * possibly using recalculateWordsInUse().
1.339 + * @param wordIndex the index to be accommodated.
1.340 + */
1.341 + private void expandTo(int wordIndex) {
1.342 + int wordsRequired = wordIndex+1;
1.343 + if (wordsInUse < wordsRequired) {
1.344 + ensureCapacity(wordsRequired);
1.345 + wordsInUse = wordsRequired;
1.346 + }
1.347 + }
1.348 +
1.349 + /**
1.350 + * Checks that fromIndex ... toIndex is a valid range of bit indices.
1.351 + */
1.352 + private static void checkRange(int fromIndex, int toIndex) {
1.353 + if (fromIndex < 0)
1.354 + throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
1.355 + if (toIndex < 0)
1.356 + throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
1.357 + if (fromIndex > toIndex)
1.358 + throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
1.359 + " > toIndex: " + toIndex);
1.360 + }
1.361 +
1.362 + /**
1.363 + * Sets the bit at the specified index to the complement of its
1.364 + * current value.
1.365 + *
1.366 + * @param bitIndex the index of the bit to flip
1.367 + * @throws IndexOutOfBoundsException if the specified index is negative
1.368 + * @since 1.4
1.369 + */
1.370 + public void flip(int bitIndex) {
1.371 + if (bitIndex < 0)
1.372 + throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
1.373 +
1.374 + int wordIndex = wordIndex(bitIndex);
1.375 + expandTo(wordIndex);
1.376 +
1.377 + words[wordIndex] ^= (1L << bitIndex);
1.378 +
1.379 + recalculateWordsInUse();
1.380 + checkInvariants();
1.381 + }
1.382 +
1.383 + /**
1.384 + * Sets each bit from the specified {@code fromIndex} (inclusive) to the
1.385 + * specified {@code toIndex} (exclusive) to the complement of its current
1.386 + * value.
1.387 + *
1.388 + * @param fromIndex index of the first bit to flip
1.389 + * @param toIndex index after the last bit to flip
1.390 + * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
1.391 + * or {@code toIndex} is negative, or {@code fromIndex} is
1.392 + * larger than {@code toIndex}
1.393 + * @since 1.4
1.394 + */
1.395 + public void flip(int fromIndex, int toIndex) {
1.396 + checkRange(fromIndex, toIndex);
1.397 +
1.398 + if (fromIndex == toIndex)
1.399 + return;
1.400 +
1.401 + int startWordIndex = wordIndex(fromIndex);
1.402 + int endWordIndex = wordIndex(toIndex - 1);
1.403 + expandTo(endWordIndex);
1.404 +
1.405 + long firstWordMask = WORD_MASK << fromIndex;
1.406 + long lastWordMask = WORD_MASK >>> -toIndex;
1.407 + if (startWordIndex == endWordIndex) {
1.408 + // Case 1: One word
1.409 + words[startWordIndex] ^= (firstWordMask & lastWordMask);
1.410 + } else {
1.411 + // Case 2: Multiple words
1.412 + // Handle first word
1.413 + words[startWordIndex] ^= firstWordMask;
1.414 +
1.415 + // Handle intermediate words, if any
1.416 + for (int i = startWordIndex+1; i < endWordIndex; i++)
1.417 + words[i] ^= WORD_MASK;
1.418 +
1.419 + // Handle last word
1.420 + words[endWordIndex] ^= lastWordMask;
1.421 + }
1.422 +
1.423 + recalculateWordsInUse();
1.424 + checkInvariants();
1.425 + }
1.426 +
1.427 + /**
1.428 + * Sets the bit at the specified index to {@code true}.
1.429 + *
1.430 + * @param bitIndex a bit index
1.431 + * @throws IndexOutOfBoundsException if the specified index is negative
1.432 + * @since JDK1.0
1.433 + */
1.434 + public void set(int bitIndex) {
1.435 + if (bitIndex < 0)
1.436 + throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
1.437 +
1.438 + int wordIndex = wordIndex(bitIndex);
1.439 + expandTo(wordIndex);
1.440 +
1.441 + words[wordIndex] |= (1L << bitIndex); // Restores invariants
1.442 +
1.443 + checkInvariants();
1.444 + }
1.445 +
1.446 + /**
1.447 + * Sets the bit at the specified index to the specified value.
1.448 + *
1.449 + * @param bitIndex a bit index
1.450 + * @param value a boolean value to set
1.451 + * @throws IndexOutOfBoundsException if the specified index is negative
1.452 + * @since 1.4
1.453 + */
1.454 + public void set(int bitIndex, boolean value) {
1.455 + if (value)
1.456 + set(bitIndex);
1.457 + else
1.458 + clear(bitIndex);
1.459 + }
1.460 +
1.461 + /**
1.462 + * Sets the bits from the specified {@code fromIndex} (inclusive) to the
1.463 + * specified {@code toIndex} (exclusive) to {@code true}.
1.464 + *
1.465 + * @param fromIndex index of the first bit to be set
1.466 + * @param toIndex index after the last bit to be set
1.467 + * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
1.468 + * or {@code toIndex} is negative, or {@code fromIndex} is
1.469 + * larger than {@code toIndex}
1.470 + * @since 1.4
1.471 + */
1.472 + public void set(int fromIndex, int toIndex) {
1.473 + checkRange(fromIndex, toIndex);
1.474 +
1.475 + if (fromIndex == toIndex)
1.476 + return;
1.477 +
1.478 + // Increase capacity if necessary
1.479 + int startWordIndex = wordIndex(fromIndex);
1.480 + int endWordIndex = wordIndex(toIndex - 1);
1.481 + expandTo(endWordIndex);
1.482 +
1.483 + long firstWordMask = WORD_MASK << fromIndex;
1.484 + long lastWordMask = WORD_MASK >>> -toIndex;
1.485 + if (startWordIndex == endWordIndex) {
1.486 + // Case 1: One word
1.487 + words[startWordIndex] |= (firstWordMask & lastWordMask);
1.488 + } else {
1.489 + // Case 2: Multiple words
1.490 + // Handle first word
1.491 + words[startWordIndex] |= firstWordMask;
1.492 +
1.493 + // Handle intermediate words, if any
1.494 + for (int i = startWordIndex+1; i < endWordIndex; i++)
1.495 + words[i] = WORD_MASK;
1.496 +
1.497 + // Handle last word (restores invariants)
1.498 + words[endWordIndex] |= lastWordMask;
1.499 + }
1.500 +
1.501 + checkInvariants();
1.502 + }
1.503 +
1.504 + /**
1.505 + * Sets the bits from the specified {@code fromIndex} (inclusive) to the
1.506 + * specified {@code toIndex} (exclusive) to the specified value.
1.507 + *
1.508 + * @param fromIndex index of the first bit to be set
1.509 + * @param toIndex index after the last bit to be set
1.510 + * @param value value to set the selected bits to
1.511 + * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
1.512 + * or {@code toIndex} is negative, or {@code fromIndex} is
1.513 + * larger than {@code toIndex}
1.514 + * @since 1.4
1.515 + */
1.516 + public void set(int fromIndex, int toIndex, boolean value) {
1.517 + if (value)
1.518 + set(fromIndex, toIndex);
1.519 + else
1.520 + clear(fromIndex, toIndex);
1.521 + }
1.522 +
1.523 + /**
1.524 + * Sets the bit specified by the index to {@code false}.
1.525 + *
1.526 + * @param bitIndex the index of the bit to be cleared
1.527 + * @throws IndexOutOfBoundsException if the specified index is negative
1.528 + * @since JDK1.0
1.529 + */
1.530 + public void clear(int bitIndex) {
1.531 + if (bitIndex < 0)
1.532 + throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
1.533 +
1.534 + int wordIndex = wordIndex(bitIndex);
1.535 + if (wordIndex >= wordsInUse)
1.536 + return;
1.537 +
1.538 + words[wordIndex] &= ~(1L << bitIndex);
1.539 +
1.540 + recalculateWordsInUse();
1.541 + checkInvariants();
1.542 + }
1.543 +
1.544 + /**
1.545 + * Sets the bits from the specified {@code fromIndex} (inclusive) to the
1.546 + * specified {@code toIndex} (exclusive) to {@code false}.
1.547 + *
1.548 + * @param fromIndex index of the first bit to be cleared
1.549 + * @param toIndex index after the last bit to be cleared
1.550 + * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
1.551 + * or {@code toIndex} is negative, or {@code fromIndex} is
1.552 + * larger than {@code toIndex}
1.553 + * @since 1.4
1.554 + */
1.555 + public void clear(int fromIndex, int toIndex) {
1.556 + checkRange(fromIndex, toIndex);
1.557 +
1.558 + if (fromIndex == toIndex)
1.559 + return;
1.560 +
1.561 + int startWordIndex = wordIndex(fromIndex);
1.562 + if (startWordIndex >= wordsInUse)
1.563 + return;
1.564 +
1.565 + int endWordIndex = wordIndex(toIndex - 1);
1.566 + if (endWordIndex >= wordsInUse) {
1.567 + toIndex = length();
1.568 + endWordIndex = wordsInUse - 1;
1.569 + }
1.570 +
1.571 + long firstWordMask = WORD_MASK << fromIndex;
1.572 + long lastWordMask = WORD_MASK >>> -toIndex;
1.573 + if (startWordIndex == endWordIndex) {
1.574 + // Case 1: One word
1.575 + words[startWordIndex] &= ~(firstWordMask & lastWordMask);
1.576 + } else {
1.577 + // Case 2: Multiple words
1.578 + // Handle first word
1.579 + words[startWordIndex] &= ~firstWordMask;
1.580 +
1.581 + // Handle intermediate words, if any
1.582 + for (int i = startWordIndex+1; i < endWordIndex; i++)
1.583 + words[i] = 0;
1.584 +
1.585 + // Handle last word
1.586 + words[endWordIndex] &= ~lastWordMask;
1.587 + }
1.588 +
1.589 + recalculateWordsInUse();
1.590 + checkInvariants();
1.591 + }
1.592 +
1.593 + /**
1.594 + * Sets all of the bits in this BitSet to {@code false}.
1.595 + *
1.596 + * @since 1.4
1.597 + */
1.598 + public void clear() {
1.599 + while (wordsInUse > 0)
1.600 + words[--wordsInUse] = 0;
1.601 + }
1.602 +
1.603 + /**
1.604 + * Returns the value of the bit with the specified index. The value
1.605 + * is {@code true} if the bit with the index {@code bitIndex}
1.606 + * is currently set in this {@code BitSet}; otherwise, the result
1.607 + * is {@code false}.
1.608 + *
1.609 + * @param bitIndex the bit index
1.610 + * @return the value of the bit with the specified index
1.611 + * @throws IndexOutOfBoundsException if the specified index is negative
1.612 + */
1.613 + public boolean get(int bitIndex) {
1.614 + if (bitIndex < 0)
1.615 + throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
1.616 +
1.617 + checkInvariants();
1.618 +
1.619 + int wordIndex = wordIndex(bitIndex);
1.620 + return (wordIndex < wordsInUse)
1.621 + && ((words[wordIndex] & (1L << bitIndex)) != 0);
1.622 + }
1.623 +
1.624 + /**
1.625 + * Returns a new {@code BitSet} composed of bits from this {@code BitSet}
1.626 + * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).
1.627 + *
1.628 + * @param fromIndex index of the first bit to include
1.629 + * @param toIndex index after the last bit to include
1.630 + * @return a new {@code BitSet} from a range of this {@code BitSet}
1.631 + * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
1.632 + * or {@code toIndex} is negative, or {@code fromIndex} is
1.633 + * larger than {@code toIndex}
1.634 + * @since 1.4
1.635 + */
1.636 + public BitSet get(int fromIndex, int toIndex) {
1.637 + checkRange(fromIndex, toIndex);
1.638 +
1.639 + checkInvariants();
1.640 +
1.641 + int len = length();
1.642 +
1.643 + // If no set bits in range return empty bitset
1.644 + if (len <= fromIndex || fromIndex == toIndex)
1.645 + return new BitSet(0);
1.646 +
1.647 + // An optimization
1.648 + if (toIndex > len)
1.649 + toIndex = len;
1.650 +
1.651 + BitSet result = new BitSet(toIndex - fromIndex);
1.652 + int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;
1.653 + int sourceIndex = wordIndex(fromIndex);
1.654 + boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);
1.655 +
1.656 + // Process all words but the last word
1.657 + for (int i = 0; i < targetWords - 1; i++, sourceIndex++)
1.658 + result.words[i] = wordAligned ? words[sourceIndex] :
1.659 + (words[sourceIndex] >>> fromIndex) |
1.660 + (words[sourceIndex+1] << -fromIndex);
1.661 +
1.662 + // Process the last word
1.663 + long lastWordMask = WORD_MASK >>> -toIndex;
1.664 + result.words[targetWords - 1] =
1.665 + ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)
1.666 + ? /* straddles source words */
1.667 + ((words[sourceIndex] >>> fromIndex) |
1.668 + (words[sourceIndex+1] & lastWordMask) << -fromIndex)
1.669 + :
1.670 + ((words[sourceIndex] & lastWordMask) >>> fromIndex);
1.671 +
1.672 + // Set wordsInUse correctly
1.673 + result.wordsInUse = targetWords;
1.674 + result.recalculateWordsInUse();
1.675 + result.checkInvariants();
1.676 +
1.677 + return result;
1.678 + }
1.679 +
1.680 + /**
1.681 + * Returns the index of the first bit that is set to {@code true}
1.682 + * that occurs on or after the specified starting index. If no such
1.683 + * bit exists then {@code -1} is returned.
1.684 + *
1.685 + * <p>To iterate over the {@code true} bits in a {@code BitSet},
1.686 + * use the following loop:
1.687 + *
1.688 + * <pre> {@code
1.689 + * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
1.690 + * // operate on index i here
1.691 + * }}</pre>
1.692 + *
1.693 + * @param fromIndex the index to start checking from (inclusive)
1.694 + * @return the index of the next set bit, or {@code -1} if there
1.695 + * is no such bit
1.696 + * @throws IndexOutOfBoundsException if the specified index is negative
1.697 + * @since 1.4
1.698 + */
1.699 + public int nextSetBit(int fromIndex) {
1.700 + if (fromIndex < 0)
1.701 + throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
1.702 +
1.703 + checkInvariants();
1.704 +
1.705 + int u = wordIndex(fromIndex);
1.706 + if (u >= wordsInUse)
1.707 + return -1;
1.708 +
1.709 + long word = words[u] & (WORD_MASK << fromIndex);
1.710 +
1.711 + while (true) {
1.712 + if (word != 0)
1.713 + return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
1.714 + if (++u == wordsInUse)
1.715 + return -1;
1.716 + word = words[u];
1.717 + }
1.718 + }
1.719 +
1.720 + /**
1.721 + * Returns the index of the first bit that is set to {@code false}
1.722 + * that occurs on or after the specified starting index.
1.723 + *
1.724 + * @param fromIndex the index to start checking from (inclusive)
1.725 + * @return the index of the next clear bit
1.726 + * @throws IndexOutOfBoundsException if the specified index is negative
1.727 + * @since 1.4
1.728 + */
1.729 + public int nextClearBit(int fromIndex) {
1.730 + // Neither spec nor implementation handle bitsets of maximal length.
1.731 + // See 4816253.
1.732 + if (fromIndex < 0)
1.733 + throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
1.734 +
1.735 + checkInvariants();
1.736 +
1.737 + int u = wordIndex(fromIndex);
1.738 + if (u >= wordsInUse)
1.739 + return fromIndex;
1.740 +
1.741 + long word = ~words[u] & (WORD_MASK << fromIndex);
1.742 +
1.743 + while (true) {
1.744 + if (word != 0)
1.745 + return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
1.746 + if (++u == wordsInUse)
1.747 + return wordsInUse * BITS_PER_WORD;
1.748 + word = ~words[u];
1.749 + }
1.750 + }
1.751 +
1.752 + /**
1.753 + * Returns the index of the nearest bit that is set to {@code true}
1.754 + * that occurs on or before the specified starting index.
1.755 + * If no such bit exists, or if {@code -1} is given as the
1.756 + * starting index, then {@code -1} is returned.
1.757 + *
1.758 + * <p>To iterate over the {@code true} bits in a {@code BitSet},
1.759 + * use the following loop:
1.760 + *
1.761 + * <pre> {@code
1.762 + * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
1.763 + * // operate on index i here
1.764 + * }}</pre>
1.765 + *
1.766 + * @param fromIndex the index to start checking from (inclusive)
1.767 + * @return the index of the previous set bit, or {@code -1} if there
1.768 + * is no such bit
1.769 + * @throws IndexOutOfBoundsException if the specified index is less
1.770 + * than {@code -1}
1.771 + * @since 1.7
1.772 + */
1.773 + public int previousSetBit(int fromIndex) {
1.774 + if (fromIndex < 0) {
1.775 + if (fromIndex == -1)
1.776 + return -1;
1.777 + throw new IndexOutOfBoundsException(
1.778 + "fromIndex < -1: " + fromIndex);
1.779 + }
1.780 +
1.781 + checkInvariants();
1.782 +
1.783 + int u = wordIndex(fromIndex);
1.784 + if (u >= wordsInUse)
1.785 + return length() - 1;
1.786 +
1.787 + long word = words[u] & (WORD_MASK >>> -(fromIndex+1));
1.788 +
1.789 + while (true) {
1.790 + if (word != 0)
1.791 + return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
1.792 + if (u-- == 0)
1.793 + return -1;
1.794 + word = words[u];
1.795 + }
1.796 + }
1.797 +
1.798 + /**
1.799 + * Returns the index of the nearest bit that is set to {@code false}
1.800 + * that occurs on or before the specified starting index.
1.801 + * If no such bit exists, or if {@code -1} is given as the
1.802 + * starting index, then {@code -1} is returned.
1.803 + *
1.804 + * @param fromIndex the index to start checking from (inclusive)
1.805 + * @return the index of the previous clear bit, or {@code -1} if there
1.806 + * is no such bit
1.807 + * @throws IndexOutOfBoundsException if the specified index is less
1.808 + * than {@code -1}
1.809 + * @since 1.7
1.810 + */
1.811 + public int previousClearBit(int fromIndex) {
1.812 + if (fromIndex < 0) {
1.813 + if (fromIndex == -1)
1.814 + return -1;
1.815 + throw new IndexOutOfBoundsException(
1.816 + "fromIndex < -1: " + fromIndex);
1.817 + }
1.818 +
1.819 + checkInvariants();
1.820 +
1.821 + int u = wordIndex(fromIndex);
1.822 + if (u >= wordsInUse)
1.823 + return fromIndex;
1.824 +
1.825 + long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1));
1.826 +
1.827 + while (true) {
1.828 + if (word != 0)
1.829 + return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);
1.830 + if (u-- == 0)
1.831 + return -1;
1.832 + word = ~words[u];
1.833 + }
1.834 + }
1.835 +
1.836 + /**
1.837 + * Returns the "logical size" of this {@code BitSet}: the index of
1.838 + * the highest set bit in the {@code BitSet} plus one. Returns zero
1.839 + * if the {@code BitSet} contains no set bits.
1.840 + *
1.841 + * @return the logical size of this {@code BitSet}
1.842 + * @since 1.2
1.843 + */
1.844 + public int length() {
1.845 + if (wordsInUse == 0)
1.846 + return 0;
1.847 +
1.848 + return BITS_PER_WORD * (wordsInUse - 1) +
1.849 + (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
1.850 + }
1.851 +
1.852 + /**
1.853 + * Returns true if this {@code BitSet} contains no bits that are set
1.854 + * to {@code true}.
1.855 + *
1.856 + * @return boolean indicating whether this {@code BitSet} is empty
1.857 + * @since 1.4
1.858 + */
1.859 + public boolean isEmpty() {
1.860 + return wordsInUse == 0;
1.861 + }
1.862 +
1.863 + /**
1.864 + * Returns true if the specified {@code BitSet} has any bits set to
1.865 + * {@code true} that are also set to {@code true} in this {@code BitSet}.
1.866 + *
1.867 + * @param set {@code BitSet} to intersect with
1.868 + * @return boolean indicating whether this {@code BitSet} intersects
1.869 + * the specified {@code BitSet}
1.870 + * @since 1.4
1.871 + */
1.872 + public boolean intersects(BitSet set) {
1.873 + for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
1.874 + if ((words[i] & set.words[i]) != 0)
1.875 + return true;
1.876 + return false;
1.877 + }
1.878 +
1.879 + /**
1.880 + * Returns the number of bits set to {@code true} in this {@code BitSet}.
1.881 + *
1.882 + * @return the number of bits set to {@code true} in this {@code BitSet}
1.883 + * @since 1.4
1.884 + */
1.885 + public int cardinality() {
1.886 + int sum = 0;
1.887 + for (int i = 0; i < wordsInUse; i++)
1.888 + sum += Long.bitCount(words[i]);
1.889 + return sum;
1.890 + }
1.891 +
1.892 + /**
1.893 + * Performs a logical <b>AND</b> of this target bit set with the
1.894 + * argument bit set. This bit set is modified so that each bit in it
1.895 + * has the value {@code true} if and only if it both initially
1.896 + * had the value {@code true} and the corresponding bit in the
1.897 + * bit set argument also had the value {@code true}.
1.898 + *
1.899 + * @param set a bit set
1.900 + */
1.901 + public void and(BitSet set) {
1.902 + if (this == set)
1.903 + return;
1.904 +
1.905 + while (wordsInUse > set.wordsInUse)
1.906 + words[--wordsInUse] = 0;
1.907 +
1.908 + // Perform logical AND on words in common
1.909 + for (int i = 0; i < wordsInUse; i++)
1.910 + words[i] &= set.words[i];
1.911 +
1.912 + recalculateWordsInUse();
1.913 + checkInvariants();
1.914 + }
1.915 +
1.916 + /**
1.917 + * Performs a logical <b>OR</b> of this bit set with the bit set
1.918 + * argument. This bit set is modified so that a bit in it has the
1.919 + * value {@code true} if and only if it either already had the
1.920 + * value {@code true} or the corresponding bit in the bit set
1.921 + * argument has the value {@code true}.
1.922 + *
1.923 + * @param set a bit set
1.924 + */
1.925 + public void or(BitSet set) {
1.926 + if (this == set)
1.927 + return;
1.928 +
1.929 + int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
1.930 +
1.931 + if (wordsInUse < set.wordsInUse) {
1.932 + ensureCapacity(set.wordsInUse);
1.933 + wordsInUse = set.wordsInUse;
1.934 + }
1.935 +
1.936 + // Perform logical OR on words in common
1.937 + for (int i = 0; i < wordsInCommon; i++)
1.938 + words[i] |= set.words[i];
1.939 +
1.940 + // Copy any remaining words
1.941 + if (wordsInCommon < set.wordsInUse)
1.942 + System.arraycopy(set.words, wordsInCommon,
1.943 + words, wordsInCommon,
1.944 + wordsInUse - wordsInCommon);
1.945 +
1.946 + // recalculateWordsInUse() is unnecessary
1.947 + checkInvariants();
1.948 + }
1.949 +
1.950 + /**
1.951 + * Performs a logical <b>XOR</b> of this bit set with the bit set
1.952 + * argument. This bit set is modified so that a bit in it has the
1.953 + * value {@code true} if and only if one of the following
1.954 + * statements holds:
1.955 + * <ul>
1.956 + * <li>The bit initially has the value {@code true}, and the
1.957 + * corresponding bit in the argument has the value {@code false}.
1.958 + * <li>The bit initially has the value {@code false}, and the
1.959 + * corresponding bit in the argument has the value {@code true}.
1.960 + * </ul>
1.961 + *
1.962 + * @param set a bit set
1.963 + */
1.964 + public void xor(BitSet set) {
1.965 + int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
1.966 +
1.967 + if (wordsInUse < set.wordsInUse) {
1.968 + ensureCapacity(set.wordsInUse);
1.969 + wordsInUse = set.wordsInUse;
1.970 + }
1.971 +
1.972 + // Perform logical XOR on words in common
1.973 + for (int i = 0; i < wordsInCommon; i++)
1.974 + words[i] ^= set.words[i];
1.975 +
1.976 + // Copy any remaining words
1.977 + if (wordsInCommon < set.wordsInUse)
1.978 + System.arraycopy(set.words, wordsInCommon,
1.979 + words, wordsInCommon,
1.980 + set.wordsInUse - wordsInCommon);
1.981 +
1.982 + recalculateWordsInUse();
1.983 + checkInvariants();
1.984 + }
1.985 +
1.986 + /**
1.987 + * Clears all of the bits in this {@code BitSet} whose corresponding
1.988 + * bit is set in the specified {@code BitSet}.
1.989 + *
1.990 + * @param set the {@code BitSet} with which to mask this
1.991 + * {@code BitSet}
1.992 + * @since 1.2
1.993 + */
1.994 + public void andNot(BitSet set) {
1.995 + // Perform logical (a & !b) on words in common
1.996 + for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
1.997 + words[i] &= ~set.words[i];
1.998 +
1.999 + recalculateWordsInUse();
1.1000 + checkInvariants();
1.1001 + }
1.1002 +
1.1003 + /**
1.1004 + * Returns the hash code value for this bit set. The hash code depends
1.1005 + * only on which bits are set within this {@code BitSet}.
1.1006 + *
1.1007 + * <p>The hash code is defined to be the result of the following
1.1008 + * calculation:
1.1009 + * <pre> {@code
1.1010 + * public int hashCode() {
1.1011 + * long h = 1234;
1.1012 + * long[] words = toLongArray();
1.1013 + * for (int i = words.length; --i >= 0; )
1.1014 + * h ^= words[i] * (i + 1);
1.1015 + * return (int)((h >> 32) ^ h);
1.1016 + * }}</pre>
1.1017 + * Note that the hash code changes if the set of bits is altered.
1.1018 + *
1.1019 + * @return the hash code value for this bit set
1.1020 + */
1.1021 + public int hashCode() {
1.1022 + long h = 1234;
1.1023 + for (int i = wordsInUse; --i >= 0; )
1.1024 + h ^= words[i] * (i + 1);
1.1025 +
1.1026 + return (int)((h >> 32) ^ h);
1.1027 + }
1.1028 +
1.1029 + /**
1.1030 + * Returns the number of bits of space actually in use by this
1.1031 + * {@code BitSet} to represent bit values.
1.1032 + * The maximum element in the set is the size - 1st element.
1.1033 + *
1.1034 + * @return the number of bits currently in this bit set
1.1035 + */
1.1036 + public int size() {
1.1037 + return words.length * BITS_PER_WORD;
1.1038 + }
1.1039 +
1.1040 + /**
1.1041 + * Compares this object against the specified object.
1.1042 + * The result is {@code true} if and only if the argument is
1.1043 + * not {@code null} and is a {@code Bitset} object that has
1.1044 + * exactly the same set of bits set to {@code true} as this bit
1.1045 + * set. That is, for every nonnegative {@code int} index {@code k},
1.1046 + * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
1.1047 + * must be true. The current sizes of the two bit sets are not compared.
1.1048 + *
1.1049 + * @param obj the object to compare with
1.1050 + * @return {@code true} if the objects are the same;
1.1051 + * {@code false} otherwise
1.1052 + * @see #size()
1.1053 + */
1.1054 + public boolean equals(Object obj) {
1.1055 + if (!(obj instanceof BitSet))
1.1056 + return false;
1.1057 + if (this == obj)
1.1058 + return true;
1.1059 +
1.1060 + BitSet set = (BitSet) obj;
1.1061 +
1.1062 + checkInvariants();
1.1063 + set.checkInvariants();
1.1064 +
1.1065 + if (wordsInUse != set.wordsInUse)
1.1066 + return false;
1.1067 +
1.1068 + // Check words in use by both BitSets
1.1069 + for (int i = 0; i < wordsInUse; i++)
1.1070 + if (words[i] != set.words[i])
1.1071 + return false;
1.1072 +
1.1073 + return true;
1.1074 + }
1.1075 +
1.1076 + /**
1.1077 + * Cloning this {@code BitSet} produces a new {@code BitSet}
1.1078 + * that is equal to it.
1.1079 + * The clone of the bit set is another bit set that has exactly the
1.1080 + * same bits set to {@code true} as this bit set.
1.1081 + *
1.1082 + * @return a clone of this bit set
1.1083 + * @see #size()
1.1084 + */
1.1085 + public Object clone() {
1.1086 + if (! sizeIsSticky)
1.1087 + trimToSize();
1.1088 +
1.1089 + try {
1.1090 + BitSet result = (BitSet) super.clone();
1.1091 + result.words = words.clone();
1.1092 + result.checkInvariants();
1.1093 + return result;
1.1094 + } catch (CloneNotSupportedException e) {
1.1095 + throw new InternalError();
1.1096 + }
1.1097 + }
1.1098 +
1.1099 + /**
1.1100 + * Attempts to reduce internal storage used for the bits in this bit set.
1.1101 + * Calling this method may, but is not required to, affect the value
1.1102 + * returned by a subsequent call to the {@link #size()} method.
1.1103 + */
1.1104 + private void trimToSize() {
1.1105 + if (wordsInUse != words.length) {
1.1106 + words = Arrays.copyOf(words, wordsInUse);
1.1107 + checkInvariants();
1.1108 + }
1.1109 + }
1.1110 +
1.1111 + /**
1.1112 + * Save the state of the {@code BitSet} instance to a stream (i.e.,
1.1113 + * serialize it).
1.1114 + */
1.1115 + private void writeObject(ObjectOutputStream s)
1.1116 + throws IOException {
1.1117 +
1.1118 + checkInvariants();
1.1119 +
1.1120 + if (! sizeIsSticky)
1.1121 + trimToSize();
1.1122 +
1.1123 + ObjectOutputStream.PutField fields = s.putFields();
1.1124 + fields.put("bits", words);
1.1125 + s.writeFields();
1.1126 + }
1.1127 +
1.1128 + /**
1.1129 + * Reconstitute the {@code BitSet} instance from a stream (i.e.,
1.1130 + * deserialize it).
1.1131 + */
1.1132 + private void readObject(ObjectInputStream s)
1.1133 + throws IOException, ClassNotFoundException {
1.1134 +
1.1135 + ObjectInputStream.GetField fields = s.readFields();
1.1136 + words = (long[]) fields.get("bits", null);
1.1137 +
1.1138 + // Assume maximum length then find real length
1.1139 + // because recalculateWordsInUse assumes maintenance
1.1140 + // or reduction in logical size
1.1141 + wordsInUse = words.length;
1.1142 + recalculateWordsInUse();
1.1143 + sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic
1.1144 + checkInvariants();
1.1145 + }
1.1146 +
1.1147 + /**
1.1148 + * Returns a string representation of this bit set. For every index
1.1149 + * for which this {@code BitSet} contains a bit in the set
1.1150 + * state, the decimal representation of that index is included in
1.1151 + * the result. Such indices are listed in order from lowest to
1.1152 + * highest, separated by ", " (a comma and a space) and
1.1153 + * surrounded by braces, resulting in the usual mathematical
1.1154 + * notation for a set of integers.
1.1155 + *
1.1156 + * <p>Example:
1.1157 + * <pre>
1.1158 + * BitSet drPepper = new BitSet();</pre>
1.1159 + * Now {@code drPepper.toString()} returns "{@code {}}".<p>
1.1160 + * <pre>
1.1161 + * drPepper.set(2);</pre>
1.1162 + * Now {@code drPepper.toString()} returns "{@code {2}}".<p>
1.1163 + * <pre>
1.1164 + * drPepper.set(4);
1.1165 + * drPepper.set(10);</pre>
1.1166 + * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
1.1167 + *
1.1168 + * @return a string representation of this bit set
1.1169 + */
1.1170 + public String toString() {
1.1171 + checkInvariants();
1.1172 +
1.1173 + int numBits = (wordsInUse > 128) ?
1.1174 + cardinality() : wordsInUse * BITS_PER_WORD;
1.1175 + StringBuilder b = new StringBuilder(6*numBits + 2);
1.1176 + b.append('{');
1.1177 +
1.1178 + int i = nextSetBit(0);
1.1179 + if (i != -1) {
1.1180 + b.append(i);
1.1181 + for (i = nextSetBit(i+1); i >= 0; i = nextSetBit(i+1)) {
1.1182 + int endOfRun = nextClearBit(i);
1.1183 + do { b.append(", ").append(i); }
1.1184 + while (++i < endOfRun);
1.1185 + }
1.1186 + }
1.1187 +
1.1188 + b.append('}');
1.1189 + return b.toString();
1.1190 + }
1.1191 +}