Debian Codegraph @

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

raw
1 // Copyright 2012 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 A map data structure that offers a convenient API to
17 * manipulate a key, value map. The key must be a string.
18 *
19 * This implementation also ensure that you can use keys that would
20 * not be usable using a normal object literal {}. Some examples
21 * include __proto__ (all newer browsers), toString/hasOwnProperty (IE
22 * <= 8).
23 * @author [email protected] (Chris Henry)
24 */
25
26 goog.provide('goog.labs.structs.Map');
27
28 goog.require('goog.array');
29 goog.require('goog.asserts');
30 goog.require('goog.object');
31
32
33
34 /**
35 * Creates a new map.
36 * @constructor
37 * @struct
38 * @final
39 */
40 goog.labs.structs.Map = function() {
41 // clear() initializes the map to the empty state.
42 this.clear();
43 };
44
45
46 /**
47 * @type {function(this: Object, string): boolean}
48 * @private
49 */
50 goog.labs.structs.Map.objectPropertyIsEnumerable_ =
51 Object.prototype.propertyIsEnumerable;
52
53
54 /**
55 * @type {function(this: Object, string): boolean}
56 * @private
57 */
58 goog.labs.structs.Map.objectHasOwnProperty_ = Object.prototype.hasOwnProperty;
59
60
61 /**
62 * Primary backing store of this map.
63 * @type {!Object}
64 * @private
65 */
66 goog.labs.structs.Map.prototype.map_;
67
68
69 /**
70 * Secondary backing store for keys. The index corresponds to the
71 * index for secondaryStoreValues_.
72 * @type {!Array<string>}
73 * @private
74 */
75 goog.labs.structs.Map.prototype.secondaryStoreKeys_;
76
77
78 /**
79 * Secondary backing store for keys. The index corresponds to the
80 * index for secondaryStoreValues_.
81 * @type {!Array<*>}
82 * @private
83 */
84 goog.labs.structs.Map.prototype.secondaryStoreValues_;
85
86
87 /**
88 * @private {number}
89 */
90 goog.labs.structs.Map.prototype.count_;
91
92
93 /**
94 * Adds the (key, value) pair, overriding previous entry with the same
95 * key, if any.
96 * @param {string} key The key.
97 * @param {*} value The value.
98 */
99 goog.labs.structs.Map.prototype.set = function(key, value) {
100 this.assertKeyIsString_(key);
101
102 var newKey = !this.hasKeyInPrimaryStore_(key);
103 this.map_[key] = value;
104
105 // __proto__ is not settable on object.
106 if (key == '__proto__' ||
107 // Shadows for built-in properties are not enumerable in IE <= 8 .
108 (!goog.labs.structs.Map.BrowserFeature.OBJECT_CREATE_SUPPORTED &&
109 !goog.labs.structs.Map.objectPropertyIsEnumerable_.call(
110 this.map_, key))) {
111 delete this.map_[key];
112 var index = goog.array.indexOf(this.secondaryStoreKeys_, key);
113 if ((newKey = index < 0)) {
114 index = this.secondaryStoreKeys_.length;
115 }
116
117 this.secondaryStoreKeys_[index] = key;
118 this.secondaryStoreValues_[index] = value;
119 }
120
121 if (newKey) this.count_++;
122 };
123
124
125 /**
126 * Gets the value for the given key.
127 * @param {string} key The key whose value we want to retrieve.
128 * @param {*=} opt_default The default value to return if the key does
129 * not exist in the map, default to undefined.
130 * @return {*} The value corresponding to the given key, or opt_default
131 * if the key does not exist in this map.
132 */
133 goog.labs.structs.Map.prototype.get = function(key, opt_default) {
134 this.assertKeyIsString_(key);
135
136 if (this.hasKeyInPrimaryStore_(key)) {
137 return this.map_[key];
138 }
139
140 var index = goog.array.indexOf(this.secondaryStoreKeys_, key);
141 return index >= 0 ? this.secondaryStoreValues_[index] : opt_default;
142 };
143
144
145 /**
146 * Removes the map entry with the given key.
147 * @param {string} key The key to remove.
148 * @return {boolean} True if the entry is removed.
149 */
150 goog.labs.structs.Map.prototype.remove = function(key) {
151 this.assertKeyIsString_(key);
152
153 if (this.hasKeyInPrimaryStore_(key)) {
154 this.count_--;
155 delete this.map_[key];
156 return true;
157 } else {
158 var index = goog.array.indexOf(this.secondaryStoreKeys_, key);
159 if (index >= 0) {
160 this.count_--;
161 goog.array.removeAt(this.secondaryStoreKeys_, index);
162 goog.array.removeAt(this.secondaryStoreValues_, index);
163 return true;
164 }
165 }
166 return false;
167 };
168
169
170 /**
171 * Adds the content of the map to this map. If a new entry uses a key
172 * that already exists in this map, the existing key is replaced.
173 * @param {!goog.labs.structs.Map} map The map to add.
174 */
175 goog.labs.structs.Map.prototype.addAll = function(map) {
176 goog.array.forEach(
177 map.getKeys(), function(key) { this.set(key, map.get(key)); }, this);
178 };
179
180
181 /**
182 * @return {boolean} True if the map is empty.
183 */
184 goog.labs.structs.Map.prototype.isEmpty = function() {
185 return !this.count_;
186 };
187
188
189 /**
190 * @return {number} The number of the entries in this map.
191 */
192 goog.labs.structs.Map.prototype.getCount = function() {
193 return this.count_;
194 };
195
196
197 /**
198 * @param {string} key The key to check.
199 * @return {boolean} True if the map contains the given key.
200 */
201 goog.labs.structs.Map.prototype.containsKey = function(key) {
202 this.assertKeyIsString_(key);
203 return this.hasKeyInPrimaryStore_(key) ||
204 goog.array.contains(this.secondaryStoreKeys_, key);
205 };
206
207
208 /**
209 * Whether the map contains the given value. The comparison is done
210 * using !== comparator. Also returns true if the passed value is NaN
211 * and a NaN value exists in the map.
212 * @param {*} value Value to check.
213 * @return {boolean} True if the map contains the given value.
214 */
215 goog.labs.structs.Map.prototype.containsValue = function(value) {
216 var found = goog.object.some(this.map_, function(v, k) {
217 return this.hasKeyInPrimaryStore_(k) && goog.object.is(v, value);
218 }, this);
219 return found || goog.array.contains(this.secondaryStoreValues_, value);
220 };
221
222
223 /**
224 * @return {!Array<string>} An array of all the keys contained in this map.
225 */
226 goog.labs.structs.Map.prototype.getKeys = function() {
227 var keys;
228 if (goog.labs.structs.Map.BrowserFeature.OBJECT_KEYS_SUPPORTED) {
229 keys = goog.array.clone(Object.keys(this.map_));
230 } else {
231 keys = [];
232 for (var key in this.map_) {
233 if (goog.labs.structs.Map.objectHasOwnProperty_.call(this.map_, key)) {
234 keys.push(key);
235 }
236 }
237 }
238
239 goog.array.extend(keys, this.secondaryStoreKeys_);
240 return keys;
241 };
242
243
244 /**
245 * @return {!Array<*>} An array of all the values contained in this map.
246 * There may be duplicates.
247 */
248 goog.labs.structs.Map.prototype.getValues = function() {
249 var values = [];
250 var keys = this.getKeys();
251 for (var i = 0; i < keys.length; i++) {
252 values.push(this.get(keys[i]));
253 }
254 return values;
255 };
256
257
258 /**
259 * @return {!Array<Array<?>>} An array of entries. Each entry is of the
260 * form [key, value]. Do not rely on consistent ordering of entries.
261 */
262 goog.labs.structs.Map.prototype.getEntries = function() {
263 var entries = [];
264 var keys = this.getKeys();
265 for (var i = 0; i < keys.length; i++) {
266 var key = keys[i];
267 entries.push([key, this.get(key)]);
268 }
269 return entries;
270 };
271
272
273 /**
274 * Clears the map to the initial state.
275 */
276 goog.labs.structs.Map.prototype.clear = function() {
277 this.map_ = goog.labs.structs.Map.BrowserFeature.OBJECT_CREATE_SUPPORTED ?
278 Object.create(null) :
279 {};
280 this.secondaryStoreKeys_ = [];
281 this.secondaryStoreValues_ = [];
282 this.count_ = 0;
283 };
284
285
286 /**
287 * Clones this map.
288 * @return {!goog.labs.structs.Map} The clone of this map.
289 */
290 goog.labs.structs.Map.prototype.clone = function() {
291 var map = new goog.labs.structs.Map();
292 map.addAll(this);
293 return map;
294 };
295
296
297 /**
298 * @param {string} key The key to check.
299 * @return {boolean} True if the given key has been added successfully
300 * to the primary store.
301 * @private
302 */
303 goog.labs.structs.Map.prototype.hasKeyInPrimaryStore_ = function(key) {
304 // New browsers that support Object.create do not allow setting of
305 // __proto__. In other browsers, hasOwnProperty will return true for
306 // __proto__ for object created with literal {}, so we need to
307 // special case it.
308 if (key == '__proto__') {
309 return false;
310 }
311
312 if (goog.labs.structs.Map.BrowserFeature.OBJECT_CREATE_SUPPORTED) {
313 return key in this.map_;
314 }
315
316 return goog.labs.structs.Map.objectHasOwnProperty_.call(this.map_, key);
317 };
318
319
320 /**
321 * Asserts that the given key is a string.
322 * @param {string} key The key to check.
323 * @private
324 */
325 goog.labs.structs.Map.prototype.assertKeyIsString_ = function(key) {
326 goog.asserts.assert(goog.isString(key), 'key must be a string.');
327 };
328
329
330 /**
331 * Browser feature enum necessary for map.
332 * @enum {boolean}
333 */
334 goog.labs.structs.Map.BrowserFeature = {
335 // TODO(chrishenry): Replace with goog.userAgent detection.
336 /**
337 * Whether Object.create method is supported.
338 */
339 OBJECT_CREATE_SUPPORTED: !!Object.create,
340
341 /**
342 * Whether Object.keys method is supported.
343 */
344 OBJECT_KEYS_SUPPORTED: !!Object.keys
345 };