001/* BitSet.java -- A vector of bits. 002 Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc. 003 004This file is part of GNU Classpath. 005 006GNU Classpath is free software; you can redistribute it and/or modify 007it under the terms of the GNU General Public License as published by 008the Free Software Foundation; either version 2, or (at your option) 009any later version. 010 011GNU Classpath is distributed in the hope that it will be useful, but 012WITHOUT ANY WARRANTY; without even the implied warranty of 013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 014General Public License for more details. 015 016You should have received a copy of the GNU General Public License 017along with GNU Classpath; see the file COPYING. If not, write to the 018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 01902110-1301 USA. 020 021Linking this library statically or dynamically with other modules is 022making a combined work based on this library. Thus, the terms and 023conditions of the GNU General Public License cover the whole 024combination. 025 026As a special exception, the copyright holders of this library give you 027permission to link this library with independent modules to produce an 028executable, regardless of the license terms of these independent 029modules, and to copy and distribute the resulting executable under 030terms of your choice, provided that you also meet, for each linked 031independent module, the terms and conditions of the license of that 032module. An independent module is a module which is not derived from 033or based on this library. If you modify this library, you may extend 034this exception to your version of the library, but you are not 035obligated to do so. If you do not wish to do so, delete this 036exception statement from your version. */ 037 038package java.util; 039 040import gnu.java.lang.CPStringBuilder; 041 042import java.io.Serializable; 043 044/* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3 045 * hashCode algorithm taken from JDK 1.2 docs. 046 */ 047 048/** 049 * This class can be thought of in two ways. You can see it as a 050 * vector of bits or as a set of non-negative integers. The name 051 * <code>BitSet</code> is a bit misleading. 052 * 053 * It is implemented by a bit vector, but its equally possible to see 054 * it as set of non-negative integer; each integer in the set is 055 * represented by a set bit at the corresponding index. The size of 056 * this structure is determined by the highest integer in the set. 057 * 058 * You can union, intersect and build (symmetric) remainders, by 059 * invoking the logical operations and, or, andNot, resp. xor. 060 * 061 * This implementation is NOT synchronized against concurrent access from 062 * multiple threads. Specifically, if one thread is reading from a bitset 063 * while another thread is simultaneously modifying it, the results are 064 * undefined. 065 * 066 * @author Jochen Hoenicke 067 * @author Tom Tromey (tromey@cygnus.com) 068 * @author Eric Blake (ebb9@email.byu.edu) 069 * @status updated to 1.4 070 */ 071public class BitSet implements Cloneable, Serializable 072{ 073 /** 074 * Compatible with JDK 1.0. 075 */ 076 private static final long serialVersionUID = 7997698588986878753L; 077 078 /** 079 * A common mask. 080 */ 081 private static final int LONG_MASK = 0x3f; 082 083 /** 084 * The actual bits. 085 * @serial the i'th bit is in bits[i/64] at position i%64 (where position 086 * 0 is the least significant). 087 */ 088 private long[] bits; 089 090 /** 091 * Create a new empty bit set. All bits are initially false. 092 */ 093 public BitSet() 094 { 095 this(64); 096 } 097 098 /** 099 * Create a new empty bit set, with a given size. This 100 * constructor reserves enough space to represent the integers 101 * from <code>0</code> to <code>nbits-1</code>. 102 * 103 * @param nbits the initial size of the bit set 104 * @throws NegativeArraySizeException if nbits < 0 105 */ 106 public BitSet(int nbits) 107 { 108 if (nbits < 0) 109 throw new NegativeArraySizeException(); 110 111 int length = nbits >>> 6; 112 if ((nbits & LONG_MASK) != 0) 113 ++length; 114 bits = new long[length]; 115 } 116 117 /** 118 * Performs the logical AND operation on this bit set and the 119 * given <code>set</code>. This means it builds the intersection 120 * of the two sets. The result is stored into this bit set. 121 * 122 * @param bs the second bit set 123 * @throws NullPointerException if bs is null 124 */ 125 public void and(BitSet bs) 126 { 127 int max = Math.min(bits.length, bs.bits.length); 128 int i; 129 for (i = 0; i < max; ++i) 130 bits[i] &= bs.bits[i]; 131 while (i < bits.length) 132 bits[i++] = 0; 133 } 134 135 /** 136 * Performs the logical AND operation on this bit set and the 137 * complement of the given <code>bs</code>. This means it 138 * selects every element in the first set, that isn't in the 139 * second set. The result is stored into this bit set and is 140 * effectively the set difference of the two. 141 * 142 * @param bs the second bit set 143 * @throws NullPointerException if bs is null 144 * @since 1.2 145 */ 146 public void andNot(BitSet bs) 147 { 148 int i = Math.min(bits.length, bs.bits.length); 149 while (--i >= 0) 150 bits[i] &= ~bs.bits[i]; 151 } 152 153 /** 154 * Returns the number of bits set to true. 155 * 156 * @return the number of true bits 157 * @since 1.4 158 */ 159 public int cardinality() 160 { 161 int card = 0; 162 for (int i = bits.length - 1; i >= 0; i--) 163 { 164 long a = bits[i]; 165 // Take care of common cases. 166 if (a == 0) 167 continue; 168 if (a == -1) 169 { 170 card += 64; 171 continue; 172 } 173 174 // Successively collapse alternating bit groups into a sum. 175 a = ((a >> 1) & 0x5555555555555555L) + (a & 0x5555555555555555L); 176 a = ((a >> 2) & 0x3333333333333333L) + (a & 0x3333333333333333L); 177 int b = (int) ((a >>> 32) + a); 178 b = ((b >> 4) & 0x0f0f0f0f) + (b & 0x0f0f0f0f); 179 b = ((b >> 8) & 0x00ff00ff) + (b & 0x00ff00ff); 180 card += ((b >> 16) & 0x0000ffff) + (b & 0x0000ffff); 181 } 182 return card; 183 } 184 185 /** 186 * Sets all bits in the set to false. 187 * 188 * @since 1.4 189 */ 190 public void clear() 191 { 192 Arrays.fill(bits, 0); 193 } 194 195 /** 196 * Removes the integer <code>pos</code> from this set. That is 197 * the corresponding bit is cleared. If the index is not in the set, 198 * this method does nothing. 199 * 200 * @param pos a non-negative integer 201 * @throws IndexOutOfBoundsException if pos < 0 202 */ 203 public void clear(int pos) 204 { 205 int offset = pos >> 6; 206 ensure(offset); 207 // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException, 208 // so we'll just let that be our exception. 209 bits[offset] &= ~(1L << pos); 210 } 211 212 /** 213 * Sets the bits between from (inclusive) and to (exclusive) to false. 214 * 215 * @param from the start range (inclusive) 216 * @param to the end range (exclusive) 217 * @throws IndexOutOfBoundsException if from < 0 || to < 0 || 218 * from > to 219 * @since 1.4 220 */ 221 public void clear(int from, int to) 222 { 223 if (from < 0 || from > to) 224 throw new IndexOutOfBoundsException(); 225 if (from == to) 226 return; 227 int lo_offset = from >>> 6; 228 int hi_offset = to >>> 6; 229 ensure(hi_offset); 230 if (lo_offset == hi_offset) 231 { 232 bits[hi_offset] &= ((1L << from) - 1) | (-1L << to); 233 return; 234 } 235 236 bits[lo_offset] &= (1L << from) - 1; 237 bits[hi_offset] &= -1L << to; 238 for (int i = lo_offset + 1; i < hi_offset; i++) 239 bits[i] = 0; 240 } 241 242 /** 243 * Create a clone of this bit set, that is an instance of the same 244 * class and contains the same elements. But it doesn't change when 245 * this bit set changes. 246 * 247 * @return the clone of this object. 248 */ 249 public Object clone() 250 { 251 try 252 { 253 BitSet bs = (BitSet) super.clone(); 254 bs.bits = (long[]) bits.clone(); 255 return bs; 256 } 257 catch (CloneNotSupportedException e) 258 { 259 // Impossible to get here. 260 return null; 261 } 262 } 263 264 /** 265 * Returns true if the <code>obj</code> is a bit set that contains 266 * exactly the same elements as this bit set, otherwise false. 267 * 268 * @param obj the object to compare to 269 * @return true if obj equals this bit set 270 */ 271 public boolean equals(Object obj) 272 { 273 if (!(obj instanceof BitSet)) 274 return false; 275 BitSet bs = (BitSet) obj; 276 int max = Math.min(bits.length, bs.bits.length); 277 int i; 278 for (i = 0; i < max; ++i) 279 if (bits[i] != bs.bits[i]) 280 return false; 281 // If one is larger, check to make sure all extra bits are 0. 282 for (int j = i; j < bits.length; ++j) 283 if (bits[j] != 0) 284 return false; 285 for (int j = i; j < bs.bits.length; ++j) 286 if (bs.bits[j] != 0) 287 return false; 288 return true; 289 } 290 291 /** 292 * Sets the bit at the index to the opposite value. 293 * 294 * @param index the index of the bit 295 * @throws IndexOutOfBoundsException if index is negative 296 * @since 1.4 297 */ 298 public void flip(int index) 299 { 300 int offset = index >> 6; 301 ensure(offset); 302 // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException, 303 // so we'll just let that be our exception. 304 bits[offset] ^= 1L << index; 305 } 306 307 /** 308 * Sets a range of bits to the opposite value. 309 * 310 * @param from the low index (inclusive) 311 * @param to the high index (exclusive) 312 * @throws IndexOutOfBoundsException if from > to || from < 0 || 313 * to < 0 314 * @since 1.4 315 */ 316 public void flip(int from, int to) 317 { 318 if (from < 0 || from > to) 319 throw new IndexOutOfBoundsException(); 320 if (from == to) 321 return; 322 int lo_offset = from >>> 6; 323 int hi_offset = to >>> 6; 324 ensure(hi_offset); 325 if (lo_offset == hi_offset) 326 { 327 bits[hi_offset] ^= (-1L << from) & ((1L << to) - 1); 328 return; 329 } 330 331 bits[lo_offset] ^= -1L << from; 332 bits[hi_offset] ^= (1L << to) - 1; 333 for (int i = lo_offset + 1; i < hi_offset; i++) 334 bits[i] ^= -1; 335 } 336 337 /** 338 * Returns true if the integer <code>bitIndex</code> is in this bit 339 * set, otherwise false. 340 * 341 * @param pos a non-negative integer 342 * @return the value of the bit at the specified position 343 * @throws IndexOutOfBoundsException if the pos is negative 344 */ 345 public boolean get(int pos) 346 { 347 int offset = pos >> 6; 348 if (offset >= bits.length) 349 return false; 350 // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException, 351 // so we'll just let that be our exception. 352 return (bits[offset] & (1L << pos)) != 0; 353 } 354 355 /** 356 * Returns a new <code>BitSet</code> composed of a range of bits from 357 * this one. 358 * 359 * @param from the low index (inclusive) 360 * @param to the high index (exclusive) 361 * @throws IndexOutOfBoundsException if from > to || from < 0 || 362 * to < 0 363 * @since 1.4 364 */ 365 public BitSet get(int from, int to) 366 { 367 if (from < 0 || from > to) 368 throw new IndexOutOfBoundsException(); 369 BitSet bs = new BitSet(to - from); 370 int lo_offset = from >>> 6; 371 if (lo_offset >= bits.length || to == from) 372 return bs; 373 374 int lo_bit = from & LONG_MASK; 375 int hi_offset = to >>> 6; 376 if (lo_bit == 0) 377 { 378 int len = Math.min(hi_offset - lo_offset + 1, bits.length - lo_offset); 379 System.arraycopy(bits, lo_offset, bs.bits, 0, len); 380 if (hi_offset < bits.length) 381 bs.bits[hi_offset - lo_offset] &= (1L << to) - 1; 382 return bs; 383 } 384 385 int len = Math.min(hi_offset, bits.length - 1); 386 int reverse = 64 - lo_bit; 387 int i; 388 for (i = 0; lo_offset < len; lo_offset++, i++) 389 bs.bits[i] = ((bits[lo_offset] >>> lo_bit) 390 | (bits[lo_offset + 1] << reverse)); 391 if ((to & LONG_MASK) > lo_bit) 392 bs.bits[i++] = bits[lo_offset] >>> lo_bit; 393 if (hi_offset < bits.length) 394 bs.bits[i - 1] &= (1L << (to - from)) - 1; 395 return bs; 396 } 397 398 /** 399 * Returns a hash code value for this bit set. The hash code of 400 * two bit sets containing the same integers is identical. The algorithm 401 * used to compute it is as follows: 402 * 403 * Suppose the bits in the BitSet were to be stored in an array of 404 * long integers called <code>bits</code>, in such a manner that 405 * bit <code>k</code> is set in the BitSet (for non-negative values 406 * of <code>k</code>) if and only if 407 * 408 * <code>((k/64) < bits.length) 409 * && ((bits[k/64] & (1L << (bit % 64))) != 0) 410 * </code> 411 * 412 * Then the following definition of the hashCode method 413 * would be a correct implementation of the actual algorithm: 414 * 415 * 416<pre>public int hashCode() 417{ 418 long h = 1234; 419 for (int i = bits.length-1; i >= 0; i--) 420 { 421 h ^= bits[i] * (i + 1); 422 } 423 424 return (int)((h >> 32) ^ h); 425}</pre> 426 * 427 * Note that the hash code values changes, if the set is changed. 428 * 429 * @return the hash code value for this bit set. 430 */ 431 public int hashCode() 432 { 433 long h = 1234; 434 for (int i = bits.length; i > 0; ) 435 h ^= i * bits[--i]; 436 return (int) ((h >> 32) ^ h); 437 } 438 439 /** 440 * Returns true if the specified BitSet and this one share at least one 441 * common true bit. 442 * 443 * @param set the set to check for intersection 444 * @return true if the sets intersect 445 * @throws NullPointerException if set is null 446 * @since 1.4 447 */ 448 public boolean intersects(BitSet set) 449 { 450 int i = Math.min(bits.length, set.bits.length); 451 while (--i >= 0) 452 if ((bits[i] & set.bits[i]) != 0) 453 return true; 454 return false; 455 } 456 457 /** 458 * Returns true if this set contains no true bits. 459 * 460 * @return true if all bits are false 461 * @since 1.4 462 */ 463 public boolean isEmpty() 464 { 465 for (int i = bits.length - 1; i >= 0; i--) 466 if (bits[i] != 0) 467 return false; 468 return true; 469 } 470 471 /** 472 * Returns the logical number of bits actually used by this bit 473 * set. It returns the index of the highest set bit plus one. 474 * Note that this method doesn't return the number of set bits. 475 * 476 * @return the index of the highest set bit plus one. 477 */ 478 public int length() 479 { 480 // Set i to highest index that contains a non-zero value. 481 int i; 482 for (i = bits.length - 1; i >= 0 && bits[i] == 0; --i) 483 ; 484 485 // if i < 0 all bits are cleared. 486 if (i < 0) 487 return 0; 488 489 // Now determine the exact length. 490 long b = bits[i]; 491 int len = (i + 1) * 64; 492 // b >= 0 checks if the highest bit is zero. 493 while (b >= 0) 494 { 495 --len; 496 b <<= 1; 497 } 498 499 return len; 500 } 501 502 /** 503 * Returns the index of the next false bit, from the specified bit 504 * (inclusive). 505 * 506 * @param from the start location 507 * @return the first false bit 508 * @throws IndexOutOfBoundsException if from is negative 509 * @since 1.4 510 */ 511 public int nextClearBit(int from) 512 { 513 int offset = from >> 6; 514 long mask = 1L << from; 515 while (offset < bits.length) 516 { 517 // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException, 518 // so we'll just let that be our exception. 519 long h = bits[offset]; 520 do 521 { 522 if ((h & mask) == 0) 523 return from; 524 mask <<= 1; 525 from++; 526 } 527 while (mask != 0); 528 mask = 1; 529 offset++; 530 } 531 return from; 532 } 533 534 /** 535 * Returns the index of the next true bit, from the specified bit 536 * (inclusive). If there is none, -1 is returned. You can iterate over 537 * all true bits with this loop:<br> 538 * 539<pre>for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) 540{ 541 // operate on i here 542}</pre> 543 * 544 * @param from the start location 545 * @return the first true bit, or -1 546 * @throws IndexOutOfBoundsException if from is negative 547 * @since 1.4 548 */ 549 public int nextSetBit(int from) 550 { 551 int offset = from >> 6; 552 long mask = 1L << from; 553 while (offset < bits.length) 554 { 555 // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException, 556 // so we'll just let that be our exception. 557 long h = bits[offset]; 558 do 559 { 560 if ((h & mask) != 0) 561 return from; 562 mask <<= 1; 563 from++; 564 } 565 while (mask != 0); 566 mask = 1; 567 offset++; 568 } 569 return -1; 570 } 571 572 /** 573 * Performs the logical OR operation on this bit set and the 574 * given <code>set</code>. This means it builds the union 575 * of the two sets. The result is stored into this bit set, which 576 * grows as necessary. 577 * 578 * @param bs the second bit set 579 * @throws NullPointerException if bs is null 580 */ 581 public void or(BitSet bs) 582 { 583 ensure(bs.bits.length - 1); 584 for (int i = bs.bits.length - 1; i >= 0; i--) 585 bits[i] |= bs.bits[i]; 586 } 587 588 /** 589 * Add the integer <code>bitIndex</code> to this set. That is 590 * the corresponding bit is set to true. If the index was already in 591 * the set, this method does nothing. The size of this structure 592 * is automatically increased as necessary. 593 * 594 * @param pos a non-negative integer. 595 * @throws IndexOutOfBoundsException if pos is negative 596 */ 597 public void set(int pos) 598 { 599 int offset = pos >> 6; 600 ensure(offset); 601 // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException, 602 // so we'll just let that be our exception. 603 bits[offset] |= 1L << pos; 604 } 605 606 /** 607 * Sets the bit at the given index to the specified value. The size of 608 * this structure is automatically increased as necessary. 609 * 610 * @param index the position to set 611 * @param value the value to set it to 612 * @throws IndexOutOfBoundsException if index is negative 613 * @since 1.4 614 */ 615 public void set(int index, boolean value) 616 { 617 if (value) 618 set(index); 619 else 620 clear(index); 621 } 622 623 /** 624 * Sets the bits between from (inclusive) and to (exclusive) to true. 625 * 626 * @param from the start range (inclusive) 627 * @param to the end range (exclusive) 628 * @throws IndexOutOfBoundsException if from < 0 || from > to || 629 * to < 0 630 * @since 1.4 631 */ 632 public void set(int from, int to) 633 { 634 if (from < 0 || from > to) 635 throw new IndexOutOfBoundsException(); 636 if (from == to) 637 return; 638 int lo_offset = from >>> 6; 639 int hi_offset = to >>> 6; 640 ensure(hi_offset); 641 if (lo_offset == hi_offset) 642 { 643 bits[hi_offset] |= (-1L << from) & ((1L << to) - 1); 644 return; 645 } 646 647 bits[lo_offset] |= -1L << from; 648 bits[hi_offset] |= (1L << to) - 1; 649 for (int i = lo_offset + 1; i < hi_offset; i++) 650 bits[i] = -1; 651 } 652 653 /** 654 * Sets the bits between from (inclusive) and to (exclusive) to the 655 * specified value. 656 * 657 * @param from the start range (inclusive) 658 * @param to the end range (exclusive) 659 * @param value the value to set it to 660 * @throws IndexOutOfBoundsException if from < 0 || from > to || 661 * to < 0 662 * @since 1.4 663 */ 664 public void set(int from, int to, boolean value) 665 { 666 if (value) 667 set(from, to); 668 else 669 clear(from, to); 670 } 671 672 /** 673 * Returns the number of bits actually used by this bit set. Note 674 * that this method doesn't return the number of set bits, and that 675 * future requests for larger bits will make this automatically grow. 676 * 677 * @return the number of bits currently used. 678 */ 679 public int size() 680 { 681 return bits.length * 64; 682 } 683 684 /** 685 * Returns the string representation of this bit set. This 686 * consists of a comma separated list of the integers in this set 687 * surrounded by curly braces. There is a space after each comma. 688 * A sample string is thus "{1, 3, 53}". 689 * @return the string representation. 690 */ 691 public String toString() 692 { 693 CPStringBuilder r = new CPStringBuilder("{"); 694 boolean first = true; 695 for (int i = 0; i < bits.length; ++i) 696 { 697 long bit = 1; 698 long word = bits[i]; 699 if (word == 0) 700 continue; 701 for (int j = 0; j < 64; ++j) 702 { 703 if ((word & bit) != 0) 704 { 705 if (! first) 706 r.append(", "); 707 r.append(64 * i + j); 708 first = false; 709 } 710 bit <<= 1; 711 } 712 } 713 return r.append("}").toString(); 714 } 715 716 /** 717 * Performs the logical XOR operation on this bit set and the 718 * given <code>set</code>. This means it builds the symmetric 719 * remainder of the two sets (the elements that are in one set, 720 * but not in the other). The result is stored into this bit set, 721 * which grows as necessary. 722 * 723 * @param bs the second bit set 724 * @throws NullPointerException if bs is null 725 */ 726 public void xor(BitSet bs) 727 { 728 ensure(bs.bits.length - 1); 729 for (int i = bs.bits.length - 1; i >= 0; i--) 730 bits[i] ^= bs.bits[i]; 731 } 732 733 /** 734 * Make sure the vector is big enough. 735 * 736 * @param lastElt the size needed for the bits array 737 */ 738 private void ensure(int lastElt) 739 { 740 if (lastElt >= bits.length) 741 { 742 long[] nd = new long[lastElt + 1]; 743 System.arraycopy(bits, 0, nd, 0, bits.length); 744 bits = nd; 745 } 746 } 747 748 // This is used by EnumSet for efficiency. 749 final boolean containsAll(BitSet other) 750 { 751 for (int i = other.bits.length - 1; i >= 0; i--) 752 { 753 if ((bits[i] & other.bits[i]) != other.bits[i]) 754 return false; 755 } 756 return true; 757 } 758}