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