Module:IngredientsHierarchy

Documentation for this module may be created at Module:IngredientsHierarchy/doc

---@module IngredientsHierarchy
local IngredientsHierarchy = {}



--region Dependencies

local GoodsData = require("Module:GoodsData")
local ServicesData = require("Module:ServicesData")

local DataModelsWithRecipes = {
    require("Module:CampsData"),
    require("Module:FarmsData"),
    require("Module:FishingData"),
    require("Module:GatheringData"),
    require("Module:InstitutionsData"),
    require("Module:RainCollectorsData"),
    require("Module:WorkshopsData"),
}

local VIEW_RESOURCE_LINK = "Resource_link/view"

--endregion



--region Private constants

local PARAMETER_HEADER_ICON_SIZE = "large"
local PARAMETER_HEADER_DISPLAY_MODE = "notext"

local PARAMETER_NODE_ICON_SIZE = "medium"
local PARAMETER_NODE_DISPLAY_MODE = "notext"

local PARAMETER_LEAF_ICON_SIZE = "small"
local PARAMETER_LEAF_DISPLAY_MODE = "notext"

local CLASS_ENCOMPASSING_TABLE = "wikitable mw-collapsible"
local CLASS_HIERARCHY_TABLE = "wikitable"
local CLASS_LEFTOVERS_TABLE = "wikitable"

local BOLD = "'''"

--endregion

--region Localization string constants

local ERROR_MESSAGE_INVALID_DEPTH = "You must specify the depth as a number that is greater than zero. Please see the template documentation for how to use the parameters"
local ERROR_MESSAGE_INVALID_PRODUCT = "You must specify a valid good or service. Please see the template documentation for how to use the parameters. Good or service not found"
local ERROR_MESSAGE_EMPTY = "You must specify at least one good or service. Please see the template documentation for how to use the parameters"

local BEST_GOODS_HEADING = "Most important goods"

--endregion



--region Private methods

---@private
---Shifts the provided array items into keys with the value _true_ that can be used to check for existence in the provided array. **Not recursive.** Like this:
---
---`local isPresentInArray = createPresenceArray(array)`
---
---`if isPresentInArray[value] then`
---
---@param mainArray table array to copy
---@return table a new array, shifted to allow presence checks
local function createPresenceArray(mainArray)
    local seen = {}
    for _, item in ipairs(mainArray) do
        seen[item] = true
    end
    return seen
end



---@private
---Generic table utility to merge two arrays into the first, ensuring uniqueness.
---
---@param mainArray table first array
---@param arrayToAdd table array to add to the first
local function mergeArrays(mainArray, arrayToAdd)

    --Quickly return from edge cases
    if not arrayToAdd or #arrayToAdd < 1 then
        return mainArray
    end
    if not mainArray or #mainArray < 1 then
        return arrayToAdd
    end

    --Create a set for fast lookup of items already in mainArray
    local isPresentInArray = createPresenceArray(mainArray)

    --Append only unique items from arrayToAdd
    for _, item in ipairs(arrayToAdd) do
        if not isPresentInArray[item] then
            table.insert(mainArray, item)
            isPresentInArray[item] = true  -- Mark as seen so we don't add it again
        end
    end

    return mainArray
end



---@private
---Flattens the provided recipe data into just its ingredient IDs.
---
---@param DataModel BaseDataModel a data model that implements the recipe query interface
---@param recipeData table pair of recipe data retrieved from a data model
---@return table array of ingredient IDs
local function getIngredientsList(DataModel, recipeData)

    if not recipeData then
        return {}
    end

    local ingredientsList = {}
    for i = 1, DataModel:getRecipeNumIngredientSlots(recipeData) do
        for j = 1, DataModel:getRecipeIngredientNumOptions(recipeData, i) do
            local ingredientID = DataModel:getRecipeIngredientOptionIDAt(recipeData, i, j)
            --Thankfully, ingredients are always goods, never services.
            table.insert(ingredientsList, ingredientID)
        end
    end

    return ingredientsList
end



