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

local location_functions = {}
local location_meta = {__index=location_functions, name="LocationList" }

shared.meta.LocationList = location_meta

function shared.createLocationList()
  return setmetatable({}, location_meta)
end

function shared.createMergedLocationList(...)
  return setmetatable({}, location_meta):merge(...)
end

-- If you think all this location management code is
-- horribly complicated... I agree with you entirely.

-- Merges the two closest nodes in list until the number of
-- nodes in the list is less than or equal to max_nodes.
-- Returns the number of nodes remaining in the list;
-- which may be less than max_nodes.
local function pruneList(list, max_nodes)
  if max_nodes < 1 then
    -- That was easy!
    table.wipe(list)
    return 0
  end
  
  local count = #list
  
  while count > max_nodes do
    local best_i, best_j, best_d2
    
    for i = 1,count-1 do
      local node_i = list[i]
      local node_i_x, node_i_y = node_i.x, node_i.y
      
      for j = i+1,count do
        local node_j = list[j]
        
        -- Multiply dx by 1.5 to account for map aspect ratio.
        local dx, dy = (node_i_x-node_j.x)*1.5, node_i_y-node_j.y
        local d2 = dx*dx+dy*dy
        
        if not best_d2 or d2 < best_d2 then
          best_i, best_j, best_d2 = i, j, d2
        end
      end
    end
    
    local node_i = list[best_i]
    local node_j = table.remove(list, best_j)
    
    local w_i, w_j = node_i.w, node_j.w
    local combine_w = w_i+w_j
    
    node_i.x = (node_i.x*w_i + node_j.x*w_j)/combine_w
    node_i.y = (node_i.y*w_i + node_j.y*w_j)/combine_w
    node_i.w = combine_w
    count = count - 1
  end
  
  return count
end

local function calculateListWeight(list)
  local weight = 0
  
  for i, node in ipairs(list) do
    weight = weight + node.w
  end
  
  return weight
end

-- Adds a new node to list, keeping the list under max_nodes.
-- Returns the number of nodes actually in the list.
local function addListNode(list, x, y, w)
  local best, best_d2
  
  for i, node in ipairs(list) do
    -- Multiply dx by 1.5 to account for map aspect ratio.
    local dx, dy = (x-node.x)*1.5, y-node.y
    local d2 = dx*dx+dy*dy
    if not best_d2 or d2 < best_d2 then
      best, best_d2 = node, d2
    end
  end
  
  -- These nodes are within about a pixel of each other, so assume they're identical.
  if best and best_d2 < 0.000001 then
    w = w or 1
    local best_w = best.w
    local w_combine = best_w+w
    best.x = (best.x*best_w + x*w)/w_combine
    best.y = (best.y*best_w + y*w)/w_combine
    best.w = w_combine
  else
    table.insert(list, {x=x, y=y, w=(w or 1)})
  end
  
  pruneList(list, 50)
end

local function pruneGeneric(list, max_locations, weightHelper, pruneHelper)
  if max_locations < 1 then
    table.wipe(list)
    return 0
  end
  
  local weights = {}
  local key_list = {}
  local weight_total = 0
  
  for key, value in pairs(list) do
    local weight = weightHelper(value)
    weights[key] = weight
    weight_total = weight_total + weight
    table.insert(key_list, key)
  end
  
  table.sort(key_list, function (a, b)
    return weights[a] < weights[b]
  end)
  
  local locations_total = 0
  
  for i, key in ipairs(key_list) do
    local weight = weights[key]
    local locations = pruneHelper(list[key], max_locations*weight/weight_total)
    locations_total = locations_total + locations
    max_locations = max_locations - locations
    weight_total = weight_total - weight
    
    if locations == 0 then
      list[key] = nil
    end
  end
  
  return locations_total
end

local function calculateWeightGeneric(list, weightHelper)
  local weight = 0
  
  for key, value in pairs(list) do
    weight = weight + weightHelper(value)
  end
  
  return weight
end

