1/* 2 [The "BSD license"] 3 Copyright (c) 2005-2009 Terence Parr 4 All rights reserved. 5 6 Redistribution and use in source and binary forms, with or without 7 modification, are permitted provided that the following conditions 8 are met: 9 1. Redistributions of source code must retain the above copyright 10 notice, this list of conditions and the following disclaimer. 11 2. Redistributions in binary form must reproduce the above copyright 12 notice, this list of conditions and the following disclaimer in the 13 documentation and/or other materials provided with the distribution. 14 3. The name of the author may not be used to endorse or promote products 15 derived from this software without specific prior written permission. 16 17 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28package org.antlr.runtime; 29 30import java.util.List; 31 32/**A stripped-down version of org.antlr.misc.BitSet that is just 33 * good enough to handle runtime requirements such as FOLLOW sets 34 * for automatic error recovery. 35 */ 36public class BitSet implements Cloneable { 37 protected final static int BITS = 64; // number of bits / long 38 protected final static int LOG_BITS = 6; // 2^6 == 64 39 40 /* We will often need to do a mod operator (i mod nbits). Its 41 * turns out that, for powers of two, this mod operation is 42 * same as (i & (nbits-1)). Since mod is slow, we use a 43 * precomputed mod mask to do the mod instead. 44 */ 45 protected final static int MOD_MASK = BITS - 1; 46 47 /** The actual data bits */ 48 protected long bits[]; 49 50 /** Construct a bitset of size one word (64 bits) */ 51 public BitSet() { 52 this(BITS); 53 } 54 55 /** Construction from a static array of longs */ 56 public BitSet(long[] bits_) { 57 bits = bits_; 58 } 59 60 /** Construction from a list of integers */ 61 public BitSet(List items) { 62 this(); 63 for (int i = 0; i < items.size(); i++) { 64 Integer v = (Integer) items.get(i); 65 add(v.intValue()); 66 } 67 } 68 69 /** Construct a bitset given the size 70 * @param nbits The size of the bitset in bits 71 */ 72 public BitSet(int nbits) { 73 bits = new long[((nbits - 1) >> LOG_BITS) + 1]; 74 } 75 76 public static BitSet of(int el) { 77 BitSet s = new BitSet(el + 1); 78 s.add(el); 79 return s; 80 } 81 82 public static BitSet of(int a, int b) { 83 BitSet s = new BitSet(Math.max(a,b)+1); 84 s.add(a); 85 s.add(b); 86 return s; 87 } 88 89 public static BitSet of(int a, int b, int c) { 90 BitSet s = new BitSet(); 91 s.add(a); 92 s.add(b); 93 s.add(c); 94 return s; 95 } 96 97 public static BitSet of(int a, int b, int c, int d) { 98 BitSet s = new BitSet(); 99 s.add(a); 100 s.add(b); 101 s.add(c); 102 s.add(d); 103 return s; 104 } 105 106 /** return this | a in a new set */ 107 public BitSet or(BitSet a) { 108 if ( a==null ) { 109 return this; 110 } 111 BitSet s = (BitSet)this.clone(); 112 s.orInPlace(a); 113 return s; 114 } 115 116 /** or this element into this set (grow as necessary to accommodate) */ 117 public void add(int el) { 118 int n = wordNumber(el); 119 if (n >= bits.length) { 120 growToInclude(el); 121 } 122 bits[n] |= bitMask(el); 123 } 124 125 /** 126 * Grows the set to a larger number of bits. 127 * @param bit element that must fit in set 128 */ 129 public void growToInclude(int bit) { 130 int newSize = Math.max(bits.length << 1, numWordsToHold(bit)); 131 long newbits[] = new long[newSize]; 132 System.arraycopy(bits, 0, newbits, 0, bits.length); 133 bits = newbits; 134 } 135 136 public void orInPlace(BitSet a) { 137 if ( a==null ) { 138 return; 139 } 140 // If this is smaller than a, grow this first 141 if (a.bits.length > bits.length) { 142 setSize(a.bits.length); 143 } 144 int min = Math.min(bits.length, a.bits.length); 145 for (int i = min - 1; i >= 0; i--) { 146 bits[i] |= a.bits[i]; 147 } 148 } 149 150 /** 151 * Sets the size of a set. 152 * @param nwords how many words the new set should be 153 */ 154 private void setSize(int nwords) { 155 long newbits[] = new long[nwords]; 156 int n = Math.min(nwords, bits.length); 157 System.arraycopy(bits, 0, newbits, 0, n); 158 bits = newbits; 159 } 160 161 private final static long bitMask(int bitNumber) { 162 int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS 163 return 1L << bitPosition; 164 } 165 166 public Object clone() { 167 BitSet s; 168 try { 169 s = (BitSet)super.clone(); 170 s.bits = new long[bits.length]; 171 System.arraycopy(bits, 0, s.bits, 0, bits.length); 172 } 173 catch (CloneNotSupportedException e) { 174 throw new InternalError(); 175 } 176 return s; 177 } 178 179 public int size() { 180 int deg = 0; 181 for (int i = bits.length - 1; i >= 0; i--) { 182 long word = bits[i]; 183 if (word != 0L) { 184 for (int bit = BITS - 1; bit >= 0; bit--) { 185 if ((word & (1L << bit)) != 0) { 186 deg++; 187 } 188 } 189 } 190 } 191 return deg; 192 } 193 194 public boolean equals(Object other) { 195 if ( other == null || !(other instanceof BitSet) ) { 196 return false; 197 } 198 199 BitSet otherSet = (BitSet)other; 200 201 int n = Math.min(this.bits.length, otherSet.bits.length); 202 203 // for any bits in common, compare 204 for (int i=0; i<n; i++) { 205 if (this.bits[i] != otherSet.bits[i]) { 206 return false; 207 } 208 } 209 210 // make sure any extra bits are off 211 212 if (this.bits.length > n) { 213 for (int i = n+1; i<this.bits.length; i++) { 214 if (this.bits[i] != 0) { 215 return false; 216 } 217 } 218 } 219 else if (otherSet.bits.length > n) { 220 for (int i = n+1; i<otherSet.bits.length; i++) { 221 if (otherSet.bits[i] != 0) { 222 return false; 223 } 224 } 225 } 226 227 return true; 228 } 229 230 public boolean member(int el) { 231 if ( el<0 ) { 232 return false; 233 } 234 int n = wordNumber(el); 235 if (n >= bits.length) return false; 236 return (bits[n] & bitMask(el)) != 0; 237 } 238 239 // remove this element from this set 240 public void remove(int el) { 241 int n = wordNumber(el); 242 if (n < bits.length) { 243 bits[n] &= ~bitMask(el); 244 } 245 } 246 247 public boolean isNil() { 248 for (int i = bits.length - 1; i >= 0; i--) { 249 if (bits[i] != 0) return false; 250 } 251 return true; 252 } 253 254 private final int numWordsToHold(int el) { 255 return (el >> LOG_BITS) + 1; 256 } 257 258 public int numBits() { 259 return bits.length << LOG_BITS; // num words * bits per word 260 } 261 262 /** return how much space is being used by the bits array not 263 * how many actually have member bits on. 264 */ 265 public int lengthInLongWords() { 266 return bits.length; 267 } 268 269 /**Is this contained within a? */ 270 /* 271 public boolean subset(BitSet a) { 272 if (a == null || !(a instanceof BitSet)) return false; 273 return this.and(a).equals(this); 274 } 275 */ 276 277 public int[] toArray() { 278 int[] elems = new int[size()]; 279 int en = 0; 280 for (int i = 0; i < (bits.length << LOG_BITS); i++) { 281 if (member(i)) { 282 elems[en++] = i; 283 } 284 } 285 return elems; 286 } 287 288 public long[] toPackedArray() { 289 return bits; 290 } 291 292 private final static int wordNumber(int bit) { 293 return bit >> LOG_BITS; // bit / BITS 294 } 295 296 public String toString() { 297 return toString(null); 298 } 299 300 public String toString(String[] tokenNames) { 301 StringBuffer buf = new StringBuffer(); 302 String separator = ","; 303 boolean havePrintedAnElement = false; 304 buf.append('{'); 305 306 for (int i = 0; i < (bits.length << LOG_BITS); i++) { 307 if (member(i)) { 308 if (i > 0 && havePrintedAnElement ) { 309 buf.append(separator); 310 } 311 if ( tokenNames!=null ) { 312 buf.append(tokenNames[i]); 313 } 314 else { 315 buf.append(i); 316 } 317 havePrintedAnElement = true; 318 } 319 } 320 buf.append('}'); 321 return buf.toString(); 322 } 323 324 325} 326