LRUCache evicts the wrong entries

Usage by agent

Timeline

1. planner iteration 1 ✓Finished 3 calls · 7,715 tokens · $0.0008 · 10.1s

   Loading…

2. coder iteration 1 ✓Finished 4 calls · 19.3K tokens · $0.0015 · 10.7s

   Loading…

3. tester iteration 1 ✓Finished 5 calls · 32.1K tokens · $0.0021 · 15.0s

   Loading…

4. verify iteration 1 ✓Passed 0.5s

   .........                                                                [100%]
   9 passed in 0.06s
   

5. reviewer iteration 1 ✓Finished 2 calls · 10.8K tokens · $0.0008 · 6.1s

   Loading…

Final diff

diff --git a/lru.py b/lru.py
index 8f9595c..1cd7f0a 100644
--- a/lru.py
+++ b/lru.py
@@ -7,9 +7,16 @@ class LRUCache:
         self._data: OrderedDict = OrderedDict()
 
     def get(self, key):
-        return self._data.get(key)
+        if key not in self._data:
+            return None
+        self._data.move_to_end(key)
+        return self._data[key]
 
     def put(self, key, value) -> None:
+        if key in self._data:
+            self._data[key] = value
+            self._data.move_to_end(key)
+            return
         if len(self._data) >= self.capacity:
             self._data.popitem(last=False)
         self._data[key] = value
diff --git a/test_lru.py b/test_lru.py
index ee81494..985113c 100644
--- a/test_lru.py
+++ b/test_lru.py
@@ -12,3 +12,111 @@ def test_evicts_when_full():
     cache.put("a", 1)
     cache.put("b", 2)
     assert cache.get("a") is None
+
+
+def test_get_marks_entry_recently_used():
+    cache = LRUCache(2)
+    cache.put("a", 1)
+    cache.put("b", 2)
+    assert cache.get("a") == 1
+    cache.put("c", 3)
+    assert cache.get("b") is None
+    assert cache.get("a") == 1
+    assert cache.get("c") == 3
+
+
+def test_update_replaces_value_without_evicting():
+    cache = LRUCache(2)
+    cache.put("a", 1)
+    cache.put("b", 2)
+    cache.put("a", 10)
+    assert list(cache._data.keys()) == ["b", "a"]
+    assert len(cache._data) == 2
+    cache.put("c", 3)
+    assert cache.get("b") is None
+    assert cache.get("a") == 10
+    assert cache.get("c") == 3
+
+
+def test_get_missing_key_does_not_change_cache():
+    cache = LRUCache(2)
+    cache.put("a", 1)
+    assert cache.get("missing") is None
+    assert list(cache._data.keys()) == ["a"]
+
+
+def test_get_missing_key_does_not_evict_or_reorder():
+    cache = LRUCache(2)
+    cache.put("a", 1)
+    cache.put("b", 2)
+    assert cache.get("missing") is None
+    assert list(cache._data.keys()) == ["a", "b"]
+    cache.put("c", 3)
+    assert cache.get("a") is None
+    assert cache.get("b") == 2
+
+
+def test_update_on_capacity_one_keeps_entry():
+    cache = LRUCache(1)
+    cache.put("a", 1)
+    cache.put("a", 2)
+    assert cache.get("a") == 2
+    assert len(cache._data) == 1
+
+
+def test_stored_none_value_is_still_an_entry():
+    cache = LRUCache(2)
+    cache.put("a", None)
+    cache.put("b", 2)
+    assert cache.get("a") is None
+    cache.put("c", 3)
+    assert list(cache._data.keys()) == ["a", "c"]
+    assert cache.get("b") is None
+    assert cache.get("c") == 3
+
+
+def test_matches_reference_model_on_random_operations():
+    import random
+
+    class Reference:
+        def __init__(self, capacity):
+            self.capacity = capacity
+            self.order = []  # least recent first
+            self.values = {}
+
+        def _touch(self, key):
+            self.order.remove(key)
+            self.order.append(key)
+
+        def get(self, key):
+            if key not in self.values:
+                return None
+            self._touch(key)
+            return self.values[key]
+
+        def put(self, key, value):
+            if key in self.values:
+                self.values[key] = value
+                self._touch(key)
+                return
+            if len(self.values) >= self.capacity:
+                oldest = self.order.pop(0)
+                del self.values[oldest]
+            self.values[key] = value
+            self.order.append(key)
+
+    rng = random.Random(1234)
+    for capacity in (1, 2, 3, 5):
+        cache = LRUCache(capacity)
+        ref = Reference(capacity)
+        keys = [f"k{i}" for i in range(capacity + 3)]
+        for _ in range(2000):
+            key = rng.choice(keys)
+            if rng.random() < 0.5:
+                assert cache.get(key) == ref.get(key)
+            else:
+                value = rng.randint(0, 100)
+                cache.put(key, value)
+                ref.put(key, value)
+            assert list(cache._data.keys()) == ref.order
+            assert dict(cache._data) == ref.values