Find the cost of adding an npm package to your app's bundle size
teardown.kelinci.dev
1interface LRUNode<K, V> {
2 key: K;
3 value: V;
4 prev: LRUNode<K, V> | null;
5 next: LRUNode<K, V> | null;
6}
7
8/**
9 * a least recently used (LRU) cache with fixed capacity
10 * evicts the least recently used items when capacity is exceeded
11 */
12export class LRUCache<K, V> {
13 readonly #size: number;
14 #count = 0;
15
16 #map = new Map<K, LRUNode<K, V>>();
17 #head: LRUNode<K, V> | null = null;
18 #tail: LRUNode<K, V> | null = null;
19
20 /**
21 * creates a new LRU cache with the specified capacity
22 * @param size the maximum number of items the cache can hold
23 */
24 constructor(size: number) {
25 this.#size = size;
26 }
27
28 /** the maximum capacity of the cache */
29 get size(): number {
30 return this.#size;
31 }
32
33 /**
34 * gets a value without affecting its position in the cache
35 * @param key the key to look up
36 * @returns the value associated with the key, or undefined if not found
37 */
38 peek(key: K): V | undefined {
39 const node = this.#map.get(key);
40 if (node === undefined) {
41 return undefined;
42 }
43
44 return node.value;
45 }
46
47 /**
48 * gets a value and marks it as most recently used
49 * @param key the key to look up
50 * @returns the value associated with the key, or undefined if not found
51 */
52 get(key: K): V | undefined {
53 const node = this.#map.get(key);
54 if (node === undefined) {
55 return undefined;
56 }
57
58 this.#moveToFront(node);
59 return node.value;
60 }
61
62 /**
63 * stores a value for the given key, marking it as most recently used
64 * evicts the least recently used item if the cache is at capacity
65 * @param key the key to store
66 * @param value the value to associate with the key
67 */
68 put(key: K, value: V): void {
69 {
70 const existing = this.#map.get(key);
71
72 if (existing !== undefined) {
73 existing.value = value;
74 this.#moveToFront(existing);
75 return;
76 }
77 }
78
79 {
80 const node: LRUNode<K, V> = { key, value, prev: null, next: null };
81 this.#map.set(key, node);
82 this.#addToFront(node);
83
84 this.#count++;
85 }
86
87 this.#evict();
88 }
89
90 /**
91 * removes a key from the cache
92 * @param key the key to remove
93 * @returns true if the key was found and removed, false otherwise
94 */
95 delete(key: K): boolean {
96 const node = this.#map.get(key);
97 if (node === undefined) {
98 return false;
99 }
100
101 this.#map.delete(key);
102 this.#removeNode(node);
103 this.#count--;
104 return true;
105 }
106
107 /**
108 * removes all items from the cache
109 */
110 clear(): void {
111 this.#map.clear();
112 this.#head = null;
113 this.#tail = null;
114 this.#count = 0;
115 }
116
117 /**
118 * checks if a key exists in the cache
119 * @param key the key to check
120 * @returns true if the key exists, false otherwise
121 */
122 has(key: K): boolean {
123 return this.#map.has(key);
124 }
125
126 /**
127 * iterates over the keys in LRU order (most to least recently used)
128 * @returns iterator of keys
129 */
130 *keys(): IterableIterator<K> {
131 let current = this.#head;
132 while (current !== null) {
133 yield current.key;
134 current = current.next;
135 }
136 }
137
138 /**
139 * iterates over the values in LRU order (most to least recently used)
140 * @returns iterator of values
141 */
142 *values(): IterableIterator<V> {
143 let current = this.#head;
144 while (current !== null) {
145 yield current.value;
146 current = current.next;
147 }
148 }
149
150 /**
151 * iterates over the key-value pairs in LRU order (most to least recently used)
152 * @returns iterator of [key, value] tuples
153 */
154 *entries(): IterableIterator<[K, V]> {
155 let current = this.#head;
156 while (current !== null) {
157 yield [current.key, current.value];
158 current = current.next;
159 }
160 }
161
162 #moveToFront(node: LRUNode<K, V>): void {
163 if (this.#head === node) {
164 return;
165 }
166
167 if (node.prev !== null) {
168 node.prev.next = node.next;
169 }
170
171 if (node.next !== null) {
172 node.next.prev = node.prev;
173 } else {
174 this.#tail = node.prev;
175 }
176
177 node.prev = null;
178 node.next = this.#head;
179
180 // Safe because this method is only called when head exists
181 this.#head!.prev = node;
182 this.#head = node;
183 }
184
185 #addToFront(node: LRUNode<K, V>): void {
186 node.next = this.#head;
187 node.prev = null;
188
189 if (this.#head !== null) {
190 this.#head.prev = node;
191 } else {
192 this.#tail = node;
193 }
194
195 this.#head = node;
196 }
197
198 #removeNode(node: LRUNode<K, V>): void {
199 if (node.prev !== null) {
200 node.prev.next = node.next;
201 } else {
202 this.#head = node.next;
203 }
204
205 if (node.next !== null) {
206 node.next.prev = node.prev;
207 } else {
208 this.#tail = node.prev;
209 }
210 }
211
212 #evict(): void {
213 const excess = this.#count - this.#size;
214 if (excess <= 0) {
215 return;
216 }
217
218 let current: LRUNode<K, V> = this.#tail!;
219
220 for (let i = 0; i < excess; i++) {
221 this.#map.delete(current.key);
222 current = current.prev!;
223 }
224
225 current.next = null;
226 this.#tail = current;
227
228 this.#count -= excess;
229 }
230}