diff options
Diffstat (limited to 'runtime/JavaScript/src/org/antlr/runtime/BitSet.js')
| -rwxr-xr-x | runtime/JavaScript/src/org/antlr/runtime/BitSet.js | 706 |
1 files changed, 706 insertions, 0 deletions
diff --git a/runtime/JavaScript/src/org/antlr/runtime/BitSet.js b/runtime/JavaScript/src/org/antlr/runtime/BitSet.js new file mode 100755 index 0000000..99bfda1 --- /dev/null +++ b/runtime/JavaScript/src/org/antlr/runtime/BitSet.js @@ -0,0 +1,706 @@ +/** + * 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; + } +}; |