const assert = require('assert')

let LRUCache = function (capacity) {
 this.capacity = capacity;
 this.cache = {};
 this.head = null;
 this.tail = null;
 this.size = 0;
};

LRUCache.prototype.removeNode = function (node) {
 let prev = node.prev,
 next = node.next;

if (prev) {
 prev.next = next;
}

if (next) {
 next.prev = prev;
} 

if (node === this.head) {
 this.head = next;
}

if (node === this.tail) {
 this.tail = prev;
}

 node.next = null;
 node.prev = null;
 
 this.size--;

 delete this.cache[node.key];

 return node;
};

LRUCache.prototype.get = function (key) {
 if (this.cache[key]) {
  let cacheHit = this.cache[key];

  this.removeNode(cacheHit);

  this.put(cacheHit.key, cacheHit.value);

  return cacheHit.value;
 }

 return -1;

};

LRUCache.prototype.put = function (key, value) {

 if (this.cache[key]) {
  this.removeNode(this.cache[key]);

  this.put(key, value);

  return
 }
 
 if (this.capacity === this.size) {
  this.removeNode(this.tail);
 }

 let itemToBeAdded = {key: key, value: value, next: null, prev: null};

 if (this.size === 0) {
  this.head = this.tail = itemToBeAdded;
 } 
 else {
  // Make the item being added the head of the linked list
  let currentHead = this.head;
  
  itemToBeAdded.next = currentHead;

  currentHead.prev = itemToBeAdded;
  
  this.head = itemToBeAdded;
 }

 this.cache[key] = itemToBeAdded;

 this.size++;

};


let cache = new LRUCache(2);

cache.put(1, 1);
cache.put(2, 2);
assert.equal(cache.get(1), 1);
cache.put(3, 3);
assert.equal(cache.get(2), -1);
cache.put(4, 4);
assert.equal(cache.get(1), -1);
assert.equal(cache.get(3), 3);
assert.equal(cache.get(4), 4);