module.exports = function(size) {
    return new LruCache(size)
  }
  
  function LruCache(size) {
    this.capacity = size | 0
    this.map = Object.create(null)
    this.list = new DoublyLinkedList()
  }
  
  LruCache.prototype.get = function(key) {
    var node = this.map[key]
    if (node == null) return undefined
    this.used(node)
    return node.val
  }
  
  LruCache.prototype.set = function(key, val) {
    var node = this.map[key]
    if (node != null) {
      node.val = val
    } else {
      if (!this.capacity) this.prune()
      if (!this.capacity) return false
      node = new DoublyLinkedNode(key, val)
      this.map[key] = node
      this.capacity--
    }
    this.used(node)
    return true
  }
  
  LruCache.prototype.used = function(node) {
    this.list.moveToFront(node)
  }
  
  LruCache.prototype.prune = function() {
    var node = this.list.pop()
    if (node != null) {
      delete this.map[node.key]
      this.capacity++
    }
  }
  
  
  function DoublyLinkedList() {
    this.firstNode = null
    this.lastNode = null
  }
  
  DoublyLinkedList.prototype.moveToFront = function(node) {
    if (this.firstNode == node) return
  
    this.remove(node)
  
    if (this.firstNode == null) {
      this.firstNode = node
      this.lastNode = node
      node.prev = null
      node.next = null
    } else {
      node.prev = null
      node.next = this.firstNode
      node.next.prev = node
      this.firstNode = node
    }
  }
  
  DoublyLinkedList.prototype.pop = function() {
    var lastNode = this.lastNode
    if (lastNode != null) {
      this.remove(lastNode)
    }
    return lastNode
  }
  
  DoublyLinkedList.prototype.remove = function(node) {
    if (this.firstNode == node) {
      this.firstNode = node.next
    } else if (node.prev != null) {
      node.prev.next = node.next
    }
    if (this.lastNode == node) {
      this.lastNode = node.prev
    } else if (node.next != null) {
      node.next.prev = node.prev
    }
  }
  
  
  function DoublyLinkedNode(key, val) {
    this.key = key
    this.val = val
    this.prev = null
    this.next = null
  }