import java.util.HashMap;
import java.util.Map.Entry;
/*
* LinkedList node to hold the cached data
*/
class NodeLRU {
int data;
NodeLRU next;
NodeLRU previous;
public NodeLRU(int data) {
this.data = data;
this.next = null;
this.previous = null;
}
}
/**
* Implementing LRU Cache using LinkedList and HashMap to get() value with O(1)
* time complexity.
*/
class LRUCache {
// Total cache size
private final static int CACHE_SIZE = 5;
// Map to hold the cached nodes
private HashMap<Integer, NodeLRU> map = new HashMap<Integer, NodeLRU>(CACHE_SIZE);
// Doubly LinkedList head and tail node pointer
private NodeLRU head = null;
private NodeLRU tail = null;
/*
* Set method which will add data into LinkedList
* and if already key present then remove and ADD as new element.
*/
public void set(int key, int val) {
if (map.containsKey(key)) {
removeExistingNode(key, val);
set(key, val);
} else {
addNode(key, val);
}
}
/*
* Get method which will return node data if present
* else returns -1. Once if data node present in map then
* Fetch the node and place it @ head location.
*/
public int get(int key) {
if (map.containsKey(key)) {
NodeLRU node = map.get(key);
makeAsRecentUsed(node);
return node.data;
}
return -1;
}
/*
* One if node present via get() method then
* pick out the node and stitch with head location as first node.
*
*/
private void makeAsRecentUsed(NodeLRU node) {
if (node.equals(head)) {
return;
} else if (node.equals(tail)) {
tail.previous.next = null;
tail = tail.previous;
} else {
node.previous.next = node.next;
node.next.previous = node.previous;
}
node.previous = null;
node.next = head;
head.previous = node;
head = node;
}
/*
* Delete the least used node frm LinkedList and map
*/
private void removeExistingNode(int key, int val) {
NodeLRU tmp = map.get(key);
if (tmp.next != null && tmp.previous != null) {
tmp.previous.next = tmp.next;
tmp.next.previous = tmp.previous;
} else if (tmp.equals(tail)) {
removeLeastUsed();
} else if (tmp.equals(head)) {
removeHeadNode();
}
}
/*
* Removing 1st node
*/
private void removeHeadNode() {
NodeLRU firstNode = head;
tail = tail.next;
tail.previous = null;
removeFromMap(firstNode);
}
/*
* Adding new node to LinkedList
*/
private void addNode(int key, int val) {
if (map.size() < CACHE_SIZE) {
NodeLRU tmp = new NodeLRU(val);
if (head == null && tail == null) {
head = tail = tmp;
} else {
head.previous = tmp;
tmp.next = head;
head = tmp;
}
map.put(key, tmp);
} else {
removeLeastUsed();
addNode(key, val);
}
}
/*
* Removing least/ last node from LinkedList
*/
private void removeLeastUsed() {
NodeLRU leastUsed = tail;
tail = tail.previous;
tail.next = null;
removeFromMap(leastUsed);
}
/*
* Removing from map also based on value node
*/
private void removeFromMap(NodeLRU node) {
for (Entry<Integer, NodeLRU> entry : map.entrySet()) {
if (entry.getValue().equals(node)) {
map.remove(entry.getKey());
return;
}
}
}
/*
* Method to print all LinkedList nodes data
*/
public void printValueFromCache() {
NodeLRU tmp = head;
System.out.print("CACHE VALUES : ");
while (tmp != null) {
System.out.print(tmp.data + ", ");
tmp = tmp.next;
}
System.out.println();
}
public static void main(String[] args) {
LRUCache obj = new LRUCache();
// Adding 1 to 5 values to cache
obj.set(1, 11);
obj.set(2, 12);
obj.set(3, 13);
obj.set(4, 14);
obj.set(5, 15);
obj.printValueFromCache();
/*
* Reading value with key (1) which we adding 1st and
* placed last in LL. Once we read same value (Node) should
* be placed as recent and moved to top of linked List.
*/
int val = obj.get(1);
System.out.println("READ VALUE : "+val);
obj.printValueFromCache();
/*
* Adding some more values to Cache. Since we set cache size as 5
* least used 3 nodes like (2,3,4) need to removed and (6,7,8)
* values need to added to linked list
*/
obj.set(6, 66);
obj.set(7, 77);
obj.set(8, 88);
obj.printValueFromCache();
/*
* Reading again with key (5) which makes node to shift to head
* which will be recently used
*/
val = obj.get(5);
System.out.println("READ VALUE : "+val);
obj.printValueFromCache();
}
}
CACHE VALUES : 15, 14, 13, 12, 11,
READ VALUE : 11
CACHE VALUES : 11, 15, 14, 13, 12,
CACHE VALUES : 88, 77, 66, 11, 15,
READ VALUE : 15
CACHE VALUES : 15, 88, 77, 66, 11,