public class LRUCache1<K, V> extends LRUCache<K, V> {
private class Node<T, U> {
Node<T, U> previous;
Node<T, U> next;
T key;
U value;
public Node(Node<T, U> previous, Node<T, U> next, T key, U value) {
this.previous = previous;
this.next = next;
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "{" + key + "," + value + "}";
}
public String toStringWithNeighbors() {
StringBuilder sb = new StringBuilder();
if (previous != null) {
sb.append("prev ");
sb.append(previous);
sb.append(" ");
}
sb.append(this);
if (next != null) {
sb.append(" next ");
sb.append(next);
}
return sb.toString();
}
}
private Node<K, V> leastRecentlyUsed;
private Node<K, V> mostRecentlyUsed;
private final int capacity;
private int currentSize;
LRUCache1(int capacity) {
super(capacity);
this.capacity = capacity;
this.currentSize = 0;
leastRecentlyUsed = new Node<>(null, null, null, null);
mostRecentlyUsed = leastRecentlyUsed;
}
@Override
V get(K key) {
Node<K, V> tempNode = findNode(key);
if (tempNode == null) {
return null;
}
promoteNode(tempNode);
return tempNode.value;
}
@Override
void put(K key, V value) {
Node<K, V> node = findNode(key);
if (node != null) { // just update the value
node.value = value;
return;
} else {
addMostRecentlyUsed(key, value);
if (currentSize == 0) {
leastRecentlyUsed = mostRecentlyUsed;
}
}
if (currentSize == capacity) {
removeLeastRecentlyUsed();
} else {
currentSize++;
}
}
private void addMostRecentlyUsed(K key, V value) {
Node<K, V> myNode = new Node<>(mostRecentlyUsed, null, key, value);
mostRecentlyUsed.next = myNode;
mostRecentlyUsed = myNode;
}
private void removeLeastRecentlyUsed() {
leastRecentlyUsed = leastRecentlyUsed.next;
leastRecentlyUsed.previous = null;
}
private Node<K, V> findNode(K key) {
Node<K, V> tempNode = mostRecentlyUsed;
while (tempNode.key != key) {
if (tempNode.previous == null) {
return null; // not found
}
tempNode = tempNode.previous;
}
return tempNode;
}
private void promoteNode(Node<K, V> tempNode) {
if (tempNode.key == mostRecentlyUsed.key) {
return; // if it's most recently node, don't promote
}
Node<K, V> nextNode = tempNode.next;
Node<K, V> previousNode = tempNode.previous;
if (tempNode.key == leastRecentlyUsed.key) { // If we are in the beginning
nextNode.previous = null;
leastRecentlyUsed = nextNode;
} else { // If we are in the middle,
previousNode.next = nextNode;
nextNode.previous = previousNode;
}
// Move node to the most recently used (right/end)
tempNode.previous = mostRecentlyUsed;
mostRecentlyUsed.next = tempNode;
mostRecentlyUsed = tempNode;
mostRecentlyUsed.next = null;
}
}