-- 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 provides some functions for searching in a sorted list.

local floor, insert, remove = math.floor, table.insert, table.remove

local function defaultCmp(a, b)
  return a < b
end

function shared.lowerBound(value, list, cmp)
  cmp = cmp or defaultCmp
  
  local mn, mx = 1, #list+1
  
  while mn ~= mx do
    local m = floor((mn+mx)*0.5)
    
    if cmp(list[m], value) then
      mn = m+1
    else
      mx = m
    end
  end
  
  return mn
end

function shared.upperBound(value, list, cmp)
  cmp = cmp or defaultCmp
  
  local mn, mx = 1, #list+1
  
  while mn ~= mx do
    local m = floor((mn+mx)*0.5)
    
    if cmp(value, list[m]) then
      mx = m
    else
      mn = m+1
    end
  end
  
  return mn
end

-- This function returns another function that will insert objects into a sorted list.
function shared.sortedInserter(list, cmp)
  cmp = cmp or defaultCmp
  
  return function (value)
    local mn, mx = 1, #list+1
    
    while mn ~= mx do
      local m = floor((mn+mx)*0.5)
      
      if cmp(value, list[m]) then
        mx = m
      else
        mn = m+1
      end
    end
    
    insert(list, mn, value)
    return mn
  end
end

-- This function returns another function that will remove objects from a sorted list.
-- An error will be generated if the object isn't found.
function shared.sortedRemover(list, cmp)
  cmp = cmp or defaultCmp
  
  return function (value)
    local mn, mx = 1, #list+1
    
    while mn ~= mx do
      local m = floor((mn+mx)*0.5)
      
      if cmp(value, list[m]) then
        mx = m
      else
        mn = m+1
      end
    end
    
    mn = mn - 1
    
    local k = list[mn]
    
    while k ~= nil do
      if k == value then
        remove(list, mn)
        return mn
      end
      
      mn = mn - 1
      k = list[mn]
    end
    
    error("Value to be removed wasn't found.", 2)
  end
end
