/*

 * Copyright (c) 1995, 2007, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package java.util;

import java.io.*;

/**

 * This class implements a vector of bits that grows as needed. Each

 * component of the bit set has a {@code boolean} value. The

 * bits of a {@code BitSet} are indexed by nonnegative integers.

 * Individual indexed bits can be examined, set, or cleared. One

 * {@code BitSet} may be used to modify the contents of another

 * {@code BitSet} through logical AND, logical inclusive OR, and

 * logical exclusive OR operations.

 *

 * <p>By default, all bits in the set initially have the value

 * {@code false}.

 *

 * <p>Every bit set has a current size, which is the number of bits

 * of space currently in use by the bit set. Note that the size is

 * related to the implementation of a bit set, so it may change with

 * implementation. The length of a bit set relates to logical length

 * of a bit set and is defined independently of implementation.

 *

 * <p>Unless otherwise noted, passing a null parameter to any of the

 * methods in a {@code BitSet} will result in a

 * {@code NullPointerException}.

 *

 * <p>A {@code BitSet} is not safe for multithreaded use without

 * external synchronization.

 *

 * @author  Arthur van Hoff

 * @author  Michael McCloskey

 * @author  Martin Buchholz

 * @since   JDK1.0

 */

public class BitSet implements Cloneable, java.io.Serializable {

    /*

     * BitSets are packed into arrays of "words."  Currently a word is

     * a long, which consists of 64 bits, requiring 6 address bits.

     * The choice of word size is determined purely by performance concerns.

     */

    private final static int ADDRESS_BITS_PER_WORD = 6;

    private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;

    private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;

    /* Used to shift left or right for a partial word mask */

    private static final long WORD_MASK = 0xffffffffffffffffL;

    /**

     * @serialField bits long[]

     *

     * The bits in this BitSet.  The ith bit is stored in bits[i/64] at

     * bit position i % 64 (where bit position 0 refers to the least

     * significant bit and 63 refers to the most significant bit).

     */

    private static final ObjectStreamField[] serialPersistentFields = {

        new ObjectStreamField("bits", long[].class),

    };

    /**

     * The internal field corresponding to the serialField "bits".

     */

    private long[] words;

    /**

     * The number of words in the logical size of this BitSet.

     */

    private transient int wordsInUse = 0;

    /**

     * Whether the size of "words" is user-specified.  If so, we assume

     * the user knows what he's doing and try harder to preserve it.

     */

    private transient boolean sizeIsSticky = false;

    /* use serialVersionUID from JDK 1.0.2 for interoperability */

    private static final long serialVersionUID = 7997698588986878753L;

    /**

     * Given a bit index, return word index containing it.

     */

    private static int wordIndex(int bitIndex) {

        return bitIndex >> ADDRESS_BITS_PER_WORD;

    }

    /**

     * Every public method must preserve these invariants.

     */

    private void checkInvariants() {

        assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);

        assert(wordsInUse >= 0 && wordsInUse <= words.length);

