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


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {}
        # 新建两个节点 head 和 tail
        self.head = ListNode()
        self.tail = ListNode()
        # 初始化链表为 head <-> tail
        self.head.next = self.tail
        self.tail.prev = self.head

    # 因为get与put操作都可能需要将双向链表中的某个节点移到末尾，所以定义一个方法
    def move_node_to_tail(self, key):
            # 先将哈希表key指向的节点拎出来，为了简洁起名node
            #      hashmap[key]                               hashmap[key]
            #           |                                          |
            #           V              -->                         V
            # prev <-> node <-> next         pre <-> next   ...   node
            node = self.hashmap[key]
            node.prev.next = node.next
            node.next.prev = node.prev
            # 之后将node插入到尾节点前
            #                 hashmap[key]                 hashmap[key]
            #                      |                            |
            #                      V        -->                 V
            # prev <-> tail  ...  node                prev <-> node <-> tail
            node.prev = self.tail.prev
            node.next = self.tail
            self.tail.prev.next = node
            self.tail.prev = node

    def get(self, key: int) -> int:
        if key in self.hashmap:
            # 如果已经在链表中了久把它移到末尾（变成最新访问的）
            self.move_node_to_tail(key)
        res = self.hashmap.get(key, -1)
        if res == -1:
            return res
        else:
            return res.value

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            # 如果key本身已经在哈希表中了就不需要在链表中加入新的节点
            # 但是需要更新字典该值对应节点的value
            self.hashmap[key].value = value
            # 之后将该节点移到末尾
            self.move_node_to_tail(key)
        else:
            if len(self.hashmap) == self.capacity:
                # 去掉哈希表对应项
                self.hashmap.pop(self.head.next.key)
                # 去掉最久没有被访问过的节点，即头节点之后的节点
                self.head.next = self.head.next.next
                self.head.next.prev = self.head
            # 如果不在的话就插入到尾节点前
            new = ListNode(key, value)
            self.hashmap[key] = new
            new.prev = self.tail.prev
            new.next = self.tail
            self.tail.prev.next = new
            self.tail.prev = new
    def getall(self):
        for _ in self.hashmap:
            print(_, end='')
        print()

class LRUCacheMY():
    def __init__(self,capacity: int):
        self.capacity = capacity
        self.dict = {}
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head
    def delete(self,node):
        node.prev.next, node.next.prev = node.next, node.prev
    def insert(self,node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev,self.head.next = node,node

    def get(self,key) ->int:
        if not key  in self.dict:
            return -1
        node = self.dict[key]
        self.delete(node)
        self.insert(node)
        return node.value
    def put(self,key:int, value) ->int:
        if key in self.dict:
            node = self.dict[key]
            node.value = value
            self.delete(node)
            self.insert(node)
            return
        if len(self.dict) == self.capacity:
            node = self.tail.prev
            self.delete(node)
            del self.dict[node.key]
        node = ListNode(key,value)
        self.dict[key] = node
        self.insert(node)
    def getall(self):
        for _ in self.dict:
            print(_, end='')
        print()
if __name__ == '__main__':
    cache = LRUCacheMY(2)
    cache.put(1, 1)
    cache.getall()
    cache.put(2, 2)
    cache.getall()
    print(cache.get(1)) # returns 1
    cache.put(3, 3) # evicts key 2
    cache.getall()
    print(cache.get(2)) # returns - 1(not found)
    cache.put(4, 4) # evicts  key 1
    cache.getall()
    print(cache.get(1)) # returns - 1(not found)
    print(cache.get(3)) # returns3
    print(cache.get(4)) # returns4
