LFU — Least Frequently Used

// O(1) LFU sketch — frequency buckets keyed by count.
// Each bucket is an ordered set so we can break ties by recency.
class LFU<K, V> {
  private values = new Map<K, V>();
  private freq = new Map<K, number>();
  private buckets = new Map<number, Set<K>>(); // freq -> keys at that freq
  private minFreq = 0;

  constructor(private capacity: number) {}

  get(key: K): V | undefined {
    if (!this.values.has(key)) return undefined;
    this.touch(key);
    return this.values.get(key);
  }

  set(key: K, value: V): void {
    if (this.capacity === 0) return;
    if (this.values.has(key)) {
      this.values.set(key, value);
      this.touch(key);
      return;
    }
    if (this.values.size >= this.capacity) this.evict();
    this.values.set(key, value);
    this.freq.set(key, 1);
    this.bucket(1).add(key);
    this.minFreq = 1;
  }

  private touch(key: K): void {
    const f = this.freq.get(key)!;
    this.bucket(f).delete(key);
    if (this.bucket(f).size === 0 && f === this.minFreq) this.minFreq++;
    this.freq.set(key, f + 1);
    this.bucket(f + 1).add(key);
  }

  private evict(): void {
    const victims = this.bucket(this.minFreq);
    const victim = victims.values().next().value!; // oldest at min freq
    victims.delete(victim);
    this.values.delete(victim);
    this.freq.delete(victim);
  }

  private bucket(f: number): Set<K> {
    if (!this.buckets.has(f)) this.buckets.set(f, new Set());
    return this.buckets.get(f)!;
  }
}