1 /*

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

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

     4  *

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

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

     7  * published by the Free Software Foundation.  Oracle designates this

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

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

    10  *

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

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

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

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

    15  * accompanied this code).

    16  *

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

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

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

    20  *

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

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

    23  * questions.

    24  */

    25 

    26 package java.util;

    27 

    28 import java.io.*;

    29 import java.nio.ByteBuffer;

    30 import java.nio.ByteOrder;

    31 import java.nio.LongBuffer;

    32 import java.util.function.IntConsumer;

    33 import java.util.stream.IntStream;

    34 import java.util.stream.StreamSupport;

    35 

    36 /**

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

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

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

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

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

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

    43  * logical exclusive OR operations.

    44  *

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

    46  * {@code false}.

    47  *

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

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

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

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

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

    53  *

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

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

    56  * {@code NullPointerException}.

    57  *

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

    59  * external synchronization.

    60  *

    61  * @author  Arthur van Hoff

    62  * @author  Michael McCloskey

    63  * @author  Martin Buchholz

    64  * @since   1.0

    65  */

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

    67     /*

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

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

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

    71      */

    72     private static final int ADDRESS_BITS_PER_WORD = 6;

    73     private static final int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;

    74     private static final int BIT_INDEX_MASK = BITS_PER_WORD - 1;

    75 

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

    77     private static final long WORD_MASK = 0xffffffffffffffffL;

    78 

    79     /**

    80      * @serialField bits long[]

    81      *

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

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

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

    85      */

    86     private static final ObjectStreamField[] serialPersistentFields = {

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

    88     };

    89 

    90     /**

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

    92      */

    93     private long[] words;

    94 

    95     /**

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

    97      */

    98     private transient int wordsInUse = 0;

    99 

   100     /**

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

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

   103      */

   104     private transient boolean sizeIsSticky = false;

   105 

   106     /* use serialVersionUID from JDK 1.0.2 for interoperability */

   107     private static final long serialVersionUID = 7997698588986878753L;

   108 

   109     /**

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

   111      */

   112     private static int wordIndex(int bitIndex) {

   113         return bitIndex >> ADDRESS_BITS_PER_WORD;

   114     }

   115 

   116     /**

   117      * Every public method must preserve these invariants.

   118      */

   119     private void checkInvariants() {

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

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

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

   123     }

   124 

   125     /**

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

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

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

   129      */

   130     private void recalculateWordsInUse() {

   131         // Traverse the bitset until a used word is found

   132         int i;

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

   134             if (words[i] != 0)

   135                 break;

   136 

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

   138     }

   139 

   140     /**

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

   142      */

   143     public BitSet() {

   144         initWords(BITS_PER_WORD);

   145         sizeIsSticky = false;

   146     }

   147 

   148     /**

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

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

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

   152      *

   153      * @param  nbits the initial size of the bit set

   154      * @throws NegativeArraySizeException if the specified initial size

   155      *         is negative

   156      */

   157     public BitSet(int nbits) {

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

   159         if (nbits < 0)

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

   161 

   162         initWords(nbits);

   163         sizeIsSticky = true;

   164     }

   165 

   166     private void initWords(int nbits) {

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

   168     }

   169 

   170     /**

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

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

   173      */

   174     private BitSet(long[] words) {

   175         this.words = words;

   176         this.wordsInUse = words.length;

   177         checkInvariants();

   178     }

   179 

   180     /**

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

   182      *

   183      * <p>More precisely,

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

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

   186      *

   187      * <p>This method is equivalent to

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

   189      *

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

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

   192      *        new bit set

   193      * @return a {@code BitSet} containing all the bits in the long array

   194      * @since 1.7

   195      */

   196     public static BitSet valueOf(long[] longs) {

   197         int n;

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

   199             ;

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

   201     }

   202 

   203     /**

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

   205      * buffer between its position and limit.

   206      *

   207      * <p>More precisely,

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

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

   210      *

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

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

   213      *

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

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

   216      *        used as the initial bits of the new bit set

   217      * @return a {@code BitSet} containing all the bits in the buffer in the

   218      *         specified range

   219      * @since 1.7

   220      */

   221     public static BitSet valueOf(LongBuffer lb) {

   222         lb = lb.slice();

   223         int n;

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

   225             ;

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

   227         lb.get(words);

   228         return new BitSet(words);

   229     }

   230 

   231     /**

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

   233      *

   234      * <p>More precisely,

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

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

   237      *

   238      * <p>This method is equivalent to

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

   240      *

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

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

   243      *        initial bits of the new bit set

   244      * @return a {@code BitSet} containing all the bits in the byte array

   245      * @since 1.7

   246      */

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

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

   249     }

   250 

   251     /**

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

   253      * buffer between its position and limit.

   254      *

   255      * <p>More precisely,

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

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

   258      *

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

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

   261      *

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

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

   264      *        used as the initial bits of the new bit set

   265      * @return a {@code BitSet} containing all the bits in the buffer in the

   266      *         specified range

   267      * @since 1.7

   268      */

   269     public static BitSet valueOf(ByteBuffer bb) {

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

   271         int n;

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

   273             ;

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

   275         bb.limit(n);

   276         int i = 0;

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

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

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

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

   281         return new BitSet(words);

   282     }

   283 

   284     /**

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

   286      *

   287      * <p>More precisely, if

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

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

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

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

   292      *

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

   294      *         of all the bits in this bit set

   295      * @since 1.7

   296     */

   297     public byte[] toByteArray() {

   298         int n = wordsInUse;

   299         if (n == 0)

   300             return new byte[0];

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

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

   303             len++;

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

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

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

   307             bb.putLong(words[i]);

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

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

   310         return bytes;

   311     }

   312 

   313     /**

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

   315      *

   316      * <p>More precisely, if

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

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

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

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

   321      *

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

   323      *         of all the bits in this bit set

   324      * @since 1.7

   325     */

   326     public long[] toLongArray() {

   327         return Arrays.copyOf(words, wordsInUse);

   328     }

   329 

   330     /**

   331      * Ensures that the BitSet can hold enough words.

   332      * @param wordsRequired the minimum acceptable number of words.

   333      */

   334     private void ensureCapacity(int wordsRequired) {

   335         if (words.length < wordsRequired) {

   336             // Allocate larger of doubled size or required size

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

   338             words = Arrays.copyOf(words, request);

   339             sizeIsSticky = false;

   340         }

   341     }

   342 

   343     /**

   344      * Ensures that the BitSet can accommodate a given wordIndex,

   345      * temporarily violating the invariants.  The caller must

   346      * restore the invariants before returning to the user,

   347      * possibly using recalculateWordsInUse().

   348      * @param wordIndex the index to be accommodated.

   349      */

   350     private void expandTo(int wordIndex) {

   351         int wordsRequired = wordIndex+1;

   352         if (wordsInUse < wordsRequired) {

   353             ensureCapacity(wordsRequired);

   354             wordsInUse = wordsRequired;

   355         }

   356     }

   357 

   358     /**

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

   360      */

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

   362         if (fromIndex < 0)

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

   364         if (toIndex < 0)

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

   366         if (fromIndex > toIndex)

   367             throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +

   368                                                 " > toIndex: " + toIndex);

   369     }

   370 

   371     /**

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

   373      * current value.

   374      *

   375      * @param  bitIndex the index of the bit to flip

   376      * @throws IndexOutOfBoundsException if the specified index is negative

   377      * @since  1.4

   378      */

   379     public void flip(int bitIndex) {

   380         if (bitIndex < 0)

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

   382 

   383         int wordIndex = wordIndex(bitIndex);

   384         expandTo(wordIndex);

   385 

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

   387 

   388         recalculateWordsInUse();

   389         checkInvariants();

   390     }

   391 

   392     /**

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

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

   395      * value.

   396      *

   397      * @param  fromIndex index of the first bit to flip

   398      * @param  toIndex index after the last bit to flip

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

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

   401      *         larger than {@code toIndex}

   402      * @since  1.4

   403      */

   404     public void flip(int fromIndex, int toIndex) {

   405         checkRange(fromIndex, toIndex);

   406 

   407         if (fromIndex == toIndex)

   408             return;

   409 

   410         int startWordIndex = wordIndex(fromIndex);

   411         int endWordIndex   = wordIndex(toIndex - 1);

   412         expandTo(endWordIndex);

   413 

   414         long firstWordMask = WORD_MASK << fromIndex;

   415         long lastWordMask  = WORD_MASK >>> -toIndex;

   416         if (startWordIndex == endWordIndex) {

   417             // Case 1: One word

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

   419         } else {

   420             // Case 2: Multiple words

   421             // Handle first word

   422             words[startWordIndex] ^= firstWordMask;

   423 

   424             // Handle intermediate words, if any

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

   426                 words[i] ^= WORD_MASK;

   427 

   428             // Handle last word

   429             words[endWordIndex] ^= lastWordMask;

   430         }

   431 

   432         recalculateWordsInUse();

   433         checkInvariants();

   434     }

   435 

   436     /**

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

   438      *

   439      * @param  bitIndex a bit index

   440      * @throws IndexOutOfBoundsException if the specified index is negative

   441      * @since  1.0

   442      */

   443     public void set(int bitIndex) {

   444         if (bitIndex < 0)

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

   446 

   447         int wordIndex = wordIndex(bitIndex);

   448         expandTo(wordIndex);

   449 

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

   451 

   452         checkInvariants();

   453     }

   454 

   455     /**

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

   457      *

   458      * @param  bitIndex a bit index

   459      * @param  value a boolean value to set

   460      * @throws IndexOutOfBoundsException if the specified index is negative

   461      * @since  1.4

   462      */

   463     public void set(int bitIndex, boolean value) {

   464         if (value)

   465             set(bitIndex);

   466         else

   467             clear(bitIndex);

   468     }

   469 

   470     /**

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

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

   473      *

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

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

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

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

   478      *         larger than {@code toIndex}

   479      * @since  1.4

   480      */

   481     public void set(int fromIndex, int toIndex) {

   482         checkRange(fromIndex, toIndex);

   483 

   484         if (fromIndex == toIndex)

   485             return;

   486 

   487         // Increase capacity if necessary

   488         int startWordIndex = wordIndex(fromIndex);

   489         int endWordIndex   = wordIndex(toIndex - 1);

   490         expandTo(endWordIndex);

   491 

   492         long firstWordMask = WORD_MASK << fromIndex;

   493         long lastWordMask  = WORD_MASK >>> -toIndex;

   494         if (startWordIndex == endWordIndex) {

   495             // Case 1: One word

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

   497         } else {

   498             // Case 2: Multiple words

   499             // Handle first word

   500             words[startWordIndex] |= firstWordMask;

   501 

   502             // Handle intermediate words, if any

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

   504                 words[i] = WORD_MASK;

   505 

   506             // Handle last word (restores invariants)

   507             words[endWordIndex] |= lastWordMask;

   508         }

   509 

   510         checkInvariants();

   511     }

   512 

   513     /**

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

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

   516      *

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

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

   519      * @param  value value to set the selected bits to

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

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

   522      *         larger than {@code toIndex}

   523      * @since  1.4

   524      */

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

   526         if (value)

   527             set(fromIndex, toIndex);

   528         else

   529             clear(fromIndex, toIndex);

   530     }

   531 

   532     /**

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

   534      *

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

   536      * @throws IndexOutOfBoundsException if the specified index is negative

   537      * @since  1.0

   538      */

   539     public void clear(int bitIndex) {

   540         if (bitIndex < 0)

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

   542 

   543         int wordIndex = wordIndex(bitIndex);

   544         if (wordIndex >= wordsInUse)

   545             return;

   546 

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

   548 

   549         recalculateWordsInUse();

   550         checkInvariants();

   551     }

   552 

   553     /**

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

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

   556      *

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

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

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

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

   561      *         larger than {@code toIndex}

   562      * @since  1.4

   563      */

   564     public void clear(int fromIndex, int toIndex) {

   565         checkRange(fromIndex, toIndex);

   566 

   567         if (fromIndex == toIndex)

   568             return;

   569 

   570         int startWordIndex = wordIndex(fromIndex);

   571         if (startWordIndex >= wordsInUse)

   572             return;

   573 

   574         int endWordIndex = wordIndex(toIndex - 1);

   575         if (endWordIndex >= wordsInUse) {

   576             toIndex = length();

   577             endWordIndex = wordsInUse - 1;

   578         }

   579 

   580         long firstWordMask = WORD_MASK << fromIndex;

   581         long lastWordMask  = WORD_MASK >>> -toIndex;

   582         if (startWordIndex == endWordIndex) {

   583             // Case 1: One word

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

   585         } else {

   586             // Case 2: Multiple words

   587             // Handle first word

   588             words[startWordIndex] &= ~firstWordMask;

   589 

   590             // Handle intermediate words, if any

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

   592                 words[i] = 0;

   593 

   594             // Handle last word

   595             words[endWordIndex] &= ~lastWordMask;

   596         }

   597 

   598         recalculateWordsInUse();

   599         checkInvariants();

   600     }

   601 

   602     /**

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

   604      *

   605      * @since 1.4

   606      */

   607     public void clear() {

   608         while (wordsInUse > 0)

   609             words[--wordsInUse] = 0;

   610     }

   611 

   612     /**

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

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

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

   616      * is {@code false}.

   617      *

   618      * @param  bitIndex   the bit index

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

   620      * @throws IndexOutOfBoundsException if the specified index is negative

   621      */

   622     public boolean get(int bitIndex) {

   623         if (bitIndex < 0)

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

   625 

   626         checkInvariants();

   627 

   628         int wordIndex = wordIndex(bitIndex);

   629         return (wordIndex < wordsInUse)

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

   631     }

   632 

   633     /**

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

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

   636      *

   637      * @param  fromIndex index of the first bit to include

   638      * @param  toIndex index after the last bit to include

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

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

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

   642      *         larger than {@code toIndex}

   643      * @since  1.4

   644      */

   645     public BitSet get(int fromIndex, int toIndex) {

   646         checkRange(fromIndex, toIndex);

   647 

   648         checkInvariants();

   649 

   650         int len = length();

   651 

   652         // If no set bits in range return empty bitset

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

   654             return new BitSet(0);

   655 

   656         // An optimization

   657         if (toIndex > len)

   658             toIndex = len;

   659 

   660         BitSet result = new BitSet(toIndex - fromIndex);

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

   662         int sourceIndex = wordIndex(fromIndex);

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

   664 

   665         // Process all words but the last word

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

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

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

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

   670 

   671         // Process the last word

   672         long lastWordMask = WORD_MASK >>> -toIndex;

   673         result.words[targetWords - 1] =

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

   675             ? /* straddles source words */

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

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

   678             :

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

   680 

   681         // Set wordsInUse correctly

   682         result.wordsInUse = targetWords;

   683         result.recalculateWordsInUse();

   684         result.checkInvariants();

   685 

   686         return result;

   687     }

   688 

   689     /**

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

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

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

   693      *

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

   695      * use the following loop:

   696      *

   697      *  <pre> {@code

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

   699      *     // operate on index i here

   700      *     if (i == Integer.MAX_VALUE) {

   701      *         break; // or (i+1) would overflow

   702      *     }

   703      * }}</pre>

   704      *

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

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

   707      *         is no such bit

   708      * @throws IndexOutOfBoundsException if the specified index is negative

   709      * @since  1.4

   710      */

   711     public int nextSetBit(int fromIndex) {

   712         if (fromIndex < 0)

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

   714 

   715         checkInvariants();

   716 

   717         int u = wordIndex(fromIndex);

   718         if (u >= wordsInUse)

   719             return -1;

   720 

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

   722 

   723         while (true) {

   724             if (word != 0)

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

   726             if (++u == wordsInUse)

   727                 return -1;

   728             word = words[u];

   729         }

   730     }

   731 

   732     /**

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

   734      * that occurs on or after the specified starting index.

   735      *

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

   737      * @return the index of the next clear bit

   738      * @throws IndexOutOfBoundsException if the specified index is negative

   739      * @since  1.4

   740      */

   741     public int nextClearBit(int fromIndex) {

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

   743         // See 4816253.

   744         if (fromIndex < 0)

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

   746 

   747         checkInvariants();

   748 

   749         int u = wordIndex(fromIndex);

   750         if (u >= wordsInUse)

   751             return fromIndex;

   752 

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

   754 

   755         while (true) {

   756             if (word != 0)

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

   758             if (++u == wordsInUse)

   759                 return wordsInUse * BITS_PER_WORD;

   760             word = ~words[u];

   761         }

   762     }

   763 

   764     /**

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

   766      * that occurs on or before the specified starting index.

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

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

   769      *

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

   771      * use the following loop:

   772      *

   773      *  <pre> {@code

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

   775      *     // operate on index i here

   776      * }}</pre>

   777      *

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

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

   780      *         is no such bit

   781      * @throws IndexOutOfBoundsException if the specified index is less

   782      *         than {@code -1}

   783      * @since  1.7

   784      */

   785     public int previousSetBit(int fromIndex) {

   786         if (fromIndex < 0) {

   787             if (fromIndex == -1)

   788                 return -1;

   789             throw new IndexOutOfBoundsException(

   790                 "fromIndex < -1: " + fromIndex);

   791         }

   792 

   793         checkInvariants();

   794 

   795         int u = wordIndex(fromIndex);

   796         if (u >= wordsInUse)

   797             return length() - 1;

   798 

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

   800 

   801         while (true) {

   802             if (word != 0)

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

   804             if (u-- == 0)

   805                 return -1;

   806             word = words[u];

   807         }

   808     }

   809 

   810     /**

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

   812      * that occurs on or before the specified starting index.

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

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

   815      *

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

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

   818      *         is no such bit

   819      * @throws IndexOutOfBoundsException if the specified index is less

   820      *         than {@code -1}

   821      * @since  1.7

   822      */

   823     public int previousClearBit(int fromIndex) {

   824         if (fromIndex < 0) {

   825             if (fromIndex == -1)

   826                 return -1;

   827             throw new IndexOutOfBoundsException(

   828                 "fromIndex < -1: " + fromIndex);

   829         }

   830 

   831         checkInvariants();

   832 

   833         int u = wordIndex(fromIndex);

   834         if (u >= wordsInUse)

   835             return fromIndex;

   836 

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

   838 

   839         while (true) {

   840             if (word != 0)

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

   842             if (u-- == 0)

   843                 return -1;

   844             word = ~words[u];

   845         }

   846     }

   847 

   848     /**

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

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

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

   852      *

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

   854      * @since  1.2

   855      */

   856     public int length() {

   857         if (wordsInUse == 0)

   858             return 0;

   859 

   860         return BITS_PER_WORD * (wordsInUse - 1) +

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

   862     }

   863 

   864     /**

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

   866      * to {@code true}.

   867      *

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

   869      * @since  1.4

   870      */

   871     public boolean isEmpty() {

   872         return wordsInUse == 0;

   873     }

   874 

   875     /**

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

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

   878      *

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

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

   881      *         the specified {@code BitSet}

   882      * @since  1.4

   883      */

   884     public boolean intersects(BitSet set) {

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

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

   887                 return true;

   888         return false;

   889     }

   890 

   891     /**

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

   893      *

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

   895      * @since  1.4

   896      */

   897     public int cardinality() {

   898         int sum = 0;

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

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

   901         return sum;

   902     }

   903 

   904     /**

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

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

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

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

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

   910      *

   911      * @param set a bit set

   912      */

   913     public void and(BitSet set) {

   914         if (this == set)

   915             return;

   916 

   917         while (wordsInUse > set.wordsInUse)

   918             words[--wordsInUse] = 0;

   919 

   920         // Perform logical AND on words in common

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

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

   923 

   924         recalculateWordsInUse();

   925         checkInvariants();

   926     }

   927 

   928     /**

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

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

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

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

   933      * argument has the value {@code true}.

   934      *

   935      * @param set a bit set

   936      */

   937     public void or(BitSet set) {

   938         if (this == set)

   939             return;

   940 

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

   942 

   943         if (wordsInUse < set.wordsInUse) {

   944             ensureCapacity(set.wordsInUse);

   945             wordsInUse = set.wordsInUse;

   946         }

   947 

   948         // Perform logical OR on words in common

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

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

   951 

   952         // Copy any remaining words

   953         if (wordsInCommon < set.wordsInUse)

   954             System.arraycopy(set.words, wordsInCommon,

   955                              words, wordsInCommon,

   956                              wordsInUse - wordsInCommon);

   957 

   958         // recalculateWordsInUse() is unnecessary

   959         checkInvariants();

   960     }

   961 

   962     /**

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

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

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

   966      * statements holds:

   967      * <ul>

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

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

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

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

   972      * </ul>

   973      *

   974      * @param  set a bit set

   975      */

   976     public void xor(BitSet set) {

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

   978 

   979         if (wordsInUse < set.wordsInUse) {

   980             ensureCapacity(set.wordsInUse);

   981             wordsInUse = set.wordsInUse;

   982         }

   983 

   984         // Perform logical XOR on words in common

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

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

   987 

   988         // Copy any remaining words

   989         if (wordsInCommon < set.wordsInUse)

   990             System.arraycopy(set.words, wordsInCommon,

   991                              words, wordsInCommon,

   992                              set.wordsInUse - wordsInCommon);

   993 

   994         recalculateWordsInUse();

   995         checkInvariants();

   996     }

   997 

   998     /**

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

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

  1001      *

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

  1003      *         {@code BitSet}

  1004      * @since  1.2

  1005      */

  1006     public void andNot(BitSet set) {

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

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

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

  1010 

  1011         recalculateWordsInUse();

  1012         checkInvariants();

  1013     }

  1014 

  1015     /**

  1016      * Returns the hash code value for this bit set. The hash code depends

  1017      * only on which bits are set within this {@code BitSet}.

  1018      *

  1019      * <p>The hash code is defined to be the result of the following

  1020      * calculation:

  1021      *  <pre> {@code

  1022      * public int hashCode() {

  1023      *     long h = 1234;

  1024      *     long[] words = toLongArray();

  1025      *     for (int i = words.length; --i >= 0; )

  1026      *         h ^= words[i] * (i + 1);

  1027      *     return (int)((h >> 32) ^ h);

  1028      * }}</pre>

  1029      * Note that the hash code changes if the set of bits is altered.

  1030      *

  1031      * @return the hash code value for this bit set

  1032      */

  1033     public int hashCode() {

  1034         long h = 1234;

  1035         for (int i = wordsInUse; --i >= 0; )

  1036             h ^= words[i] * (i + 1);

  1037 

  1038         return (int)((h >> 32) ^ h);

  1039     }

  1040 

  1041     /**

  1042      * Returns the number of bits of space actually in use by this

  1043      * {@code BitSet} to represent bit values.

  1044      * The maximum element in the set is the size - 1st element.

  1045      *

  1046      * @return the number of bits currently in this bit set

  1047      */

  1048     public int size() {

  1049         return words.length * BITS_PER_WORD;

  1050     }

  1051 

  1052     /**

  1053      * Compares this object against the specified object.

  1054      * The result is {@code true} if and only if the argument is

  1055      * not {@code null} and is a {@code Bitset} object that has

  1056      * exactly the same set of bits set to {@code true} as this bit

  1057      * set. That is, for every nonnegative {@code int} index {@code k},

  1058      * <pre>((BitSet)obj).get(k) == this.get(k)</pre>

  1059      * must be true. The current sizes of the two bit sets are not compared.

  1060      *

  1061      * @param  obj the object to compare with

  1062      * @return {@code true} if the objects are the same;

  1063      *         {@code false} otherwise

  1064      * @see    #size()

  1065      */

  1066     public boolean equals(Object obj) {

  1067         if (!(obj instanceof BitSet))

  1068             return false;

  1069         if (this == obj)

  1070             return true;

  1071 

  1072         BitSet set = (BitSet) obj;

  1073 

  1074         checkInvariants();

  1075         set.checkInvariants();

  1076 

  1077         if (wordsInUse != set.wordsInUse)

  1078             return false;

  1079 

  1080         // Check words in use by both BitSets

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

  1082             if (words[i] != set.words[i])

  1083                 return false;

  1084 

  1085         return true;

  1086     }

  1087 

  1088     /**

  1089      * Cloning this {@code BitSet} produces a new {@code BitSet}

  1090      * that is equal to it.

  1091      * The clone of the bit set is another bit set that has exactly the

  1092      * same bits set to {@code true} as this bit set.

  1093      *

  1094      * @return a clone of this bit set

  1095      * @see    #size()

  1096      */

  1097     public Object clone() {

  1098         if (! sizeIsSticky)

  1099             trimToSize();

  1100 

  1101         try {

  1102             BitSet result = (BitSet) super.clone();

  1103             result.words = words.clone();

  1104             result.checkInvariants();

  1105             return result;

  1106         } catch (CloneNotSupportedException e) {

  1107             throw new InternalError(e);

  1108         }

  1109     }

  1110 

  1111     /**

  1112      * Attempts to reduce internal storage used for the bits in this bit set.

  1113      * Calling this method may, but is not required to, affect the value

  1114      * returned by a subsequent call to the {@link #size()} method.

  1115      */

  1116     private void trimToSize() {

  1117         if (wordsInUse != words.length) {

  1118             words = Arrays.copyOf(words, wordsInUse);

  1119             checkInvariants();

  1120         }

  1121     }

  1122 

  1123     /**

  1124      * Save the state of the {@code BitSet} instance to a stream (i.e.,

  1125      * serialize it).

  1126      */

  1127     private void writeObject(ObjectOutputStream s)

  1128         throws IOException {

  1129 

  1130         checkInvariants();

  1131 

  1132         if (! sizeIsSticky)

  1133             trimToSize();

  1134