1import OrderedCollections
2
3/// This implements a very basic LRU (least-recently used) cache.
4///
5/// The cache has a maximum size, and objects get evicted when the cache grows
6/// too large.  This is primarily used to cache images, and avoid the memory
7/// footprint of the application growing forever.
8struct LRUCache<Key: Hashable, Value> {
9    private var contents: Dictionary<Key, Value>
10    private var keyHistory: OrderedSet<Key>
11    
12    var maxSize: Int
13    
14    init(withMaxSize maxSize: Int) {
15        self.maxSize = maxSize
16        
17        self.contents = Dictionary()
18        self.keyHistory = OrderedSet()
19    }
20    
21    subscript(key: Key) -> Value? {
22        get {
23            contents[key]
24        }
25        
26        set {
27            contents[key] = newValue
28            
29            // Move the key to the beginning of the key history
30            keyHistory.remove(key)
31            keyHistory.insert(key, at: 0)
32            
33            assert(contents.count == keyHistory.count)
34            
35            while contents.count > self.maxSize {
36                let lastKey = keyHistory.last!
37                
38                contents.removeValue(forKey: lastKey)
39                keyHistory.remove(lastKey)
40            }
41        }
42    }
43    
44    mutating func removeValue(forKey key: Key) {
45        keyHistory.remove(key)
46        contents.removeValue(forKey: key)
47    }
48}