Skip to content

Instantly share code, notes, and snippets.

@robbywashere robbywashere/lru.ts
Last active Feb 13, 2019

Embed
What would you like to do?
simple LRU cache typescript implementation
import { strict as assert } from "assert";
type Node<V> = { parent?: Node<V>; next?: Node<V>; value: V };
class DoublyLinkedList<V> {
private _head?: Node<V>;
private _tail?: Node<V>;
get head() {
return this._head!;
}
get tail() {
return this._tail!;
}
set head(node: Node<V>) {
this._head = node;
}
set tail(node: Node<V>) {
this._tail = node;
}
moveTohead(node: Node<V>) {
if (this._head) this._head.parent = node;
node.next = this._head;
if (this._tail === node) this._tail = this._tail.parent;
this._head = node;
return node;
}
unshift(value: V) {
let node = { value } as Node<V>;
let _head = this._head;
this._head = node;
this._head.next = _head;
if (_head) _head.parent = node;
if (!this._tail) this._tail = node;
return node;
}
pop() {
const _tail = this._tail!;
this._tail = _tail.parent;
return _tail;
}
index(n: number) {
let count = 0;
let node: Node<V> | undefined = this._head;
while (node && count < n) {
node = node.next as Node<V>;
count++;
}
return node;
}
}
class LRU<K, V> {
private _size = 0;
private cache = new Map<K, Node<V>>();
private weakKeyMap = new WeakMap<Node<V>, K>();
private _dll = new DoublyLinkedList<V>();
constructor(private max: number) {}
get size() {
return this._size;
}
get dll() {
return this._dll;
}
get(key: K): Node<V> | undefined {
if (this.cache.has(key)) {
const node = this.cache.get(key);
return this._dll.moveTohead(node!);
}
}
set(key: K, value: V) {
if (this.cache.has(key)) {
let node = this.cache.get(key)!;
node.value = value;
return this._dll.moveTohead(node);
}
let node = this._dll.unshift(value);
this.weakKeyMap.set(node, key);
this.cache.set(key, node);
this._size++;
if (this._size > this.max) {
this.cache.delete(this.weakKeyMap.get(this._dll.pop())!);
this._size--;
}
return node;
}
}
const lru = new LRU<string, number>(3);
lru.set("one", 1);
assert.equal(lru.dll.index(0)!.value, 1, "index(0) value should equal 1");
assert.equal(
lru.dll.head.value,
1,
"head value should equal 1, the same as index(0)"
);
lru.set("two", 2);
assert.equal(lru.dll.index(0)!.value, 2);
assert.equal(
lru.dll.head.value,
2,
"head value should equal 2, the same as index(0)"
);
lru.set("three", 3);
assert.equal(lru.dll.index(0)!.value, 3);
assert.equal(lru.dll.tail!.value, 1, "tail value should equal 1");
lru.set("three", 333);
assert.equal(
lru.dll.index(0)!.value,
333,
"should replace value of existing key"
);
assert.equal(lru.size, 3, "lru size should remain at 3");
assert.equal(lru.dll.head!.value, 333, "head value should equal 333");
assert.equal(lru.dll.tail!.value, 1, "tail value should equal 1");
lru.set("four", 4);
assert.equal(lru.dll.tail!.value, 2, "new tail value should equal 2");
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.