LRU Cache with TTL and Automatic Eviction

package main

import (
	"container/list"
	"fmt"
	"sync"
	"time"
)

// CacheEntry represents a single entry in the LRU cache
type CacheEntry struct {
	key        string
	value      interface{}
	expiresAt  time.Time
	lastAccessed time.Time
}

// LRUCache is a thread-safe LRU cache with TTL support
type LRUCache struct {
	mu           sync.RWMutex
	capacity     int
	defaultTTL   time.Duration
	items        map[string]*list.Element
	order        *list.List
	hitCount     int64
	missCount    int64
	stopEviction chan struct{}
}

// NewLRUCache creates a new LRU cache with specified capacity and default TTL
func NewLRUCache(capacity int, defaultTTL time.Duration) *LRUCache {
	cache := &LRUCache{
		capacity:     capacity,
		defaultTTL:   defaultTTL,
		items:        make(map[string]*list.Element),
		order:        list.New(),
		stopEviction: make(chan struct{}),
	}

	// Start background eviction goroutine
	go cache.startEvictionWorker(1 * time.Minute)

	return cache
}

// startEvictionWorker periodically removes expired entries
func (c *LRUCache) startEvictionWorker(interval time.Duration) {
	ticker := time.NewTicker(interval)
	defer ticker.Stop()

	for {
		select {
		case <-ticker.C:
			c.EvictExpired()
		case <-c.stopEviction:
			return
		}
	}
}

// Set adds or updates an entry in the cache with the default TTL
func (c *LRUCache) Set(key string, value interface{}) {
	c.SetWithTTL(key, value, c.defaultTTL)
}

// SetWithTTL adds or updates an entry in the cache with a custom TTL
func (c *LRUCache) SetWithTTL(key string, value interface{}, ttl time.Duration) {
	c.mu.Lock()
	defer c.mu.Unlock()

	// Check if key already exists
	if elem, exists := c.items[key]; exists {
		// Update existing entry
		c.order.MoveToFront(elem)
		entry := elem.Value.(*CacheEntry)
		entry.value = value
		entry.expiresAt = time.Now().Add(ttl)
		entry.lastAccessed = time.Now()
		return
	}

	// Evict least recently used entry if at capacity
	if c.order.Len() >= c.capacity {
		c.evictLRU()
	}

	// Create new entry
	entry := &CacheEntry{
		key:        key,
		value:      value,
		expiresAt:  time.Now().Add(ttl),
		lastAccessed: time.Now(),
	}
	elem := c.order.PushFront(entry)
	c.items[key] = elem
}

// Get retrieves an entry from the cache (updates access time)
func (c *LRUCache) Get(key string) (interface{}, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()

	if elem, exists := c.items[key]; exists {
		entry := elem.Value.(*CacheEntry)

		// Check if entry is expired
		if time.Now().After(entry.expiresAt) {
			c.removeElement(elem)
			c.missCount++
			return nil, false
		}

		// Update access time and move to front
		entry.lastAccessed = time.Now()
		c.order.MoveToFront(elem)
		c.hitCount++
		return entry.value, true
	}

	c.missCount++
	return nil, false
}

// Delete removes an entry from the cache
func (c *LRUCache) Delete(key string) {
	c.mu.Lock()
	defer c.mu.Unlock()

	if elem, exists := c.items[key]; exists {
		c.removeElement(elem)
	}
}

// EvictExpired removes all expired entries from the cache
func (c *LRUCache) EvictExpired() {
	c.mu.Lock()
	defer c.mu.Unlock()

	now := time.Now()
	for elem := c.order.Back(); elem != nil; {
		nextElem := elem.Prev()
		entry := elem.Value.(*CacheEntry)

		if now.After(entry.expiresAt) {
			c.removeElement(elem)
		}

		elems = nextElem
	}
}

// evictLRU removes the least recently used entry
func (c *LRUCache) evictLRU() {
	if elem := c.order.Back(); elem != nil {
		c.removeElement(elem)
	}
}

// removeElement removes an element from the cache and order list
func (c *LRUCache) removeElement(elem *list.Element) {
	entry := elem.Value.(*CacheEntry)
	delete(c.items, entry.key)
	c.order.Remove(elem)
}

// Stats returns cache statistics (hits, misses, size)
func (c *LRUCache) Stats() (hits, misses, size int64) {
	c.mu.RLock()
	defer c.mu.RUnlock()
	return c.hitCount, c.missCount, int64(c.order.Len())
}

// Close stops the background eviction worker and clears the cache
func (c *LRUCache) Close() {
	close(c.stopEviction)
	c.mu.Lock()
	defer c.mu.Unlock()
	c.items = make(map[string]*list.Element)
	c.order = list.New()
	c.hitCount = 0
	c.missCount = 0
}

func main() {
	// Create cache with capacity 5 and default TTL 10 seconds
	cache := NewLRUCache(5, 10*time.Second)
	defer cache.Close()

	// Add entries
	cache.Set("user:1", map[string]string{"name": "Alice", "email": "[email protected]"})
	cache.Set("user:2", map[string]string{"name": "Bob", "email": "[email protected]"})

	// Retrieve entry
	if val, ok := cache.Get("user:1"); ok {
		fmt.Printf("Found user: %v\n", val)
	}

	// Add entry with custom TTL
	cache.SetWithTTL("temp:data", "short-lived-value", 2*time.Second)

	// Wait for expiration
	time.Sleep(3 * time.Second)

	// Try to get expired entry
	if _, ok := cache.Get("temp:data"); !ok {
		fmt.Println("temp:data has expired")
	}

	// Print stats
	hits, misses, size := cache.Stats()
	fmt.Printf("Cache Stats - Hits: %d, Misses: %d, Size: %d\n", hits, misses, size)
}