"""Simple LRU cache implementation backed by an ordered dict.

The LRU policy evicts the least-recently-used entry whenever an
insertion would exceed the configured capacity. Lookups, insertions,
and evictions all run in amortized O(1) time because OrderedDict
maintains insertion order and supports cheap move-to-end operations.
"""

from __future__ import annotations

from collections import OrderedDict
from typing import Generic, TypeVar

K = TypeVar("K")
V = TypeVar("V")


class LRUCache(Generic[K, V]):
    """Bounded mapping with least-recently-used eviction."""

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self._store: OrderedDict[K, V] = OrderedDict()

    def __len__(self) -> int:
        return len(self._store)

    def __contains__(self, key: object) -> bool:
        return key in self._store

    def get(self, key: K, default: V | None = None) -> V | None:
        if key not in self._store:
            return default
        self._store.move_to_end(key)
        return self._store[key]

    def put(self, key: K, value: V) -> None:
        if key in self._store:
            self._store.move_to_end(key)
            self._store[key] = value
            return
        self._store[key] = value
        if len(self._store) > self.capacity:
            self._store.popitem(last=False)

    def clear(self) -> None:
        self._store.clear()


def demo() -> None:
    cache: LRUCache[str, int] = LRUCache(capacity=3)
    cache.put("a", 1)
    cache.put("b", 2)
    cache.put("c", 3)
    assert cache.get("a") == 1
    cache.put("d", 4)  # evicts "b" because "a" was just touched
    assert "b" not in cache
    assert cache.get("c") == 3
    print("ok", len(cache))


if __name__ == "__main__":
    demo()
