import java.util.HashMap;
import java.util.Map;

/**
 * @Author:田宇寒.
 * @Date:Created in 9:49 2021年6月7日
 * @Description:LRU缓存机制
 * @ModifiedBy:
 * @Version: 1.0
 */
public class code146 {
 private Map<Integer, Node> map;
 private int capacity;
 private int size;
 private Node head;
 private Node tail;

 class Node {
 Node pre;
 Node next;
 int key;
 int value;

 Node() {}

 Node(int key, int value) {
 this.key = key;
 this.value = value;
 }
 }

 public code146(int capacity) {
 this.capacity = capacity;
 this.size = 0;
 this.map = new HashMap<>(capacity);
 this.head = new Node();
 this.tail = new Node();
 this.head.next = tail;
 this.tail.pre = head;
 }

 public int get(int key) {
 if (!map.containsKey(key)) {
 return -1;
 } else {
 Node node = map.get(key);
 refreshNode(node);
 return node.value;
 }
 }

 public void put(int key, int value) {
 //如果已经存在更新键值
 if (map.containsKey(key)) {
 Node node = map.get(key);
 node.value = value;
 refreshNode(node);
 return;
 }
 //如果容量等于上限了移除头指针的下一个节点,否则添加到tail节点前
 synchronized (this) {
 if (size == capacity) {
 map.remove(deleteNode());
 size--;
 }
 Node node = new Node(key, value);
 map.put(key, node);
 size++;
 addNode(node);
 }
 }

 private int deleteNode() {
 Node node = head.next;
 node.next.pre = head;
 node.pre = null;
 head.next = node.next;
 return node.key;
 }

 private void addNode(Node node) {
 Node preNode = tail.pre;
 preNode.next = node;
 node.pre = preNode;
 node.next = tail;
 tail.pre = node;
 }

 private void refreshNode(Node node) {
 if (node.next == tail) {
 return;
 }
 Node preNode = node.pre;
 Node nextNode = node.next;
 Node tailPreNode = tail.pre;

 preNode.next = nextNode;
 nextNode.pre = preNode;

 tailPreNode.next = node;
 tail.pre = node;

 node.pre = tailPreNode;
 node.next = tail;
 }
}