--[[
============================================================================
ETB v12.37.1 - LRUCache.lua
============================================================================
Bounded LRU (Least Recently Used) cache — true O(1) implementation.

Uses a doubly-linked list (via two hashmaps) threaded through the keyspace,
plus the existing data hashmap for values. Every operation is constant-time:
  - Get(key):    O(1) — hash lookup + unlink + pushFront
  - Set(key):    O(1) — hash lookup + unlink/pushFront, or pushFront + evict
  - Remove(key): O(1) — hash lookup + unlink
  - Has(key):    O(1) — hash lookup

Prior implementation (v12.37.0) was O(n) per operation because Get/Set
linearly scanned self.order array and then did table.remove() which shifts
the tail. With maxSize=500, every cache hit could do ~500 comparisons + a
500-element array shift. This version removes both costs.

Public API is identical to v12.37.0. No call sites need to change.
============================================================================
]]--

local ADDON_NAME, NS = ...
local ETB = NS.ETB

-- Sentinel keys for the linked list head and tail. Chosen to never collide
-- with real keys (all current consumers use numeric itemIDs or numeric hashes).
local HEAD = "__ETB_LRU_HEAD__"
local TAIL = "__ETB_LRU_TAIL__"

local LRUCache = {}
LRUCache.__index = LRUCache

-- ============================================================================
-- Constructor
-- ============================================================================

function LRUCache:New(maxSize, name)
    local cache = setmetatable({}, LRUCache)
    cache.maxSize = maxSize or 500
    cache.name = name or "LRUCache"
    cache.data = {}          -- key -> value
    cache.prev = {}          -- key -> predecessor key (toward HEAD/MRU)
    cache.next = {}          -- key -> successor key (toward TAIL/LRU)
    cache.size = 0
    cache.hits = 0
    cache.misses = 0
    -- Initialize empty list: HEAD <-> TAIL
    cache.next[HEAD] = TAIL
    cache.prev[TAIL] = HEAD
    return cache
end

-- ============================================================================
-- Internal linked-list helpers — all O(1)
-- ============================================================================

-- Remove key from its current position in the list.
-- Caller must ensure the key is in the list.
function LRUCache:_unlink(key)
    local p = self.prev[key]
    local n = self.next[key]
    self.next[p] = n
    self.prev[n] = p
    self.prev[key] = nil
    self.next[key] = nil
end

-- Insert key at the front of the list (adjacent to HEAD, i.e. MRU position).
function LRUCache:_pushFront(key)
    local first = self.next[HEAD]
    self.next[HEAD] = key
    self.prev[key] = HEAD
    self.next[key] = first
    self.prev[first] = key
end

-- Move key to the front of the list (mark as MRU).
-- Caller must ensure the key is in the list.
function LRUCache:_moveToFront(key)
    -- Optimization: if already at front, nothing to do.
    if self.prev[key] == HEAD then return end
    self:_unlink(key)
    self:_pushFront(key)
end

-- Remove and return the LRU key (the one adjacent to TAIL).
-- Returns nil if the list is empty.
function LRUCache:_popBack()
    local last = self.prev[TAIL]
    if last == HEAD then return nil end  -- list is empty
    self:_unlink(last)
    return last
end

-- ============================================================================
-- Public API — matches v12.37.0 surface exactly
-- ============================================================================

function LRUCache:Get(key)
    local value = self.data[key]
    if value ~= nil then
        self.hits = self.hits + 1
        self:_moveToFront(key)
        return value
    end
    self.misses = self.misses + 1
    return nil
end

function LRUCache:Set(key, value)
    if self.data[key] ~= nil then
        -- Update existing: overwrite value, mark as MRU.
        self.data[key] = value
        self:_moveToFront(key)
    else
        -- Add new: evict LRU if at capacity, then push front.
        if self.size >= self.maxSize then
            local evicted = self:_popBack()
            if evicted then
                self.data[evicted] = nil
                self.size = self.size - 1
            end
        end
        self.data[key] = value
        self:_pushFront(key)
        self.size = self.size + 1
    end
end

function LRUCache:Has(key)
    return self.data[key] ~= nil
end

function LRUCache:Remove(key)
    if self.data[key] ~= nil then
        self.data[key] = nil
        self:_unlink(key)
        self.size = self.size - 1
        return true
    end
    return false
end

function LRUCache:Clear()
    wipe(self.data)
    wipe(self.prev)
    wipe(self.next)
    self.size = 0
    -- Re-establish empty list sentinels
    self.next[HEAD] = TAIL
    self.prev[TAIL] = HEAD
    -- Note: hits/misses counters preserved across Clear() — matches prior
    -- behavior and lets /etb stats show cumulative lifetime statistics.
end

