--[[
    Commander 3.0 - Trie Data Structure
    Efficient prefix lookup for autocomplete.
]]

local ADDON_NAME, C3 = ...

local Trie = C3.class()
C3.Trie = Trie

function Trie:init()
    self.root = { children = {}, items = {} }
end

---Insert an item with a key string
---@param key string
---@param item any
function Trie:Insert(key, item)
    if not key or key == "" then return end
    key = key:lower()

    local node = self.root

    for i = 1, #key do
        local char = key:sub(i, i)
        if not node.children[char] then
            node.children[char] = { children = {}, items = {} }
        end
        node = node.children[char]

        -- Store item at every node in its path for instant prefix retrieval
        table.insert(node.items, item)
    end
end

---Find items by prefix
---@param prefix string
---@return table items
function Trie:FindPrefix(prefix)
    if not prefix or prefix == "" then return {} end
    prefix = prefix:lower()

    local node = self.root
    for i = 1, #prefix do
        local char = prefix:sub(i, i)
        node = node.children[char]
        if not node then return {} end
    end

    return node.items
end

---Clear the trie
function Trie:Clear()
    self.root = { children = {}, items = {} }
end

---Get count of items at a prefix
---@param prefix string
---@return number
function Trie:CountPrefix(prefix)
    local items = self:FindPrefix(prefix)
    return #items
end

return Trie
