package lru

import "container/list"

// Cache is a fixed-capacity least-recently-used cache.
// The zero value is not ready for use; create caches with New.
type Cache[K comparable, V any] struct {
	capacity int
	items    map[K]*list.Element
	order    *list.List
}

type entry[K comparable, V any] struct {
	key   K
	value V
}

// New creates an LRU cache that stores up to capacity items.
func New[K comparable, V any](capacity int) *Cache[K, V] {
	if capacity < 1 {
		capacity = 1
	}

	return &Cache[K, V]{
		capacity: capacity,
		items:    make(map[K]*list.Element),
		order:    list.New(),
	}
}

// Get returns the value for key and marks it as recently used.
func (c *Cache[K, V]) Get(key K) (V, bool) {
	if elem, ok := c.items[key]; ok {
		c.order.MoveToFront(elem)
		return elem.Value.(entry[K, V]).value, true
	}

	var zero V
	return zero, false
}

// Put inserts or updates a value and evicts the least recently used item
// when the cache grows beyond its capacity.
func (c *Cache[K, V]) Put(key K, value V) {
	if elem, ok := c.items[key]; ok {
		elem.Value = entry[K, V]{key: key, value: value}
		c.order.MoveToFront(elem)
		return
	}

	elem := c.order.PushFront(entry[K, V]{key: key, value: value})
	c.items[key] = elem

	if len(c.items) > c.capacity {
		c.evictOldest()
	}
}

// Delete removes key from the cache.
func (c *Cache[K, V]) Delete(key K) bool {
	elem, ok := c.items[key]
	if !ok {
		return false
	}

	c.order.Remove(elem)
	delete(c.items, key)
	return true
}

// Len returns the number of items currently stored.
func (c *Cache[K, V]) Len() int {
	return len(c.items)
}

func (c *Cache[K, V]) evictOldest() {
	elem := c.order.Back()
	if elem == nil {
		return
	}

	c.order.Remove(elem)
	delete(c.items, elem.Value.(entry[K, V]).key)
}