final class UnfairLock: NSLocking {
    let unfairLock: NSLocking
    
    init() {
        if #available(iOS 16.0, *) {
            unfairLock = AllocatedUnfairLock()
        } else {
            unfairLock = OSUnfairLock()
        }
    }
    
    func lock() {
        unfairLock.lock()
    }
    
    func unlock() {
        unfairLock.unlock()
    }
    
    @available(iOS 16.0, *)
    private final class AllocatedUnfairLock: NSLocking {
        private let allocUnfairLock = OSAllocatedUnfairLock()
        
        func lock() {
            allocUnfairLock.lock()
        }
        
        func unlock() {
            allocUnfairLock.unlock()
        }
    }
    
    private final class OSUnfairLock: NSLocking {
        
        private let osUnfairLock: os_unfair_lock_t
        
        init() {
            osUnfairLock = .allocate(capacity: 1)
            osUnfairLock.initialize(to: os_unfair_lock())
        }
        
        deinit {
            osUnfairLock.deinitialize(count: 1)
            osUnfairLock.deallocate()
        }
        
        func lock() {
            os_unfair_lock_lock(osUnfairLock)
        }
        
        func tryLock() -> Bool {
            return os_unfair_lock_trylock(osUnfairLock)
        }
        
        func unlock() {
            os_unfair_lock_unlock(osUnfairLock)
        }
    }
}

class DoublyLinkedList<K, V>{
    var key: K
    var value: V
    var previous: DoublyLinkedList?
    var next: DoublyLinkedList?
    
    init(_ key: K, _ value: V) {
        self.key = key
        self.value = value
    }
}

final class LRUCache<K: Hashable, V> {
    private var maxCapacity: Int
    private var head: DoublyLinkedList<K, V>
    private var tail: DoublyLinkedList<K, V>
    private var cache: [K: DoublyLinkedList<K, V>]
    
    private let lock = UnfairLock()

    init(key: K, value: V, maxCapacity: Int) {
        self.maxCapacity = maxCapacity
        self.cache = [K: DoublyLinkedList<K, V>]()
        self.head = DoublyLinkedList<K, V>(key, value)
        self.tail = DoublyLinkedList<K, V>(key, value)
        self.head.next = self.tail
        self.tail.previous = self.head
        
        NotificationCenter.default.addObserver(self, selector: #selector(receiveMemoryWarning), name: UIApplication.didReceiveMemoryWarningNotification, object: nil)
    }
    
    deinit {
        removeAll()
        NotificationCenter.default.removeObserver(self)
    }
    
    @objc private func receiveMemoryWarning() {
        removeAll()
    }
    
    private func add(_ node: DoublyLinkedList<K, V>){
        let next = head.next
        head.next = node
        node.previous = head
        node.next = next
        next?.previous = node
    }
    
    func removeAll() {
        lock.lock()
        defer { lock.unlock() }

        for (key, node) in cache {
            remove(node)
            cache.removeValue(forKey: key)
        }
        self.head.next = nil
        self.tail.previous = nil
    }
    
    func remove(_ key: K) {
        lock.lock()
        defer { lock.unlock() }

        if let node = cache[key] {
            remove(node)
            cache.removeValue(forKey: key)
        }
    }
    
    private func remove(_ node: DoublyLinkedList<K, V>){
        let previous = node.previous
        let next = node.next
        previous?.next = next
        next?.previous = previous
    }
    
    func get(_ key: K) -> V?{
        lock.lock()
        defer { lock.unlock() }

        if let node = cache[key]{
            remove(node)
            add(node)
            return node.value
        }
        return nil
    }
    
    func put(key: K, value: V){
        lock.lock()
        defer { lock.unlock() }

        if let node = cache[key]{
            remove(node)
            cache.removeValue(forKey: key)
        }else if cache.keys.count >= maxCapacity{
            if let leastNode = tail.previous{
                remove(leastNode)
                cache.removeValue(forKey: leastNode.key)
            }
        }
        let newNode = DoublyLinkedList(key, value)
        cache[key] = newNode
        add(newNode)
    }
    
    subscript(index: K) -> V? {
        get {
            return get(index)
        }
        
        set {
            guard let newValue = newValue else {
                return
            }
            put(key: index, value: newValue)
        }
    }
}