package lru

import "testing"

// Cache is a fixed-capacity least-recently-used cache.
type Cache[K comparable, V any] struct {
	capacity int
	items    map[K]*node[K, V]
	head     *node[K, V]
	tail     *node[K, V]
}

type node[K comparable, V any] struct {
	key        K
	value      V
	prev, next *node[K, V]
}

// New creates an LRU cache. Capacity must be positive.
func New[K comparable, V any](capacity int) *Cache[K, V] {
	if capacity <= 0 {
		panic("lru: capacity must be positive")
	}
	return &Cache[K, V]{
		capacity: capacity,
		items:    make(map[K]*node[K, V], capacity),
	}
}

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

// Put inserts or updates a value, evicting the least-recently-used item if full.
func (c *Cache[K, V]) Put(key K, value V) {
	if n, ok := c.items[key]; ok {
		n.value = value
		c.moveToFront(n)
		return
	}

	n := &node[K, V]{key: key, value: value}
	c.items[key] = n
	c.pushFront(n)

	if len(c.items) > c.capacity {
		c.remove(c.tail)
	}
}

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

func (c *Cache[K, V]) moveToFront(n *node[K, V]) {
	if n == c.head {
		return
	}
	c.unlink(n)
	c.pushFront(n)
}

func (c *Cache[K, V]) pushFront(n *node[K, V]) {
	n.prev = nil
	n.next = c.head
	if c.head != nil {
		c.head.prev = n
	}
	c.head = n
	if c.tail == nil {
		c.tail = n
	}
}

func (c *Cache[K, V]) remove(n *node[K, V]) {
	if n == nil {
		return
	}
	c.unlink(n)
	delete(c.items, n.key)
}

func (c *Cache[K, V]) unlink(n *node[K, V]) {
	if n.prev != nil {
		n.prev.next = n.next
	} else {
		c.head = n.next
	}
	if n.next != nil {
		n.next.prev = n.prev
	} else {
		c.tail = n.prev
	}
	n.prev = nil
	n.next = nil
}

func TestCacheEvictsLeastRecentlyUsed(t *testing.T) {
	c := New[string, int](2)

	c.Put("a", 1)
	c.Put("b", 2)
	c.Put("c", 3)

	if _, ok := c.Get("a"); ok {
		t.Fatal("expected a to be evicted")
	}
	if got, ok := c.Get("b"); !ok || got != 2 {
		t.Fatalf("expected b=2, got %v, ok=%v", got, ok)
	}
	if got, ok := c.Get("c"); !ok || got != 3 {
		t.Fatalf("expected c=3, got %v, ok=%v", got, ok)
	}
}

func TestCacheGetRefreshesUsage(t *testing.T) {
	c := New[string, int](2)

	c.Put("a", 1)
	c.Put("b", 2)
	if _, ok := c.Get("a"); !ok {
		t.Fatal("expected a to exist")
	}
	c.Put("c", 3)

	if _, ok := c.Get("b"); ok {
		t.Fatal("expected b to be evicted")
	}
	if got, ok := c.Get("a"); !ok || got != 1 {
		t.Fatalf("expected a=1, got %v, ok=%v", got, ok)
	}
}