love = love or {}
local pprint = require "pprint"

--[[
    If you are familiar with jargon, then a "path bag" is
    a muliset that is implemented as a prefix tree.

    this is a path
    this is another path
    this is a final path
    this is a path
        |
        V
    this <-> is <-> a <-> path {2}
              |     |    
              |     + <-> final path {1}
              |
              + <-> another <-> path {1}             
--]]
local PathBag = {}
PathBag.__mt = {}

function PathBag.new()
    local obj = { root = {children = {}, child_count = 0, count = 0} }
    return setmetatable(obj, {__index = PathBag.__mt})
end

function PathBag.__mt:insert(path)
    local root = self.root
    for _, step in ipairs(path) do
        if not root.children[step] then
            root.children[step] = { value = step, children = {}, child_count = 0, count = 0, parent = root }
            root.child_count = root.child_count + 1
        end
        root = root.children[step]
    end
    root.count = root.count + 1
end

function PathBag.__mt:get(path)
    local root = self.root
    for _, step in ipairs(path) do
        if step == "*" then 
            _, root = next(root.children)
            if not root then return end 
        elseif not root.children[step] then 
            return nil
        else
            root = root.children[step]
        end
    end

    return root.count ~= 0 and root or nil
end

function PathBag.__mt:remove_node(node)
    local leaf = node
    while leaf.parent do
        leaf.count = leaf.count - 1
        if leaf.count <= 0 and leaf.child_count <= 0 then
            local path = leaf.value
            leaf = leaf.parent
            leaf.children[path] = nil
            leaf.child_count = leaf.child_count - 1
        else
            return
        end
    end
end

function PathBag.__mt:get_and_bind(path)
    local bindings, root = {}, self.root
    for _, step in ipairs(path) do
        if type(step) == "string" and step:find("^%$") then 
            key, root = next(root.children)
            if not root then return end
            bindings[step:sub(2)] = key
        elseif not root.children[step] then 
            return nil
        else
            root = root.children[step]
        end
    end

    if root.count ~= 0 then
        return root, bindings
    end
end



return PathBag