-- Copyright (C) 2010 Tyson Brown
-- 
-- This file is part QuestHelper2, an AddOn for World of Warcraft.
-- 
-- QuestHelper2 is free software: you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation, either version 3 of the License, or
-- (at your option) any later version.
-- 
-- QuestHelper2 is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
-- 
-- You should have received a copy of the GNU General Public License
-- along with QuestHelper2. If not, see <http://www.gnu.org/licenses/>.

if LibDebug then LibDebug() end
local shared = select(2, ...)

-- Make these functions local.
local insert, remove, wipe, floor = table.insert, table.remove, table.wipe, math.floor

-- If true, our understanding of how the maps are connected is probably
-- wrong and needs to be rechecked.
local dirty = true

-- MapLink objects that are concerned with movement between maps.
local links = {}

shared.onMapLinkEnabled(function (link)
  dirty = true
  
  if shared.areaVirtualMap(link:getOrigin()) ~= shared.areaVirtualMap(link:getDestination()) then
    links[link] = true
  end
end)

shared.onMapLinkDisabled(function (link)
  dirty = true
  links[link] = nil
end)

shared.onMapPatherModified(function ()
  dirty = true
end)

local nodes = {}
local map_nodes = {}

local function getExistingNode(x, y, map_id)
  local node_list = map_nodes[map_id]
  
  if node_list then
    local best, best_d2
    
    for i, node in pairs(node_list) do
      assert(node.map == map_id)
      local dx, dy = x-node.mx, y-node.my
      local d2 = dx*dx + dy*dy
      if not best or d2 < best_d2 then
        best, best_d2 = node, d2
      end
    end
    
    if best and best_d2 < 100 then
      return best
    end
  end
end

local function getNode(area_id, level, x, y, ex, ey)
  local mx, my, map_id = shared.mapVirtualPosition(area_id, level, x, y)
  
  local node = getExistingNode(mx, my, map_id)
  
  if node then
    return node
  end
  
  local node_list = map_nodes[map_id]
  
  if not node_list then
    node_list = {}
    map_nodes[map_id] = node_list
  end
  
  node = { mx = mx, my = my, map = map_id, area_id = area_id, level = level, x = x, y = y, ex = ex, ey = ey, links = {} }
  table.insert(node_list, node)
  nodes[node] = true
  return node
end

local function setLinkTime(from, to, time, distance)
  if time then
    local links = from.links
    local old_info = links[to]
    
    if not old_info or time < old_info.time then
      links[to] = { time=time, distance=distance }
    end
  end
end

local sorted_node_list, sorted_node_list_len = {}, 0

local function regenerateMapData()
  wipe(nodes)
  wipe(map_nodes)
  wipe(sorted_node_list)
  sorted_node_list_len = 0
  
  -- Create and link the nodes representing where the player can leave one map and enter another.
  for link in pairs(links) do
    local fwd, rev = link.forward_time, link.reverse_time
    
    local node1, node2 = getNode(link:getOrigin()), getNode(link:getDestination())
    
    if fwd then
      -- TODO: Calculate a more reasonable distance than zero.
      setLinkTime(node1, node2, fwd, 0)
      node1.exit = true
      node2.entrance = true
    end
    
    if rev then
      -- TODO: Calculate a more reasonable distance than zero.
      setLinkTime(node2, node1, rev, 0)
      node2.exit = true
      node1.entrance = true
    end
  end
  
  -- Go through all the entrance nodes for a given map, and calculate the
  -- time it takes to reach any of the exit nodes, so that we can
  -- path through an area without
  for map_id, node_list in pairs(map_nodes) do
    local entrances, exits = {}, {}
    
    for i, node in ipairs(node_list) do
      if node.entrance then entrances[node] = true end
      if node.exit then exits[node] = true end
    end
    
    local map_pather = shared.getMapPather(map_id)
    
    if map_pather then
      for entrance in pairs(entrances) do
        map_pather:setStart(entrance.area_id, entrance.level, entrance.x, entrance.y, entrance.ex, entrance.ey, 0, 0)
        
        for exit in pairs(exits) do
          if entrance ~= exit then
            setLinkTime(entrance, exit, map_pather:getEndTravelTime(exit.area_id, exit.level, exit.x, exit.y, exit.ex, exit.ey))
          end
        end
      end
    else
      print("No pathing model defined for map #"..map_id)
    end
  end
  
  -- TODO: calculate the time it takes to reach an entrance from an exit by going through other maps,
  -- and create MapLink objects if the travel time is less than what it would take to travel there
  -- directly.
  
  dirty = false
end

local function resetMapNodes()
  for node in pairs(nodes) do
    node.solved, node.time, node.distance, node.origin = nil, nil, nil, nil
  end
  
  wipe(sorted_node_list)
  sorted_node_list_len = 0
end

