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