package cache

type node struct {
	previous *node
	next     *node
	key      interface{}
	value    interface{}
}

type list struct {
	head *node
	tail *node
}

func (l *list) remove(n *node) *node {
	prev := n.previous
	next := n.next
	if prev == nil {
		l.head = next
	} else {
	prev.next = next
	}
	if next == nil {
		l.tail = prev
	} else {
		next.previous = prev
	}

	n.next = nil
	n.previous = nil
	return n
}

func (l *list) push(n *node) {
	n.next = nil
	n.previous = nil
	n.next = l.head
	if l.head != nil {
		l.head.previous = n
	}
	l.head = n
	if l.tail == nil {
		l.tail = n
	}
}

type LRU struct {
	lookup map[interface{}]*node
	size   int
	nodes  *list
}

func NewLRU(size int) *LRU {
	return &LRU{
		lookup: make(map[interface{}]*node),
		nodes: &list{},
		size:  size,
	}
}

func (l *LRU) Put(key, value interface{}) {
	n := &node{
		key:   key,
		value: value,
	}
	if oldN, ok := l.lookup[key]; ok {
		l.nodes.remove(oldN)
		l.lookup[key] = n
		l.nodes.push(n)
		return
	}
	if len(l.lookup) >= l.size {
		oldN := l.nodes.tail
		l.nodes.remove(oldN)
		delete(l.lookup, oldN.key)
	}

	l.lookup[key] = n
	l.nodes.push(n)
	return
}

func (l *LRU) Get(key interface{}) (interface{}, bool) {
	n, ok := l.lookup[key]
	if !ok {
		return nil, false
	}

	l.nodes.remove(n)
	l.nodes.push(n)
	return n.value, true
}