"""Reference solution — LRU Cache to Size-Aware TTL Cache.

DO NOT READ BEFORE YOU HAVE RUN THE PROBLEM UNDER THE CLOCK.
Teaching text: ../../../WARMUP.md § Chapter 3.

Two structures, wired together. A dict answers "is this key here" in O(1) and
knows nothing about order. A doubly-linked list answers "what was used longest
ago" in O(1) and cannot find a key. So the dict maps key -> NODE, and the node
is a list element -- "intrusive", meaning the cache entry IS the list node.

The list must be DOUBLY linked: eviction and promotion both need to unlink a
node you already have a pointer to, and a singly-linked node does not know its
predecessor, so unlinking would be an O(n) scan and the whole design collapses.

Sentinel head and tail nodes remove every edge case. The invariant becomes
"every real node has non-None prev and next", so insert and unlink are
branch-free and an empty list works through the same code path as a full one.
"""

from __future__ import annotations

import threading
import time

_MISS = object()


class _Node:
    __slots__ = ("key", "value", "expires_at", "cost", "prev", "next")

    def __init__(self, key=None, value=None, expires_at=None, cost=1):
        self.key, self.value = key, value
        self.expires_at, self.cost = expires_at, cost
        self.prev = self.next = None


class LRUCache:
    """O(1) LRU with per-entry TTL, a byte budget, and single-flight loading."""

    def __init__(self, capacity, max_bytes=None, clock=time.monotonic, sample=8):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        if max_bytes is not None and max_bytes <= 0:
            raise ValueError("max_bytes must be positive")
        self.capacity = capacity
        self.max_bytes = max_bytes
        self._clock = clock
        self._sample = sample
        self._map = {}
        self._head, self._tail = _Node(), _Node()      # sentinels
        self._head.next, self._tail.prev = self._tail, self._head
        self.total_bytes = 0
        self._lock = threading.RLock()
        self._inflight = {}        # key -> threading.Event
        self._errors = {}          # key -> exception from the leading loader
        self.hits = self.misses = self.evictions = self.expirations = 0

    # ---- list primitives (branch-free, thanks to the sentinels) ----------
    @staticmethod
    def _unlink(node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        first = self._head.next
        node.prev, node.next = self._head, first
        self._head.next, first.prev = node, node

    def _touch(self, node):
        self._unlink(node)
        self._push_front(node)

    # ---- expiry ----------------------------------------------------------
    def _expired(self, node):
        return node.expires_at is not None and self._clock() >= node.expires_at

    def _drop(self, node):
        self._unlink(node)
        del self._map[node.key]
        self.total_bytes -= node.cost

    def _sample_expired(self):
        """Redis-style: check a bounded sample from the cold end.

        Lazy expiry alone never frees an entry that is never read again, so
        memory grows with the cold keyspace. A full sweep is O(n) and fights
        request traffic for the lock. Sampling is O(1) amortised and converges.
        """
        checked = 0
        node = self._tail.prev
        while node is not self._head and checked < self._sample:
            nxt = node.prev
            checked += 1
            if self._expired(node):
                self._drop(node)
                self.expirations += 1
            node = nxt

    # ---- core ------------------------------------------------------------
    def _get_locked(self, key):
        node = self._map.get(key)
        if node is None:
            return _MISS
        if self._expired(node):                 # lazy expiry on the read path
            self._drop(node)
            self.expirations += 1
            return _MISS
        self._touch(node)
        return node.value

    def get(self, key, default=None):
        with self._lock:
            value = self._get_locked(key)
            if value is _MISS:
                self.misses += 1
                return default
            self.hits += 1
            return value

    def _put_locked(self, key, value, ttl=None, cost=1):
        if cost <= 0:
            raise ValueError("cost must be positive")
        if self.max_bytes is not None and cost > self.max_bytes:
            # Admitting it would evict everything else for one entry. Refuse
            # rather than let a single request destroy the cache for everyone.
            raise ValueError("entry cost exceeds max_bytes")

        existing = self._map.get(key)
        if existing is not None:
            self._drop(existing)

        node = _Node(key, value, None if ttl is None else self._clock() + ttl, cost)
        self._map[key] = node
        self._push_front(node)
        self.total_bytes += cost

        self._sample_expired()

        # Evict UNTIL under both bounds. One eviction is not enough when the
        # entry just inserted is large.
        while self._map and (
            len(self._map) > self.capacity
            or (self.max_bytes is not None and self.total_bytes > self.max_bytes)
        ):
            victim = self._tail.prev
            if victim is self._head:
                break
            self._drop(victim)
            self.evictions += 1
        return node

    def put(self, key, value, ttl=None, cost=1):
        with self._lock:
            self._put_locked(key, value, ttl, cost)

    # ---- single flight ---------------------------------------------------
    def get_or_load(self, key, loader):
        """Exactly one caller runs `loader`; the rest wait for that result.

        Without this, a popular key expiring sends N concurrent misses to the
        backing store at the moment the cache was supposed to be protecting
        it. That is a cache stampede, and it is how caches take down the thing
        behind them.
        """
        while True:
            with self._lock:
                value = self._get_locked(key)
                if value is not _MISS:
                    self.hits += 1
                    return value
                self.misses += 1
                event = self._inflight.get(key)
                if event is None:
                    event = threading.Event()
                    self._inflight[key] = event
                    self._errors.pop(key, None)
                    leader = True
                else:
                    leader = False

            if leader:
                try:
                    loaded = loader(key)
                except BaseException as exc:
                    with self._lock:
                        self._errors[key] = exc
                        self._inflight.pop(key, None)
                    event.set()
                    raise
                with self._lock:
                    self._put_locked(key, loaded)
                    self._inflight.pop(key, None)
                event.set()
                return loaded

            event.wait()
            with self._lock:
                error = self._errors.get(key)
                if error is not None:
                    raise error
                value = self._get_locked(key)
                if value is not _MISS:
                    return value
            # The leader's value was evicted before we woke. Try again.

    # ---- introspection ---------------------------------------------------
    def __len__(self):
        with self._lock:
            return len(self._map)

    def __contains__(self, key):
        with self._lock:
            return self._get_locked(key) is not _MISS

    def keys_mru_first(self):
        with self._lock:
            out, node = [], self._head.next
            while node is not self._tail:
                out.append(node.key)
                node = node.next
            return out

    def stats(self):
        with self._lock:
            total = self.hits + self.misses
            return {
                "size": len(self._map), "bytes": self.total_bytes,
                "hits": self.hits, "misses": self.misses,
                "hit_rate": self.hits / total if total else 0.0,
                "evictions": self.evictions, "expirations": self.expirations,
            }