LRUCacheExample.swift

   //  Created by Nick Peterson on 8/7/19.
//  Copyright © 2019 Nicholas Peterson. All rights reserved.
//

import Foundation

class Cache<T> {
    class Node<T> {
        var object: T?
        let key: String
        var next: Node<T>?
        var previous: Node<T>?
        
        init(object: T?, key: String) {
            self.object = object
            self.key = key
        }
    }
   
    private let head = Node<T>(object: nil, key: "INTERNAL_HEAD")
    private var cacheStore = [String : Node<T>]()
    let capacity: Int
    
    init(withCapacity capacity: Int) {
        self.capacity = capacity
        head.next = head
        head.previous = head
    }
    
    func addObject(_ object: T, for key: String) {
        if let existing = cacheStore[key] {
            touchNode(existing)
            existing.object = object
            return
        }
        
        if cacheStore.count >= self.capacity {
            evictLast()
        }
        
        let newNode = Node(object: object, key: key)
        cacheStore[key] = newNode
        touchNode(newNode)
        //print("didCache: \(key)")
    }
    
    func objectForKey(_ key: String) -> T? {
        guard let node = cacheStore[key] else { return nil }
        
        touchNode(node)
        return node.object
    }
    
    func hasCached(_ key: String) -> Bool {
        guard let node = cacheStore[key] else { return false }
        
        return node.object != nil
    }
    
    private func touchNode(_ node: Node<T>) {
        node.next?.previous = node.previous
        node.previous?.next = node.next
        
        node.next = head.next
        node.previous = head
        
        node.next?.previous = node
        head.next = node
        //print("touched: \(node.key)")
    }
    
    private func evictLast() {
        guard let evicting = head.previous,
            evicting.key != head.key
            else { return } //Cache Empty
        
        head.previous = evicting.previous
        evicting.previous?.next = head
        
        cacheStore[evicting.key] = nil
        //print("evicted: \(evicting.key)")
    }
}