from __future__ import annotations

from collections import OrderedDict
from typing import Generic, TypeVar
import unittest

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


class LRUCache(Generic[K, V]):
    """A small LRU cache backed by OrderedDict."""

    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 | None:
        """Return a value and mark it as recently used."""
        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 clear(self) -> None:
        self._items.clear()

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

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

    def __repr__(self) -> str:
        return f"{type(self).__name__}(capacity={self.capacity}, items={dict(self._items)!r})"


class TestLRUCache(unittest.TestCase):
    def test_evicts_least_recently_used_item(self) -> None:
        cache: LRUCache[str, int] = LRUCache(capacity=2)

        cache.put("a", 1)
        cache.put("b", 2)
        cache.put("c", 3)

        self.assertIsNone(cache.get("a"))
        self.assertEqual(cache.get("b"), 2)
        self.assertEqual(cache.get("c"), 3)

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

        cache.put("a", 1)
        cache.put("b", 2)
        self.assertEqual(cache.get("a"), 1)
        cache.put("c", 3)

        self.assertEqual(cache.get("a"), 1)
        self.assertIsNone(cache.get("b"))
        self.assertEqual(cache.get("c"), 3)


if __name__ == "__main__":
    unittest.main()