from __future__ import annotations

from collections import OrderedDict
from typing import Generic, Iterable, Iterator, Optional, TypeVar

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


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

    def __init__(self, capacity: int, items: Optional[Iterable[tuple[K, V]]] = None) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")

        self.capacity = capacity
        self._data: OrderedDict[K, V] = OrderedDict()

        if items is not None:
            for key, value in items:
                self.put(key, value)

    def get(self, key: K) -> Optional[V]:
        """Return a cached value and mark it as recently used."""
        if key not in self._data:
            return None

        value = self._data.pop(key)
        self._data[key] = value
        return value

    def put(self, key: K, value: V) -> None:
        """Insert or update a value, evicting the least-recently-used item if full."""
        if key in self._data:
            self._data.pop(key)

        self._data[key] = value

        if len(self._data) > self.capacity:
            self._data.popitem(last=False)

    def remove(self, key: K) -> bool:
        """Remove a key if it exists."""
        if key not in self._data:
            return False

        del self._data[key]
        return True

    def items(self) -> list[tuple[K, V]]:
        """Return items from least recently used to most recently used."""
        return list(self._data.items())

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

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

    def __iter__(self) -> Iterator[K]:
        return iter(self._data)


def _run_tests() -> None:
    cache: LRUCache[str, int] = LRUCache(2)

    cache.put("a", 1)
    cache.put("b", 2)
    assert cache.get("a") == 1
    cache.put("c", 3)
    assert cache.get("b") is None
    assert cache.items() == [("a", 1), ("c", 3)]

    cache.put("a", 10)
    assert cache.get("a") == 10
    cache.put("d", 4)
    assert "c" not in cache
    assert cache.items() == [("a", 10), ("d", 4)]

    try:
        LRUCache[str, int](0)
    except ValueError:
        pass
    else:
        raise AssertionError("expected ValueError for non-positive capacity")


if __name__ == "__main__":
    _run_tests()
    print("All tests passed.")