package main

// BiListNode ...
type BiListNode struct {
	Key  int
	Val  int
	Prev *BiListNode
	Next *BiListNode
}

// LRUCache ...
type LRUCache struct {
	Cap   int
	Size  int
	Head  *BiListNode
	Tail  *BiListNode
	Cache map[int]*BiListNode
}

// Constructor ...
func Constructor(capacity int) (cache LRUCache) {
	cache.Cap, cache.Size = capacity, 0
	cache.Cache = make(map[int]*BiListNode)
	return
}

// Get ...
func (cache *LRUCache) Get(key int) int {
	if node, ok := cache.Cache[key]; ok {
		if node != cache.Head {
			if node == cache.Tail {
				cache.Tail = cache.Tail.Prev
			}
			// Delete node
			if node.Next != nil {
				node.Next.Prev = node.Prev
			}
			node.Prev.Next = node.Next
			// node is the new Head
			node.Prev = nil
			node.Next = cache.Head
			cache.Head.Prev = node
			cache.Head = node
			// Update Tail
			if cache.Tail == nil {
				cache.Tail = cache.Head
			}
		}
		return node.Val
	}
	return -1
}

// Put ...
func (cache *LRUCache) Put(key int, value int) {
	if node, ok := cache.Cache[key]; ok {
		if node != cache.Head {
			if node == cache.Tail {
				cache.Tail = cache.Tail.Prev
			}
			// Delete node
			if node.Next != nil {
				node.Next.Prev = node.Prev
			}
			node.Prev.Next = node.Next
			// node is the new Head
			node.Prev = nil
			node.Next = cache.Head
			cache.Head.Prev = node
			cache.Head = node
			// Update Tail
			if cache.Tail == nil {
				cache.Tail = cache.Head
			}
		}
		cache.Head.Val = value
	} else {
		node := &BiListNode{key, value, nil, cache.Head}
		if cache.Size == 0 {
			cache.Tail = node
		} else {
			cache.Head.Prev = node
		}
		cache.Head = node
		cache.Size++
		if cache.Size > cache.Cap {
			delete(cache.Cache, cache.Tail.Key)
			cache.Tail = cache.Tail.Prev
			cache.Tail.Next = nil
			cache.Size--
		}
		cache.Cache[key] = cache.Head
	}
}

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

// func main() {
// 	cache := Constructor(2 /* capacity */)
// 	cache.Put(1, 1)
// 	cache.Put(2, 2)
// 	println(cache.Get(1)) // returns 1
// 	cache.Put(3, 3)       // evicts key 2
// 	println(cache.Get(2)) // returns -1 (not found)
// 	cache.Put(4, 4)       // evicts key 1
// 	println(cache.Get(1)) // returns -1 (not found)
// 	println(cache.Get(3)) // returns 3
// 	println(cache.Get(4)) // returns 4
// }