// Copyright 2006 The Closure Library Authors. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS-IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
/**
* @fileoverview Datastructure: Hash Map.
*
* @author arv@google.com (Erik Arvidsson)
*
* This file contains an implementation of a Map structure. It implements a lot
* of the methods used in goog.structs so those functions work on hashes. This
* is best suited for complex key types. For simple keys such as numbers and
* strings consider using the lighter-weight utilities in goog.object.
*/
goog.provide('goog.structs.Map');
goog.require('goog.iter.Iterator');
goog.require('goog.iter.StopIteration');
goog.require('goog.object');
/**
* Class for Hash Map datastructure.
* @param {*=} opt_map Map or Object to initialize the map with.
* @param {...*} var_args If 2 or more arguments are present then they
* will be used as key-value pairs.
* @constructor
* @template K, V
* @deprecated This type is misleading: use ES6 Map instead.
*/
goog.structs.Map = function(opt_map, var_args) {
/**
* Underlying JS object used to implement the map.
* @private {!Object}
*/
this.map_ = {};
/**
* An array of keys. This is necessary for two reasons:
* 1. Iterating the keys using for (var key in this.map_) allocates an
* object for every key in IE which is really bad for IE6 GC perf.
* 2. Without a side data structure, we would need to escape all the keys
* as that would be the only way we could tell during iteration if the
* key was an internal key or a property of the object.
*
* This array can contain deleted keys so it's necessary to check the map
* as well to see if the key is still in the map (this doesn't require a
* memory allocation in IE).
* @private {!Array<string>}
*/
this.keys_ = [];
/**
* The number of key value pairs in the map.
* @private {number}
*/
this.count_ = 0;
/**
* Version used to detect changes while iterating.
* @private {number}
*/
this.version_ = 0;
var argLength = arguments.length;
if (argLength > 1) {
if (argLength % 2) {
throw Error('Uneven number of arguments');
}
for (var i = 0; i < argLength; i += 2) {
this.set(arguments[i], arguments[i + 1]);
}
} else if (opt_map) {
this.addAll(/** @type {Object} */ (opt_map));
}
};
/**
* @return {number} The number of key-value pairs in the map.
*/
goog.structs.Map.prototype.getCount = function() {
return this.count_;
};
/**
* Returns the values of the map.
* @return {!Array<V>} The values in the map.
*/
goog.structs.Map.prototype.getValues = function() {
this.cleanupKeysArray_();
var rv = [];
for (var i = 0; i < this.keys_.length; i++) {
var key = this.keys_[i];
rv.push(this.map_[key]);
}
return rv;
};
/**
* Returns the keys of the map.
* @return {!Array<string>} Array of string values.
*/
goog.structs.Map.prototype.getKeys = function() {
this.cleanupKeysArray_();
return /** @type {!Array<string>} */ (this.keys_.concat());
};
/**
* Whether the map contains the given key.
* @param {*} key The key to check for.
* @return {boolean} Whether the map contains the key.
*/
goog.structs.Map.prototype.containsKey = function(key) {
return goog.structs.Map.hasKey_(this.map_, key);
};
/**
* Whether the map contains the given value. This is O(n).
* @param {V} val The value to check for.
* @return {boolean} Whether the map contains the value.
*/
goog.structs.Map.prototype.containsValue = function(val) {
for (var i = 0; i < this.keys_.length; i++) {
var key = this.keys_[i];
if (goog.structs.Map.hasKey_(this.map_, key) && this.map_[key] == val) {
return true;
}
}
return false;
};
/**
* Whether this map is equal to the argument map.
* @param {goog.structs.Map} otherMap The map against which to test equality.
* @param {function(V, V): boolean=} opt_equalityFn Optional equality function
* to test equality of values. If not specified, this will test whether
* the values contained in each map are identical objects.
* @return {boolean} Whether the maps are equal.
*/
goog.structs.Map.prototype.equals = function(otherMap, opt_equalityFn) {
if (this === otherMap) {
return true;
}
if (this.count_ != otherMap.getCount()) {
return false;
}
var equalityFn = opt_equalityFn || goog.structs.Map.defaultEquals;
this.cleanupKeysArray_();
for (var key, i = 0; key = this.keys_[i]; i++) {
if (!equalityFn(this.get(key), otherMap.get(key))) {
return false;
}
}
return true;
};
/**
* Default equality test for values.
* @param {*} a The first value.
* @param {*} b The second value.
* @return {boolean} Whether a and b reference the same object.
*/
goog.structs.Map.defaultEquals = function(a, b) {
return a === b;
};
/**
* @return {boolean} Whether the map is empty.
*/
goog.structs.Map.prototype.isEmpty = function() {
return this.count_ == 0;
};
/**
* Removes all key-value pairs from the map.
*/
goog.structs.Map.prototype.clear = function() {
this.map_ = {};
this.keys_.length = 0;
this.count_ = 0;
this.version_ = 0;
};
/**
* Removes a key-value pair based on the key. This is O(logN) amortized due to
* updating the keys array whenever the count becomes half the size of the keys
* in the keys array.
* @param {*} key The key to remove.
* @return {boolean} Whether object was removed.
*/
goog.structs.Map.prototype.remove = function(key) {
if (goog.structs.Map.hasKey_(this.map_, key)) {
delete this.map_[key];
this.count_--;
this.version_++;
// clean up the keys array if the threshold is hit
if (this.keys_.length > 2 * this.count_) {
this.cleanupKeysArray_();
}
return true;
}
return false;
};
/**
* Cleans up the temp keys array by removing entries that are no longer in the
* map.
* @private
*/
goog.structs.Map.prototype.cleanupKeysArray_ = function() {
if (this.count_ != this.keys_.length) {
// First remove keys that are no longer in the map.
var srcIndex = 0;
var destIndex = 0;
while (srcIndex < this.keys_.length) {
var key = this.keys_[srcIndex];
if (goog.structs.Map.hasKey_(this.map_, key)) {
this.keys_[destIndex++] = key;
}
srcIndex++;
}
this.keys_.length = destIndex;
}
if (this.count_ != this.keys_.length) {
// If the count still isn't correct, that means we have duplicates. This can
// happen when the same key is added and removed multiple times. Now we have
// to allocate one extra Object to remove the duplicates. This could have
// been done in the first pass, but in the common case, we can avoid
// allocating an extra object by only doing this when necessary.
var seen = {};
var srcIndex = 0;
var destIndex = 0;
while (srcIndex < this.keys_.length) {
var key = this.keys_[srcIndex];
if (!(goog.structs.Map.hasKey_(seen, key))) {
this.keys_[destIndex++] = key;
seen[key] = 1;
}
srcIndex++;
}
this.keys_.length = destIndex;
}
};
/**
* Returns the value for the given key. If the key is not found and the default
* value is not given this will return {@code undefined}.
* @param {*} key The key to get the value for.
* @param {DEFAULT=} opt_val The value to return if no item is found for the
* given key, defaults to undefined.
* @return {V|DEFAULT} The value for the given key.
* @template DEFAULT
*/
goog.structs.Map.prototype.get = function(key, opt_val) {
if (goog.structs.Map.hasKey_(this.map_, key)) {
return this.map_[key];
}
return opt_val;
};
/**
* Adds a key-value pair to the map.
* @param {*} key The key.
* @param {V} value The value to add.
* @return {*} Some subclasses return a value.
*/
goog.structs.Map.prototype.set = function(key, value) {
if (!(goog.structs.Map.hasKey_(this.map_, key))) {
this.count_++;
// TODO(johnlenz): This class lies, it claims to return an array of string
// keys, but instead returns the original object used.
this.keys_.push(/** @type {?} */ (key));
// Only change the version if we add a new key.
this.version_++;
}
this.map_[key] = value;
};
/**
* Adds multiple key-value pairs from another goog.structs.Map or Object.
* @param {Object} map Object containing the data to add.
*/
goog.structs.Map.prototype.addAll = function(map) {
var keys, values;
if (map instanceof goog.structs.Map) {
keys = map.getKeys();
values = map.getValues();
} else {
keys = goog.object.getKeys(map);
values = goog.object.getValues(map);
}
// we could use goog.array.forEach here but I don't want to introduce that
// dependency just for this.
for (var i = 0; i < keys.length; i++) {
this.set(keys[i], values[i]);
}
};
/**
* Calls the given function on each entry in the map.
* @param {function(this:T, V, K, goog.structs.Map<K,V>)} f
* @param {T=} opt_obj The value of "this" inside f.
* @template T
*/
goog.structs.Map.prototype.forEach = function(f, opt_obj) {
var keys = this.getKeys();
for (var i = 0; i < keys.length; i++) {
var key = keys[i];
var value = this.get(key);
f.call(opt_obj, value, key, this);
}
};
/**
* Clones a map and returns a new map.
* @return {!goog.structs.Map} A new map with the same key-value pairs.
*/
goog.structs.Map.prototype.clone = function() {
return new goog.structs.Map(this);
};
/**
* Returns a new map in which all the keys and values are interchanged
* (keys become values and values become keys). If multiple keys map to the
* same value, the chosen transposed value is implementation-dependent.
*
* It acts very similarly to {goog.object.transpose(Object)}.
*
* @return {!goog.structs.Map} The transposed map.
*/
goog.structs.Map.prototype.transpose = function() {
var transposed = new goog.structs.Map();
for (var i = 0; i < this.keys_.length; i++) {
var key = this.keys_[i];
var value = this.map_[key];
transposed.set(value, key);
}
return transposed;
};
/**
* @return {!Object} Object representation of the map.
*/
goog.structs.Map.prototype.toObject = function() {
this.cleanupKeysArray_();
var obj = {};
for (var i = 0; i < this.keys_.length; i++) {
var key = this.keys_[i];
obj[key] = this.map_[key];
}
return obj;
};
/**
* Returns an iterator that iterates over the keys in the map. Removal of keys
* while iterating might have undesired side effects.
* @return {!goog.iter.Iterator} An iterator over the keys in the map.
*/
goog.structs.Map.prototype.getKeyIterator = function() {
return this.__iterator__(true);
};
/**
* Returns an iterator that iterates over the values in the map. Removal of
* keys while iterating might have undesired side effects.
* @return {!goog.iter.Iterator} An iterator over the values in the map.
*/
goog.structs.Map.prototype.getValueIterator = function() {
return this.__iterator__(false);
};
/**
* Returns an iterator that iterates over the values or the keys in the map.
* This throws an exception if the map was mutated since the iterator was
* created.
* @param {boolean=} opt_keys True to iterate over the keys. False to iterate
* over the values. The default value is false.
* @return {!goog.iter.Iterator} An iterator over the values or keys in the map.
*/
goog.structs.Map.prototype.__iterator__ = function(opt_keys) {
// Clean up keys to minimize the risk of iterating over dead keys.
this.cleanupKeysArray_();
var i = 0;
var version = this.version_;
var selfObj = this;
var newIter = new goog.iter.Iterator;
newIter.next = function() {
if (version != selfObj.version_) {
throw Error('The map has changed since the iterator was created');
}
if (i >= selfObj.keys_.length) {
throw goog.iter.StopIteration;
}
var key = selfObj.keys_[i++];
return opt_keys ? key : selfObj.map_[key];
};
return newIter;
};
/**
* Safe way to test for hasOwnProperty. It even allows testing for
* 'hasOwnProperty'.
* @param {Object} obj The object to test for presence of the given key.
* @param {*} key The key to check for.
* @return {boolean} Whether the object has the key.
* @private
*/
goog.structs.Map.hasKey_ = function(obj, key) {
return Object.prototype.hasOwnProperty.call(obj, key);
};