# Reference patch — 01-least-frequently-used

The answer key for how the reference absorbs this change, and the thing that makes `budget.json`
reproducible. **Never shipped to the candidate.**

1. **Add** `LfuEvictionPolicy.java` (in this directory) to `reference/src/`. New file, so
   `measureChange` charges nothing for it. It implements the same package-private
   `EvictionPolicy` interface `LruEvictionPolicy` already implements, and nothing else in
   `reference/src` needs to know it exists.
2. **Add** `contract-delta/Entry.java` (the full revised entry point, with `createLfu` added
   beside the existing two factories) to the candidate's contract. Not counted in the measured
   diff, the same convention every other curveball in this corpus that extends the contract
   follows: a contract extension is free, and only the reference's own absorption of it is
   charged.

That is the entire change. **No file that existed before this curveball was opened.**
`reference/src/LruCache.java` is untouched — `Entry.createLfu` calls the same package-private
`LruCache(int, EvictionPolicy)` constructor `Entry.create(int)` already calls internally, just
with a different policy.

Measured: `reference_diff = 0` (0 added, 0 removed, 0 files touched, 1 new file), so
`diff_budget = max(3, 0 + min(ceil(0/2), 6)) = 3`.

Both the curveball suite (3 tests) and the base suite (16 tests) are green after the patch, and
so is the full concurrency suite — nothing about `put`, `get`, or the locking in `LruCache`
changed, so there was nothing new for the stress suite to re-prove.

## Why this one is the corpus's honest test of the policy seam

The task this problem was authored against says it directly: *"the LFU one should be near-zero
if the policy seam is real — that is the test of whether it is."* `LruCache` was written from the
start with eviction as a call to an injected `EvictionPolicy` it never inspects, precisely so that
"a different rule" is a new implementation of three methods, not a rewrite of `LruCache` itself.
A `reference_diff` of zero here is not a coincidence produced by a curveball chosen to flatter the
design — it is what the design was built to make true, and this curveball is the one that checks
the claim rather than just asserting it.

## A real bug this curveball's own tests found, and fixed in the base reference — not here

Writing this curveball's tests caught a genuine ordering bug in `LruCache.put`, not in
`LfuEvictionPolicy`: the original code called `policy.onInsert(key)` for a brand-new key **before**
checking whether the cache was over capacity and asking `policy.victim()` for a name. For
`LruEvictionPolicy` this is harmless, because a just-inserted key is, by construction, the most
recently touched one and can never be the least-recently-touched victim. For a frequency-based
policy it is not harmless at all: a brand-new key starts at a use count of one, which is usually
*the lowest count in the whole cache*, so asking for a victim after registering it let the cache
nominate the key it had just been asked to make room for, evicting the wrong entry (observed:
`evictsLeastFrequentlyUsedNotLeastRecentlyUsed` evicted the just-inserted key `"c"` instead of
`"b"`). This is a property of the general contract between `LruCache` and any `EvictionPolicy`,
not a fact about frequency specifically, so the fix — choose the victim from the pre-existing
entries *before* registering the new key, never after — was made in `reference/src/LruCache.java`
directly, ahead of this curveball's own baseline measurement, exactly as the corpus's rule for a
large `reference_diff` prescribes: fix the reference, not the budget. It is recorded here, rather
than folded silently into the base reference's own history, because it is the reason this
curveball exists to catch: a candidate who wires up least-frequently-used eviction without this
same care will fail `evictsLeastFrequentlyUsedNotLeastRecentlyUsed` on exactly this symptom.
