LRU Cache

cache.py

class Node:
    def __init__(self, key=None, value=None, prev=None, next=None):
        self.key = key
        self.value = value
        self.prev = prev
        self.next = next

    def leave(self):
        prev, next = self.prev, self.next
        assert isinstance(prev, Node)
        assert isinstance(next, Node)
        prev.next = next
        next.prev = prev
        self.prev = self.next = None

    def insert_before(self, target):
        assert isinstance(target, Node)
        assert isinstance(target.prev, Node)
        prev = target.prev
        prev.next = target.prev = self
        self.prev = prev
        self.next = target

    def __repr__(self):
        return f'<Node {self.key}-{self.value}>'


class Cache:
    def __init__(self, maxsize=128):
        assert maxsize > 0
        self.maxsize = maxsize
        self.cache = {}
        self.root = Node()
        self.root.next = self.root.prev = self.root

    def set(self, key, value):
        if key in self.cache:
            target: Node = self.cache[key]
            target.value = value
            if target.next is not self.root:
                target.leave()
                target.insert_before(self.root)
        elif len(self.cache) < self.maxsize:
            new_node = Node(key, value)
            new_node.insert_before(self.root)
            self.cache[key] = new_node
        else:
            # 把root指向最旧的节点
            old_root: Node = self.root
            self.root = old_root.next
            del self.cache[self.root.key]
            # 原root变成最新缓存节点
            old_root.key = key
            old_root.value = value
            self.cache[key] = old_root

    def get(self, key):
        if key not in self.cache:
            return None
        target: Node = self.cache[key]
        if target.next is not self.root:
            target.leave()
            target.insert_before(self.root)
        return target.value

    def remove(self, key):
        target = self.cache.get(key)
        if target is not None:
            target.leave()
            del self.cache[key]