cacheLFUAlgorithm.swift

class Node {
    var key: Int
    var value: Int
    var freq: Int
    var next: Node?
    var prev: Node?
    
    init(key: Int, value: Int) {
        self.key = key
        self.value = value
        self.freq = 1
    }
}

class List {
    var size: Int
    var head: Node?
    var tail: Node?
    
    init() {
        size = 0
    }
    
    func addAtFront(node: Node) {
        defer {
            head = node
            size += 1
        }
        
        guard let head = head else {
            tail = node
            return
        }
        
        head.prev = node
        node.prev = nil
        node.next = head
    }
    
    func removeNode(node: Node?) {
        let prev = node?.prev
        let next = node?.next
        node?.prev = nil
        node?.next = nil
        size -= 1
        
        if tail === node {
            tail = prev
            prev?.next = nil
        } 
        if head === node {
            head = next
            next?.prev = nil
        }
        
        prev?.next = next
        next?.prev = prev
    }
    
    func removeLast() -> Node? {
        guard let tail = self.tail else { return nil }
        
        let previous = tail.prev
        previous?.next = nil
        self.tail = previous
        
        if size == 1 {
            head = nil
        }
        
        size -= 1
        
        return tail
    }
}

class LFUCache {
    var keyNodeDic: [Int: Node] = [:]
    var frequentListDic: [Int: List] = [:]
    
    var maxSizeCache: Int
    var minFrequency: Int
    var currentSize: Int
    
    init(_ capacity: Int) {
        self.maxSizeCache = max(capacity,0)
        keyNodeDic.reserveCapacity(maxSizeCache)
        frequentListDic.reserveCapacity(maxSizeCache)
        minFrequency = 0
        currentSize = 0
    }
    
    func get(_ key: Int) -> Int {
        if let node = keyNodeDic[key] {
            updateFreqListDic(node)
            return node.value
        }
        return -1
    }
    
    func put(_ key: Int, _ value: Int) {
        guard maxSizeCache > 0 else { return }
        
        if let node = keyNodeDic[key] {
            node.value = value
            updateFreqListDic(node)
            return
        } else {
            if currentSize == maxSizeCache,
               let list = frequentListDic[minFrequency] {
                let removedNode = list.removeLast()
                keyNodeDic.removeValue(forKey: removedNode?.key ?? 0)
                currentSize -= 1
            }
            
            currentSize += 1
            minFrequency = 1
            var listFreq = List()
            if let nextList = frequentListDic[minFrequency] {
                listFreq = nextList
            }
            
            let newNode = Node(key: key, value: value)
            listFreq.addAtFront(node: newNode)
            keyNodeDic[key] = newNode
            frequentListDic[minFrequency] = listFreq
        }
    }
    
    private func updateFreqListMap(_ node: Node) {
        frequentListDic[node.freq]?.removeNode(node: node)
        
        if (node.freq == minFrequency) && (frequentListDic[node.freq]?.size == 0) {
            minFrequency += 1
            frequentListDic.removeValue(forKey: node.freq)
        }
        
        var nextHigherFreqList = List()
        if let nextList = frequentListDic[node.freq + 1] {
            nextHigherFreqList = nextList
        }
        
        node.freq += 1
        nextHigherFreqList.addAtFront(node: node)
        frequentListDic[node.freq] = nextHigherFreqList
        keyNodeDic[node.key] = node
    }
}