local Object = require "object"


--[[
    Prefix Tree Stack preserves the insertion order
    of the items being added. This can create duplicate
    branches when a normal prefix tree wouldn't have it

    Insertion Operations:
        insert apple
        insert application
        insert banana
        insert banned
        insert apply
        insert bandana
        insert apples 
    
    Normal Prefix Tree:
        appl
         +-- e -> apple 
         |   +-- s -> apples
         +-- ication -> application
         +-- y -> apply
        ban
         +-- ana -> banana
         +-- ned -> banned
         +-- dana -> bandana

    Ordered Prefix Tree:
        appl
         +-- e -> apple
         +-- ication -> application
        ban
         +-- ana -> banana
         +-- ned -> banned
        apply -> apply
        bandan -> bandan
        apples -> apples

]]
local PrefixTreeStack = Object:extend()

function PrefixTreeStack:new()
    self.stack = {n = 0}
end

function PrefixTreeStack:push(string)
    local stack = self.stack
    for char in string:gmatch(".") do
        if stack.n == 0 then
            local newStack = {prefix = char, n = 0;}
            stack.n = stack.n + 1
            table.insert(stack, newStack)
            stack = newStack
        elseif stack[stack.n].prefix == char then
            stack = stack[stack.n]
        else
            local newStack = {prefix = char, n = 0;}
            stack.n = stack.n + 1
            table.insert(stack, newStack)
            stack = newStack
        end
    end
end


--[[
    Each node should have a + before its prefix
    Each node should have a | leading to its sibling
]]
function PrefixTreeStack:__tostring()
    local string = {}
    local function walkTree(stack, depth)
        local children = {}
        for i = 1, stack.n do
            local path = stack[i]
            table.insert(children, "+ " .. path.prefix)
            local subchildren = walkTree(path, depth + 2)
            for _, subchild in ipairs(subchildren) do
                if i ~= stack.n then
                    table.insert(children, "| " .. subchild)
                else
                    table.insert(children, "  " .. subchild)
                end
            end
        end
        return children
    end
    string = walkTree(self.stack, 0)
    return table.concat(string, "\n")
end

local pprint = require "pprint"

local pts = PrefixTreeStack()
pts:push "apple"
pts:push "apples"
pts:push "banana"
pts:push "bandana"
pts:push "banned"
pts:push "banner"
pts:push "application"
pts:push "applies"
pts:push "apply"

print(pts)