lru.go

type LRUCache struct {
	capacity int
	cache    map[int]int
	priority *list.List
	key2node map[int]*list.Element
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]int),
		priority: list.New(),
		key2node: make(map[int]*list.Element),
	}
}

func (this *LRUCache) Get(key int) int {
	val, ok := this.cache[key]
	if !ok {
		return -1
	}
	this.remove(key)
	this.insert(key, val)
	return val
}

func (this *LRUCache) Put(key, value int) {
	if _, ok := this.cache[key]; ok {
		this.remove(key)
	} else if this.priority.Len() >= this.capacity {
		if node := this.priority.Back(); node != nil {
			this.remove(node.Value.(int))
		}
	}
	this.insert(key, value)
}

func (this *LRUCache) remove(key int) {
	delete(this.cache, key)
	if node, _ := this.key2node[key]; node != nil {
		this.priority.Remove(node)
		delete(this.key2node, key)
	}
}

func (this *LRUCache) insert(key, val int) {
	this.cache[key] = val
	this.key2node[key] = this.priority.PushFront(key)
}