LRU Dictionary

by Anton Bagayev

HTML

<p id="intermediate"></p>
<p></p>
<p id="output"></p>

JavaScript

let Node = function() {
  this.value = undefined;
  this.prev = undefined;
  this.next = undefined;
}

let DictionaryWithLast = function() {
  this._dict = {};
  this.lruList = undefined;  
}  
	
DictionaryWithLast.prototype.set = function(key, value) {
  let node = new Node();
  node.value = value;
  if (this.lruList !== undefined) {
  	this.lruList.prev = node;
  }
  node.next = this.lruList;
  this.lruList = node;
  this._dict[key] = node;
}

DictionaryWithLast.prototype.get = function(key) {
  if (this._dict[key] == undefined) {
    return "No such key exists";
  }
  let result = this._dict[key].value;
  this._dict[key].next.prev = this._dict[key].prev;
  this._dict[key].prev.next = this._dict[key].next;
  this._dict[key].next = this.lruList;
  this._dict[key].prev = undefined;
  this.lruList.prev = this._dict[key];
  this.lruList = this._dict[key];
}

DictionaryWithLast.prototype.remove = function(key) {
  if (this._dict[key] == undefined) {
    return "No such key exists";
  }
  let result = this._dict[key];
  delete this._dict[key];
  this._last = result.last;
  return result;
}

DictionaryWithLast.prototype.last = function() {
  return this._last;
}

function printDict(dict) {
	let keys = Object.keys(dict);
  let result = "";
  for (let idx in keys) {
  	let key = keys[idx]; 
  	result += key + ":" + dict[key].value + 
    	" prev: " + (dict[key].prev ? dict[key].prev.value : "undefined") +
      " next: " + (dict[key].next ? dict[key].next.value : "undefined") + "\n";
  }
  return result;
}

let dict = new DictionaryWithLast();
dict.set("a", "anton");
dict.set("b", "brian");
dict.set("c", "charles");
document.getElementById("intermediate").innerText = printDict(dict._dict);