-- Copyright (C) 2010, 2011 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, ...)

-- The default heuristic returns 0 for everything.
local function defaultHeuristic()
  return 0
end

local wipe, min = table.wipe, math.min

local function nodeCmp(a, b)
  return a.estimate < b.estimate
end

function shared.createGraph(heuristicBase)
  local heuristicFunc = defaultHeuristic
  
  -- Set of node objects.
  local nodes = {}
  
  -- Set of link objects.
  local links = {}
  
  -- Maps a node to its initial cost.
  local starts = {}
  
  local open = shared.createHeap(nodeCmp)
  
  local graph_clean = true
  
  local insert, pop, update = open.insert, open.pop, open.update
  
  local function addOpen(node, cost, origin)
    if node.state == nil then
      node.state = "open"
      local heuristic = heuristicFunc(node)
      node.heuristic = heuristic
      node.cost = cost
      node.estimate = cost+heuristic
      node.origin = origin
      insert(node)
    elseif node.state == "open" then
      if cost < node.cost then
        node.cost = cost
        node.estimate = cost+node.heuristic
        node.origin = origin
        update(node)
      end
    else
      --[===[@debug@
      assert(node.state == "closed")
      --@end-debug@]===]
    end
  end
  
  local function addStart(node, cost)
    assert(nodes[node])
    
    local old_cost = starts[node]
    
    if not old_cost or (cost or 0) < old_cost then
      starts[node] = cost or 0
      graph_clean = false
    end
  end
  
  local function clearStartNodes()
    table.wipe(starts)
    graph_clean = false
  end
  
  local function reset()
    for node in pairs(nodes) do
      node.state = nil
    end
    
    open.clear()
    
    for node, cost in pairs(starts) do
      addOpen(node, cost, nil)
    end
    
    graph_clean = true
  end
  
  local function nodeCost(end_node)
    if not graph_clean then reset() end
    
    if end_node.state == "closed" then
      return end_node.cost
    end
    
    if heuristicBase then
      heuristicFunc = function (node)
        return heuristicBase(node, end_node)
      end
      
      for i, node in ipairs(open) do
        local h = heuristicFunc(node)
        node.heuristic = h
        node.estimate = node.cost + h
      end
      
      open.heapify()
    end
    
    while true do
      local cur = pop()
      
      if cur then
        assert(cur.state == "open")
        cur.state = "closed"
        
        local cost = cur.cost
        
        for link_node, link_cost in pairs(cur.links) do
          addOpen(link_node, cost+link_cost, cur)
        end
        
        if cur == end_node then
          return cost
        end
      else
        -- No path to the node was found!
        return
      end
    end
  end
  
  local function nodesetCost(node_set)
    if not graph_clean then reset() end
    
    local best_node, best_cost
    
    for node in pairs(node_set) do
      if node.state == "closed" then
        local cost = node.cost
        if not best_node or cost < best_cost then
          best_node, best_cost = node, cost
        end
      end
    end
    
    if best_node then
      return best_node, best_cost
    end
    
    if heuristicBase then
      heuristicFunc = function (node)
        local h = 1/0
        
        for end_node in pairs(node_set) do
          h = min(h, heuristicBase(node, end_node))
        end
        
        return h
      end
      
      for i, node in ipairs(open) do
        local h = heuristicFunc(node)
        node.heuristic = h
        node.estimate = node.cost + h
      end
      
      open.heapify()
    end
    
    while true do
      local cur = pop()
      
      if cur then
        assert(cur.state == "open")
        cur.state = "closed"
        
        local cost = cur.cost
        
        for link_node, link_cost in pairs(cur.links) do
          addOpen(link_node, cost+link_cost, cur)
        end
        
        if node_set[cur] then
          return cur, cost
        end
      else
        -- No path to any of the nodes was found.
        return
      end
    end
  end
  
  local function createNode()
    local node = {
      perm_links = {}, -- Maps nodes to the cost to reach them from this node.
      rev_perm_links = {}, -- A set of nodes that hold permanent links to this node.
      links = {}, -- Maps nodes to the cost to reach them from this node; the merging between perm_links and the links referenced in link_origins.
      link_origins = {}, -- Maps a link object to the node it is linking this node to.
      link_destinations = {} -- Maps a link object to the node that is linking to this node.
      
      -- Variables created elsewhere:
      -- origin - The node this node inherited its cost value from, following the origin values creates a sort of linked list back to the starting node.
      -- cost - How expensive it is to reach this node from the start.
      -- heuristic - How expensive we expect it will be to reach the destination.
      -- estimate - How expensive we expect it will be to reach the destination from the start by passing through this node; equal to cost+heuristic.
      -- state - The state of the node in the search algorithm.
      --           nil - Node hasn't been visited yet,
      --           "open", a path has been found to this node but it may not be optimal.
      --           "closed", this node has been solved, the pathing code is done with it.
    }
    
    nodes[node] = true
    return node
  end
  
  local removeLink
  
  local function removeNode(node)
    if nodes[node] then
      nodes[node] = nil
      
      for rev_node in pairs(node.rev_perm_links) do
        rev_node.links[node] = nil
        rev_node.perm_links[node] = nil
        rev_node.rev_perm_links[node] = nil
      end
      
      -- Remove any links that were using this node as an origin.
      for link in pairs(node.link_origins) do
        removeLink(link)
      end
      
      -- Remove any links that were using this node as a destination.
      for link in pairs(node.link_destinations) do
        removeLink(link)
      end
      
      graph_clean = false
    end
  end
  
  local function addPermanantLink(origin, destination, cost)
    assert(nodes[origin])
    assert(nodes[destination])
    
    if origin ~= destination then
      local old_cost = origin.perm_links[destination]
      if not old_cost or cost < old_cost then
        origin.perm_links[destination] = cost
        destination.rev_perm_links[origin] = true
        
        local cur_cost = origin.links[destination]
        if not cur_cost or cost < cur_cost then
          origin.links[destination] = cost
          graph_clean = false
        end
      end
    end
  end
  
  local function addLink(origin, destination, cost)
    assert(nodes[origin])
    assert(nodes[destination])
    
    if origin ~= destination then
      local link = {
        origin = origin,
        destination = destination,
        cost = const
      }
      
      local cur_cost = origin.links[destination]
      if not cur_cost or cost < cur_cost then
        -- This link creates a shorter route to the destination, use this link's cost
        -- and mark the graph as dirty.
        origin.links[destination] = cost
        graph_clean = false
      end
      
      origin.link_origins[link] = destination
      destionation.link_destinations[link] = origin
      
      links[link] = true
      return link
    end
  end
  
  removeLink = function(link)
    if links[link] then
      local origin, destination, cost = link.origin, link.destination, link.cost
      
      -- Inform the nodes that this link is connecting that
      -- this link doesn't exist any more.
      origin.link_origins[link] = nil
      destination.link_destinations[link] = nil
      
      if origin.links[destination] == cost then
        -- The node's cost for this destination matches what this link's cost is;
        -- recalculate the cost to this destination in case that cost was set by
        -- this link object.
        local new_cost = origin.perm_links[destination]
        
        for link, dest in pairs(origin.link_origins) do
          if dest == destination then
            new_cost = min(new_cost, link.cost)
          end
        end
        
        if new_cost ~= cost then
          -- The calculated cost doesn't match what it originally was, so the cost came
          -- from this link object. Use the calculated cost, and consider the graph dirty.
          origin.links[destination] = new_cost
          graph_clean = false
        end
      end
    end
  end
  
  return {
    clearStartNodes = clearStartNodes,
    addStart = addStart,
    nodeCost = nodeCost,
    nodesetCost = nodesetCost, -- 'set' is a noun, not verb here. In fact, it's part of a compound noun.
    createNode = createNode,
    removeNode = removeNode,
    addPermanantLink =  addPermanantLink,
    addLink = addLink,
    removeLink = removeLink
  }
end
