| // Copyright 2009 The Closure Library Authors. All Rights Reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS-IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| /** |
| * @fileoverview Data structure for set of strings. |
| * |
| * |
| * This class implements a set data structure for strings. Adding and removing |
| * is O(1). It doesn't contain any bloat from {@link goog.structs.Set}, i.e. |
| * it isn't optimized for IE6 garbage collector (see the description of |
| * {@link goog.structs.Map#keys_} for details), and it distinguishes its |
| * elements by their string value not by hash code. |
| * The implementation assumes that no new keys are added to Object.prototype. |
| */ |
| |
| goog.provide('goog.structs.StringSet'); |
| |
| goog.require('goog.asserts'); |
| goog.require('goog.iter'); |
| |
| |
| |
| /** |
| * Creates a set of strings. |
| * @param {!Array<?>=} opt_elements Elements to add to the set. The non-string |
| * items will be converted to strings, so 15 and '15' will mean the same. |
| * @constructor |
| * @final |
| */ |
| goog.structs.StringSet = function(opt_elements) { |
| /** |
| * An object storing the escaped elements of the set in its keys. |
| * @type {!Object} |
| * @private |
| */ |
| this.elements_ = {}; |
| |
| if (opt_elements) { |
| for (var i = 0; i < opt_elements.length; i++) { |
| this.elements_[goog.structs.StringSet.encode_(opt_elements[i])] = null; |
| } |
| } |
| |
| goog.asserts.assertObjectPrototypeIsIntact(); |
| }; |
| |
| |
| /** |
| * Empty object. Referring to it is faster than creating a new empty object in |
| * {@code goog.structs.StringSet.encode_}. |
| * @const {!Object} |
| * @private |
| */ |
| goog.structs.StringSet.EMPTY_OBJECT_ = {}; |
| |
| |
| /** |
| * The '__proto__' and the '__count__' keys aren't enumerable in Firefox, and |
| * 'toString', 'valueOf', 'constructor', etc. aren't enumerable in IE so they |
| * have to be escaped before they are added to the internal object. |
| * NOTE: When a new set is created, 50-80% of the CPU time is spent in encode. |
| * @param {*} element The element to escape. |
| * @return {*} The escaped element or the element itself if it doesn't have to |
| * be escaped. |
| * @private |
| */ |
| goog.structs.StringSet.encode_ = function(element) { |
| return element in goog.structs.StringSet.EMPTY_OBJECT_ || |
| String(element).charCodeAt(0) == 32 ? ' ' + element : element; |
| }; |
| |
| |
| /** |
| * Inverse function of {@code goog.structs.StringSet.encode_}. |
| * NOTE: forEach would be 30% faster in FF if the compiler inlined decode. |
| * @param {string} key The escaped element used as the key of the internal |
| * object. |
| * @return {string} The unescaped element. |
| * @private |
| */ |
| goog.structs.StringSet.decode_ = function(key) { |
| return key.charCodeAt(0) == 32 ? key.substr(1) : key; |
| }; |
| |
| |
| /** |
| * Adds a single element to the set. |
| * @param {*} element The element to add. It will be converted to string. |
| */ |
| goog.structs.StringSet.prototype.add = function(element) { |
| this.elements_[goog.structs.StringSet.encode_(element)] = null; |
| }; |
| |
| |
| /** |
| * Adds a the elements of an array to this set. |
| * @param {!Array<?>} arr The array to add the elements of. |
| */ |
| goog.structs.StringSet.prototype.addArray = function(arr) { |
| for (var i = 0; i < arr.length; i++) { |
| this.elements_[goog.structs.StringSet.encode_(arr[i])] = null; |
| } |
| }; |
| |
| |
| /** |
| * Adds the elements which are in {@code set1} but not in {@code set2} to this |
| * set. |
| * @param {!goog.structs.StringSet} set1 First set. |
| * @param {!goog.structs.StringSet} set2 Second set. |
| * @private |
| */ |
| goog.structs.StringSet.prototype.addDifference_ = function(set1, set2) { |
| for (var key in set1.elements_) { |
| if (!(key in set2.elements_)) { |
| this.elements_[key] = null; |
| } |
| } |
| }; |
| |
| |
| /** |
| * Adds a the elements of a set to this set. |
| * @param {!goog.structs.StringSet} stringSet The set to add the elements of. |
| */ |
| goog.structs.StringSet.prototype.addSet = function(stringSet) { |
| for (var key in stringSet.elements_) { |
| this.elements_[key] = null; |
| } |
| }; |
| |
| |
| /** |
| * Removes all elements of the set. |
| */ |
| goog.structs.StringSet.prototype.clear = function() { |
| this.elements_ = {}; |
| }; |
| |
| |
| /** |
| * @return {!goog.structs.StringSet} Clone of the set. |
| */ |
| goog.structs.StringSet.prototype.clone = function() { |
| var ret = new goog.structs.StringSet; |
| ret.addSet(this); |
| return ret; |
| }; |
| |
| |
| /** |
| * Tells if the set contains the given element. |
| * @param {*} element The element to check. |
| * @return {boolean} Whether it is in the set. |
| */ |
| goog.structs.StringSet.prototype.contains = function(element) { |
| return goog.structs.StringSet.encode_(element) in this.elements_; |
| }; |
| |
| |
| /** |
| * Tells if the set contains all elements of the array. |
| * @param {!Array<?>} arr The elements to check. |
| * @return {boolean} Whether they are in the set. |
| */ |
| goog.structs.StringSet.prototype.containsArray = function(arr) { |
| for (var i = 0; i < arr.length; i++) { |
| if (!(goog.structs.StringSet.encode_(arr[i]) in this.elements_)) { |
| return false; |
| } |
| } |
| return true; |
| }; |
| |
| |
| /** |
| * Tells if this set has the same elements as the given set. |
| * @param {!goog.structs.StringSet} stringSet The other set. |
| * @return {boolean} Whether they have the same elements. |
| */ |
| goog.structs.StringSet.prototype.equals = function(stringSet) { |
| return this.isSubsetOf(stringSet) && stringSet.isSubsetOf(this); |
| }; |
| |
| |
| /** |
| * Calls a function for each element in the set. |
| * @param {function(string, undefined, !goog.structs.StringSet)} f The function |
| * to call for every element. It takes the element, undefined (because sets |
| * have no notion of keys), and the set. |
| * @param {Object=} opt_obj The object to be used as the value of 'this' |
| * within {@code f}. |
| */ |
| goog.structs.StringSet.prototype.forEach = function(f, opt_obj) { |
| for (var key in this.elements_) { |
| f.call(opt_obj, goog.structs.StringSet.decode_(key), undefined, this); |
| } |
| }; |
| |
| |
| /** |
| * Counts the number of elements in the set in linear time. |
| * NOTE: getCount is always called at most once per set instance in google3. |
| * If this usage pattern won't change, the linear getCount implementation is |
| * better, because |
| * <li>populating a set and getting the number of elements in it takes the same |
| * amount of time as keeping a count_ member up to date and getting its value; |
| * <li>if getCount is not called, adding and removing elements have no overhead. |
| * @return {number} The number of elements in the set. |
| */ |
| goog.structs.StringSet.prototype.getCount = Object.keys ? |
| function() { |
| return Object.keys(this.elements_).length; |
| } : |
| function() { |
| var count = 0; |
| for (var key in this.elements_) { |
| count++; |
| } |
| return count; |
| }; |
| |
| |
| /** |
| * Calculates the difference of two sets. |
| * @param {!goog.structs.StringSet} stringSet The set to subtract from this set. |
| * @return {!goog.structs.StringSet} {@code this} minus {@code stringSet}. |
| */ |
| goog.structs.StringSet.prototype.getDifference = function(stringSet) { |
| var ret = new goog.structs.StringSet; |
| ret.addDifference_(this, stringSet); |
| return ret; |
| }; |
| |
| |
| /** |
| * Calculates the intersection of this set with another set. |
| * @param {!goog.structs.StringSet} stringSet The set to take the intersection |
| * with. |
| * @return {!goog.structs.StringSet} A new set with the common elements. |
| */ |
| goog.structs.StringSet.prototype.getIntersection = function(stringSet) { |
| var ret = new goog.structs.StringSet; |
| for (var key in this.elements_) { |
| if (key in stringSet.elements_) { |
| ret.elements_[key] = null; |
| } |
| } |
| return ret; |
| }; |
| |
| |
| /** |
| * Calculates the symmetric difference of two sets. |
| * @param {!goog.structs.StringSet} stringSet The other set. |
| * @return {!goog.structs.StringSet} A new set with the elements in exactly one |
| * of {@code this} and {@code stringSet}. |
| */ |
| goog.structs.StringSet.prototype.getSymmetricDifference = function(stringSet) { |
| var ret = new goog.structs.StringSet; |
| ret.addDifference_(this, stringSet); |
| ret.addDifference_(stringSet, this); |
| return ret; |
| }; |
| |
| |
| /** |
| * Calculates the union of this set and another set. |
| * @param {!goog.structs.StringSet} stringSet The set to take the union with. |
| * @return {!goog.structs.StringSet} A new set with the union of elements. |
| */ |
| goog.structs.StringSet.prototype.getUnion = function(stringSet) { |
| var ret = this.clone(); |
| ret.addSet(stringSet); |
| return ret; |
| }; |
| |
| |
| /** |
| * @return {!Array<string>} The elements of the set. |
| */ |
| goog.structs.StringSet.prototype.getValues = Object.keys ? |
| function() { |
| // Object.keys was introduced in JavaScript 1.8.5, Array#map in 1.6. |
| return Object.keys(this.elements_).map( |
| goog.structs.StringSet.decode_, this); |
| } : |
| function() { |
| var ret = []; |
| for (var key in this.elements_) { |
| ret.push(goog.structs.StringSet.decode_(key)); |
| } |
| return ret; |
| }; |
| |
| |
| /** |
| * Tells if this set and the given set are disjoint. |
| * @param {!goog.structs.StringSet} stringSet The other set. |
| * @return {boolean} True iff they don't have common elements. |
| */ |
| goog.structs.StringSet.prototype.isDisjoint = function(stringSet) { |
| for (var key in this.elements_) { |
| if (key in stringSet.elements_) { |
| return false; |
| } |
| } |
| return true; |
| }; |
| |
| |
| /** |
| * @return {boolean} Whether the set is empty. |
| */ |
| goog.structs.StringSet.prototype.isEmpty = function() { |
| for (var key in this.elements_) { |
| return false; |
| } |
| return true; |
| }; |
| |
| |
| /** |
| * Tells if this set is the subset of the given set. |
| * @param {!goog.structs.StringSet} stringSet The other set. |
| * @return {boolean} Whether this set if the subset of that. |
| */ |
| goog.structs.StringSet.prototype.isSubsetOf = function(stringSet) { |
| for (var key in this.elements_) { |
| if (!(key in stringSet.elements_)) { |
| return false; |
| } |
| } |
| return true; |
| }; |
| |
| |
| /** |
| * Tells if this set is the superset of the given set. |
| * @param {!goog.structs.StringSet} stringSet The other set. |
| * @return {boolean} Whether this set if the superset of that. |
| */ |
| goog.structs.StringSet.prototype.isSupersetOf = function(stringSet) { |
| return stringSet.isSubsetOf(this); |
| }; |
| |
| |
| /** |
| * Removes a single element from the set. |
| * @param {*} element The element to remove. |
| * @return {boolean} Whether the element was in the set. |
| */ |
| goog.structs.StringSet.prototype.remove = function(element) { |
| var key = goog.structs.StringSet.encode_(element); |
| if (key in this.elements_) { |
| delete this.elements_[key]; |
| return true; |
| } |
| return false; |
| }; |
| |
| |
| /** |
| * Removes all elements of the given array from this set. |
| * @param {!Array<?>} arr The elements to remove. |
| */ |
| goog.structs.StringSet.prototype.removeArray = function(arr) { |
| for (var i = 0; i < arr.length; i++) { |
| delete this.elements_[goog.structs.StringSet.encode_(arr[i])]; |
| } |
| }; |
| |
| |
| /** |
| * Removes all elements of the given set from this set. |
| * @param {!goog.structs.StringSet} stringSet The set of elements to remove. |
| */ |
| goog.structs.StringSet.prototype.removeSet = function(stringSet) { |
| for (var key in stringSet.elements_) { |
| delete this.elements_[key]; |
| } |
| }; |
| |
| |
| /** |
| * Returns an iterator that iterates over the elements in the set. |
| * NOTE: creating the iterator copies the whole set so use {@link #forEach} when |
| * possible. |
| * @param {boolean=} opt_keys Ignored for sets. |
| * @return {!goog.iter.Iterator} An iterator over the elements in the set. |
| */ |
| goog.structs.StringSet.prototype.__iterator__ = function(opt_keys) { |
| return goog.iter.toIterator(this.getValues()); |
| }; |