Skip to content

Instantly share code, notes, and snippets.

@MarcoSantarossa
Last active October 18, 2022 05:46
Show Gist options
  • Save MarcoSantarossa/e21599d028a9187e4f88e767f8d2acf0 to your computer and use it in GitHub Desktop.
Save MarcoSantarossa/e21599d028a9187e4f88e767f8d2acf0 to your computer and use it in GitHub Desktop.
final class CacheLRU<Key: Hashable, Value> {
private struct CachePayload {
let key: Key
let value: Value
}
private let capacity: Int
private let list = DoublyLinkedList<CachePayload>()
private var nodesDict = [Key: DoublyLinkedListNode<CachePayload>]()
init(capacity: Int) {
self.capacity = max(0, capacity)
}
func setValue(_ value: Value, for key: Key) {
let payload = CachePayload(key: key, value: value)
if let node = nodesDict[key] {
node.payload = payload
list.moveToHead(node)
} else {
let node = list.addHead(payload)
nodesDict[key] = node
}
if list.count > capacity {
let nodeRemoved = list.removeLast()
if let key = nodeRemoved?.payload.key {
nodesDict[key] = nil
}
}
}
func getValue(for key: Key) -> Value? {
guard let node = nodesDict[key] else { return nil }
list.moveToHead(node)
return node.payload.value
}
}
typealias DoublyLinkedListNode<T> = DoublyLinkedList<T>.Node<T>
final class DoublyLinkedList<T> {
final class Node<T> {
var payload: T
var previous: Node<T>?
var next: Node<T>?
init(payload: T) {
self.payload = payload
}
}
private(set) var count: Int = 0
private var head: Node<T>?
private var tail: Node<T>?
func addHead(_ payload: T) -> Node<T> {
let node = Node(payload: payload)
defer {
head = node
count += 1
}
guard let head = head else {
tail = node
return node
}
head.previous = node
node.previous = nil
node.next = head
return node
}
func moveToHead(_ node: Node<T>) {
guard node !== head else { return }
let previous = node.previous
let next = node.next
previous?.next = next
next?.previous = previous
node.next = head
node.previous = nil
if node === tail {
tail = previous
}
self.head = node
}
func removeLast() -> Node<T>? {
guard let tail = self.tail else { return nil }
let previous = tail.previous
previous?.next = nil
self.tail = previous
if count == 1 {
head = nil
}
count -= 1
return tail
}
}
@ruralcoder
Copy link

There is a bug in the DoublyLinkedList

func moveToHead(_ node: Node<T>) {
        guard node !== head else { return }
        let previous = node.previous
        let next = node.next
        
        previous?.next = next
        next?.previous = previous
        
        node.next = head
        node.previous = nil
        
        if node === tail {
            tail = previous
        }
        
        self.head?.previous = node  // << missing line
        self.head = node
    }

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment