# 
# Question: Least Recently Used (LRU) Cache Implementation
# 
# Design and implement a Least Recently Used (LRU) cache. The cache should be initialized with a positive integer capacity.
# 
# Your implementation must support the following operations with $O(1)$ time complexity for both:
# 
# get(key): Retrieve the value of the item identified by key. If the key exists, return its value. If it doesn't, return $-1$. This operation also marks the key as the most recently used.
# 
# put(key, value): Insert or update an item. If the key already exists, update its value and mark it as the most recently used. If the key does not exist, insert the new item. When the cache reaches its capacity, it must evict the least recently used item before inserting the new one.
# 
# You must use a Hash Map and a Doubly Linked List for the implementation.

# Cache , limit 3

from typing import Dict

# tail.prev.next = node, node.left = tails.prev, tails.prev = Node, node.next = tail

# Head <-> Tail
# Head ->     Node  <-> Tail   , 
# Head <-> Node <-> Node1 <-> Tail, 
# node.prev.next = node.next, node.next.prev = node.prev

class Node:

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

class LRU:

    def __init__(self, capacity: int = 2):
        self.db: Dict[str, Node] = {}
        self.capacity = capacity

        self.head = Node("-1", "-1")
        self.tail = Node("-1", "-1")
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key: str):
        node = self.db[key]
        self._remove(node)
        self._add_to_tail(node)
        return node.value

    def put(self, key: str, value: str):
        if len(self.db) < self.capacity or key in self.db:
            new_node = Node(key, value)
            self._add_to_tail(new_node)
            self.db[key] = new_node
        else:
            least_recently_used_node = self.head.next
            self._remove(least_recently_used_node)
            del self.db[least_recently_used_node.key]

            new_node = Node(key, value)
            self._add_to_tail(new_node)
            self.db[key] = new_node

    def _remove(self, node: Node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_to_tail(self, node):
        self.tail.prev.next, node.prev, self.tail.prev, node.next = node, self.tail.prev, node, self.tail 

lru = LRU()
lru.put("june", "park")
lru.put("victor", "sun")
lru.get("june")
lru.put("bowen", "sun")