Radix cache for integer sequences with LRU eviction

Implement RadixCache, a cache of integer sequences (for example, token IDs of model prompts) stored in a radix tree: a trie whose edges hold runs of integers instead of single integers. Sequences that share a prefix must share the nodes for that prefix, and a long unshared tail must be stored on a single edge, not one node per integer.

Implement:

• insert(seq: list[int]) -> int: store seq. Return how many of its leading integers were already in the cache before this call.
• match_prefix(seq: list[int]) -> int: return the length of the longest prefix of seq that is stored in the cache (as part of any stored sequence).
• search(seq: list[int]) -> bool: return true only if seq itself was inserted, not merely a prefix of something inserted.
• delete(seq: list[int]) -> bool: remove seq if it was inserted. Keep the tree compressed afterward.
• evict(num_ints: int) -> int: free at least num_ints cached integers by removing whole leaves, least recently used first (a sequence counts as used when it is inserted or matched). Return how many integers were freed.

Also keep size: the total number of integers stored on all edges.

Constraints: up to 10^5 sequences, each up to 10^4 integers. Every operation except evict should run in time linear in the length of its argument.

Example 1

c = RadixCache()
c.insert([5, 6, 7, 8])      -> 0
c.insert([5, 6, 9])         -> 2    # edge (5,6,7,8) splits into (5,6) -> (7,8), (9)
c.size                      -> 5
c.match_prefix([5, 6, 7, 1]) -> 3
c.search([5, 6])            -> False

Example 2

c = RadixCache()
c.insert([1, 2, 3]); c.insert([4, 5]); c.insert([1, 2, 6])
c.match_prefix([1, 2, 3])   # touch it
c.evict(1)                  -> 2    # leaf (4,5) is the least recently used
c.search([4, 5])            -> False
c.search([1, 2, 6])         -> True