// Copyright 2007 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 A LinkedMap data structure that is accessed using key/value * pairs like an ordinary Map, but which guarantees a consistent iteration * order over its entries. The iteration order is either insertion order (the * default) or ordered from most recent to least recent use. By setting a fixed * size, the LRU version of the LinkedMap makes an effective object cache. This * data structure is similar to Java's LinkedHashMap. * */ goog.provide('goog.structs.LinkedMap'); goog.require('goog.structs.Map'); /** * Class for a LinkedMap datastructure, which combines O(1) map access for * key/value pairs with a linked list for a consistent iteration order. Sample * usage: * *
* var m = new LinkedMap(); * m.set('param1', 'A'); * m.set('param2', 'B'); * m.set('param3', 'C'); * alert(m.getKeys()); // param1, param2, param3 * * var c = new LinkedMap(5, true); * for (var i = 0; i < 10; i++) { * c.set('entry' + i, false); * } * alert(c.getKeys()); // entry9, entry8, entry7, entry6, entry5 * * c.set('entry5', true); * c.set('entry1', false); * alert(c.getKeys()); // entry1, entry5, entry9, entry8, entry7 ** * @param {number=} opt_maxCount The maximum number of objects to store in the * LinkedMap. If unspecified or 0, there is no maximum. * @param {boolean=} opt_cache When set, the LinkedMap stores items in order * from most recently used to least recently used, instead of insertion * order. * @constructor */ goog.structs.LinkedMap = function(opt_maxCount, opt_cache) { /** * The maximum number of entries to allow, or null if there is no limit. * @type {?number} * @private */ this.maxCount_ = opt_maxCount || null; /** * @type {boolean} * @private */ this.cache_ = !!opt_cache; this.map_ = new goog.structs.Map(); this.head_ = new goog.structs.LinkedMap.Node_('', undefined); this.head_.next = this.head_.prev = this.head_; }; /** * Finds a node and updates it to be the most recently used. * @param {string} key The key of the node. * @return {goog.structs.LinkedMap.Node_} The node or null if not found. * @private */ goog.structs.LinkedMap.prototype.findAndMoveToTop_ = function(key) { var node = /** @type {goog.structs.LinkedMap.Node_} */ (this.map_.get(key)); if (node) { if (this.cache_) { node.remove(); this.insert_(node); } } return node; }; /** * Retrieves the value for a given key. If this is a caching LinkedMap, the * entry will become the most recently used. * @param {string} key The key to retrieve the value for. * @param {*=} opt_val A default value that will be returned if the key is * not found, defaults to undefined. * @return {*} The retrieved value. */ goog.structs.LinkedMap.prototype.get = function(key, opt_val) { var node = this.findAndMoveToTop_(key); return node ? node.value : opt_val; }; /** * Retrieves the value for a given key without updating the entry to be the * most recently used. * @param {string} key The key to retrieve the value for. * @param {*=} opt_val A default value that will be returned if the key is * not found. * @return {*} The retrieved value. */ goog.structs.LinkedMap.prototype.peekValue = function(key, opt_val) { var node = this.map_.get(key); return node ? node.value : opt_val; }; /** * Sets a value for a given key. If this is a caching LinkedMap, this entry * will become the most recently used. * @param {string} key The key to retrieve the value for. * @param {*} value A default value that will be returned if the key is * not found. */ goog.structs.LinkedMap.prototype.set = function(key, value) { var node = this.findAndMoveToTop_(key); if (node) { node.value = value; } else { node = new goog.structs.LinkedMap.Node_(key, value); this.map_.set(key, node); this.insert_(node); } }; /** * Returns the value of the first node without making any modifications. * @return {*} The value of the first node or undefined if the map is empty. */ goog.structs.LinkedMap.prototype.peek = function() { return this.head_.next.value; }; /** * Returns the value of the last node without making any modifications. * @return {*} The value of the last node or undefined if the map is empty. */ goog.structs.LinkedMap.prototype.peekLast = function() { return this.head_.prev.value; }; /** * Removes the first node from the list and returns its value. * @return {*} The value of the popped node, or undefined if the map was empty. */ goog.structs.LinkedMap.prototype.shift = function() { return this.popNode_(this.head_.next); }; /** * Removes the last node from the list and returns its value. * @return {*} The value of the popped node, or undefined if the map was empty. */ goog.structs.LinkedMap.prototype.pop = function() { return this.popNode_(this.head_.prev); }; /** * Removes a value from the LinkedMap based on its key. * @param {string} key The key to remove. * @return {boolean} True if the entry was removed, false if the key was not * found. */ goog.structs.LinkedMap.prototype.remove = function(key) { var node = /** @type {goog.structs.LinkedMap.Node_} */ (this.map_.get(key)); if (node) { this.removeNode(node); return true; } return false; }; /** * Removes a node from the {@code LinkedMap}. It can be overridden to do * further cleanup such as disposing of the node value. * @param {!goog.structs.LinkedMap.Node_} node The node to remove. * @protected */ goog.structs.LinkedMap.prototype.removeNode = function(node) { node.remove(); this.map_.remove(node.key); }; /** * @return {number} The number of items currently in the LinkedMap. */ goog.structs.LinkedMap.prototype.getCount = function() { return this.map_.getCount(); }; /** * @return {boolean} True if the cache is empty, false if it contains any items. */ goog.structs.LinkedMap.prototype.isEmpty = function() { return this.map_.isEmpty(); }; /** * Sets the maximum number of entries allowed in this object, truncating any * excess objects if necessary. * @param {number} maxCount The new maximum number of entries to allow. */ goog.structs.LinkedMap.prototype.setMaxCount = function(maxCount) { this.maxCount_ = maxCount || null; if (this.maxCount_ != null) { this.truncate_(this.maxCount_); } }; /** * @return {Array.