ts-03-lru-cache

# Generic LRU cache

Implement **`solution.ts`** exporting a generic class:

```ts
export class LRUCache<K, V> {
  constructor(capacity: number);
  get(key: K): V | undefined;
  put(key: K, value: V): void;
  get size(): number;
}
```

A least-recently-used cache holding at most `capacity` entries.

- `get(key)` returns the stored value, or `undefined` if absent. A successful `get`
  counts as a **use** (it makes that key the most-recently used).
- `put(key, value)` inserts or updates a key. Updating an existing key also counts as a
  use. When inserting a **new** key would exceed `capacity`, evict the
  least-recently-used key first.
- `size` is the current number of entries (never exceeds `capacity`).
- Throw a `RangeError` if `capacity < 1`.

Example:

```ts
const c = new LRUCache<string, number>(2);
c.put("a", 1);
c.put("b", 2);
c.get("a");      // 1  -> "a" is now most-recently used
c.put("c", 3);   // evicts "b" (least-recently used)
c.get("b");      // undefined
c.get("a");      // 1
c.get("c");      // 3
c.size;          // 2
```

Keep it fully typed (must pass `tsc --noEmit` in strict mode). Do not use `any` in the
public API.

import { test } from "node:test";
import { strict as assert } from "node:assert";
import { LRUCache } from "./solution.ts";

test("stores and retrieves values", () => {
  const c = new LRUCache<string, number>(2);
  c.put("a", 1);
  c.put("b", 2);
  assert.equal(c.get("a"), 1);
  assert.equal(c.get("b"), 2);
  assert.equal(c.size, 2);
});

test("missing key returns undefined", () => {
  const c = new LRUCache<string, number>(2);
  assert.equal(c.get("nope"), undefined);
});

test("evicts least-recently-used on overflow", () => {
  const c = new LRUCache<string, number>(2);
  c.put("a", 1);
  c.put("b", 2);
  c.put("c", 3); // evicts "a"
  assert.equal(c.get("a"), undefined);
  assert.equal(c.get("b"), 2);
  assert.equal(c.get("c"), 3);
  assert.equal(c.size, 2);
});

test("get counts as a use and protects from eviction", () => {
  const c = new LRUCache<string, number>(2);
  c.put("a", 1);
  c.put("b", 2);
  assert.equal(c.get("a"), 1); // "a" now most-recently used
  c.put("c", 3); // evicts "b"
  assert.equal(c.get("b"), undefined);
  assert.equal(c.get("a"), 1);
  assert.equal(c.get("c"), 3);
});

test("put updates existing key and marks it used", () => {
  const c = new LRUCache<string, number>(2);
  c.put("a", 1);
  c.put("b", 2);
  c.put("a", 10); // update + use "a"
  c.put("c", 3); // evicts "b"
  assert.equal(c.get("a"), 10);
  assert.equal(c.get("b"), undefined);
  assert.equal(c.get("c"), 3);
  assert.equal(c.size, 2);
});

test("capacity of 1 keeps only the newest", () => {
  const c = new LRUCache<number, string>(1);
  c.put(1, "one");
  c.put(2, "two");
  assert.equal(c.get(1), undefined);
  assert.equal(c.get(2), "two");
  assert.equal(c.size, 1);
});

test("invalid capacity throws RangeError", () => {
  assert.throws(() => new LRUCache<string, number>(0), RangeError);
});

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

To solve this problem, we need to implement a generic Least Recently Used (LRU) cache in TypeScript. The cache should be able to store key-value pairs and manage them based on their usage frequency, ensuring that the least recently used items are evicted when the cache reaches its capacity.

### Approach
The LRU cache is implemented using a combination of a Map and an array to track the order of key accesses. Here's a detailed breakdown of the approach:

1. **Data Structures**:
   - **Map**: Used to store the key-value pairs for efficient lookups and updates.
   - **Array**: Used to maintain the order of key accesses, where the most recently used key is at the end of the array.

2. **Constructor**:
   - Initializes the cache with a given capacity.
   - Throws a `RangeError` if the capacity is less than 1.

3. **Get Method**:
   - Checks if the key exists in the Map.
   - If it exists, moves the key to the end of the array to mark it as the most recently used.
   - Returns the value if the key exists, otherwise returns `undefined`.

