Debian Codegraph @

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

raw
1 // Copyright 2006 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 Datastructure: Hash Map.
17 *
18 * @author [email protected] (Erik Arvidsson)
19 *
20 * This file contains an implementation of a Map structure. It implements a lot
21 * of the methods used in goog.structs so those functions work on hashes. This
22 * is best suited for complex key types. For simple keys such as numbers and
23 * strings consider using the lighter-weight utilities in goog.object.
24 */
25
26
27 goog.provide('goog.structs.Map');
28
29 goog.require('goog.iter.Iterator');
30 goog.require('goog.iter.StopIteration');
31 goog.require('goog.object');
32
33
34
35 /**
36 * Class for Hash Map datastructure.
37 * @param {*=} opt_map Map or Object to initialize the map with.
38 * @param {...*} var_args If 2 or more arguments are present then they
39 * will be used as key-value pairs.
40 * @constructor
41 * @template K, V
42 * @deprecated This type is misleading: use ES6 Map instead.
43 */
44 goog.structs.Map = function(opt_map, var_args) {
45
46 /**
47 * Underlying JS object used to implement the map.
48 * @private {!Object}
49 */
50 this.map_ = {};
51
52 /**
53 * An array of keys. This is necessary for two reasons:
54 * 1. Iterating the keys using for (var key in this.map_) allocates an
55 * object for every key in IE which is really bad for IE6 GC perf.
56 * 2. Without a side data structure, we would need to escape all the keys
57 * as that would be the only way we could tell during iteration if the
58 * key was an internal key or a property of the object.
59 *
60 * This array can contain deleted keys so it's necessary to check the map
61 * as well to see if the key is still in the map (this doesn't require a
62 * memory allocation in IE).
63 * @private {!Array<string>}
64 */
65 this.keys_ = [];
66
67 /**
68 * The number of key value pairs in the map.
69 * @private {number}
70 */
71 this.count_ = 0;
72
73 /**
74 * Version used to detect changes while iterating.
75 * @private {number}
76 */
77 this.version_ = 0;
78
79 var argLength = arguments.length;
80
81 if (argLength > 1) {
82 if (argLength % 2) {
83 throw new Error('Uneven number of arguments');
84 }
85 for (var i = 0; i < argLength; i += 2) {
86 this.set(arguments[i], arguments[i + 1]);
87 }
88 } else if (opt_map) {
89 this.addAll(/** @type {Object} */ (opt_map));
90 }
91 };
92
93
94 /**
95 * @return {number} The number of key-value pairs in the map.
96 */
97 goog.structs.Map.prototype.getCount = function() {
98 return this.count_;
99 };
100
101
102 /**
103 * Returns the values of the map.
104 * @return {!Array<V>} The values in the map.
105 */
106 goog.structs.Map.prototype.getValues = function() {
107 this.cleanupKeysArray_();
108
109 var rv = [];
110 for (var i = 0; i < this.keys_.length; i++) {
111 var key = this.keys_[i];
112 rv.push(this.map_[key]);
113 }
114 return rv;
115 };
116
117
118 /**
119 * Returns the keys of the map.
120 * @return {!Array<string>} Array of string values.
121 */
122 goog.structs.Map.prototype.getKeys = function() {
123 this.cleanupKeysArray_();
124 return /** @type {!Array<string>} */ (this.keys_.concat());
125 };
126
127
128 /**
129 * Whether the map contains the given key.
130 * @param {*} key The key to check for.
131 * @return {boolean} Whether the map contains the key.
132 */
133 goog.structs.Map.prototype.containsKey = function(key) {
134 return goog.structs.Map.hasKey_(this.map_, key);
135 };
136
137
138 /**
139 * Whether the map contains the given value. This is O(n).
140 * @param {V} val The value to check for.
141 * @return {boolean} Whether the map contains the value.
142 */
143 goog.structs.Map.prototype.containsValue = function(val) {
144 for (var i = 0; i < this.keys_.length; i++) {
145 var key = this.keys_[i];
146 if (goog.structs.Map.hasKey_(this.map_, key) && this.map_[key] == val) {
147 return true;
148 }
149 }
150 return false;
151 };
152
153
154 /**
155 * Whether this map is equal to the argument map.
156 * @param {goog.structs.Map} otherMap The map against which to test equality.
157 * @param {function(V, V): boolean=} opt_equalityFn Optional equality function
158 * to test equality of values. If not specified, this will test whether
159 * the values contained in each map are identical objects.
160 * @return {boolean} Whether the maps are equal.
161 */
162 goog.structs.Map.prototype.equals = function(otherMap, opt_equalityFn) {
163 if (this === otherMap) {
164 return true;
165 }
166
167 if (this.count_ != otherMap.getCount()) {
168 return false;
169 }
170
171 var equalityFn = opt_equalityFn || goog.structs.Map.defaultEquals;
172
173 this.cleanupKeysArray_();
174 for (var key, i = 0; key = this.keys_[i]; i++) {
175 if (!equalityFn(this.get(key), otherMap.get(key))) {
176 return false;
177 }
178 }
179
180 return true;
181 };
182
183
184 /**
185 * Default equality test for values.
186 * @param {*} a The first value.
187 * @param {*} b The second value.
188 * @return {boolean} Whether a and b reference the same object.
189 */
190 goog.structs.Map.defaultEquals = function(a, b) {
191 return a === b;
192 };
193
194
195 /**
196 * @return {boolean} Whether the map is empty.
197 */
198 goog.structs.Map.prototype.isEmpty = function() {
199 return this.count_ == 0;
200 };
201
202
203 /**
204 * Removes all key-value pairs from the map.
205 */
206 goog.structs.Map.prototype.clear = function() {
207 this.map_ = {};
208 this.keys_.length = 0;
209 this.count_ = 0;
210 this.version_ = 0;
211 };
212
213
214 /**
215 * Removes a key-value pair based on the key. This is O(logN) amortized due to
216 * updating the keys array whenever the count becomes half the size of the keys
217 * in the keys array.
218 * @param {*} key The key to remove.
219 * @return {boolean} Whether object was removed.
220 */
221 goog.structs.Map.prototype.remove = function(key) {
222 if (goog.structs.Map.hasKey_(this.map_, key)) {
223 delete this.map_[key];
224 this.count_--;
225 this.version_++;
226
227 // clean up the keys array if the threshold is hit
228 if (this.keys_.length > 2 * this.count_) {
229 this.cleanupKeysArray_();
230 }
231
232 return true;
233 }
234 return false;
235 };
236
237
238 /**
239 * Cleans up the temp keys array by removing entries that are no longer in the
240 * map.
241 * @private
242 */
243 goog.structs.Map.prototype.cleanupKeysArray_ = function() {
244 if (this.count_ != this.keys_.length) {
245 // First remove keys that are no longer in the map.
246 var srcIndex = 0;
247 var destIndex = 0;
248 while (srcIndex < this.keys_.length) {
249 var key = this.keys_[srcIndex];
250 if (goog.structs.Map.hasKey_(this.map_, key)) {
251 this.keys_[destIndex++] = key;
252 }
253 srcIndex++;
254 }
255 this.keys_.length = destIndex;
256 }
257
258 if (this.count_ != this.keys_.length) {
259 // If the count still isn't correct, that means we have duplicates. This can
260 // happen when the same key is added and removed multiple times. Now we have
261 // to allocate one extra Object to remove the duplicates. This could have
262 // been done in the first pass, but in the common case, we can avoid
263 // allocating an extra object by only doing this when necessary.
264 var seen = {};
265 var srcIndex = 0;
266 var destIndex = 0;
267 while (srcIndex < this.keys_.length) {
268 var key = this.keys_[srcIndex];
269 if (!(goog.structs.Map.hasKey_(seen, key))) {
270 this.keys_[destIndex++] = key;
271 seen[key] = 1;
272 }
273 srcIndex++;
274 }
275 this.keys_.length = destIndex;
276 }
277 };
278
279
280 /**
281 * Returns the value for the given key. If the key is not found and the default
282 * value is not given this will return {@code undefined}.
283 * @param {*} key The key to get the value for.
284 * @param {DEFAULT=} opt_val The value to return if no item is found for the
285 * given key, defaults to undefined.
286 * @return {V|DEFAULT} The value for the given key.
287 * @template DEFAULT
288 */
289 goog.structs.Map.prototype.get = function(key, opt_val) {
290 if (goog.structs.Map.hasKey_(this.map_, key)) {
291 return this.map_[key];
292 }
293 return opt_val;
294 };
295
296
297 /**
298 * Adds a key-value pair to the map.
299 * @param {*} key The key.
300 * @param {V} value The value to add.
301 * @return {*} Some subclasses return a value.
302 */
303 goog.structs.Map.prototype.set = function(key, value) {
304 if (!(goog.structs.Map.hasKey_(this.map_, key))) {
305 this.count_++;
306 // TODO(johnlenz): This class lies, it claims to return an array of string
307 // keys, but instead returns the original object used.
308 this.keys_.push(/** @type {?} */ (key));
309 // Only change the version if we add a new key.
310 this.version_++;
311 }
312 this.map_[key] = value;
313 };
314
315
316 /**
317 * Adds multiple key-value pairs from another goog.structs.Map or Object.
318 * @param {Object} map Object containing the data to add.
319 */
320 goog.structs.Map.prototype.addAll = function(map) {
321 var keys, values;
322 if (map instanceof goog.structs.Map) {
323 keys = map.getKeys();
324 values = map.getValues();
325 } else {
326 keys = goog.object.getKeys(map);
327 values = goog.object.getValues(map);
328 }
329 // we could use goog.array.forEach here but I don't want to introduce that
330 // dependency just for this.
331 for (var i = 0; i < keys.length; i++) {
332 this.set(keys[i], values[i]);
333 }
334 };
335
336
337 /**
338 * Calls the given function on each entry in the map.
339 * @param {function(this:T, V, K, goog.structs.Map<K,V>)} f
340 * @param {T=} opt_obj The value of "this" inside f.
341 * @template T
342 */
343 goog.structs.Map.prototype.forEach = function(f, opt_obj) {
344 var keys = this.getKeys();
345 for (var i = 0; i < keys.length; i++) {
346 var key = keys[i];
347 var value = this.get(key);
348 f.call(opt_obj, value, key, this);
349 }
350 };
351
352
353 /**
354 * Clones a map and returns a new map.
355 * @return {!goog.structs.Map} A new map with the same key-value pairs.
356 */
357 goog.structs.Map.prototype.clone = function() {
358 return new goog.structs.Map(this);
359 };
360
361
362 /**
363 * Returns a new map in which all the keys and values are interchanged
364 * (keys become values and values become keys). If multiple keys map to the
365 * same value, the chosen transposed value is implementation-dependent.
366 *
367 * It acts very similarly to {goog.object.transpose(Object)}.
368 *
369 * @return {!goog.structs.Map} The transposed map.
370 */
371 goog.structs.Map.prototype.transpose = function() {
372 var transposed = new goog.structs.Map();
373 for (var i = 0; i < this.keys_.length; i++) {
374 var key = this.keys_[i];
375 var value = this.map_[key];
376 transposed.set(value, key);
377 }
378
379 return transposed;
380 };
381
382
383 /**
384 * @return {!Object} Object representation of the map.
385 */
386 goog.structs.Map.prototype.toObject = function() {
387 this.cleanupKeysArray_();
388 var obj = {};
389 for (var i = 0; i < this.keys_.length; i++) {
390 var key = this.keys_[i];
391 obj[key] = this.map_[key];
392 }
393 return obj;
394 };
395
396
397 /**
398 * Returns an iterator that iterates over the keys in the map. Removal of keys
399 * while iterating might have undesired side effects.
400 * @return {!goog.iter.Iterator} An iterator over the keys in the map.
401 */
402 goog.structs.Map.prototype.getKeyIterator = function() {
403 return this.__iterator__(true);
404 };
405
406
407 /**
408 * Returns an iterator that iterates over the values in the map. Removal of
409 * keys while iterating might have undesired side effects.
410 * @return {!goog.iter.Iterator} An iterator over the values in the map.
411 */
412 goog.structs.Map.prototype.getValueIterator = function() {
413 return this.__iterator__(false);
414 };
415
416
417 /**
418 * Returns an iterator that iterates over the values or the keys in the map.
419 * This throws an exception if the map was mutated since the iterator was
420 * created.
421 * @param {boolean=} opt_keys True to iterate over the keys. False to iterate
422 * over the values. The default value is false.
423 * @return {!goog.iter.Iterator} An iterator over the values or keys in the map.
424 */
425 goog.structs.Map.prototype.__iterator__ = function(opt_keys) {
426 // Clean up keys to minimize the risk of iterating over dead keys.
427 this.cleanupKeysArray_();
428
429 var i = 0;
430 var version = this.version_;
431 var selfObj = this;
432
433 var newIter = new goog.iter.Iterator;
434 newIter.next = function() {
435 if (version != selfObj.version_) {
436 throw new Error('The map has changed since the iterator was created');
437 }
438 if (i >= selfObj.keys_.length) {
439 throw goog.iter.StopIteration;
440 }
441 var key = selfObj.keys_[i++];
442 return opt_keys ? key : selfObj.map_[key];
443 };
444 return newIter;
445 };
446
447
448 /**
449 * Safe way to test for hasOwnProperty. It even allows testing for
450 * 'hasOwnProperty'.
451 * @param {Object} obj The object to test for presence of the given key.
452 * @param {*} key The key to check for.
453 * @return {boolean} Whether the object has the key.
454 * @private
455 */
456 goog.structs.Map.hasKey_ = function(obj, key) {
457 return Object.prototype.hasOwnProperty.call(obj, key);
458 };