lru.py

class LRUCache:
    """
    https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)
    """

    def __init__(self, maxsize: int = 16) -> None:
        self.cache = {}
        self.maxsize = maxsize

    def put(self, key: Hashable, value: Any) -> None:
        """Time Complexity: O(1)"""
        if key in self.cache:
            self.cache.pop(key)
        self.cache[key] = value
        if len(self.cache) > self.maxsize:
            first_key = next(iter(self.cache))
            self.cache.pop(first_key)

    def get(self, key: Hashable) -> Any:
        """Time Complexity: O(1)"""
        current_element = self.cache.get(key)
        if current_element is not None:
            self.cache.pop(key)
            self.cache[key] = current_element
            return current_element
        raise KeyError("No such key in this cache")

    def exists(self, key: Hashable) -> bool:
        """Time Complexity: O(1)"""
        return key in self.cache

    def size(self) -> int:
        """Time Complexity: O(1)"""
        return len(self.cache)

    def __repr__(self):
        return f"LRUCache({self.cache})"