from collections import OrderedDict
from typing import Generic, 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) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self._items: OrderedDict[K, V] = OrderedDict()

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

        self._items.move_to_end(key)
        return self._items[key]

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

        self._items[key] = value

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

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

        del self._items[key]
        return True

    def items(self) -> Iterator[tuple[K, V]]:
        """Iterate from least recently used to most recently used."""
        return iter(self._items.items())

    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)
    assert cache.get("a") == 1

    cache.put("c", 3)

    assert "a" in cache
    assert "b" not in cache
    assert "c" in cache
    assert list(cache.items()) == [("a", 1), ("c", 3)]


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

    cache.put(1, "one")
    cache.put(2, "two")
    cache.put(1, "ONE")
    cache.put(3, "three")

    assert cache.get(1) == "ONE"
    assert cache.get(2) is None
    assert cache.get(3) == "three"


if __name__ == "__main__":
    _test_capacity_eviction()
    _test_update_refreshes_recency()