cache with expired

cache.ts

/**
  Design and implement a data structure for a cache,
  which has the following functions:
  - `get(key)`
    Return the value associated with the specified key
    if it exists in the cache, else return -1 .
  - `put(key, value, weight)`
    Associate with key in the cache,
    such that might be later retrieved by `get(key)`.

    Cache has a fixed capacity, and when such capacity is reached,
    key with the least score must be invalidated until the number of key s falls within cache capacity.
    The score is calculated as follows:
      `weight [ln(current_time - last_accessed_time + 1) + 1]`
*/

import { describe, afterEach, beforeEach, expect, test, vi } from "vitest";

function Cache<T>(capacity: number) {
  type Item = {
    key: string;
    weight: number;
    value: T;
    last_accessed_time: number;
  };
  let size = 0;
  const cache: Record<string, Item> = {};

  function score({ weight, last_accessed_time }: Item) {
    return weight / (Math.log(Date.now() - last_accessed_time + 1) + 1);
  }

  function get(key: string): T | undefined {
    const item = cache[key];
    if (!item) return undefined;
    item.last_accessed_time = Date.now();
    return item.value;
  }

  function put(key: string, value: T, weight: number): void {
    // when cache reach capacity, remove item which has the least score
    if (size + 1 > capacity) {
      const item = Object.values(cache).reduce((a, b) =>
        score(a) > score(b) ? b : a
      );
      delete cache[item.key];
      size -= 1;
    }

    // save
    const item = { key, weight, value, last_accessed_time: Date.now() };
    cache[key] = item;
    size += 1;
  }

  return {
    get,
    put,
  };
}

describe("test cache", () => {
  const wait = (ms: number) =>
    new Promise((resolve) => setTimeout(resolve, ms));

  beforeEach(() => {
    vi.useFakeTimers();
  });
  afterEach(() => {
    vi.restoreAllMocks();
  });

  test("test cache", () => {
    const cache = Cache(3);
    cache.put("a", 1, 10);
    cache.put("b", 2, 10);
    cache.put("c", 3, 10);
    expect(cache.get("c")).toBe(3);
    cache.put("d", 4, 10);
    expect(cache.get("a")).toBeUndefined();
  });

  test("time expired", async () => {
    const cache = Cache(2);

    cache.put("a", 1, 10000);
    wait(1000);
    await vi.advanceTimersToNextTimerAsync();

    cache.put("b", 1, 10);
    wait(1000);
    await vi.advanceTimersToNextTimerAsync();

    cache.put("c", 1, 10);
    expect(cache.get("a")).toBe(1);
    expect(cache.get("b")).toBeUndefined();
  });
});