-- Локальные переменные для оптимизации
local pairs = pairs
local table_insert = table.insert
local string_utf8sub = string.utf8sub
local string_utf8len = string.utf8len

-- Локальная таблица для хранения методов RadixTree
local RadixTreeMethods = {}

-- Функция для добавления строки
function RadixTreeMethods:insert(word, value)
    local node = self.table
    local i = 1
    local wordLength = string_utf8len(word)

    while i <= wordLength do
        node.c = node.c or {}
        local found = false

        -- Поиск совпадающего префикса среди дочерних узлов
        for childPrefix, childNode in pairs(node.c) do
            local commonPrefix = ""
            local minLength = math.min(string_utf8len(childPrefix), wordLength - i + 1)
            for j = 1, minLength do
                if string_utf8sub(childPrefix, j, j) == string_utf8sub(word, i + j - 1, i + j - 1) then
                    commonPrefix = commonPrefix .. string_utf8sub(childPrefix, j, j)
                else
                    break
                end
            end

            if string_utf8len(commonPrefix) > 0 then
                -- Если найден общий префикс, разделяем узел
                if commonPrefix ~= childPrefix then
                    local newChild = { c = {} }
                    newChild.c[string_utf8sub(childPrefix, string_utf8len(commonPrefix) + 1)] = childNode
                    node.c[commonPrefix] = newChild
                    node.c[childPrefix] = nil
                end

                -- Переходим к следующему узлу
                node = node.c[commonPrefix]
                i = i + string_utf8len(commonPrefix)
                found = true
                break
            end
        end

        -- Если совпадающий префикс не найден, создаем новый узел
        if not found then
            local remainingWord = string_utf8sub(word, i)
            node.c[remainingWord] = {
                value = (i + string_utf8len(remainingWord) > wordLength) and value or nil,
                c = (i + string_utf8len(remainingWord) <= wordLength) and {} or nil
            }
            break
        end
    end
end

-- Функция для поиска строки
function RadixTreeMethods:search(word)
    local node = self.table
    local i = 1
    local wordLength = string_utf8len(word)

    while i <= wordLength do
        local found = false

        for childPrefix, childNode in pairs(node.c or {}) do
            if string_utf8sub(childPrefix, 1, 1) == string_utf8sub(word, i, i) then
                local prefixLength = string_utf8len(childPrefix)
                if string_utf8sub(word, i, i + prefixLength - 1) == childPrefix then
                    node = childNode
                    i = i + prefixLength
                    found = true
                    break
                end
            end
        end

        if not found then
            return nil
        end
    end

    return node.value
end

-- Функция для поиска по префиксу (автодополнение)
function RadixTreeMethods:searchPrefix(prefix)
    local node = self.table
    local i = 1
    local prefixLength = string_utf8len(prefix)

    while i <= prefixLength do
        local found = false

        for childPrefix, childNode in pairs(node.c or {}) do
            if string_utf8sub(childPrefix, 1, 1) == string_utf8sub(prefix, i, i) then
                local childPrefixLength = string_utf8len(childPrefix)
                if string_utf8sub(prefix, i, i + childPrefixLength - 1) == childPrefix then
                    node = childNode
                    i = i + childPrefixLength
                    found = true
                    break
                end
            end
        end

        if not found then
            return {}
        end
    end

    -- Сбор всех слов с данным префиксом
    local results = {}
    local stack = { { node = node, prefix = prefix } }

    while #stack > 0 do
        local current = table.remove(stack)
        local currentNode = current.node
        local currentPrefix = current.prefix

        if currentNode.value ~= nil then
            table_insert(results, { word = currentPrefix, value = currentNode.value })
        end

        for childPrefix, childNode in pairs(currentNode.c or {}) do
            table_insert(stack, { node = childNode, prefix = currentPrefix .. childPrefix })
        end
    end

    return results
end

-- Метатаблица для RadixTree
local RadixTreeMetaTable = {
    __index = RadixTreeMethods
}

-- Функция для создания нового RadixTree
function RadixTree(storageTable)
    local tree = {}
    tree.table = storageTable
    setmetatable(tree, RadixTreeMetaTable)
    return tree
end