Skip to content

Instantly share code, notes, and snippets.

@SarasArya
Created March 28, 2019 18:26
Show Gist options
  • Save SarasArya/d3802e7354dee146f86e111b25af3f53 to your computer and use it in GitHub Desktop.
Save SarasArya/d3802e7354dee146f86e111b25af3f53 to your computer and use it in GitHub Desktop.
Create an LRU in javascript
const NEWER = Symbol("newer");
const OLDER = Symbol("older");
class LRU {
constructor(limit = 10) {
this.limit;
this.size;
this.cache = new Map();
this.newest = undefined;
this.oldest = undefined;
}
get(key) {
const entry = this.cache.get(key);
if (!entry) {
console.log("No entry found");
return;
}
this.markAsUsed(entry);
return entry.value;
}
set(key, value) {
let entry = this.cache.get(key);
if (entry) {
entry.value = value;
this.markAsUsed(entry);
return this;
}
// no entry;
const newNode = new createNode(key, value);
entry = this.cache.set(newNode);
if (this.newest) {
this.newest[NEWER] = entry;
entry[OLDER] = this.newest;
} else {
this.oldest = entry;
}
this.newest = entry;
++this.size;
if (this.size > this.limit) {
// we hit the limit remove the head
this.shift();
}
}
shift() {
// if (that's the only node remove);
const entry = this.oldest;
if (entry) {
if (this.oldest[NEWER]) {
this.oldest = this.oldest[NEWER];
this.oldest[OLDER] = undefined;
} else {
this.oldest = undefined;
this.newest = undefined;
}
entry[NEWER] = entry[OLDER] = undefined;
this.cache.delete(entry.key);
--this.size;
return [entry.key, entry.value];
}
// remove the head;
}
markAsUsed(entry) {
if (this.newest === entry) {
return;
}
if (entry[NEWER]) {
// A B C D E
// if entry = A
// it sets B(entry[newer]) as the oldest
if (this.oldest === entry) {
this.oldest = entry[NEWER];
}
// point C <- E
entry[NEWER][OLDER] = entry[OLDER];
}
if (entry[OLDER]) {
entry[OLDER][NEWER] = entry[NEWER];
}
// change entry new and old
entry[NEWER] = undefined;
entry[OLDER] = this.newest;
// change the newest
if (this.newest) {
this.newest[NEWER] = entry;
}
this.newest = entry;
}
toString() {
let s;
entry = this.oldest;
while (entry) {
s += `${this.entry.key} : ${this.entry.value}`;
entry = entry[NEWER];
if (entry) {
s += " < ";
}
}
return s;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment