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