Home | History | Annotate | Download | only in runtime 
      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 */
     28 package 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 }