from collections import OrderedDict
from typing import Generic, TypeVar

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


class LRUCache(Generic[K, V]):
    """A fixed-capacity least-recently-used cache."""

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

    def get(self, key: K) -> V:
        value = self._items.pop(key)  # Raises KeyError when absent.
        self._items[key] = value
        return value

    def put(self, key: K, value: V) -> None:
        if key in self._items:
            self._items.pop(key)
        self._items[key] = value

        # Evict the least recently used item.
        if len(self._items) > self.capacity:
            self._items.popitem(last=False)

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

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


def test_capacity_eviction() -> None:
    cache = LRUCache[str, int](2)
    cache.put("a", 1)
    cache.put("b", 2)
    cache.put("c", 3)

    assert "a" not in cache
    assert cache.get("b") == 2
    assert cache.get("c") == 3


def test_access_updates_recency() -> None:
    cache = LRUCache[str, int](2)
    cache.put("a", 1)
    cache.put("b", 2)
    assert cache.get("a") == 1

    cache.put("c", 3)
    assert "a" in cache
    assert "b" not in cache


def main() -> None:
    test_capacity_eviction()
    test_access_updates_recency()
    print("All tests passed.")


if __name__ == "__main__":
    main()