2Q — Two Queue

// 2Q simplified: A1in (FIFO), Am (LRU), A1out (ghost set).
class TwoQ<K, V> {
  private a1in = new Map<K, V>();   // FIFO probation
  private am = new Map<K, V>();      // LRU main
  private a1out = new Set<K>();      // ghost
  constructor(
    private kIn: number,    // capacity of A1in
    private kOut: number,   // capacity of A1out (ghost)
    private kMain: number,  // capacity of Am
  ) {}

  get(key: K): V | undefined {
    if (this.am.has(key)) {
      const v = this.am.get(key)!;
      this.am.delete(key); this.am.set(key, v); // touch (LRU)
      return v;
    }
    if (this.a1in.has(key)) {
      return this.a1in.get(key)!; // do NOT promote on first re-hit
    }
    return undefined;
  }

  set(key: K, value: V): void {
    if (this.am.has(key) || this.a1in.has(key)) return; // already cached
    if (this.a1out.has(key)) {
      // Ghost hit: promote straight to Am
      this.a1out.delete(key);
      this.evictMainIfNeeded();
      this.am.set(key, value);
      return;
    }
    // Brand-new key -> A1in
    if (this.a1in.size >= this.kIn) {
      const oldest = this.a1in.keys().next().value!;
      this.a1in.delete(oldest);
      this.a1out.add(oldest);
      if (this.a1out.size > this.kOut) {
        const ghostOldest = this.a1out.values().next().value!;
        this.a1out.delete(ghostOldest);
      }
    }
    this.a1in.set(key, value);
  }

  private evictMainIfNeeded(): void {
    if (this.am.size >= this.kMain) {
      const oldest = this.am.keys().next().value!;
      this.am.delete(oldest);
    }
  }
}