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.misc;
029:
030: import org.antlr.analysis.Label;
031: import org.antlr.tool.Grammar;
032:
033: import java.util.Collection;
034: import java.util.Iterator;
035: import java.util.List;
036: import java.util.Map;
037:
038: /**A BitSet to replace java.util.BitSet.
039: *
040: * Primary differences are that most set operators return new sets
041: * as opposed to oring and anding "in place". Further, a number of
042: * operations were added. I cannot contain a BitSet because there
043: * is no way to access the internal bits (which I need for speed)
044: * and, because it is final, I cannot subclass to add functionality.
045: * Consider defining set degree. Without access to the bits, I must
046: * call a method n times to test the ith bit...ack!
047: *
048: * Also seems like or() from util is wrong when size of incoming set is bigger
049: * than this.bits.length.
050: *
051: * @author Terence Parr
052: */
053: public class BitSet implements IntSet, Cloneable {
054: protected final static int BITS = 64; // number of bits / long
055: protected final static int LOG_BITS = 6; // 2^6 == 64
056:
057: /* We will often need to do a mod operator (i mod nbits). Its
058: * turns out that, for powers of two, this mod operation is
059: * same as (i & (nbits-1)). Since mod is slow, we use a
060: * precomputed mod mask to do the mod instead.
061: */
062: protected final static int MOD_MASK = BITS - 1;
063:
064: /** The actual data bits */
065: protected long bits[];
066:
067: /** Construct a bitset of size one word (64 bits) */
068: public BitSet() {
069: this (BITS);
070: }
071:
072: /** Construction from a static array of longs */
073: public BitSet(long[] bits_) {
074: bits = bits_;
075: }
076:
077: /** Construct a bitset given the size
078: * @param nbits The size of the bitset in bits
079: */
080: public BitSet(int nbits) {
081: bits = new long[((nbits - 1) >> LOG_BITS) + 1];
082: }
083:
084: /** or this element into this set (grow as necessary to accommodate) */
085: public void add(int el) {
086: //System.out.println("add("+el+")");
087: int n = wordNumber(el);
088: //System.out.println("word number is "+n);
089: //System.out.println("bits.length "+bits.length);
090: if (n >= bits.length) {
091: growToInclude(el);
092: }
093: bits[n] |= bitMask(el);
094: }
095:
096: public void addAll(IntSet set) {
097: if (set instanceof BitSet) {
098: this .orInPlace((BitSet) set);
099: } else if (set instanceof IntervalSet) {
100: IntervalSet other = (IntervalSet) set;
101: // walk set and add each interval
102: for (Iterator iter = other.intervals.iterator(); iter
103: .hasNext();) {
104: Interval I = (Interval) iter.next();
105: this .orInPlace(BitSet.range(I.a, I.b));
106: }
107: } else {
108: throw new IllegalArgumentException("can't add "
109: + set.getClass().getName() + " to BitSet");
110: }
111: }
112:
113: public void addAll(int[] elements) {
114: if (elements == null) {
115: return;
116: }
117: for (int i = 0; i < elements.length; i++) {
118: int e = elements[i];
119: add(e);
120: }
121: }
122:
123: public void addAll(List elements) {
124: if (elements == null) {
125: return;
126: }
127: for (int i = 0; i < elements.size(); i++) {
128: Object o = elements.get(i);
129: if (!(o instanceof Integer)) {
130: throw new IllegalArgumentException();
131: }
132: Integer eI = (Integer) o;
133: add(eI.intValue());
134: }
135: }
136:
137: public IntSet and(IntSet a) {
138: BitSet s = (BitSet) this .clone();
139: s.andInPlace((BitSet) a);
140: return s;
141: }
142:
143: public void andInPlace(BitSet a) {
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: // clear all bits in this not present in a (if this bigger than a).
149: for (int i = min; i < bits.length; i++) {
150: bits[i] = 0;
151: }
152: }
153:
154: private final static long bitMask(int bitNumber) {
155: int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS
156: return 1L << bitPosition;
157: }
158:
159: public void clear() {
160: for (int i = bits.length - 1; i >= 0; i--) {
161: bits[i] = 0;
162: }
163: }
164:
165: public void clear(int el) {
166: int n = wordNumber(el);
167: if (n >= bits.length) { // grow as necessary to accommodate
168: growToInclude(el);
169: }
170: bits[n] &= ~bitMask(el);
171: }
172:
173: public Object clone() {
174: BitSet s;
175: try {
176: s = (BitSet) super .clone();
177: s.bits = new long[bits.length];
178: System.arraycopy(bits, 0, s.bits, 0, bits.length);
179: } catch (CloneNotSupportedException e) {
180: throw new InternalError();
181: }
182: return s;
183: }
184:
185: public int size() {
186: int deg = 0;
187: for (int i = bits.length - 1; i >= 0; i--) {
188: long word = bits[i];
189: if (word != 0L) {
190: for (int bit = BITS - 1; bit >= 0; bit--) {
191: if ((word & (1L << bit)) != 0) {
192: deg++;
193: }
194: }
195: }
196: }
197: return deg;
198: }
199:
200: public boolean equals(Object other) {
201: if (other == null || !(other instanceof BitSet)) {
202: return false;
203: }
204:
205: BitSet otherSet = (BitSet) other;
206:
207: int n = Math.min(this .bits.length, otherSet.bits.length);
208:
209: // for any bits in common, compare
210: for (int i = 0; i < n; i++) {
211: if (this .bits[i] != otherSet.bits[i]) {
212: return false;
213: }
214: }
215:
216: // make sure any extra bits are off
217:
218: if (this .bits.length > n) {
219: for (int i = n + 1; i < this .bits.length; i++) {
220: if (this .bits[i] != 0) {
221: return false;
222: }
223: }
224: } else if (otherSet.bits.length > n) {
225: for (int i = n + 1; i < otherSet.bits.length; i++) {
226: if (otherSet.bits[i] != 0) {
227: return false;
228: }
229: }
230: }
231:
232: return true;
233: }
234:
235: /**
236: * Grows the set to a larger number of bits.
237: * @param bit element that must fit in set
238: */
239: public void growToInclude(int bit) {
240: int newSize = Math.max(bits.length << 1, numWordsToHold(bit));
241: long newbits[] = new long[newSize];
242: System.arraycopy(bits, 0, newbits, 0, bits.length);
243: bits = newbits;
244: }
245:
246: public boolean member(int el) {
247: int n = wordNumber(el);
248: if (n >= bits.length)
249: return false;
250: return (bits[n] & bitMask(el)) != 0;
251: }
252:
253: /** Get the first element you find and return it. Return Label.INVALID
254: * otherwise.
255: */
256: public int getSingleElement() {
257: for (int i = 0; i < (bits.length << LOG_BITS); i++) {
258: if (member(i)) {
259: return i;
260: }
261: }
262: return Label.INVALID;
263: }
264:
265: public boolean isNil() {
266: for (int i = bits.length - 1; i >= 0; i--) {
267: if (bits[i] != 0)
268: return false;
269: }
270: return true;
271: }
272:
273: public IntSet complement() {
274: BitSet s = (BitSet) this .clone();
275: s.notInPlace();
276: return s;
277: }
278:
279: public IntSet complement(IntSet set) {
280: if (set == null) {
281: return this .complement();
282: }
283: return set.subtract(this );
284: }
285:
286: public void notInPlace() {
287: for (int i = bits.length - 1; i >= 0; i--) {
288: bits[i] = ~bits[i];
289: }
290: }
291:
292: /** complement bits in the range 0..maxBit. */
293: public void notInPlace(int maxBit) {
294: notInPlace(0, maxBit);
295: }
296:
297: /** complement bits in the range minBit..maxBit.*/
298: public void notInPlace(int minBit, int maxBit) {
299: // make sure that we have room for maxBit
300: growToInclude(maxBit);
301: for (int i = minBit; i <= maxBit; i++) {
302: int n = wordNumber(i);
303: bits[n] ^= bitMask(i);
304: }
305: }
306:
307: private final int numWordsToHold(int el) {
308: return (el >> LOG_BITS) + 1;
309: }
310:
311: public static BitSet of(int el) {
312: BitSet s = new BitSet(el + 1);
313: s.add(el);
314: return s;
315: }
316:
317: public static BitSet of(Collection elements) {
318: BitSet s = new BitSet();
319: Iterator iter = elements.iterator();
320: while (iter.hasNext()) {
321: Integer el = (Integer) iter.next();
322: s.add(el.intValue());
323: }
324: return s;
325: }
326:
327: public static BitSet of(IntSet set) {
328: if (set == null) {
329: return null;
330: }
331:
332: if (set instanceof BitSet) {
333: return (BitSet) set;
334: }
335: if (set instanceof IntervalSet) {
336: BitSet s = new BitSet();
337: s.addAll(set);
338: return s;
339: }
340: throw new IllegalArgumentException("can't create BitSet from "
341: + set.getClass().getName());
342: }
343:
344: public static BitSet of(Map elements) {
345: return BitSet.of(elements.keySet());
346: }
347:
348: public static BitSet range(int a, int b) {
349: BitSet s = new BitSet(b + 1);
350: for (int i = a; i <= b; i++) {
351: int n = wordNumber(i);
352: s.bits[n] |= bitMask(i);
353: }
354: return s;
355: }
356:
357: /** return this | a in a new set */
358: public IntSet or(IntSet a) {
359: if (a == null) {
360: return this ;
361: }
362: BitSet s = (BitSet) this .clone();
363: s.orInPlace((BitSet) a);
364: return s;
365: }
366:
367: public void orInPlace(BitSet a) {
368: if (a == null) {
369: return;
370: }
371: // If this is smaller than a, grow this first
372: if (a.bits.length > bits.length) {
373: setSize(a.bits.length);
374: }
375: int min = Math.min(bits.length, a.bits.length);
376: for (int i = min - 1; i >= 0; i--) {
377: bits[i] |= a.bits[i];
378: }
379: }
380:
381: // remove this element from this set
382: public void remove(int el) {
383: int n = wordNumber(el);
384: if (n >= bits.length) {
385: growToInclude(el);
386: }
387: bits[n] &= ~bitMask(el);
388: }
389:
390: /**
391: * Sets the size of a set.
392: * @param nwords how many words the new set should be
393: */
394: private void setSize(int nwords) {
395: long newbits[] = new long[nwords];
396: int n = Math.min(nwords, bits.length);
397: System.arraycopy(bits, 0, newbits, 0, n);
398: bits = newbits;
399: }
400:
401: public int numBits() {
402: return bits.length << LOG_BITS; // num words * bits per word
403: }
404:
405: /** return how much space is being used by the bits array not
406: * how many actually have member bits on.
407: */
408: public int lengthInLongWords() {
409: return bits.length;
410: }
411:
412: /**Is this contained within a? */
413: public boolean subset(BitSet a) {
414: if (a == null)
415: return false;
416: return this .and(a).equals(this );
417: }
418:
419: /**Subtract the elements of 'a' from 'this' in-place.
420: * Basically, just turn off all bits of 'this' that are in 'a'.
421: */
422: public void subtractInPlace(BitSet a) {
423: if (a == null)
424: return;
425: // for all words of 'a', turn off corresponding bits of 'this'
426: for (int i = 0; i < bits.length && i < a.bits.length; i++) {
427: bits[i] &= ~a.bits[i];
428: }
429: }
430:
431: public IntSet subtract(IntSet a) {
432: if (a == null || !(a instanceof BitSet))
433: return null;
434:
435: BitSet s = (BitSet) this .clone();
436: s.subtractInPlace((BitSet) a);
437: return s;
438: }
439:
440: public List toList() {
441: throw new NoSuchMethodError("BitSet.toList() unimplemented");
442: }
443:
444: public int[] toArray() {
445: int[] elems = new int[size()];
446: int en = 0;
447: for (int i = 0; i < (bits.length << LOG_BITS); i++) {
448: if (member(i)) {
449: elems[en++] = i;
450: }
451: }
452: return elems;
453: }
454:
455: public long[] toPackedArray() {
456: return bits;
457: }
458:
459: public String toString() {
460: return toString(null);
461: }
462:
463: /** Transform a bit set into a string by formatting each element as an integer
464: * separator The string to put in between elements
465: * @return A commma-separated list of values
466: */
467: public String toString(Grammar g) {
468: StringBuffer buf = new StringBuffer();
469: String separator = ",";
470: boolean havePrintedAnElement = false;
471: buf.append('{');
472:
473: for (int i = 0; i < (bits.length << LOG_BITS); i++) {
474: if (member(i)) {
475: if (i > 0 && havePrintedAnElement) {
476: buf.append(separator);
477: }
478: if (g != null) {
479: buf.append(g.getTokenDisplayName(i));
480: } else {
481: buf.append(i);
482: }
483: havePrintedAnElement = true;
484: }
485: }
486: buf.append('}');
487: return buf.toString();
488: }
489:
490: /**Create a string representation where instead of integer elements, the
491: * ith element of vocabulary is displayed instead. Vocabulary is a Vector
492: * of Strings.
493: * separator The string to put in between elements
494: * @return A commma-separated list of character constants.
495: */
496: public String toString(String separator, List vocabulary) {
497: if (vocabulary == null) {
498: return toString(null);
499: }
500: String str = "";
501: for (int i = 0; i < (bits.length << LOG_BITS); i++) {
502: if (member(i)) {
503: if (str.length() > 0) {
504: str += separator;
505: }
506: if (i >= vocabulary.size()) {
507: str += "'" + (char) i + "'";
508: } else if (vocabulary.get(i) == null) {
509: str += "'" + (char) i + "'";
510: } else {
511: str += (String) vocabulary.get(i);
512: }
513: }
514: }
515: return str;
516: }
517:
518: /**
519: * Dump a comma-separated list of the words making up the bit set.
520: * Split each 64 bit number into two more manageable 32 bit numbers.
521: * This generates a comma-separated list of C++-like unsigned long constants.
522: */
523: public String toStringOfHalfWords() {
524: StringBuffer s = new StringBuffer();
525: for (int i = 0; i < bits.length; i++) {
526: if (i != 0)
527: s.append(", ");
528: long tmp = bits[i];
529: tmp &= 0xFFFFFFFFL;
530: s.append(tmp);
531: s.append("UL");
532: s.append(", ");
533: tmp = bits[i] >>> 32;
534: tmp &= 0xFFFFFFFFL;
535: s.append(tmp);
536: s.append("UL");
537: }
538: return s.toString();
539: }
540:
541: /**
542: * Dump a comma-separated list of the words making up the bit set.
543: * This generates a comma-separated list of Java-like long int constants.
544: */
545: public String toStringOfWords() {
546: StringBuffer s = new StringBuffer();
547: for (int i = 0; i < bits.length; i++) {
548: if (i != 0)
549: s.append(", ");
550: s.append(bits[i]);
551: s.append("L");
552: }
553: return s.toString();
554: }
555:
556: public String toStringWithRanges() {
557: return toString();
558: }
559:
560: private final static int wordNumber(int bit) {
561: return bit >> LOG_BITS; // bit / BITS
562: }
563: }
|