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