Debian Codegraph @

closure-library/closure/goog/structs/linkedmap.js

raw
1 // Copyright 2007 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 LinkedMap data structure that is accessed using key/value
17 * pairs like an ordinary Map, but which guarantees a consistent iteration
18 * order over its entries. The iteration order is either insertion order (the
19 * default) or ordered from most recent to least recent use. By setting a fixed
20 * size, the LRU version of the LinkedMap makes an effective object cache. This
21 * data structure is similar to Java's LinkedHashMap.
22 *
23 * @author [email protected] (Shawn Brenneman)
24 */
25
26
27 goog.provide('goog.structs.LinkedMap');
28
29 goog.require('goog.structs.Map');
30
31
32
33 /**
34 * Class for a LinkedMap datastructure, which combines O(1) map access for
35 * key/value pairs with a linked list for a consistent iteration order. Sample
36 * usage:
37 *
38 * <pre>
39 * var m = new LinkedMap();
40 * m.set('param1', 'A');
41 * m.set('param2', 'B');
42 * m.set('param3', 'C');
43 * alert(m.getKeys()); // param1, param2, param3
44 *
45 * var c = new LinkedMap(5, true);
46 * for (var i = 0; i < 10; i++) {
47 * c.set('entry' + i, false);
48 * }
49 * alert(c.getKeys()); // entry9, entry8, entry7, entry6, entry5
50 *
51 * c.set('entry5', true);
52 * c.set('entry1', false);
53 * alert(c.getKeys()); // entry1, entry5, entry9, entry8, entry7
54 * </pre>
55 *
56 * @param {number=} opt_maxCount The maximum number of objects to store in the
57 * LinkedMap. If unspecified or 0, there is no maximum.
58 * @param {boolean=} opt_cache When set, the LinkedMap stores items in order
59 * from most recently used to least recently used, instead of insertion
60 * order.
61 * @param {function(string, VALUE)=} opt_evictionCallback Called with the
62 * removed stringified key as the first argument and value as the second
63 * argument after the key was evicted from the LRU because the max count
64 * was reached.
65 * @constructor
66 * @template KEY, VALUE
67 */
68 goog.structs.LinkedMap = function(
69 opt_maxCount, opt_cache, opt_evictionCallback) {
70 /**
71 * The maximum number of entries to allow, or null if there is no limit.
72 * @private {?number}
73 */
74 this.maxCount_ = opt_maxCount || null;
75
76 /** @private @const {boolean} */
77 this.cache_ = !!opt_cache;
78
79 /** @private {function(string, VALUE)|undefined} */
80 this.evictionCallback_ = opt_evictionCallback;
81
82 /**
83 * @private @const {!goog.structs.Map<string,
84 * goog.structs.LinkedMap.Node_<string, VALUE>>}
85 */
86 this.map_ = new goog.structs.Map();
87
88 this.head_ = new goog.structs.LinkedMap.Node_('', undefined);
89 this.head_.next = this.head_.prev = this.head_;
90 };
91
92
93 /**
94 * Finds a node and updates it to be the most recently used.
95 * @param {string} key The key of the node.
96 * @return {goog.structs.LinkedMap.Node_<string, VALUE>} The node or null if not
97 * found.
98 * @private
99 */
100 goog.structs.LinkedMap.prototype.findAndMoveToTop_ = function(key) {
101 var node = this.map_.get(key);
102 if (node) {
103 if (this.cache_) {
104 node.remove();
105 this.insert_(node);
106 }
107 }
108 return node;
109 };
110
111
112 /**
113 * Retrieves the value for a given key. If this is a caching LinkedMap, the
114 * entry will become the most recently used.
115 * @param {string} key The key to retrieve the value for.
116 * @param {VALUE=} opt_val A default value that will be returned if the key is
117 * not found, defaults to undefined.
118 * @return {VALUE} The retrieved value.
119 */
120 goog.structs.LinkedMap.prototype.get = function(key, opt_val) {
121 var node = this.findAndMoveToTop_(key);
122 return node ? node.value : opt_val;
123 };
124
125
126 /**
127 * Retrieves the value for a given key without updating the entry to be the
128 * most recently used.
129 * @param {string} key The key to retrieve the value for.
130 * @param {VALUE=} opt_val A default value that will be returned if the key is
131 * not found.
132 * @return {VALUE} The retrieved value.
133 */
134 goog.structs.LinkedMap.prototype.peekValue = function(key, opt_val) {
135 var node = this.map_.get(key);
136 return node ? node.value : opt_val;
137 };
138
139
140 /**
141 * Sets a value for a given key. If this is a caching LinkedMap, this entry
142 * will become the most recently used.
143 * @param {string} key Key with which the specified value is to be associated.
144 * @param {VALUE} value Value to be associated with the specified key.
145 */
146 goog.structs.LinkedMap.prototype.set = function(key, value) {
147 var node = this.findAndMoveToTop_(key);
148 if (node) {
149 node.value = value;
150 } else {
151 node = new goog.structs.LinkedMap.Node_(key, value);
152 this.map_.set(key, node);
153 this.insert_(node);
154 }
155 };
156
157
158 /**
159 * Returns the value of the first node without making any modifications.
160 * @return {VALUE} The value of the first node or undefined if the map is empty.
161 */
162 goog.structs.LinkedMap.prototype.peek = function() {
163 return this.head_.next.value;
164 };
165
166
167 /**
168 * Returns the value of the last node without making any modifications.
169 * @return {VALUE} The value of the last node or undefined if the map is empty.
170 */
171 goog.structs.LinkedMap.prototype.peekLast = function() {
172 return this.head_.prev.value;
173 };
174
175
176 /**
177 * Removes the first node from the list and returns its value.
178 * @return {VALUE} The value of the popped node, or undefined if the map was
179 * empty.
180 */
181 goog.structs.LinkedMap.prototype.shift = function() {
182 return this.popNode_(this.head_.next);
183 };
184
185
186 /**
187 * Removes the last node from the list and returns its value.
188 * @return {VALUE} The value of the popped node, or undefined if the map was
189 * empty.
190 */
191 goog.structs.LinkedMap.prototype.pop = function() {
192 return this.popNode_(this.head_.prev);
193 };
194
195
196 /**
197 * Removes a value from the LinkedMap based on its key.
198 * @param {string} key The key to remove.
199 * @return {boolean} True if the entry was removed, false if the key was not
200 * found.
201 */
202 goog.structs.LinkedMap.prototype.remove = function(key) {
203 var node = this.map_.get(key);
204 if (node) {
205 this.removeNode(node);
206 return true;
207 }
208 return false;
209 };
210
211
212 /**
213 * Removes a node from the {@code LinkedMap}. It can be overridden to do
214 * further cleanup such as disposing of the node value.
215 * @param {!goog.structs.LinkedMap.Node_<string, VALUE>} node The node to
216 * remove.
217 * @protected
218 */
219 goog.structs.LinkedMap.prototype.removeNode = function(node) {
220 node.remove();
221 this.map_.remove(node.key);
222 };
223
224
225 /**
226 * @return {number} The number of items currently in the LinkedMap. Sub classes
227 * may override this to change how items are counted (e.g. to introduce
228 * per item weight). Truncation will always proceed as long as the count
229 * returned from this method is higher than the max count for this map.
230 */
231 goog.structs.LinkedMap.prototype.getCount = function() {
232 return this.map_.getCount();
233 };
234
235
236 /**
237 * @return {boolean} True if the cache is empty, false if it contains any items.
238 */
239 goog.structs.LinkedMap.prototype.isEmpty = function() {
240 return this.map_.isEmpty();
241 };
242
243
244 /**
245 * Sets a callback that fires when an entry is evicted because max entry
246 * count is reached. The callback is called with the removed stringified key
247 * as the first argument and value as the second argument after the key was
248 * evicted from the LRU because the max count was reached.
249 * @param {function(string, VALUE)} evictionCallback
250 */
251 goog.structs.LinkedMap.prototype.setEvictionCallback = function(
252 evictionCallback) {
253 this.evictionCallback_ = evictionCallback;
254 };
255
256
257 /**
258 * Sets the maximum number of entries allowed in this object, truncating any
259 * excess objects if necessary.
260 * @param {number} maxCount The new maximum number of entries to allow.
261 */
262 goog.structs.LinkedMap.prototype.setMaxCount = function(maxCount) {
263 this.maxCount_ = maxCount || null;
264 if (this.maxCount_ != null) {
265 this.truncate_(this.maxCount_);
266 }
267 };
268
269
270 /**
271 * @return {!Array<string>} The list of the keys in the appropriate order for
272 * this LinkedMap.
273 */
274 goog.structs.LinkedMap.prototype.getKeys = function() {
275 return this.map(function(val, key) { return key; });
276 };
277
278
279 /**
280 * @return {!Array<VALUE>} The list of the values in the appropriate order for
281 * this LinkedMap.
282 */
283 goog.structs.LinkedMap.prototype.getValues = function() {
284 return this.map(function(val, key) { return val; });
285 };
286
287
288 /**
289 * Tests whether a provided value is currently in the LinkedMap. This does not
290 * affect item ordering in cache-style LinkedMaps.
291 * @param {VALUE} value The value to check for.
292 * @return {boolean} Whether the value is in the LinkedMap.
293 */
294 goog.structs.LinkedMap.prototype.contains = function(value) {
295 return this.some(function(el) { return el == value; });
296 };
297
298
299 /**
300 * Tests whether a provided key is currently in the LinkedMap. This does not
301 * affect item ordering in cache-style LinkedMaps.
302 * @param {string} key The key to check for.
303 * @return {boolean} Whether the key is in the LinkedMap.
304 */
305 goog.structs.LinkedMap.prototype.containsKey = function(key) {
306 return this.map_.containsKey(key);
307 };
308
309
310 /**
311 * Removes all entries in this object.
312 */
313 goog.structs.LinkedMap.prototype.clear = function() {
314 this.truncate_(0);
315 };
316
317
318 /**
319 * Calls a function on each item in the LinkedMap.
320 *
321 * @see goog.structs.forEach
322 * @param {function(this:T, VALUE, KEY, goog.structs.LinkedMap<KEY, VALUE>)} f
323 * @param {T=} opt_obj The value of "this" inside f.
324 * @template T
325 */
326 goog.structs.LinkedMap.prototype.forEach = function(f, opt_obj) {
327 for (var n = this.head_.next; n != this.head_; n = n.next) {
328 f.call(opt_obj, n.value, n.key, this);
329 }
330 };
331
332
333 /**
334 * Calls a function on each item in the LinkedMap and returns the results of
335 * those calls in an array.
336 *
337 * @see goog.structs.map
338 * @param {function(this:T, VALUE, KEY,
339 * goog.structs.LinkedMap<KEY, VALUE>): RESULT} f
340 * The function to call for each item. The function takes
341 * three arguments: the value, the key, and the LinkedMap.
342 * @param {T=} opt_obj The object context to use as "this" for the
343 * function.
344 * @return {!Array<RESULT>} The results of the function calls for each item in
345 * the LinkedMap.
346 * @template T,RESULT
347 */
348 goog.structs.LinkedMap.prototype.map = function(f, opt_obj) {
349 var rv = [];
350 for (var n = this.head_.next; n != this.head_; n = n.next) {
351 rv.push(f.call(opt_obj, n.value, n.key, this));
352 }
353 return rv;
354 };
355
356
357 /**
358 * Calls a function on each item in the LinkedMap and returns true if any of
359 * those function calls returns a true-like value.
360 *
361 * @see goog.structs.some
362 * @param {function(this:T, VALUE, KEY,
363 * goog.structs.LinkedMap<KEY, VALUE>):boolean} f
364 * The function to call for each item. The function takes
365 * three arguments: the value, the key, and the LinkedMap, and returns a
366 * boolean.
367 * @param {T=} opt_obj The object context to use as "this" for the
368 * function.
369 * @return {boolean} Whether f evaluates to true for at least one item in the
370 * LinkedMap.
371 * @template T
372 */
373 goog.structs.LinkedMap.prototype.some = function(f, opt_obj) {
374 for (var n = this.head_.next; n != this.head_; n = n.next) {
375 if (f.call(opt_obj, n.value, n.key, this)) {
376 return true;
377 }
378 }
379 return false;
380 };
381
382
383 /**
384 * Calls a function on each item in the LinkedMap and returns true only if every
385 * function call returns a true-like value.
386 *
387 * @see goog.structs.some
388 * @param {function(this:T, VALUE, KEY,
389 * goog.structs.LinkedMap<KEY, VALUE>):boolean} f
390 * The function to call for each item. The function takes
391 * three arguments: the value, the key, and the Cache, and returns a
392 * boolean.
393 * @param {T=} opt_obj The object context to use as "this" for the
394 * function.
395 * @return {boolean} Whether f evaluates to true for every item in the Cache.
396 * @template T
397 */
398 goog.structs.LinkedMap.prototype.every = function(f, opt_obj) {
399 for (var n = this.head_.next; n != this.head_; n = n.next) {
400 if (!f.call(opt_obj, n.value, n.key, this)) {
401 return false;
402 }
403 }
404 return true;
405 };
406
407
408 /**
409 * Appends a node to the list. LinkedMap in cache mode adds new nodes to
410 * the head of the list, otherwise they are appended to the tail. If there is a
411 * maximum size, the list will be truncated if necessary.
412 *
413 * @param {goog.structs.LinkedMap.Node_<string, VALUE>} node The item to insert.
414 * @private
415 */
416 goog.structs.LinkedMap.prototype.insert_ = function(node) {
417 if (this.cache_) {
418 node.next = this.head_.next;
419 node.prev = this.head_;
420
421 this.head_.next = node;
422 node.next.prev = node;
423 } else {
424 node.prev = this.head_.prev;
425 node.next = this.head_;
426
427 this.head_.prev = node;
428 node.prev.next = node;
429 }
430
431 if (this.maxCount_ != null) {
432 this.truncate_(this.maxCount_);
433 }
434 };
435
436
437 /**
438 * Removes elements from the LinkedMap if the given count has been exceeded.
439 * In cache mode removes nodes from the tail of the list. Otherwise removes
440 * nodes from the head.
441 * @param {number} count Number of elements to keep.
442 * @private
443 */
444 goog.structs.LinkedMap.prototype.truncate_ = function(count) {
445 while (this.getCount() > count) {
446 var toRemove = this.cache_ ? this.head_.prev : this.head_.next;
447 this.removeNode(toRemove);
448 if (this.evictionCallback_) {
449 this.evictionCallback_(toRemove.key, toRemove.value);
450 }
451 }
452 };
453
454
455 /**
456 * Removes the node from the LinkedMap if it is not the head, and returns
457 * the node's value.
458 * @param {!goog.structs.LinkedMap.Node_<string, VALUE>} node The item to
459 * remove.
460 * @return {VALUE} The value of the popped node.
461 * @private
462 */
463 goog.structs.LinkedMap.prototype.popNode_ = function(node) {
464 if (this.head_ != node) {
465 this.removeNode(node);
466 }
467 return node.value;
468 };
469
470
471
472 /**
473 * Internal class for a doubly-linked list node containing a key/value pair.
474 * @param {KEY} key The key.
475 * @param {VALUE} value The value.
476 * @constructor
477 * @template KEY, VALUE
478 * @private
479 */
480 goog.structs.LinkedMap.Node_ = function(key, value) {
481 /** @type {KEY} */
482 this.key = key;
483
484 /** @type {VALUE} */
485 this.value = value;
486 };
487
488
489 /**
490 * The next node in the list.
491 * @type {!goog.structs.LinkedMap.Node_<KEY, VALUE>}
492 */
493 goog.structs.LinkedMap.Node_.prototype.next;
494
495
496 /**
497 * The previous node in the list.
498 * @type {!goog.structs.LinkedMap.Node_<KEY, VALUE>}
499 */
500 goog.structs.LinkedMap.Node_.prototype.prev;
501
502
503 /**
504 * Causes this node to remove itself from the list.
505 */
506 goog.structs.LinkedMap.Node_.prototype.remove = function() {
507 this.prev.next = this.next;
508 this.next.prev = this.prev;
509
510 delete this.prev;
511 delete this.next;
512 };