function LRUCache:GetStats()
    return {
        name = self.name,
        size = self.size,
        maxSize = self.maxSize,
        hits = self.hits,
        misses = self.misses,
        hitRate = self.hits + self.misses > 0 and
                  (self.hits / (self.hits + self.misses) * 100) or 0,
    }
end

-- ============================================================================
-- Export
-- ============================================================================

ETB.LRUCache = LRUCache

function ETB:CreateLRUCache(maxSize, name)
    return LRUCache:New(maxSize, name)
end

-- ============================================================================
-- Self-test (debug-only) — verifies O(1) semantics and eviction order.
-- Runs once at file load when ETB.debug is true.
-- ============================================================================

if ETB.debug then
    local function _selfTest()
        -- Case 1: basic set/get
        local c = LRUCache:New(3, "selftest")
        c:Set(1, "a")
        c:Set(2, "b")
        c:Set(3, "c")
        assert(c:Get(1) == "a", "selftest-1: expected 'a' for key 1")
        assert(c:Get(2) == "b", "selftest-2: expected 'b' for key 2")
        assert(c:Get(3) == "c", "selftest-3: expected 'c' for key 3")
        assert(c.size == 3, "selftest-4: expected size=3")

        -- Case 2: eviction at capacity
        c:Set(4, "d")  -- should evict key 1 (LRU after the Get sequence above)
        -- After the Gets, order from MRU to LRU was: 3, 2, 1.
        -- Then Set(4) pushes 4 to front and evicts 1 from back.
        -- Order is now: 4, 3, 2.
        assert(c:Has(1) == false, "selftest-5: key 1 should be evicted")
        assert(c:Has(2) == true,  "selftest-6: key 2 should remain")
        assert(c:Has(3) == true,  "selftest-7: key 3 should remain")
        assert(c:Has(4) == true,  "selftest-8: key 4 should be present")
        assert(c.size == 3, "selftest-9: expected size=3 after eviction")

        -- Case 3: Get promotes to MRU
        c:Get(2)  -- 2 becomes MRU. Order: 2, 4, 3.
        c:Set(5, "e")  -- evicts 3 (LRU). Order: 5, 2, 4.
        assert(c:Has(3) == false, "selftest-10: key 3 should be evicted after Get(2)")
        assert(c:Has(2) == true,  "selftest-11: key 2 should remain (was promoted)")

        -- Case 4: Remove
        local removed = c:Remove(4)
        assert(removed == true, "selftest-12: Remove returned true")
        assert(c:Has(4) == false, "selftest-13: key 4 gone")
        assert(c.size == 2, "selftest-14: size decremented")
        assert(c:Remove(999) == false, "selftest-15: Remove of missing key returns false")

        -- Case 5: overwrite promotes to MRU
        local c2 = LRUCache:New(3, "selftest2")
        c2:Set(1, "a"); c2:Set(2, "b"); c2:Set(3, "c")
        c2:Set(1, "A")  -- overwrite — 1 is now MRU. Order: 1, 3, 2.
        c2:Set(4, "d")  -- evicts 2. Order: 4, 1, 3.
        assert(c2:Get(1) == "A", "selftest-16: updated value")
        assert(c2:Has(2) == false, "selftest-17: key 2 evicted after overwrite promoted 1")
        assert(c2:Has(3) == true, "selftest-18: key 3 survives")

        -- Case 6: Clear
        c2:Clear()
        assert(c2.size == 0, "selftest-19: Clear reset size")
        assert(c2:Has(1) == false, "selftest-20: Clear removed entries")
        -- After Clear, list should still work:
        c2:Set(99, "z")
        assert(c2:Get(99) == "z", "selftest-21: cache usable after Clear")

        -- Case 7: single-element cache edge case
        local c3 = LRUCache:New(1, "selftest3")
        c3:Set(1, "a")
        c3:Set(2, "b")  -- evicts 1
        assert(c3:Has(1) == false, "selftest-22: single-slot eviction")
        assert(c3:Get(2) == "b", "selftest-23: single-slot survivor")
        assert(c3.size == 1, "selftest-24: single-slot size")

        -- Case 8: hit/miss counters
        local c4 = LRUCache:New(3, "selftest4")
        c4:Set(1, "a")
        c4:Get(1)          -- hit
        c4:Get(1)          -- hit
        c4:Get(999)        -- miss
        local stats = c4:GetStats()
        assert(stats.hits == 2, "selftest-25: expected 2 hits, got " .. tostring(stats.hits))
        assert(stats.misses == 1, "selftest-26: expected 1 miss, got " .. tostring(stats.misses))

        print("|cff00ff00[ETB LRUCache] All 26 self-tests passed.|r")
    end

    local ok, err = pcall(_selfTest)
    if not ok then
        print("|cffff0000[ETB LRUCache] SELF-TEST FAILED: " .. tostring(err) .. "|r")
    end
end
