1/* 2 [The "BSD licence"] 3 Copyright (c) 2005-2006 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 30 /**A stripped-down version of org.antlr.misc.BitSet that is just 31 * good enough to handle runtime requirements such as FOLLOW sets 32 * for automatic error recovery. 33 */ 34 public class BitSet { 35 protected static const BITS:uint = 32; // number of bits / int 36 protected static const LOG_BITS:uint = 5; // 2^5 == 32 37 38 /* We will often need to do a mod operator (i mod nbits). Its 39 * turns out that, for powers of two, this mod operation is 40 * same as (i & (nbits-1)). Since mod is slow, we use a 41 * precomputed mod mask to do the mod instead. 42 */ 43 protected static const MOD_MASK:uint = BITS - 1; 44 45 /** The actual data bits */ 46 protected var bits:Array; 47 48 /** Construction from a static array of longs */ 49 public function BitSet(bits:Array = null) { 50 if (bits == null) { 51 this.bits = new Array(); 52 } 53 else { 54 this.bits = new Array(); 55 for (var i:int = 0; i < bits.length; i++) { 56 this.bits[i] = bits[i]; 57 } 58 } 59 } 60 61 public static function of(... args):BitSet { 62 var s:BitSet = new BitSet(); 63 for (var i:int = 0; i < args.length; i++) { 64 s.add(args[i]); 65 } 66 return s; 67 } 68 69 /** return this | a in a new set */ 70 public function or(a:BitSet):BitSet { 71 if ( a==null ) { 72 return this; 73 } 74 var s:BitSet = this.clone(); 75 s.orInPlace(a); 76 return s; 77 } 78 79 /** or this element into this set (grow as necessary to accommodate) */ 80 public function add(el:int):void { 81 var n:int = wordNumber(el); 82 if (n >= bits.length) { 83 growToInclude(el); 84 } 85 bits[n] |= bitMask(el); 86 } 87 88 /** 89 * Grows the set to a larger number of bits. 90 * @param bit element that must fit in set 91 */ 92 public function growToInclude(bit:int):void { 93 var newSize:int = Math.max(bits.length << 1, numWordsToHold(bit)); 94 bits.length = newSize; 95 } 96 97 public function orInPlace(a:BitSet):void { 98 if ( a==null ) { 99 return; 100 } 101 // If this is smaller than a, grow this first 102 if (a.bits.length > bits.length) { 103 this.bits.length = a.bits.length; 104 } 105 var min:int = Math.min(bits.length, a.bits.length); 106 for (var i:int = min - 1; i >= 0; i--) { 107 bits[i] |= a.bits[i]; 108 } 109 } 110 111 /** 112 * Sets the size of a set. 113 * @param nwords how many words the new set should be 114 */ 115 private function set size(nwords:int):void { 116 bits.length = nwords; 117 } 118 119 private static function bitMask(bitNumber:int):int { 120 var bitPosition:int = bitNumber & MOD_MASK; // bitNumber mod BITS 121 return 1 << bitPosition; 122 } 123 124 public function clone():BitSet { 125 var s:BitSet = new BitSet(bits); 126 return s; 127 } 128 129 public function get size():int { 130 var deg:uint = 0; 131 for (var i:int = bits.length - 1; i >= 0; i--) { 132 var word:uint = bits[i]; 133 if (word != 0) { 134 for (var bit:int = BITS - 1; bit >= 0; bit--) { 135 if ((word & (1 << bit)) != 0) { 136 deg++; 137 } 138 } 139 } 140 } 141 return deg; 142 } 143 144 public function equals(other:Object):Boolean { 145 if ( other == null || !(other is BitSet) ) { 146 return false; 147 } 148 149 var otherSet:BitSet = BitSet(other); 150 151 var n:int = Math.min(this.bits.length, otherSet.bits.length); 152 153 // for any bits in common, compare 154 for (var i:int=0; i<n; i++) { 155 if (this.bits[i] != otherSet.bits[i]) { 156 return false; 157 } 158 } 159 160 // make sure any extra bits are off 161 162 if (this.bits.length > n) { 163 for (i = n+1; i<this.bits.length; i++) { 164 if (this.bits[i] != 0) { 165 return false; 166 } 167 } 168 } 169 else if (otherSet.bits.length > n) { 170 for (i = n+1; i<otherSet.bits.length; i++) { 171 if (otherSet.bits[i] != 0) { 172 return false; 173 } 174 } 175 } 176 177 return true; 178 } 179 180 public function member(el:int):Boolean { 181 if ( el<0 ) { 182 return false; 183 } 184 var n:int = wordNumber(el); 185 if (n >= bits.length) return false; 186 return (bits[n] & bitMask(el)) != 0; 187 } 188 189 // remove this element from this set 190 public function remove(el:int):void { 191 var n:int = wordNumber(el); 192 if (n < bits.length) { 193 bits[n] &= ~bitMask(el); 194 } 195 } 196 197 public function get isNil():Boolean { 198 for (var i:int = bits.length - 1; i >= 0; i--) { 199 if (bits[i] != 0) return false; 200 } 201 return true; 202 } 203 204 private final function numWordsToHold(el:int):int { 205 return (el >> LOG_BITS) + 1; 206 } 207 208 public function get numBits():int { 209 return bits.length << LOG_BITS; // num words * bits per word 210 } 211 212 /** return how much space is being used by the bits array not 213 * how many actually have member bits on. 214 */ 215 public function get lengthInLongWords():int { 216 return bits.length; 217 } 218 219 public function toArray():Array { 220 var elems:Array = new Array[this.bits.length]; 221 var en:int = 0; 222 for (var i:int = 0; i < (bits.length << LOG_BITS); i++) { 223 if (member(i)) { 224 elems[en++] = i; 225 } 226 } 227 return elems; 228 } 229 230 public function toPackedArray():Array { 231 return bits; 232 } 233 234 private static function wordNumber(bit:uint):uint { 235 return bit >> LOG_BITS; // bit / BITS 236 } 237 238 public function toString():String { 239 return toStringFromTokens(null); 240 } 241 242 public function toStringFromTokens(tokenNames:Array):String { 243 var buf:String = ""; 244 const separator:String = ","; 245 var havePrintedAnElement:Boolean = false; 246 buf = buf + '{'; 247 248 for (var i:int = 0; i < (bits.length << LOG_BITS); i++) { 249 if (member(i)) { 250 if (i > 0 && havePrintedAnElement ) { 251 buf += separator; 252 } 253 if ( tokenNames!=null ) { 254 buf += tokenNames[i]; 255 } 256 else { 257 buf += i; 258 } 259 havePrintedAnElement = true; 260 } 261 } 262 buf += '}'; 263 return buf; 264 } 265 266 } 267}