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.

```ts
export class LRUCache<K, V> {
  private capacity: number;
  private size: number;
  private map: Map<K, { value: V; node: Node }>;
  private head: Node;
  private tail: Node;

  constructor(capacity: number) {
    if (capacity < 1) {
      throw new RangeError("Capacity must be at least 1");
    }
    this.capacity = capacity;
    this.size = 0;
    this.map = new Map();
    this.head = new Node();
    this.tail = new Node();
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: K): V | undefined {
    const entry = this.map.get(key);
    if (!entry) {
      return undefined;
    }
    this.moveToHead(entry.node);
    return entry.value;
  }

  put(key: K, value: V): void {
    const entry = this.map.get(key);
    if (entry) {
      entry.value = value;
      this.moveToHead(entry.node);
      return;
    }

    const newNode = new Node();
    newNode.key = key;
    newNode.value = value;

    this.map.set(key, { value, node: newNode });
    this.addToHead(newNode);
    this.size++;

    if (this.size > this.capacity) {
      const tail = this.removeTail();
      this.map.delete(tail.key);
      this.size--;
    }
  }

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

  private moveToHead(node: Node): void {
    this.removeNode(node);
    this.addToHead(node);
  }

  private addToHead(node: Node): void {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

  private removeNode(node: Node): void {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  private removeTail(): Node {
    const tail = this.tail.prev;
    this.removeNode(tail);
    return tail;
  }
}

class Node {
  key: any;
  value: any;
  prev: Node;
  next: Node;
}
```