class LFUCache {
private int capacity;
private Block L, R;
private Map<Integer, Node> key2Node;
private Map<Integer, Block> key2Block;
public LFUCache(int capacity) {
this.capacity = capacity;
this.L = new Block(0);
this.R = new Block(Integer.MAX_VALUE);
this.L.right = R;
this.R.left = L;
this.key2Node = new HashMap<>();
this.key2Block = new HashMap<>();
}
public int get(int key) {
if (!key2Block.containsKey(key)) {
return -1;
}
Block block = key2Block.get(key);
Node node = key2Node.get(key);
block.removeNode(node, key2Block);
if (block.right.cnt != block.cnt + 1) {
Block newBlock = new Block(block.cnt + 1);
block.insertRight(newBlock);
}
block.right.insertNode(node, key2Node, key2Block);
if (block.isEmpty()) {
block.left.removeRight();
}
return node.val;
}
public void put(int key, int value) {
if (!key2Block.containsKey(key)) {
if (key2Block.size() + 1 > this.capacity) {
Node remNode = L.right.L.right;
L.right.removeNode(remNode, key2Block);
if (L.right.isEmpty()) {
L.removeRight();
}
}
Node node = new Node(key, value);
if (L.right.cnt > 1) {
Block block = new Block(1);
L.insertRight(block);
}
L.right.insertNode(node, key2Node, key2Block);
} else {
Node node = key2Node.get(key);
node.val = value;
this.get(key);
}
}
private class Node {
public int key;
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int key, int val) {
this.key = key;
this.val = val;
this.left = this.right = null;
}
public void removeRight(Map<Integer, Node> key2Node) {
Node remNode = this.right;
this.right = remNode.right;
remNode.right.left = this;
key2Node.remove(remNode.key);
}
public void insertRight(Node node, Map<Integer, Node> key2Node) {
Node right = this.right;
node.right = right;
right.left = node;
this.right = node;
node.left = this;
key2Node.put(node.key, node);
}
}
private class Block {
public int cnt;
public Block left;
public Block right;
public Node L;
public Node R;
public Block() {}
public Block(int cnt) {
this.cnt = cnt;
this.L = new Node();
this.R = new Node();
this.L.right = R;
this.R.left = L;
this.left = this.right = null;
}
public void removeNode(Node node, Map<Integer, Block> key2Block) {
key2Block.remove(node.key);
node.left.removeRight(key2Node);
}
public void insertNode(Node node, Map<Integer, Node> key2Node, Map<Integer, Block> key2Block) {
key2Block.put(node.key, this);
this.R.left.insertRight(node, key2Node);
}
public void removeRight() {
Block remBlock = this.right;
this.right = remBlock.right;
remBlock.right.left = this;
}
public void insertRight(Block block) {
Block right = this.right;
block.right = right;
right.left = block;
this.right = block;
block.left = this;
}
public boolean isEmpty() {
return this.L.right == this.R && this.R.left == this.L;
}
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/