0
# LRU Map
1

2
A doubly linked list-based Least Recently Used (LRU) cache that maintains a finite key-value map where the most recently used items are kept alive while older, less recently used items are evicted to make room for newer items. Provides O(1) complexity for all operations.
3

4
## Package Information
5

6
- **Package Name**: lru_map
7
- **Package Type**: npm
8
- **Language**: JavaScript with TypeScript definitions
9
- **Installation**: `npm install lru_map`
10

11
## Core Imports
12

13
```typescript
14
import { LRUMap } from "lru_map";
15
```
16

17
For CommonJS:
18

19
```javascript
20
const { LRUMap } = require("lru_map");
21
```
22

23
For AMD:
24

25
```javascript
26
define(["lru_map"], function(lru) {
27
  const { LRUMap } = lru;
28
});
29
```
30

31
## Basic Usage
32

33
```typescript
34
import { LRUMap } from "lru_map";
35

36
// Create LRU cache with capacity of 3
37
const cache = new LRUMap<string, number>(3);
38

39
// Add entries
40
cache.set('adam', 29);
41
cache.set('john', 26);
42
cache.set('angela', 24);
43

44
console.log(cache.toString()); // "adam:29 < john:26 < angela:24"
45

46
// Access entry (moves to most recently used)
47
const johnAge = cache.get('john'); // 26
48
console.log(cache.toString()); // "adam:29 < angela:24 < john:26"
49

50
// Adding 4th entry evicts oldest
51
cache.set('zorro', 141);
52
console.log(cache.toString()); // "angela:24 < john:26 < zorro:141"
53
// 'adam' was evicted
54

55
// Alternative constructor with entries
56
const cacheFromEntries = new LRUMap([
57
  ['key1', 'value1'],
58
  ['key2', 'value2']
59
]);
60
```
61

62
## Architecture
63

64
LRU Map uses a doubly-linked list design for efficient cache management:
65

66
- **Doubly-linked list**: Enables O(1) complexity for insertion, deletion, and reordering
67
- **Hash map lookup**: Internal Map provides O(1) key-to-entry mapping
68
- **Head/tail pointers**: `oldest` (head) and `newest` (tail) entries for efficient eviction
69
- **Generic types**: Full TypeScript support with `LRUMap<K,V>`
70
- **Map-compatible API**: Similar interface to JavaScript's native Map
71

72
## Capabilities
73

74
### Construction
75

76
Create new LRU cache instances with optional capacity limits and initial entries.
77

78
```typescript { .api }
79
/**
80
 * Create LRU cache with specified capacity limit
81
 */
82
constructor(limit: number, entries?: Iterable<[K,V]>);
83

84
/**
85
 * Convenience constructor equivalent to new LRUMap(count(entries), entries)
86
 */
87
constructor(entries: Iterable<[K,V]>);
88
```
89

90
### Core Cache Operations
91

92
Essential cache operations for storing, retrieving, and managing entries.
93

94
```typescript { .api }
95
/**
96
 * Add or update entry and mark as most recently used
97
 * @param key - Entry key
98
 * @param value - Entry value
99
 * @returns This LRUMap instance for chaining
100
 */
101
set(key: K, value: V): LRUMap<K,V>;
102

103
/**
104
 * Get value and mark entry as most recently used
105
 * @param key - Entry key
106
 * @returns Value if found, undefined otherwise
107
 */
108
get(key: K): V | undefined;
109

110
/**
111
 * Check if key exists without affecting usage order
112
 * @param key - Entry key
113
 * @returns True if key exists
114
 */
115
has(key: K): boolean;
116

117
/**
118
 * Remove entry from cache
119
 * @param key - Entry key to remove
120
 * @returns Removed value if found, undefined otherwise
121
 */
122
delete(key: K): V | undefined;
123

124
/**
125
 * Remove all entries from cache
126
 */
127
clear(): void;
128
```
129

130
### Advanced Access Operations
131

132
Additional methods for cache inspection and management.
133

