-- 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, ...)

-- This file is in charge sorting a list of objectives by order of quest.

local objective_priority, objective_priority_temp = {}, {}

local function propogateObjectivePriorities(objective)
  local priority = objective_priority_temp[objective]
  
  if not priority then
    priority = assert(objective_priority[objective], "Not in route?")
    
    for dep in objective:fwdDependencies() do
      if objective_priority[dep] and not dep.root then
        priority = math.min(priority, propogateObjectivePriorities(dep))
      end
    end
    
    objective_priority_temp[objective] = priority
  end
  
  return priority
end

local function objectiveCmp(a, b)
  return objective_priority[a] < objective_priority[b]
end

local temp_indent = {}

-- Yes, this function creates a bit of garbage, but hey, that's what garbage collectors are for.
function shared.sortObjectivesByQuest(list, indent)
  assert(type(list) == "table")
  
  table.wipe(temp_indent)
  
  if indent then
    table.wipe(indent)
  else
    indent = temp_indent
  end
  
  -- Assign the objectives a priority based on their position in the route.
  for i, obj in ipairs(list) do
    objective_priority[obj] = i
  end
  
  -- Propogate those priorities into objective_priority_temp such that
  -- that objectives get assigned the lowest priority of any of their children.
  for obj in pairs(objective_priority) do
    propogateObjectivePriorities(obj)
  end
  
  -- Move objective_priority_temp into objective_priority and clear objective_priority_temp.
  objective_priority, objective_priority_temp = objective_priority_temp, objective_priority
  
  -- Move contents of list into objective_priority_temp.
  table.wipe(objective_priority_temp)
  
  for i, obj in ipairs(list) do
    objective_priority_temp[i] = obj
  end
  
  table.wipe(list)
  
  local function getObjectiveRoot(objective)
    if indent[objective] then return end
    if objective.root then return objective end
    
    local list = {}
    
    for dep in objective:revDependencies() do
      if objective_priority[dep] and not indent[dep] then
        table.insert(list, dep)
      end
    end
    
    table.sort(list, objectiveCmp)
    
    for i, dep in ipairs(list) do
      local root = getObjectiveRoot(dep)
      if root then return root end
    end
    
    return objective
  end
  
  local i = 1
  
  local function processObjective(objective, d)
    if not objective_priority[objective] or indent[objective] then return end
    list[i] = objective
    indent[objective] = d
    i, d = i + 1, d + 1
    
    local list = {}
    
    for dep in objective:fwdDependencies() do
      if objective_priority[dep] and not indent[dep] then
        table.insert(list, dep)
      end
    end
    
    table.sort(list, objectiveCmp)
    
    for i, dep in ipairs(list) do
      processObjective(dep, d)
    end
  end
  
  -- Finally, figure out the priorities of all the objectives.
  -- objective_depth also gets updated in the process.
  for i, obj in ipairs(objective_priority_temp) do
    processObjective(getObjectiveRoot(obj), 0)
  end
  
  -- assert(#list == #objective_priority_temp, "Expected "..#objective_priority_temp.." objectives; got "..#list)
  
  table.wipe(objective_priority)
  table.wipe(objective_priority_temp)
end
