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