cache.go

type LRUCache struct {
    capacity   int
    cache      map[int]*node // map
    head, tail *node         // linked list
}

type node struct {
    prev, next *node
    key, val   int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{capacity: capacity, cache: map[int]*node{},
        head: nil, tail: nil}
}

func (this *LRUCache) Get(key int) int {
    node, ok := this.cache[key]
    // cache miss
    if !ok {
        return -1
    }
    // cache hit on most recently used; do nothing
    if this.head != nil && node.key == this.head.key {
        return node.val
    }
    // cache hit on least recently used; pop to front
    if this.tail != nil && node.key == this.tail.key {
        this.popTail()
        this.insert(node)
        this.cache[node.key] = node
        return node.val
    }
    // pop to front
    if node.prev != nil && node.next != nil {
        node.prev.next = node.next
        node.next.prev = node.prev
        this.insert(node)
    }

    return node.val
}

func (this *LRUCache) Put(key int, value int) {
    // cache has, pop to front
    if this.Get(key) != -1 {
        this.cache[key].val = value
        return
    }

    // cache doesn't have, insert node
    n := &node{key: key, val: value}

    this.cache[key] = n
    this.insert(n)
    // evict least recently used if over capacity
    if len(this.cache) > this.capacity {
        this.popTail()
    }

    return
}

func (this *LRUCache) insert(n *node) {
    // nothing inserted yet
    if this.tail == nil {
        this.tail = n
        this.head = n
        n.next = this.tail
        return
    }
    this.head.prev = n
    n.next = this.head
    this.head = n
}

func (this *LRUCache) popTail() {
    // remove key
    delete(this.cache, this.tail.key)
    // nothing in cache yet
    if this.tail.prev == nil {
        this.tail = nil
        return
    }
    // pop tail
    this.tail.prev.next = nil
    this.tail = this.tail.prev
}