xref: /external/antlr/runtime/JavaScript/src/org/antlr/runtime/BitSet.js

/**
 * A BitSet similar to java.util.BitSet.
 *
 * <p>JavaScript Note: There is no good way to implement something like this in
 * JavaScript.  JS has no true int type, arrays are usually implemented as
 * hashes, etc.  This class should probably be nixed for something that is
 * similarly (in)efficient, but more clear.</p>
 *
 * @class
 * @param {Number|Array} [bits] a 32 bit number or array of 32 bit numbers
 *                              representing the bitset.  These are typically
 *                              generated by the ANTLR Tool.
 */
org.antlr.runtime.BitSet = function(bits) {
    if (!bits) {
        bits = org.antlr.runtime.BitSet.BITS;
    }

    if (org.antlr.lang.isArray(bits)) {
        /**
         * An array of Numbers representing the BitSet.
         * @type Array
         */
        this.bits = bits;
    } else if(org.antlr.lang.isNumber(bits)) {
        this.bits = [];
    }
};

org.antlr.lang.augmentObject(org.antlr.runtime.BitSet, {
    /**
     * Number of bits in each number.
     * @constant
     * @memberOf org.antlr.runtime.BitSet
     */
    BITS: 32,

    /**
     * Log (base 2) of the number of bits in each number.
     * @constant
     * @memberOf org.antlr.runtime.BitSet
     */
    LOG_BITS: 5,  // 2^5 == 32

    /**
     * We will often need to do a mod operator (i mod nbits).  Its
     * turns out that, for powers of two, this mod operation is
     * same as (i & (nbits-1)).  Since mod is slow, we use a
     * precomputed mod mask to do the mod instead.
     * @constant
     * @memberOf org.antlr.runtime.BitSet
     */
    MOD_MASK: 31, // BITS - 1

    /**
     * Create mask for bit modded to fit in a single word.
     * @example
     * bitmask(35) => 00000000000000000000000000000100
     * bitmask(3)  => 00000000000000000000000000000100
     * @param {Number} bitNumber the bit to create a mask for.
     * @returns {Number} the bitmask.
     * @memberOf org.antlr.runtime.BitSet
     * @private
     */
    bitMask: function(bitNumber) {
        var bitPosition = bitNumber & org.antlr.runtime.BitSet.MOD_MASK;
        return 1 << bitPosition;
    },

    /**
     * Calculate the minimum number of bits needed to represent el.
     * @param {Number} el a number to be included in the BitSet.
     * @returns {Number} the number of bits need to create a BitSet with member
     *                   el.
     * @memberOf org.antlr.runtime.BitSet
     * @private
     */
    numWordsToHold: function(el) {
        return (el >> org.antlr.runtime.BitSet.LOG_BITS) + 1;
    },

    /**
     * @param {Number} bit a number to be included in the BitSet
     * @returns {Number} the index of the word in the field bits that would
     *                   hold bit.
     * @memberOf org.antlr.runtime.BitSet
     * @private
     */
    wordNumber: function(bit) {
        return bit >> org.antlr.runtime.BitSet.LOG_BITS; // bit / BITS
    },

    /**
     * BitSet factory method.
     *
     * <p>Operates in a number of modes:
     * <ul>
     * <li>If el is a number create the BitSet containing that number.</li>
     * <li>If el is an array create the BitSet containing each number in the
     * array.</li>
     * <li>If el is a BitSet return el.</li>
     * <li>If el is an Object create the BitSet containing each numeric value
     * in el.</li>
     * <li>If el is a number and el2 is a number return a BitSet containing
     * the numbers between el and el2 (inclusive).</li>
     * </ul>
     * </p>
     * @param {Number|Array|org.antlr.runtime.BitSet|Object} el
     * @param {Number} el2
     * @returns {org.antlr.runtime.BitSet}
     * @memberOf org.antlr.runtime.BitSet
     */
    of: function(el, el2) {
        var i, n, s, keys;

        if (org.antlr.lang.isNumber(el)) {
            if (org.antlr.lang.isNumber(el2)) {
                s = new org.antlr.runtime.BitSet(el2 + 1);
                for (i = el; i <= el2; i++) {
                    n = org.antlr.runtime.BitSet.wordNumber(i);
                    s.bits[n] |= org.antlr.runtime.BitSet.bitMask(i);
                }
                return s;
            } else {
                s = new org.antlr.runtime.BitSet(el + 1);
                s.add(el);
                return s;
            }
        } else if(org.antlr.lang.isArray(el)) {
            s = new org.antlr.runtime.BitSet();
            for (i=el.length-1; i>=0; i--) {
                s.add(el[i]);
            }
            return s;
        } else if (el instanceof org.antlr.runtime.BitSet) {
            if (!el) {
                return null;
            }
            return el;
        } else if (el instanceof org.antlr.runtime.IntervalSet) {
            if (!el) {
                return null;
            }
            s = new org.antlr.runtime.BitSet();
            s.addAll(el);
            return s;
        } else if (org.antlr.lang.isObject(el)) {
            keys = [];
            for (i in el) {
                if (org.antlr.lang.isNumber(i)) {
                    keys.push(i);
                }
            }
            return org.antlr.runtime.BitSet.of(keys);
        }
    }
});



