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. Non-positive capacities produce a cache
// that stores no entries.
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 entry 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. If the cache exceeds its capacity,
// the least recently used entry is evicted.
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]).value = value
		c.order.MoveToFront(element)
		return
	}

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

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

// Delete removes 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
}

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