local function makeHierarchy(rootID)

    --First go through all the data models and extract an array of ingredients, with no duplicates.
    local ingredientsList = {}
    for _, DataModel in ipairs(DataModelsWithRecipes) do

        local recipeList = DataModel:getIDsAndRecipesWhereProductID(rootID)

        --There will always be at least one recipe, but we don't know whether any have ingredients yet.
        if #recipeList > 0 then
            --Go through all of those recipes, still for just this data model, and pull out a flat list of ingredients.
            for _, recipe in ipairs(recipeList) do

                local newList = getIngredientsList(DataModel, recipe)

                --Check if it's a leaf node, if so, add to the running ingredients list
                if #newList > 0 then
                    ingredientsList = mergeArrays(ingredientsList, newList)
                end
            end
        end
    end

    --Recurse only if it's not a leaf node, but we have to wait to do this until we get through all the data models.
    if #ingredientsList > 0 then
        --We need to remove any ingredients that turn into tables, but keep them in order and in an array with no gaps. To do this, we'll create a new list to return and re-add subtables and string alike, in order.
        local returnList = {}
        for _, newRoot in ipairs(ingredientsList) do
            local newNode = makeHierarchy(newRoot)
            if type(newNode) == "table" then
                returnList[newRoot] = newNode
            else
                --When not a table, need to add the ingredient to the list we'll return
                table.insert(returnList, newRoot)
            end
        end
        return returnList
    else
        --No new ingredients, so just return the string itself
        return rootID
    end
end



---@private
---Runs through the provided table, counting how many times each entry appears in the hierarchy. The second parameter is cumulative, while descending the tree.
---
---@param hierarchyTable table hierarchy of products and ingredients
---@param countingTable table (not needed on first call), the running tally
local function countInstances(hierarchyTable, countingTable)

    --Only require the second parameter on recursion.
    if not countingTable then
        countingTable = {}
    end

    for key, item in pairs(hierarchyTable) do

        local id = ""
        --We recurse for tables, but we still need to add their items to the total
        if type(item) == "table" then
            countInstances(item, countingTable)
            id = key
        else
            id = item
        end

        if not countingTable[id] then
            countingTable[id] = 1
        else
            countingTable[id] = countingTable[id] + 1
        end
    end

    return countingTable
end



---@private
---Counts all the unique items in the provided table and sorts the counts. The result is a sorted array of pairs, where pair.id and pair.count store the ID of the good or service.
---
---@param hierarchyTable table hierarchy of products and ingredients
---@return table sorted array of pairs of IDs and counts
local function countAndSort(hierarchyTable)

    local countingTable = countInstances(hierarchyTable)

    local sortedCountingTable = {}
    for ingredient, totalCount in pairs(countingTable) do
        table.insert(sortedCountingTable, { id = ingredient, count = totalCount })
    end

    table.sort(sortedCountingTable, function(a, b)
        return a.count > b.count
    end)

    return sortedCountingTable
end



---@private
---Rolls up any items below the specified depth to an array at the specified depth. Non-destructive: returns a copy and does not modify the provided hierarchy.
---
---@param hierarchyTable table hierarchy of products and ingredients
---@param depth number the depth in the hierarchy to roll up to
---@return table a new, rolled-up hierarchy table
local function reduceBelowDepth(hierarchyTable, depth)

    --Leaf node, return immediately.
    if type(hierarchyTable) == "string" then
        return hierarchyTable
    end

    local reducedTable = {}
    if depth == 0 then
        --This, conveniently, flattens the table, we just have to extract the names.
        countingTable = countInstances(hierarchyTable)
        for id, _ in pairs(countingTable) do
            table.insert(reducedTable, id)
        end
    else
        --Recurse down each subtable
        for key, item in pairs(hierarchyTable) do
            if type(item) == "table" then
                reducedTable[key] = reduceBelowDepth(item, depth - 1)
            else
                table.insert(reducedTable, item)
            end
        end
    end

    return reducedTable
end



---@private
---Gets all the items at the specified depth of the specified table.
---
---@param hierarchyTable table hierarchy of products and ingredients
---@param depth number the depth in the hierarchy to extract from
---@return table array of items found in the hierarchy at that depth
local function extractFromDepth(hierarchyTable, depth)

    local extractedItems = {}

    --Merge nodes at specified depth or if we get to strings first.
    if depth == 0 then
        for key, item in pairs(hierarchyTable) do
            if type(item) == "table" then
                extractedItems = mergeArrays(extractedItems, {key})
            else
                extractedItems = mergeArrays(extractedItems, {item})
            end
        end
        return extractedItems
    end

    for _, item in pairs(hierarchyTable) do
        --Skip any leaf nodes until we recurse to depth 0
        if type(item) == "table" then
            extractedItems = mergeArrays(extractedItems, extractFromDepth(item, depth-1))
        end
    end
    return extractedItems
