-- HousingDecorGuide/modules/HDG_MogulLP.lua
-- LP-relaxation alternative to the greedy planner.
--
-- Approach (profit mode only; collection delegates to greedy):
--   1. Reuse HDG_Mogul.ScoreRecipe to compute per-craft profit for each candidate.
--   2. Solve the relaxed LP:
--        max   sum_r  x_r * profit_r
--        s.t.  sum_r  x_r * tierQty[r,t]  <=  budget_t   for each lumber tier t
--              x_r >= 0
--      via tableau simplex. No integer constraint, no shared-mat handling --
--      the LP is the "lumber-only" master problem; mats are post-processed.
--   3. Round LP solution down to integers (floor each x_r).
--   4. Greedy-fill remaining lumber: any tier with leftover space, pick the
--      highest profit-per-binding-tier recipe that still fits, repeat.
--   5. Allocate owned non-lumber mats across the resulting plan rows; whatever
--      isn't owned goes to the shoppingList at AH price.
--   6. Compute totals (revenue, netProfit, lumberUsed, crafts).
--
-- This is a heuristic too -- LP relaxation + integer rounding is not
-- provably optimal (full MILP would branch-and-bound). But on the housing
-- recipe problem size it typically beats greedy when multi-tier or
-- shared-mat effects matter, and matches greedy on the common single-tier
-- case.

local HDG_MogulLP = {}

local EPS = 1e-9

-- =====================================================================
-- TABLEAU SIMPLEX
-- =====================================================================
-- Solves: max c'x  s.t.  A*x <= b,  x >= 0
-- c: array of length N (objective coefficients)
-- A: array of T rows, each an array of N cells (constraint matrix)
-- b: array of length T (RHS, all >= 0)
-- Returns: x (array of length N) on success, nil + reason on failure.

local function Simplex(c, A, b)
    local T = #A
    local N = #c
    if T == 0 or N == 0 then
        local zero = {}
        for j = 1, N do zero[j] = 0 end
        return zero
    end

    -- Tableau dimensions: (T + 1) rows by (N + T + 1) cols.
    -- Rows 1..T = constraints (with slack identity appended), Row T+1 = objective.
    -- Cols 1..N = original vars, N+1..N+T = slacks, N+T+1 = RHS.
    local cols = N + T + 1
    local tab = {}
    for i = 1, T do
        local row = {}
        for j = 1, N do row[j] = A[i][j] or 0 end
        for j = 1, T do row[N + j] = (j == i) and 1 or 0 end
        row[cols] = b[i] or 0
        tab[i] = row
    end
    local objRow = {}
    for j = 1, N do objRow[j] = -(c[j] or 0) end   -- negate: simplex minimises
    for j = 1, T do objRow[N + j] = 0 end
    objRow[cols] = 0
    tab[T + 1] = objRow

    -- Basis: initial BFS uses all slacks.
    local basis = {}
    for i = 1, T do basis[i] = N + i end

    -- Bland's rule (smallest-index entering var) prevents cycling on degenerate LPs.
    local maxIter = 4 * (N + T) * (N + T)
    for _ = 1, maxIter do
        -- Find entering: smallest-index column with negative reduced cost (Bland).
        local entering = -1
        for j = 1, N + T do
            if tab[T + 1][j] < -EPS then entering = j; break end
        end
        if entering == -1 then break end -- optimal

        -- Min ratio test: smallest-index leaving row among ties.
        local leaving = -1
        local minRatio = math.huge
        for i = 1, T do
            local a = tab[i][entering]
            if a > EPS then
                local ratio = tab[i][cols] / a
                if ratio < minRatio - EPS then
                    minRatio = ratio
                    leaving = i
                elseif ratio < minRatio + EPS and leaving ~= -1 and basis[i] < basis[leaving] then
                    leaving = i  -- tie-break by smallest basis index (Bland)
                end
            end
        end
        if leaving == -1 then return nil, "unbounded" end

        -- Pivot.
        local piv = tab[leaving][entering]
        local pivRow = tab[leaving]
        for j = 1, cols do pivRow[j] = pivRow[j] / piv end
        for i = 1, T + 1 do
            if i ~= leaving then
                local factor = tab[i][entering]
                if factor < -EPS or factor > EPS then
                    local row = tab[i]
                    for j = 1, cols do row[j] = row[j] - factor * pivRow[j] end
                end
            end
        end
        basis[leaving] = entering
    end

    -- Extract primal solution: any basic variable that's an original (j <= N)
    -- gets its tableau RHS value; non-basic stays zero.
    local x = {}
    for j = 1, N do x[j] = 0 end
    for i = 1, T do
        if basis[i] <= N then x[basis[i]] = tab[i][cols] end
    end
    return x
end

