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}