-
Notifications
You must be signed in to change notification settings - Fork 13
/
LL_LRUCache.java
138 lines (111 loc) · 4.59 KB
/
LL_LRUCache.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
// https://practice.geeksforgeeks.org/problems/lru-cache/1
// https://www.youtube.com/watch?v=S6IfqDXWa10 (BEST Video explanation)
// https://leetcode.com/problems/lru-cache/
// https://github.com/bephrem1/backtobackswe/blob/master/Linked%20Lists/LRUCache/LRUCache.java
// https://leetcode.com/problems/lru-cache/discuss/45911/Java-Hashtable-%2B-Double-linked-list-(with-a-touch-of-pseudo-nodes)
public class LL_LRUCache {
private static class LRUCache {
private final Map<Integer, ListNode> map = new HashMap<>();
private final ListNode head;
private final ListNode tail;
private int totalItemInCache;
private final int maxCapacity;
public LRUCache(int capacity) {
this.maxCapacity = capacity; /* Cache starts empty and capacity is set by client */
this.totalItemInCache = 0;
this.head = new ListNode(); /* Dummy head and tail nodes to avoid empty states */
this.tail = new ListNode();
this.head.next = tail; /* Wire the head and tail together */
this.tail.prev = head;
}
public int get(int key) {
ListNode node = map.get(key);
if (node == null) {
return -1;
}
moveToHead(node); /* Item has been accessed. Move to the front of the cache */
return node.value;
}
public void put(int key, int value) {
ListNode node = map.get(key);
if (node == null) { /* Item not found, create a new entry */
node = new ListNode();
node.key = key;
node.value = value;
map.put(key, node); /* Add to the hashmap and the actual list that represents the cache */
addToFront(node);
++totalItemInCache;
if(totalItemInCache > maxCapacity) { /* If over capacity remove the LRU item */
removeLRUEntry();
}
}
else { /* If item is found in the cache, just update it and Move to the front of the cache */
node.value = value;
moveToHead(node);
}
}
private void moveToHead(ListNode node) {
removeFromList(node);
addToFront(node);
}
private void removeFromList(ListNode node) {
ListNode prevOfNodeToBeRemoved = node.prev;
ListNode nextOfNodeToBeRemoved = node.next;
prevOfNodeToBeRemoved.next = nextOfNodeToBeRemoved;
nextOfNodeToBeRemoved.prev = prevOfNodeToBeRemoved;
}
private void addToFront(ListNode node) {
node.prev = head; /* Wire up the new node being to be inserted */
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeLRUEntry() {
ListNode tailItem = popTail();
map.remove(tailItem.key);
--totalItemInCache;
}
private ListNode popTail() {
ListNode tailItem = tail.prev;
removeFromList(tailItem);
return tailItem;
}
// doubly linked list
private static class ListNode {
private int key;
private int value;
private ListNode prev;
private ListNode next;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
int capacity = Integer.parseInt(br.readLine());
int queries = Integer.parseInt(br.readLine());
LRUCache cache = new LRUCache(capacity);
String[] input = br.readLine().trim().split("\\s+");
int len = input.length;
int itr = 0;
for (int i = 0; (i < queries) && (itr < len); i++) {
String queryType = input[itr++];
if (queryType.equals("SET")) {
int key = Integer.parseInt(input[itr++]);
int value = Integer.parseInt(input[itr++]);
cache.put(key, value);
}
if (queryType.equals("GET")) {
int key = Integer.parseInt(input[itr++]);
System.out.print(cache.get(key) + " ");
}
}
System.out.println();
}
}
}