Brinding in BitSet
authorJaroslav Tulach <jtulach@netbeans.org>
Thu, 31 Oct 2013 11:30:50 +0100
changeset 1400a0690c970a4d
parent 1398 9926996eca2d
parent 1399 07587a260d68
child 1401 9aeb2a41e009
Brinding in BitSet
     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:50 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 ",&nbsp;" (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 +}