LRUCache

gistfile1.txt

package lrucache

type LRUCacheNode struct {
	Key  int
	Val  int
	Next *LRUCacheNode
	Prev *LRUCacheNode
}

type LRUCache struct {
	capacity int
	len      int
	head     *LRUCacheNode
	tail     *LRUCacheNode
	hashmap  map[int]*LRUCacheNode
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		len:      0,
		head:     nil,
		tail:     nil,
		hashmap:  make(map[int]*LRUCacheNode),
	}
}

func (cache *LRUCache) Get(key int) int {
	value, ok := cache.hashmap[key]
	if ok {
		cache.moveToTail(value)
		return value.Val
	}
	return -1
}

func (cache *LRUCache) moveToTail(node *LRUCacheNode) {
	cache.deleteNode(node)
	cache.addNode(node)
}

func (cache *LRUCache) Put(key int, value int) {
	node, ok := cache.hashmap[key]
	if !ok {
		if cache.Len() >= cache.capacity {
			cache.deleteNode(cache.head)
		}
		node = &LRUCacheNode{Key: key, Val: value, Next: nil, Prev: nil}
		cache.addNode(node)
	} else {
		node.Val = value
		cache.moveToTail(node)
	}
}

func (cache *LRUCache) Len() int {
	return cache.len
}

func (cache *LRUCache) incrLen() {
	cache.len++
}

func (cache *LRUCache) decrLen() {
	cache.len--
}

func (cache *LRUCache) deleteNode(node *LRUCacheNode) {
	if node == nil {
		return
	}
	cache.hashmap[node.Key] = nil
	delete(cache.hashmap, node.Key)
	if cache.head == node {
		if cache.head.Next == nil {
			cache.head = nil
			cache.tail = nil
		} else {
			cache.head = cache.head.Next
			cache.head.Prev = nil
		}
		cache.decrLen()
		return
	}
	if cache.tail == node {
		cache.tail = cache.tail.Prev
		cache.decrLen()
		return
	}
	if node.Prev != nil {
		node.Prev.Next = node.Next
	}
	if node.Next != nil {
		node.Next.Prev = node.Prev
	}
	cache.decrLen()
}

func (cache *LRUCache) addNode(node *LRUCacheNode) {
	cache.hashmap[node.Key] = node
	if cache.head == nil {
		cache.head = node
		cache.tail = node
		cache.incrLen()
		return
	}
	cache.tail.Next = node
	node.Prev = cache.tail
	node.Next = nil
	cache.tail = node
	cache.incrLen()
}