| Frames | No Frames |
1: /* BitSet.java -- A vector of bits. 2: Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc. 3: 4: This file is part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; see the file COPYING. If not, write to the 18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19: 02110-1301 USA. 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: package java.util; 39: 40: import gnu.java.lang.CPStringBuilder; 41: 42: import java.io.Serializable; 43: 44: /* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3 45: * hashCode algorithm taken from JDK 1.2 docs. 46: */ 47: 48: /** 49: * This class can be thought of in two ways. You can see it as a 50: * vector of bits or as a set of non-negative integers. The name 51: * <code>BitSet</code> is a bit misleading. 52: * 53: * It is implemented by a bit vector, but its equally possible to see 54: * it as set of non-negative integer; each integer in the set is 55: * represented by a set bit at the corresponding index. The size of 56: * this structure is determined by the highest integer in the set. 57: * 58: * You can union, intersect and build (symmetric) remainders, by 59: * invoking the logical operations and, or, andNot, resp. xor. 60: * 61: * This implementation is NOT synchronized against concurrent access from 62: * multiple threads. Specifically, if one thread is reading from a bitset 63: * while another thread is simultaneously modifying it, the results are 64: * undefined. 65: * 66: * @author Jochen Hoenicke 67: * @author Tom Tromey (tromey@cygnus.com) 68: * @author Eric Blake (ebb9@email.byu.edu) 69: * @status updated to 1.4 70: */ 71: public class BitSet implements Cloneable, Serializable 72: { 73: /** 74: * Compatible with JDK 1.0. 75: */ 76: private static final long serialVersionUID = 7997698588986878753L; 77: 78: /** 79: * A common mask. 80: */ 81: private static final int LONG_MASK = 0x3f; 82: 83: /** 84: * The actual bits. 85: * @serial the i'th bit is in bits[i/64] at position i%64 (where position 86: * 0 is the least significant). 87: */ 88: private long[] bits; 89: 90: /** 91: * Create a new empty bit set. All bits are initially false. 92: */ 93: public BitSet() 94: { 95: this(64); 96: } 97: 98: /** 99: * 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: }