4. **Put Method**:
   - Updates the value of an existing key or adds a new key-value pair.
   - Moves the key to the end of the array if it already exists or adds it to the end if it is new.
   - If adding a new key exceeds the cache capacity, the least recently used key (first element of the array) is evicted.

5. **Size Property**:
   - Returns the current number of entries in the cache, which is the size of the Map.

### Solution Code
```typescript
export class LRUCache<K, V> {
  private map = new Map<K, V>();
  private order: K[] = [];
  private capacity: number;

  constructor(capacity: number) {
    if (capacity < 1) {
      throw new RangeError("Capacity must be at least 1");
    }
    this.capacity = capacity;
  }

  get(key: K): V | undefined {
    if (!this.map.has(key)) {
      return undefined;
    }
    const index = this.order.indexOf(key);
    if (index !== -1) {
      this.order.splice(index, 1);
    }
    this.order.push(key);
    return this.map.get(key);
  }

  put(key: K, value: V): void {
    if (this.map.has(key)) {
      this.map.set(key, value);
      const index = this.order.indexOf(key);
      if (index !== -1) {
        this.order.splice(index, 1);
      }
      this.order.push(key);
    } else {
      this.map.set(key, value);
      this.order.push(key);
      if (this.map.size > this.capacity) {
        const evictedKey = this.order.shift();
        if (evictedKey) {
          this.map.delete(evictedKey);
        }
      }
    }
  }

  get size(): number {
    return this.map.size;
  }
}
```

### Explanation
- **Map Usage**: The Map is used to store the key-value pairs because it provides O(1) average time complexity for both insertions and lookups.
- **Array for Order Tracking**: The array keeps track of the order in which keys are accessed. Each time a key is accessed (either via `get` or `put`), it is moved to the end of the array to mark it as the most recently used.
- **Eviction Strategy**: When the cache is full and a new key is added, the least recently used key (the first element of the array) is evicted to make space for the new key.

This approach ensures that the cache efficiently manages its entries based on usage frequency, adhering to the LRU eviction policy.

Okay, I need to implement a generic LRU cache in TypeScript. The class is called LRUCache and it should have methods get, put, and a size property. Let me think about how to structure this.

First, the constructor takes a capacity. I should check that capacity is at least 1; otherwise, throw a RangeError. So in the constructor, I'll add that check.

Next, the data structure. An LRU cache typically uses an ordered data structure to keep track of the usage order. I remember that in JavaScript, a Map can be used, but for tracking the order, maybe a combination of a Map and a Doubly Linked List would work. Alternatively, I can use a Map to store the key-value pairs and another structure to track the order of usage.

Wait, another approach is to use a Map where each entry also keeps track of the order. But maintaining the order might be tricky. Alternatively, I can have a list that represents the order of usage, where the most recently used is at the end.

Hmm, perhaps using a Map to store the key-value pairs and an array to keep track of the order. Every time a key is accessed (either via get or put), it's moved to the end of the array. When the cache is full and a new key is added, the first element of the array is evicted.

But wait, that might not be efficient because moving elements in an array can be O(n) time. For a small capacity, it's manageable, but for larger capacities, it's not ideal. Oh, but in TypeScript, the problem might not have performance constraints beyond correctness, so maybe it's acceptable.

Alternatively, using a Doubly Linked List would allow O(1) moves, but implementing that from scratch might be more complex. Since I'm writing in TypeScript, perhaps using a Map to track the order as well.

Wait, another idea: each node in the linked list can have a key, value, and pointers to previous and next nodes. But that's a lot of code to write.

Alternatively, perhaps using a Map to track the order. For each key, we can store the time it was last used. Then, when we need to evict, we find the key with the smallest last used time.

But that approach would require, on each put, to check all keys to find the least recently used, which is O(n) time. For small n, it's acceptable, but for large n, it's not efficient. However, given that the problem doesn't specify performance constraints, maybe it's acceptable.

Wait, but the problem expects the solution to be correct, not necessarily the most efficient. So perhaps the array approach is manageable.

Let me outline the steps:

1. The cache will have a Map (or a plain object) to store the key-value pairs.
2. An array will keep track of the order of usage. The first element is the least recently used, the last is the most recently used.
3. When a key is accessed (get or put), it's moved to the end of the array.
4. When putting a new key and the cache is full, remove the first element of the array and delete it from the Map.

Wait, but the array could have duplicates. For example, if a key is accessed multiple times, it's moved to the end each time. So the array will have the order of most recent to least recent, but each key can appear multiple times. So when evicting, we need to make sure that we remove the first occurrence of the key in the array.

