jdk/src/java.base/share/classes/java/util/BitSet.java
author mchung
Fri, 22 May 2015 16:43:39 -0700
changeset 30789 9eca83469588
parent 29816 43ad6bf3975b
child 32649 2ee9017c7597
permissions -rw-r--r--
8074431: Remove native2ascii tool Reviewed-by: erikj, alanb, okutsu, mfang, naoto
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     1
/*
24257
f524e23d7f7b 8040806: BitSet.toString() can throw IndexOutOfBoundsException
igerasim
parents: 23010
diff changeset
     2
 * Copyright (c) 1995, 2014, Oracle and/or its affiliates. All rights reserved.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     3
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
90ce3da70b43 Initial load
duke
parents:
diff changeset
     4
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
     5
 * This code is free software; you can redistribute it and/or modify it
90ce3da70b43 Initial load
duke
parents:
diff changeset
     6
 * under the terms of the GNU General Public License version 2 only, as
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
     7
 * published by the Free Software Foundation.  Oracle designates this
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     8
 * particular file as subject to the "Classpath" exception as provided
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
     9
 * by Oracle in the LICENSE file that accompanied this code.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    10
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    11
 * This code is distributed in the hope that it will be useful, but WITHOUT
90ce3da70b43 Initial load
duke
parents:
diff changeset
    12
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
90ce3da70b43 Initial load
duke
parents:
diff changeset
    13
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
90ce3da70b43 Initial load
duke
parents:
diff changeset
    14
 * version 2 for more details (a copy is included in the LICENSE file that
90ce3da70b43 Initial load
duke
parents:
diff changeset
    15
 * accompanied this code).
90ce3da70b43 Initial load
duke
parents:
diff changeset
    16
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    17
 * You should have received a copy of the GNU General Public License version
90ce3da70b43 Initial load
duke
parents:
diff changeset
    18
 * 2 along with this work; if not, write to the Free Software Foundation,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    19
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    20
 *
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    21
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    22
 * or visit www.oracle.com if you need additional information or have any
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    23
 * questions.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    24
 */
90ce3da70b43 Initial load
duke
parents:
diff changeset
    25
90ce3da70b43 Initial load
duke
parents:
diff changeset
    26
package java.util;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    27
90ce3da70b43 Initial load
duke
parents:
diff changeset
    28
import java.io.*;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    29
import java.nio.ByteBuffer;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    30
import java.nio.ByteOrder;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    31
import java.nio.LongBuffer;
17421
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
    32
import java.util.stream.IntStream;
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
    33
import java.util.stream.StreamSupport;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    34
90ce3da70b43 Initial load
duke
parents:
diff changeset
    35
/**
90ce3da70b43 Initial load
duke
parents:
diff changeset
    36
 * This class implements a vector of bits that grows as needed. Each
90ce3da70b43 Initial load
duke
parents:
diff changeset
    37
 * component of the bit set has a {@code boolean} value. The
90ce3da70b43 Initial load
duke
parents:
diff changeset
    38
 * bits of a {@code BitSet} are indexed by nonnegative integers.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    39
 * Individual indexed bits can be examined, set, or cleared. One
90ce3da70b43 Initial load
duke
parents:
diff changeset
    40
 * {@code BitSet} may be used to modify the contents of another
90ce3da70b43 Initial load
duke
parents:
diff changeset
    41
 * {@code BitSet} through logical AND, logical inclusive OR, and
90ce3da70b43 Initial load
duke
parents:
diff changeset
    42
 * logical exclusive OR operations.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    43
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    44
 * <p>By default, all bits in the set initially have the value
90ce3da70b43 Initial load
duke
parents:
diff changeset
    45
 * {@code false}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    46
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    47
 * <p>Every bit set has a current size, which is the number of bits
90ce3da70b43 Initial load
duke
parents:
diff changeset
    48
 * of space currently in use by the bit set. Note that the size is
90ce3da70b43 Initial load
duke
parents:
diff changeset
    49
 * related to the implementation of a bit set, so it may change with
90ce3da70b43 Initial load
duke
parents:
diff changeset
    50
 * implementation. The length of a bit set relates to logical length
90ce3da70b43 Initial load
duke
parents:
diff changeset
    51
 * of a bit set and is defined independently of implementation.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    52
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    53
 * <p>Unless otherwise noted, passing a null parameter to any of the
90ce3da70b43 Initial load
duke
parents:
diff changeset
    54
 * methods in a {@code BitSet} will result in a
90ce3da70b43 Initial load
duke
parents:
diff changeset
    55
 * {@code NullPointerException}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    56
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    57
 * <p>A {@code BitSet} is not safe for multithreaded use without
90ce3da70b43 Initial load
duke
parents:
diff changeset
    58
 * external synchronization.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    59
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    60
 * @author  Arthur van Hoff
90ce3da70b43 Initial load
duke
parents:
diff changeset
    61
 * @author  Michael McCloskey
90ce3da70b43 Initial load
duke
parents:
diff changeset
    62
 * @author  Martin Buchholz
24865
09b1d992ca72 8044740: Convert all JDK versions used in @since tag to 1.n[.n] in jdk repo
henryjen
parents: 24257
diff changeset
    63
 * @since   1.0
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    64
 */
90ce3da70b43 Initial load
duke
parents:
diff changeset
    65
