Created
September 5, 2019 05:10
-
-
Save rakin92/41fd0e707fb24724ad8f2903cc78af59 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// LRU CACHE | |
class Node { | |
constructor(key, value, next = null, prev = null) { | |
this.key = key; | |
this.value = value; | |
this.next = next; | |
this.prev = prev; | |
} | |
} | |
class LRU { | |
constructor(limit = 10) { | |
this.size = 0; | |
this.limit = limit; | |
this.head = null; | |
this.tail = null; | |
this.cache = {}; | |
} | |
// Write to head of LinkedList | |
write(key, value) { | |
this.ensureLimit(); | |
if (!this.head) { | |
this.head = this.tail = new Node(key, value); | |
} else { | |
const node = new Node(key, value, this.head.next); | |
this.head.prev = node; | |
this.head = node; | |
} | |
//Update the cache map | |
this.cache[key] = this.head; | |
this.size++; | |
} | |
// Read from cache map and make that node as new Head of LinkedList | |
read(key) { | |
if (this.cache[key]) { | |
const value = this.cache[key].value; | |
const node = new Node(key, value); | |
// node removed from it's position and cache | |
this.remove(key) | |
this.write(key, value); | |
return value; | |
} | |
console.log(`Item not available in cache for key ${key}`); | |
} | |
ensureLimit() { | |
if (this.size === this.limit) { | |
this.remove(this.tail.key) | |
} | |
} | |
remove(key) { | |
const node = this.cache[key]; | |
if (node.prev !== null) { | |
node.prev.next = node.next; | |
} else { | |
this.head = node.next; | |
} | |
if (node.next !== null) { | |
node.next.prev = node.prev; | |
} else { | |
this.tail = node.prev | |
} | |
delete this.cache[key]; | |
this.size--; | |
} | |
clear() { | |
this.head = null; | |
this.tail = null; | |
this.size = 0; | |
this.cache = {}; | |
} | |
// Invokes the callback function with every node of the chain and the index of the node. | |
forEach(fn) { | |
let node = this.head; | |
let counter = 0; | |
while (node) { | |
fn(node, counter); | |
node = node.next; | |
counter++; | |
} | |
} | |
// To iterate over LRU with a 'for...of' loop | |
*[Symbol.iterator]() { | |
let node = this.head; | |
while (node) { | |
yield node; | |
node = node.next; | |
} | |
} | |
} | |
let lruCache = new LRU(3); | |
lruCache.write('a', 123); | |
lruCache.write('b', 456); | |
lruCache.write('c', 789); | |
lruCache.read('a'); // output 123 | |
// Now max limit 3 is reached. Let's add a new element | |
lruCache.write('d', 0); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment