Module:table
Documentation for this module may be created at Module:table/doc
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 [[Module:array]].
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 [[c:Module:TableTools|Module:TableTools]] 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 relation_module = "Module:relation"
local table = table
local concat = table.concat
local dump = mw.dumpObject
local insert = table.insert
local invert -- defined as export.invert
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 table_reverse -- defined as export.reverse
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 less_than(...)
less_than = require(relation_module).less_than
return less_than(...)
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
--[==[
Extend an existing list by a new list, modifying the existing list in-place. Compare the Python expression
{list.extend(new_items)}.]==]
function export.extend(t, ...)
if select("#", ...) < 2 then
local i, new_items = 0, ...
while true do
i = i + 1
local item = new_items[i]
if item == nil then
return t
end
insert(t, item)
end
return
end
local i, pos, new_items = 0, ...
while true do
i = i + 1
local item = new_items[i]
if item == nil then
return t
end
insert(t, pos, item)
pos = pos + 1
end
end
--[==[
Given a list, returns a new list consisting of the items between the start index `i` and end index `j` (inclusive). `i` defaults to `1`, and `j` defaults to the length of the input list.]==]
function export.slice(t, i, j)
local t_len = table_len(t)
i = i and signed_index(t_len, i) or 1
local list, offset = {}, i - 1
for key = i, j and signed_index(t_len, j) or t_len do
list[key - offset] = t[key]
end
return list
end
--[==[
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
--[==[
An iterator which works like `indexIpairs`, but which only returns the value.]==]
function export.iterateList(t)
local i = 0
return function()
i = i + 1
return t[i]
end
end
--[==[
This returns the length of a table, or the first integer key n counting from 1 such that t[n + 1] 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[n] == nil
return n - 1
end
table_len = export.length
do
local function get_nested(t, k, ...)
if t == nil then
return nil
elseif select("#", ...) ~= 0 then
return get_nested(t[k], ...)
end
return t[k]
end
--[==[
Given a table and an arbitrary number of keys, will successively access subtables using each key in turn, returning the value at the final key. For example, if {t} is { {[1] = {[2] = {[3] = "foo"}}}}, {export.getNested(t, 1, 2, 3)} will return {"foo"}.
If no subtable exists for a given key value, returns nil, but will throw an error if a non-table is found at an intermediary key.]==]
function export.getNested(t, ...)
if t == nil or select("#", ...) == 0 then
error("Must provide a table and at least one key.")
end
return get_nested(t, ...)
end
end
do
local function set_nested(t, v, k, ...)
if select("#", ...) == 0 then
t[k] = v
return
end
local next_t = t[k]
if next_t == nil then
-- If there's no next table while setting nil, there's nothing more to do.
if v == nil then
return
end
next_t = {}
t[k] = next_t
end
return set_nested(next_t, v, ...)
end
--[==[
Given a table, value and an arbitrary number of keys, will successively access subtables using each key in turn, and sets the value at the final key. For example, if {t} is { {} }, {export.setNested(t, "foo", 1, 2, 3)} will modify {t} to { {[1] = {[2] = {[3] = "foo"} } } }.
If no subtable exists for a given key value, one will be created, but the function will throw an error if a non-table value is found at an intermediary key.
Note: the parameter order (table, value, keys) differs from functions like rawset, because the number of keys can be arbitrary. This is to avoid situations where an additional argument must be appended to arbitrary lists of variables, which can be awkward and error-prone: for example, when handling variable arguments ({{lua|...}}) or function return values.]==]
function export.setNested(t, ...)
if t == nil or select("#", ...) < 2 then
error("Must provide a table and at least one key.")
end
return set_nested(t, ...)
end
end
--[==[
Iterates through a table using `ipairs` in reverse.
`__ipairs` metamethods will be used, including those which return arbitrary (i.e. non-array) keys, but note that this function assumes that the first return value is a key which can be used to retrieve a value from the input table via a table lookup. As such, `__ipairs` metamethods for which this assumption is not true will not work correctly.
If the value `nil` is encountered early (e.g. because the table has been modified), the loop will terminate early.]==]
function export.reverseIpairs(t)
-- `__ipairs` metamethods can return arbitrary keys, so compile a list.
local keys, i = {}, 0
for k in ipairs(t) do
i = i + 1
keys[i] = k
end
return function()
if i == 0 then
return nil
end
local k = keys[i]
-- Retrieve `v` from the table. These aren't stored during the initial ipairs loop, so that they can be modified during the loop.
local v = t[k]
-- Return if not an early nil.
if v ~= nil then
i = i - 1
return k, v
end
end
end
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[i]
for k = i + step, j, step do
ret = func(ret, k, t[k])
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[k] = func(k, t[k])
-- Otherwise, add the existing value if `generate` is set.
elseif generate then
t_new[k] = t[k]
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[k]) 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[k])) 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[1]
if item ~= nil then
local dumped = {}
repeat
dumped[i] = dump(item)
i = i + 1
item = seq[i]
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[1]
end
local conj = options and options.conj
if conj == nil then
conj = "and"
end
if length == 2 then
return seq[1] .. " " .. conj .. " " .. seq[2]
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[length]
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[k]
if v == nil then
return concat(list, sep, i, j)
end
list[k] = v
end
end
--[==[
Values of numeric keys in array portion of table are reversed: { { "a", "b", "c" }} -> { { "c", "b", "a" }}]==]
function export.reverse(t)
local list, t_len = {}, table_len(t)
for i = t_len, 1, -1 do
list[t_len - i + 1] = t[i]
end
return list
end
table_reverse = export.reverse
--[==[
Invert a table. For example, {invert({ "a", "b", "c" })} -> { { a = 1, b = 2, c = 3 }}]==]
function export.invert(t)
local map = {}
for k, v in pairs(t) do
map[v] = k
end
return map
end
invert = export.invert
do
local function flatten(t, list, seen, n)
seen[t] = true
local i = 0
while true do
i = i + 1
local v = t[i]
if v == nil then
return n
elseif type(v) == "table" then
if seen[v] then
error("loop in input list")
end
n = flatten(v, list, seen, n)
else
n = n + 1
list[n] = v
end
end
end
--[==[
Given a list, which may contain sublists, flatten it into a single list. For example, {flatten({ "a", { "b", "c" }, "d" })} ->
{ { "a", "b", "c", "d" }}]==]
function export.flatten(t)
local list = {}
flatten(t, list, {}, 0)
return list
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[alias] = t[k]
end
end
local mt = {}
function mt:__index(k)
local submodule = safe_require("Module:table/" .. k)
self[k] = submodule
return submodule
end
return setmetatable(export, mt)