Lru

cache.py

@dataclass
class Node:
    val: int
    key: int
    next: Optional[None]
    prev: Optional[None]


class LRUCache:
    def __init__(self, capacity: int):
        self._capacity = capacity
        self._sz: int = 0
        self._usage_list_head: Node | None = None
        self._usage_list_tail: Node | None = None
        self._cache: dict[int, Node] = {}

    def get(self, key: int) -> int:
        if self._sz == 0 or key not in self._cache:
            return -1
        node = self._cache[key]
        self._move_node_to_back(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self._cache:
            self._cache[key].val = value
            self._move_node_to_back(self._cache[key])
            return

        if self._sz >= self._capacity:  # if we don't have enough space evict
            evicted, self._usage_list_head = self._usage_list_head, self._usage_list_head.next
            del self._cache[evicted.key]
            if self._usage_list_head is None:
                self._usage_list_tail = None
            self._sz -= 1

        node = Node(val=value, key=key, next=None, prev=None)
        self._cache[key] = node
        if self._usage_list_head is None:
            self._usage_list_head = node
            self._usage_list_tail = node
        else:
            self._usage_list_tail.next, node.prev = node, self._usage_list_tail
            self._usage_list_tail = node
        self._sz += 1

    def _move_node_to_back(self, node: Node) -> None:
        if node == self._usage_list_tail or self._sz == 1:
            # when node is at tail or there isn't anything else, don't do anything
            return

        if node == self._usage_list_head:  # move to end
            self._usage_list_head = node.next
            self._usage_list_tail.next, node.prev = node, self._usage_list_tail
            self._usage_list_tail = node
        else:
            node.prev.next, node.next.prev = node.next, node.prev
            self._usage_list_tail.next, node.prev = node, self._usage_list_tail
            self._usage_list_tail = node