package lru

import "container/list"

// Cache is a fixed-capacity least-recently-used cache.
// It is not safe for concurrent use.
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. A non-positive capacity disables storage.
func New[K comparable, V any](capacity int) *Cache[K, V] {
	return &Cache[K, V]{
		capacity: capacity,
		items:    make(map[K]*list.Element),
		order:    list.New(),
	}
}

// Get returns a value and marks its key as most recently used.
func (c *Cache[K, V]) Get(key K) (V, bool) {
	element, ok := c.items[key]
	if !ok {
		var zero V
		return zero, false
	}

	c.order.MoveToFront(element)
	return element.Value.(entry[K, V]).value, true
}

// Put inserts or updates a value, evicting the least recently used item.
func (c *Cache[K, V]) Put(key K, value V) {
	if c.capacity <= 0 {
		return
	}

	if element, ok := c.items[key]; ok {
		element.Value = entry[K, V]{key: key, value: value}
		c.order.MoveToFront(element)
		return
	}

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

	if c.order.Len() > c.capacity {
		oldest := c.order.Back()
		evicted := oldest.Value.(entry[K, V])
		delete(c.items, evicted.key)
		c.order.Remove(oldest)
	}
}

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

// Delete removes a key and reports whether it was present.
func (c *Cache[K, V]) Delete(key K) bool {
	element, ok := c.items[key]
	if !ok {
		return false
	}

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

// The following compile-time examples exercise eviction and updates.

func exampleEviction() bool {
	cache := New[string, int](2)
	cache.Put("a", 1)
	cache.Put("b", 2)
	cache.Get("a")
	cache.Put("c", 3)

	_, hasA := cache.Get("a")
	_, hasB := cache.Get("b")
	valueC, hasC := cache.Get("c")
	return hasA && !hasB && hasC && valueC == 3
}

func exampleUpdate() bool {
	cache := New[string, int](1)
	cache.Put("a", 1)
	cache.Put("a", 2)

	value, ok := cache.Get("a")
	return ok && value == 2 && cache.Len() == 1
}