text: // Copyright 2014 The Chromium Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  
  /**
   * A linked-list node which holds data for cache entry such as key, value, size.
   * @param {string} key
   * @param {T} value
   * @param {number} size
   * @constructor
   * @template T
   */
  function LRUCacheNode(key, value, size) {
    /** @type {string} */
    this.key = key;
  
    /** @type {T} */
    this.value = value;
  
    /** @type {number} */
    this.size = size;
  
    /** @type {LRUCacheNode} */
    this.next = null;
  
    /** @type {LRUCacheNode} */
    this.prev = null;
  }
  
  /**
   * Container of the list of cache nodes.
   * @constructor
   */
  function LRUCacheList() {
    /** @private {!LRUCacheNode} */
    this.sentinelTail_ = new LRUCacheNode('sentinel', null, 0);
  
    /** @private {LRUCacheNode} */
    this.head_ = this.sentinelTail_;
  }
  
  /**
   * Removes a node from this list.
   * @param {!LRUCacheNode} node
   */
  LRUCacheList.prototype.remove = function(node) {
    if (node.prev)
      node.prev.next = node.next;
    if (node.next)
      node.next.prev = node.prev;
    if (node === this.head_)
      this.head_ = node.next;
    node.prev = null;
    node.next = null;
  };
  
  /**
   * Adds a node at the head of this list.
   * @param {!LRUCacheNode} node
   */
  LRUCacheList.prototype.prepend = function(node) {
    node.prev = null;
    node.next = this.head_;
    node.next.prev = node;
    this.head_ = node;
  };
  
  /**
   * Returns the last node of the list, or null if the list has no nodes.
   * @return {LRUCacheNode}
   */
  LRUCacheList.prototype.lastNode = function() {
    return this.sentinelTail_.prev;
  };
  
  /**
   * Cache management class implementing LRU algorithm.
   * @param {number} maxSize Maximum total size of items this cache can hold. When
   *     items are put without specifying their sizes, their sizes are treated as
   *     1 and the |maxSize| can be interpreted as the maximum number of items.
   *     If items are put with specifying their sizes in bytes, the |maxSize| can
   *     be interpreted as the maximum number of bytes.
   * @constructor
   * @template T
   */
  function LRUCache(maxSize) {
    /** @private {number} */
    this.totalSize_ = 0;
  
    /** @private {number} */
    this.maxSize_ = maxSize;
  
    /** @private {!LRUCacheList} */
    this.list_ = new LRUCacheList();
  
    /** @private {!Object<!LRUCacheNode>} */
    this.nodes_ = {};
  }
  
  /**
   * Returns a cached item corresponding to the given key. The referenced item
   * will be the most recently used item and won't be evicted soon.
   * @param {string} key
   * @return {T}
   */
  LRUCache.prototype.get = function(key) {
    var node = this.nodes_[key];
    if (!node)
      return null;
  
    this.moveNodeToHead_(node);
    return node.value;
  };
  
  /**
   * Returns a cached item corresponding to the given key without making the
   * referenced item the most recently used item.
   * @param {string} key
   * @return {T}
   */
  LRUCache.prototype.peek = function(key) {
    var node = this.nodes_[key];
    if (!node)
      return null;
  
    return node.value;
  };
  
  /**
   * Returns true if the cache contains the key.
   * @param {string} key
   * @return {boolean}
   */
  LRUCache.prototype.hasKey = function(key) {
    return key in this.nodes_;
  };
  
  /**
   * Saves an item in this cache. The saved item will be the most recently used
   * item and won't be evicted soon. If an item with the same key already exists
   * in the cache, the existing item's value and size will be updated and the item
   * will become the most recently used item.
   * @param {string} key Key to find the cached item later.
   * @param {T} value Value of the item to be cached.
   * @param {number=} opt_size Size of the put item. If not specified, the size is
   *     regarded as 1. If the size is larger than the |maxSize_|, put operation
   *     will be ignored keeping cache state unchanged.
   */
  LRUCache.prototype.put = function(key, value, opt_size) {
    var size = opt_size ? opt_size : 1;
    if (size > this.maxSize_)
      return;
  
    var node = this.nodes_[key];
  
    while (this.totalSize_ + size - (node ? node.size : 0) > this.maxSize_) {
      this.evictLastNode_();
      // The referenced node may be evicted, so it needs to be updated.
      node = this.nodes_[key];
    }
  
    if (node) {
      this.updateNode_(node, value, size);
      this.moveNodeToHead_(node);
    } else {
      node = new LRUCacheNode(key, value, size);
      this.prependNode_(node);
    }
  };
  
  /**
   * Removes an item from the cache.
   * @param {string} key
   */
  LRUCache.prototype.remove = function(key) {
    var node = this.nodes_[key];
    if (node)
      this.removeNode_(node);
  };
  
  /**
   * Returns the cache size.
   * @return {number}
   */
  LRUCache.prototype.size = function() {
    return this.totalSize_;
  };
  
  /**
   * Updates max size of the cache.
   * @param {number} value New max size.
   */
  LRUCache.prototype.setMaxSize = function(value) {
    this.maxSize_ = value;
    while (this.totalSize_ > this.maxSize_) {
      this.evictLastNode_();
    }
  };
  
  /**
   * Returns the max size of the cache.
   * @return {number}
   */
  LRUCache.prototype.getMaxSize = function() {
    return this.maxSize_;
  };
  
  /**
   * Evicts the oldest cache node.
   * @private
   */
  LRUCache.prototype.evictLastNode_ = function() {
    var lastNode = this.list_.lastNode();
    if (!lastNode)
      throw new Error('No more nodes to evict.');
  
    this.removeNode_(lastNode);
  };
  
  /**
   * Removes given node from this cache store completely.
   * @param {!LRUCacheNode} node
   * @private
   */
  LRUCache.prototype.removeNode_ = function(node) {
    this.list_.remove(node);
    this.totalSize_ -= node.size;
    console.assert(this.totalSize_ >= 0);
    console.assert(!!this.nodes_[node.key]);
    delete this.nodes_[node.key];
  };
  
  /**
   * Prepends given node to the head of list.
   * @param {!LRUCacheNode} node
   * @private
   */
  LRUCache.prototype.prependNode_ = function(node) {
    this.list_.prepend(node);
    this.totalSize_ += node.size;
    console.assert(this.totalSize_ <= this.maxSize_);
    console.assert(!this.nodes_[node.key]);
    this.nodes_[node.key] = node;
  };
  
  /**
   * Updates the given nodes size and value.
   * @param {!LRUCacheNode} node
   * @param {T} value
   * @param {number} size
   * @private
   */
  LRUCache.prototype.updateNode_ = function(node, value, size) {
    this.totalSize_ += size - node.size;
    console.assert(this.totalSize_ >= 0 && this.totalSize_ <= this.maxSize_);
    node.value = value;
    node.size = size;
  };
  
  /**
   * Moves the given node to the head of the linked list.
   * @param {!LRUCacheNode} node
   * @private
   */
  LRUCache.prototype.moveNodeToHead_ = function(node) {
    this.list_.remove(node);
    this.list_.prepend(node);
  };
  