package lru

import (
	"sync"
)

type node struct {
	key, value any
	prev, next *node
}

type LRUCache struct {
	capacity int
	cache    map[any]*node
	head     *node
	tail     *node
	mu       sync.RWMutex
}

func NewLRUCache(capacity int) *LRUCache {
	head := &node{}
	tail := &node{}
	head.next = tail
	tail.prev = head

	return &LRUCache{
		capacity: capacity,
		cache:    make(map[any]*node, capacity),
		head:     head,
		tail:     tail,
	}
}

func (lru *LRUCache) Get(key any) (any, bool) {
	lru.mu.Lock()
	defer lru.mu.Unlock()

	if node, exists := lru.cache[key]; exists {
		lru.moveToHead(node)
		return node.value, true
	}
	return nil, false
}

func (lru *LRUCache) Put(key, value any) {
	lru.mu.Lock()
	defer lru.mu.Unlock()

	if node, exists := lru.cache[key]; exists {
		node.value = value
		lru.moveToHead(node)
		return
	}

	newNode := &node{key: key, value: value}
	lru.cache[key] = newNode
	lru.addToHead(newNode)

	if len(lru.cache) > lru.capacity {
		removed := lru.removeTail()
		delete(lru.cache, removed.key)
	}
}

func (lru *LRUCache) moveToHead(node *node) {
	lru.removeNode(node)
	lru.addToHead(node)
}

func (lru *LRUCache) removeNode(node *node) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (lru *LRUCache) addToHead(node *node) {
	node.prev = lru.head
	node.next = lru.head.next
	lru.head.next.prev = node
	lru.head.next = node
}

func (lru *LRUCache) removeTail() *node {
	node := lru.tail.prev
	lru.removeNode(node)
	return node
}

func (lru *LRUCache) Len() int {
	lru.mu.RLock()
	defer lru.mu.RUnlock()
	return len(lru.cache)
}

func (lru *LRUCache) Clear() {
	lru.mu.Lock()
	defer lru.mu.Unlock()
	lru.cache = make(map[any]*node, lru.capacity)
	lru.head.next = lru.tail
	lru.tail.prev = lru.head
}