LeetCode: LFU Cache

// https://code.dennyzhang.com/lfu-cache
// Basic Ideas: double linkedlist + hashmap
//
//  Notice: double linkedlist works, but linkedlist won't
//    This is because we the previous node will be modified
//  Notice: Nodes need to be sorted by frequency.
//  Notice: To initialize a double linkedlist, we only need one node, instead of two
//
// How to update the frequent?
//   When get or put, increase it by 1.
//
// How to find the node to be evicted? minFreq
//   When a new node, minFreq set to be 1.
//   The pattern of minFreq: 
//     1. It keeps growing with 1 step.
//     2. Reset to 1. Then go to step1
//
// Question: what if freq grows too large?
//
// Complexity: Time O(1), Space O(1)
type DLinkedListNode struct {
    freq int
    key int
    val int
    prev *DLinkedListNode
    next *DLinkedListNode
}

type LFUCache struct {
    capacity int
    nodes map[int]*DLinkedListNode
    lists map[int]*DLinkedListNode
    minList int
}

func Constructor(capacity int) LFUCache {
    return LFUCache{capacity:capacity, 
                    nodes:map[int]*DLinkedListNode{},
                    lists:map[int]*DLinkedListNode{}, 
                    minList:0}
}

func (this *LFUCache) Del(node *DLinkedListNode) {
    if node == nil {
        return
    }
    prev, next := node.prev, node.next
    // prev <-> node <-> next
    prev.next = next
    next.prev = prev
    // After the deletion, the chain would be empty
    head := this.lists[this.minList]
    if node.freq == this.minList && head.next == head {
        // Only cause hitting this: increase freq to another one
        this.minList++
    }
    delete(this.nodes, node.key)
}

func (this *LFUCache) AddTail(node *DLinkedListNode) {
    if node == nil {
        return
    }

    if node.freq == 1 {
        // reset the evicted position
        this.minList = 1
    }
    if _, ok := this.lists[node.freq]; !ok {
        dummyNode := &DLinkedListNode{}
        dummyNode.next = dummyNode
        dummyNode.prev = dummyNode
        this.lists[node.freq] = dummyNode
    }
    // add to tail
    head := this.lists[node.freq]
    tail := this.lists[node.freq].prev
    node.next, node.prev = head, tail
    tail.next, head.prev = node, node
    // update hashmap
    this.nodes[node.key] = node
}

func (this *LFUCache) Get(key int) int {
    res := -1
    if node, ok := this.nodes[key]; ok {
        // move the node
        this.Del(node)
        node.freq++
        this.AddTail(node)
        res = node.val
    }
    return res
}

func (this *LFUCache) Put(key int, value int) {
    if node, ok := this.nodes[key]; !ok {
        if this.capacity == 0 {
            if this.minList == 0 {
                // no enough capacity
                return
            }
            // evict one node
            oldNode := this.lists[this.minList].next
            this.Del(oldNode)
        } else {
            this.capacity--
        }
        // add new one
        node = &DLinkedListNode{key: key, freq:1, val:value}
        this.AddTail(node)
    } else {
        // adjust
        node.val = value
        this.Get(key)
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */