import java.util.HashMap;
import java.util.Map;
/**
* @since 2020/9/26 9:20
*/
public class LRUCache<K, V> {
static class Node<K, V> {
K key;
V value;
Node<K, V> pre;
Node<K, V> next;
public Node() {
}
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
private int size;
private int capacity;
private Node<K, V> head;
private Node<K, V> tail;
private final Map<K, Node<K, V>> cache = new HashMap<>();
public LRUCache() {
this(10);
}
public LRUCache(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("capacity <= 0");
}
this.size = 0;
this.capacity = capacity;
this.head = new Node<>();
this.tail = new Node<>();
head.next = tail;
tail.pre = head;
}
public V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
Node<K, V> node = cache.get(key);
if (node == null) {
return null;
}
moveToHead(node);
return node.value;
}
public void put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
Node<K, V> node = cache.get(key);
if (node == null) {
Node<K, V> newNode = new Node<>(key, value);
cache.put(key, newNode);
addToHead(newNode);
++size;
if (size > capacity) {
Node<K, V> tail = removeTail();
cache.remove(tail.key);
--size;
}
} else {
node.value = value;
moveToHead(node);
}
}
private void moveToHead(Node<K, V> node) {
removeNode(node);
addToHead(node);
}
private void addToHead(Node<K, V> node) {
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
private void removeNode(Node<K, V> node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private Node<K, V> removeTail() {
Node<K, V> node = tail.pre;
removeNode(node);
return node;
}
}