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
};
346

347