src/third_party/google_input_tools/third_party/closure_library/closure/goog/structs/map.js

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