Wait, no. Because when a key is accessed, it's moved to the end. So the array will have the order of usage, with the most recent at the end. So when the cache is full, the first element is the least recently used.

So, for example, in the sample:

c.put("a", 1);
c.put("b", 2);
c.get("a"); // moves a to end
c.put("c", 3); // evicts b, adds c to end.

So the array after each step:

After put a: ["a"]
After put b: ["a", "b"]
After get a: ["b", "a"]
After put c: evict "b", add "c" → ["a", "c"]

Wait, no. Because when you put "c", the array is ["b", "a"], and adding "c" would require moving it to the end, making ["b", "a", "c"], but since capacity is 2, we need to evict the first element, which is "b".

So the array after evicting becomes ["a", "c"].

Wait, no. Because when you put "c", the array is ["b", "a"], and you add "c" to the end, making it ["b", "a", "c"], but since capacity is 2, you need to remove the first element, which is "b". So the array becomes ["a", "c"].

So the array always contains the order of usage, with the first element being the least recently used.

So, the plan is:

- Use a Map to store the key-value pairs.
- Use an array to track the order of keys, where the first element is the least recently used.
- When get(key) is called:
   - If the key is not in the Map, return undefined.
   - If it is, move the key to the end of the array (if it's not already there) and return the value.
- When put(key, value) is called:
   - If the key is already in the Map, update its value and move it to the end of the array.
   - If it's not in the Map:
      - Add it to the Map.
      - Add it to the end of the array.
      - If the size exceeds capacity, remove the first element of the array, remove it from the Map, and continue.

Wait, but the array could have multiple entries for the same key. For example, if a key is accessed multiple times, each time it's moved to the end. So the array may have the same key appearing multiple times, but only the last occurrence is relevant.

Wait, no. Because each time a key is accessed, it's moved to the end. So the array will have the keys in the order of their last access, with the most recent at the end. So when a key is accessed again, it's moved to the end, which effectively updates its position.

So, the array can have multiple entries for the same key, but only the last occurrence is the current position. So when evicting, the first element is the least recently used, regardless of duplicates.

Wait, but if a key is accessed multiple times, it's moved to the end each time. So the array will have the key appearing multiple times, but the last occurrence is the current position.

So, for example:

After put a, array is [a].
After get a, array is [a] (no change, since it's already at the end).
After put a again, array is [a] (no change).

So, when evicting, the first element is the
…[8178 chars elided]…
put("b", 2); // map: {a:1, b:2}, order: ["a", "b"]
c.get("a"); // returns 1, order becomes ["b", "a"]
c.put("c", 3); // map size is 3, which is >2. Evict "b". map now {a:1, c:3}, order: ["a", "c"]
c.get("b"); // undefined
c.get("a"); // returns 1, order becomes ["c", "a"]
c.get("c"); // returns 3, order becomes ["a", "c"]
c.size; // 2

Which matches the example.

Another test case: when the same key is accessed multiple times.

c.put("a", 1);
c.get("a"); // moves to end, order remains ["a"]
c.put("a", 2); // updates value, moves to end → same as before.

Yes.

Another test: when the cache is full and a new key is added.

c = new LRUCache(2);
c.put("a", 1);
c.put("b", 2);
c.put("c", 3); // evicts "a", order becomes ["b", "c"]

Yes.

Now, what about when the key is not a string? For example, numbers or other types. Since it's generic, it should handle any K.

Another consideration: the order array could have multiple entries for the same key if it's accessed multiple times, but the code correctly moves it to the end each time.

Wait, no. Because each time get is called, it finds the index and removes it, then adds it to the end. So the array will have the key only once, at the end.

Wait, no. Because if the key is already in the array, it's removed and added again. So the array will have the key only once, at the end.

Wait, no. Let's see:

Suppose the order is ["a", "b", "c"], and we call get("b"). The index is 1. We remove it, then add it to the end. So the order becomes ["a", "c", "b"].

So the array is always in the order of last access, with the most recent at the end.

Yes.

So the code should handle all cases correctly.

Now, implementing this in TypeScript.

Wait, but in TypeScript, the Map and array are typed, so the code should be correct.

Potential issues:

- The order array could have multiple entries for the same key, but the code correctly moves it to the end each time, so it's handled.

- When evicting, the first element is the least recently used, which is correct.

So, the code should be correct.