Module:table

local export = {}

--[==[ intro:
This module provides functions for dealing with Lua tables. All of them, except for two helper functions, take a table
as their first argument.

Some functions are available as methods in the arrays created by ].

Functions by what they do:
* Create a new table:
** `shallowCopy`, `deepCopy`, `removeDuplicates`, `numKeys`, `compressSparseArray`, `keysToList`, `reverse`, `invert`, `listToSet`
* Create an array:
** `removeDuplicates`, `numKeys`, `compressSparseArray`, `keysToList`, `reverse`
* Return information about the table:
** `size`, `length`, `contains`, `isArray`, `deepEquals`
* Treat the table as an array (that is, operate on the values in the array portion of the table: values indexed by
  consecutive integers starting at {1}):
** `removeDuplicates`, `length`, `contains`, `serialCommaJoin`, `reverseIpairs`, `reverse`, `invert`, `listToSet`, `isArray`
* Treat a table as a sparse array (that is, operate on values indexed by non-consecutive integers):
** `numKeys`, `maxIndex`, `compressSparseArray`, `sparseConcat`, `sparseIpairs`
* Generate an iterator:
** `sparseIpairs`, `sortedPairs`, `reverseIpairs`
* Other functions:
** `sparseConcat`, `serialCommaJoin`, `reverseConcat`

The original version was a copy of {{w|Module:TableTools}} on Wikipedia via ] on
Commons, but in the course of time this module has been almost completely rewritten, with many new functions added. The
main legacy of this is the use of camelCase for function names rather than snake_case, as is normal in the English
Wiktionary.
]==]

local load_module = "Module:load"
local math_module = "Module:math"

local table = table

local concat = table.concat
local dump = mw.dumpObject
local ipairs = ipairs
local ipairs_default_iter = ipairs{export}
local next = next
local pairs = pairs
local require = require
local select = select
local signed_index -- defined as export.signedIndex
local table_len -- defined as export.length
local type = type

--[==[
Loaders for functions in other modules, which overwrite themselves with the target function when called. This ensures modules are only loaded when needed, retains the speed/convenience of locally-declared pre-loaded functions, and has no overhead after the first call, since the target functions are called directly in any subsequent calls.]==]
local function is_integer(...)
	is_integer = require(math_module).is_integer
	return is_integer(...)
end

local function safe_require(...)
	safe_require = require(load_module).safe_require
	return safe_require(...)
end

--[==[
Given an array and a signed index, returns the true table index. If the signed index is negative, the array will be counted from the end, where {-1} is the highest index in the array; otherwise, the returned index will be the same. To aid optimization, the first argument may be a number representing the array length instead of the array itself; this is useful when the array length is already known, as it avoids recalculating it each time this function is called.]==]
function export.signedIndex(t, k)
	if not is_integer(k) then
		error("index must be an integer")
	end
	return k < 0 and (type(t) == "table" and table_len(t) or t) + k + 1 or k
end
signed_index = export.signedIndex

--[==[
An iterator which works like `pairs`, but ignores any `__pairs` metamethod.]==]
function export.rawPairs(t)
	return next, t, nil
end

--[==[
An iterator which works like `ipairs`, but ignores any `__ipairs` metamethod.]==]
function export.rawIpairs(t)
	return ipairs_default_iter, t, 0
end

--[==[
This returns the length of a table, or the first integer key n counting from 1 such that t is nil. It is a more reliable form of the operator `#`, which can become unpredictable under certain circumstances due to the implementation of tables under the hood in Lua, and therefore should not be used when dealing with arbitrary tables. `#` also does not use metamethods, so will return the wrong value in cases where it is desirable to take these into account (e.g. data loaded via `mw.loadData`). If `raw` is set, then metamethods will be ignored, giving the true table length.

For arrays, this function is faster than `export.size`.]==]
function export.length(t, raw)
	local n = 0
	if raw then
		for i in ipairs_default_iter, t, 0 do
			n = i
		end
		return n
	end
	repeat
		n = n + 1
	until t == nil
	return n - 1
end
table_len = export.length

local function getIteratorValues(i, j , step, t_len)
	i, j = i and signed_index(t_len, i), j and signed_index(t_len, j)
	if step == nil then
		i, j = i or 1, j or t_len
		return i, j, j < i and -1 or 1
	elseif step == 0 or not is_integer(step) then
		error("step must be a non-zero integer")
	elseif step < 0 then
		return i or t_len, j or 1, step
	end
	return i or 1, j or t_len, step
end

