local sounddict = {
    ["hi"] = "",
    ["hi there"] = "",
    ["eat me"] = "",
    ["eat"] = "",
    ["an eye for an eye"] = "",
    ["an eye for an apple or banana"] = "",
    ["orange"] = "",
    ["cactus"] = "",
    ["cactus please"] = "",
    ["no sir"] = "",
}

local testphraselist = {
    "hello",
    "say hi",
    "hi there",
    "oh hi there",
    "an eye for an eye for an eye for an apple or banana",
    "an eye for an apple or banana",
    "cactus orange no sir",
    "eat me hi",
}

local soundtree = {}
local soundtree_filekey = newproxy and newproxy() or {}
for sound_patt, sound_file in pairs(sounddict) do
    local currnode = soundtree
    for part in string.gmatch(sound_patt, "([a-z_]+)") do
        -- TODO: preprocess part to ignore case and such
        currnode[part] = currnode[part] or {}
        currnode = currnode[part]
    end
    currnode[soundtree_filekey] = string.gsub(sound_patt, " ", "_")..".wav"
end

function stuff(soundtree, phrase)
    -- TODO: preprocess phrase to ignore case and such

    local foundlist = {}

    local stack_i = 0
    local stack_eposlist = { [0] = 1 }
    local stack_nodelist = { [0] = soundtree }
    local complete, atend = false, false
    local backtrack = false
    repeat
        local spos = stack_eposlist[stack_i]
        local node = stack_nodelist[stack_i]
        stack_i = stack_i+1
        -- get next word
        local word_s, word_e, mods = string.find(phrase, "([a-z_]+)(%p%d)+", spos, true)
        if word_s then
            -- we have a next word
            local word = string.sub(phrase, word_s, word_e)
            local subnode = node[word] -- (you could do pattern matching here)
            if subnode then
                -- we have a pattern that matches this next word
                -- (could be first, middle or last word in pattern!)
                stack_eposlist[stack_i] = word_e+1
                stack_nodelist[stack_i] = subnode
                -- continue
            else
                -- there is no continuing pattern that matches this word
                if stack_i == 1 then
                    -- this is the first word or next unmatched word and no pattern starts with it
                    -- so jump to next word
                    stack_i = 0
                    stack_eposlist[0] = word_e+1
                else
                    -- we were matching a pattern, see what comes of it
                    -- (this word did not continue any pattern, so it's not considered)
                    backtrack = true
                end
            end
        else
            -- there is no next word, check for patterns
            -- (last few words may be rechecked if there is no sound for their nodes)
            atend = true
            backtrack = true
        end
        if backtrack then
            -- find the longest pattern on the stack that has a sound associated
            for stack_j = stack_i-1, 1, -1 do
                -- work backwards through each word to see if it has a sound
                local node = stack_nodelist[stack_j]
                local soundfile = node[soundtree_filekey]
                if soundfile then
                    -- this word has a sound
                    table.insert(foundlist, soundfile)
                    -- TODO: handle mods here

                    if stack_j == stack_i and atend then
                        -- we consumed the last word
                        complete = true
                    else
                        -- start searching for new patterns
                        stack_i = 0
                        -- resume from word after longest pattern with a sound
                        stack_eposlist[0] = stack_eposlist[stack_j+1]
                    end
                    -- stop backtracking
                    break
                end
            end
            backtrack, atend = false, false
        end
    until complete

    return foundlist
end

for testphrase_i = 1, #testphraselist do
    local testphrase = testphraselist[testphrase_i]
    local out = stuff(soundtree, testphrase)
    for sound_i = 1, #out do
        print(out[sound_i])
    end
end