1protocol Cacheable {
2 associatedtype Key: Hashable
3 associatedtype Value
4 mutating func get(_ key: Key) -> Value?
5 mutating func set(_ key: Key, value: Value)
6 var count: Int { get }
7}
8
9struct LRUCache<K: Hashable, V>: Cacheable {
10 typealias Key = K
11 typealias Value = V
12
13 private var capacity: Int
14 private var storage: [K: V] = [:]
15 private var order: [K] = []
16
17 init(capacity: Int) {
18 precondition(capacity > 0, "Capacity must be positive")
19 self.capacity = capacity
20 }
21
22 var count: Int { storage.count }
23
24 mutating func get(_ key: K) -> V? {
25 guard let value = storage[key] else { return nil }
26 moveToFront(key)
27 return value
28 }
29
30 mutating func set(_ key: K, value: V) {
31 if storage[key] != nil {
32 storage[key] = value
33 moveToFront(key)
34 } else {
35 if storage.count >= capacity {
36 let evicted = order.removeLast()
37 storage.removeValue(forKey: evicted)
38 }
39 storage[key] = value
40 order.insert(key, at: 0)
41 }
42 }
43
44 private mutating func moveToFront(_ key: K) {
45 if let idx = order.firstIndex(of: key) {
46 order.remove(at: idx)
47 order.insert(key, at: 0)
48 }
49 }
50}