13447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/* 23447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein [The "BSD license"] 33447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Copyright (c) 2005-2009 Terence Parr 43447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein All rights reserved. 53447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 63447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Redistribution and use in source and binary forms, with or without 73447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein modification, are permitted provided that the following conditions 83447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein are met: 93447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1. Redistributions of source code must retain the above copyright 103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer. 113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2. Redistributions in binary form must reproduce the above copyright 123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer in the 133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein documentation and/or other materials provided with the distribution. 143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3. The name of the author may not be used to endorse or promote products 153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein derived from this software without specific prior written permission. 163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpackage org.antlr.runtime; 293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport java.util.List; 313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/**A stripped-down version of org.antlr.misc.BitSet that is just 333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * good enough to handle runtime requirements such as FOLLOW sets 343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * for automatic error recovery. 353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpublic class BitSet implements Cloneable { 373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected final static int BITS = 64; // number of bits / long 383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected final static int LOG_BITS = 6; // 2^6 == 64 393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /* We will often need to do a mod operator (i mod nbits). Its 413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * turns out that, for powers of two, this mod operation is 423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * same as (i & (nbits-1)). Since mod is slow, we use a 433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * precomputed mod mask to do the mod instead. 443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected final static int MOD_MASK = BITS - 1; 463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** The actual data bits */ 483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected long bits[]; 493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Construct a bitset of size one word (64 bits) */ 513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public BitSet() { 523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this(BITS); 533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Construction from a static array of longs */ 563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public BitSet(long[] bits_) { 573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein bits = bits_; 583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Construction from a list of integers */ 613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public BitSet(List items) { 623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this(); 633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i = 0; i < items.size(); i++) { 643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Integer v = (Integer) items.get(i); 653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein add(v.intValue()); 663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Construct a bitset given the size 703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * @param nbits The size of the bitset in bits 713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 723447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public BitSet(int nbits) { 733447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein bits = new long[((nbits - 1) >> LOG_BITS) + 1]; 743447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 753447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 763447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static BitSet of(int el) { 773447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein BitSet s = new BitSet(el + 1); 783447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein s.add(el); 793447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return s; 803447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 813447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 823447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static BitSet of(int a, int b) { 833447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein BitSet s = new BitSet(Math.max(a,b)+1); 843447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein s.add(a); 853447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein s.add(b); 863447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return s; 873447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 883447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 893447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static BitSet of(int a, int b, int c) { 903447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein BitSet s = new BitSet(); 913447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein s.add(a); 923447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein s.add(b); 933447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein s.add(c); 943447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return s; 953447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 963447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 973447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static BitSet of(int a, int b, int c, int d) { 983447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein BitSet s = new BitSet(); 993447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein s.add(a); 1003447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein s.add(b); 1013447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein s.add(c); 1023447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein s.add(d); 1033447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return s; 1043447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1053447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1063447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** return this | a in a new set */ 1073447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public BitSet or(BitSet a) { 1083447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( a==null ) { 1093447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return this; 1103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein BitSet s = (BitSet)this.clone(); 1123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein s.orInPlace(a); 1133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return s; 1143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** or this element into this set (grow as necessary to accommodate) */ 1173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void add(int el) { 1183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int n = wordNumber(el); 1193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (n >= bits.length) { 1203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein growToInclude(el); 1213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein bits[n] |= bitMask(el); 1233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** 1263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Grows the set to a larger number of bits. 1273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * @param bit element that must fit in set 1283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 1293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void growToInclude(int bit) { 1303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int newSize = Math.max(bits.length << 1, numWordsToHold(bit)); 1313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein long newbits[] = new long[newSize]; 1323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein System.arraycopy(bits, 0, newbits, 0, bits.length); 1333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein bits = newbits; 1343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void orInPlace(BitSet a) { 1373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( a==null ) { 1383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return; 1393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // If this is smaller than a, grow this first 1413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (a.bits.length > bits.length) { 1423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein setSize(a.bits.length); 1433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int min = Math.min(bits.length, a.bits.length); 1453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i = min - 1; i >= 0; i--) { 1463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein bits[i] |= a.bits[i]; 1473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** 1513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Sets the size of a set. 1523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * @param nwords how many words the new set should be 1533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 1543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein private void setSize(int nwords) { 1553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein long newbits[] = new long[nwords]; 1563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int n = Math.min(nwords, bits.length); 1573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein System.arraycopy(bits, 0, newbits, 0, n); 1583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein bits = newbits; 1593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein private final static long bitMask(int bitNumber) { 1623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS 1633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return 1L << bitPosition; 1643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object clone() { 1673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein BitSet s; 1683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein try { 1693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein s = (BitSet)super.clone(); 1703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein s.bits = new long[bits.length]; 1713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein System.arraycopy(bits, 0, s.bits, 0, bits.length); 1723447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1733447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein catch (CloneNotSupportedException e) { 1743447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein throw new InternalError(); 1753447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1763447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return s; 1773447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1783447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1793447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int size() { 1803447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int deg = 0; 1813447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i = bits.length - 1; i >= 0; i--) { 1823447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein long word = bits[i]; 1833447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (word != 0L) { 1843447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int bit = BITS - 1; bit >= 0; bit--) { 1853447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ((word & (1L << bit)) != 0) { 1863447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein deg++; 1873447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1883447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1893447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1903447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1913447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return deg; 1923447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1933447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1943447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public boolean equals(Object other) { 1953447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( other == null || !(other instanceof BitSet) ) { 1963447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 1973447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1983447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1993447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein BitSet otherSet = (BitSet)other; 2003447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2013447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int n = Math.min(this.bits.length, otherSet.bits.length); 2023447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2033447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // for any bits in common, compare 2043447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i=0; i<n; i++) { 2053447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (this.bits[i] != otherSet.bits[i]) { 2063447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 2073447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2083447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2093447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // make sure any extra bits are off 2113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (this.bits.length > n) { 2133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i = n+1; i<this.bits.length; i++) { 2143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (this.bits[i] != 0) { 2153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 2163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein else if (otherSet.bits.length > n) { 2203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i = n+1; i<otherSet.bits.length; i++) { 2213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (otherSet.bits[i] != 0) { 2223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 2233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return true; 2283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public boolean member(int el) { 2313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( el<0 ) { 2323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return false; 2333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int n = wordNumber(el); 2353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (n >= bits.length) return false; 2363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return (bits[n] & bitMask(el)) != 0; 2373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // remove this element from this set 2403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void remove(int el) { 2413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int n = wordNumber(el); 2423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (n < bits.length) { 2433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein bits[n] &= ~bitMask(el); 2443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public boolean isNil() { 2483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i = bits.length - 1; i >= 0; i--) { 2493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (bits[i] != 0) return false; 2503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return true; 2523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein private final int numWordsToHold(int el) { 2553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return (el >> LOG_BITS) + 1; 2563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int numBits() { 2593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return bits.length << LOG_BITS; // num words * bits per word 2603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** return how much space is being used by the bits array not 2633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * how many actually have member bits on. 2643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 2653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int lengthInLongWords() { 2663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return bits.length; 2673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /**Is this contained within a? */ 2703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /* 2713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public boolean subset(BitSet a) { 2723447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (a == null || !(a instanceof BitSet)) return false; 2733447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return this.and(a).equals(this); 2743447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2753447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 2763447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2773447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int[] toArray() { 2783447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int[] elems = new int[size()]; 2793447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int en = 0; 2803447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i = 0; i < (bits.length << LOG_BITS); i++) { 2813447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (member(i)) { 2823447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein elems[en++] = i; 2833447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2843447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2853447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return elems; 2863447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2873447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2883447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public long[] toPackedArray() { 2893447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return bits; 2903447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2913447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2923447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein private final static int wordNumber(int bit) { 2933447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return bit >> LOG_BITS; // bit / BITS 2943447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2953447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2963447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public String toString() { 2973447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return toString(null); 2983447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 2993447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3003447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public String toString(String[] tokenNames) { 3013447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein StringBuffer buf = new StringBuffer(); 3023447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein String separator = ","; 3033447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein boolean havePrintedAnElement = false; 3043447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein buf.append('{'); 3053447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3063447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein for (int i = 0; i < (bits.length << LOG_BITS); i++) { 3073447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (member(i)) { 3083447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if (i > 0 && havePrintedAnElement ) { 3093447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein buf.append(separator); 3103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tokenNames!=null ) { 3123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein buf.append(tokenNames[i]); 3133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein else { 3153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein buf.append(i); 3163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein havePrintedAnElement = true; 3183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein buf.append('}'); 3213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return buf.toString(); 3223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 3233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein} 326