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