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