public class BitSet implements Cloneable, java.io.Serializable {
90ce3da70b43 Initial load
duke
parents:
diff changeset
    66
    /*
90ce3da70b43 Initial load
duke
parents:
diff changeset
    67
     * BitSets are packed into arrays of "words."  Currently a word is
90ce3da70b43 Initial load
duke
parents:
diff changeset
    68
     * a long, which consists of 64 bits, requiring 6 address bits.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    69
     * The choice of word size is determined purely by performance concerns.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    70
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
    71
    private final static int ADDRESS_BITS_PER_WORD = 6;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    72
    private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    73
    private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    74
90ce3da70b43 Initial load
duke
parents:
diff changeset
    75
    /* Used to shift left or right for a partial word mask */
90ce3da70b43 Initial load
duke
parents:
diff changeset
    76
    private static final long WORD_MASK = 0xffffffffffffffffL;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    77
90ce3da70b43 Initial load
duke
parents:
diff changeset
    78
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
    79
     * @serialField bits long[]
90ce3da70b43 Initial load
duke
parents:
diff changeset
    80
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    81
     * The bits in this BitSet.  The ith bit is stored in bits[i/64] at
90ce3da70b43 Initial load
duke
parents:
diff changeset
    82
     * bit position i % 64 (where bit position 0 refers to the least
90ce3da70b43 Initial load
duke
parents:
diff changeset
    83
     * significant bit and 63 refers to the most significant bit).
90ce3da70b43 Initial load
duke
parents:
diff changeset
    84
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
    85
    private static final ObjectStreamField[] serialPersistentFields = {
90ce3da70b43 Initial load
duke
parents:
diff changeset
    86
        new ObjectStreamField("bits", long[].class),
90ce3da70b43 Initial load
duke
parents:
diff changeset
    87
    };
90ce3da70b43 Initial load
duke
parents:
diff changeset
    88
90ce3da70b43 Initial load
duke
parents:
diff changeset
    89
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
    90
     * The internal field corresponding to the serialField "bits".
90ce3da70b43 Initial load
duke
parents:
diff changeset
    91
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
    92
    private long[] words;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    93
90ce3da70b43 Initial load
duke
parents:
diff changeset
    94
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
    95
     * The number of words in the logical size of this BitSet.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    96
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
    97
    private transient int wordsInUse = 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    98
90ce3da70b43 Initial load
duke
parents:
diff changeset
    99
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   100
     * Whether the size of "words" is user-specified.  If so, we assume
90ce3da70b43 Initial load
duke
parents:
diff changeset
   101
     * the user knows what he's doing and try harder to preserve it.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   102
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   103
    private transient boolean sizeIsSticky = false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   104
90ce3da70b43 Initial load
duke
parents:
diff changeset
   105
    /* use serialVersionUID from JDK 1.0.2 for interoperability */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   106
    private static final long serialVersionUID = 7997698588986878753L;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   107
90ce3da70b43 Initial load
duke
parents:
diff changeset
   108
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   109
     * Given a bit index, return word index containing it.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   110
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   111
    private static int wordIndex(int bitIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   112
        return bitIndex >> ADDRESS_BITS_PER_WORD;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   113
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   114
90ce3da70b43 Initial load
duke
parents:
diff changeset
   115
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   116
     * Every public method must preserve these invariants.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   117
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   118
    private void checkInvariants() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   119
        assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   120
        assert(wordsInUse >= 0 && wordsInUse <= words.length);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   121
        assert(wordsInUse == words.length || words[wordsInUse] == 0);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   122
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   123
90ce3da70b43 Initial load
duke
parents:
diff changeset
   124
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   125
     * Sets the field wordsInUse to the logical size in words of the bit set.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   126
     * WARNING:This method assumes that the number of words actually in use is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   127
     * less than or equal to the current value of wordsInUse!
90ce3da70b43 Initial load
duke
parents:
diff changeset
   128
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   129
    private void recalculateWordsInUse() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   130
        // Traverse the bitset until a used word is found
90ce3da70b43 Initial load
duke
parents:
diff changeset
   131
        int i;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   132
        for (i = wordsInUse-1; i >= 0; i--)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   133
            if (words[i] != 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   134
                break;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   135
90ce3da70b43 Initial load
duke
parents:
diff changeset
   136
        wordsInUse = i+1; // The new logical size
90ce3da70b43 Initial load
duke
parents:
diff changeset
   137
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   138
90ce3da70b43 Initial load
duke
parents:
diff changeset
   139
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   140
     * Creates a new bit set. All bits are initially {@code false}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   141
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   142
    public BitSet() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   143
        initWords(BITS_PER_WORD);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   144
        sizeIsSticky = false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   145
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   146
90ce3da70b43 Initial load
duke
parents:
diff changeset
   147
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   148
     * Creates a bit set whose initial size is large enough to explicitly
90ce3da70b43 Initial load
duke
parents:
diff changeset
   149
     * represent bits with indices in the range {@code 0} through
90ce3da70b43 Initial load
duke
parents:
diff changeset
   150
     * {@code nbits-1}. All bits are initially {@code false}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   151
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   152
     * @param  nbits the initial size of the bit set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   153
     * @throws NegativeArraySizeException if the specified initial size
90ce3da70b43 Initial load
duke
parents:
diff changeset
   154
     *         is negative
90ce3da70b43 Initial load
duke
parents:
diff changeset
   155
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   156
    public BitSet(int nbits) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   157
        // nbits can't be negative; size 0 is OK
90ce3da70b43 Initial load
duke
parents:
diff changeset
   158
        if (nbits < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   159
            throw new NegativeArraySizeException("nbits < 0: " + nbits);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   160
90ce3da70b43 Initial load
duke
parents:
diff changeset
   161
        initWords(nbits);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   162
        sizeIsSticky = true;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   163
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   164
90ce3da70b43 Initial load
duke
parents:
diff changeset
   165
    private void initWords(int nbits) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   166
        words = new long[wordIndex(nbits-1) + 1];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   167
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   168
90ce3da70b43 Initial load
duke
parents:
diff changeset
   169
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   170
     * Creates a bit set using words as the internal representation.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   171
     * The last word (if there is one) must be non-zero.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   172
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   173
    private BitSet(long[] words) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   174
        this.words = words;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   175
        this.wordsInUse = words.length;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   176
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   177
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   178
90ce3da70b43 Initial load
duke
parents:
diff changeset
   179
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   180
     * Returns a new bit set containing all the bits in the given long array.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   181
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   182
     * <p>More precisely,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   183
     * <br>{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   184
     * <br>for all {@code n < 64 * longs.length}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   185
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   186
     * <p>This method is equivalent to
90ce3da70b43 Initial load
duke
parents:
diff changeset
   187
     * {@code BitSet.valueOf(LongBuffer.wrap(longs))}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   188
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   189
     * @param longs a long array containing a little-endian representation
90ce3da70b43 Initial load
duke
parents:
diff changeset
   190
     *        of a sequence of bits to be used as the initial bits of the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   191
     *        new bit set
18829
ec84f0c313b0 8020409: Clean up doclint problems in java.util package, part 1
bpb
parents: 18822
diff changeset
   192
     * @return a {@code BitSet} containing all the bits in the long array
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   193
     * @since 1.7
90ce3da70b43 Initial load
duke
parents:
diff changeset
   194
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   195
    public static BitSet valueOf(long[] longs) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   196
        int n;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   197
        for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   198
            ;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   199
        return new BitSet(Arrays.copyOf(longs, n));
90ce3da70b43 Initial load
duke
parents:
diff changeset
   200
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   201
90ce3da70b43 Initial load
duke
parents:
diff changeset
   202
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   203
     * Returns a new bit set containing all the bits in the given long
90ce3da70b43 Initial load
duke
parents:
diff changeset
   204
     * buffer between its position and limit.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   205
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   206
     * <p>More precisely,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   207
     * <br>{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   208
     * <br>for all {@code n < 64 * lb.remaining()}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   209
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   210
     * <p>The long buffer is not modified by this method, and no
90ce3da70b43 Initial load
duke
parents:
diff changeset
   211
     * reference to the buffer is retained by the bit set.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   212
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   213
     * @param lb a long buffer containing a little-endian representation
90ce3da70b43 Initial load
duke
parents:
diff changeset
   214
     *        of a sequence of bits between its position and limit, to be
90ce3da70b43 Initial load
duke
parents:
diff changeset
   215
     *        used as the initial bits of the new bit set
18829
ec84f0c313b0 8020409: Clean up doclint problems in java.util package, part 1
bpb
parents: 18822
diff changeset
   216
     * @return a {@code BitSet} containing all the bits in the buffer in the
ec84f0c313b0 8020409: Clean up doclint problems in java.util package, part 1
bpb
parents: 18822
diff changeset
   217
     *         specified range
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   218
     * @since 1.7
90ce3da70b43 Initial load
duke
parents:
diff changeset
   219
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   220
    public static BitSet valueOf(LongBuffer lb) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   221
        lb = lb.slice();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   222
        int n;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   223
        for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   224
            ;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   225
        long[] words = new long[n];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   226
        lb.get(words);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   227
        return new BitSet(words);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   228
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   229
90ce3da70b43 Initial load
duke
parents:
diff changeset
   230
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   231
     * Returns a new bit set containing all the bits in the given byte array.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   232
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   233
     * <p>More precisely,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   234
     * <br>{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   235
     * <br>for all {@code n <  8 * bytes.length}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   236
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   237
     * <p>This method is equivalent to
90ce3da70b43 Initial load
duke
parents:
diff changeset
   238
     * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   239
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   240
     * @param bytes a byte array containing a little-endian
90ce3da70b43 Initial load
duke
parents:
diff changeset
   241
     *        representation of a sequence of bits to be used as the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   242
     *        initial bits of the new bit set
18829
ec84f0c313b0 8020409: Clean up doclint problems in java.util package, part 1
bpb
parents: 18822
diff changeset
   243
     * @return a {@code BitSet} containing all the bits in the byte array
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   244
     * @since 1.7
90ce3da70b43 Initial load
duke
parents:
diff changeset
   245
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   246
    public static BitSet valueOf(byte[] bytes) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   247
        return BitSet.valueOf(ByteBuffer.wrap(bytes));
90ce3da70b43 Initial load
duke
parents:
diff changeset
   248
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   249
90ce3da70b43 Initial load
duke
parents:
diff changeset
   250
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   251
     * Returns a new bit set containing all the bits in the given byte
90ce3da70b43 Initial load
duke
parents:
diff changeset
   252
     * buffer between its position and limit.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   253
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   254
     * <p>More precisely,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   255
     * <br>{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   256
     * <br>for all {@code n < 8 * bb.remaining()}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   257
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   258
     * <p>The byte buffer is not modified by this method, and no
90ce3da70b43 Initial load
duke
parents:
diff changeset
   259
     * reference to the buffer is retained by the bit set.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   260
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   261
     * @param bb a byte buffer containing a little-endian representation
90ce3da70b43 Initial load
duke
parents:
diff changeset
   262
     *        of a sequence of bits between its position and limit, to be
90ce3da70b43 Initial load
duke
parents:
diff changeset
   263
     *        used as the initial bits of the new bit set
18829
ec84f0c313b0 8020409: Clean up doclint problems in java.util package, part 1
bpb
parents: 18822
diff changeset
   264
     * @return a {@code BitSet} containing all the bits in the buffer in the
ec84f0c313b0 8020409: Clean up doclint problems in java.util package, part 1
bpb
parents: 18822
diff changeset
   265
     *         specified range
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   266
     * @since 1.7
90ce3da70b43 Initial load
duke
parents:
diff changeset
   267
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   268
    public static BitSet valueOf(ByteBuffer bb) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   269
        bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   270
        int n;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   271
        for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   272
            ;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   273
        long[] words = new long[(n + 7) / 8];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   274
        bb.limit(n);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   275
        int i = 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   276
        while (bb.remaining() >= 8)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   277
            words[i++] = bb.getLong();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   278
        for (int remaining = bb.remaining(), j = 0; j < remaining; j++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   279
            words[i] |= (bb.get() & 0xffL) << (8 * j);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   280
        return new BitSet(words);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   281
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   282
90ce3da70b43 Initial load
duke
parents:
diff changeset
   283
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   284
     * Returns a new byte array containing all the bits in this bit set.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   285
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   286
     * <p>More precisely, if
90ce3da70b43 Initial load
duke
parents:
diff changeset
   287
     * <br>{@code byte[] bytes = s.toByteArray();}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   288
     * <br>then {@code bytes.length == (s.length()+7)/8} and
90ce3da70b43 Initial load
duke
parents:
diff changeset
   289
     * <br>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   290
     * <br>for all {@code n < 8 * bytes.length}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   291
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   292
     * @return a byte array containing a little-endian representation
90ce3da70b43 Initial load
duke
parents:
diff changeset
   293
     *         of all the bits in this bit set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   294
     * @since 1.7
90ce3da70b43 Initial load
duke
parents:
diff changeset
   295
    */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   296
    public byte[] toByteArray() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   297
        int n = wordsInUse;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   298
        if (n == 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   299
            return new byte[0];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   300
        int len = 8 * (n-1);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   301
        for (long x = words[n - 1]; x != 0; x >>>= 8)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   302
            len++;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   303
        byte[] bytes = new byte[len];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   304
        ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   305
        for (int i = 0; i < n - 1; i++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   306
            bb.putLong(words[i]);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   307
        for (long x = words[n - 1]; x != 0; x >>>= 8)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   308
            bb.put((byte) (x & 0xff));
90ce3da70b43 Initial load
duke
parents:
diff changeset
   309
        return bytes;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   310
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   311
90ce3da70b43 Initial load
duke
parents:
diff changeset
   312
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   313
     * Returns a new long array containing all the bits in this bit set.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   314
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   315
     * <p>More precisely, if
90ce3da70b43 Initial load
duke
parents:
diff changeset
   316
     * <br>{@code long[] longs = s.toLongArray();}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   317
     * <br>then {@code longs.length == (s.length()+63)/64} and
90ce3da70b43 Initial load
duke
parents:
diff changeset
   318
     * <br>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   319
     * <br>for all {@code n < 64 * longs.length}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   320
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   321
     * @return a long array containing a little-endian representation
90ce3da70b43 Initial load
duke
parents:
diff changeset
   322
     *         of all the bits in this bit set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   323
     * @since 1.7
90ce3da70b43 Initial load
duke
parents:
diff changeset
   324
    */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   325
    public long[] toLongArray() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   326
        return Arrays.copyOf(words, wordsInUse);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   327
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   328
90ce3da70b43 Initial load
duke
parents:
diff changeset
   329
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   330
     * Ensures that the BitSet can hold enough words.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   331
     * @param wordsRequired the minimum acceptable number of words.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   332
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   333
    private void ensureCapacity(int wordsRequired) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   334
        if (words.length < wordsRequired) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   335
            // Allocate larger of doubled size or required size
90ce3da70b43 Initial load
duke
parents:
diff changeset
   336
            int request = Math.max(2 * words.length, wordsRequired);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   337
            words = Arrays.copyOf(words, request);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   338
            sizeIsSticky = false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   339
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   340
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   341
90ce3da70b43 Initial load
duke
parents:
diff changeset
   342
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   343
     * Ensures that the BitSet can accommodate a given wordIndex,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   344
     * temporarily violating the invariants.  The caller must
90ce3da70b43 Initial load
duke
parents:
diff changeset
   345
     * restore the invariants before returning to the user,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   346
     * possibly using recalculateWordsInUse().
90ce3da70b43 Initial load
duke
parents:
diff changeset
   347
     * @param wordIndex the index to be accommodated.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   348
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   349
    private void expandTo(int wordIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   350
        int wordsRequired = wordIndex+1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   351
        if (wordsInUse < wordsRequired) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   352
            ensureCapacity(wordsRequired);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   353
            wordsInUse = wordsRequired;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   354
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   355
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   356
90ce3da70b43 Initial load
duke
parents:
diff changeset
   357
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   358
     * Checks that fromIndex ... toIndex is a valid range of bit indices.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   359
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   360
    private static void checkRange(int fromIndex, int toIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   361
        if (fromIndex < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   362
            throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   363
        if (toIndex < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   364
            throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   365
        if (fromIndex > toIndex)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   366
            throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
90ce3da70b43 Initial load
duke
parents:
diff changeset
   367
                                                " > toIndex: " + toIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   368
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   369
90ce3da70b43 Initial load
duke
parents:
diff changeset
   370
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   371
     * Sets the bit at the specified index to the complement of its
90ce3da70b43 Initial load
duke
parents:
diff changeset
   372
     * current value.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   373
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   374
     * @param  bitIndex the index of the bit to flip
90ce3da70b43 Initial load
duke
parents:
diff changeset
   375
     * @throws IndexOutOfBoundsException if the specified index is negative
90ce3da70b43 Initial load
duke
parents:
diff changeset
   376
     * @since  1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   377
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   378
    public void flip(int bitIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   379
        if (bitIndex < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   380
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   381
90ce3da70b43 Initial load
duke
parents:
diff changeset
   382
        int wordIndex = wordIndex(bitIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   383
        expandTo(wordIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   384
90ce3da70b43 Initial load
duke
parents:
diff changeset
   385
        words[wordIndex] ^= (1L << bitIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   386
90ce3da70b43 Initial load
duke
parents:
diff changeset
   387
        recalculateWordsInUse();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   388
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   389
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   390
90ce3da70b43 Initial load
duke
parents:
diff changeset
   391
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   392
     * Sets each bit from the specified {@code fromIndex} (inclusive) to the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   393
     * specified {@code toIndex} (exclusive) to the complement of its current
90ce3da70b43 Initial load
duke
parents:
diff changeset
   394
     * value.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   395
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   396
     * @param  fromIndex index of the first bit to flip
90ce3da70b43 Initial load
duke
parents:
diff changeset
   397
     * @param  toIndex index after the last bit to flip
90ce3da70b43 Initial load
duke
parents:
diff changeset
   398
     * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   399
     *         or {@code toIndex} is negative, or {@code fromIndex} is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   400
     *         larger than {@code toIndex}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   401
     * @since  1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   402
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   403
    public void flip(int fromIndex, int toIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   404
        checkRange(fromIndex, toIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   405
90ce3da70b43 Initial load
duke
parents:
diff changeset
   406
        if (fromIndex == toIndex)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   407
            return;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   408
90ce3da70b43 Initial load
duke
parents:
diff changeset
   409
        int startWordIndex = wordIndex(fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   410
        int endWordIndex   = wordIndex(toIndex - 1);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   411
        expandTo(endWordIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   412
90ce3da70b43 Initial load
duke
parents:
diff changeset
   413
        long firstWordMask = WORD_MASK << fromIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   414
        long lastWordMask  = WORD_MASK >>> -toIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   415
        if (startWordIndex == endWordIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   416
            // Case 1: One word
90ce3da70b43 Initial load
duke
parents:
diff changeset
   417
            words[startWordIndex] ^= (firstWordMask & lastWordMask);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   418
        } else {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   419
            // Case 2: Multiple words
90ce3da70b43 Initial load
duke
parents:
diff changeset
   420
            // Handle first word
90ce3da70b43 Initial load
duke
parents:
diff changeset
   421
            words[startWordIndex] ^= firstWordMask;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   422
90ce3da70b43 Initial load
duke
parents:
diff changeset
   423
            // Handle intermediate words, if any
90ce3da70b43 Initial load
duke
parents:
diff changeset
   424
            for (int i = startWordIndex+1; i < endWordIndex; i++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   425
                words[i] ^= WORD_MASK;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   426
90ce3da70b43 Initial load
duke
parents:
diff changeset
   427
            // Handle last word
90ce3da70b43 Initial load
duke
parents:
diff changeset
   428
            words[endWordIndex] ^= lastWordMask;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   429
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   430
90ce3da70b43 Initial load
duke
parents:
diff changeset
   431
        recalculateWordsInUse();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   432
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   433
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   434
90ce3da70b43 Initial load
duke
parents:
diff changeset
   435
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   436
     * Sets the bit at the specified index to {@code true}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   437
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   438
     * @param  bitIndex a bit index
90ce3da70b43 Initial load
duke
parents:
diff changeset
   439
     * @throws IndexOutOfBoundsException if the specified index is negative
24865
09b1d992ca72 8044740: Convert all JDK versions used in @since tag to 1.n[.n] in jdk repo
henryjen
parents: 24257
diff changeset
   440
     * @since  1.0
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   441
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   442
    public void set(int bitIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   443
        if (bitIndex < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   444
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   445
90ce3da70b43 Initial load
duke
parents:
diff changeset
   446
        int wordIndex = wordIndex(bitIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   447
        expandTo(wordIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   448
90ce3da70b43 Initial load
duke
parents:
diff changeset
   449
        words[wordIndex] |= (1L << bitIndex); // Restores invariants
90ce3da70b43 Initial load
duke
parents:
diff changeset
   450
90ce3da70b43 Initial load
duke
parents:
diff changeset
   451
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   452
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   453
90ce3da70b43 Initial load
duke
parents:
diff changeset
   454
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   455
     * Sets the bit at the specified index to the specified value.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   456
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   457
     * @param  bitIndex a bit index
90ce3da70b43 Initial load
duke
parents:
diff changeset
   458
     * @param  value a boolean value to set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   459
     * @throws IndexOutOfBoundsException if the specified index is negative
90ce3da70b43 Initial load
duke
parents:
diff changeset
   460
     * @since  1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   461
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   462
    public void set(int bitIndex, boolean value) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   463
        if (value)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   464
            set(bitIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   465
        else
90ce3da70b43 Initial load
duke
parents:
diff changeset
   466
            clear(bitIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   467
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   468
90ce3da70b43 Initial load
duke
parents:
diff changeset
   469
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   470
     * Sets the bits from the specified {@code fromIndex} (inclusive) to the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   471
     * specified {@code toIndex} (exclusive) to {@code true}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   472
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   473
     * @param  fromIndex index of the first bit to be set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   474
     * @param  toIndex index after the last bit to be set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   475
     * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   476
     *         or {@code toIndex} is negative, or {@code fromIndex} is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   477
     *         larger than {@code toIndex}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   478
     * @since  1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   479
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   480
    public void set(int fromIndex, int toIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   481
        checkRange(fromIndex, toIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   482
90ce3da70b43 Initial load
duke
parents:
diff changeset
   483
        if (fromIndex == toIndex)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   484
            return;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   485
90ce3da70b43 Initial load
duke
parents:
diff changeset
   486
        // Increase capacity if necessary
90ce3da70b43 Initial load
duke
parents:
diff changeset
   487
        int startWordIndex = wordIndex(fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   488
        int endWordIndex   = wordIndex(toIndex - 1);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   489
        expandTo(endWordIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   490
90ce3da70b43 Initial load
duke
parents:
diff changeset
   491
        long firstWordMask = WORD_MASK << fromIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   492
        long lastWordMask  = WORD_MASK >>> -toIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   493
        if (startWordIndex == endWordIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   494
            // Case 1: One word
90ce3da70b43 Initial load
duke
parents:
diff changeset
   495
            words[startWordIndex] |= (firstWordMask & lastWordMask);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   496
        } else {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   497
            // Case 2: Multiple words
90ce3da70b43 Initial load
duke
parents:
diff changeset
   498
            // Handle first word
90ce3da70b43 Initial load
duke
parents:
diff changeset
   499
            words[startWordIndex] |= firstWordMask;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   500
90ce3da70b43 Initial load
duke
parents:
diff changeset
   501
            // Handle intermediate words, if any
90ce3da70b43 Initial load
duke
parents:
diff changeset
   502
            for (int i = startWordIndex+1; i < endWordIndex; i++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   503
                words[i] = WORD_MASK;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   504
90ce3da70b43 Initial load
duke
parents:
diff changeset
   505
            // Handle last word (restores invariants)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   506
            words[endWordIndex] |= lastWordMask;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   507
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   508
90ce3da70b43 Initial load
duke
parents:
diff changeset
   509
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   510
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   511
90ce3da70b43 Initial load
duke
parents:
diff changeset
   512
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   513
     * Sets the bits from the specified {@code fromIndex} (inclusive) to the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   514
     * specified {@code toIndex} (exclusive) to the specified value.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   515
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   516
     * @param  fromIndex index of the first bit to be set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   517
     * @param  toIndex index after the last bit to be set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   518
     * @param  value value to set the selected bits to
90ce3da70b43 Initial load
duke
parents:
diff changeset
   519
     * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   520
     *         or {@code toIndex} is negative, or {@code fromIndex} is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   521
     *         larger than {@code toIndex}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   522
     * @since  1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   523
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   524
    public void set(int fromIndex, int toIndex, boolean value) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   525
        if (value)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   526
            set(fromIndex, toIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   527
        else
90ce3da70b43 Initial load
duke
parents:
diff changeset
   528
            clear(fromIndex, toIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   529
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   530
90ce3da70b43 Initial load
duke
parents:
diff changeset
   531
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   532
     * Sets the bit specified by the index to {@code false}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   533
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   534
     * @param  bitIndex the index of the bit to be cleared
90ce3da70b43 Initial load
duke
parents:
diff changeset
   535
     * @throws IndexOutOfBoundsException if the specified index is negative
24865
09b1d992ca72 8044740: Convert all JDK versions used in @since tag to 1.n[.n] in jdk repo
henryjen
parents: 24257
diff changeset
   536
     * @since  1.0
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   537
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   538
    public void clear(int bitIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   539
        if (bitIndex < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   540
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   541
90ce3da70b43 Initial load
duke
parents:
diff changeset
   542
        int wordIndex = wordIndex(bitIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   543
        if (wordIndex >= wordsInUse)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   544
            return;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   545
90ce3da70b43 Initial load
duke
parents:
diff changeset
   546
        words[wordIndex] &= ~(1L << bitIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   547
90ce3da70b43 Initial load
duke
parents:
diff changeset
   548
        recalculateWordsInUse();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   549
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   550
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   551
90ce3da70b43 Initial load
duke
parents:
diff changeset
   552
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   553
     * Sets the bits from the specified {@code fromIndex} (inclusive) to the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   554
     * specified {@code toIndex} (exclusive) to {@code false}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   555
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   556
     * @param  fromIndex index of the first bit to be cleared
90ce3da70b43 Initial load
duke
parents:
diff changeset
   557
     * @param  toIndex index after the last bit to be cleared
90ce3da70b43 Initial load
duke
parents:
diff changeset
   558
     * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   559
     *         or {@code toIndex} is negative, or {@code fromIndex} is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   560
     *         larger than {@code toIndex}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   561
     * @since  1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   562
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   563
    public void clear(int fromIndex, int toIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   564
        checkRange(fromIndex, toIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   565
90ce3da70b43 Initial load
duke
parents:
diff changeset
   566
        if (fromIndex == toIndex)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   567
            return;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   568
90ce3da70b43 Initial load
duke
parents:
diff changeset
   569
        int startWordIndex = wordIndex(fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   570
        if (startWordIndex >= wordsInUse)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   571
            return;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   572
90ce3da70b43 Initial load
duke
parents:
diff changeset
   573
        int endWordIndex = wordIndex(toIndex - 1);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   574
        if (endWordIndex >= wordsInUse) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   575
            toIndex = length();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   576
            endWordIndex = wordsInUse - 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   577
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   578
90ce3da70b43 Initial load
duke
parents:
diff changeset
   579
        long firstWordMask = WORD_MASK << fromIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   580
        long lastWordMask  = WORD_MASK >>> -toIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   581
        if (startWordIndex == endWordIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   582
            // Case 1: One word
90ce3da70b43 Initial load
duke
parents:
diff changeset
   583
            words[startWordIndex] &= ~(firstWordMask & lastWordMask);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   584
        } else {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   585
            // Case 2: Multiple words
90ce3da70b43 Initial load
duke
parents:
diff changeset
   586
            // Handle first word
90ce3da70b43 Initial load
duke
parents:
diff changeset
   587
            words[startWordIndex] &= ~firstWordMask;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   588
90ce3da70b43 Initial load
duke
parents:
diff changeset
   589
            // Handle intermediate words, if any
90ce3da70b43 Initial load
duke
parents:
diff changeset
   590
            for (int i = startWordIndex+1; i < endWordIndex; i++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   591
                words[i] = 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   592
90ce3da70b43 Initial load
duke
parents:
diff changeset
   593
            // Handle last word
90ce3da70b43 Initial load
duke
parents:
diff changeset
   594
            words[endWordIndex] &= ~lastWordMask;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   595
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   596
90ce3da70b43 Initial load
duke
parents:
diff changeset
   597
        recalculateWordsInUse();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   598
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   599
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   600
90ce3da70b43 Initial load
duke
parents:
diff changeset
   601
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   602
     * Sets all of the bits in this BitSet to {@code false}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   603
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   604
     * @since 1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   605
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   606
    public void clear() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   607
        while (wordsInUse > 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   608
            words[--wordsInUse] = 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   609
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   610
90ce3da70b43 Initial load
duke
parents:
diff changeset
   611
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   612
     * Returns the value of the bit with the specified index. The value
90ce3da70b43 Initial load
duke
parents:
diff changeset
   613
     * is {@code true} if the bit with the index {@code bitIndex}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   614
     * is currently set in this {@code BitSet}; otherwise, the result
90ce3da70b43 Initial load
duke
parents:
diff changeset
   615
     * is {@code false}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   616
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   617
     * @param  bitIndex   the bit index
90ce3da70b43 Initial load
duke
parents:
diff changeset
   618
     * @return the value of the bit with the specified index
90ce3da70b43 Initial load
duke
parents:
diff changeset
   619
     * @throws IndexOutOfBoundsException if the specified index is negative
90ce3da70b43 Initial load
duke
parents:
diff changeset
   620
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   621
    public boolean get(int bitIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   622
        if (bitIndex < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   623
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   624
90ce3da70b43 Initial load
duke
parents:
diff changeset
   625
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   626
90ce3da70b43 Initial load
duke
parents:
diff changeset
   627
        int wordIndex = wordIndex(bitIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   628
        return (wordIndex < wordsInUse)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   629
            && ((words[wordIndex] & (1L << bitIndex)) != 0);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   630
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   631
90ce3da70b43 Initial load
duke
parents:
diff changeset
   632
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   633
     * Returns a new {@code BitSet} composed of bits from this {@code BitSet}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   634
     * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   635
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   636
     * @param  fromIndex index of the first bit to include
90ce3da70b43 Initial load
duke
parents:
diff changeset
   637
     * @param  toIndex index after the last bit to include
90ce3da70b43 Initial load
duke
parents:
diff changeset
   638
     * @return a new {@code BitSet} from a range of this {@code BitSet}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   639
     * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   640
     *         or {@code toIndex} is negative, or {@code fromIndex} is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   641
     *         larger than {@code toIndex}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   642
     * @since  1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   643
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   644
    public BitSet get(int fromIndex, int toIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   645
        checkRange(fromIndex, toIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   646
90ce3da70b43 Initial load
duke
parents:
diff changeset
   647
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   648
90ce3da70b43 Initial load
duke
parents:
diff changeset
   649
        int len = length();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   650
90ce3da70b43 Initial load
duke
parents:
diff changeset
   651
        // If no set bits in range return empty bitset
90ce3da70b43 Initial load
duke
parents:
diff changeset
   652
        if (len <= fromIndex || fromIndex == toIndex)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   653
            return new BitSet(0);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   654
90ce3da70b43 Initial load
duke
parents:
diff changeset
   655
        // An optimization
90ce3da70b43 Initial load
duke
parents:
diff changeset
   656
        if (toIndex > len)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   657
            toIndex = len;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   658
90ce3da70b43 Initial load
duke
parents:
diff changeset
   659
        BitSet result = new BitSet(toIndex - fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   660
        int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   661
        int sourceIndex = wordIndex(fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   662
        boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   663
90ce3da70b43 Initial load
duke
parents:
diff changeset
   664
        // Process all words but the last word
90ce3da70b43 Initial load
duke
parents:
diff changeset
   665
        for (int i = 0; i < targetWords - 1; i++, sourceIndex++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   666
            result.words[i] = wordAligned ? words[sourceIndex] :
90ce3da70b43 Initial load
duke
parents:
diff changeset
   667
                (words[sourceIndex] >>> fromIndex) |
90ce3da70b43 Initial load
duke
parents:
diff changeset
   668
                (words[sourceIndex+1] << -fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   669
90ce3da70b43 Initial load
duke
parents:
diff changeset
   670
        // Process the last word
90ce3da70b43 Initial load
duke
parents:
diff changeset
   671
        long lastWordMask = WORD_MASK >>> -toIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   672
        result.words[targetWords - 1] =
90ce3da70b43 Initial load
duke
parents:
diff changeset
   673
            ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   674
            ? /* straddles source words */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   675
            ((words[sourceIndex] >>> fromIndex) |
90ce3da70b43 Initial load
duke
parents:
diff changeset
   676
             (words[sourceIndex+1] & lastWordMask) << -fromIndex)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   677
            :
90ce3da70b43 Initial load
duke
parents:
diff changeset
   678
            ((words[sourceIndex] & lastWordMask) >>> fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   679
90ce3da70b43 Initial load
duke
parents:
diff changeset
   680
        // Set wordsInUse correctly
90ce3da70b43 Initial load
duke
parents:
diff changeset
   681
        result.wordsInUse = targetWords;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   682
        result.recalculateWordsInUse();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   683
        result.checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   684
90ce3da70b43 Initial load
duke
parents:
diff changeset
   685
        return result;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   686
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   687
90ce3da70b43 Initial load
duke
parents:
diff changeset
   688
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   689
     * Returns the index of the first bit that is set to {@code true}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   690
     * that occurs on or after the specified starting index. If no such
90ce3da70b43 Initial load
duke
parents:
diff changeset
   691
     * bit exists then {@code -1} is returned.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   692
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   693
     * <p>To iterate over the {@code true} bits in a {@code BitSet},
90ce3da70b43 Initial load
duke
parents:
diff changeset
   694
     * use the following loop:
90ce3da70b43 Initial load
duke
parents:
diff changeset
   695
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   696
     *  <pre> {@code
90ce3da70b43 Initial load
duke
parents:
diff changeset
   697
     * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   698
     *     // operate on index i here
24257
f524e23d7f7b 8040806: BitSet.toString() can throw IndexOutOfBoundsException
igerasim
parents: 23010
diff changeset
   699
     *     if (i == Integer.MAX_VALUE) {
f524e23d7f7b 8040806: BitSet.toString() can throw IndexOutOfBoundsException
igerasim
parents: 23010
diff changeset
   700
     *         break; // or (i+1) would overflow
f524e23d7f7b 8040806: BitSet.toString() can throw IndexOutOfBoundsException
igerasim
parents: 23010
diff changeset
   701
     *     }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   702
     * }}</pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   703
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   704
     * @param  fromIndex the index to start checking from (inclusive)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   705
     * @return the index of the next set bit, or {@code -1} if there
90ce3da70b43 Initial load
duke
parents:
diff changeset
   706
     *         is no such bit
90ce3da70b43 Initial load
duke
parents:
diff changeset
   707
     * @throws IndexOutOfBoundsException if the specified index is negative
90ce3da70b43 Initial load
duke
parents:
diff changeset
   708
     * @since  1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   709
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   710
    public int nextSetBit(int fromIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   711
        if (fromIndex < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   712
            throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   713
90ce3da70b43 Initial load
duke
parents:
diff changeset
   714
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   715
90ce3da70b43 Initial load
duke
parents:
diff changeset
   716
        int u = wordIndex(fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   717
        if (u >= wordsInUse)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   718
            return -1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   719
90ce3da70b43 Initial load
duke
parents:
diff changeset
   720
        long word = words[u] & (WORD_MASK << fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   721
90ce3da70b43 Initial load
duke
parents:
diff changeset
   722
        while (true) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   723
            if (word != 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   724
                return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   725
            if (++u == wordsInUse)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   726
                return -1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   727
            word = words[u];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   728
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   729
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   730
90ce3da70b43 Initial load
duke
parents:
diff changeset
   731
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   732
     * Returns the index of the first bit that is set to {@code false}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   733
     * that occurs on or after the specified starting index.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   734
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   735
     * @param  fromIndex the index to start checking from (inclusive)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   736
     * @return the index of the next clear bit
90ce3da70b43 Initial load
duke
parents:
diff changeset
   737
     * @throws IndexOutOfBoundsException if the specified index is negative
90ce3da70b43 Initial load
duke
parents:
diff changeset
   738
     * @since  1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   739
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   740
    public int nextClearBit(int fromIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   741
        // Neither spec nor implementation handle bitsets of maximal length.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   742
        // See 4816253.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   743
        if (fromIndex < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   744
            throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   745
90ce3da70b43 Initial load
duke
parents:
diff changeset
   746
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   747
90ce3da70b43 Initial load
duke
parents:
diff changeset
   748
        int u = wordIndex(fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   749
        if (u >= wordsInUse)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   750
            return fromIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   751
90ce3da70b43 Initial load
duke
parents:
diff changeset
   752
        long word = ~words[u] & (WORD_MASK << fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   753
90ce3da70b43 Initial load
duke
parents:
diff changeset
   754
        while (true) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   755
            if (word != 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   756
                return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   757
            if (++u == wordsInUse)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   758
                return wordsInUse * BITS_PER_WORD;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   759
            word = ~words[u];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   760
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   761
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   762
90ce3da70b43 Initial load
duke
parents:
diff changeset
   763
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   764
     * Returns the index of the nearest bit that is set to {@code true}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   765
     * that occurs on or before the specified starting index.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   766
     * If no such bit exists, or if {@code -1} is given as the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   767
     * starting index, then {@code -1} is returned.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   768
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   769
     * <p>To iterate over the {@code true} bits in a {@code BitSet},
90ce3da70b43 Initial load
duke
parents:
diff changeset
   770
     * use the following loop:
90ce3da70b43 Initial load
duke
parents:
diff changeset
   771
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   772
     *  <pre> {@code
90ce3da70b43 Initial load
duke
parents:
diff changeset
   773
     * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   774
     *     // operate on index i here
90ce3da70b43 Initial load
duke
parents:
diff changeset
   775
     * }}</pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   776
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   777
     * @param  fromIndex the index to start checking from (inclusive)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   778
     * @return the index of the previous set bit, or {@code -1} if there
90ce3da70b43 Initial load
duke
parents:
diff changeset
   779
     *         is no such bit
90ce3da70b43 Initial load
duke
parents:
diff changeset
   780
     * @throws IndexOutOfBoundsException if the specified index is less
90ce3da70b43 Initial load
duke
parents:
diff changeset
   781
     *         than {@code -1}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   782
     * @since  1.7
90ce3da70b43 Initial load
duke
parents:
diff changeset
   783
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   784
    public int previousSetBit(int fromIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   785
        if (fromIndex < 0) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   786
            if (fromIndex == -1)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   787
                return -1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   788
            throw new IndexOutOfBoundsException(
90ce3da70b43 Initial load
duke
parents:
diff changeset
   789
                "fromIndex < -1: " + fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   790
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   791
90ce3da70b43 Initial load
duke
parents:
diff changeset
   792
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   793
90ce3da70b43 Initial load
duke
parents:
diff changeset
   794
        int u = wordIndex(fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   795
        if (u >= wordsInUse)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   796
            return length() - 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   797
90ce3da70b43 Initial load
duke
parents:
diff changeset
   798
        long word = words[u] & (WORD_MASK >>> -(fromIndex+1));
90ce3da70b43 Initial load
duke
parents:
diff changeset
   799
90ce3da70b43 Initial load
duke
parents:
diff changeset
   800
        while (true) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   801
            if (word != 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   802
                return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   803
            if (u-- == 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   804
                return -1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   805
            word = words[u];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   806
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   807
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   808
90ce3da70b43 Initial load
duke
parents:
diff changeset
   809
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   810
     * Returns the index of the nearest bit that is set to {@code false}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   811
     * that occurs on or before the specified starting index.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   812
     * If no such bit exists, or if {@code -1} is given as the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   813
     * starting index, then {@code -1} is returned.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   814
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   815
     * @param  fromIndex the index to start checking from (inclusive)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   816
     * @return the index of the previous clear bit, or {@code -1} if there
90ce3da70b43 Initial load
duke
parents:
diff changeset
   817
     *         is no such bit
90ce3da70b43 Initial load
duke
parents:
diff changeset
   818
     * @throws IndexOutOfBoundsException if the specified index is less
90ce3da70b43 Initial load
duke
parents:
diff changeset
   819
     *         than {@code -1}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   820
     * @since  1.7
90ce3da70b43 Initial load
duke
parents:
diff changeset
   821
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   822
    public int previousClearBit(int fromIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   823
        if (fromIndex < 0) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   824
            if (fromIndex == -1)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   825
                return -1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   826
            throw new IndexOutOfBoundsException(
90ce3da70b43 Initial load
duke
parents:
diff changeset
   827
                "fromIndex < -1: " + fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   828
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   829
90ce3da70b43 Initial load
duke
parents:
diff changeset
   830
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   831
90ce3da70b43 Initial load
duke
parents:
diff changeset
   832
        int u = wordIndex(fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   833
        if (u >= wordsInUse)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   834
            return fromIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   835
90ce3da70b43 Initial load
duke
parents:
diff changeset
   836
        long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1));
90ce3da70b43 Initial load
duke
parents:
diff changeset
   837
90ce3da70b43 Initial load
duke
parents:
diff changeset
   838
        while (true) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   839
            if (word != 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   840
                return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   841
            if (u-- == 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   842
                return -1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   843
            word = ~words[u];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   844
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   845
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   846
90ce3da70b43 Initial load
duke
parents:
diff changeset
   847
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   848
     * Returns the "logical size" of this {@code BitSet}: the index of
90ce3da70b43 Initial load
duke
parents:
diff changeset
   849
     * the highest set bit in the {@code BitSet} plus one. Returns zero
90ce3da70b43 Initial load
duke
parents:
diff changeset
   850
     * if the {@code BitSet} contains no set bits.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   851
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   852
     * @return the logical size of this {@code BitSet}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   853
     * @since  1.2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   854
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   855
    public int length() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   856
        if (wordsInUse == 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   857
            return 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   858
90ce3da70b43 Initial load
duke
parents:
diff changeset
   859
        return BITS_PER_WORD * (wordsInUse - 1) +
90ce3da70b43 Initial load
duke
parents:
diff changeset
   860
            (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
90ce3da70b43 Initial load
duke
parents:
diff changeset
   861
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   862
90ce3da70b43 Initial load
duke
parents:
diff changeset
   863
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   864
     * Returns true if this {@code BitSet} contains no bits that are set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   865
     * to {@code true}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   866
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   867
     * @return boolean indicating whether this {@code BitSet} is empty
90ce3da70b43 Initial load
duke
parents:
diff changeset
   868
     * @since  1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   869
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   870
    public boolean isEmpty() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   871
        return wordsInUse == 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   872
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   873
90ce3da70b43 Initial load
duke
parents:
diff changeset
   874
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   875
     * Returns true if the specified {@code BitSet} has any bits set to
90ce3da70b43 Initial load
duke
parents:
diff changeset
   876
     * {@code true} that are also set to {@code true} in this {@code BitSet}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   877
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   878
     * @param  set {@code BitSet} to intersect with
90ce3da70b43 Initial load
duke
parents:
diff changeset
   879
     * @return boolean indicating whether this {@code BitSet} intersects
90ce3da70b43 Initial load
duke
parents:
diff changeset
   880
     *         the specified {@code BitSet}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   881
     * @since  1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   882
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   883
    public boolean intersects(BitSet set) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   884
        for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   885
            if ((words[i] & set.words[i]) != 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   886
                return true;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   887
        return false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   888
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   889
90ce3da70b43 Initial load
duke
parents:
diff changeset
   890
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   891
     * Returns the number of bits set to {@code true} in this {@code BitSet}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   892
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   893
     * @return the number of bits set to {@code true} in this {@code BitSet}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   894
     * @since  1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   895
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   896
    public int cardinality() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   897
        int sum = 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   898
        for (int i = 0; i < wordsInUse; i++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   899
            sum += Long.bitCount(words[i]);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   900
        return sum;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   901
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   902
90ce3da70b43 Initial load
duke
parents:
diff changeset
   903
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   904
     * Performs a logical <b>AND</b> of this target bit set with the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   905
     * argument bit set. This bit set is modified so that each bit in it
90ce3da70b43 Initial load
duke
parents:
diff changeset
   906
     * has the value {@code true} if and only if it both initially
90ce3da70b43 Initial load
duke
parents:
diff changeset
   907
     * had the value {@code true} and the corresponding bit in the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   908
     * bit set argument also had the value {@code true}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   909
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   910
     * @param set a bit set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   911
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   912
    public void and(BitSet set) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   913
        if (this == set)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   914
            return;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   915
90ce3da70b43 Initial load
duke
parents:
diff changeset
   916
        while (wordsInUse > set.wordsInUse)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   917
            words[--wordsInUse] = 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   918
90ce3da70b43 Initial load
duke
parents:
diff changeset
   919
        // Perform logical AND on words in common
90ce3da70b43 Initial load
duke
parents:
diff changeset
   920
        for (int i = 0; i < wordsInUse; i++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   921
            words[i] &= set.words[i];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   922
90ce3da70b43 Initial load
duke
parents:
diff changeset
   923
        recalculateWordsInUse();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   924
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   925
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   926
90ce3da70b43 Initial load
duke
parents:
diff changeset
   927
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   928
     * Performs a logical <b>OR</b> of this bit set with the bit set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   929
     * argument. This bit set is modified so that a bit in it has the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   930
     * value {@code true} if and only if it either already had the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   931
     * value {@code true} or the corresponding bit in the bit set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   932
     * argument has the value {@code true}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   933
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   934
     * @param set a bit set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   935
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   936
    public void or(BitSet set) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   937
        if (this == set)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   938
            return;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   939
90ce3da70b43 Initial load
duke
parents:
diff changeset
   940
        int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   941
90ce3da70b43 Initial load
duke
parents:
diff changeset
   942
        if (wordsInUse < set.wordsInUse) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   943
            ensureCapacity(set.wordsInUse);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   944
            wordsInUse = set.wordsInUse;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   945
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   946
90ce3da70b43 Initial load
duke
parents:
diff changeset
   947
        // Perform logical OR on words in common
90ce3da70b43 Initial load
duke
parents:
diff changeset
   948
        for (int i = 0; i < wordsInCommon; i++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   949
            words[i] |= set.words[i];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   950
90ce3da70b43 Initial load
duke
parents:
diff changeset
   951
        // Copy any remaining words
90ce3da70b43 Initial load
duke
parents:
diff changeset
   952
        if (wordsInCommon < set.wordsInUse)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   953
            System.arraycopy(set.words, wordsInCommon,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   954
                             words, wordsInCommon,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   955
                             wordsInUse - wordsInCommon);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   956
90ce3da70b43 Initial load
duke
parents:
diff changeset
   957
        // recalculateWordsInUse() is unnecessary
90ce3da70b43 Initial load
duke
parents:
diff changeset
   958
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   959
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   960
90ce3da70b43 Initial load
duke
parents:
diff changeset
   961
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   962
     * Performs a logical <b>XOR</b> of this bit set with the bit set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   963
     * argument. This bit set is modified so that a bit in it has the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   964
     * value {@code true} if and only if one of the following
90ce3da70b43 Initial load
duke
parents:
diff changeset
   965
     * statements holds:
90ce3da70b43 Initial load
duke
parents:
diff changeset
   966
     * <ul>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   967
     * <li>The bit initially has the value {@code true}, and the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   968
     *     corresponding bit in the argument has the value {@code false}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   969
     * <li>The bit initially has the value {@code false}, and the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   970
     *     corresponding bit in the argument has the value {@code true}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   971
     * </ul>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   972
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   973
     * @param  set a bit set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   974
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   975
    public void xor(BitSet set) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   976
        int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   977
90ce3da70b43 Initial load
duke
parents:
diff changeset
   978
        if (wordsInUse < set.wordsInUse) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   979
            ensureCapacity(set.wordsInUse);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   980
            wordsInUse = set.wordsInUse;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   981
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   982
90ce3da70b43 Initial load
duke
parents:
diff changeset
   983
        // Perform logical XOR on words in common
90ce3da70b43 Initial load
duke
parents:
diff changeset
   984
        for (int i = 0; i < wordsInCommon; i++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   985
            words[i] ^= set.words[i];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   986
90ce3da70b43 Initial load
duke
parents:
diff changeset
   987
        // Copy any remaining words
90ce3da70b43 Initial load
duke
parents:
diff changeset
   988
        if (wordsInCommon < set.wordsInUse)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   989
            System.arraycopy(set.words, wordsInCommon,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   990
                             words, wordsInCommon,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   991
                             set.wordsInUse - wordsInCommon);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   992
90ce3da70b43 Initial load
duke
parents:
diff changeset
   993
        recalculateWordsInUse();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   994
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   995
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   996
90ce3da70b43 Initial load
duke
parents:
diff changeset
   997
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   998
     * Clears all of the bits in this {@code BitSet} whose corresponding
90ce3da70b43 Initial load
duke
parents:
diff changeset
   999
     * bit is set in the specified {@code BitSet}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1000
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1001
     * @param  set the {@code BitSet} with which to mask this
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1002
     *         {@code BitSet}
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1003
     * @since  1.2
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1004
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1005
    public void andNot(BitSet set) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1006
        // Perform logical (a & !b) on words in common
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1007
        for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1008
            words[i] &= ~set.words[i];
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1009
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1010
        recalculateWordsInUse();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1011
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1012
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1013
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1014
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1015
     * Returns the hash code value for this bit set. The hash code depends
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1016
     * only on which bits are set within this {@code BitSet}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1017
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1018
     * <p>The hash code is defined to be the result of the following
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1019
     * calculation:
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1020
     *  <pre> {@code
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1021
     * public int hashCode() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1022
     *     long h = 1234;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1023
     *     long[] words = toLongArray();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1024
     *     for (int i = words.length; --i >= 0; )
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1025
     *         h ^= words[i] * (i + 1);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1026
     *     return (int)((h >> 32) ^ h);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1027
     * }}</pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1028
     * Note that the hash code changes if the set of bits is altered.
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1029
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1030
     * @return the hash code value for this bit set
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1031
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1032
    public int hashCode() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1033
        long h = 1234;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1034
        for (int i = wordsInUse; --i >= 0; )
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1035
            h ^= words[i] * (i + 1);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1036
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1037
        return (int)((h >> 32) ^ h);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1038
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1039
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1040
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1041
     * Returns the number of bits of space actually in use by this
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1042
     * {@code BitSet} to represent bit values.
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1043
     * The maximum element in the set is the size - 1st element.
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1044
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1045
     * @return the number of bits currently in this bit set
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1046
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1047
    public int size() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1048
        return words.length * BITS_PER_WORD;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1049
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1050
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1051
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1052
     * Compares this object against the specified object.
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1053
     * The result is {@code true} if and only if the argument is
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1054
     * not {@code null} and is a {@code Bitset} object that has
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1055
     * exactly the same set of bits set to {@code true} as this bit
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1056
     * set. That is, for every nonnegative {@code int} index {@code k},
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1057
     * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1058
     * must be true. The current sizes of the two bit sets are not compared.
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1059
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1060
     * @param  obj the object to compare with
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1061
     * @return {@code true} if the objects are the same;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1062
     *         {@code false} otherwise
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1063
     * @see    #size()
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1064
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1065
    public boolean equals(Object obj) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1066
        if (!(obj instanceof BitSet))
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1067
            return false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1068
        if (this == obj)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1069
            return true;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1070
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1071
        BitSet set = (BitSet) obj;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1072
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1073
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1074
        set.checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1075
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1076
        if (wordsInUse != set.wordsInUse)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1077
            return false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1078
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1079
        // Check words in use by both BitSets
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1080
        for (int i = 0; i < wordsInUse; i++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1081
            if (words[i] != set.words[i])
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1082
                return false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1083
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1084
        return true;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1085
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1086
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1087
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1088
     * Cloning this {@code BitSet} produces a new {@code BitSet}
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1089
     * that is equal to it.
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1090
     * The clone of the bit set is another bit set that has exactly the
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1091
     * same bits set to {@code true} as this bit set.
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1092
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1093
     * @return a clone of this bit set
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1094
     * @see    #size()
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1095
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1096
    public Object clone() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1097
        if (! sizeIsSticky)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1098
            trimToSize();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1099
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1100
        try {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1101
            BitSet result = (BitSet) super.clone();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1102
            result.words = words.clone();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1103
            result.checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1104
            return result;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1105
        } catch (CloneNotSupportedException e) {
10419
12c063b39232 7084245: Update usages of InternalError to use exception chaining
sherman
parents: 5506
diff changeset
  1106
            throw new InternalError(e);
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1107
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1108
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1109
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1110
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1111
     * Attempts to reduce internal storage used for the bits in this bit set.
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1112
     * Calling this method may, but is not required to, affect the value
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1113
     * returned by a subsequent call to the {@link #size()} method.
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1114
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1115
    private void trimToSize() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1116
        if (wordsInUse != words.length) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1117
            words = Arrays.copyOf(words, wordsInUse);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1118
            checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1119
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1120
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1121
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1122
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1123
     * Save the state of the {@code BitSet} instance to a stream (i.e.,
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1124
     * serialize it).
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1125
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1126
    private void writeObject(ObjectOutputStream s)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1127
        throws IOException {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1128
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1129
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1130
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1131
        if (! sizeIsSticky)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1132
            trimToSize();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1133
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1134
        ObjectOutputStream.PutField fields = s.putFields();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1135
        fields.put("bits", words);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1136
        s.writeFields();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1137
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1138
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1139
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1140
     * Reconstitute the {@code BitSet} instance from a stream (i.e.,
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1141
     * deserialize it).
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1142
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1143
    private void readObject(ObjectInputStream s)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1144
        throws IOException, ClassNotFoundException {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1145
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1146
        ObjectInputStream.GetField fields = s.readFields();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1147
        words = (long[]) fields.get("bits", null);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1148
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1149
        // Assume maximum length then find real length
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1150
        // because recalculateWordsInUse assumes maintenance
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1151
        // or reduction in logical size
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1152
        wordsInUse = words.length;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1153
        recalculateWordsInUse();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1154
        sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1155
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1156
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1157
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1158
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1159
     * Returns a string representation of this bit set. For every index
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1160
     * for which this {@code BitSet} contains a bit in the set
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1161
     * state, the decimal representation of that index is included in
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1162
     * the result. Such indices are listed in order from lowest to
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1163
     * highest, separated by ",&nbsp;" (a comma and a space) and
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1164
     * surrounded by braces, resulting in the usual mathematical
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1165
     * notation for a set of integers.
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1166
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1167
     * <p>Example:
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1168
     * <pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1169
     * BitSet drPepper = new BitSet();</pre>
21334
c60dfce46a77 8026982: javadoc errors in core libs
rriggs
parents: 18829
diff changeset
  1170
     * Now {@code drPepper.toString()} returns "{@code {}}".
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1171
     * <pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1172
     * drPepper.set(2);</pre>
21334
c60dfce46a77 8026982: javadoc errors in core libs
rriggs
parents: 18829
diff changeset
  1173
     * Now {@code drPepper.toString()} returns "{@code {2}}".
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1174
     * <pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1175
     * drPepper.set(4);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1176
     * drPepper.set(10);</pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1177
     * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1178
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1179
     * @return a string representation of this bit set
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1180
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1181
    public String toString() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1182
        checkInvariants();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1183
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1184
        int numBits = (wordsInUse > 128) ?
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1185
            cardinality() : wordsInUse * BITS_PER_WORD;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1186
        StringBuilder b = new StringBuilder(6*numBits + 2);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1187
        b.append('{');
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1188
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1189
        int i = nextSetBit(0);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1190
        if (i != -1) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1191
            b.append(i);
24257
f524e23d7f7b 8040806: BitSet.toString() can throw IndexOutOfBoundsException
igerasim
parents: 23010
diff changeset
  1192
            while (true) {
f524e23d7f7b 8040806: BitSet.toString() can throw IndexOutOfBoundsException
igerasim
parents: 23010
diff changeset
  1193
                if (++i < 0) break;
f524e23d7f7b 8040806: BitSet.toString() can throw IndexOutOfBoundsException
igerasim
parents: 23010
diff changeset
  1194
                if ((i = nextSetBit(i)) < 0) break;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1195
                int endOfRun = nextClearBit(i);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1196
                do { b.append(", ").append(i); }
24257
f524e23d7f7b 8040806: BitSet.toString() can throw IndexOutOfBoundsException
igerasim
parents: 23010
diff changeset
  1197
                while (++i != endOfRun);
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1198
            }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1199
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1200
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1201
        b.append('}');
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1202
        return b.toString();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1203
    }
17421
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1204
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1205
    /**
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1206
     * Returns a stream of indices for which this {@code BitSet}
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1207
     * contains a bit in the set state. The indices are returned
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1208
     * in order, from lowest to highest. The size of the stream
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1209
     * is the number of bits in the set state, equal to the value
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1210
     * returned by the {@link #cardinality()} method.
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1211
     *
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1212
     * <p>The bit set must remain constant during the execution of the
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1213
     * terminal stream operation.  Otherwise, the result of the terminal
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1214
     * stream operation is undefined.
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1215
     *
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1216
     * @return a stream of integers representing set indices
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1217
     * @since 1.8
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1218
     */
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1219
    public IntStream stream() {
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1220
        class BitSetIterator implements PrimitiveIterator.OfInt {
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1221
            int next = nextSetBit(0);
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1222
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1223
            @Override
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1224
            public boolean hasNext() {
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1225
                return next != -1;
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1226
            }
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1227
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1228
            @Override
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1229
            public int nextInt() {
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1230
                if (next != -1) {
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1231
                    int ret = next;
29816
43ad6bf3975b 8076442: Cannot fully read BitSet.stream() if bit Integer.MAX_VALUE is set
chegar
parents: 25859
diff changeset
  1232
                    next = (next == Integer.MAX_VALUE) ? -1 : nextSetBit(next+1);
17421
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1233
                    return ret;
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1234
                } else {
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1235
                    throw new NoSuchElementException();
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1236
                }
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1237
            }
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1238
        }
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1239
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1240
        return StreamSupport.intStream(
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1241
                () -> Spliterators.spliterator(
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1242
                        new BitSetIterator(), cardinality(),
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1243
                        Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED),
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1244
                Spliterator.SIZED | Spliterator.SUBSIZED |
18822
4b6be7c19547 8019395: Consolidate StreamSupport.{stream,parallelStream} into a single method
psandoz
parents: 17421
diff changeset
  1245
                        Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED,
4b6be7c19547 8019395: Consolidate StreamSupport.{stream,parallelStream} into a single method
psandoz
parents: 17421
diff changeset
  1246
                false);
17421
f3fbcfe6e2cf 8012645: Stream methods on BitSet, Random, ThreadLocalRandom, ZipFile
mduigou
parents: 14342
diff changeset
  1247
    }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1248
}