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