--[[
    Navigation/TravelGraph.lua

    Works out how to get from where the hunter is standing to the map a beast
    lives on, using the links in Data/TravelNetwork.lua.

    ---------------------------------------------------------------------------
    Why a graph and not a list of routes
    ---------------------------------------------------------------------------

    A list would need an entry for every pair of maps, and there are hundreds.
    A graph needs one entry per portal, and finds the rest. Adding a single new
    portal in a future patch teaches it every journey that portal shortens.

    ---------------------------------------------------------------------------
    Breadth-first, not shortest-distance
    ---------------------------------------------------------------------------

    Fewest hops is what a player actually wants. A route with one portal and a
    long flight beats three portals that save a minute of flying, because every
    hop is a chance to get lost, and a hunter reads a route once before setting
    off. Distance is not even comparable across a portal.

    The search is bounded: a route nobody would follow is not worth finding.
]]

local _, ns = ...

local TravelGraph = ns.NewModule("TravelGraph")
ns.Navigation = ns.Navigation or {}
ns.Navigation.TravelGraph = TravelGraph

-- Past this many hops a route stops being guidance and becomes a chore. It
-- also bounds the search on a network that will only grow.
local MAX_HOPS = 6

-- How each kind of link is phrased. A recorded link knows only what the player
-- said it was, and that is enough to write the step.
local KIND_LABEL = {
    portal = "TRAVEL_STEP_PORTAL",
    boat = "TRAVEL_STEP_BOAT",
    zeppelin = "TRAVEL_STEP_ZEPPELIN",
    ship = "TRAVEL_STEP_SHIP",
    tram = "TRAVEL_STEP_TRAM",
    flight = "TRAVEL_STEP_FLIGHT",
}

-- from -> { link, link, ... }, built once at load from the flat list.
local outgoing = {}
local linkCount = 0

--=============================================================================
-- Index
--=============================================================================

-- The player's own faction, resolved once. A link restricted to the other side
-- is not a route: it is a locked door with a hunter sent to stand in front of
-- it. Better to say nothing than to send them there.
local playerFaction

local function UsableByPlayer(link)
    if not link.faction then return true end
    playerFaction = playerFaction or (UnitFactionGroup and UnitFactionGroup("player"))
    -- Until the client answers, assume nothing is barred: a missing answer
    -- should not silently empty the network.
    return playerFaction == nil or link.faction == playerFaction
end