        assert(wordsInUse == words.length || words[wordsInUse] == 0);

    }

    /**

     * Sets the field wordsInUse to the logical size in words of the bit set.

     * WARNING:This method assumes that the number of words actually in use is

     * less than or equal to the current value of wordsInUse!

     */

    private void recalculateWordsInUse() {

        // Traverse the bitset until a used word is found

        int i;

        for (i = wordsInUse-1; i >= 0; i--)

            if (words[i] != 0)

                break;

        wordsInUse = i+1; // The new logical size

    }

    /**

     * Creates a new bit set. All bits are initially {@code false}.

     */

    public BitSet() {

        initWords(BITS_PER_WORD);

        sizeIsSticky = false;

    }

    /**

     * Creates a bit set whose initial size is large enough to explicitly

     * represent bits with indices in the range {@code 0} through

     * {@code nbits-1}. All bits are initially {@code false}.

     *

     * @param  nbits the initial size of the bit set

     * @throws NegativeArraySizeException if the specified initial size

     *         is negative

     */

    public BitSet(int nbits) {

        // nbits can't be negative; size 0 is OK

        if (nbits < 0)

            throw new NegativeArraySizeException("nbits < 0: " + nbits);

        initWords(nbits);

        sizeIsSticky = true;

    }

    private void initWords(int nbits) {

        words = new long[wordIndex(nbits-1) + 1];

    }

    /**

     * Creates a bit set using words as the internal representation.

     * The last word (if there is one) must be non-zero.

     */

    private BitSet(long[] words) {

        this.words = words;

        this.wordsInUse = words.length;

        checkInvariants();

    }

    /**

     * Returns a new bit set containing all the bits in the given long array.

     *

     * <p>More precisely,

     * <br>{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}

     * <br>for all {@code n < 64 * longs.length}.

     *

     * <p>This method is equivalent to

     * {@code BitSet.valueOf(LongBuffer.wrap(longs))}.

     *

     * @param longs a long array containing a little-endian representation

     *        of a sequence of bits to be used as the initial bits of the

     *        new bit set

     * @since 1.7

     */

    public static BitSet valueOf(long[] longs) {

        int n;

        for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)

            ;

        return new BitSet(Arrays.copyOf(longs, n));

    }

    /**

     * Returns a new bit set containing all the bits in the given long

     * buffer between its position and limit.

     *

     * <p>More precisely,

     * <br>{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)}

     * <br>for all {@code n < 64 * lb.remaining()}.

     *

     * <p>The long buffer is not modified by this method, and no

     * reference to the buffer is retained by the bit set.

     *

     * @param lb a long buffer containing a little-endian representation

     *        of a sequence of bits between its position and limit, to be

     *        used as the initial bits of the new bit set

     * @since 1.7

     */

//    public static BitSet valueOf(LongBuffer lb) {

//        lb = lb.slice();

//        int n;

//        for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)

//            ;

//        long[] words = new long[n];

//        lb.get(words);

//        return new BitSet(words);

//    }

    /**

     * Returns a new bit set containing all the bits in the given byte array.

     *

     * <p>More precisely,

     * <br>{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}

     * <br>for all {@code n <  8 * bytes.length}.

     *

     * <p>This method is equivalent to

     * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}.

     *

     * @param bytes a byte array containing a little-endian

     *        representation of a sequence of bits to be used as the

     *        initial bits of the new bit set

     * @since 1.7

     */

//    public static BitSet valueOf(byte[] bytes) {

//        return BitSet.valueOf(ByteBuffer.wrap(bytes));

//    }

    /**

     * Returns a new bit set containing all the bits in the given byte

     * buffer between its position and limit.

     *

     * <p>More precisely,

     * <br>{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)}

     * <br>for all {@code n < 8 * bb.remaining()}.

     *

     * <p>The byte buffer is not modified by this method, and no

     * reference to the buffer is retained by the bit set.

     *

     * @param bb a byte buffer containing a little-endian representation

     *        of a sequence of bits between its position and limit, to be

     *        used as the initial bits of the new bit set

     * @since 1.7

     */

//    public static BitSet valueOf(ByteBuffer bb) {

//        bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);

//        int n;

//        for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--)

//            ;

//        long[] words = new long[(n + 7) / 8];

//        bb.limit(n);

//        int i = 0;

//        while (bb.remaining() >= 8)

//            words[i++] = bb.getLong();

//        for (int remaining = bb.remaining(), j = 0; j < remaining; j++)

//            words[i] |= (bb.get() & 0xffL) << (8 * j);

//        return new BitSet(words);

//    }

    /**

     * Returns a new byte array containing all the bits in this bit set.

     *

     * <p>More precisely, if

     * <br>{@code byte[] bytes = s.toByteArray();}

     * <br>then {@code bytes.length == (s.length()+7)/8} and

     * <br>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}

     * <br>for all {@code n < 8 * bytes.length}.

     *

     * @return a byte array containing a little-endian representation

     *         of all the bits in this bit set

     * @since 1.7

    */

//    public byte[] toByteArray() {

//        int n = wordsInUse;

//        if (n == 0)

//            return new byte[0];

//        int len = 8 * (n-1);

