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 cannot retain 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. It returns an evicted entry, if any.
func (c *Cache[K, V]) Put(key K, value V) (evictedKey K, evictedValue V, evicted bool) {
	if c.capacity <= 0 {
		return key, value, true
	}

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

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

	if c.order.Len() <= c.capacity {
		return evictedKey, evictedValue, false
	}

	oldest := c.order.Back()
	oldEntry := oldest.Value.(entry[K, V])
	delete(c.items, oldEntry.key)
	c.order.Remove(oldest)
	return oldEntry.key, oldEntry.value, true
}

// Remove deletes an entry and returns its former value.
func (c *Cache[K, V]) Remove(key K) (V, bool) {
	element, ok := c.items[key]
	if !ok {
		var zero V
		return zero, false
	}

	delete(c.items, key)
	c.order.Remove(element)
	return element.Value.(entry[K, V]).value, true
}

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

// Purge removes all entries.
func (c *Cache[K, V]) Purge() {
	clear(c.items)
	c.order.Init()
}