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 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 * @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 JDK1.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 JDK1.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 * }}</pre>
700 *
701 * @param fromIndex the index to start checking from (inclusive)
702 * @return the index of the next set bit, or {@code -1} if there
703 * is no such bit
704 * @throws IndexOutOfBoundsException if the specified index is negative
705 * @since 1.4
706 */
707 public int nextSetBit(int fromIndex) {
708 if (fromIndex < 0)
709 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
710
711 checkInvariants();
712
713 int u = wordIndex(fromIndex);
714 if (u >= wordsInUse)
715 return -1;
716
717 long word = words[u] & (WORD_MASK << fromIndex);
718
719 while (true) {
720 if (word != 0)
721 return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
722 if (++u == wordsInUse)
723 return -1;
724 word = words[u];
725 }
726 }
727
728 /**
729 * Returns the index of the first bit that is set to {@code false}
730 * that occurs on or after the specified starting index.
731 *
732 * @param fromIndex the index to start checking from (inclusive)
733 * @return the index of the next clear bit
734 * @throws IndexOutOfBoundsException if the specified index is negative
735 * @since 1.4
736 */
737 public int nextClearBit(int fromIndex) {
738 // Neither spec nor implementation handle bitsets of maximal length.
739 // See 4816253.
740 if (fromIndex < 0)
741 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
742
743 checkInvariants();
744
745 int u = wordIndex(fromIndex);
746 if (u >= wordsInUse)
747 return fromIndex;
748
749 long word = ~words[u] & (WORD_MASK << fromIndex);
750
751 while (true) {
752 if (word != 0)
753 return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
754 if (++u == wordsInUse)
755 return wordsInUse * BITS_PER_WORD;
756 word = ~words[u];
757 }
758 }
759
760 /**
761 * Returns the index of the nearest bit that is set to {@code true}
762 * that occurs on or before the specified starting index.
763 * If no such bit exists, or if {@code -1} is given as the
764 * starting index, then {@code -1} is returned.
765 *
766 * <p>To iterate over the {@code true} bits in a {@code BitSet},
767 * use the following loop:
768 *
769 * <pre> {@code
770 * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
771 * // operate on index i here
772 * }}</pre>
773 *
774 * @param fromIndex the index to start checking from (inclusive)
775 * @return the index of the previous set bit, or {@code -1} if there
776 * is no such bit
777 * @throws IndexOutOfBoundsException if the specified index is less
778 * than {@code -1}
779 * @since 1.7
780 */
781 public int previousSetBit(int fromIndex) {
782 if (fromIndex < 0) {
783 if (fromIndex == -1)
784 return -1;
785 throw new IndexOutOfBoundsException(
786 "fromIndex < -1: " + fromIndex);
787 }
788
789 checkInvariants();
790
791 int u = wordIndex(fromIndex);
792 if (u >= wordsInUse)
793 return length() - 1;
794
795 long word = words[u] & (WORD_MASK >>> -(fromIndex+1));
796
797 while (true) {
798 if (word != 0)
799 return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
800 if (u-- == 0)
801 return -1;
802 word = words[u];
803 }
804 }
805
806 /**
807 * Returns the index of the nearest bit that is set to {@code false}
808 * that occurs on or before the specified starting index.
809 * If no such bit exists, or if {@code -1} is given as the
810 * starting index, then {@code -1} is returned.
811 *
812 * @param fromIndex the index to start checking from (inclusive)
813 * @return the index of the previous clear bit, or {@code -1} if there
814 * is no such bit
815 * @throws IndexOutOfBoundsException if the specified index is less
816 * than {@code -1}
817 * @since 1.7
818 */
819 public int previousClearBit(int fromIndex) {
820 if (fromIndex < 0) {
821 if (fromIndex == -1)
822 return -1;
823 throw new IndexOutOfBoundsException(
824 "fromIndex < -1: " + fromIndex);
825 }
826
827 checkInvariants();
828
829 int u = wordIndex(fromIndex);
830 if (u >= wordsInUse)
831 return fromIndex;
832
833 long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1));
834
835 while (true) {
836 if (word != 0)
837 return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);
838 if (u-- == 0)
839 return -1;
840 word = ~words[u];
841 }
842 }
843
844 /**
845 * Returns the "logical size" of this {@code BitSet}: the index of
846 * the highest set bit in the {@code BitSet} plus one. Returns zero
847 * if the {@code BitSet} contains no set bits.
848 *
849 * @return the logical size of this {@code BitSet}
850 * @since 1.2
851 */
852 public int length() {
853 if (wordsInUse == 0)
854 return 0;
855
856 return BITS_PER_WORD * (wordsInUse - 1) +
857 (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
858 }
859
860 /**
861 * Returns true if this {@code BitSet} contains no bits that are set
862 * to {@code true}.
863 *
864 * @return boolean indicating whether this {@code BitSet} is empty
865 * @since 1.4
866 */
867 public boolean isEmpty() {
868 return wordsInUse == 0;
869 }
870
871 /**
872 * Returns true if the specified {@code BitSet} has any bits set to
873 * {@code true} that are also set to {@code true} in this {@code BitSet}.
874 *
875 * @param set {@code BitSet} to intersect with
876 * @return boolean indicating whether this {@code BitSet} intersects
877 * the specified {@code BitSet}
878 * @since 1.4
879 */
880 public boolean intersects(BitSet set) {
881 for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
882 if ((words[i] & set.words[i]) != 0)
883 return true;
884 return false;
885 }
886
887 /**
888 * Returns the number of bits set to {@code true} in this {@code BitSet}.
889 *
890 * @return the number of bits set to {@code true} in this {@code BitSet}
891 * @since 1.4
892 */
893 public int cardinality() {
894 int sum = 0;
895 for (int i = 0; i < wordsInUse; i++)
896 sum += Long.bitCount(words[i]);
897 return sum;
898 }
899
900 /**
901 * Performs a logical <b>AND</b> of this target bit set with the
902 * argument bit set. This bit set is modified so that each bit in it
903 * has the value {@code true} if and only if it both initially
904 * had the value {@code true} and the corresponding bit in the
905 * bit set argument also had the value {@code true}.
906 *
907 * @param set a bit set
908 */
909 public void and(BitSet set) {
910 if (this == set)
911 return;
912
913 while (wordsInUse > set.wordsInUse)
914 words[--wordsInUse] = 0;
915
916 // Perform logical AND on words in common
917 for (int i = 0; i < wordsInUse; i++)
918 words[i] &= set.words[i];
919
920 recalculateWordsInUse();
921 checkInvariants();
922 }
923
924 /**
925 * Performs a logical <b>OR</b> of this bit set with the bit set
926 * argument. This bit set is modified so that a bit in it has the
927 * value {@code true} if and only if it either already had the
928 * value {@code true} or the corresponding bit in the bit set
929 * argument has the value {@code true}.
930 *
931 * @param set a bit set
932 */
933 public void or(BitSet set) {
934 if (this == set)
935 return;
936
937 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
938
939 if (wordsInUse < set.wordsInUse) {
940 ensureCapacity(set.wordsInUse);
941 wordsInUse = set.wordsInUse;
942 }
943
944 // Perform logical OR on words in common
945 for (int i = 0; i < wordsInCommon; i++)
946 words[i] |= set.words[i];
947
948 // Copy any remaining words
949 if (wordsInCommon < set.wordsInUse)
950 System.arraycopy(set.words, wordsInCommon,
951 words, wordsInCommon,
952 wordsInUse - wordsInCommon);
953
954 // recalculateWordsInUse() is unnecessary
955 checkInvariants();
956 }
957
958 /**
959 * Performs a logical <b>XOR</b> of this bit set with the bit set
960 * argument. This bit set is modified so that a bit in it has the
961 * value {@code true} if and only if one of the following
962 * statements holds:
963 * <ul>
964 * <li>The bit initially has the value {@code true}, and the
965 * corresponding bit in the argument has the value {@code false}.
966 * <li>The bit initially has the value {@code false}, and the
967 * corresponding bit in the argument has the value {@code true}.
968 * </ul>
969 *
970 * @param set a bit set
971 */
972 public void xor(BitSet set) {
973 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
974
975 if (wordsInUse < set.wordsInUse) {
976 ensureCapacity(set.wordsInUse);
977 wordsInUse = set.wordsInUse;
978 }
979
980 // Perform logical XOR on words in common
981 for (int i = 0; i < wordsInCommon; i++)
982 words[i] ^= set.words[i];
983
984 // Copy any remaining words
985 if (wordsInCommon < set.wordsInUse)
986 System.arraycopy(set.words, wordsInCommon,
987 words, wordsInCommon,
988 set.wordsInUse - wordsInCommon);
989
990 recalculateWordsInUse();
991 checkInvariants();
992 }
993
994 /**
995 * Clears all of the bits in this {@code BitSet} whose corresponding
996 * bit is set in the specified {@code BitSet}.
997 *
998 * @param set the {@code BitSet} with which to mask this
999 * {@code BitSet}
1000 * @since 1.2
1001 */
1002 public void andNot(BitSet set) {
1003 // Perform logical (a & !b) on words in common
1004 for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
1005 words[i] &= ~set.words[i];
1006
1007 recalculateWordsInUse();
1008 checkInvariants();
1009 }
1010
1011 /**
1012 * Returns the hash code value for this bit set. The hash code depends
1013 * only on which bits are set within this {@code BitSet}.
1014 *
1015 * <p>The hash code is defined to be the result of the following
1016 * calculation:
1017 * <pre> {@code
1018 * public int hashCode() {
1019 * long h = 1234;
1020 * long[] words = toLongArray();
1021 * for (int i = words.length; --i >= 0; )
1022 * h ^= words[i] * (i + 1);
1023 * return (int)((h >> 32) ^ h);
1024 * }}</pre>
1025 * Note that the hash code changes if the set of bits is altered.
1026 *
1027 * @return the hash code value for this bit set
1028 */
1029 public int hashCode() {
1030 long h = 1234;
1031 for (int i = wordsInUse; --i >= 0; )
1032 h ^= words[i] * (i + 1);
1033
1034 return (int)((h >> 32) ^ h);
1035 }
1036
1037 /**
1038 * Returns the number of bits of space actually in use by this
1039 * {@code BitSet} to represent bit values.
1040 * The maximum element in the set is the size - 1st element.
1041 *
1042 * @return the number of bits currently in this bit set
1043 */
1044 public int size() {
1045 return words.length * BITS_PER_WORD;
1046 }
1047
1048 /**
1049 * Compares this object against the specified object.
1050 * The result is {@code true} if and only if the argument is
1051 * not {@code null} and is a {@code Bitset} object that has
1052 * exactly the same set of bits set to {@code true} as this bit
1053 * set. That is, for every nonnegative {@code int} index {@code k},
1054 * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
1055 * must be true. The current sizes of the two bit sets are not compared.
1056 *
1057 * @param obj the object to compare with
1058 * @return {@code true} if the objects are the same;
1059 * {@code false} otherwise
1060 * @see #size()
1061 */
1062 public boolean equals(Object obj) {
1063 if (!(obj instanceof BitSet))
1064 return false;
1065 if (this == obj)
1066 return true;
1067
1068 BitSet set = (BitSet) obj;
1069
1070 checkInvariants();
1071 set.checkInvariants();
1072
1073 if (wordsInUse != set.wordsInUse)
1074 return false;
1075
1076 // Check words in use by both BitSets
1077 for (int i = 0; i < wordsInUse; i++)
1078 if (words[i] != set.words[i])
1079 return false;
1080
1081 return true;
1082 }
1083
1084 /**
1085 * Cloning this {@code BitSet} produces a new {@code BitSet}
1086 * that is equal to it.
1087 * The clone of the bit set is another bit set that has exactly the
1088 * same bits set to {@code true} as this bit set.
1089 *
1090 * @return a clone of this bit set
1091 * @see #size()
1092 */
1093 public Object clone() {
1094 if (! sizeIsSticky)
1095 trimToSize();
1096
1097 try {
1098 BitSet result = (BitSet) super.clone();
1099 result.words = words.clone();
1100 result.checkInvariants();
1101 return result;
1102 } catch (CloneNotSupportedException e) {
1103 throw new InternalError(e);
1104 }
1105 }
1106
1107 /**
1108 * Attempts to reduce internal storage used for the bits in this bit set.
1109 * Calling this method may, but is not required to, affect the value
1110 * returned by a subsequent call to the {@link #size()} method.
1111 */
1112 private void trimToSize() {
1113 if (wordsInUse != words.length) {
1114 words = Arrays.copyOf(words, wordsInUse);
1115 checkInvariants();
1116 }
1117 }
1118
1119 /**
1120 * Save the state of the {@code BitSet} instance to a stream (i.e.,
1121 * serialize it).
1122 */
1123 private void writeObject(ObjectOutputStream s)
1124 throws IOException {
1125
1126 checkInvariants();
1127
1128 if (! sizeIsSticky)
1129 trimToSize();
1130
1131 ObjectOutputStream.PutField fields = s.putFields();
1132 fields.put("bits", words);
1133 s.writeFields();
1134 }
1135
1136 /**
1137 * Reconstitute the {@code BitSet} instance from a stream (i.e.,
1138 * deserialize it).
1139 */
1140 private void readObject(ObjectInputStream s)
1141 throws IOException, ClassNotFoundException {
1142
1143 ObjectInputStream.GetField fields = s.readFields();
1144 words = (long[]) fields.get("bits", null);
1145
1146 // Assume maximum length then find real length
1147 // because recalculateWordsInUse assumes maintenance
1148 // or reduction in logical size
1149 wordsInUse = words.length;
1150 recalculateWordsInUse();
1151 sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic
1152 checkInvariants();
1153 }
1154
1155 /**
1156 * Returns a string representation of this bit set. For every index
1157 * for which this {@code BitSet} contains a bit in the set
1158 * state, the decimal representation of that index is included in
1159 * the result. Such indices are listed in order from lowest to
1160 * highest, separated by ", " (a comma and a space) and
1161 * surrounded by braces, resulting in the usual mathematical
1162 * notation for a set of integers.
1163 *
1164 * <p>Example:
1165 * <pre>
1166 * BitSet drPepper = new BitSet();</pre>
1167 * Now {@code drPepper.toString()} returns "{@code {}}".
1168 * <pre>
1169 * drPepper.set(2);</pre>
1170 * Now {@code drPepper.toString()} returns "{@code {2}}".
1171 * <pre>
1172 * drPepper.set(4);
1173 * drPepper.set(10);</pre>
1174 * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
1175 *
1176 * @return a string representation of this bit set
1177 */
1178 public String toString() {
1179 checkInvariants();
1180
1181 int numBits = (wordsInUse > 128) ?
1182 cardinality() : wordsInUse * BITS_PER_WORD;
1183 StringBuilder b = new StringBuilder(6*numBits + 2);
1184 b.append('{');
1185
1186 int i = nextSetBit(0);
1187 if (i != -1) {
1188 b.append(i);
1189 while (true) {
1190 if (++i < 0) break;
1191 if ((i = nextSetBit(i)) < 0) break;
1192 int endOfRun = nextClearBit(i);
1193 do { b.append(", ").append(i); }
1194 while (++i != endOfRun);
1195 }
1196 }
1197
1198 b.append('}');
1199 return b.toString();
1200 }
1201
1202 /**
1203 * Returns a stream of indices for which this {@code BitSet}
1204 * contains a bit in the set state. The indices are returned
1205 * in order, from lowest to highest. The size of the stream
1206 * is the number of bits in the set state, equal to the value
1207 * returned by the {@link #cardinality()} method.
1208 *
1209 * <p>The bit set must remain constant during the execution of the
1210 * terminal stream operation. Otherwise, the result of the terminal
1211 * stream operation is undefined.
1212 *
1213 * @return a stream of integers representing set indices
1214 * @since 1.8
1215 */
1216 public IntStream stream() {
1217 class BitSetIterator implements PrimitiveIterator.OfInt {
1218 int next = nextSetBit(0);
1219
1220 @Override
1221 public boolean hasNext() {
1222 return next != -1;
1223 }
1224
1225 @Override
1226 public int nextInt() {
1227 if (next != -1) {
1228 int ret = next;
1229 next = nextSetBit(next+1);
1230 return ret;
1231 } else {
1232 throw new NoSuchElementException();
1233 }
1234 }
1235 }
1236
1237 return StreamSupport.intStream(
1238 () -> Spliterators.spliterator(
1239 new BitSetIterator(), cardinality(),
1240 Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED),
1241 Spliterator.SIZED | Spliterator.SUBSIZED |
1242 Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED,
1243 false);
1244 }
1245 }