-- HousingDecorGuide/Core/HDG_AutoLayout.lua
-- Pure-Lua spatial reconstruction: from {roomID -> {shape, fingerprint, worldCardinals?, occupiedCardinals?}}
-- produce {layout = {roomID -> {cell, rotation}}, connections = [{fromID, toID, fromDir, toDir}]}
-- using greedy hub-first BFS over world-space cardinal door facings.
--
-- Input priority (for door sets):
--   1. occupiedCardinals — rotation-aware world-space occupied doors (from RotationDeducer)
--   2. fingerprint.occupiedDoors — compass-string fallback (fingerprint-only path)
--
-- Coordinate convention: +x East, +y South. North is -y, West is -x.

local _, privateDB = ...
local M = {}

local DIR_DELTA    = { N = { 0, -1 }, E = { 1, 0 }, S = { 0, 1 }, W = { -1, 0 } }
local OPPOSITE     = { N = "S",       E = "W",      S = "N",      W = "E" }
local DIRS_ORDERED = { "N", "E", "S", "W" }

-- Build occupied-door multiset from room data.
-- Prefers occupiedCardinals (rotation-deduced, world-space) when available;
-- falls back to fingerprint.occupiedDoors for backward compat with tests.
local function _occupiedDoorSet(room)
    local set = {}
    if room.occupiedCardinals then
        for _, d in ipairs(room.occupiedCardinals) do
            set[d] = (set[d] or 0) + 1
        end
    elseif room.fingerprint and room.fingerprint.occupiedDoors then
        for _, d in ipairs(room.fingerprint.occupiedDoors) do
            set[d] = (set[d] or 0) + 1
        end
    end
    return set
end

local function _degree(room)
    if room.occupiedCardinals then return #room.occupiedCardinals end
    return (room.fingerprint and room.fingerprint.degree) or 0
end

-- For a given direction needed at a placed room, pick the best unplaced candidate
-- with an unused door in the OPPOSITE direction. Lowest degree first (leaves before
-- chains before hubs, per Reference/HOUSING_API.md §"Tree reconstruction"); alphabetical tiebreak.
local function _pickCandidate(rooms, placed, usedDoors, direction)
    local opp = OPPOSITE[direction]
    local bestID, bestDeg = nil, math.huge
    for id, r in pairs(rooms) do
        if not placed[id] then
            local oppDoors = _occupiedDoorSet(r)
            local used = usedDoors[id] or {}
            local available = (oppDoors[opp] or 0) - (used[opp] or 0)
            if available > 0 then
                local deg = _degree(r)
                if deg < bestDeg or (deg == bestDeg and (bestID == nil or id < bestID)) then
                    bestID, bestDeg = id, deg
                end
            end
        end
    end
    return bestID
end

-- Pick the best seed (highest degree, alphabetical tiebreak) from unplaced rooms.
local function _pickSeed(rooms, placed)
    local bestID, bestDeg = nil, -1
    for id, r in pairs(rooms) do
        if not placed[id] then
            local deg = _degree(r)
            if deg > bestDeg or (deg == bestDeg and (bestID == nil or id < bestID)) then
                bestID, bestDeg = id, deg
            end
        end
    end
    return bestID
end

local function _allPlaced(rooms, placed)
    for id in pairs(rooms) do
        if not placed[id] then return false end
    end
    return true
end

function M.compute(rooms)
    local result = { layout = {}, connections = {} }
    if not rooms or not next(rooms) then return result end

    local placed     = {}    -- roomID -> true once placed
    local cellMap    = {}    -- "x,y" -> roomID
    local usedDoors  = {}    -- roomID -> {N=count, E=count, S=count, W=count}

    local function _placeAt(id, x, y)
        result.layout[id] = { cell = { x = x, y = y }, rotation = 0 }
        placed[id] = true
        cellMap[x .. "," .. y] = id
        usedDoors[id] = usedDoors[id] or {}
    end

    local function _addConnection(fromID, toID, fromDir)
        result.connections[#result.connections + 1] = {
            fromID = fromID, toID = toID,
            fromDir = fromDir, toDir = OPPOSITE[fromDir],
        }
        usedDoors[fromID] = usedDoors[fromID] or {}
        usedDoors[fromID][fromDir] = (usedDoors[fromID][fromDir] or 0) + 1
        usedDoors[toID] = usedDoors[toID] or {}
        usedDoors[toID][OPPOSITE[fromDir]] = (usedDoors[toID][OPPOSITE[fromDir]] or 0) + 1
    end

    -- Find first free cell scanning right from origin row, used for new components.
    local nextFreeX = 0
    local function _firstFreeCell()
        while cellMap[nextFreeX .. ",0"] do nextFreeX = nextFreeX + 1 end
        return nextFreeX, 0
    end

    -- Connected component traversal — repeat until all rooms placed.
    while not _allPlaced(rooms, placed) do
        local seedID = _pickSeed(rooms, placed)
        if not seedID then break end

        if next(placed) then
            -- New component — place at next free cell on row 0
            local x, y = _firstFreeCell()
            _placeAt(seedID, x, y)
        else
            _placeAt(seedID, 0, 0)
        end

        -- BFS: queue of rooms whose unused doors we still need to walk
        local queue = { seedID }
        while #queue > 0 do
            local currentID = table.remove(queue, 1)
            local current = rooms[currentID]
            if current then
                local doorSet = _occupiedDoorSet(current)
                for _, dir in ipairs(DIRS_ORDERED) do
                    local total = doorSet[dir] or 0
                    local used = (usedDoors[currentID] and usedDoors[currentID][dir]) or 0
                    if total > used then
                        local cand = _pickCandidate(rooms, placed, usedDoors, dir)
                        if cand then
                            local cur = result.layout[currentID].cell
                            local dx, dy = DIR_DELTA[dir][1], DIR_DELTA[dir][2]
                            -- Footprint-aware step: half-extent of current + half-extent of candidate
                            -- on the axis we're moving on. Defaults to 1 when footprint absent (tests).
                            local function _fp(r) return (r and r.footprint) or { 1, 1 } end
                            local curFp  = _fp(current)
                            local candFp = _fp(rooms[cand])
                            local step
                            if dir == "N" or dir == "S" then
                                step = math.max(1, math.ceil((curFp[2] + candFp[2]) / 2))
                            else
                                step = math.max(1, math.ceil((curFp[1] + candFp[1]) / 2))
                            end
                            local nx, ny = cur.x + dx * step, cur.y + dy * step
                            -- Collision: nudge along same axis until free
                            while cellMap[nx .. "," .. ny] do
                                nx, ny = nx + dx, ny + dy
                            end
                            _placeAt(cand, nx, ny)
                            _addConnection(currentID, cand, dir)
                            queue[#queue + 1] = cand
                        end
                        -- If no candidate: door stays unfilled; renderer draws an open-door orb.
                    end
                end
            end
        end
    end

    return result
end

if privateDB then privateDB.HDG_AutoLayout = M end
return M
