Add LRUCache (#6)

0xLeif · Jun 10, 2023 · 5a797f4 · 5a797f4
1 parent e8bb8f8
commit 5a797f4
Show file tree

Hide file tree

Showing 2 changed files with 194 additions and 0 deletions.
diff --git a/Sources/Cache/Cache/LRUCache.swift b/Sources/Cache/Cache/LRUCache.swift
@@ -0,0 +1,101 @@
+import Foundation
+
+/**
+The `LRUCache` class is a cache that uses the Least Recently Used (LRU) algorithm to evict items when the cache capacity is exceeded. The LRU cache is implemented as a key-value store where the access to items is tracked and the least recently used ones are evicted when the capacity is reached.
+
+Use `LRUCache` to create a cache that automatically evicts items from memory when the cache capacity is exceeded. The cache contents are automatically loaded from the initial values dictionary when initialized.
+
+Note: You must make sure that the specified key type conforms to the `Hashable` protocol.
+
+Error Handling: The set(value:forKey:) function does not throw any error. Instead, when the cache capacity is exceeded, the least recently used item is automatically evicted from the cache.
+
+The `LRUCache` class is a subclass of the `Cache` class. You can use its `capacity` property to specify the maximum number of key-value pairs that the cache can hold.
+*/
+public class LRUCache<Key: Hashable, Value>: Cache<Key, Value> {
+    private var keys: [Key]
+
+    /// The maximum capacity of the cache.
+    public let capacity: UInt
+
+    /**
+     Initializes a new `LRUCache` instance with the specified capacity.
+
+     - Parameter capacity: The maximum number of key-value pairs that the cache can hold.
+     */
+    public init(capacity: UInt) {
+        self.keys = []
+        self.capacity = capacity
+
+        super.init()
+    }
+
+    /**
+     Initializes a new `LRUCache` instance with the specified initial values dictionary.
+
+     The contents of the dictionary are loaded into the cache, and the capacity is set to the number of key-value pairs in the dictionary.
+
+     - Parameter initialValues: A dictionary of key-value pairs to load into the cache initially.
+     */
+    public required init(initialValues: [Key: Value] = [:]) {
+        let keys = Array(initialValues.keys)
+
+        self.keys = keys
+        self.capacity = UInt(keys.count)
+
+        super.init(initialValues: initialValues)
+    }
+
+    public override func get<Output>(_ key: Key, as: Output.Type = Output.self) -> Output? {
+        guard let value = super.get(key, as: Output.self) else {
+            return nil
+        }
+
+        updateKeys(recentlyUsed: key)
+
+        return value
+    }
+
+    public override func set(value: Value, forKey key: Key) {
+        super.set(value: value, forKey: key)
+
+        updateKeys(recentlyUsed: key)
+        checkCapacity()
+    }
+
+    public override func remove(_ key: Key) {
+        super.remove(key)
+
+        if let index = keys.firstIndex(of: key) {
+            keys.remove(at: index)
+        }
+    }
+
+    public override func contains(_ key: Key) -> Bool {
+        guard super.contains(key) else {
+            return false
+        }
+
+        updateKeys(recentlyUsed: key)
+
+        return true
+    }
+
+    // MARK: - Private Helpers
+
+    private func checkCapacity() {
+        guard
+            keys.count > capacity,
+            let keyToRemove = keys.first
+        else { return }
+
+        remove(keyToRemove)
+    }
+
+    private func updateKeys(recentlyUsed: Key) {
+        if let index = keys.firstIndex(of: recentlyUsed) {
+            keys.remove(at: index)
+        }
+
+        keys.append(recentlyUsed)
+    }
+}
diff --git a/Tests/CacheTests/LRUCacheTests.swift b/Tests/CacheTests/LRUCacheTests.swift
@@ -0,0 +1,93 @@
+import XCTest
+@testable import Cache
+
+final class LRUCacheTests: XCTestCase {
+    func testLRUCacheCapacity() {
+        let cache = LRUCache<String, Int>(capacity: 3)
+
+        // Add some key-value pairs
+        cache["one"] = 1
+        cache["two"] = 2
+        cache["three"] = 3
+
+        // Test that the cache has the expected contents
+        XCTAssertEqual(cache["one"], 1)
+        XCTAssertEqual(cache["two"], 2)
+        XCTAssertEqual(cache["three"], 3)
+
+        // Add a new key-value pair to exceed the capacity
+        cache["four"] = 4
+
+        // Test that the least recently used key was removed
+        XCTAssertNil(cache["one"])
+
+        // Test that the cache has the expected contents
+        XCTAssertEqual(cache["two"], 2)
+        XCTAssertEqual(cache["three"], 3)
+        XCTAssertEqual(cache["four"], 4)
+
+        // Access an existing key to promote it to the end of the keys array
+        XCTAssert(cache.contains("two"))
+
+        // Add another key-value pair to exceed the capacity
+        cache["five"] = 5
+
+        // Test that the least recently used key was removed
+        XCTAssertNil(cache["three"])
+
+        // Test that the cache has the expected contents
+        XCTAssertEqual(cache["two"], 2)
+        XCTAssertEqual(cache["four"], 4)
+        XCTAssertEqual(cache["five"], 5)
+
+        // Remove a key and test that it was removed from both the cache and the keys array
+        cache["two"] = nil
+        XCTAssertNil(cache["two"])
+        XCTAssertFalse(cache.contains("two"))
+    }
+
+    func testLRUCacheInitialValues() {
+        let cache = LRUCache<String, Int>(
+            initialValues: [
+                "one": 1,
+                "two": 2,
+                "three": 3
+            ]
+        )
+
+        // Test that the cache has the expected contents
+        XCTAssertEqual(cache["one"], 1)
+        XCTAssertEqual(cache["two"], 2)
+        XCTAssertEqual(cache["three"], 3)
+
+        // Add a new key-value pair to exceed the capacity
+        cache["four"] = 4
+
+        // Test that the least recently used key was removed
+        XCTAssertNil(cache["one"])
+
+        // Test that the cache has the expected contents
+        XCTAssertEqual(cache["two"], 2)
+        XCTAssertEqual(cache["three"], 3)
+        XCTAssertEqual(cache["four"], 4)
+
+        // Access an existing key to promote it to the end of the keys array
+        XCTAssert(cache.contains("two"))
+
+        // Add another key-value pair to exceed the capacity
+        cache["five"] = 5
+
+        // Test that the least recently used key was removed
+        XCTAssertNil(cache["three"])
+
+        // Test that the cache has the expected contents
+        XCTAssertEqual(cache["two"], 2)
+        XCTAssertEqual(cache["four"], 4)
+        XCTAssertEqual(cache["five"], 5)
+
+        // Remove a key and test that it was removed from both the cache and the keys array
+        cache["two"] = nil
+        XCTAssertNil(cache["two"])
+        XCTAssertFalse(cache.contains("two"))
+    }
+}