Add LFU Cache (TheAlgorithms#3161)

itsAkshayDubey · web-flow · commit 2a2c575c89c0 · 2022-06-22T19:31:24.000+03:00
diff --git a/src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java b/src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java
@@ -0,0 +1,147 @@
+package com.thealgorithms.datastructures.caches;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * Java program for LFU Cache (https://en.wikipedia.org/wiki/Least_frequently_used)
+ * @author Akshay Dubey (https://github.com/itsAkshayDubey)
+ */
+public class LFUCache<K,V> {
+
+	private class Node {
+		private K key;
+		private V value;
+		private int frequency;
+		private Node previous;
+		private Node next;
+
+		public Node(K key, V value, int frequency) {
+			this.key = key;
+			this.value = value;
+			this.frequency = frequency;
+		}
+	}
+
+	private Node head;
+	private Node tail;
+	private Map<K,Node> map = null;
+	private Integer capacity;
+	private static final int DEFAULT_CAPACITY = 100;
+	
+	public LFUCache() {
+		this.capacity = DEFAULT_CAPACITY;
+	}
+
+	public LFUCache(Integer capacity) {
+		this.capacity = capacity;
+		this.map = new HashMap<>();
+	}
+	
+    /**
+     * This method returns value present in the cache corresponding to the key passed as parameter
+     *
+     * @param <K> key for which value is to be retrieved 
+     * @returns <V> object corresponding to the key passed as parameter, returns null if <K> key is not present in the cache
+     */
+	public V get(K key) {
+		if(this.map.get(key) == null) {
+			return null;
+		}
+
+		Node node = map.get(key);
+		removeNode(node);
+		node.frequency += 1;
+		addNodeWithUpdatedFrequency(node);
+
+		return node.value;
+	}
+
+    /**
+     * This method stores <K> key and <V> value in the cache
+     *
+     * @param <K> key which is to be stored in the cache
+     * @param <V> value which is to be stored in the cache 
+     */
+	public void put(K key, V value) {
+		if(map.containsKey(key)) {
+			Node node =  map.get(key);
+			node.value = value;
+			node.frequency += 1;
+			removeNode(node);
+			addNodeWithUpdatedFrequency(node);
+		}
+		else {
+			if(map.size() >= capacity) {
+				map.remove(this.head.key);
+				removeNode(head);
+			}
+			Node node = new Node(key,value,1);
+			addNodeWithUpdatedFrequency(node);
+			map.put(key, node);
+		}
+	}
+
+    /**
+     * This method stores the node in the cache with updated frequency
+     *
+     * @param Node node which is to be updated in the cache 
+     */
+	private void addNodeWithUpdatedFrequency(Node node) {
+		if(tail != null && head != null) {
+			Node temp = this.head;
+			while(temp != null) {
+				if(temp.frequency > node.frequency) {
+					if(temp==head) {
+						node.next = temp;
+						temp.previous = node;
+						this.head = node;
+						break;
+					}
+					else {
+						node.next = temp;
+						node.previous = temp.previous;
+						temp.previous.next = node;
+						node.previous = temp.previous;
+						break;
+					}
+				}
+				else {
+					temp = temp.next;
+					if(temp == null) {
+						tail.next = node;
+						node.previous = tail;
+						node.next = null;
+						tail = node;
+						break;
+					}
+				}
+			}
+		}
+		else {
+			tail = node;
+			head = tail;
+		}
+	}
+
+    /**
+     * This method removes node from the cache 
+     * 
+     * @param Node node which is to be removed in the cache 
+     */
+	private void removeNode(Node node) {
+		if(node.previous != null) {
+			node.previous.next = node.next;
+		}
+		else {
+			this.head = node.next;
+		}
+
+		if(node.next != null) {
+			node.next.previous = node.previous;
+		}
+		else {
+			this.tail = node.previous;
+		}		
+	}
+}
diff --git a/src/test/java/com/thealgorithms/datastructures/caches/LFUCacheTest.java b/src/test/java/com/thealgorithms/datastructures/caches/LFUCacheTest.java
@@ -0,0 +1,67 @@
+package com.thealgorithms.datastructures.caches;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import org.junit.jupiter.api.Test;
+
+class LFUCacheTest {
+
+	@Test
+	void testLFUCacheWithIntegerValueShouldPass() {
+
+		LFUCache<Integer, Integer> lfuCache = new LFUCache<>(5);
+		lfuCache.put(1, 10);
+		lfuCache.put(2, 20);
+		lfuCache.put(3, 30);
+		lfuCache.put(4, 40);
+		lfuCache.put(5, 50);
+
+		//get method call will increase frequency of key 1 by 1
+		assertEquals(10, lfuCache.get(1));
+
+		//this operation will remove value with key as 2
+		lfuCache.put(6, 60);
+
+		//will return null as value with key 2 is now evicted
+		assertEquals(null, lfuCache.get(2));
+
+		//should return 60
+		assertEquals(60, lfuCache.get(6));
+
+		//this operation will remove value with key as 3
+		lfuCache.put(7, 70);
+
+		assertEquals(null, lfuCache.get(2));
+		assertEquals(70, lfuCache.get(7));
+	}
+
+	@Test
+	void testLFUCacheWithStringValueShouldPass() {
+
+		LFUCache<Integer, String> lfuCache = new LFUCache<>(5);
+		lfuCache.put(1, "Alpha");
+		lfuCache.put(2, "Beta");
+		lfuCache.put(3, "Gamma");
+		lfuCache.put(4, "Delta");
+		lfuCache.put(5, "Eplison");
+
+		//get method call will increase frequency of key 1 by 1
+		assertEquals("Alpha", lfuCache.get(1));
+
+		//this operation will remove value with key as 2
+		lfuCache.put(6, "Digamma");
+
+		//will return null as value with key 2 is now evicted
+		assertEquals(null, lfuCache.get(2));
+
+		//should return string Digamma
+		assertEquals("Digamma", lfuCache.get(6));
+
+		//this operation will remove value with key as 3
+		lfuCache.put(7, "Zeta");
+
+		assertEquals(null, lfuCache.get(2));
+		assertEquals("Zeta", lfuCache.get(7));
+	}
+
+}