local function pruneInsideData(inside_data, max_locations)
  if max_locations < 1 then
    table.wipe(inside_data)
    return 0
  end
  
  local entrance_list = {}
  local weight_total = 0
  
  for entrance in pairs(inside_data) do
    table.insert(entrance_list, entrance)
    weight_total = weight_total + entrance.w
  end
  
  table.sort(entrance_list, function (a, b)
    return a.w < b.w
  end)
  
  local locations_total = 0
  
  for i, entrance in ipairs(entrance_list) do
    local list = inside_data[entrance]
    
    local required_locations = max_locations*entrance.w/weight_total
    
    if required_locations == 0 then
      -- Merge this entrance with another and try pruning again.
      
      inside_data[entrance] = nil
      local nearest, nearest_d2
      
      for entrance in pairs(inside_data) do
        local dx, dy = (ex-entrance.x)*1.5, ey-entrance.y
        local d2 = dx*dx+dy*dy
        
        if not nearest or d2 < nearest_d2 then
          nearest, nearest_d2 = entrance, d2
        end
      end
      
      local nearest_w, entrance_w = nearest.w, entrance.w
      local w_combine = nearest_w + entrance_w
      nearest.x = (nearest.x*nearest_w + entrance.x*entrance_w)/w_combine
      nearest.y = (nearest.y*nearest_w + entrance.y*entrance_w)/w_combine
      nearest.w = w_combine
      
      local nearest_list = inside_data[nearest]
      
      for i, node in ipairs(list) do
        addListNode(nearest_list, node.x, node.y, node.w)
      end
      
      -- I believe we start with the smallest first, so if this happened,
      -- max_locations should still be the original value we had at the beginning.
      return pruneInsideData(inside_data, max_locations)
    else
      local locations = pruneList(list, required_locations)
      locations_total = locations_total + locations
      max_locations = max_locations - locations
      weight_total = weight_total - entrance.w
      
      if locations == 0 then
        inside_data[entrance] = nil
      end
    end
  end
  
  return locations_total
end

local function calculateInsideDataWeight(inside_data)
  local weight = 0
  
  for entrance in pairs(inside_data) do
    -- entrance weight should be equal to the weight of
    -- all the nodes the region contains... in theory.
    -- In practice, I expect there to be rounding errors
    -- getting compounded over time.
    weight = weight + entrance.w
  end
  
  return weight
end

local function addInsideDataNode(inside_data, x, y, ex, ey, w)
  local nearest, nearest_d2
  local entrance_count = 0
  
  for entrance, list in pairs(inside_data) do
    local dx, dy = (ex-entrance.x)*1.5, ey-entrance.y
    local d2 = dx*dx+dy*dy
    entrance_count = entrance_count + 1
    
    if not nearest or d2 < nearest_d2 then
      nearest, nearest_d2 = entrance, d2
    end
  end
  
  if nearest and nearest_d2 < 0.0006*entrance_count*entrance_count then
    nearest.x = (nearest.x*nearest.w + ex*w)/(nearest.w + w)
    nearest.y = (nearest.y*nearest.w + ey*w)/(nearest.w + w)
    nearest.w = nearest.w + w
    
    addListNode(inside_data[nearest], x, y, w)
  else
    inside_data[{x=ex, y=ey, w=1}] = {{x=x, y=y, w=w}}
  end
end

local function pruneLevelData(level_data, max_locations)
  local outside_weight = calculateListWeight(level_data.outside)
  local weight_total = outside_weight + calculateInsideDataWeight(level_data.inside)
  
  local locations = pruneList(level_data.outside, max_locations*outside_weight/weight_total)
  return locations + pruneInsideData(level_data.inside, max_locations-locations)
end

local function calculateLevelDataWeight(level_data)
  return calculateListWeight(level_data.outside) +
         calculateInsideDataWeight(level_data.inside)
end

local function addLevelDataNode(level_data, x, y, ex, ey, w)
  if ex then
    addInsideDataNode(level_data.inside, x, y, ex, ey, w)
  else
    addListNode(level_data.outside, x, y, w)
  end
end

local function pruneAreaData(area_data, max_locations)
  return pruneGeneric(area_data, max_locations, calculateLevelDataWeight, pruneLevelData)
end

local function calculateAreaDataWeight(area_data)
  return calculateWeightGeneric(area_data, calculateLevelDataWeight)
end

local function addAreaDataNode(area_data, level, x, y, ex, ey, w)
  local level_data = area_data[level]
  
  if not level_data then
    level_data = {inside={}, outside={}}
    area_data[level] = level_data
  end
  
  addLevelDataNode(level_data, x, y, ex, ey, w)
end

-- We store the nodes to iterate through in a cache,
-- since iterating through all of them incrementally would
-- be a huge pain.
local iterate_cache = setmetatable({}, {__mode="kv"})

function location_functions:pruneLocations(max_locations)
  iterate_cache[self] = nil
  return pruneGeneric(self, max_locations, calculateAreaDataWeight, pruneAreaData)
end

function location_functions:clear()
  self:pruneLocations(0)
end