--[==[
Given an array `list` and function `func`, iterate through the array applying {func(r, k, v)}, and returning the result,
where `r` is the value calculated so far, `k` is an index, and `v` is the value at index `k`. For example,
{reduce(array, function(a, _, v) return a + v end)} will return the sum of `array`.

Optional arguments:
* `i`: start index; negative values count from the end of the array
* `j`: end index; negative values count from the end of the array
* `step`: step increment
These must be non-zero integers. The function will determine where to iterate from, whether to iterate forwards or
backwards and by how much, based on these inputs (see examples below for default behaviours).

Examples:
# No values for i, j or step results in forward iteration from the start to the end in steps of 1 (the default).
# step=-1 results in backward iteration from the end to the start in steps of 1.
# i=7, j=3 results in backward iteration from indices 7 to 3 in steps of 1 (i.e. step=-1).
# j=-3 results in forward iteration from the start to the 3rd last index.
# j=-3, step=-1 results in backward iteration from the end to the 3rd last index.]==]
function export.reduce(t, func, i, j, step)
	i, j, step = getIteratorValues(i, j, step, table_len(t))
	local ret = t
	for k = i + step, j, step do
		ret = func(ret, k, t)
	end
	return ret
end

do
	local function replace(t, func, i, j, step, generate)
		local t_len = table_len(t)
		-- Normalized i, j and step, based on the inputs.
		local norm_i, norm_j, norm_step = getIteratorValues(i, j, step, t_len)
		if norm_step > 0 then
			i, j, step = 1, t_len, 1
		else
			i, j, step = t_len, 1, -1
		end
		-- "Signed" variables are multiplied by -1 if `step` is negative.
		local t_new, signed_i, signed_j = generate and {} or t, norm_i * step, norm_j * step
		for k = i, j, step do
			-- Replace the values iff they're within the i to j range and `step` wouldn't skip the key.
			-- Note: i > j if `step` is positive; i < j if `step` is negative. Otherwise, the range is empty.
			local signed_k = k * step
			if signed_k >= signed_i and signed_k <= signed_j and (k - norm_i) % norm_step == 0 then
				t_new = func(k, t)
			-- Otherwise, add the existing value if `generate` is set.
			elseif generate then
				t_new = t
			end
		end
		return t_new
	end

	--[==[
	Given an array `list` and function `func`, iterate through the array applying {func(k, v)} (where `k` is an index, and
	`v` is the value at index `k`), replacing the relevant values with the result. For example,
	{apply(array, function(_, v) return 2 * v end)} will double each member of the array.

	Optional arguments:
	* `i`: start index; negative values count from the end of the array
	* `j`: end index; negative values count from the end of the array
	* `step`: step increment
	These must be non-zero integers. The function will determine where to iterate from, whether to iterate forwards or
	backwards and by how much, based on these inputs (see examples below for default behaviours).

	Examples:
	# No values for i, j or step results in forward iteration from the start to the end in steps of 1 (the default).
	# step=-1 results in backward iteration from the end to the start in steps of 1.
	# i=7, j=3 results in backward iteration from indices 7 to 3 in steps of 1 (i.e. step=-1).
	# j=-3 results in forward iteration from the start to the 3rd last index.
	# j=-3, step=-1 results in backward iteration from the end to the 3rd last index.]==]
	function export.apply(t, func, i, j, step)
		return replace(t, func, i, j, step, false)
	end

	--[==[
	Given an array `list` and function `func`, iterate through the array applying {func(k, v)} (where `k` is an index, and
	`v` is the value at index `k`), and return a shallow copy of the original array with the relevant values replaced. For example,
	{generate(array, function(_, v) return 2 * v end)} will return a new array in which each value has been doubled.

	Optional arguments:
	* `i`: start index; negative values count from the end of the array
	* `j`: end index; negative values count from the end of the array
	* `step`: step increment
	These must be non-zero integers. The function will determine where to iterate from, whether to iterate forwards or
	backwards and by how much, based on these inputs (see examples below for default behaviours).

	Examples:
	# No values for i, j or step results in forward iteration from the start to the end in steps of 1 (the default).
	# step=-1 results in backward iteration from the end to the start in steps of 1.
	# i=7, j=3 results in backward iteration from indices 7 to 3 in steps of 1 (i.e. step=-1).
	# j=-3 results in forward iteration from the start to the 3rd last index.
	# j=-3, step=-1 results in backward iteration from the end to the 3rd last index.]==]
	function export.generate(t, func, i, j, step)
		return replace(t, func, i, j, step, true)
	end
end

--[==[
Given an array `list` and function `func`, iterate through the array applying {func(k, v)} (where `k` is an index, and
`v` is the value at index `k`), and returning whether the function is true for all iterations.

Optional arguments:
* `i`: start index; negative values count from the end of the array
* `j`: end index; negative values count from the end of the array
* `step`: step increment
These must be non-zero integers. The function will determine where to iterate from, whether to iterate forwards or
backwards and by how much, based on these inputs (see examples below for default behaviours).

Examples:
# No values for i, j or step results in forward iteration from the start to the end in steps of 1 (the default).
# step=-1 results in backward iteration from the end to the start in steps of 1.
# i=7, j=3 results in backward iteration from indices 7 to 3 in steps of 1 (i.e. step=-1).
# j=-3 results in forward iteration from the start to the 3rd last index.
# j=-3, step=-1 results in backward iteration from the end to the 3rd last index.]==]
function export.all(t, func, i, j, step)
	i, j, step = getIteratorValues(i, j, step, table_len(t))
	for k = i, j, step do
		if not func(k, t) then
			return false
		end
	end
	return true
end

--[==[
Given an array `list` and function `func`, iterate through the array applying {func(k, v)} (where `k` is an index, and
`v` is the value at index `k`), and returning whether the function is true for at least one iteration.

Optional arguments:
* `i`: start index; negative values count from the end of the array
* `j`: end index; negative values count from the end of the array
* `step`: step increment
These must be non-zero integers. The function will determine where to iterate from, whether to iterate forwards or
backwards and by how much, based on these inputs (see examples below for default behaviours).

Examples:
# No values for i, j or step results in forward iteration from the start to the end in steps of 1 (the default).
# step=-1 results in backward iteration from the end to the start in steps of 1.
# i=7, j=3 results in backward iteration from indices 7 to 3 in steps of 1 (i.e. step=-1).
# j=-3 results in forward iteration from the start to the 3rd last index.
# j=-3, step=-1 results in backward iteration from the end to the 3rd last index.]==]
function export.any(t, func, i, j, step)
	i, j, step = getIteratorValues(i, j, step, table_len(t))
	for k = i, j, step do
		if not not (func(k, t)) then
			return true
		end
	end
	return false
end

--[==[
Joins an array with serial comma and serial conjunction, normally {"and"}. An improvement on {mw.text.listToText},
which doesn't properly handle serial commas.

Options:
* `conj`: Conjunction to use; defaults to {"and"}.
* `punc`: Punctuation to use; default to {","}.
* `dontTag`: Don't tag the serial comma and serial {"and"}. For error messages, in which HTML cannot be used.
* `dump`: Each item will be serialized with {mw.dumpObject}. For warnings and error messages.]==]
function export.serialCommaJoin(seq, options)
	-- If the `dump` option is set, determine the table length as part of the
	-- dump loop, instead of calling `table_len` separately.
	local length
	if options and options.dump then
		local i, item = 1, seq
		if item ~= nil then
			local dumped = {}
			repeat
				dumped = dump(item)
				i = i + 1
				item = seq
			until item == nil
			seq = dumped
		end
		length = i - 1
	else
		length = table_len(seq)
	end

	if length == 0 then
		return ""
	elseif length == 1 then
		return seq
	end

	local conj = options and options.conj
	if conj == nil then
		conj = "and"
	end

	if length == 2 then
		return seq .. " " .. conj .. " " .. seq
	end

	local punc, dont_tag
	if options then
		punc = options.punc
		if punc == nil then
			punc = ","
		end
		dont_tag = options.dontTag
	else
		punc = ","
	end

	local comma
	if dont_tag then
		comma = "" -- since by default the serial comma doesn't display, when we can't tag we shouldn't display it.
		conj = " " .. conj .. " "
	else
		comma = "<span class=\"serial-comma\">" .. punc .. "</span>"
		conj = "<span class=\"serial-and\"> " .. conj .. "</span> "
	end

	return concat(seq, punc .. " ", 1, length - 1) .. comma .. conj .. seq
end

--[==[
A function which works like `table.concat`, but respects any `__index` metamethod. This is useful for data loaded via `mw.loadData`.]==]
function export.concat(t, sep, i, j)
	local list, k = {}, 0
	while true do
		k = k + 1
		local v = t
		if v == nil then
			return concat(list, sep, i, j)
		end
		list = v
	end
end

--[==[
Add a list of aliases for a given key to a table. The aliases must be given as a table.]==]
function export.alias(t, k, aliases)
	for _, alias in pairs(aliases) do
		t = t
	end
end

local mt = {}

function mt:__index(k)
	local submodule = safe_require("Module:table/" .. k)
	self = submodule
	return submodule
end

return setmetatable(export, mt)