Debian Codegraph @

closure-library/closure/goog/structs/stringset.js

raw
1 // Copyright 2009 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 /**
16 * @fileoverview Data structure for set of strings.
17 *
18 *
19 * This class implements a set data structure for strings. Adding and removing
20 * is O(1). It doesn't contain any bloat from {@link goog.structs.Set}, i.e.
21 * it isn't optimized for IE6 garbage collector (see the description of
22 * {@link goog.structs.Map#keys_} for details), and it distinguishes its
23 * elements by their string value not by hash code.
24 * The implementation assumes that no new keys are added to Object.prototype.
25 */
26
27 goog.provide('goog.structs.StringSet');
28
29 goog.require('goog.asserts');
30 goog.require('goog.iter');
31
32
33
34 /**
35 * Creates a set of strings.
36 * @param {!Array<?>=} opt_elements Elements to add to the set. The non-string
37 * items will be converted to strings, so 15 and '15' will mean the same.
38 * @constructor
39 * @final
40 */
41 goog.structs.StringSet = function(opt_elements) {
42 /**
43 * An object storing the escaped elements of the set in its keys.
44 * @type {!Object}
45 * @private
46 */
47 this.elements_ = {};
48
49 if (opt_elements) {
50 for (var i = 0; i < opt_elements.length; i++) {
51 this.elements_[goog.structs.StringSet.encode_(opt_elements[i])] = null;
52 }
53 }
54
55 goog.asserts.assertObjectPrototypeIsIntact();
56 };
57
58
59 /**
60 * Empty object. Referring to it is faster than creating a new empty object in
61 * {@code goog.structs.StringSet.encode_}.
62 * @const {!Object}
63 * @private
64 */
65 goog.structs.StringSet.EMPTY_OBJECT_ = {};
66
67
68 /**
69 * The '__proto__' and the '__count__' keys aren't enumerable in Firefox, and
70 * 'toString', 'valueOf', 'constructor', etc. aren't enumerable in IE so they
71 * have to be escaped before they are added to the internal object.
72 * NOTE: When a new set is created, 50-80% of the CPU time is spent in encode.
73 * @param {*} element The element to escape.
74 * @return {*} The escaped element or the element itself if it doesn't have to
75 * be escaped.
76 * @private
77 */
78 goog.structs.StringSet.encode_ = function(element) {
79 return element in goog.structs.StringSet.EMPTY_OBJECT_ ||
80 String(element).charCodeAt(0) == 32 ?
81 ' ' + element :
82 element;
83 };
84
85
86 /**
87 * Inverse function of {@code goog.structs.StringSet.encode_}.
88 * NOTE: forEach would be 30% faster in FF if the compiler inlined decode.
89 * @param {string} key The escaped element used as the key of the internal
90 * object.
91 * @return {string} The unescaped element.
92 * @private
93 */
94 goog.structs.StringSet.decode_ = function(key) {
95 return key.charCodeAt(0) == 32 ? key.substr(1) : key;
96 };
97
98
99 /**
100 * Adds a single element to the set.
101 * @param {*} element The element to add. It will be converted to string.
102 */
103 goog.structs.StringSet.prototype.add = function(element) {
104 this.elements_[goog.structs.StringSet.encode_(element)] = null;
105 };
106
107
108 /**
109 * Adds a the elements of an array to this set.
110 * @param {!Array<?>} arr The array to add the elements of.
111 */
112 goog.structs.StringSet.prototype.addArray = function(arr) {
113 for (var i = 0; i < arr.length; i++) {
114 this.elements_[goog.structs.StringSet.encode_(arr[i])] = null;
115 }
116 };
117
118
119 /**
120 * Adds the elements which are in {@code set1} but not in {@code set2} to this
121 * set.
122 * @param {!goog.structs.StringSet} set1 First set.
123 * @param {!goog.structs.StringSet} set2 Second set.
124 * @private
125 */
126 goog.structs.StringSet.prototype.addDifference_ = function(set1, set2) {
127 for (var key in set1.elements_) {
128 if (!(key in set2.elements_)) {
129 this.elements_[key] = null;
130 }
131 }
132 };
133
134
135 /**
136 * Adds a the elements of a set to this set.
137 * @param {!goog.structs.StringSet} stringSet The set to add the elements of.
138 */
139 goog.structs.StringSet.prototype.addSet = function(stringSet) {
140 for (var key in stringSet.elements_) {
141 this.elements_[key] = null;
142 }
143 };
144
145
146 /**
147 * Removes all elements of the set.
148 */
149 goog.structs.StringSet.prototype.clear = function() {
150 this.elements_ = {};
151 };
152
153
154 /**
155 * @return {!goog.structs.StringSet} Clone of the set.
156 */
157 goog.structs.StringSet.prototype.clone = function() {
158 var ret = new goog.structs.StringSet;
159 ret.addSet(this);
160 return ret;
161 };
162
163
164 /**
165 * Tells if the set contains the given element.
166 * @param {*} element The element to check.
167 * @return {boolean} Whether it is in the set.
168 */
169 goog.structs.StringSet.prototype.contains = function(element) {
170 return goog.structs.StringSet.encode_(element) in this.elements_;
171 };
172
173
174 /**
175 * Tells if the set contains all elements of the array.
176 * @param {!Array<?>} arr The elements to check.
177 * @return {boolean} Whether they are in the set.
178 */
179 goog.structs.StringSet.prototype.containsArray = function(arr) {
180 for (var i = 0; i < arr.length; i++) {
181 if (!(goog.structs.StringSet.encode_(arr[i]) in this.elements_)) {
182 return false;
183 }
184 }
185 return true;
186 };
187
188
189 /**
190 * Tells if this set has the same elements as the given set.
191 * @param {!goog.structs.StringSet} stringSet The other set.
192 * @return {boolean} Whether they have the same elements.
193 */
194 goog.structs.StringSet.prototype.equals = function(stringSet) {
195 return this.isSubsetOf(stringSet) && stringSet.isSubsetOf(this);
196 };
197
198
199 /**
200 * Calls a function for each element in the set.
201 * @param {function(string, undefined, !goog.structs.StringSet)} f The function
202 * to call for every element. It takes the element, undefined (because sets
203 * have no notion of keys), and the set.
204 * @param {Object=} opt_obj The object to be used as the value of 'this'
205 * within {@code f}.
206 */
207 goog.structs.StringSet.prototype.forEach = function(f, opt_obj) {
208 for (var key in this.elements_) {
209 f.call(opt_obj, goog.structs.StringSet.decode_(key), undefined, this);
210 }
211 };
212
213
214 /**
215 * Counts the number of elements in the set in linear time.
216 * NOTE: getCount is always called at most once per set instance in google3.
217 * If this usage pattern won't change, the linear getCount implementation is
218 * better, because
219 * <li>populating a set and getting the number of elements in it takes the same
220 * amount of time as keeping a count_ member up to date and getting its value;
221 * <li>if getCount is not called, adding and removing elements have no overhead.
222 * @return {number} The number of elements in the set.
223 */
224 goog.structs.StringSet.prototype.getCount = Object.keys ? function() {
225 return Object.keys(this.elements_).length;
226 } : function() {
227 var count = 0;
228 for (var key in this.elements_) {
229 count++;
230 }
231 return count;
232 };
233
234
235 /**
236 * Calculates the difference of two sets.
237 * @param {!goog.structs.StringSet} stringSet The set to subtract from this set.
238 * @return {!goog.structs.StringSet} {@code this} minus {@code stringSet}.
239 */
240 goog.structs.StringSet.prototype.getDifference = function(stringSet) {
241 var ret = new goog.structs.StringSet;
242 ret.addDifference_(this, stringSet);
243 return ret;
244 };
245
246
247 /**
248 * Calculates the intersection of this set with another set.
249 * @param {!goog.structs.StringSet} stringSet The set to take the intersection
250 * with.
251 * @return {!goog.structs.StringSet} A new set with the common elements.
252 */
253 goog.structs.StringSet.prototype.getIntersection = function(stringSet) {
254 var ret = new goog.structs.StringSet;
255 for (var key in this.elements_) {
256 if (key in stringSet.elements_) {
257 ret.elements_[key] = null;
258 }
259 }
260 return ret;
261 };
262
263
264 /**
265 * Calculates the symmetric difference of two sets.
266 * @param {!goog.structs.StringSet} stringSet The other set.
267 * @return {!goog.structs.StringSet} A new set with the elements in exactly one
268 * of {@code this} and {@code stringSet}.
269 */
270 goog.structs.StringSet.prototype.getSymmetricDifference = function(stringSet) {
271 var ret = new goog.structs.StringSet;
272 ret.addDifference_(this, stringSet);
273 ret.addDifference_(stringSet, this);
274 return ret;
275 };
276
277
278 /**
279 * Calculates the union of this set and another set.
280 * @param {!goog.structs.StringSet} stringSet The set to take the union with.
281 * @return {!goog.structs.StringSet} A new set with the union of elements.
282 */
283 goog.structs.StringSet.prototype.getUnion = function(stringSet) {
284 var ret = this.clone();
285 ret.addSet(stringSet);
286 return ret;
287 };
288
289
290 /**
291 * @return {!Array<string>} The elements of the set.
292 */
293 goog.structs.StringSet.prototype.getValues = Object.keys ? function() {
294 // Object.keys was introduced in JavaScript 1.8.5, Array#map in 1.6.
295 return Object.keys(this.elements_).map(goog.structs.StringSet.decode_, this);
296 } : function() {
297 var ret = [];
298 for (var key in this.elements_) {
299 ret.push(goog.structs.StringSet.decode_(key));
300 }
301 return ret;
302 };
303
304
305 /**
306 * Tells if this set and the given set are disjoint.
307 * @param {!goog.structs.StringSet} stringSet The other set.
308 * @return {boolean} True iff they don't have common elements.
309 */
310 goog.structs.StringSet.prototype.isDisjoint = function(stringSet) {
311 for (var key in this.elements_) {
312 if (key in stringSet.elements_) {
313 return false;
314 }
315 }
316 return true;
317 };
318
319
320 /**
321 * @return {boolean} Whether the set is empty.
322 */
323 goog.structs.StringSet.prototype.isEmpty = function() {
324 for (var key in this.elements_) {
325 return false;
326 }
327 return true;
328 };
329
330
331 /**
332 * Tells if this set is the subset of the given set.
333 * @param {!goog.structs.StringSet} stringSet The other set.
334 * @return {boolean} Whether this set if the subset of that.
335 */
336 goog.structs.StringSet.prototype.isSubsetOf = function(stringSet) {
337 for (var key in this.elements_) {
338 if (!(key in stringSet.elements_)) {
339 return false;
340 }
341 }
342 return true;
343 };
344
345
346 /**
347 * Tells if this set is the superset of the given set.
348 * @param {!goog.structs.StringSet} stringSet The other set.
349 * @return {boolean} Whether this set if the superset of that.
350 */
351 goog.structs.StringSet.prototype.isSupersetOf = function(stringSet) {
352 return stringSet.isSubsetOf(this);
353 };
354
355
356 /**
357 * Removes a single element from the set.
358 * @param {*} element The element to remove.
359 * @return {boolean} Whether the element was in the set.
360 */
361 goog.structs.StringSet.prototype.remove = function(element) {
362 var key = goog.structs.StringSet.encode_(element);
363 if (key in this.elements_) {
364 delete this.elements_[key];
365 return true;
366 }
367 return false;
368 };
369
370
371 /**
372 * Removes all elements of the given array from this set.
373 * @param {!Array<?>} arr The elements to remove.
374 */
375 goog.structs.StringSet.prototype.removeArray = function(arr) {
376 for (var i = 0; i < arr.length; i++) {
377 delete this.elements_[goog.structs.StringSet.encode_(arr[i])];
378 }
379 };
380
381
382 /**
383 * Removes all elements of the given set from this set.
384 * @param {!goog.structs.StringSet} stringSet The set of elements to remove.
385 */
386 goog.structs.StringSet.prototype.removeSet = function(stringSet) {
387 for (var key in stringSet.elements_) {
388 delete this.elements_[key];
389 }
390 };
391
392
393 /**
394 * Returns an iterator that iterates over the elements in the set.
395 * NOTE: creating the iterator copies the whole set so use {@link #forEach} when
396 * possible.
397 * @param {boolean=} opt_keys Ignored for sets.
398 * @return {!goog.iter.Iterator} An iterator over the elements in the set.
399 */
400 goog.structs.StringSet.prototype.__iterator__ = function(opt_keys) {
401 return goog.iter.toIterator(this.getValues());
402 };