134
```typescript { .api }
135
/**
136
 * Access value without marking as recently used (peek)
137
 * @param key - Entry key
138
 * @returns Value if found, undefined otherwise
139
 */
140
find(key: K): V | undefined;
141

142
/**
143
 * Remove and return least recently used entry
144
 * @returns Tuple of [key, value] or undefined if empty
145
 */
146
shift(): [K,V] | undefined;
147

148
/**
149
 * Replace all entries with provided iterable
150
 * @param entries - Iterable of [key, value] pairs
151
 */
152
assign(entries: Iterable<[K,V]>): void;
153
```
154

155
### Iteration and Traversal
156

157
Methods for iterating over cache entries in LRU order (oldest to newest).
158

159
```typescript { .api }
160
/**
161
 * Iterator over keys from oldest to newest
162
 */
163
keys(): Iterator<K>;
164

165
/**
166
 * Iterator over values from oldest to newest
167
 */
168
values(): Iterator<V>;
169

170
/**
171
 * Iterator over [key, value] pairs from oldest to newest
172
 */
173
entries(): Iterator<[K,V]>;
174

175
/**
176
 * Default iterator (same as entries())
177
 */
178
[Symbol.iterator](): Iterator<[K,V]>;
179

180
/**
181
 * Execute function for each entry from oldest to newest
182
 * @param fun - Function to call for each entry
183
 * @param thisArg - Optional this context
184
 */
185
forEach(fun: (value: V, key: K, m: LRUMap<K,V>) => void, thisArg?: any): void;
186
```
187

188
### Serialization
189

190
Convert cache contents to standard data formats.
191

192
```typescript { .api }
193
/**
194
 * Convert to JSON-serializable array
195
 * @returns Array of {key, value} objects in LRU order
196
 */
197
toJSON(): Array<{key: K, value: V}>;
198

199
/**
200
 * Create human-readable string representation
201
 * @returns String showing entries in LRU order: "key1:value1 < key2:value2"
202
 */
203
toString(): string;
204
```
205

206
### Properties
207

208
Cache state and configuration properties.
209

210
```typescript { .api }
211
/**
212
 * Current number of entries (read-only)
213
 */
214
readonly size: number;
215

216
/**
217
 * Maximum number of entries allowed
218
 */
219
limit: number;
220

221
/**
222
 * Least recently used entry (internal use, may be invalidated)
223
 */
224
readonly oldest: Entry<K,V>;
225

226
/**
227
 * Most recently used entry (internal use, may be invalidated)
228
 */
229
readonly newest: Entry<K,V>;
230
```
231

232
## Types
233

234
```typescript { .api }
235
/**
236
 * Entry holds key and value with internal linking pointers
237
 * Note: Entry objects should not be stored or modified directly
238
 */
239
interface Entry<K,V> {
240
  key: K;
241
  value: V;
242
}
243
```
244

245
## Error Handling
246

247
- Constructor throws `Error('overflow')` if initial entries exceed the specified limit during `assign()`
248
- All other methods handle missing keys gracefully by returning `undefined`
249
- No other exceptions are thrown during normal operation
250

251
## Advanced Usage Patterns
252

253
**Custom Eviction Handling:**
254

255
```typescript
256
// Wrap shift method to handle evicted entries
257
const cache = new LRUMap<string, Resource>(100);
258
const originalShift = cache.shift.bind(cache);
259
cache.shift = function() {
260
  const entry = originalShift();
261
  if (entry) {
262
    // Clean up evicted resource
263
    cleanupResource(entry[1]);
264
  }
265
  return entry;
266
};
267
```
268

269
**Iteration Examples:**
270

271
```typescript
272
// Iterate in LRU order (oldest first)
273
for (const [key, value] of cache) {
274
  console.log(`${key}: ${value}`);
275
}
276

277
// Get all keys as array
278
const allKeys = Array.from(cache.keys());
279

280
// Process with forEach
281
cache.forEach((value, key) => {
282
  console.log(`Processing ${key}: ${value}`);
283
});
284
```
285

286
**JSON Serialization:**
287

288
```typescript
289
// Serialize cache state
290
const serialized = JSON.stringify(cache.toJSON());
291

292
// Restore from serialized state
293
const restored = new LRUMap<string, number>(100);
294
const data = JSON.parse(serialized);
295
restored.assign(data.map(item => [item.key, item.value]));
296
```