package lru

import (
	"container/list"
	"testing"
)

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

// 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 // Most recently used entries are at the front.
}

// New creates an LRU cache. Non-positive capacities create 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 recently used.
func (c *Cache[K, V]) Get(key K) (V, bool) {
	if element, ok := c.items[key]; ok {
		c.order.MoveToFront(element)
		return element.Value.(entry[K, V]).value, true
	}

	var zero V
	return zero, false
}

// Put inserts or updates a value, evicting the least-recently-used entry
// when the cache exceeds its capacity.
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()
		item := oldest.Value.(entry[K, V])
		delete(c.items, item.key)
		c.order.Remove(oldest)
	}
}

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

func TestCacheEvictsLeastRecentlyUsed(t *testing.T) {
	cache := New[string, int](2)
	cache.Put("a", 1)
	cache.Put("b", 2)

	if value, ok := cache.Get("a"); !ok || value != 1 {
		t.Fatalf("Get(a) = %d, %v; want 1, true", value, ok)
	}

	cache.Put("c", 3)

	if _, ok := cache.Get("b"); ok {
		t.Fatal("expected b to be evicted")
	}
	if value, ok := cache.Get("c"); !ok || value != 3 {
		t.Fatalf("Get(c) = %d, %v; want 3, true", value, ok)
	}
}

func TestCacheUpdatesExistingEntry(t *testing.T) {
	cache := New[string, int](1)
	cache.Put("a", 1)
	cache.Put("a", 2)

	if cache.Len() != 1 {
		t.Fatalf("Len() = %d; want 1", cache.Len())
	}
	if value, ok := cache.Get("a"); !ok || value != 2 {
		t.Fatalf("Get(a) = %d, %v; want 2, true", value, ok)
	}
}