type biNode struct {
	key  int
	val  int
	prev *biNode
	next *biNode
}

type LRUCache struct {
	capacity int
	size     int
	cache    map[int]*biNode
	head     *biNode
	tail     *biNode
}

func Constructor(capacity int) LRUCache {
	var lru LRUCache
	lru.capacity = capacity
	lru.cache = make(map[int]*biNode)
	return lru
}

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

func (this *LRUCache) Put(key int, value int) {
	if node, ok := this.cache[key]; ok {
		node.val = value
		this.moveToHead(node)
		return
	} // Already exsist, update value & move to head
	newHead := &biNode{key, value, nil, this.head}
	if this.size == 0 {
		this.head = newHead
		this.tail = newHead
	} else {
		this.head.prev = newHead
		this.head = newHead
	}
	this.cache[key] = this.head
	this.size++                    // Not exsist, add new head
	if this.size > this.capacity { // Remove tail
		this.size--
		delete(this.cache, this.tail.key)
		this.tail = this.tail.prev
		if this.tail == nil {
			this.head = nil
		} else {
			this.tail.next = nil
		}
	}
}

func (this *LRUCache) moveToHead(node *biNode) {
	if node == this.head {
		return
	}
	if node == this.tail {
		this.tail.next = this.head
		this.head.prev = this.tail
		this.head = this.tail
		this.tail = this.tail.prev
		this.tail.next = nil
		this.head.prev = nil
		return
	}
	prev, next := node.prev, node.next
	next.prev = prev
	prev.next = next
	node.prev = nil
	node.next = this.head
	this.head.prev = node
	this.head = node
}

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