org.antlr.runtime.BitSet.prototype = {
    /**
     * Add el into this set.
     * @param {Number} el the number to add to the set.
     */
    add: function(el) {
        var n = org.antlr.runtime.BitSet.wordNumber(el);
        if (n >= this.bits.length) {
            this.growToInclude(el);
        }
        this.bits[n] |= org.antlr.runtime.BitSet.bitMask(el);
    },

    /**
     * Add multiple elements into this set.
     * @param {Array|org.antlr.runtime.BitSet} elements the elements to be added to
     *                                           this set.
     */
    addAll: function(elements) {
        var other,
            i,
            e;

        if ( elements instanceof org.antlr.runtime.BitSet ) {
            this.orInPlace(elements);
        }
		else if ( elements instanceof org.antlr.runtime.IntervalSet ) {
			other = elements;
			// walk set and add each interval
            /* @todo after implementing intervalset
			for (Iterator iter = other.intervals.iterator(); iter.hasNext();) {
				Interval I = (Interval) iter.next();
				this.orInPlace(BitSet.range(I.a,I.b));
			}*/
		} else if (org.antlr.lang.isArray(elements)) {
    		for (i = 0; i < elements.length; i++) {
	    		e = elements[i];
		    	this.add(e);
    		}
        } else {
            return;
        }
	},

    /**
     * Clone this BitSet and then {@link #andInPlace} with a.
     * @param {org.antlr.runtime.BitSet} a a bit set.
     * @returns {org.antlr.runtime.BitSet}
     */
    and: function(a) {
        var s = this.clone();
        s.andInPlace(a);
        return s;
    },

    /**
     * Perform a logical AND of this target BitSet with the argument BitSet.
     *
     * This bit set is modified so that each bit in it has the value true if
     * and only if it both initially had the value true and the corresponding
     * bit in the bit set argument also had the value true.
     * @param {org.antlr.runtime.BitSet} a a bit set.
     * @returns {org.antlr.runtime.BitSet}
     */
    andInPlace: function(a) {
        var min = Math.min(this.bits.length, a.bits.length),
            i;
        for (i = min - 1; i >= 0; i--) {
            this.bits[i] &= a.bits[i];
        }
        // clear all bits in this not present in a (if this bigger than a).
        for (i = min; i < this.bits.length; i++) {
            this.bits[i] = 0;
        }
    },

    /**
     * Clear all bits or a specific bit.
     *
     * If no arguments given, sets all of the bits in this BitSet to false.
     * If one argument given, sets the bit specified by the index to false.
     * @param {Number} [el] the index of the bit to be cleared.
     */
    clear: function(el) {
        if (arguments.length===0) {
            var i;
            for (i = this.bits.length - 1; i >= 0; i--) {
                this.bits[i] = 0;
            }
            return;
        }

        var n = org.antlr.runtime.BitSet.wordNumber(el);
        if (n >= this.bits.length) {	// grow as necessary to accommodate
            this.growToInclude(el);
        }
        this.bits[n] &= ~org.antlr.runtime.BitSet.bitMask(el);
    },

    /**
     * Cloning this BitSet produces a new BitSet  that is equal to it.
     *
     * The clone of the bit set is another bit set that has exactly the same
     * bit set to true as this bit set.
     * @returns {org.antlr.runtime.BitSet} a clone of this BitSet.
     */
    clone: function() {
        var i, len, b=[];
        for (i=0, len=this.bits.length; i<len; i++) {
            b[i] = this.bits[i];
        }
        return new org.antlr.runtime.BitSet(b);
    },

    /**
     * Returns the number of bits of space actually in use by this BitSet to
     * represent bit values.
     *
     * The maximum element in the set is the size - 1st element.
     * @returns {Number} the number of bits currently in this bit set.
     */
    size: function() {
        var deg = 0, i, word, bit;
        for (i = this.bits.length - 1; i >= 0; i--) {
            word = this.bits[i];
            if (word !== 0) {
                for (bit = org.antlr.runtime.BitSet.BITS - 1; bit >= 0; bit--) {
                    if ((word & (1 << bit)) !== 0) {
                        deg++;
                    }
                }
            }
        }
        return deg;
    },

    /**
     * Compares this object against the specified object.
     *
     * The result is true if and only if the argument is not null and is a
     * BitSet object that has exactly the same set of bits set to true as
     * this bit set. That is, for every nonnegative int index k,
     * <pre><code>
     * ((BitSet)obj).get(k) == this.get(k)
     * </code></pre>
     * must be true. The current sizes of the two bit sets are not compared.
     * @param {Object} other the object to compare with.
     * @returns {Boolean} if the objects are the same; false otherwise.
     */
    equals: function(other) {
        if ( !other || !(other instanceof org.antlr.runtime.BitSet) ) {
            return false;
        }

        var otherSet = other,
            i,
            n = Math.min(this.bits.length, otherSet.bits.length);

        // for any bits in common, compare
        for (i=0; i<n; i++) {
            if (this.bits[i] != otherSet.bits[i]) {
                return false;
            }
        }

        // make sure any extra bits are off

        if (this.bits.length > n) {
            for (i = n+1; i<this.bits.length; i++) {
                if (this.bits[i] !== 0) {
                    return false;
                }
            }
        }
        else if (otherSet.bits.length > n) {
            for (i = n+1; i<otherSet.bits.length; i++) {
                if (otherSet.bits[i] !== 0) {
                    return false;
                }
            }
        }

        return true;
    },

    /**
     * Grows the set to a larger number of bits.
     * @param {Number} bit element that must fit in set
     * @private
     */
    growToInclude: function(bit) {
        var newSize = Math.max(this.bits.length << 1, org.antlr.runtime.BitSet.numWordsToHold(bit)),
            newbits = [], //new Array(newSize),
            i,
            len;
        for (i=0, len=this.bits.length; i<len; i++) {
            newbits[i] = this.bits[i];
        }
        this.bits = newbits;
    },

    /**
     * Returns the value of the bit with the specified index.
     *
     * The value is true if the bit with the index el is currently set
     * in this BitSet; otherwise, the result is false.
     * @param {Number} el the bit index.
     * @returns {Boolean} the value of the bit with the specified index.
     */
    member: function(el) {
        var n = org.antlr.runtime.BitSet.wordNumber(el);
        if (n >= this.bits.length) { return false; }
        return (this.bits[n] & org.antlr.runtime.BitSet.bitMask(el)) !== 0;
    },

    /**
     * Returns the index of the first bit that is set to true.
     * If no such bit exists then -1 is returned.
     * @returns {Number} the index of the next set bit.
     */
    getSingleElement: function() {
        var i;
        for (i = 0; i < (this.bits.length << org.antlr.runtime.BitSet.LOG_BITS); i++) {
            if (this.member(i)) {
                return i;
            }
        }
        return -1; //Label.INVALID;
    },

    /**
     * Returns true if this BitSet contains no bits that are set to true.
     * @returns {Boolean} boolean indicating whether this BitSet is empty.
     */
    isNil: function() {
        var i;
        for (i = this.bits.length - 1; i >= 0; i--) {
            if (this.bits[i] !== 0) {
                return false;
            }
        }
        return true;
    },

    /**
     * If a bit set argument is passed performs a {@link #subtract} of this bit
     * set with the argument bit set.  If no argument is passed, clone this bit
     * set and {@link #notInPlace}.
     * @param {org.antlr.runtime.BitSet} [set]
     * @returns {org.antlr.runtime.BitSet}
     */
    complement: function(set) {
        if (set) {
            return set.subtract(this);
        } else {
            var s = this.clone();
            s.notInPlace();
            return s;
        }
    },

    /**
     * If no arguments are passed sets all bits to the complement of their
     * current values.  If one argument is passed sets each bit from the
     * beginning of the bit set to index1 (inclusive) to the complement of its
     * current value.  If two arguments are passed sets each bit from the
     * specified index1 (inclusive) to the sepcified index2 (inclusive) to the
     * complement of its current value.
     * @param {Number} index1
     * @param {Number} index2
     */
    notInPlace: function() {
        var minBit, maxBit, i, n;
        if (arguments.length===0) {
            for (i = this.bits.length - 1; i >= 0; i--) {
                this.bits[i] = ~this.bits[i];
            }
        } else {
            if (arguments.length===1) {
                minBit = 0;
                maxBit = arguments[0];
            } else {
                minBit = arguments[0];
                maxBit = arguments[1];
            }
            // make sure that we have room for maxBit
            this.growToInclude(maxBit);
            for (i = minBit; i <= maxBit; i++) {
                n = org.antlr.runtime.BitSet.wordNumber(i);
                this.bits[n] ^= org.antlr.runtime.BitSet.bitMask(i);
            }
        }

    },

    /**
     * Performs a logical OR of this bit set with the bit set argument.
     * If no argument is passed, return this bit set.  Otherwise a clone of
     * this bit set is modified so that a bit in it has the value true if and
     * only if it either already had the value true or the corresponding bit
     * in the bit set argument has the value true.
     * @param {org.antlr.runtime.BitSet} [a] a bit set.
     * @returns {org.antlr.runtime.BitSet}
     */
    or: function(a) {
		if ( !a ) {
			return this;
		}
        var s = this.clone();
        s.orInPlace(a);
        return s;
    },

    /**
     * Performs a logical {@link #or} in place.
     * @param {org.antlr.runtime.BitSet} [a]
     * @returns {org.antlr.runtime.BitSet}
     */
    orInPlace: function(a) {
		if ( !a ) {
			return;
		}
        // If this is smaller than a, grow this first
        if (a.bits.length > this.bits.length) {
            this.setSize(a.bits.length);
        }
        var min = Math.min(this.bits.length, a.bits.length),
            i;
        for (i = min - 1; i >= 0; i--) {
            this.bits[i] |= a.bits[i];
        }
    },

    /**
     * Sets the bit specified by the index to false.
     * @param {Number} bitIndex the index of the bit to be cleared.
     */
    remove: function(el) {
        var n = org.antlr.runtime.BitSet.wordNumber(el);
        if (n >= this.bits.length) {
            this.growToInclude(el);
        }
        this.bits[n] &= ~org.antlr.runtime.BitSet.bitMask(el);
    },

    /**
     * Grows the internal bits array to include at least nwords numbers.
     * @param {Number} nwords how many words the new set should be
     * @private
     */
    setSize: function(nwords) {
        var n = nwords - this.bits.length;
        while (n>=0) {
            this.bits.push(0);
            n--;
        }
    },

    /**
     * Returns the number of bits capable of being represented by this bit set
     * given its current size.
     * @returns {Number} the maximum number of bits that can be represented at
     *                   the moment.
     * @private
     */
    numBits: function() {
        return this.bits.length << org.antlr.runtime.BitSet.LOG_BITS; // num words * bits per word
    },

    /**
     * Return how much space is being used by the bits array not
     * how many actually have member bits on.
     * @returns {Number} the length of the internal bits array.
     * @private
     */
    lengthInLongWords: function() {
        return this.bits.length;
    },

    /**
     * Is this bit set contained within a?
     * @param {org.antlr.runtime.BitSet} a bit set
     * @returns {Boolean} true if and only if a is a subset of this bit set.
     */
    subset: function(a) {
        if (!a) { return false; }
        return this.and(a).equals(this);
    },

    /**
     * Subtract the elements of the argument bit set from this bit set in place.
     * That is, for each set bit in the argument bit set, set the corresponding
     * bit in this bit set to false.
     * @param {org.antlr.runtime.BitSet} a bit set.
     */
    subtractInPlace: function(a) {
        if (!a) { return; }
        // for all words of 'a', turn off corresponding bits of 'this'
        var i;
        for (i = 0; i < this.bits.length && i < a.bits.length; i++) {
            this.bits[i] &= ~a.bits[i];
        }
    },

    /**
     * Perform a {@link #subtractInPlace} on a clone of this bit set.
     * @param {org.antlr.runtime.BitSet} a bit set.
     * @returns {org.antlr.runtime.BitSet} the new bit set.
     */
    subtract: function(a) {
        if (!a || !(a instanceof org.antlr.runtime.BitSet)) { return null; }

        var s = this.clone();
        s.subtractInPlace(a);
        return s;
    },

    /* antlr-java needs this to make its class hierarchy happy . . .
    toList: function() {
		throw new Error("BitSet.toList() unimplemented");
	},
    */

    /**
     * Creates an array of the indexes of each bit set in this bit set.
     * @returns {Array}
     */
    toArray: function() {
        var elems = [], //new Array(this.size()),
            i,
            en = 0;
        for (i = 0; i < (this.bits.length << org.antlr.runtime.BitSet.LOG_BITS); i++) {
            if (this.member(i)) {
                elems[en++] = i;
            }
        }
        return elems;
    },

    /**
     * Returns the internal representation of this bit set.
     * This representation is an array of numbers, each representing 32 bits.
     * @returns {Array}
     */
    toPackedArray: function() {
        return this.bits;
    },

    /**
     * Returns a string representation of this bit set.
     * <p>For every index for which this BitSet contains a bit in the set state,
     * the decimal representation of that index is included in the result.
     * Such indices are listed in order from lowest to highest, separated by
     * ", " (a comma and a space) and surrounded by braces, resulting in the
     * usual mathematical notation for a set of integers.</p>
     *
     * <p>If a grammar g is passed, print g.getTokenDisplayName(i) for each set
     * index instead of the numerical index.</p>
     *
     * <>If two arguments are passed, the first will be used as a custom
     * separator string.  The second argument is an array whose i-th element
     * will be added if the corresponding bit is set.</p>
     *
     * @param {Object|String} [arg1] an Object with function property
     *      getTokenDispalyName or a String that will be used as a list
     *      separator.
     * @param {Array} [vocabulary] array from which the i-th value will be
     *      drawn if the corresponding bit is set.  Must pass a string as the
     *      first argument if using this option.
     * @return A commma-separated list of values
     */
    toString: function() {
        if (arguments.length===0) {
            return this.toString1(null);
        } else {
            if (org.antlr.lang.isString(arguments[0])) {
                if (!org.antlr.lang.isValue(arguments[1])) {
                    return this.toString1(null);
                } else {
                    return this.toString2(arguments[0], arguments[1]);
                }
            } else {
                return this.toString1(arguments[0]);
            }
        }
    },

    /**
     * Transform a bit set into a string by formatting each element as an
     * integer separator The string to put in between elements
     * @private
     * @return A commma-separated list of values
     */
    toString1: function(g) {
        var buf = "{",
            separator = ",",
            i,
		    havePrintedAnElement = false;

        for (i = 0; i < (this.bits.length << org.antlr.runtime.BitSet.LOG_BITS); i++) {
            if (this.member(i)) {
                if (i > 0 && havePrintedAnElement ) {
                    buf += separator;
                }
                if ( g ) {
                    buf += g.getTokenDisplayName(i);
                }
                else {
                    buf += i.toString();
                }
				havePrintedAnElement = true;
            }
        }
        return buf + "}";
    },

    /**
     * Create a string representation where instead of integer elements, the
     * ith element of vocabulary is displayed instead.  Vocabulary is a Vector
     * of Strings.
     * separator The string to put in between elements
     * @private
     * @return A commma-separated list of character constants.
     */
    toString2: function(separator, vocabulary) {
        var str = "",
            i;
        for (i = 0; i < (this.bits.length << org.antlr.runtime.BitSet.LOG_BITS); i++) {
            if (this.member(i)) {
                if (str.length > 0) {
                    str += separator;
                }
                if (i >= vocabulary.size()) {
                    str += "'" + i + "'";
                }
                else if (!org.antlr.lang.isValue(vocabulary.get(i))) {
                    str += "'" + i + "'";
                }
                else {
                    str += vocabulary.get(i);
                }
            }
        }
        return str;
    }
};