001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2006 Terence Parr
004: All rights reserved.
005:
006: Redistribution and use in source and binary forms, with or without
007: modification, are permitted provided that the following conditions
008: are met:
009: 1. Redistributions of source code must retain the above copyright
010: notice, this list of conditions and the following disclaimer.
011: 2. Redistributions in binary form must reproduce the above copyright
012: notice, this list of conditions and the following disclaimer in the
013: documentation and/or other materials provided with the distribution.
014: 3. The name of the author may not be used to endorse or promote products
015: derived from this software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
018: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
019: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
020: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
021: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
022: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
023: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
024: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
026: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028: package org.antlr.runtime;
029:
030: import java.util.List;
031:
032: /**A stripped-down version of org.antlr.misc.BitSet that is just
033: * good enough to handle runtime requirements such as FOLLOW sets
034: * for automatic error recovery.
035: */
036: public class BitSet implements Cloneable {
037: protected final static int BITS = 64; // number of bits / long
038: protected final static int LOG_BITS = 6; // 2^6 == 64
039:
040: /* We will often need to do a mod operator (i mod nbits). Its
041: * turns out that, for powers of two, this mod operation is
042: * same as (i & (nbits-1)). Since mod is slow, we use a
043: * precomputed mod mask to do the mod instead.
044: */
045: protected final static int MOD_MASK = BITS - 1;
046:
047: /** The actual data bits */
048: protected long bits[];
049:
050: /** Construct a bitset of size one word (64 bits) */
051: public BitSet() {
052: this (BITS);
053: }
054:
055: /** Construction from a static array of longs */
056: public BitSet(long[] bits_) {
057: bits = bits_;
058: }
059:
060: /** Construction from a list of integers */
061: public BitSet(List items) {
062: for (int i = 0; i < items.size(); i++) {
063: Integer v = (Integer) items.get(i);
064: add(v.intValue());
065: }
066: }
067:
068: /** Construct a bitset given the size
069: * @param nbits The size of the bitset in bits
070: */
071: public BitSet(int nbits) {
072: bits = new long[((nbits - 1) >> LOG_BITS) + 1];
073: }
074:
075: public static BitSet of(int el) {
076: BitSet s = new BitSet(el + 1);
077: s.add(el);
078: return s;
079: }
080:
081: public static BitSet of(int a, int b) {
082: BitSet s = new BitSet(Math.max(a, b) + 1);
083: s.add(a);
084: s.add(b);
085: return s;
086: }
087:
088: public static BitSet of(int a, int b, int c) {
089: BitSet s = new BitSet();
090: s.add(a);
091: s.add(b);
092: s.add(c);
093: return s;
094: }
095:
096: public static BitSet of(int a, int b, int c, int d) {
097: BitSet s = new BitSet();
098: s.add(a);
099: s.add(b);
100: s.add(c);
101: s.add(d);
102: return s;
103: }
104:
105: /** return this | a in a new set */
106: public BitSet or(BitSet a) {
107: if (a == null) {
108: return this ;
109: }
110: BitSet s = (BitSet) this .clone();
111: s.orInPlace(a);
112: return s;
113: }
114:
115: /** or this element into this set (grow as necessary to accommodate) */
116: public void add(int el) {
117: int n = wordNumber(el);
118: if (n >= bits.length) {
119: growToInclude(el);
120: }
121: bits[n] |= bitMask(el);
122: }
123:
124: /**
125: * Grows the set to a larger number of bits.
126: * @param bit element that must fit in set
127: */
128: public void growToInclude(int bit) {
129: int newSize = Math.max(bits.length << 1, numWordsToHold(bit));
130: long newbits[] = new long[newSize];
131: System.arraycopy(bits, 0, newbits, 0, bits.length);
132: bits = newbits;
133: }
134:
135: public void orInPlace(BitSet a) {
136: if (a == null) {
137: return;
138: }
139: // If this is smaller than a, grow this first
140: if (a.bits.length > bits.length) {
141: setSize(a.bits.length);
142: }
143: int min = Math.min(bits.length, a.bits.length);
144: for (int i = min - 1; i >= 0; i--) {
145: bits[i] |= a.bits[i];
146: }
147: }
148:
149: /**
150: * Sets the size of a set.
151: * @param nwords how many words the new set should be
152: */
153: private void setSize(int nwords) {
154: long newbits[] = new long[nwords];
155: int n = Math.min(nwords, bits.length);
156: System.arraycopy(bits, 0, newbits, 0, n);
157: bits = newbits;
158: }
159:
160: private final static long bitMask(int bitNumber) {
161: int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS
162: return 1L << bitPosition;
163: }
164:
165: public Object clone() {
166: BitSet s;
167: try {
168: s = (BitSet) super .clone();
169: s.bits = new long[bits.length];
170: System.arraycopy(bits, 0, s.bits, 0, bits.length);
171: } catch (CloneNotSupportedException e) {
172: throw new InternalError();
173: }
174: return s;
175: }
176:
177: public int size() {
178: int deg = 0;
179: for (int i = bits.length - 1; i >= 0; i--) {
180: long word = bits[i];
181: if (word != 0L) {
182: for (int bit = BITS - 1; bit >= 0; bit--) {
183: if ((word & (1L << bit)) != 0) {
184: deg++;
185: }
186: }
187: }
188: }
189: return deg;
190: }
191:
192: public boolean equals(Object other) {
193: if (other == null || !(other instanceof BitSet)) {
194: return false;
195: }
196:
197: BitSet otherSet = (BitSet) other;
198:
199: int n = Math.min(this .bits.length, otherSet.bits.length);
200:
201: // for any bits in common, compare
202: for (int i = 0; i < n; i++) {
203: if (this .bits[i] != otherSet.bits[i]) {
204: return false;
205: }
206: }
207:
208: // make sure any extra bits are off
209:
210: if (this .bits.length > n) {
211: for (int i = n + 1; i < this .bits.length; i++) {
212: if (this .bits[i] != 0) {
213: return false;
214: }
215: }
216: } else if (otherSet.bits.length > n) {
217: for (int i = n + 1; i < otherSet.bits.length; i++) {
218: if (otherSet.bits[i] != 0) {
219: return false;
220: }
221: }
222: }
223:
224: return true;
225: }
226:
227: public boolean member(int el) {
228: if (el < 0) {
229: return false;
230: }
231: int n = wordNumber(el);
232: if (n >= bits.length)
233: return false;
234: return (bits[n] & bitMask(el)) != 0;
235: }
236:
237: // remove this element from this set
238: public void remove(int el) {
239: int n = wordNumber(el);
240: if (n < bits.length) {
241: bits[n] &= ~bitMask(el);
242: }
243: }
244:
245: public boolean isNil() {
246: for (int i = bits.length - 1; i >= 0; i--) {
247: if (bits[i] != 0)
248: return false;
249: }
250: return true;
251: }
252:
253: private final int numWordsToHold(int el) {
254: return (el >> LOG_BITS) + 1;
255: }
256:
257: public int numBits() {
258: return bits.length << LOG_BITS; // num words * bits per word
259: }
260:
261: /** return how much space is being used by the bits array not
262: * how many actually have member bits on.
263: */
264: public int lengthInLongWords() {
265: return bits.length;
266: }
267:
268: /**Is this contained within a? */
269: /*
270: public boolean subset(BitSet a) {
271: if (a == null || !(a instanceof BitSet)) return false;
272: return this.and(a).equals(this);
273: }
274: */
275:
276: public int[] toArray() {
277: int[] elems = new int[size()];
278: int en = 0;
279: for (int i = 0; i < (bits.length << LOG_BITS); i++) {
280: if (member(i)) {
281: elems[en++] = i;
282: }
283: }
284: return elems;
285: }
286:
287: public long[] toPackedArray() {
288: return bits;
289: }
290:
291: private final static int wordNumber(int bit) {
292: return bit >> LOG_BITS; // bit / BITS
293: }
294:
295: public String toString() {
296: return toString(null);
297: }
298:
299: public String toString(String[] tokenNames) {
300: StringBuffer buf = new StringBuffer();
301: String separator = ",";
302: boolean havePrintedAnElement = false;
303: buf.append('{');
304:
305: for (int i = 0; i < (bits.length << LOG_BITS); i++) {
306: if (member(i)) {
307: if (i > 0 && havePrintedAnElement) {
308: buf.append(separator);
309: }
310: if (tokenNames != null) {
311: buf.append(tokenNames[i]);
312: } else {
313: buf.append(i);
314: }
315: havePrintedAnElement = true;
316: }
317: }
318: buf.append('}');
319: return buf.toString();
320: }
321:
322: }
|