local function BuildIndex()
    wipe(outgoing)
    linkCount = 0

    for _, link in ipairs(ns.Data.TravelLinks or {}) do
        -- A link without both ends is not a link. Skipping it quietly would
        -- hide a mistake in the data, so it is reported and dropped.
        if type(link.from) ~= "number" or type(link.to) ~= "number" then
            ns.Debug:Warn("TRAVEL", "link with no map ids ignored (%s -> %s)",
                tostring(link.from), tostring(link.to))
        else
            outgoing[link.from] = outgoing[link.from] or {}
            local list = outgoing[link.from]
            list[#list + 1] = link
            linkCount = linkCount + 1
        end
    end
end

--=============================================================================
-- Reachability
--=============================================================================

--- Walks up the map hierarchy collecting every map a player standing here
--- could reasonably board from.
--
-- Standing in Silvermoon, the portal that starts the journey is recorded
-- against the city; standing in the woods outside, against the zone. Both are
-- "here" as far as a traveller is concerned, so both are searched.
local function OriginsFor(mapID)
    local origins, depth = {}, 0
    while mapID and depth < 4 do
        origins[#origins + 1] = mapID
        local info = C_Map and C_Map.GetMapInfo and C_Map.GetMapInfo(mapID)
        mapID = info and info.parentMapID
        depth = depth + 1
    end
    return origins
end

--- Is this map the destination, or somewhere inside it?
--
-- A beast on a zone map is reached by arriving on that zone, but also by
-- arriving on the continent it belongs to -- the last stretch is flying, and
-- no route needs to spell that out.
local function Reaches(mapID, destinationID)
    if mapID == destinationID then return true end

    local current, depth = destinationID, 0
    while current and depth < 4 do
        local info = C_Map and C_Map.GetMapInfo and C_Map.GetMapInfo(current)
        current = info and info.parentMapID
        if current == mapID then return true end
        depth = depth + 1
    end
    return false
end

--=============================================================================
-- Public API
--=============================================================================

--- @return boolean Whether any links are loaded at all.
function TravelGraph:HasNetwork()
    return linkCount > 0
end

--- Finds the fewest-hop route between two maps.
-- @param fromMapID number Where the player is.
-- @param toMapID number Where the beast is.
-- @return table|nil An array of links, in order. nil when there is no route,
--   which includes the common case of both being on the same continent.
function TravelGraph:FindRoute(fromMapID, toMapID)
    if not fromMapID or not toMapID or linkCount == 0 then
        return nil
    end

    -- Already there: no route is the right answer, not an empty one.
    for _, origin in ipairs(OriginsFor(fromMapID)) do
        if Reaches(origin, toMapID) then
            return nil
        end
    end

    local visited = {}
    local queue = {}

    for _, origin in ipairs(OriginsFor(fromMapID)) do
        visited[origin] = true
        queue[#queue + 1] = { mapID = origin, steps = {} }
    end

    local head = 1
    while head <= #queue do
        local node = queue[head]
        head = head + 1

        if #node.steps < MAX_HOPS then
            for _, link in ipairs(outgoing[node.mapID] or {}) do
                if not visited[link.to] and UsableByPlayer(link) then
                    visited[link.to] = true

                    local steps = { unpack(node.steps) }
                    steps[#steps + 1] = link

                    if Reaches(link.to, toMapID) then
                        return steps
                    end

                    queue[#queue + 1] = { mapID = link.to, steps = steps }
                end
            end
        end
    end

    return nil
end

--- The first step of the journey, described for the player.
-- @return string|nil text, table|nil link
function TravelGraph:DescribeNextStep(fromMapID, toMapID)
    local route = self:FindRoute(fromMapID, toMapID)
    if not route or #route == 0 then
        return nil
    end

    local link = route[1]
    local destination = C_Map and C_Map.GetMapInfo and C_Map.GetMapInfo(link.to)

    -- A shipped link may name its own wording; one the player recorded only
    -- knows what kind of thing it was, which is enough to phrase it.
    local key = link.labelKey or KIND_LABEL[link.kind or ""]
    local text = (key and ns.L[key]) or ns.L["TRAVEL_STEP_GENERIC"]
    local step = text:format(destination and destination.name
        or ns.L["DETAIL_ZONE_UNKNOWN"])

    -- The imported network names the door itself -- "Portal to Silvermoon
    -- City", "Menethil Harbor Dock". That is what the player is looking for
    -- on screen, so it goes after the step rather than being thrown away.
    if link.label and link.label ~= "" then
        step = step .. " · " .. link.label
    end

    return step, link
end

--=============================================================================
-- Recording a link by travelling it
--=============================================================================

-- Where the player was standing when they said they were about to travel.
local pendingDeparture

--- Records half a link, then the other half after the journey.
--
-- A portal is written down by walking through it, not by remembering it. The
-- first call notes where the player stands; the second, made after arriving,
-- notes where they came out. Both ends are then facts observed on this client,
-- which is the same standard the sighting log and the display-id harvest hold
-- themselves to.
--
-- Links learned this way live in saved variables. They guide the player who
-- recorded them immediately, and are reviewed before any of them ships.
function TravelGraph:RecordStep(kind)
    local mapID = C_Map and C_Map.GetBestMapForUnit
        and C_Map.GetBestMapForUnit("player")
    local position = mapID and C_Map.GetPlayerMapPosition
        and C_Map.GetPlayerMapPosition(mapID, "player")

    if not mapID or not position then
        ns.Print(ns.L["TRAVEL_RECORD_NO_POSITION"])
        return false
    end

    if not pendingDeparture then
        pendingDeparture = {
            from = mapID,
            x = position.x,
            y = position.y,
            kind = kind or "portal",
        }
        local info = C_Map.GetMapInfo(mapID)
        ns.Print(ns.L["TRAVEL_RECORD_DEPARTURE"]:format(
            info and info.name or tostring(mapID),
            position.x * 100, position.y * 100))
        return true
    end

    if mapID == pendingDeparture.from then
        ns.Print(ns.L["TRAVEL_RECORD_SAME_MAP"])
        return false
    end

    local account = ns.Database:GetAccountData()
    if not account then return false end
    account.travelLinks = account.travelLinks or {}

    local link = {
        from = pendingDeparture.from,
        to = mapID,
        x = pendingDeparture.x,
        y = pendingDeparture.y,
        kind = pendingDeparture.kind,
        recordedAt = time(),
    }
    account.travelLinks[#account.travelLinks + 1] = link
    pendingDeparture = nil

    -- Available for the rest of this session without a reload: a hunter who
    -- just mapped a portal should be guided through it on the way back.
    ns.Data.TravelLinks[#ns.Data.TravelLinks + 1] = link
    BuildIndex()

    local origin = C_Map.GetMapInfo(link.from)
    local arrival = C_Map.GetMapInfo(link.to)
    ns.Print(ns.L["TRAVEL_RECORD_DONE"]:format(
        origin and origin.name or tostring(link.from),
        arrival and arrival.name or tostring(link.to)))
    ns.Debug:Log("TRAVEL", "recorded %s %d (%.1f, %.1f) -> %d",
        link.kind, link.from, link.x * 100, link.y * 100, link.to)
    return true
end

--- Forgets a departure noted by mistake.
function TravelGraph:CancelRecording()
    pendingDeparture = nil
    ns.Print(ns.L["TRAVEL_RECORD_CANCELLED"])
end

--=============================================================================
-- Lifecycle
--=============================================================================

function TravelGraph:OnEnable()
    -- Links this player mapped themselves are appended to the shipped set, so
    -- a portal they walked through guides them even before it is reviewed.
    local account = ns.Database:GetAccountData()
    for _, link in ipairs(account and account.travelLinks or {}) do
        ns.Data.TravelLinks[#ns.Data.TravelLinks + 1] = link
    end

    BuildIndex()
    ns.Debug:Log("TRAVEL", "%d travel links across %d origins",
        linkCount, ns.Util.CountKeys(outgoing))
end