//        for (long x = words[n - 1]; x != 0; x >>>= 8)

//            len++;

//        byte[] bytes = new byte[len];

//        ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);

//        for (int i = 0; i < n - 1; i++)

//            bb.putLong(words[i]);

//        for (long x = words[n - 1]; x != 0; x >>>= 8)

//            bb.put((byte) (x & 0xff));

//        return bytes;

//    }

    /**

     * Returns a new long array containing all the bits in this bit set.

     *

     * <p>More precisely, if

     * <br>{@code long[] longs = s.toLongArray();}

     * <br>then {@code longs.length == (s.length()+63)/64} and

     * <br>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}

     * <br>for all {@code n < 64 * longs.length}.

     *

     * @return a long array containing a little-endian representation

     *         of all the bits in this bit set

     * @since 1.7

    */

    public long[] toLongArray() {

        return Arrays.copyOf(words, wordsInUse);

    }

    /**

     * Ensures that the BitSet can hold enough words.

     * @param wordsRequired the minimum acceptable number of words.

     */

    private void ensureCapacity(int wordsRequired) {

        if (words.length < wordsRequired) {

            // Allocate larger of doubled size or required size

            int request = Math.max(2 * words.length, wordsRequired);

            words = Arrays.copyOf(words, request);

            sizeIsSticky = false;

        }

    }

    /**

     * Ensures that the BitSet can accommodate a given wordIndex,

     * temporarily violating the invariants.  The caller must

     * restore the invariants before returning to the user,

     * possibly using recalculateWordsInUse().

     * @param wordIndex the index to be accommodated.

     */

    private void expandTo(int wordIndex) {

        int wordsRequired = wordIndex+1;

        if (wordsInUse < wordsRequired) {

            ensureCapacity(wordsRequired);

            wordsInUse = wordsRequired;

        }

    }

    /**

     * Checks that fromIndex ... toIndex is a valid range of bit indices.

     */

    private static void checkRange(int fromIndex, int toIndex) {

        if (fromIndex < 0)

            throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

        if (toIndex < 0)

            throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);

        if (fromIndex > toIndex)

            throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +

                                                " > toIndex: " + toIndex);

    }

    /**

     * Sets the bit at the specified index to the complement of its

     * current value.

     *

     * @param  bitIndex the index of the bit to flip

     * @throws IndexOutOfBoundsException if the specified index is negative

     * @since  1.4

     */

    public void flip(int bitIndex) {

        if (bitIndex < 0)

            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        int wordIndex = wordIndex(bitIndex);

        expandTo(wordIndex);

        words[wordIndex] ^= (1L << bitIndex);

        recalculateWordsInUse();

        checkInvariants();

    }

    /**

     * Sets each bit from the specified {@code fromIndex} (inclusive) to the

     * specified {@code toIndex} (exclusive) to the complement of its current

     * value.

     *

     * @param  fromIndex index of the first bit to flip

     * @param  toIndex index after the last bit to flip

     * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,

     *         or {@code toIndex} is negative, or {@code fromIndex} is

     *         larger than {@code toIndex}

     * @since  1.4

     */

    public void flip(int fromIndex, int toIndex) {

        checkRange(fromIndex, toIndex);

        if (fromIndex == toIndex)

            return;

        int startWordIndex = wordIndex(fromIndex);

        int endWordIndex   = wordIndex(toIndex - 1);

        expandTo(endWordIndex);

        long firstWordMask = WORD_MASK << fromIndex;

        long lastWordMask  = WORD_MASK >>> -toIndex;

        if (startWordIndex == endWordIndex) {

            // Case 1: One word

            words[startWordIndex] ^= (firstWordMask & lastWordMask);

        } else {

            // Case 2: Multiple words

            // Handle first word

            words[startWordIndex] ^= firstWordMask;

            // Handle intermediate words, if any

            for (int i = startWordIndex+1; i < endWordIndex; i++)

                words[i] ^= WORD_MASK;

            // Handle last word

            words[endWordIndex] ^= lastWordMask;

        }

        recalculateWordsInUse();

        checkInvariants();

    }

    /**

     * Sets the bit at the specified index to {@code true}.

     *

     * @param  bitIndex a bit index

     * @throws IndexOutOfBoundsException if the specified index is negative

     * @since  JDK1.0

     */

    public void set(int bitIndex) {

        if (bitIndex < 0)

            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        int wordIndex = wordIndex(bitIndex);

        expandTo(wordIndex);

        words[wordIndex] |= (1L << bitIndex); // Restores invariants

        checkInvariants();

    }

    /**

     * Sets the bit at the specified index to the specified value.

     *

     * @param  bitIndex a bit index

     * @param  value a boolean value to set

     * @throws IndexOutOfBoundsException if the specified index is negative

     * @since  1.4

     */

    public void set(int bitIndex, boolean value) {

        if (value)

            set(bitIndex);

        else

            clear(bitIndex);

    }

    /**

     * Sets the bits from the specified {@code fromIndex} (inclusive) to the

     * specified {@code toIndex} (exclusive) to {@code true}.

     *

     * @param  fromIndex index of the first bit to be set

     * @param  toIndex index after the last bit to be set

     * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,

     *         or {@code toIndex} is negative, or {@code fromIndex} is

     *         larger than {@code toIndex}

     * @since  1.4

     */

    public void set(int fromIndex, int toIndex) {

        checkRange(fromIndex, toIndex);

        if (fromIndex == toIndex)

            return;

        // Increase capacity if necessary

        int startWordIndex = wordIndex(fromIndex);

        int endWordIndex   = wordIndex(toIndex - 1);

        expandTo(endWordIndex);

        long firstWordMask = WORD_MASK << fromIndex;

        long lastWordMask  = WORD_MASK >>> -toIndex;

        if (startWordIndex == endWordIndex) {

            // Case 1: One word

            words[startWordIndex] |= (firstWordMask & lastWordMask);

        } else {

            // Case 2: Multiple words

            // Handle first word

            words[startWordIndex] |= firstWordMask;

            // Handle intermediate words, if any

            for (int i = startWordIndex+1; i < endWordIndex; i++)

                words[i] = WORD_MASK;

            // Handle last word (restores invariants)

            words[endWordIndex] |= lastWordMask;

        }

        checkInvariants();

    }

    /**

     * Sets the bits from the specified {@code fromIndex} (inclusive) to the

     * specified {@code toIndex} (exclusive) to the specified value.

     *

     * @param  fromIndex index of the first bit to be set

     * @param  toIndex index after the last bit to be set

     * @param  value value to set the selected bits to

     * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,

     *         or {@code toIndex} is negative, or {@code fromIndex} is

     *         larger than {@code toIndex}

     * @since  1.4

     */

    public void set(int fromIndex, int toIndex, boolean value) {

        if (value)

            set(fromIndex, toIndex);

        else

            clear(fromIndex, toIndex);

    }

    /**

     * Sets the bit specified by the index to {@code false}.

     *

     * @param  bitIndex the index of the bit to be cleared

     * @throws IndexOutOfBoundsException if the specified index is negative

     * @since  JDK1.0

     */

    public void clear(int bitIndex) {

        if (bitIndex < 0)

            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        int wordIndex = wordIndex(bitIndex);

        if (wordIndex >= wordsInUse)

            return;

        words[wordIndex] &= ~(1L << bitIndex);

        recalculateWordsInUse();

        checkInvariants();

    }

    /**

     * Sets the bits from the specified {@code fromIndex} (inclusive) to the

     * specified {@code toIndex} (exclusive) to {@code false}.

     *

     * @param  fromIndex index of the first bit to be cleared

     * @param  toIndex index after the last bit to be cleared

     * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,

     *         or {@code toIndex} is negative, or {@code fromIndex} is

     *         larger than {@code toIndex}

     * @since  1.4

     */

    public void clear(int fromIndex, int toIndex) {

        checkRange(fromIndex, toIndex);

        if (fromIndex == toIndex)

            return;

        int startWordIndex = wordIndex(fromIndex);

        if (startWordIndex >= wordsInUse)

            return;

        int endWordIndex = wordIndex(toIndex - 1);

        if (endWordIndex >= wordsInUse) {

            toIndex = length();

            endWordIndex = wordsInUse - 1;

        }

        long firstWordMask = WORD_MASK << fromIndex;

        long lastWordMask  = WORD_MASK >>> -toIndex;

        if (startWordIndex == endWordIndex) {

            // Case 1: One word

            words[startWordIndex] &= ~(firstWordMask & lastWordMask);

        } else {

            // Case 2: Multiple words

            // Handle first word

            words[startWordIndex] &= ~firstWordMask;

            // Handle intermediate words, if any

            for (int i = startWordIndex+1; i < endWordIndex; i++)

                words[i] = 0;

            // Handle last word

            words[endWordIndex] &= ~lastWordMask;

        }

        recalculateWordsInUse();

        checkInvariants();

    }

    /**

     * Sets all of the bits in this BitSet to {@code false}.

     *

     * @since 1.4

     */

    public void clear() {

        while (wordsInUse > 0)

            words[--wordsInUse] = 0;

    }

    /**

     * Returns the value of the bit with the specified index. The value

     * is {@code true} if the bit with the index {@code bitIndex}

     * is currently set in this {@code BitSet}; otherwise, the result

     * is {@code false}.

     *

     * @param  bitIndex   the bit index

     * @return the value of the bit with the specified index

     * @throws IndexOutOfBoundsException if the specified index is negative

     */

    public boolean get(int bitIndex) {

        if (bitIndex < 0)

            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        checkInvariants();

        int wordIndex = wordIndex(bitIndex);

        return (wordIndex < wordsInUse)

            && ((words[wordIndex] & (1L << bitIndex)) != 0);

    }

    /**

     * Returns a new {@code BitSet} composed of bits from this {@code BitSet}

     * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).

     *

     * @param  fromIndex index of the first bit to include

     * @param  toIndex index after the last bit to include

     * @return a new {@code BitSet} from a range of this {@code BitSet}

     * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,

     *         or {@code toIndex} is negative, or {@code fromIndex} is

     *         larger than {@code toIndex}

     * @since  1.4

     */

    public BitSet get(int fromIndex, int toIndex) {

        checkRange(fromIndex, toIndex);

        checkInvariants();

        int len = length();

        // If no set bits in range return empty bitset

        if (len <= fromIndex || fromIndex == toIndex)

            return new BitSet(0);

        // An optimization

        if (toIndex > len)

            toIndex = len;

        BitSet result = new BitSet(toIndex - fromIndex);

        int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;

        int sourceIndex = wordIndex(fromIndex);

        boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);

        // Process all words but the last word

        for (int i = 0; i < targetWords - 1; i++, sourceIndex++)

            result.words[i] = wordAligned ? words[sourceIndex] :

                (words[sourceIndex] >>> fromIndex) |

                (words[sourceIndex+1] << -fromIndex);

        // Process the last word

        long lastWordMask = WORD_MASK >>> -toIndex;

        result.words[targetWords - 1] =

            ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)

            ? /* straddles source words */

            ((words[sourceIndex] >>> fromIndex) |

             (words[sourceIndex+1] & lastWordMask) << -fromIndex)

            :

            ((words[sourceIndex] & lastWordMask) >>> fromIndex);

        // Set wordsInUse correctly

        result.wordsInUse = targetWords;

        result.recalculateWordsInUse();

        result.checkInvariants();

        return result;

    }

    /**

     * Returns the index of the first bit that is set to {@code true}

     * that occurs on or after the specified starting index. If no such

     * bit exists then {@code -1} is returned.

     *

     * <p>To iterate over the {@code true} bits in a {@code BitSet},

     * use the following loop:

     *

     *  <pre> {@code

     * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {

     *     // operate on index i here

     * }}</pre>

     *

     * @param  fromIndex the index to start checking from (inclusive)

     * @return the index of the next set bit, or {@code -1} if there

     *         is no such bit

     * @throws IndexOutOfBoundsException if the specified index is negative

     * @since  1.4

     */

    public int nextSetBit(int fromIndex) {

        if (fromIndex < 0)

            throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

        checkInvariants();

        int u = wordIndex(fromIndex);

        if (u >= wordsInUse)

            return -1;

        long word = words[u] & (WORD_MASK << fromIndex);

        while (true) {

            if (word != 0)

                return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);

            if (++u == wordsInUse)

                return -1;

            word = words[u];

        }

    }

    /**

     * Returns the index of the first bit that is set to {@code false}

     * that occurs on or after the specified starting index.

     *

     * @param  fromIndex the index to start checking from (inclusive)

     * @return the index of the next clear bit

     * @throws IndexOutOfBoundsException if the specified index is negative

     * @since  1.4

     */

    public int nextClearBit(int fromIndex) {

        // Neither spec nor implementation handle bitsets of maximal length.

        // See 4816253.

        if (fromIndex < 0)

            throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

        checkInvariants();

        int u = wordIndex(fromIndex);

        if (u >= wordsInUse)

            return fromIndex;

        long word = ~words[u] & (WORD_MASK << fromIndex);

        while (true) {

            if (word != 0)

                return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);

            if (++u == wordsInUse)

                return wordsInUse * BITS_PER_WORD;

            word = ~words[u];

        }

    }

    /**

     * Returns the index of the nearest bit that is set to {@code true}

     * that occurs on or before the specified starting index.

     * If no such bit exists, or if {@code -1} is given as the

     * starting index, then {@code -1} is returned.

     *

     * <p>To iterate over the {@code true} bits in a {@code BitSet},

     * use the following loop:

     *

     *  <pre> {@code

     * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {

     *     // operate on index i here

     * }}</pre>

     *

     * @param  fromIndex the index to start checking from (inclusive)

     * @return the index of the previous set bit, or {@code -1} if there

     *         is no such bit

     * @throws IndexOutOfBoundsException if the specified index is less

     *         than {@code -1}

     * @since  1.7

     */

    public int previousSetBit(int fromIndex) {

        if (fromIndex < 0) {

            if (fromIndex == -1)

                return -1;

            throw new IndexOutOfBoundsException(

                "fromIndex < -1: " + fromIndex);

        }

        checkInvariants();

        int u = wordIndex(fromIndex);

        if (u >= wordsInUse)

            return length() - 1;

        long word = words[u] & (WORD_MASK >>> -(fromIndex+1));

        while (true) {

            if (word != 0)

                return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);

            if (u-- == 0)

                return -1;

            word = words[u];

        }

    }

    /**

     * Returns the index of the nearest bit that is set to {@code false}

     * that occurs on or before the specified starting index.

     * If no such bit exists, or if {@code -1} is given as the

     * starting index, then {@code -1} is returned.

     *

     * @param  fromIndex the index to start checking from (inclusive)

     * @return the index of the previous clear bit, or {@code -1} if there

     *         is no such bit

     * @throws IndexOutOfBoundsException if the specified index is less

     *         than {@code -1}

     * @since  1.7

     */

    public int previousClearBit(int fromIndex) {

        if (fromIndex < 0) {

            if (fromIndex == -1)

                return -1;

            throw new IndexOutOfBoundsException(

                "fromIndex < -1: " + fromIndex);

        }

        checkInvariants();

        int u = wordIndex(fromIndex);

        if (u >= wordsInUse)

            return fromIndex;

        long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1));

        while (true) {

            if (word != 0)

                return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);

            if (u-- == 0)

                return -1;

            word = ~words[u];

        }

    }

    /**

     * Returns the "logical size" of this {@code BitSet}: the index of

     * the highest set bit in the {@code BitSet} plus one. Returns zero

     * if the {@code BitSet} contains no set bits.

     *

     * @return the logical size of this {@code BitSet}

     * @since  1.2

     */

    public int length() {

        if (wordsInUse == 0)

            return 0;

        return BITS_PER_WORD * (wordsInUse - 1) +

            (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));

    }

    /**

     * Returns true if this {@code BitSet} contains no bits that are set

     * to {@code true}.

     *

     * @return boolean indicating whether this {@code BitSet} is empty

     * @since  1.4

     */

    public boolean isEmpty() {

        return wordsInUse == 0;

    }

    /**

     * Returns true if the specified {@code BitSet} has any bits set to

     * {@code true} that are also set to {@code true} in this {@code BitSet}.

     *

     * @param  set {@code BitSet} to intersect with

     * @return boolean indicating whether this {@code BitSet} intersects

     *         the specified {@code BitSet}

     * @since  1.4

     */

    public boolean intersects(BitSet set) {

        for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)

            if ((words[i] & set.words[i]) != 0)

                return true;

        return false;

    }

    /**

     * Returns the number of bits set to {@code true} in this {@code BitSet}.

     *

     * @return the number of bits set to {@code true} in this {@code BitSet}

     * @since  1.4

     */

    public int cardinality() {

        int sum = 0;

        for (int i = 0; i < wordsInUse; i++)

            sum += Long.bitCount(words[i]);

        return sum;

    }

    /**

     * Performs a logical <b>AND</b> of this target bit set with the

     * argument bit set. This bit set is modified so that each bit in it

     * has the value {@code true} if and only if it both initially

     * had the value {@code true} and the corresponding bit in the

     * bit set argument also had the value {@code true}.

     *

     * @param set a bit set

     */

    public void and(BitSet set) {

        if (this == set)

            return;

        while (wordsInUse > set.wordsInUse)

            words[--wordsInUse] = 0;

        // Perform logical AND on words in common

        for (int i = 0; i < wordsInUse; i++)

            words[i] &= set.words[i];

        recalculateWordsInUse();

        checkInvariants();

    }

    /**

     * Performs a logical <b>OR</b> of this bit set with the bit set

     * argument. This bit set is modified so that a bit in it has the

     * value {@code true} if and only if it either already had the

     * value {@code true} or the corresponding bit in the bit set

     * argument has the value {@code true}.

     *

     * @param set a bit set

     */

    public void or(BitSet set) {

        if (this == set)

            return;

        int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);

        if (wordsInUse < set.wordsInUse) {

            ensureCapacity(set.wordsInUse);

            wordsInUse = set.wordsInUse;

        }

        // Perform logical OR on words in common

        for (int i = 0; i < wordsInCommon; i++)

            words[i] |= set.words[i];

        // Copy any remaining words

        if (wordsInCommon < set.wordsInUse)

            System.arraycopy(set.words, wordsInCommon,

                             words, wordsInCommon,

                             wordsInUse - wordsInCommon);

        // recalculateWordsInUse() is unnecessary

        checkInvariants();

    }

    /**

     * Performs a logical <b>XOR</b> of this bit set with the bit set

     * argument. This bit set is modified so that a bit in it has the

     * value {@code true} if and only if one of the following

     * statements holds:

     * <ul>

     * <li>The bit initially has the value {@code true}, and the

     *     corresponding bit in the argument has the value {@code false}.

     * <li>The bit initially has the value {@code false}, and the

     *     corresponding bit in the argument has the value {@code true}.

     * </ul>

     *

     * @param  set a bit set

     */

    public void xor(BitSet set) {

        int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);

        if (wordsInUse < set.wordsInUse) {

            ensureCapacity(set.wordsInUse);

            wordsInUse = set.wordsInUse;

        }

        // Perform logical XOR on words in common

        for (int i = 0; i < wordsInCommon; i++)

            words[i] ^= set.words[i];

        // Copy any remaining words

        if (wordsInCommon < set.wordsInUse)

            System.arraycopy(set.words, wordsInCommon,

                             words, wordsInCommon,

                             set.wordsInUse - wordsInCommon);

        recalculateWordsInUse();

        checkInvariants();

    }

    /**

     * Clears all of the bits in this {@code BitSet} whose corresponding

     * bit is set in the specified {@code BitSet}.

     *

     * @param  set the {@code BitSet} with which to mask this

     *         {@code BitSet}

     * @since  1.2

     */

    public void andNot(BitSet set) {

        // Perform logical (a & !b) on words in common

        for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)

            words[i] &= ~set.words[i];