JavaScript LRU cache implementation

lru_cache.js

var LRUCache = (function() {
  function LRUCache(options) {
    this._options  = options || {}
    this._map      = {}
    this._queue    = {}
    this._capacity = this._options.capacity || 10
    this._size     = 0
  }

  var _detachFromQueue = function(node, queue) {
    if (node === queue.first)
      queue.first = node.next
    if (node === queue.last)
      queue.last = node.prev
    if (node.prev != null)
      node.prev.next = node.next
    if (node.next != null)
      node.next.prev = node.prev
  }

  var _moveToLast = function(node, queue) {
    node.prev = queue.last
    node.next = null
    if (queue.last != null)
      queue.last.next = node
    queue.last = node
    if (queue.first == null)
      queue.first = node
  }

  LRUCache.prototype.put = function(key, value) {
    var replaced = this.delete(key)
    var queue    = this._queue
    var node     = { value: value, key: key }
    _moveToLast(node, queue)
    this._map[key] = node
    this._size += 1
    if (this._size > this._capacity)
      this.delete(this._queue.first.key)
    return replaced
  }

  LRUCache.prototype.get = function(key) {
    var node = this._map[key]
    if (node == null) return null
    if (this._options.touchOnGet) {
      _detachFromQueue(node, this._queue)
      _moveToLast(node, this._queue)
    }
    return node.value
  }

  LRUCache.prototype.delete = function(key) {
    var node = this._map[key]
    if (node == null) {
      return false
    } else {
      _detachFromQueue(node, this._queue)
      delete this._map[key]
      this._size -= 1
      return true
    }
  }

  LRUCache.prototype.forEach = function(callback, thisArg) {
    var node = this._queue.first
    while(node != null) {
      callback.call(thisArg, node.value, node.key)
      node = node.next
    }
  }

  return LRUCache;
})();

// --------- Tests --------- //

(function() {
  var __when, __then, __errors
  var __group = 0

  var when = function(description, callback) {
    __when   = description
    __then   = []
    __errors = []
    __group++
    console.log('Test group ' + __group + ':')
    callback()
    if (__errors.length > 0)
      for (var i in __errors) { console.error(__errors[i]) }
    else
      console.log('All fine :)')
  }

  var then = function(description, callback) {
    __then.push(description)
    callback()
  }

  var assert = function(condition, message) {
    if (condition == false) {
      var error = 'Assertion failed: when ' + __when + ', then ' + __then.join(' then ') + ', ' + message
      __errors.push(error)
    }
  }

  when('starting from a cache with capacity 3', function() {
    var c = new LRUCache({ capacity: 3 })
    then('putting a = 1', function() {
      c.put('a', 1)
      assert(c.get('a') == 1, 'get a returns 1')
      assert(c.get('b') == null, 'get b returns nothing')
    })
    then('putting b = 2', function() {
      c.put('b', 2)
      assert(c.get('a') == 1, 'get a returns 1')
      assert(c.get('b') == 2, 'get b returns 2')
    })
    then('putting c = 3', function() {
      c.put('c', 3)
      assert(c.get('a') == 1, 'get a returns 1')
      assert(c.get('b') == 2, 'get b returns 2')
      assert(c.get('c') == 3, 'get c returns 3')
    }) 
    then('putting d = 4', function() {
      c.put('d', 4)
      assert(c.get('a') == null, 'get a returns nothing')
      assert(c.get('b') == 2, 'get b returns 2')
      assert(c.get('c') == 3, 'get c returns 3')
      assert(c.get('d') == 4, 'get d returns 4')
    })
    then('putting b = 5', function() {
      c.put('b', 5)
      assert(c.get('b') == 5, 'get b returns 5')
      assert(c.get('c') == 3, 'get c returns 3')
      assert(c.get('d') == 4, 'get d returns 4')
    })
    then('putting e = 0', function() {
      c.put('e', 0)
      assert(c.get('b') == 5, 'get b returns 5')
      assert(c.get('c') == null, 'get c returns nothing')
      assert(c.get('d') == 4, 'get d returns 4')
      assert(c.get('e') == 0, 'get e returns 0')
    })
    then('deleting b', function() {
      c.delete('b')
      assert(c.get('b') == null, 'get b returns nothing')
      assert(c.get('d') == 4, 'get d returns 4')
      assert(c.get('e') == 0, 'get e returns 0')
    })
    then('deleting e', function() {
      c.delete('e')
      assert(c.get('d') == 4, 'get d returns 4')
      assert(c.get('e') == null, 'get e returns nothing')
    })
    then('deleting d', function() {
      c.delete('d')
      assert(c.get('d') == null, 'get d returns nothing')
    })
  })

  when('starting with a cache with capacity 3 and touchOnGet', function() {
    var c2 = new LRUCache({ capacity: 3, touchOnGet: true })
    then('putting a = 1, b = 2, c = 3, then getting a, then putting d = 4', function() {
      c2.put('a', 1)
      c2.put('b', 2)
      c2.put('c', 3)
      c2.get('a')
      c2.put('d', 4)
      assert(c2.get('a') == 1, 'get a returns 1')
      assert(c2.get('b') == null, 'get b returns nothing')
      assert(c2.get('c') == 3, 'get c returns 3')
    })
  })

  when('starting with a cache with capacity 3', function() {
    var c3 = new LRUCache({ capacity: 3 })
    then('putting a = 1, b = 2, c = 3 then iterating with forEach', function() {
      c3.put('a', 1)
      c3.put('b', 2)
      c3.put('c', 3)
      var list = []
      c3.forEach(function(val, key) {
        list.push([key, val])
      })
      assert(list.toString() == 'a,1,b,2,c,3', 'the elements are iterated in order of insertion')
    })
  })
})();