package lru

import "testing"

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

// Cache stores up to capacity items and evicts the least recently used item.
type Cache[K comparable, V any] struct {
	capacity   int
	items      map[K]*entry[K, V]
	head, tail *entry[K, V]
}

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]*entry[K, V]),
	}
}

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

// Put inserts or updates a value.
func (c *Cache[K, V]) Put(key K, value V) {
	if c.capacity == 0 {
		return
	}
	if node, ok := c.items[key]; ok {
		node.value = value
		c.moveToFront(node)
		return
	}

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

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

func (c *Cache[K, V]) Len() int {
	return len(c.items)
}

func (c *Cache[K, V]) moveToFront(node *entry[K, V]) {
	if node == c.head {
		return
	}
	c.remove(node)
	c.addToFront(node)
}

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

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

func TestCacheEvictsLeastRecentlyUsed(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 b to be evicted")
	}
	if value, ok := cache.Get("a"); !ok || value != 1 {
		t.Fatalf("expected a=1, got %d, %v", value, ok)
	}
}

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

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