js-03-lru-cache

# LRU cache

Implement an ES module **`solution.js`** exporting a least-recently-used cache class:

```js
export class LRUCache {
  constructor(capacity) { /* ... */ }
  get(key) { /* ... */ }
  put(key, value) { /* ... */ }
}
```

`capacity` is a positive integer — the maximum number of entries the cache holds.

- **`get(key)`** returns the stored value, or `undefined` if the key is not present. A successful
  `get` counts as a use: it marks the key as the **most recently used**.
- **`put(key, value)`** inserts or updates the entry and marks it most recently used. If adding a
  **new** key would exceed `capacity`, evict the **least recently used** entry first. Updating an
  existing key never changes the number of entries (and refreshes its recency).

"Recently used" is updated by **both** `get` and `put`. Keys may be any value usable as a `Map` key.

Example:
```js
const c = new LRUCache(2);
c.put("a", 1);
c.put("b", 2);
c.get("a");       // => 1   (now "a" is most-recently-used, "b" is least)
c.put("c", 3);    // capacity exceeded -> evicts "b"
c.get("b");       // => undefined
c.get("a");       // => 1
c.get("c");       // => 3
```

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

test("stores and retrieves a value", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  assert.equal(c.get("a"), 1);
});

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

test("evicts the least-recently-used entry at capacity", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  c.put("b", 2);
  c.put("c", 3); // exceeds capacity -> "a" (oldest) evicted
  assert.equal(c.get("a"), undefined);
  assert.equal(c.get("b"), 2);
  assert.equal(c.get("c"), 3);
});

test("get refreshes recency so a different key is evicted", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  c.put("b", 2);
  c.get("a"); // "a" now most-recently-used, "b" least
  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("updating an existing key does not grow size and refreshes recency", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  c.put("b", 2);
  c.put("a", 10); // update -> "a" most-recently-used, size stays 2
  c.put("c", 3); // evicts "b", not "a"
  assert.equal(c.get("b"), undefined);
  assert.equal(c.get("a"), 10);
  assert.equal(c.get("c"), 3);
});

test("capacity of 1 keeps only the latest entry", () => {
  const c = new LRUCache(1);
  c.put("a", 1);
  c.put("b", 2);
  assert.equal(c.get("a"), undefined);
  assert.equal(c.get("b"), 2);
});

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.

```js
export class LRUCache {
  constructor(capacity) {
    if (capacity <= 0) {
      throw new Error("Capacity must be a positive integer");
    }
    this.capacity = capacity;
    this.cache = new Map();
    this.order = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) {
      return undefined;
    }

    const value = this.cache.get(key);
    this._moveToMostRecentlyUsed(key);
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.set(key, value);
      this._moveToMostRecentlyUsed(key);
    } else {
      if (this.cache.size >= this.capacity) {
        this._evictLeastRecentlyUsed();
      }
      this.cache.set(key, value);
      this._moveToMostRecentlyUsed(key);
    }
  }

  _moveToMostRecentlyUsed(key) {
    const order = this.order;
    const cache = this.cache;

    order.delete(key);
    order.set(key, true);
  }

  _evictLeastRecentlyUsed() {
    const order = this.order;
    const cache = this.cache;

    let firstKey = null;
    for (const [key] of order) {
      firstKey = key;
      break;
    }

    if (firstKey !== null) {
      order.delete(firstKey);
      cache.delete(firstKey);
    }
  }
}
```

The task is to implement an LRU (Least Recently Used) cache in JavaScript. I need to create an ES module with a class that has:
- `constructor(capacity)` - initialize with max capacity
- `get(key)` - retrieve value and mark as most recently used
- `put(key, value)` - insert/update and mark as most recently used, evict LRU if needed

The key requirements:
1. Track which keys are most recently used
2. When capacity is exceeded, evict the least recently used entry
3. Both `get` and `put` operations update recency
4. Return `undefined` if key not found in `get`

The standard approach for LRU cache is to use:
1. A Map or object to store key-value pairs
2. A doubly-linked list to track access order (most recently used at one end, least recently used at the other)

However, in JavaScript, we can simplify this by using:
1. A Map to store key-value pairs
2. A separate Map or object to track the order of keys (insertion order)

Actually, the cleanest approach in JavaScript is to use:
1. A Map for key-value storage
2. A separate Map to track the order (or use the Map's iteration order)

But since we need to efficiently move keys to the "most recently used" position, we need to track the order explicitly.

The most efficient implementation uses:
1. A Map for O(1) key-value lookups
2. A doubly-linked list for O(1) move-to-front operations

However, implementing a doubly-linked list in JavaScript is more complex. A simpler approach:

Option 1: Use a Map and track order with another Map
- Store key-value in a Map
- Store access order in another Map (or use the Map's insertion order)
- When accessing, move key to end of order
- When evicting, remove from beginning of order

Option 2: Use a Map and track order with an array
- Store key-value in a Map
- Store order in an array
- When accessing, remove from array and add to end
- When evicting, remove from beginning

Option 3: Use a Map and track order with a separate Map for order
- Store key-value in a Map
- Store order in another Map (key -> index in order array)
- When accessing, update index and move to end
- When evicting, remove from beginning

Actually, the simplest and most efficient approach in JavaScript is:
1. Use a Map for key-value storage
2. Use a separate Map to track the order of keys (most recently used at the end)
3. When accessing a key, move it to the end of the order Map
4. When evicting, remove from the beginning of the order Map

Wait, Maps in JavaScript maintain insertion order, but we need to be able to move keys around. 

I'll focus on creating a robust implementation that handles key movement efficiently. The core challenge is maintaining the LRU order while allowing quick access and updates. I'll need to carefully manage how keys are tracked and moved to ensure optimal cache performance.

The implementation will require tracking key access order, managing capacity limits, and providing fast retrieval and insertion methods. Careful attention to edge cases like empty cache, full cache, and key updates will be crucial.