function location_functions:addLocation(area_id, level, x, y, ex, ey, w)
  area_id, level, x, y, ex, ey = shared.normalizeLocation(area_id, level, x, y, ex, ey)
  
  iterate_cache[self] = nil
  local area_data = self[area_id]
  
  if not area_data then
    area_data = {}
    self[area_id] = area_data
  end
  
  addAreaDataNode(area_data, level, x, y, ex, ey, w or 1)
end

local function iterateList(cache, list, area_id, level, ex, ey)
  local n = cache.next
  
  for i, node in ipairs(list) do
    cache[n+0], cache[n+1], cache[n+2], cache[n+3], cache[n+4], cache[n+5], cache[n+6] =
      area_id, level, node.x, node.y, ex, ey, node.w
    
    n = n+7
  end
  
  cache.next = n
end

local function iterateLevelData(cache, level_data, area_id, level)
  iterateList(cache, level_data.outside, area_id, level, nil, nil)
  for entrance, list in pairs(level_data.inside) do
    iterateList(cache, list, area_id, level, entrance.x, entrance.y)
  end
end

local function iterateAreaData(cache, area_data, area_id)
  for level, level_data in pairs(area_data) do
    iterateLevelData(cache, level_data, area_id, level)
  end
end

function location_functions:iterate()
  local cache = iterate_cache[self]
  
  if not cache then
    cache = {next=1}
    iterate_cache[self] = cache
    
    for area_id, area_data in pairs(self) do
      iterateAreaData(cache, area_data, area_id)
    end
  end
  
  local i = 1
  return function()
    local pos = i
    i = i + 7
    return unpack(cache, pos, pos+6)
  end
end

local function getListCenter(list)
  local x, y, w = 0, 0, 0
  
  for i, node in ipairs(list) do
    x, y, w = x + node.x*node.w, y + node.y*node.w, w + node.w
  end
  
  return x/w, y/w, w
end

function location_functions:nearestLocation(distanceMetric, target_area_id, target_level, target_x, target_y, target_ex, target_ey)
  local best_area_id, best_level, best_x, best_y, best_ex, best_ey
  
  if target_area_id then
    -- Return the closest match to the target location.
    local best_d
    
    for area_id, area_data in pairs(self) do
      for level, level_data in pairs(area_data) do
        if level_data.outside[1] then
          local cx, cy = getListCenter(level_data.outside)
          
          local d = distanceMetric(target_area_id, target_level, target_x, target_y, target_ex, target_ey,
                                   area_id, level, cx, cy, nil, nil)
          
          if d and (not best_area_id or d < best_d) then
            best_area_id, best_level, best_x, best_y, best_ex, best_ey, best_d =
              area_id, level, cx, cy, nil, nil, d
          end
        end
        
        for entrance, list in pairs(level_data.inside) do
          local cx, cy = getListCenter(list)
          local d = distanceMetric(target_area_id, target_level, target_x, target_y, target_ex, target_ey,
                                   area_id, level, cx, cy, entrance.x, entrance.y)
          
          if d and (not best_area_id or d < best_d) then
            best_area_id, best_level, best_x, best_y, best_ex, best_ey, best_d =
              area_id, level, cx, cy, entrance.x, entrance.y, d
          end
        end
      end
    end
  else
    -- Return the location with the highest weight.
    local best_w
    
    for area_id, area_data in pairs(self) do
      for level, level_data in pairs(area_data) do
        if level_data.outside[1] then
          local cx, cy, cw = getListCenter(level_data.outside)
          
          if not best_area_id or cw > best_w then
            best_area_id, best_level, best_x, best_y, best_ex, best_ey, best_w =
              area_id, level, cx, cy, nil, nil, cw
          end
        end
        
        for entrance, list in pairs(level_data.inside) do
          local cx, cy, cw = getListCenter(list)
          
          if not best_area_id or cw > best_w then
            best_area_id, best_level, best_x, best_y, best_ex, best_ey, best_w =
              area_id, level, cx, cy, entrance.x, entrance.y, cw
          end
        end
      end
    end
  end
  
  return best_area_id, best_level, best_x, best_y, best_ex, best_ey
end

-- TODO: This should be a variable rather than a function.
-- TODO: Document this.
function location_functions:empty()
  return not next(self)
end

function location_functions:weight()
  local weight = 0
  
  for area_id, data in pairs(self) do
    weight = weight + calculateAreaDataWeight(data)
  end
  
  return weight
end

function location_functions:merge(...)
  for i=1,select("#",...) do
    local reference = select(i, ...)
    if reference and reference ~= self then
      for a,l,x,y,ex,ey,w in reference:iterate() do
        self:addLocation(a,l,x,y,ex,ey,w)
      end
    end
  end
  
  return self
end
