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