class Node:
def __init__(self, key, value, left=None, right=None):
self.key = key
self.value = value
self.left = left
self.right = right
class Block:
def __init__(self, cnt, left=None, right=None, head=None, tail=None):
self.cnt = cnt
self.left = left
self.right = right
self.head = Node(-1, -1) # least recent
self.tail = Node(-1, -1)
self.head.right = self.tail
self.tail.left = self.head
def add(self, node):
left = self.tail.left
left.right = node
node.left = left
node.right = self.tail
self.tail.left = node
def remove(self, node):
if node.left:
node.left.right = node.right
if node.right:
node.right.left = node.left
def is_empty(self):
return self.head.right == self.tail
class LFUCache:
def __init__(self, capacity: int):
self.c = capacity
self.head = Block(0)
self.tail = Block(float("inf"))
self.head.right = self.tail
self.tail.left = self.head
self.node = {} # key -> node
self.block = {} # key -> block
def get_next_block(self, block):
if block.right.cnt == block.cnt + 1:
return block.right
cnt = block.cnt + 1
new_block = Block(cnt)
right = block.right
block.right = new_block
new_block.left = block
new_block.right = right
right.left = new_block
return new_block
def remove(self, block):
block.left.right = block.right
block.right.left = block.left
def get(self, key: int) -> int:
if key not in self.block:
return -1
block = self.block[key]
node = self.node[key]
block.remove(node)
next_block = self.get_next_block(block)
next_block.add(node)
if block.is_empty():
self.remove(block)
self.block[key] = next_block
# self.print(self.head)
return node.value
def print(self, block):
while block:
row = []
node = block.head
while node:
row.append(str(node.key))
node = node.right
print(str(block.cnt) + " " + ",".join(row))
block = block.right
print()
def put(self, key: int, value: int) -> None:
if key in self.block:
node = self.node[key]
node.value = value
self.get(key)
return
if len(self.block) == self.c:
head_block = self.head.right
head_node = head_block.head.right
head_key = head_node.key
head_block.remove(head_node)
if head_block.is_empty():
self.remove(head_block)
del self.node[head_key]
del self.block[head_key]
node = Node(key, value)
next_block = self.get_next_block(self.head)
next_block.add(node)
self.block[key] = next_block
self.node[key] = node
# self.print(self.head)
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)