java LRUCache with LinkedHashMap

cirosantilli · cirosantilli · commit 728ad252ab04 · 2015-12-10T14:06:15.000-02:00
diff --git a/algorithms/java/src/lruCache/LRUCache.java b/algorithms/java/src/lruCache/LRUCache.java
@@ -0,0 +1,45 @@
+/*
+Analogous to the C++ solution at:
+https://github.com/haoel/leetcode/blob/625ad10464701fc4177b9ef33c8ad052d0a7d984/algorithms/cpp/LRUCache/LRUCache.cpp
+which uses linked list + hash map. But the Java stdlib provides LinkedHashMap
+which already implements that for us, making this solution shorter.
+
+This could also be done by using, but that generates
+some inheritance boilerplate, and ends up taking the same number of lines:
+https://github.com/cirosantilli/haoel-leetcode/commit/ff04930b2dc31f270854e40b560723577c7b49fd
+*/
+
+import java.util.LinkedHashMap;
+import java.util.Iterator;
+
+public class LRUCache {
+
+    private int capacity;
+    private LinkedHashMap<Integer,Integer> map;
+
+    public LRUCache(int capacity) {
+        this.capacity = capacity;
+        this.map = new LinkedHashMap<>();
+    }
+
+    public int get(int key) {
+        Integer value = this.map.get(key);
+        if (value == null) {
+            value = -1;
+        } else {
+            this.set(key, value);
+        }
+        return value;
+    }
+
+    public void set(int key, int value) {
+        if (this.map.containsKey(key)) {
+            this.map.remove(key);
+        } else if (this.map.size() == this.capacity) {
+            Iterator<Integer> it = this.map.keySet().iterator();
+            it.next();
+            it.remove();
+        }
+        map.put(key, value);
+    }
+}
diff --git a/algorithms/java/src/lruCache/LRUCacheTest.java b/algorithms/java/src/lruCache/LRUCacheTest.java
@@ -0,0 +1,49 @@
+import java.util.ArrayList;
+
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+public class LRUCacheTest {
+
+    private LRUCache c;
+
+    public LRUCacheTest() {
+        this.c = new LRUCache(2);
+    }
+
+    @Test
+    public void testCacheStartsEmpty() {
+        assertEquals(c.get(1), -1);
+    }
+
+    @Test
+    public void testSetBelowCapacity() {
+        c.set(1, 1);
+        assertEquals(c.get(1), 1);
+        assertEquals(c.get(2), -1);
+        c.set(2, 4);
+        assertEquals(c.get(1), 1);
+        assertEquals(c.get(2), 4);
+    }
+
+    @Test
+    public void testCapacityReachedOldestRemoved() {
+        c.set(1, 1);
+        c.set(2, 4);
+        c.set(3, 9);
+        assertEquals(c.get(1), -1);
+        assertEquals(c.get(2), 4);
+        assertEquals(c.get(3), 9);
+    }
+
+    @Test
+    public void testGetRenewsEntry() {
+        c.set(1, 1);
+        c.set(2, 4);
+        assertEquals(c.get(1), 1);
+        c.set(3, 9);
+        assertEquals(c.get(1), 1);
+        assertEquals(c.get(2), -1);
+        assertEquals(c.get(3), 9);
+    }
+}