local function addNode(node, origin, time, distance)
  local len = #sorted_node_list
  local mn, mx = 1, len+1
  
  local old_time = node.time
  
  if old_time then
    -- Node is already in the list.
    if old_time <= time then
      -- We already know of a faster route to this node.
      return
    end
    
    -- Locate the lower bound for distance in the list.
    while mn ~= mx do
      local m = floor((mn+mx)*0.5)
      
      if old_time < sorted_node_list[m].time then
        mn = m+1
      else
        mx = m
      end
    end
    
    -- Starting at the lower bound, move forward until we find the node.
    while sorted_node_list[mn] ~= node do
      assert(old_time == sorted_node_list[mn].time)
      mn = mn + 1
    end
    
    -- Remove the node, and set the maximum range to the end of the list.
    -- for when we chose the insert position.
    remove(sorted_node_list, mn)
    mx = len -- Not len+1, because we've removed an element and len currently one too many.
  end
  
  -- Locate the upper bound for distance in the list.
  while mn ~= mx do
    local m = floor((mn+mx)*0.5)
    
    if sorted_node_list[m].time < time then
      mx = m
    else
      mn = m+1
    end
  end
  
  -- Insert the node at the upper bound, and assign the nodes distance.
  insert(sorted_node_list, mn, node)
  
  node.distance, node.time, node.origin = distance, time, origin
end

local function getTravelTime(node)
  if node.solved then
    return node.time, node.distance
  end
  
  while true do
    local next_node = table.remove(sorted_node_list)
    if not next_node then return nil end
    next_node.solved = true
    
    local time, distance = next_node.time, next_node.distance
    
    for link, info in pairs(next_node.links) do
      if distance and info.distance then
        addNode(link, next_node, time+info.time, distance+info.distance)
      else
        addNode(link, next_node, time+info.time, nil)
      end
    end
    
    if next_node == node then
      return time, distance
    end
  end
end

local empty_list = {}

function shared.calculateTravelTime(src_area_id,  src_level,  src_x,  src_y,  src_ex,  src_ey,
                                    dest_area_id, dest_level, dest_x, dest_y, dest_ex, dest_ey,
                                    path)
  
  local src_map, dest_map = shared.areaVirtualMap(src_area_id, src_level), shared.areaVirtualMap(dest_area_id, dest_level)
  
  if src_map == dest_map then
    local map_pather = shared.getMapPather(src_map)
    
    if map_pather then
      return map_pather:calculateTravelTime(src_area_id,  src_level,  src_x,  src_y,  src_ex,  src_ey,
                                            dest_area_id, dest_level, dest_x, dest_y, dest_ex, dest_ey, path)
    end
    
    return nil
  end
  
  if dirty then
    regenerateMapData()
  else
    resetMapNodes()
  end
  
  local start_pather, dest_pather = shared.getMapPather(src_map), shared.getMapPather(dest_map)
  
  if start_pather and dest_pather then
    start_pather:setStart(src_area_id,  src_level,  src_x,  src_y,  src_ex,  src_ey, 0)
    
    for i, node in ipairs(map_nodes[src_map] or empty_list) do
      if node.exit then
        addNode(node, nil, start_pather:getEndTravelTime(node.area_id, node.level, node.x, node.y, node.ex, node.ey))
      end
    end
    
    dest_pather:clearStart()
    
    for i, node in ipairs(map_nodes[dest_map] or empty_list) do
      if node.entrance then
        local time, distance = getTravelTime(node)
        if time then
          dest_pather:addStart(node.area_id, node.level, node.x, node.y, node.ex, node.ey, time, distance)
        end
      end
    end
    
    local time, distance, area_id, level, x, y, ex, ey = dest_pather:getEndTravelTime(dest_area_id, dest_level, dest_x, dest_y, dest_ex, dest_ey)
    
    if time and path then
      local node = assert(getExistingNode(shared.mapVirtualPosition(area_id, level, x, y)))
      node.next = nil
      
      while node.origin do
        node.origin.next = node
        node = node.origin
      end
      
      start_pather:calculateTravelTime(src_area_id,  src_level,  src_x,  src_y,  src_ex,  src_ey,
                                       node.area_id, node.level, node.x, node.y, node.ex, node.ey,
                                       path)
      
      while node.next do
        local next = node.next
        if node.map == next.map then
          assert(shared.getMapPather(node.map)):calculateTravelTime(node.area_id, node.level, node.x, node.y, node.ex, node.ey,
                                                                    next.area_id, next.level, next.x, next.y, next.ex, next.ey,
                                                                    path)
          
        end
        
        node = next
      end
      
      dest_pather:calculateTravelTime(area_id, level, x, y, ex, ey, dest_area_id, dest_level, dest_x, dest_y, dest_ex, dest_ey, path)
    end
    
    return time, distance
  end
end
