// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

type LRUCache struct {
	capacity   int
	head, tail *Node
	values     map[int]*Node
}

type Node struct {
	key, value int
	prev, next *Node
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		values:   map[int]*Node{},
		capacity: capacity,
	}
}

func (lr *LRUCache) Get(key int) int {
	node, ok := lr.values[key]
	if !ok {
		return -1
	}
	lr.moveToLast(node)
	return node.value
}

func (lr *LRUCache) moveToLast(node *Node) {
	if node == lr.tail {
		return
	}
	if node == lr.head {
		lr.head = lr.head.next
		lr.head.prev = nil
	} else {
		node.prev.next = node.next
		node.next.prev = node.prev
	}
	lr.tail.next = node
	node.prev = lr.tail
	lr.tail = lr.tail.next
	lr.tail.next = nil
}

func (lr *LRUCache) Put(key int, value int) {
	if _, ok := lr.values[key]; ok {
		lr.values[key].value = value
		lr.moveToLast(lr.values[key])
		return
	}
	if len(lr.values) < lr.capacity {
		lr.append(key, value)
		return
	}
	node := lr.head
	lr.moveToLast(node)
	delete(lr.values, node.key)

	lr.values[key] = node
	node.key = key
	node.value = value
}

func (lr *LRUCache) append(key, value int) {
	node := &Node{
		key:   key,
		value: value,
	}
	if lr.tail == nil {
		lr.tail = node
		lr.head = node
	} else {
		lr.tail.next = node
		node.prev = lr.tail
		lr.tail = node
	}
	lr.values[key] = node
}

func main() {
	obj := Constructor(2)
	obj.Put(5, 88)
	res := obj.Get(5)
	fmt.Println(res)
}

//$ go run interview3-7.go
//88