// Exercise 05 — LRU Cache
//
// ASSIGNMENT
// ----------
// Implement a thread-safe LRU cache:
//
//  1. NewLRU(capacity): holds at most `capacity` entries.
//  2. Get(key): returns (value, true) and marks the entry most-recently-used;
//     (nil, false) on miss.
//  3. Put(key, value): inserts or updates; updating also marks MRU.
//     When over capacity, evicts the LEAST recently used entry.
//  4. Both operations O(1). (Hint: map + container/list, or hand-roll a
//     doubly linked list.)
//  5. Safe for concurrent use (tests run with -race).
//
// Run the tests:   go test -race ./05-lru-cache/
package main

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

type entry struct {
	key string
	val any
}
type LRU struct {
	// TODO: fields (mutex, capacity, map[string]*list.Element, *list.List)
	// Remember: the list element must store the KEY too, or you can't
	// delete the map entry on eviction.
	mu       sync.Mutex
	capacity int
	lruList  *list.List
	kvMap    map[string]*list.Element
}

// NewLRU creates an LRU cache with the given capacity (capacity >= 1).
// TODO: implement me.
func NewLRU(capacity int) *LRU {
	return &LRU{capacity: capacity, lruList: list.New(), kvMap: make(map[string]*list.Element)}
}

// Get returns the value and whether it was present. Hit = mark MRU.
// TODO: implement me.
func (c *LRU) Get(key string) (any, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()

	if el, ok := c.kvMap[key]; ok {
		c.lruList.MoveToFront(el)
		return el.Value.(*entry).val, true
	}

	return nil, false
}

// Put inserts/updates a value, evicting the LRU entry if over capacity.
// TODO: implement me.
func (c *LRU) Put(key string, val any) {
	// lock mutex
	c.mu.Lock()
	defer c.mu.Unlock()
	// if key exists, update value and move it to the front of the list and return/quit
	if el, ok := c.kvMap[key]; ok {
		c.lruList.MoveToFront(el)
		el.Value.(*entry).val = val
		return
	}

	// if len > capacity, remove the last element from both the list and the map
	if c.lruList.Len() >= c.capacity {
		// remove last element from list
		lastEl := c.lruList.Back()
		c.lruList.Remove(lastEl)
		// remove it by key from map
		delete(c.kvMap, lastEl.Value.(*entry).key)
	}

	// if key doesn't exist, insert'
	el := c.lruList.PushFront(&entry{key: key, val: val})
	c.kvMap[key] = el

}

// Len returns the current number of entries.
// TODO: implement me.
func (c *LRU) Len() int {
	c.mu.Lock()
	defer c.mu.Unlock()
	return c.lruList.Len()
}

func main() {
	c := NewLRU(2)
	c.Put("a", 1)
	c.Put("b", 2)
	c.Get("a")    // a is now MRU
	c.Put("c", 3) // evicts b
	_, ok := c.Get("b")
	fmt.Println("b present:", ok) // false
}