---
-- TableTools --
-- --
-- This module includes a number of functions for dealing with Lua tables. --
-- It is a meta-module, meant to be called from other Lua modules, and should not --
-- be called directly from #invoke. --
---  
local libraryUtil = require('libraryUtil')  
local p = {}  
-- Define often-used variables and functions.
local floor = math.floor
local infinity = math.huge
local checkType = libraryUtil.checkType
local checkTypeMulti = libraryUtil.checkTypeMulti  
---
-- isPositiveInteger
---
-- This function returns true if the given value is a positive integer, and false
-- if not. Although it doesn't operate on tables, it is included here as it is
-- useful for determining whether a given table key is in the array part or the
-- hash part of a table.
---
function p.isPositiveInteger(v)
return type(v) == 'number' and v >= 1 and floor(v) == v and v < infinity
end  
---
-- isNan
---
-- This function returns true if the given number is a NaN value, and false if
-- not. Although it doesn't operate on tables, it is included here as it is useful
-- for determining whether a value can be a valid table key. Lua will generate an
-- error if a NaN is used as a table key.
---
function p.isNan(v)
return type(v) == 'number' and v ~= v
end  
---
-- shallowClone
---
-- This returns a clone of a table. The value returned is a new table, but all
-- subtables and functions are shared. Metamethods are respected, but the returned
-- table will have no metatable of its own.
---
function p.shallowClone(t)
checkType('shallowClone', 1, t, 'table')
local ret = {}
for k, v in pairs(t) do
ret[k] = v
end
return ret
end  
---
-- removeDuplicates
---
-- This removes duplicate values from an array. Non-positive-integer keys are
-- ignored. The earliest value is kept, and all subsequent duplicate values are
-- removed, but otherwise the array order is unchanged.
---
function p.removeDuplicates(arr)
checkType('removeDuplicates', 1, arr, 'table')
local isNan = p.isNan
local ret, exists = {}, {}
for _, v in ipairs(arr) do
if isNan(v) then
-- NaNs can't be table keys, and they are also unique, so we don't need to check existence.
ret[#ret + 1] = v
elseif not exists[v] then
ret[#ret + 1] = v
exists[v] = true
end
end
return ret
end  
---
-- numKeys
---
-- This takes a table and returns an array containing the numbers of any numerical
-- keys that have non-nil values, sorted in numerical order.
---
function p.numKeys(t)
checkType('numKeys', 1, t, 'table')
local isPositiveInteger = p.isPositiveInteger
local nums = {}
for k in pairs(t) do
if isPositiveInteger(k) then
nums[#nums + 1] = k
end
end
table.sort(nums)
return nums
end  
---
-- affixNums
---
-- This takes a table and returns an array containing the numbers of keys with the
-- specified prefix and suffix. For example, for the table
-- {a1 = 'foo', a3 = 'bar', a6 = 'baz'} and the prefix "a", affixNums will return
-- {1, 3, 6}.
---
function p.affixNums(t, prefix, suffix)
checkType('affixNums', 1, t, 'table')
checkType('affixNums', 2, prefix, 'string', true)
checkType('affixNums', 3, suffix, 'string', true)  
local function cleanPattern(s)
-- Cleans a pattern so that the magic characters %.[]*+-?^$ are interpreted literally.
return s:gsub('([%(%)%%%.%[%]%*%+%-%?%^%$])', '%%%1')
end  
prefix = prefix or ''
suffix = suffix or ''
prefix = cleanPattern(prefix)
suffix = cleanPattern(suffix)
local pattern = '^' .. prefix .. '([1-9]%d*)' .. suffix .. '$'  
local nums = {}
for k in pairs(t) do
if type(k) == 'string' then
local num = mw.ustring.match(k, pattern)
if num then
nums[#nums + 1] = tonumber(num)
end
end
end
table.sort(nums)
return nums
end  
---
-- numData
---
-- Given a table with keys like {"foo1", "bar1", "foo2", "baz2"}, returns a table
-- of subtables in the format
-- {[1] = {foo = 'text', bar = 'text'}, [2] = {foo = 'text', baz = 'text'}}.
-- Keys that don't end with an integer are stored in a subtable named "other". The
-- compress option compresses the table so that it can be iterated over with
-- ipairs.
---
function p.numData(t, compress)
checkType('numData', 1, t, 'table')
checkType('numData', 2, compress, 'boolean', true)
local ret = {}
for k, v in pairs(t) do
local prefix, num = mw.ustring.match(tostring(k), '^([^0-9]*)([1-9][0-9]*)$')
if num then
num = tonumber(num)
local subtable = ret[num] or {}
if prefix == '' then
-- Positional parameters match the blank string; put them at the start of the subtable instead.
prefix = 1
end
subtable[prefix] = v
ret[num] = subtable
else
local subtable = ret.other or {}
subtable[k] = v
ret.other = subtable
end
end
if compress then
local other = ret.other
ret = p.compressSparseArray(ret)
ret.other = other
end
return ret
end  
---
-- compressSparseArray
---
-- This takes an array with one or more nil values, and removes the nil values
-- while preserving the order, so that the array can be safely traversed with
-- ipairs.
---
function p.compressSparseArray(t)
checkType('compressSparseArray', 1, t, 'table')
local ret = {}
local nums = p.numKeys(t)
for _, num in ipairs(nums) do
ret[#ret + 1] = t[num]
end
return ret
end  
---
-- sparseIpairs
---
-- This is an iterator for sparse arrays. It can be used like ipairs, but can
-- handle nil values.
---
function p.sparseIpairs(t)
checkType('sparseIpairs', 1, t, 'table')
local nums = p.numKeys(t)
local i = 0
local lim = #nums
return function
i = i + 1
if i <= lim then
local key = nums[i]
return key, t[key]
else
return nil, nil
end
end
end  
---
-- size
---
-- This returns the size of a key/value pair table. It will also work on arrays,
-- but for arrays it is more efficient to use the # operator.
---
function p.size(t)
checkType('size', 1, t, 'table')
local i = 0
for _ in pairs(t) do
i = i + 1
end
return i
end  
local function defaultKeySort(item1, item2)
-- "number" < "string", so numbers will be sorted before strings.
local type1, type2 = type(item1), type(item2)
if type1 ~= type2 then
return type1 < type2
elseif type1 == 'table' or type1 == 'boolean' or type1 == 'function' then
return tostring(item1) < tostring(item2)
else
return item1 < item2
end
end
---
-- keysToList
---
-- Returns an array of the keys in a table, sorted using either a default
-- comparison function or a custom keySort function.
---
function p.keysToList(t, keySort, checked)
if not checked then
checkType('keysToList', 1, t, 'table')
checkTypeMulti('keysToList', 2, keySort, {'function', 'boolean', 'nil'})
end  
local arr = {}
local index = 1
for k in pairs(t) do
arr[index] = k
index = index + 1
end  
if keySort ~= false then
keySort = type(keySort) == 'function' and keySort or defaultKeySort
table.sort(arr, keySort)
end  
return arr
end  
---
-- sortedPairs
---
-- Iterates through a table, with the keys sorted using the keysToList function.
-- If there are only numerical keys, sparseIpairs is probably more efficient.
---
function p.sortedPairs(t, keySort)
checkType('sortedPairs', 1, t, 'table')
checkType('sortedPairs', 2, keySort, 'function', true)  
local arr = p.keysToList(t, keySort, true)  
local i = 0
return function
i = i + 1
local key = arr[i]
if key ~= nil then
return key, t[key]
else
return nil, nil
end
end
end  
---
-- isArray
---
-- Returns true if the given value is a table and all keys are consecutive
-- integers starting at 1.
---
function p.isArray(v)
if type(v) ~= 'table' then
return false
end
local i = 0
for _ in pairs(v) do
i = i + 1
if v[i] == nil then
return false
end
end
return true
end  
---
-- isArrayLike
---
-- Returns true if the given value is iterable and all keys are consecutive
-- integers starting at 1.
---
function p.isArrayLike(v)
if not pcall(pairs, v) then
return false
end
local i = 0
for _ in pairs(v) do
i = i + 1
if v[i] == nil then
return false
end
end
return true
end  
---
-- invert
---
-- Transposes the keys and values in an array. For example, {"a", "b", "c"} ->
-- {a = 1, b = 2, c = 3}. Duplicates are not supported (result values refer to
-- the index of the last duplicate) and NaN values are ignored.
---