Skip to content

Commit 80b765b

Browse files
StepfenShawnStepfenShawn
authored
Merge pull request TheAlgorithms#1371 from tanmaylaud/Development
Added LFU Cache implementation
2 parents bf223bb + 36e23bb commit 80b765b

File tree

2 files changed

+180
-0
lines changed

2 files changed

+180
-0
lines changed

‎src/main/java/com/caching/LFUCache.java

Lines changed: 155 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,155 @@
1+
package com.caching;
2+
3+
import java.util.HashMap;
4+
import java.util.NoSuchElementException;
5+
import java.util.TreeMap;
6+
7+
/**
8+
* Your LFUCache object can be instantiated and called as such: LFUCache
9+
* lfuCache = new LFUCache(capacity); lfuCache.put(key,value); int param_1 =
10+
* lfuCache.get(key);
11+
*/
12+
class LFUCache<T> {
13+
// internal Node to store cache element
14+
private class Node {
15+
int key;
16+
T value;
17+
int freq;
18+
Node next;
19+
Node pre;
20+
21+
public Node(int key, T value, int freq) {
22+
this.key = key;
23+
this.value = value;
24+
this.freq = freq;
25+
next = pre = null;
26+
}
27+
28+
public String toString() {
29+
return " Key: " + key + "Value: " + value + "Freq: " + freq;
30+
}
31+
32+
}
33+
34+
// internal Doubly Linked List to store cache nodes
35+
private class DLL {
36+
Node head;
37+
Node tail;
38+
int len;
39+
40+
public DLL() {
41+
head = new Node(-1, null, -1);
42+
tail = new Node(-1, null, -1);
43+
head.next = tail;
44+
tail.pre = head;
45+
len = 0;
46+
}
47+
48+
public void addToHead(Node node) {
49+
node.next = head.next;
50+
head.next.pre = node;
51+
head.next = node;
52+
node.pre = head;
53+
len++;
54+
}
55+
56+
public void deleteNode(Node node) {
57+
node.pre.next = node.next;
58+
node.next.pre = node.pre;
59+
len--;
60+
}
61+
62+
}
63+
64+
private int capacity;
65+
private int size;
66+
private TreeMap<Integer, DLL> freq;
67+
private HashMap<Integer, Node> map;
68+
69+
/**
70+
* instantiates LFUCache with fixed capacity
71+
*
72+
* @param capacity The capacity of the cache. Once the cache reaches capacity,
73+
* new elements will replace old elements in LFU manner
74+
*/
75+
public LFUCache(int capacity) {
76+
this.capacity = capacity;
77+
size = 0;
78+
freq = new TreeMap<Integer, DLL>();
79+
map = new HashMap<Integer, Node>();
80+
System.out.println("LFUCache initialised with capacity: " + capacity);
81+
}
82+
83+
/**
84+
* To get the cached value for given key
85+
*
86+
* @param key The key (int) of the expected value
87+
* @return corresponding value for input key
88+
* @throws NoSuchElementException if key is absent
89+
*/
90+
public T get(int key) {
91+
// Cache hit condition
92+
if (map.containsKey(key)) {
93+
Node node = map.get(key);
94+
System.out.println("Returning value from cache:" + node.toString());
95+
DLL dll = freq.get(node.freq);
96+
dll.deleteNode(node);
97+
if (dll.len == 0)
98+
freq.remove(node.freq);
99+
node.freq += 1;
100+
dll = freq.computeIfAbsent(node.freq, k -> new DLL());
101+
dll.addToHead(node);
102+
return node.value;
103+
}
104+
// Cache miss condition
105+
throw new NoSuchElementException("No element for key: " + key);
106+
}
107+
108+
/**
109+
* To put a value in LFU cache with corresponding key
110+
*
111+
* @param key The key (int)
112+
* @param value The value to be cached
113+
*/
114+
public void put(int key, T value) {
115+
if (capacity == 0) {
116+
System.out.println("Cache set to 0 capacity. No element will be cached");
117+
return;
118+
}
119+
if (map.containsKey(key)) {
120+
System.out.println("Key " + key + " already present in cache.Value will be replaced");
121+
Node node = map.get(key);
122+
node.value = value;
123+
DLL dll = freq.get(node.freq);
124+
dll.deleteNode(node);
125+
if (dll.len == 0)
126+
freq.remove(node.freq);
127+
node.freq += 1;
128+
dll = freq.computeIfAbsent(node.freq, k -> new DLL());
129+
dll.addToHead(node);
130+
} else {
131+
System.out.println("Adding new key " + key + " to cache");
132+
Node node = new Node(key, value, 1);
133+
map.put(key, node);
134+
135+
if (size < capacity) {
136+
size++;
137+
DLL dll = freq.computeIfAbsent(1, k -> new DLL());
138+
dll.addToHead(node);
139+
} else {
140+
System.out.println("Cache at peak capacity.Old values will be removed in LFU fashion");
141+
Integer lowest = freq.firstKey();
142+
DLL dll = freq.get(lowest);
143+
map.remove(dll.tail.pre.key);
144+
System.out.println("Value removed:" + dll.tail.pre.value.toString());
145+
dll.deleteNode(dll.tail.pre);
146+
if (dll.len == 0 && lowest != 1)
147+
freq.remove(lowest);
148+
DLL freq_one = freq.computeIfAbsent(1, k -> new DLL());
149+
freq_one.addToHead(node);
150+
}
151+
}
152+
153+
}
154+
155+
}

‎src/test/java/com/caching/LFUCacheTest.java

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package com.caching;
2+
3+
import java.util.NoSuchElementException;
4+
5+
import org.junit.jupiter.api.Assertions;
6+
import org.junit.jupiter.api.Test;
7+
8+
public class LFUCacheTest {
9+
10+
@Test
11+
public void testLFUCache() {
12+
LFUCache<Integer> cache = new LFUCache<Integer>(2 /* capacity */ );
13+
14+
cache.put(1, 1);
15+
cache.put(2, 2);
16+
Assertions.assertEquals(1, cache.get(1)); // returns 1
17+
cache.put(3, 3); // evicts key 2
18+
Assertions.assertThrows(NoSuchElementException.class, () -> cache.get(2));// throws exception
19+
Assertions.assertEquals(3, cache.get(3)); // returns 3.
20+
cache.put(4, 4); // evicts key 1.
21+
Assertions.assertThrows(NoSuchElementException.class, () -> cache.get(1));// throws exception
22+
Assertions.assertEquals(3, cache.get(3)); // returns 3
23+
Assertions.assertEquals(4, cache.get(4)); // returns 4
24+
}
25+
}

0 commit comments

Comments
 (0)