LRU/lru_test.go

package lru

import (
	"sync"
	"testing"
)

func TestNewLRUCache(t *testing.T) {
	cache := NewLRUCache(5)
	if cache.capacity != 5 {
		t.Errorf("expected capacity 5, got %d", cache.capacity)
	}
	if cache.Len() != 0 {
		t.Errorf("expected empty cache, got length %d", cache.Len())
	}
}

func TestPutAndGet(t *testing.T) {
	cache := NewLRUCache(3)

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

	val, exists := cache.Get("a")
	if !exists || val != 1 {
		t.Errorf("expected (1, true), got (%v, %v)", val, exists)
	}

	val, exists = cache.Get("b")
	if !exists || val != 2 {
		t.Errorf("expected (2, true), got (%v, %v)", val, exists)
	}

	// Test miss
	val, exists = cache.Get("z")
	if exists {
		t.Errorf("expected (nil, false), got (%v, %v)", val, exists)
	}
}

func TestUpdateExistingKey(t *testing.T) {
	cache := NewLRUCache(2)

	cache.Put("a", 1)
	cache.Put("a", 10) // Update

	val, exists := cache.Get("a")
	if !exists || val != 10 {
		t.Errorf("expected (10, true), got (%v, %v)", val, exists)
	}

	if cache.Len() != 1 {
		t.Errorf("expected length 1, got %d", cache.Len())
	}
}

func TestEviction(t *testing.T) {
	cache := NewLRUCache(3)

	cache.Put("a", 1)
	cache.Put("b", 2)
	cache.Put("c", 3)
	cache.Put("d", 4) // Should evict "a"

	_, exists := cache.Get("a")
	if exists {
		t.Error("expected 'a' to be evicted")
	}

	val, exists := cache.Get("b")
	if !exists || val != 2 {
		t.Errorf("expected (2, true), got (%v, %v)", val, exists)
	}
}

func TestLRUOrdering(t *testing.T) {
	cache := NewLRUCache(3)

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

	// Access "a" to make it recently used
	cache.Get("a")

	// Add "d", should evict "b" (least recently used)
	cache.Put("d", 4)

	_, exists := cache.Get("b")
	if exists {
		t.Error("expected 'b' to be evicted")
	}

	// Verify others still exist
	val, exists := cache.Get("a")
	if !exists || val != 1 {
		t.Errorf("expected (1, true), got (%v, %v)", val, exists)
	}

	val, exists = cache.Get("c")
	if !exists || val != 3 {
		t.Errorf("expected (3, true), got (%v, %v)", val, exists)
	}

	val, exists = cache.Get("d")
	if !exists || val != 4 {
		t.Errorf("expected (4, true), got (%v, %v)", val, exists)
	}
}

func TestUpdateMakesRecent(t *testing.T) {
	cache := NewLRUCache(3)

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

	// Update "a" to make it recently used
	cache.Put("a", 10)

	// Add "d", should evict "b"
	cache.Put("d", 4)

	_, exists := cache.Get("b")
	if exists {
		t.Error("expected 'b' to be evicted")
	}

	val, exists := cache.Get("a")
	if !exists || val != 10 {
		t.Errorf("expected (10, true), got (%v, %v)", val, exists)
	}
}

func TestClear(t *testing.T) {
	cache := NewLRUCache(3)

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

	cache.Clear()

	if cache.Len() != 0 {
		t.Errorf("expected empty cache after clear, got length %d", cache.Len())
	}

	_, exists := cache.Get("a")
	if exists {
		t.Error("expected cache to be empty after clear")
	}
}

func TestSingleCapacity(t *testing.T) {
	cache := NewLRUCache(1)

	cache.Put("a", 1)
	cache.Put("b", 2) // Should evict "a"

	_, exists := cache.Get("a")
	if exists {
		t.Error("expected 'a' to be evicted")
	}

	val, exists := cache.Get("b")
	if !exists || val != 2 {
		t.Errorf("expected (2, true), got (%v, %v)", val, exists)
	}
}

func TestDifferentTypes(t *testing.T) {
	cache := NewLRUCache(3)

	// Test with different key/value types
	cache.Put(1, "one")
	cache.Put("two", 2)
	cache.Put(3.14, []int{1, 2, 3})

	val, exists := cache.Get(1)
	if !exists || val != "one" {
		t.Errorf("expected ('one', true), got (%v, %v)", val, exists)
	}

	val, exists = cache.Get("two")
	if !exists || val != 2 {
		t.Errorf("expected (2, true), got (%v, %v)", val, exists)
	}

	val, exists = cache.Get(3.14)
	if !exists {
		t.Errorf("expected slice value, got (%v, %v)", val, exists)
	}
}

func TestConcurrentAccess(t *testing.T) {
	cache := NewLRUCache(100)
	var wg sync.WaitGroup

	// Concurrent puts
	for i := range 50 {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			cache.Put(i, i*10)
		}(i)
	}

	// Concurrent gets
	for i := range 50 {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			cache.Get(i)
		}(i)
	}

	// Concurrent updates
	for i := range 25 {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			cache.Put(i, i*100)
		}(i)
	}

	// Concurrent len checks
	for range 10 {
		wg.Add(1)
		go func() {
			defer wg.Done()
			cache.Len()
		}()
	}

	// Concurrent clear
	wg.Add(1)
	go func() {
		defer wg.Done()
		cache.Clear()
	}()

	wg.Wait()
}

func TestRaceCondition(t *testing.T) {
	cache := NewLRUCache(10)
	done := make(chan bool)

	go func() {
		for i := range 1000 {
			cache.Put(i%10, i)
		}
		done <- true
	}()

	go func() {
		for i := range 1000 {
			cache.Get(i % 10)
		}
		done <- true
	}()

	<-done
	<-done
}

func BenchmarkPut(b *testing.B) {
	cache := NewLRUCache(1000)

	for i := 0; b.Loop(); i++ {
		cache.Put(i%1000, i)
	}
}

func BenchmarkGet(b *testing.B) {
	cache := NewLRUCache(1000)
	for i := range 1000 {
		cache.Put(i, i)
	}

	for i := 0; b.Loop(); i++ {
		cache.Get(i % 1000)
	}
}