Head (MRU) ← → ... ← → Tail (LRU)
  [key3]           [key1]
  (baru diakses)   (paling lama tidak diakses)

Kalau cache penuh → evict Tail
Kalau akses key1 → pindahin key1 ke Head

package lru

import (
    "container/list"
    "sync"
)

// Cache is a thread-safe LRU cache.
type Cache struct {
    mu       sync.Mutex
    capacity int
    items    map[string]*list.Element // key → node in eviction list
    evictList *list.List               // doubly linked list (most recent → least recent)
}

type entry struct {
    key   string
    value interface{}
}

func New(capacity int) *Cache {
    return &Cache{
        capacity:  capacity,
        items:     make(map[string]*list.Element, capacity),
        evictList: list.New(),
    }
}

func (c *Cache) Get(key string) (interface{}, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()

    elem, ok := c.items[key]
    if !ok {
        return nil, false
    }

    // Move to front (most recently used)
    c.evictList.MoveToFront(elem)

    return elem.Value.(*entry).value, true
}

func (c *Cache) Put(key string, value interface{}) {
    c.mu.Lock()
    defer c.mu.Unlock()

    // Update existing
    if elem, ok := c.items[key]; ok {
        c.evictList.MoveToFront(elem)
        elem.Value.(*entry).value = value
        return
    }

    // Add new
    elem := c.evictList.PushFront(&entry{key: key, value: value})
    c.items[key] = elem

    // Evict if over capacity
    if c.evictList.Len() > c.capacity {
        c.evict()
    }
}

func (c *Cache) evict() {
    // Remove from back (least recently used)
    elem := c.evictList.Back()
    if elem == nil {
        return
    }

    c.evictList.Remove(elem)
    delete(c.items, elem.Value.(*entry).key)
}

func (c *Cache) Len() int {
    c.mu.Lock()
    defer c.mu.Unlock()
    return c.evictList.Len()
}

func (c *Cache) Remove(key string) {
    c.mu.Lock()
    defer c.mu.Unlock()

    if elem, ok := c.items[key]; ok {
        c.evictList.Remove(elem)
        delete(c.items, key)
    }
}

type node struct {
    key   string
    value interface{}
    prev  *node
    next  *node
}

type Cache struct {
    mu       sync.Mutex
    capacity int
    items    map[string]*node
    head     *node // most recently used
    tail     *node // least recently used
}

func (c *Cache) moveToFront(n *node) {
    if c.head == n {
        return // already at front
    }

    // Remove from current position
    if n.prev != nil {
        n.prev.next = n.next
    }
    if n.next != nil {
        n.next.prev = n.prev
    }
    if c.tail == n {
        c.tail = n.prev
    }

    // Insert at front
    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) addToFront(n *node) {
    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) removeTail() {
    if c.tail == nil {
        return
    }
    delete(c.items, c.tail.key)

    if c.tail.prev != nil {
        c.tail.prev.next = nil
    }
    c.tail = c.tail.prev

    if c.tail == nil {
        c.head = nil
    }
}

func TestCache_Basic(t *testing.T) {
    c := New(2)

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

    v, ok := c.Get("a")
    assert.True(t, ok)
    assert.Equal(t, 1, v)

    // Evicts "b" (LRU)
    c.Put("c", 3)

    _, ok = c.Get("b")
    assert.False(t, ok, "b should be evicted")
}

func TestCache_UpdateExisting(t *testing.T) {
    c := New(2)

    c.Put("a", 1)
    c.Put("a", 100) // update

    v, _ := c.Get("a")
    assert.Equal(t, 100, v)
    assert.Equal(t, 1, c.Len()) // still 1 item
}

func TestCache_Concurrent(t *testing.T) {
    c := New(100)
    var wg sync.WaitGroup

    for i := 0; i < 1000; i++ {
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            key := fmt.Sprintf("key-%d", i%50)
            c.Put(key, i)
            c.Get(key)
        }(i)
    }
    wg.Wait()

    // Should not panic (no concurrent map writes)
    assert.LessOrEqual(t, c.Len(), 100)
}

type ShardedCache struct {
    shards    []*Cache
    shardMask uint32
}

func NewSharded(shardCount int, capacityPerShard int) *ShardedCache {
    // shardCount harus power of 2
    shards := make([]*Cache, shardCount)
    for i := range shards {
        shards[i] = New(capacityPerShard)
    }
    return &ShardedCache{
        shards:    shards,
        shardMask: uint32(shardCount - 1),
    }
}

func (s *ShardedCache) getShard(key string) *Cache {
    h := fnv.New32a()
    h.Write([]byte(key))
    return s.shards[h.Sum32()&s.shardMask]
}

func (s *ShardedCache) Get(key string) (interface{}, bool) {
    return s.getShard(key).Get(key)
}

func (s *ShardedCache) Put(key string, value interface{}) {
    s.getShard(key).Put(key, value)
}