-- =====================================================================
-- HELPERS (small duplications of HDG_Mogul internals to keep this module
-- self-contained and avoid import-order surprises)
-- =====================================================================

local function copyTable(t)
    local out = {}
    for k, v in pairs(t) do out[k] = v end
    return out
end

local function totalLumberRemaining(remaining)
    local s = 0
    for _, n in pairs(remaining) do s = s + n end
    return s
end

local function lumberFitsOne(score, remaining)
    if #score.lumberReagents == 0 then return true end
    for _, lr in ipairs(score.lumberReagents) do
        if (remaining[lr.id] or 0) < lr.qty then return false end
    end
    return true
end

local function deductOneCraft(score, remaining)
    for _, lr in ipairs(score.lumberReagents) do
        remaining[lr.id] = (remaining[lr.id] or 0) - lr.qty
    end
end

-- =====================================================================
-- MAIN ENTRY
-- =====================================================================

function HDG_MogulLP.BuildPlan(opts)
    -- Collection mode is already cheapest-lumber-first which is near-optimal
    -- for "max distinct uncollected"; LP adds nothing. Defer to greedy.
    if opts.mode == "collection" then
        if _G.HDG_Mogul and _G.HDG_Mogul.BuildPlan then
            -- Force greedy path even if caller asked for LP.
            local greedyOpts = copyTable(opts)
            greedyOpts.algorithm = "greedy"
            return _G.HDG_Mogul.BuildPlan(greedyOpts)
        end
        return { rows = {}, totals = {}, shoppingList = {}, candidates = {} }
    end

    -- Smooth supply-impact is a piecewise-linear-with-decay objective; modelling
    -- it in this simplex would require N*cap helper variables. Simpler: when the
    -- player picks Smooth, route to greedy (which handles decay natively per-unit).
    -- Cap mode stays in LP -- it's just a per-recipe upper bound, trivially linear.
    local siMode  = (opts.supplyImpact and opts.supplyImpact.mode) or "off"
    local siCap   = (opts.supplyImpact and opts.supplyImpact.cap) or 10
    if siMode == "smooth" and _G.HDG_Mogul and _G.HDG_Mogul.BuildPlan then
        local greedyOpts = copyTable(opts)
        greedyOpts.algorithm = "greedy"
        return _G.HDG_Mogul.BuildPlan(greedyOpts)
    end

    if not (_G.HDG_Mogul and _G.HDG_Mogul.ScoreRecipe) then
        return { rows = {}, totals = {}, shoppingList = {}, candidates = {} }
    end

    local lumberBudgets = opts.lumberBudgets or {}
    local candidates = opts.candidates or {}
    local ownedMats = opts.ownedMats or {}
    local matPrices = opts.matPrices or {}
    local lumberIDs = opts.lumberIDs or {}
    local optimizeBy = opts.optimizeBy or "lumberOnly"

    -- Pre-score all candidates; drop lumberless (Mogul is the lumber optimizer).
    local scored = {}
    for _, recipe in ipairs(candidates) do
        local s = _G.HDG_Mogul.ScoreRecipe(recipe, { lumberIDs = lumberIDs, matPrices = matPrices })
        s.recipe = recipe
        if s.lumberCost > 0 then scored[#scored + 1] = s end
    end

    -- Order lumber tiers stably so LP indices are deterministic across runs.
    local tierIDs = {}
    for tID in pairs(lumberBudgets) do tierIDs[#tierIDs + 1] = tID end
    table.sort(tierIDs)
    local T = #tierIDs
    local tierIndex = {}
    for i, tID in ipairs(tierIDs) do tierIndex[tID] = i end

    local N = #scored
    if N == 0 or T == 0 then
        return {
            rows = {},
            totals = { revenue = 0, netProfit = 0, lumberUsed = 0, crafts = 0 },
            shoppingList = {},
            candidates = scored,
        }
    end

    -- Per-craft profit. lumberOnly mode treats mats as free (revenue only);
    -- lumberPlusMats subtracts full mat cost (LP can't model the owned-mat
    -- discount linearly without extra variables -- step 5 reclaims that gap
    -- post-hoc on the rounded plan).
    local profit = {}
    for r = 1, N do
        local s = scored[r]
        local p
        if optimizeBy == "lumberOnly" then
            p = s.salePrice
        else
            p = s.salePrice - s.nonLumberMatCost
        end
        profit[r] = p > 0 and p or 0   -- skip negatives by zeroing the LP coefficient
    end

    -- Constraint matrix A: T tiers by N recipes; cell [t][r] = qty of tier t in recipe r.
    local A = {}
    for t = 1, T do
        A[t] = {}
        for r = 1, N do A[t][r] = 0 end
    end
    for r = 1, N do
        for _, lr in ipairs(scored[r].lumberReagents) do
            local tIdx = tierIndex[lr.id]
            if tIdx then A[tIdx][r] = lr.qty end
        end
    end

    -- RHS b
    local b = {}
    for t = 1, T do b[t] = lumberBudgets[tierIDs[t]] or 0 end

    -- Cap mode: append N per-recipe upper-bound constraints x_r <= cap. The
    -- simplex tableau handles them as standard <= rows; total constraints
    -- become T + N. Sub-millisecond on housing recipe sizes.
    if siMode == "cap" then
        for r = 1, N do
            local row = {}
            for j = 1, N do row[j] = (j == r) and 1 or 0 end
            A[#A + 1] = row
            b[#b + 1] = siCap
        end
    end

    -- Solve LP relaxation
    local x = Simplex(profit, A, b)
    local intCrafts = {}
    if x then
        for r = 1, N do intCrafts[r] = math.floor(x[r] + EPS) end  -- floor with epsilon for FP slop
    else
        for r = 1, N do intCrafts[r] = 0 end
    end

    -- Track remaining lumber after the rounded LP plan.
    local remainingLumber = copyTable(lumberBudgets)
    local initialTotal = totalLumberRemaining(remainingLumber)
    for r = 1, N do
        if intCrafts[r] > 0 then
            for _, lr in ipairs(scored[r].lumberReagents) do
                remainingLumber[lr.id] = (remainingLumber[lr.id] or 0) - intCrafts[r] * lr.qty
            end
        end
    end

    -- Greedy fill: rounding loses fractional crafts. Add one craft at a time of
    -- the highest profit-per-bottleneck-lumber recipe that still fits, until none do.
    -- Cap mode: respect the per-recipe ceiling here too (LP already capped, but
    -- this fill pass could otherwise push a recipe back over the line).
    while true do
        local best, bestPerL = -1, -math.huge
        for r = 1, N do
            local s = scored[r]
            local capOK = (siMode ~= "cap") or (intCrafts[r] < siCap)
            if capOK and profit[r] > 0 and lumberFitsOne(s, remainingLumber) then
                local perL = profit[r] / s.bindingLumberQty
                if perL > bestPerL then
                    bestPerL = perL
                    best = r
                end
            end
        end
        if best == -1 then break end
        intCrafts[best] = intCrafts[best] + 1
        deductOneCraft(scored[best], remainingLumber)
    end

    -- Build plan rows from intCrafts; sort by profit desc for display stability.
    local rows = {}
    for r = 1, N do
        if intCrafts[r] > 0 then
            rows[#rows + 1] = { recipe = scored[r].recipe, crafts = intCrafts[r], score = scored[r] }
        end
    end
    table.sort(rows, function(r1, r2)
        return r1.crafts * r1.score.salePrice > r2.crafts * r2.score.salePrice
    end)

    -- Allocate owned mats; surplus -> shoppingList at AH price.
    local remainingMats = copyTable(ownedMats)
    local matsBoughtPerID = {}
    local actualMatSpend = 0
    for _, row in ipairs(rows) do
        for _, m in ipairs(row.score.nonLumberMats) do
            local need = row.crafts * m.qty
            local owned = remainingMats[m.id] or 0
            local fromOwned = math.min(owned, need)
            remainingMats[m.id] = owned - fromOwned
            local buy = need - fromOwned
            if buy > 0 then
                matsBoughtPerID[m.id] = (matsBoughtPerID[m.id] or 0) + buy
                actualMatSpend = actualMatSpend + buy * (matPrices[m.id] or 0)
            end
        end
    end

    local totalRevenue = 0
    local totalCrafts = 0
    for _, row in ipairs(rows) do
        totalRevenue = totalRevenue + row.crafts * row.score.salePrice
        totalCrafts = totalCrafts + row.crafts
    end

    local lumberRemaining = totalLumberRemaining(remainingLumber)
    local capLimited = (siMode == "cap") and (lumberRemaining > 0) and (#rows > 0)
    local totals = {
        revenue       = totalRevenue,
        netProfit     = totalRevenue - actualMatSpend,
        lumberUsed    = initialTotal - lumberRemaining,
        lumberBudget  = initialTotal,
        crafts        = totalCrafts,
        matSpend      = actualMatSpend,
        capLimited    = capLimited,
    }

    local shoppingList = {}
    for matID, qty in pairs(matsBoughtPerID) do
        local price = matPrices[matID] or 0
        shoppingList[#shoppingList + 1] = {
            id        = matID,
            qty       = qty,
            unitPrice = price,
            totalCost = qty * price,
        }
    end
    table.sort(shoppingList, function(s1, s2) return s1.totalCost > s2.totalCost end)

    return {
        rows         = rows,
        totals       = totals,
        shoppingList = shoppingList,
        candidates   = scored,
    }
end

if _G then _G.HDG_MogulLP = HDG_MogulLP end
return HDG_MogulLP
