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