/** * The inital size of BitSet. * @readonly * @static */ var INITAL_SIZE = 2; /** * The bit size of a single word, which is uint32. * @readonly * @static */ var BITS_PER_WORD = 32; /** * The bit size of a byte, which is 8 bits. * @readonly * @static */ var BITS_PER_BYTE = 8; /** * Implements an array of bits that grows by itself. Each bit is a boolean, * and its index is non-negative integer. * Basically it's Javascript implementation of Java's BitSet. * @constructor * @param [value] - Initial value for the BitSet. */ function BitSet(value) { if(value instanceof BitSet) { this._words = new Uint32Array(value._words); } else if(value != null) { this._words = new Uint32Array(value); } else { this._words = new Uint32Array(INITAL_SIZE); } } /** * Reallocates BitSet to expand to the requested bit size. * @private * @param bitSize {Number} - the requested bit size. */ BitSet.prototype._reallocate = function(bitSize) { while(this._words.length <= ((bitSize / BITS_PER_WORD)|0)) { var newWords = new Uint32Array(this._words.length * 2); newWords.set(this._words); this._words = newWords; } } /** * Returns BitSet's allocated size in bits. * @returns {Number} allocated size in bits. */ BitSet.prototype.size = function() { return this._words.byteLength * BITS_PER_BYTE; } /** * Sets specified bit to false. * @param pos {Number} - The bit position to set to false. * @see {@link BitSet#set} */ BitSet.prototype.clear = function(pos) { this.set(pos, false); } /** * Sets specified range of bits to false. * @param from {Number} - The start bit position. * @param to {Number} - The end bit position. * @see {@link BitSet#setRange} */ BitSet.prototype.clearRange = function(from, to) { this.setRange(from, to, false); } /** * Sets all bits to false. * @see {@link BitSet#setAll} */ BitSet.prototype.clearAll = function() { this.setAll(false); } /** * Sets specified bit. * @param pos {Number} - The bit position to set. * @param set {Boolean} - The value to set. */ BitSet.prototype.set = function(pos, set) { pos |= 0; this._reallocate(pos); var wordPos = pos / BITS_PER_WORD | 0; var shiftPos = (pos % BITS_PER_WORD); if(set) { this._words[wordPos] |= 1 << shiftPos; } else { this._words[wordPos] &= ~(1 << shiftPos); } } /** * Sets specified range of bits. * @param from {Number} - The start bit position. * @param to {Number} - The end bit position. * @param set {Boolean} - The value to set. */ BitSet.prototype.setRange = function(from, to, set) { for(var i = from; i <= to; ++i) { this.set(i, set); } } /** * Sets all bits. * @param set {Boolean} - The value to set. */ BitSet.prototype.setAll = function(set) { var val = 0; if(set) val = ~0; for(var i = 0; i < this._words.length; ++i) { this._words[i] = val; } } /** * Returns the value of specified bit. * @param pos {Number} - The bit position. * @returns {Boolean} Whether if the bit is set or not. */ BitSet.prototype.get = function(pos) { pos |= 0; this._reallocate(pos); var wordPos = pos / BITS_PER_WORD | 0; var shiftPos = (pos % BITS_PER_WORD); return (this._words[wordPos] & (1 << shiftPos)) != 0; } // logic functions // aka intersection /** * Performs AND logical operation on two BitSet. * That means it will be set to 1 if both are 1, 0 otherwise. * The result will be applied to this BitSet. * @param set {BitSet} - The other BitSet. */ BitSet.prototype.and = function(set) { if(set == null) { this.clearAll(); return; } var intersectSize = Math.min(this._words.length, set._words.length)|0; var unionSize = Math.max(this._words.length, set._words.length)|0; this._reallocate(unionSize * BITS_PER_WORD); for(var i = 0; i < unionSize; ++i) { if(i > intersectSize) { this._words[i] = 0; } else { this._words[i] &= set._words[i]; } } } // aka union /** * Performs OR logical operation on two BitSet. * That means it will be set to 1 if one of them is 1, 0 if both are 0. * The result will be applied to this BitSet. * @param set {BitSet} - The other BitSet. */ BitSet.prototype.or = function(set) { if(set == null) { return; } var unionSize = Math.max(this._words.length, set._words.length)|0; this._reallocate(unionSize * BITS_PER_WORD-1); for(var i = 0; i < unionSize; ++i) { this._words[i] |= set._words[i]; } } // ??? /** * Performs XOR logical operation on two BitSet. * That means it will be set to 1 if the bits are different, 0 if they're same. * The result will be applied to this BitSet. * @param set {BitSet} - The other BitSet. */ BitSet.prototype.xor = function(set) { if(set == null) { return; } var unionSize = Math.max(this._words.length, set._words.length)|0; this._reallocate(unionSize * BITS_PER_WORD-1); for(var i = 0; i < unionSize; ++i) { this._words[i] ^= set._words[i]; } } /** * Performs NOT logical operation on the BitSet. * That means it will be set to 1 if bit is 0, 0 otherwise. * The result will be applied to this BitSet. */ BitSet.prototype.not = function() { for(var i = 0; i < this._words.length; ++i) { this._words[i] = ~this._words[i]; } } // compare functions /** * Checkes whether the BitSet is filled with 0. * This function will return false if the BitSet has any bit that is set to 1. * @returns {Boolean} Whether if the BitSet is empty. */ BitSet.prototype.isEmpty = function() { for(var i = 0; i < this._words.length; ++i) { if(this._words[i]) return false; } return true; } /** * Checks if two BitSet has a same bit to set to 1. * This function will return true if they have matching part, false otherwise. * @param set - The other BitSet. * @returns {Boolean} Whether if two BitSet intersects. */ BitSet.prototype.intersects = function(set) { if(set == null) { return false; } var intersectSize = Math.min(this._words.length, set._words.length)|0; for(var i = 0; i < intersectSize; ++i) { if(this._words[i] & set._words[i]) return true; } return false; } // this -> set /** * Checks if this BitSet contains all the bits from the other BitSet. * This function will return true if , false otherwise. * @param set - The other BitSet. * @returns {Boolean} Whether if two BitSet intersects. */ BitSet.prototype.contains = function(set) { if(set == null) { return false; } var intersectSize = Math.min(this._words.length, set._words.length)|0; for(var i = 0; i < intersectSize; ++i) { if((this._words[i] & set._words[i]) != set._words[i]) return false; } return true; } /** * Checks if two BitSet is same. * This function will return true if they are same, false otherwise. * @param set - The other BitSet. * @returns {Boolean} Whether if two BitSet equals. */ BitSet.prototype.equals = function(set) { if(set == null || !(set instanceof BitSet)) { return false; } var intersectSize = Math.min(this._words.length, set._words.length)|0; var unionSize = Math.max(this._words.length, set._words.length)|0; for(var i = 0; i < unionSize; ++i) { if(i > intersectSize) { if(this._words.length < set._words.length) { if(set._words[i]) return false; } else { if(this._words[i]) return false; } } else { if((this._words[i] ^ set._words[i])) return false; } } return true; } /** * Changes the BitSet to String form. * @param {Number} [redix=2] - The redix to use. * @returns {String} The stringified BitSet. */ BitSet.prototype.toString = function(redix) { var map = []; for(var i = 0; i < this._words.length; ++i) { var value = this._words[i]; map.push(value.toString(redix || 2)); } return map.reverse().join(' '); } if(typeof module !== 'undefined') { module.exports = BitSet; }