| GNU Classpath (0.95) | |
| 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: import java.io.Serializable; 40: 41: /* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3 42: * hashCode algorithm taken from JDK 1.2 docs. 43: */ 44: 45: /** 46: * This class can be thought of in two ways. You can see it as a 47: * vector of bits or as a set of non-negative integers. The name 48: * <code>BitSet</code> is a bit misleading. 49: * 50: * It is implemented by a bit vector, but its equally possible to see 51: * it as set of non-negative integer; each integer in the set is 52: * represented by a set bit at the corresponding index. The size of 53: * this structure is determined by the highest integer in the set. 54: * 55: * You can union, intersect and build (symmetric) remainders, by 56: * invoking the logical operations and, or, andNot, resp. xor. 57: * 58: * This implementation is NOT synchronized against concurrent access from 59: * multiple threads. Specifically, if one thread is reading from a bitset 60: * while another thread is simultaneously modifying it, the results are 61: * undefined. 62: * 63: * @author Jochen Hoenicke 64: * @author Tom Tromey (tromey@cygnus.com) 65: * @author Eric Blake (ebb9@email.byu.edu) 66: * @status updated to 1.4 67: */ 68: public class BitSet implements Cloneable, Serializable 69: { 70: /** 71: * Compatible with JDK 1.0. 72: */ 73: private static final long serialVersionUID = 7997698588986878753L; 74: 75: /** 76: * A common mask. 77: */ 78: private static final int LONG_MASK = 0x3f; 79: 80: /** 81: * The actual bits. 82: * @serial the i'th bit is in bits[i/64] at position i%64 (where position 83: * 0 is the least significant). 84: */ 85: private long[] bits; 86: 87: /** 88: * Create a new empty bit set. All bits are initially false. 89: */ 90: public BitSet() 91: { 92: this(64); 93: } 94: 95: /** 96: * Create a new empty bit set, with a given size. This 97: * constructor reserves enough space to represent the integers 98: * from <code>0</code> to <code>nbits-1</code>. 99: * 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: }
| GNU Classpath (0.95) |