lru_cache.js

// Least Recently Used cache
// Implement a data structure to store keys for a LRU cache

/*
  doubly linked list to hold order of keys
  front of list is the most recently used key
  back of list is the least recently used key

  dictionary holds references to each node in the linked list
  keys are the keys being held
  values are pointers to the nodes

  node structure
  var cacheNode = {
    data: 'key',
    previous: null,
    next: null,
  };

  The LRU Cache implements two methods:
  get(key) - 
    if the key is not in the cache, return null
    if the key is in the cache, return the value for that key and
      move the node representing that key's position to the front of the list

  set(key, value) - 
    if the key is already in the cache, replace the value for that key and 
      move that node to the front of the list
    if the key is not in the cache and the cache is not full, add that key to
      the front of the list
    if the key is not in the cache and the cache is full, delete the least
      recently used key and add the new key to the front of the list
*/

function Cache(max) {
  this.cacheStore = {};
  this.cachePointers = {};
  this.firstNode = null;
  this.lastNode = null;
  this.maxNodes = max;
}

Cache.prototype.newNode = function(data, previous, next) {
  return {
    data: data,
    previous: prev,
    next: next,
  };
}

Cache.prototype.get = function(key) {
  if (key in this.cachePointers) {
    /* Move the corresponding node to the front of the list */
    var currentNode = this.cachePointers[key];

    // Splice out the node
    currentNode.previous.next = currentNode.next;
    // Move the node to the front
    this.firstNode.previous = currentNode;
    this.firstNode = currentNode;

    return this.cacheStore[key];
  } else {
    return -1;
  }
};

Cache.prototype.set = function(key, value) {
  if (Object.keys(this.cachePointers).length === this.maxNodes) {
    // Delete the least recently used key
    this.lastNode = this.lastNode.previous;

    // Potential memory leak? Do we need to delete the old node?
  }

  /* Store the new value */
  if (key in this.cachePointers) {
    /* Move the corresponding node to the front of the list */
    var currentNode = this.cachePointers[key];

    // Splice out the node
    currentNode.previous.next = currentNode.next;
    // Move the node to the front
    this.firstNode.previous = currentNode;
    this.firstNode = currentNode;

    this.cacheStore[key] = value;
  } else {
    // Create a new node
    var newNode = this.newNode(key, null, this.firstNode);
    // If firstNode is null, that means the cache is empty
    if (this.firstNode === null) {
      // Set the lastNode to point to the new node
      this.lastNode = newNode;
    } else {
      // Set the old first node's prev pointer to the new node
      this.firstNode.previous = newNode;
    }
    // Set the new node's next pointer to the previous first node
    newNode.next = this.firstNode;
    // Set the first node pointer to the new node
    this.firstNode = newNode;

    // Store the key,value pair in the cache and the pointer to the node
    this.cacheStore[key] = value;
    this.cachePointers[key] = newNode;
  }
  
}