ARC — Adaptive Replacement Cache

// Sketch only — full ARC needs careful list manipulation.
// T1, T2: hold real values; B1, B2: hold keys only (ghosts).
class ARC<K, V> {
  private t1 = new Map<K, V>(); // recent, seen once
  private t2 = new Map<K, V>(); // frequent, seen 2+ times
  private b1 = new Set<K>();    // ghost of T1
  private b2 = new Set<K>();    // ghost of T2
  private p = 0;                // target size of T1, learned

  constructor(private c: number) {}

  get(key: K): V | undefined {
    // Hit in T1 or T2 -> promote to T2 (head)
    if (this.t1.has(key)) {
      const v = this.t1.get(key)!;
      this.t1.delete(key);
      this.t2.set(key, v);
      return v;
    }
    if (this.t2.has(key)) {
      const v = this.t2.get(key)!;
      this.t2.delete(key); this.t2.set(key, v); // touch
      return v;
    }
    return undefined;
  }

  set(key: K, value: V): void {
    // Ghost hits adapt p: B1 -> favor recency; B2 -> favor frequency
    if (this.b1.has(key)) {
      this.p = Math.min(this.c, this.p + Math.max(1, this.b2.size / this.b1.size));
      this.replace(key);
      this.b1.delete(key);
      this.t2.set(key, value);
      return;
    }
    if (this.b2.has(key)) {
      this.p = Math.max(0, this.p - Math.max(1, this.b1.size / this.b2.size));
      this.replace(key);
      this.b2.delete(key);
      this.t2.set(key, value);
      return;
    }
    // Brand new key
    if (this.t1.size + this.t2.size >= this.c) this.replace(key);
    this.t1.set(key, value);
  }

  private replace(_: K): void { /* evict from T1 or T2 based on p */ }
}