end



---@private
---Cuts off the provided table at the specified depth. Any keys to subtables at that level are converted into flat items, with no contents of their subtable preserved. Non-destructive: returns a copy and does not modify the provided hierarchy.
---
---@param hierarchyTable table hierarchy of products and ingredients
---@param depth number the depth in the hierarchy to extract from
---@return table the truncated hierarchy
local function truncateAtDepth(hierarchyTable, depth)

    local truncatedTable = {}

    if depth == 0 then
        for key, item in pairs(hierarchyTable) do
            --At depth, convert any tables to regular strings and delete their children.
            if type(item) == "table" then
                table.insert(truncatedTable, key)
            else
                table.insert(truncatedTable, item)
            end
        end
        return truncatedTable
    end

    for key, item in pairs(hierarchyTable) do
        if type(item) == "table" then
            truncatedTable[key] = truncateAtDepth(item, depth-1)
        else
            table.insert(truncatedTable, item)
        end
    end
    return truncatedTable
end



local function simplifyHierarchy(hierarchyTable, isAlreadyPresent)

    local simplifiedHierarchy = {}

    --Leaf nodes.
    if type(hierarchyTable) ~= "table" then
        if isAlreadyPresent[hierarchyTable] then
            return nil
        else
            return hierarchyTable
        end
    end

    for key, item in pairs(hierarchyTable) do

        if type(item) == "table" then
            if not isAlreadyPresent[key] then
                --If it is already present, then skipping it is sufficient.
                simplifiedHierarchy[key] = simplifyHierarchy(item, isAlreadyPresent)
            end

        else
            if not isAlreadyPresent[item] then
                table.insert(simplifiedHierarchy, item)
            end
        end
    end

    return simplifiedHierarchy
end



local function renderResourceLink(frame, goodID, iconSize, displayMode)

    local iconFilename = GoodsData.getIcon(goodID)
    local name = GoodsData.getName(goodID)

    local viewParameters = {
        ["name"] = name,
        ["iconsize"] = iconSize,
        ["iconfilename"] = iconFilename,
        ["display"] = displayMode,
    }
    return "" .. frame:expandTemplate{
        title = VIEW_RESOURCE_LINK,
        args = viewParameters,
    }
end



function IngredientsHierarchy.renderHeaderRow(frame, cutoffDepth, goodID)

    --Table row markup must always start on a newline, so ensure it does.
    local ret = "\n|-" ..
            "\n!colspan=" .. cutoffDepth .. "|"

    return ret .. renderResourceLink(frame, goodID, PARAMETER_HEADER_ICON_SIZE, PARAMETER_HEADER_DISPLAY_MODE)
end



function IngredientsHierarchy.renderRowWithResourceID(frame, goodID, level)

    --Table row markup must always start on a newline, so ensure it does.
    local ret = "\n|-" ..
            "\n| "

    --Put some blank table cells before the link, to indent the ingredient.
    for _ = 1, level do
        ret = ret .. "|| "
    end

    return ret .. renderResourceLink(frame, goodID, PARAMETER_NODE_ICON_SIZE, PARAMETER_NODE_DISPLAY_MODE)
end



function IngredientsHierarchy.renderHierarchy(frame, hierarchyTable, level)

    if not level then
        level = 0
    end

    local ret = ""
    for key, item in pairs(hierarchyTable) do
        if type(item) == "table" then
            ret = ret .. IngredientsHierarchy.renderRowWithResourceID(frame, key, level)
            ret = ret .. IngredientsHierarchy.renderHierarchy(frame, item, level + 1)
        else
            --String nodes
            ret = ret .. (IngredientsHierarchy.renderRowWithResourceID(frame, item, level))
        end
    end

    return ret
end



