/**
* @license
* Copyright The Closure Library Authors.
* SPDX-License-Identifier: Apache-2.0
*/
/**
* @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:
*
* <pre>
* 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
* </pre>
*
* @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.
* @param {function(string, VALUE)=} opt_evictionCallback Called with the
* removed stringified key as the first argument and value as the second
* argument after the key was evicted from the LRU because the max count
* was reached.
* @constructor
* @template KEY, VALUE
*/
goog.structs.LinkedMap = function(
opt_maxCount, opt_cache, opt_evictionCallback) {
'use strict';
/**
* The maximum number of entries to allow, or null if there is no limit.
* @private {?number}
*/
this.maxCount_ = opt_maxCount || null;
/** @private @const {boolean} */
this.cache_ = !!opt_cache;
/** @private {function(string, VALUE)|undefined} */
this.evictionCallback_ = opt_evictionCallback;
/**
* @private @const {!goog.structs.Map<string,
* goog.structs.LinkedMap.Node_<string, VALUE>>}
*/
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_<string, VALUE>} The node or null if not
* found.
* @private
*/
goog.structs.LinkedMap.prototype.findAndMoveToTop_ = function(key) {
'use strict';
var 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 {VALUE=} opt_val A default value that will be returned if the key is
* not found, defaults to undefined.
* @return {VALUE} The retrieved value.
*/
goog.structs.LinkedMap.prototype.get = function(key, opt_val) {
'use strict';
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 {VALUE=} opt_val A default value that will be returned if the key is
* not found.
* @return {VALUE} The retrieved value.
*/
goog.structs.LinkedMap.prototype.peekValue = function(key, opt_val) {
'use strict';
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 Key with which the specified value is to be associated.
* @param {VALUE} value Value to be associated with the specified key.
*/
goog.structs.LinkedMap.prototype.set = function(key, value) {
'use strict';
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 {VALUE} The value of the first node or undefined if the map is empty.
*/
goog.structs.LinkedMap.prototype.peek = function() {
'use strict';
return this.head_.next.value;
};
/**
* Returns the value of the last node without making any modifications.
* @return {VALUE} The value of the last node or undefined if the map is empty.
*/
goog.structs.LinkedMap.prototype.peekLast = function() {
'use strict';
return this.head_.prev.value;
};
/**
* Removes the first node from the list and returns its value.
* @return {VALUE} The value of the popped node, or undefined if the map was
* empty.
*/
goog.structs.LinkedMap.prototype.shift = function() {
'use strict';
return this.popNode_(this.head_.next);
};
/**
* Removes the last node from the list and returns its value.
* @return {VALUE} The value of the popped node, or undefined if the map was
* empty.
*/
goog.structs.LinkedMap.prototype.pop = function() {
'use strict';
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) {
'use strict';
var node = this.map_.get(key);
if (node) {
this.removeNode(node);
return true;
}
return false;
};
/**
* Removes a node from the `LinkedMap`. It can be overridden to do
* further cleanup such as disposing of the node value.
* @param {!goog.structs.LinkedMap.Node_<string, VALUE>} node The node to
* remove.
* @protected
*/
goog.structs.LinkedMap.prototype.removeNode = function(node) {
'use strict';
node.remove();
this.map_.remove(node.key);
};
/**
* @return {number} The number of items currently in the LinkedMap. Sub classes
* may override this to change how items are counted (e.g. to introduce
* per item weight). Truncation will always proceed as long as the count
* returned from this method is higher than the max count for this map.
*/
goog.structs.LinkedMap.prototype.getCount = function() {
'use strict';
return this.map_.getCount();
};
/**
* @return {boolean} True if the cache is empty, false if it contains any items.
*/
goog.structs.LinkedMap.prototype.isEmpty = function() {
'use strict';
return this.map_.isEmpty();
};
/**
* Sets a callback that fires when an entry is evicted because max entry
* count is reached. The callback is called with the removed stringified key
* as the first argument and value as the second argument after the key was
* evicted from the LRU because the max count was reached.
* @param {function(string, VALUE)} evictionCallback
*/
goog.structs.LinkedMap.prototype.setEvictionCallback = function(
evictionCallback) {
'use strict';
this.evictionCallback_ = evictionCallback;
};
/**
* 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) {
'use strict';
this.maxCount_ = maxCount || null;
if (this.maxCount_ != null) {
this.truncate_(this.maxCount_);
}
};
/**
* @return {!Array<string>} The list of the keys in the appropriate order for
* this LinkedMap.
*/
goog.structs.LinkedMap.prototype.getKeys = function() {
'use strict';
return this.map(function(val, key) {
'use strict';
return key;
});
};
/**
* @return {!Array<VALUE>} The list of the values in the appropriate order for
* this LinkedMap.
*/
goog.structs.LinkedMap.prototype.getValues = function() {
'use strict';
return this.map(function(val, key) {
'use strict';
return val;
});
};
/**
* Tests whether a provided value is currently in the LinkedMap. This does not
* affect item ordering in cache-style LinkedMaps.
* @param {VALUE} value The value to check for.
* @return {boolean} Whether the value is in the LinkedMap.
*/
goog.structs.LinkedMap.prototype.contains = function(value) {
'use strict';
return this.some(function(el) {
'use strict';
return el == value;
});
};
/**
* Tests whether a provided key is currently in the LinkedMap. This does not
* affect item ordering in cache-style LinkedMaps.
* @param {string} key The key to check for.
* @return {boolean} Whether the key is in the LinkedMap.
*/
goog.structs.LinkedMap.prototype.containsKey = function(key) {
'use strict';
return this.map_.containsKey(key);
};
/**
* Removes all entries in this object.
*/
goog.structs.LinkedMap.prototype.clear = function() {
'use strict';
this.truncate_(0);
};
/**
* Calls a function on each item in the LinkedMap.
*
* @see goog.structs.forEach
* @param {function(this:T, VALUE, KEY, goog.structs.LinkedMap<KEY, VALUE>)} f
* @param {T=} opt_obj The value of "this" inside f.
* @template T
*/
goog.structs.LinkedMap.prototype.forEach = function(f, opt_obj) {
'use strict';
for (var n = this.head_.next; n != this.head_; n = n.next) {
f.call(opt_obj, n.value, n.key, this);
}
};
/**
* Calls a function on each item in the LinkedMap and returns the results of
* those calls in an array.
*
* @see goog.structs.map
* @param {function(this:T, VALUE, KEY,
* goog.structs.LinkedMap<KEY, VALUE>): RESULT} f
* The function to call for each item. The function takes
* three arguments: the value, the key, and the LinkedMap.
* @param {T=} opt_obj The object context to use as "this" for the
* function.
* @return {!Array<RESULT>} The results of the function calls for each item in
* the LinkedMap.
* @template T,RESULT
*/
goog.structs.LinkedMap.prototype.map = function(f, opt_obj) {
'use strict';
var rv = [];
for (var n = this.head_.next; n != this.head_; n = n.next) {
rv.push(f.call(opt_obj, n.value, n.key, this));
}
return rv;
};
/**
* Calls a function on each item in the LinkedMap and returns true if any of
* those function calls returns a true-like value.
*
* @see goog.structs.some
* @param {function(this:T, VALUE, KEY,
* goog.structs.LinkedMap<KEY, VALUE>):boolean} f
* The function to call for each item. The function takes
* three arguments: the value, the key, and the LinkedMap, and returns a
* boolean.
* @param {T=} opt_obj The object context to use as "this" for the
* function.
* @return {boolean} Whether f evaluates to true for at least one item in the
* LinkedMap.
* @template T
*/
goog.structs.LinkedMap.prototype.some = function(f, opt_obj) {
'use strict';
for (var n = this.head_.next; n != this.head_; n = n.next) {
if (f.call(opt_obj, n.value, n.key, this)) {
return true;
}
}
return false;
};
/**
* Calls a function on each item in the LinkedMap and returns true only if every
* function call returns a true-like value.
*
* @see goog.structs.some
* @param {function(this:T, VALUE, KEY,
* goog.structs.LinkedMap<KEY, VALUE>):boolean} f
* The function to call for each item. The function takes
* three arguments: the value, the key, and the Cache, and returns a
* boolean.
* @param {T=} opt_obj The object context to use as "this" for the
* function.
* @return {boolean} Whether f evaluates to true for every item in the Cache.
* @template T
*/
goog.structs.LinkedMap.prototype.every = function(f, opt_obj) {
'use strict';
for (var n = this.head_.next; n != this.head_; n = n.next) {
if (!f.call(opt_obj, n.value, n.key, this)) {
return false;
}
}
return true;
};
/**
* Appends a node to the list. LinkedMap in cache mode adds new nodes to
* the head of the list, otherwise they are appended to the tail. If there is a
* maximum size, the list will be truncated if necessary.
*
* @param {goog.structs.LinkedMap.Node_<string, VALUE>} node The item to insert.
* @private
*/
goog.structs.LinkedMap.prototype.insert_ = function(node) {
'use strict';
if (this.cache_) {
node.next = this.head_.next;
node.prev = this.head_;
this.head_.next = node;
node.next.prev = node;
} else {
node.prev = this.head_.prev;
node.next = this.head_;
this.head_.prev = node;
node.prev.next = node;
}
if (this.maxCount_ != null) {
this.truncate_(this.maxCount_);
}
};
/**
* Removes elements from the LinkedMap if the given count has been exceeded.
* In cache mode removes nodes from the tail of the list. Otherwise removes
* nodes from the head.
* @param {number} count Number of elements to keep.
* @private
*/
goog.structs.LinkedMap.prototype.truncate_ = function(count) {
'use strict';
while (this.getCount() > count) {
var toRemove = this.cache_ ? this.head_.prev : this.head_.next;
this.removeNode(toRemove);
if (this.evictionCallback_) {
this.evictionCallback_(toRemove.key, toRemove.value);
}
}
};
/**
* Removes the node from the LinkedMap if it is not the head, and returns
* the node's value.
* @param {!goog.structs.LinkedMap.Node_<string, VALUE>} node The item to
* remove.
* @return {VALUE} The value of the popped node.
* @private
*/
goog.structs.LinkedMap.prototype.popNode_ = function(node) {
'use strict';
if (this.head_ != node) {
this.removeNode(node);
}
return node.value;
};
/**
* Internal class for a doubly-linked list node containing a key/value pair.
* @param {KEY} key The key.
* @param {VALUE} value The value.
* @constructor
* @template KEY, VALUE
* @private
*/
goog.structs.LinkedMap.Node_ = function(key, value) {
'use strict';
/** @type {KEY} */
this.key = key;
/** @type {VALUE} */
this.value = value;
};
/**
* The next node in the list.
* @type {!goog.structs.LinkedMap.Node_<KEY, VALUE>}
*/
goog.structs.LinkedMap.Node_.prototype.next;
/**
* The previous node in the list.
* @type {!goog.structs.LinkedMap.Node_<KEY, VALUE>}
*/
goog.structs.LinkedMap.Node_.prototype.prev;
/**
* Causes this node to remove itself from the list.
*/
goog.structs.LinkedMap.Node_.prototype.remove = function() {
'use strict';
this.prev.next = this.next;
this.next.prev = this.prev;
delete this.prev;
delete this.next;
};
Codebase Browser
chromium