• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1/**
2 * A BitSet similar to java.util.BitSet.
3 *
4 * <p>JavaScript Note: There is no good way to implement something like this in
5 * JavaScript.  JS has no true int type, arrays are usually implemented as
6 * hashes, etc.  This class should probably be nixed for something that is
7 * similarly (in)efficient, but more clear.</p>
8 *
9 * @class
10 * @param {Number|Array} [bits] a 32 bit number or array of 32 bit numbers
11 *                              representing the bitset.  These are typically
12 *                              generated by the ANTLR Tool.
13 */
14org.antlr.runtime.BitSet = function(bits) {
15    if (!bits) {
16        bits = org.antlr.runtime.BitSet.BITS;
17    }
18
19    if (org.antlr.lang.isArray(bits)) {
20        /**
21         * An array of Numbers representing the BitSet.
22         * @type Array
23         */
24        this.bits = bits;
25    } else if(org.antlr.lang.isNumber(bits)) {
26        this.bits = [];
27    }
28};
29
30org.antlr.lang.augmentObject(org.antlr.runtime.BitSet, {
31    /**
32     * Number of bits in each number.
33     * @constant
34     * @memberOf org.antlr.runtime.BitSet
35     */
36    BITS: 32,
37
38    /**
39     * Log (base 2) of the number of bits in each number.
40     * @constant
41     * @memberOf org.antlr.runtime.BitSet
42     */
43    LOG_BITS: 5,  // 2^5 == 32
44
45    /**
46     * We will often need to do a mod operator (i mod nbits).  Its
47     * turns out that, for powers of two, this mod operation is
48     * same as (i & (nbits-1)).  Since mod is slow, we use a
49     * precomputed mod mask to do the mod instead.
50     * @constant
51     * @memberOf org.antlr.runtime.BitSet
52     */
53    MOD_MASK: 31, // BITS - 1
54
55    /**
56     * Create mask for bit modded to fit in a single word.
57     * @example
58     * bitmask(35) => 00000000000000000000000000000100
59     * bitmask(3)  => 00000000000000000000000000000100
60     * @param {Number} bitNumber the bit to create a mask for.
61     * @returns {Number} the bitmask.
62     * @memberOf org.antlr.runtime.BitSet
63     * @private
64     */
65    bitMask: function(bitNumber) {
66        var bitPosition = bitNumber & org.antlr.runtime.BitSet.MOD_MASK;
67        return 1 << bitPosition;
68    },
69
70    /**
71     * Calculate the minimum number of bits needed to represent el.
72     * @param {Number} el a number to be included in the BitSet.
73     * @returns {Number} the number of bits need to create a BitSet with member
74     *                   el.
75     * @memberOf org.antlr.runtime.BitSet
76     * @private
77     */
78    numWordsToHold: function(el) {
79        return (el >> org.antlr.runtime.BitSet.LOG_BITS) + 1;
80    },
81
82    /**
83     * @param {Number} bit a number to be included in the BitSet
84     * @returns {Number} the index of the word in the field bits that would
85     *                   hold bit.
86     * @memberOf org.antlr.runtime.BitSet
87     * @private
88     */
89    wordNumber: function(bit) {
90        return bit >> org.antlr.runtime.BitSet.LOG_BITS; // bit / BITS
91    },
92
93    /**
94     * BitSet factory method.
95     *
96     * <p>Operates in a number of modes:
97     * <ul>
98     * <li>If el is a number create the BitSet containing that number.</li>
99     * <li>If el is an array create the BitSet containing each number in the
100     * array.</li>
101     * <li>If el is a BitSet return el.</li>
102     * <li>If el is an Object create the BitSet containing each numeric value
103     * in el.</li>
104     * <li>If el is a number and el2 is a number return a BitSet containing
105     * the numbers between el and el2 (inclusive).</li>
106     * </ul>
107     * </p>
108     * @param {Number|Array|org.antlr.runtime.BitSet|Object} el
109     * @param {Number} el2
110     * @returns {org.antlr.runtime.BitSet}
111     * @memberOf org.antlr.runtime.BitSet
112     */
113    of: function(el, el2) {
114        var i, n, s, keys;
115
116        if (org.antlr.lang.isNumber(el)) {
117            if (org.antlr.lang.isNumber(el2)) {
118                s = new org.antlr.runtime.BitSet(el2 + 1);
119                for (i = el; i <= el2; i++) {
120                    n = org.antlr.runtime.BitSet.wordNumber(i);
121                    s.bits[n] |= org.antlr.runtime.BitSet.bitMask(i);
122                }
123                return s;
124            } else {
125                s = new org.antlr.runtime.BitSet(el + 1);
126                s.add(el);
127                return s;
128            }
129        } else if(org.antlr.lang.isArray(el)) {
130            s = new org.antlr.runtime.BitSet();
131            for (i=el.length-1; i>=0; i--) {
132                s.add(el[i]);
133            }
134            return s;
135        } else if (el instanceof org.antlr.runtime.BitSet) {
136            if (!el) {
137                return null;
138            }
139            return el;
140        } else if (el instanceof org.antlr.runtime.IntervalSet) {
141            if (!el) {
142                return null;
143            }
144            s = new org.antlr.runtime.BitSet();
145            s.addAll(el);
146            return s;
147        } else if (org.antlr.lang.isObject(el)) {
148            keys = [];
149            for (i in el) {
150                if (org.antlr.lang.isNumber(i)) {
151                    keys.push(i);
152                }
153            }
154            return org.antlr.runtime.BitSet.of(keys);
155        }
156    }
157});
158
159
160
161org.antlr.runtime.BitSet.prototype = {
162    /**
163     * Add el into this set.
164     * @param {Number} el the number to add to the set.
165     */
166    add: function(el) {
167        var n = org.antlr.runtime.BitSet.wordNumber(el);
168        if (n >= this.bits.length) {
169            this.growToInclude(el);
170        }
171        this.bits[n] |= org.antlr.runtime.BitSet.bitMask(el);
172    },
173
174    /**
175     * Add multiple elements into this set.
176     * @param {Array|org.antlr.runtime.BitSet} elements the elements to be added to
177     *                                           this set.
178     */
179    addAll: function(elements) {
180        var other,
181            i,
182            e;
183
184        if ( elements instanceof org.antlr.runtime.BitSet ) {
185            this.orInPlace(elements);
186        }
187		else if ( elements instanceof org.antlr.runtime.IntervalSet ) {
188			other = elements;
189			// walk set and add each interval
190            /* @todo after implementing intervalset
191			for (Iterator iter = other.intervals.iterator(); iter.hasNext();) {
192				Interval I = (Interval) iter.next();
193				this.orInPlace(BitSet.range(I.a,I.b));
194			}*/
195		} else if (org.antlr.lang.isArray(elements)) {
196    		for (i = 0; i < elements.length; i++) {
197	    		e = elements[i];
198		    	this.add(e);
199    		}
200        } else {
201            return;
202        }
203	},
204
205    /**
206     * Clone this BitSet and then {@link #andInPlace} with a.
207     * @param {org.antlr.runtime.BitSet} a a bit set.
208     * @returns {org.antlr.runtime.BitSet}
209     */
210    and: function(a) {
211        var s = this.clone();
212        s.andInPlace(a);
213        return s;
214    },
215
216    /**
217     * Perform a logical AND of this target BitSet with the argument BitSet.
218     *
219     * This bit set is modified so that each bit in it has the value true if
220     * and only if it both initially had the value true and the corresponding
221     * bit in the bit set argument also had the value true.
222     * @param {org.antlr.runtime.BitSet} a a bit set.
223     * @returns {org.antlr.runtime.BitSet}
224     */
225    andInPlace: function(a) {
226        var min = Math.min(this.bits.length, a.bits.length),
227            i;
228        for (i = min - 1; i >= 0; i--) {
229            this.bits[i] &= a.bits[i];
230        }
231        // clear all bits in this not present in a (if this bigger than a).
232        for (i = min; i < this.bits.length; i++) {
233            this.bits[i] = 0;
234        }
235    },
236
237    /**
238     * Clear all bits or a specific bit.
239     *
240     * If no arguments given, sets all of the bits in this BitSet to false.
241     * If one argument given, sets the bit specified by the index to false.
242     * @param {Number} [el] the index of the bit to be cleared.
243     */
244    clear: function(el) {
245        if (arguments.length===0) {
246            var i;
247            for (i = this.bits.length - 1; i >= 0; i--) {
248                this.bits[i] = 0;
249            }
250            return;
251        }
252
253        var n = org.antlr.runtime.BitSet.wordNumber(el);
254        if (n >= this.bits.length) {	// grow as necessary to accommodate
255            this.growToInclude(el);
256        }
257        this.bits[n] &= ~org.antlr.runtime.BitSet.bitMask(el);
258    },
259
260    /**
261     * Cloning this BitSet produces a new BitSet  that is equal to it.
262     *
263     * The clone of the bit set is another bit set that has exactly the same
264     * bit set to true as this bit set.
265     * @returns {org.antlr.runtime.BitSet} a clone of this BitSet.
266     */
267    clone: function() {
268        var i, len, b=[];
269        for (i=0, len=this.bits.length; i<len; i++) {
270            b[i] = this.bits[i];
271        }
272        return new org.antlr.runtime.BitSet(b);
273    },
274
275    /**
276     * Returns the number of bits of space actually in use by this BitSet to
277     * represent bit values.
278     *
279     * The maximum element in the set is the size - 1st element.
280     * @returns {Number} the number of bits currently in this bit set.
281     */
282    size: function() {
283        var deg = 0, i, word, bit;
284        for (i = this.bits.length - 1; i >= 0; i--) {
285            word = this.bits[i];
286            if (word !== 0) {
287                for (bit = org.antlr.runtime.BitSet.BITS - 1; bit >= 0; bit--) {
288                    if ((word & (1 << bit)) !== 0) {
289                        deg++;
290                    }
291                }
292            }
293        }
294        return deg;
295    },
296
297    /**
298     * Compares this object against the specified object.
299     *
300     * The result is true if and only if the argument is not null and is a
301     * BitSet object that has exactly the same set of bits set to true as
302     * this bit set. That is, for every nonnegative int index k,
303     * <pre><code>
304     * ((BitSet)obj).get(k) == this.get(k)
305     * </code></pre>
306     * must be true. The current sizes of the two bit sets are not compared.
307     * @param {Object} other the object to compare with.
308     * @returns {Boolean} if the objects are the same; false otherwise.
309     */
310    equals: function(other) {
311        if ( !other || !(other instanceof org.antlr.runtime.BitSet) ) {
312            return false;
313        }
314
315        var otherSet = other,
316            i,
317            n = Math.min(this.bits.length, otherSet.bits.length);
318
319        // for any bits in common, compare
320        for (i=0; i<n; i++) {
321            if (this.bits[i] != otherSet.bits[i]) {
322                return false;
323            }
324        }
325
326        // make sure any extra bits are off
327
328        if (this.bits.length > n) {
329            for (i = n+1; i<this.bits.length; i++) {
330                if (this.bits[i] !== 0) {
331                    return false;
332                }
333            }
334        }
335        else if (otherSet.bits.length > n) {
336            for (i = n+1; i<otherSet.bits.length; i++) {
337                if (otherSet.bits[i] !== 0) {
338                    return false;
339                }
340            }
341        }
342
343        return true;
344    },
345
346    /**
347     * Grows the set to a larger number of bits.
348     * @param {Number} bit element that must fit in set
349     * @private
350     */
351    growToInclude: function(bit) {
352        var newSize = Math.max(this.bits.length << 1, org.antlr.runtime.BitSet.numWordsToHold(bit)),
353            newbits = [], //new Array(newSize),
354            i,
355            len;
356        for (i=0, len=this.bits.length; i<len; i++) {
357            newbits[i] = this.bits[i];
358        }
359        this.bits = newbits;
360    },
361
362    /**
363     * Returns the value of the bit with the specified index.
364     *
365     * The value is true if the bit with the index el is currently set
366     * in this BitSet; otherwise, the result is false.
367     * @param {Number} el the bit index.
368     * @returns {Boolean} the value of the bit with the specified index.
369     */
370    member: function(el) {
371        var n = org.antlr.runtime.BitSet.wordNumber(el);
372        if (n >= this.bits.length) { return false; }
373        return (this.bits[n] & org.antlr.runtime.BitSet.bitMask(el)) !== 0;
374    },
375
376    /**
377     * Returns the index of the first bit that is set to true.
378     * If no such bit exists then -1 is returned.
379     * @returns {Number} the index of the next set bit.
380     */
381    getSingleElement: function() {
382        var i;
383        for (i = 0; i < (this.bits.length << org.antlr.runtime.BitSet.LOG_BITS); i++) {
384            if (this.member(i)) {
385                return i;
386            }
387        }
388        return -1; //Label.INVALID;
389    },
390
391    /**
392     * Returns true if this BitSet contains no bits that are set to true.
393     * @returns {Boolean} boolean indicating whether this BitSet is empty.
394     */
395    isNil: function() {
396        var i;
397        for (i = this.bits.length - 1; i >= 0; i--) {
398            if (this.bits[i] !== 0) {
399                return false;
400            }
401        }
402        return true;
403    },
404
405    /**
406     * If a bit set argument is passed performs a {@link #subtract} of this bit
407     * set with the argument bit set.  If no argument is passed, clone this bit
408     * set and {@link #notInPlace}.
409     * @param {org.antlr.runtime.BitSet} [set]
410     * @returns {org.antlr.runtime.BitSet}
411     */
412    complement: function(set) {
413        if (set) {
414            return set.subtract(this);
415        } else {
416            var s = this.clone();
417            s.notInPlace();
418            return s;
419        }
420    },
421
422    /**
423     * If no arguments are passed sets all bits to the complement of their
424     * current values.  If one argument is passed sets each bit from the
425     * beginning of the bit set to index1 (inclusive) to the complement of its
426     * current value.  If two arguments are passed sets each bit from the
427     * specified index1 (inclusive) to the sepcified index2 (inclusive) to the
428     * complement of its current value.
429     * @param {Number} index1
430     * @param {Number} index2
431     */
432    notInPlace: function() {
433        var minBit, maxBit, i, n;
434        if (arguments.length===0) {
435            for (i = this.bits.length - 1; i >= 0; i--) {
436                this.bits[i] = ~this.bits[i];
437            }
438        } else {
439            if (arguments.length===1) {
440                minBit = 0;
441                maxBit = arguments[0];
442            } else {
443                minBit = arguments[0];
444                maxBit = arguments[1];
445            }
446            // make sure that we have room for maxBit
447            this.growToInclude(maxBit);
448            for (i = minBit; i <= maxBit; i++) {
449                n = org.antlr.runtime.BitSet.wordNumber(i);
450                this.bits[n] ^= org.antlr.runtime.BitSet.bitMask(i);
451            }
452        }
453
454    },
455
456    /**
457     * Performs a logical OR of this bit set with the bit set argument.
458     * If no argument is passed, return this bit set.  Otherwise a clone of
459     * this bit set is modified so that a bit in it has the value true if and
460     * only if it either already had the value true or the corresponding bit
461     * in the bit set argument has the value true.
462     * @param {org.antlr.runtime.BitSet} [a] a bit set.
463     * @returns {org.antlr.runtime.BitSet}
464     */
465    or: function(a) {
466		if ( !a ) {
467			return this;
468		}
469        var s = this.clone();
470        s.orInPlace(a);
471        return s;
472    },
473
474    /**
475     * Performs a logical {@link #or} in place.
476     * @param {org.antlr.runtime.BitSet} [a]
477     * @returns {org.antlr.runtime.BitSet}
478     */
479    orInPlace: function(a) {
480		if ( !a ) {
481			return;
482		}
483        // If this is smaller than a, grow this first
484        if (a.bits.length > this.bits.length) {
485            this.setSize(a.bits.length);
486        }
487        var min = Math.min(this.bits.length, a.bits.length),
488            i;
489        for (i = min - 1; i >= 0; i--) {
490            this.bits[i] |= a.bits[i];
491        }
492    },
493
494    /**
495     * Sets the bit specified by the index to false.
496     * @param {Number} bitIndex the index of the bit to be cleared.
497     */
498    remove: function(el) {
499        var n = org.antlr.runtime.BitSet.wordNumber(el);
500        if (n >= this.bits.length) {
501            this.growToInclude(el);
502        }
503        this.bits[n] &= ~org.antlr.runtime.BitSet.bitMask(el);
504    },
505
506    /**
507     * Grows the internal bits array to include at least nwords numbers.
508     * @param {Number} nwords how many words the new set should be
509     * @private
510     */
511    setSize: function(nwords) {
512        var n = nwords - this.bits.length;
513        while (n>=0) {
514            this.bits.push(0);
515            n--;
516        }
517    },
518
519    /**
520     * Returns the number of bits capable of being represented by this bit set
521     * given its current size.
522     * @returns {Number} the maximum number of bits that can be represented at
523     *                   the moment.
524     * @private
525     */
526    numBits: function() {
527        return this.bits.length << org.antlr.runtime.BitSet.LOG_BITS; // num words * bits per word
528    },
529
530    /**
531     * Return how much space is being used by the bits array not
532     * how many actually have member bits on.
533     * @returns {Number} the length of the internal bits array.
534     * @private
535     */
536    lengthInLongWords: function() {
537        return this.bits.length;
538    },
539
540    /**
541     * Is this bit set contained within a?
542     * @param {org.antlr.runtime.BitSet} a bit set
543     * @returns {Boolean} true if and only if a is a subset of this bit set.
544     */
545    subset: function(a) {
546        if (!a) { return false; }
547        return this.and(a).equals(this);
548    },
549
550    /**
551     * Subtract the elements of the argument bit set from this bit set in place.
552     * That is, for each set bit in the argument bit set, set the corresponding
553     * bit in this bit set to false.
554     * @param {org.antlr.runtime.BitSet} a bit set.
555     */
556    subtractInPlace: function(a) {
557        if (!a) { return; }
558        // for all words of 'a', turn off corresponding bits of 'this'
559        var i;
560        for (i = 0; i < this.bits.length && i < a.bits.length; i++) {
561            this.bits[i] &= ~a.bits[i];
562        }
563    },
564
565    /**
566     * Perform a {@link #subtractInPlace} on a clone of this bit set.
567     * @param {org.antlr.runtime.BitSet} a bit set.
568     * @returns {org.antlr.runtime.BitSet} the new bit set.
569     */
570    subtract: function(a) {
571        if (!a || !(a instanceof org.antlr.runtime.BitSet)) { return null; }
572
573        var s = this.clone();
574        s.subtractInPlace(a);
575        return s;
576    },
577
578    /* antlr-java needs this to make its class hierarchy happy . . .
579    toList: function() {
580		throw new Error("BitSet.toList() unimplemented");
581	},
582    */
583
584    /**
585     * Creates an array of the indexes of each bit set in this bit set.
586     * @returns {Array}
587     */
588    toArray: function() {
589        var elems = [], //new Array(this.size()),
590            i,
591            en = 0;
592        for (i = 0; i < (this.bits.length << org.antlr.runtime.BitSet.LOG_BITS); i++) {
593            if (this.member(i)) {
594                elems[en++] = i;
595            }
596        }
597        return elems;
598    },
599
600    /**
601     * Returns the internal representation of this bit set.
602     * This representation is an array of numbers, each representing 32 bits.
603     * @returns {Array}
604     */
605    toPackedArray: function() {
606        return this.bits;
607    },
608
609    /**
610     * Returns a string representation of this bit set.
611     * <p>For every index for which this BitSet contains a bit in the set state,
612     * the decimal representation of that index is included in the result.
613     * Such indices are listed in order from lowest to highest, separated by
614     * ", " (a comma and a space) and surrounded by braces, resulting in the
615     * usual mathematical notation for a set of integers.</p>
616     *
617     * <p>If a grammar g is passed, print g.getTokenDisplayName(i) for each set
618     * index instead of the numerical index.</p>
619     *
620     * <>If two arguments are passed, the first will be used as a custom
621     * separator string.  The second argument is an array whose i-th element
622     * will be added if the corresponding bit is set.</p>
623     *
624     * @param {Object|String} [arg1] an Object with function property
625     *      getTokenDispalyName or a String that will be used as a list
626     *      separator.
627     * @param {Array} [vocabulary] array from which the i-th value will be
628     *      drawn if the corresponding bit is set.  Must pass a string as the
629     *      first argument if using this option.
630     * @return A commma-separated list of values
631     */
632    toString: function() {
633        if (arguments.length===0) {
634            return this.toString1(null);
635        } else {
636            if (org.antlr.lang.isString(arguments[0])) {
637                if (!org.antlr.lang.isValue(arguments[1])) {
638                    return this.toString1(null);
639                } else {
640                    return this.toString2(arguments[0], arguments[1]);
641                }
642            } else {
643                return this.toString1(arguments[0]);
644            }
645        }
646    },
647
648    /**
649     * Transform a bit set into a string by formatting each element as an
650     * integer separator The string to put in between elements
651     * @private
652     * @return A commma-separated list of values
653     */
654    toString1: function(g) {
655        var buf = "{",
656            separator = ",",
657            i,
658		    havePrintedAnElement = false;
659
660        for (i = 0; i < (this.bits.length << org.antlr.runtime.BitSet.LOG_BITS); i++) {
661            if (this.member(i)) {
662                if (i > 0 && havePrintedAnElement ) {
663                    buf += separator;
664                }
665                if ( g ) {
666                    buf += g.getTokenDisplayName(i);
667                }
668                else {
669                    buf += i.toString();
670                }
671				havePrintedAnElement = true;
672            }
673        }
674        return buf + "}";
675    },
676
677    /**
678     * Create a string representation where instead of integer elements, the
679     * ith element of vocabulary is displayed instead.  Vocabulary is a Vector
680     * of Strings.
681     * separator The string to put in between elements
682     * @private
683     * @return A commma-separated list of character constants.
684     */
685    toString2: function(separator, vocabulary) {
686        var str = "",
687            i;
688        for (i = 0; i < (this.bits.length << org.antlr.runtime.BitSet.LOG_BITS); i++) {
689            if (this.member(i)) {
690                if (str.length > 0) {
691                    str += separator;
692                }
693                if (i >= vocabulary.size()) {
694                    str += "'" + i + "'";
695                }
696                else if (!org.antlr.lang.isValue(vocabulary.get(i))) {
697                    str += "'" + i + "'";
698                }
699                else {
700                    str += vocabulary.get(i);
701                }
702            }
703        }
704        return str;
705    }
706};
707