function IngredientsHierarchy.renderProductTable(frame, cutoffDepth, caption, productIDList, hierarchyTable, leftoverItemsArray, sortedCountingTable)

    local ret = "{|class=" .. CLASS_ENCOMPASSING_TABLE ..
            "\n|+ " .. caption

    for _, id in ipairs(productIDList) do
        --Start a new cell of the encompassing table's header row
        local newCell = "\n| "
        --Enclose the entire product hierarchy table in that cell.
        newCell = newCell ..
                "\n{|class=" .. CLASS_HIERARCHY_TABLE ..
                IngredientsHierarchy.renderHeaderRow(frame, cutoffDepth, id) ..
                IngredientsHierarchy.renderHierarchy(frame, hierarchyTable[id]) ..
                "\n|}"
        ret = ret .. newCell
    end

    if leftoverItemsArray and #leftoverItemsArray > 0 then
        --New row in the encompassing table
        ret = ret .. "\n|-" ..
                "\n|colspan=" .. #productIDList .. "|"
        --Make the leftover ingredients list
        local list = "\n{|class=" .. CLASS_LEFTOVERS_TABLE
        for _, goodID in ipairs(leftoverItemsArray) do
            list = list .. "\n" .. renderResourceLink(frame, goodID, PARAMETER_LEAF_ICON_SIZE, PARAMETER_LEAF_DISPLAY_MODE)
        end
        list = list .. "\n|}"
        ret = ret .. list
    end

    if sortedCountingTable and #sortedCountingTable > 0 then

        local best = "\n{|class=" .. CLASS_LEFTOVERS_TABLE
                .. "\n! " .. BEST_GOODS_HEADING .. ": "

        local cutoffCount = sortedCountingTable[1].count / 2
        for _, pair in ipairs(sortedCountingTable) do
            --Quit once we get below the cutoff
            if pair.count < cutoffCount then
                break
            end

            best = best .. "\n| " .. BOLD .. pair.count .. BOLD .. " " .. renderResourceLink(frame, pair.id, PARAMETER_LEAF_ICON_SIZE, PARAMETER_LEAF_DISPLAY_MODE)
        end
        best = best .. "\n|}"
        ret = ret .. best
    end

    return ret .. "\n|}"
end

--endregion



--region Public methods

function IngredientsHierarchy.main(frame)

    --Validate the depth
    local cutoffDepth = tonumber(frame.args.depth)
    if not cutoffDepth or type(cutoffDepth) ~= "number" or cutoffDepth < 0 then
        error(ERROR_MESSAGE_INVALID_DEPTH)
    end
    --Increment, so that depth of 1 doesn't flatten even the top-level products
    cutoffDepth = cutoffDepth + 1

    --Validate the products
    local productIDList = {}
    --Using ipairs will skip over the named parameters for depth and caption.
    for _, productName in ipairs(frame.args) do
        --Convert the parameters to IDs instead of names.
        local productID = GoodsData.getGoodID(productName)
        if not productID then
            --Swap out names of services for the goods, since we're focusing on the products themselves; this also has the nice side-effect of reducing the level of the hierarchy by one where it doesn't matter much.
            productID = ServicesData.getServiceGoodID(productName)
        end
        if not productID then
            error(ERROR_MESSAGE_INVALID_PRODUCT .. ": " .. productName)
        end
        table.insert(productIDList, productID)
    end
    if #productIDList < 1 then
        error(ERROR_MESSAGE_EMPTY)
    end

    --Build the hierarchy and the total counts.
    local totalHierarchy = {}
    for _, id in ipairs(productIDList) do
        totalHierarchy[id] = makeHierarchy(id)
    end
    local sortedCountingTable = countAndSort(totalHierarchy)

    --Split the hierarchy at the specified depth into a separate flat list.
    local rolledupHierarchy = reduceBelowDepth(totalHierarchy, cutoffDepth)
    local leftoverItemsArray = extractFromDepth(rolledupHierarchy, cutoffDepth)
    local truncatedHierarchy = truncateAtDepth(rolledupHierarchy, cutoffDepth-1)
    local simplifiedHierarchy = simplifyHierarchy(truncatedHierarchy, createPresenceArray(leftoverItemsArray))

    local caption = frame.args.caption or ""

    return IngredientsHierarchy.renderProductTable(frame, cutoffDepth, caption, productIDList, simplifiedHierarchy, leftoverItemsArray, sortedCountingTable)
end



return IngredientsHierarchy