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 that holds at most capacity entries.
func New[K comparable, V any](capacity int) *Cache[K, V] {
	if capacity < 0 {
		capacity = 0
	}
	return &Cache[K, V]{
		capacity: capacity,
		items:    make(map[K]*node[K, V]),
	}
}

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

// 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 and evicts 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 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)
	}
}

// Remove deletes a key if present.
func (c *Cache[K, V]) Remove(key K) bool {
	n, ok := c.items[key]
	if !ok {
		return false
	}

	c.remove(n)
	return true
}

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) {
	cache := New[string, int](2)

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

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

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

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

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