Editing Module:Array

Jump to navigation Jump to search
Warning: You are not logged in. Once you make an edit, a temporary account will be created for you. Learn more. Log in or create an account to continue receiving notifications after this account expires, and to access other features.
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.
Latest revision Your text
Line 1: Line 1:
-- <nowiki> awawa
local libraryUtil = require('libraryUtil')
local libraryUtil = require('libraryUtil')
local checkType = libraryUtil.checkType
local checkType = libraryUtil.checkType
local checkTypeMulti = libraryUtil.checkTypeMulti
local checkTypeMulti = libraryUtil.checkTypeMulti
local arr = {}


---Returns the length of the array but it also works on proxy arrays
setmetatable(arr, {
---@param arr any[]
__call = function (_, array)
---@return integer
return arr.new(array)
local function len(arr)
end
local l = #arr
})
if l == 0 then
 
if arr[1] ~= nil then
function arr.__index(t, k)
-- Exponential search to find length of proxy table
if type(k) == 'table' then
local low = 1
local res = arr.new()
local high = 1
for i = 1, #t do
local ceil = math.ceil
res[i] = t[k[i]]
while arr[high] ~= nil do
high = high * 2
end
while low ~= high do
local m = ceil((low + high) / 2)
if arr[m] == nil then
high = m - 1
else
low = m
end
end
return low
else
return 0
end
end
return res
else
else
return l
return arr[k]
end
end
end
end


---@class Array
function arr.__tostring(array)
---@operator call(any[]): Array
local dumpObject = mw.dumpObject --require('Module:Logger').dumpObject
---@operator concat(any[]): Array
setmetatable(array, nil)
---@operator concat(number|string|function): string
local str = dumpObject(array, {clean=true, collapseLimit=100})
---@operator unm: Array
setmetatable(array, arr)
---@operator add(number|number[]|Array): Array
return str
---@operator sub(number|number[]|Array): Array
end
---@operator mul(number|number[]|Array): Array
---@operator div(number|number[]|Array): Array
---@operator pow(number|number[]|Array): Array
local Array = {
pop = table.remove,
len = len
}
Array.__index = Array
 
setmetatable(Array, {
__index = table,
__call = function (_, arr)
return Array.new(arr)
end
})


function Array.__concat(lhs, rhs)
function arr.__concat(lhs, rhs)
if type(lhs) == 'table' and type(rhs) == 'table' then
if type(lhs) == 'table' and type(rhs) == 'table' then
local res = {}
local res = setmetatable({}, getmetatable(lhs) or getmetatable(rhs))
local l1 = len(lhs)
for i = 1, #lhs do
for i = 1, l1 do
res[i] = lhs[i]
res[i] = lhs[i]
end
end
for i = 1, len(rhs) do
local l = #lhs
res[l1 + i] = rhs[i]
for i = 1, #rhs do
res[i + l] = rhs[i]
end
end
return setmetatable(res, getmetatable(lhs) or getmetatable(rhs))
return res
else
else
return tostring(lhs) .. tostring(rhs)
return tostring(lhs) .. tostring(rhs)
Line 73: Line 47:
end
end


function Array.__unm(arr)
function arr.__unm(array)
return Array.map(arr, function(x) return -x end)
return arr.map(array, function(x) return -x end)
end
end


---@param lhs number|number[]|Array
local function mathTemplate(lhs, rhs, funName, fun)
---@param rhs number|number[]|Array
---@param funName string
---@param opName string
---@param fun fun(lhs: number, rhs: number): number
---@return Array
local function mathTemplate(lhs, rhs, funName, opName, fun)
checkTypeMulti('Module:Array.' .. funName, 1, lhs, {'number', 'table'})
checkTypeMulti('Module:Array.' .. funName, 1, lhs, {'number', 'table'})
checkTypeMulti('Module:Array.' .. funName, 2, rhs, {'number', 'table'})
checkTypeMulti('Module:Array.' .. funName, 2, rhs, {'number', 'table'})
local res = {}
local res = setmetatable({}, getmetatable(lhs) or getmetatable(rhs))


if type(lhs) == 'number' then
if type(lhs) == 'number' then
for i = 1, len(rhs) do
for i = 1, #rhs do
res[i] = fun(lhs, rhs[i])
res[i] = fun(lhs, rhs[i])
end
end
elseif type(rhs) == 'number' then
elseif type(rhs) == 'number' then
for i = 1, len(lhs) do
for i = 1, #lhs do
res[i] = fun(lhs[i], rhs)
res[i] = fun(lhs[i], rhs)
end
end
else
else
assert(len(lhs) == len(rhs), string.format('Elementwise %s failed because arrays have different sizes (left: %d, right: %d)', opName, len(lhs), len(rhs)))
assert(#lhs == #rhs, string.format('Tables are not equal length (lhs=%d, rhs=%d)', #lhs, #rhs))
for i = 1, len(lhs) do
for i = 1, #lhs do
res[i] = fun(lhs[i], rhs[i])
res[i] = fun(lhs[i], rhs[i])
end
end
end
end


return setmetatable(res, getmetatable(lhs) or getmetatable(rhs))
return res
end
end


function Array.__add(lhs, rhs)
function arr.__add(lhs, rhs)
return mathTemplate(lhs, rhs, '__add', 'addition', function(x, y) return x + y end)
return mathTemplate(lhs, rhs, '__add', function(x, y) return x + y end)
end
end


function Array.__sub(lhs, rhs)
function arr.__sub(lhs, rhs)
return mathTemplate(lhs, rhs, '__sub', 'substraction', function(x, y) return x - y end)
return mathTemplate(lhs, rhs, '__sub', function(x, y) return x - y end)
end
end


function Array.__mul(lhs, rhs)
function arr.__mul(lhs, rhs)
return mathTemplate(lhs, rhs, '__mul', 'multiplication', function(x, y) return x * y end)
return mathTemplate(lhs, rhs, '__mul', function(x, y) return x * y end)
end
end


function Array.__div(lhs, rhs)
function arr.__div(lhs, rhs)
return mathTemplate(lhs, rhs, '__div', 'division', function(x, y) return x / y end)
return mathTemplate(lhs, rhs, '__div', function(x, y) return x / y end)
end
end


function Array.__pow(lhs, rhs)
function arr.__pow(lhs, rhs)
return mathTemplate(lhs, rhs, '__pow', 'exponentiation', function(x, y) return x ^ y end)
return mathTemplate(lhs, rhs, '__pow', function(x, y) return x ^ y end)
end
end


function Array.__eq(lhs, rhs)
function arr.__lt(lhs, rhs)
if len(lhs) ~= len(rhs) then
for i = 1, math.min(#lhs, #rhs) do
if lhs[i] >= rhs[i] then
return false
end
end
return true
end
 
function arr.__le(lhs, rhs)
for i = 1, math.min(#lhs, #rhs) do
if lhs[i] > rhs[i] then
return false
end
end
return true
end
 
function arr.__eq(lhs, rhs)
if #lhs ~= #rhs then
return false
return false
end
end
for i = 1, len(lhs) do
for i = 1, #lhs do
if lhs[i] ~= rhs[i] then
if lhs[i] ~= rhs[i] then
return false
return false
Line 138: Line 124:
end
end


---Behaviour depends on the value of `fn`:
function arr.all(array, fn)
---* `nil` - Checks that the array doesn't contain any **false** elements.
checkType('Module:Array.all', 1, array, 'table')
---* `fun(elem: any, i?: integer): boolean` - Returns **true** if `fn` returns **true** for every element.
---* `number` | `table` | `boolean` - Checks that all elements in `arr` are equal to this value.
---@param arr any[]
---@param fn? any
---@return boolean
function Array.all(arr, fn)
checkType('Module:Array.all', 1, arr, 'table')
if fn == nil then fn = function(item) return item end end
if fn == nil then fn = function(item) return item end end
if type(fn) ~= 'function' then
if type(fn) ~= 'function' then
Line 152: Line 131:
fn = function(item) return item == val end
fn = function(item) return item == val end
end
end
for i = 1, len(arr) do
local i = 1
---@diagnostic disable-next-line: redundant-parameter
while array[i] ~= nil do
if not fn(arr[i], i) then
if not fn(array[i], i) then
return false
return false
end
end
i = i + 1
end
end
return true
return true
end
end


---Behaviour depends on the value of `fn`:
function arr.any(array, fn)
---* `nil` - Checks that the array contains at least one non **false** element.
checkType('Module:Array.any', 1, array, 'table')
---* `fun(elem: any, i?: integer): boolean` - Returns **true** if `fn` returns **true** for at least one element.
---* `number` | `table` | `boolean` - Checks that `arr` contains this value.
---@param arr any[]
---@param fn? any
---@return boolean
function Array.any(arr, fn)
checkType('Module:Array.any', 1, arr, 'table')
if fn == nil then fn = function(item) return item end end
if fn == nil then fn = function(item) return item end end
if type(fn) ~= 'function' then
if type(fn) ~= 'function' then
Line 175: Line 148:
fn = function(item) return item == val end
fn = function(item) return item == val end
end
end
for i = 1, len(arr) do
local i = 1
---@diagnostic disable-next-line: redundant-parameter
while array[i] ~= nil do
if fn(arr[i], i) then
if fn(array[i], i) then
return true
return true
end
end
i = i + 1
end
end
return false
return false
end
end


---Recursively removes all metatables.
function arr.clean(array)
---@param arr any[]
checkType('Module:Array.clean', 1, array, 'table')
---@return any[]
for i = 1, #array do
function Array.clean(arr)
if type(array[i]) == 'table' then
checkType('Module:Array.clean', 1, arr, 'table')
arr.clean(array[i])
for i = 1, len(arr) do
if type(arr[i]) == 'table' then
Array.clean(arr[i])
end
end
end
end
setmetatable(arr, nil)
setmetatable(array, nil)
return arr
return array
end
end


---Make a copy of the input table. Preserves metatables.
function arr.contains(array, elem, useElemTableContent)
---@generic T: any[]
checkType('Module:Array.contains', 1, array, 'table')
---@param arr T
if type(elem) == 'table' and useElemTableContent ~= false then
---@param deep? boolean # Recursively clone subtables if **true**.
local elemMap = {}
---@return T
local isFound = {}
function Array.clone(arr, deep)
arr.each(elem, function(x, i) elemMap[x] = i; isFound[i] = false end)
checkType('Module:Array.clone', 1, arr, 'table')
for i = 1, #array do
checkType('Module:Array.clone', 2, deep, 'boolean', true)
local j = elemMap[array[i]]
local res = {}
if j then
for i = 1, len(arr) do
isFound[j] = true
if deep == true and type(arr[i]) == 'table' then
end
res[i] = Array.clone(arr[i], true)
else
res[i] = arr[i]
end
end
return arr.all(isFound, true)
else
return arr.any(array, function(item) return item == elem end)
end
end
return setmetatable(res, getmetatable(arr))
end
end


---Check if `arr` contains `val`.
function arr.count(array, fn)
---@param arr any[]
checkType('Module:Array.count', 1, array, 'table')
---@param val any
if fn == nil then fn = function(item) return item end end
---@return boolean
if type(fn) ~= 'function' then
function Array.contains(arr, val)
local val = fn
checkType('Module:Array.contains', 1, arr, 'table')
fn = function(item) return item == val end
for i = 1, len(arr) do
if arr[i] == val then
return true
end
end
return false
end
 
---Check if `arr` contains any of the values in the table `t`.
---@param arr any[]
---@param t any[]
---@return boolean
function Array.containsAny(arr, t)
checkType('Module:Array.containsAny', 1, arr, 'table')
checkType('Module:Array.containsAny', 2, t, 'table')
local lookupTbl = {}
for i = 1, len(t) do
lookupTbl[t[i]] = true
end
for i = 1, len(arr) do
if lookupTbl[arr[i]] then
return true
end
end
return false
end
 
---Check if `arr` contains all values in the table `t`.
---@param arr any[]
---@param t any[]
---@return boolean
function Array.containsAll(arr, t)
checkType('Module:Array.containsAll', 1, arr, 'table')
checkType('Module:Array.containsAll', 2, t, 'table')
local lookupTbl = {}
local trueCount = 0
local l = len(t)
for i = 1, l do
lookupTbl[t[i]] = false
end
for i = 1, len(arr) do
if lookupTbl[arr[i]] == false then
lookupTbl[arr[i]] = true
trueCount = trueCount + 1
end
if trueCount == l then
return true
end
end
return false
end
 
---Convolute two number arrays.
---@generic T: number[]
---@param x T
---@param y T
---@return T
function Array.convolve(x, y)
checkType('Module:Array.convolve', 1, x, 'table')
checkType('Module:Array.convolve', 2, y, 'table')
local z = {}
    local xLen, yLen = len(x), len(y)
    for j = 1, (xLen + yLen - 1) do
        local sum = 0
        for k = math.max(1, j - yLen + 1), math.min(xLen, j) do
            sum = sum + x[k] * y[j-k+1]
        end
        z[j] = sum
    end
    return setmetatable(z, getmetatable(x) or getmetatable(y))
end
 
---Remove **nil** values from `arr` while preserving order.
---@generic T: any[]
---@param arr T
---@return T
function Array.condenseSparse(arr)
checkType('Module:Array.condenseSparse', 1, arr, 'table')
local keys = {}
local res = {}
local l = 0
for k in pairs(arr) do
l = l + 1
keys[l] = k
end
table.sort(keys)
for i =  1, l do
res[i] = arr[keys[i]]
end
return setmetatable(res, getmetatable(arr))
end
 
---Behaviour depends on value of `val`:
---* `nil` - Counts the number of non **false** elements.
---* `fun(elem: any): boolean` - Count the number of times the function returned **true**.
---* `boolean` | `number` | `table` - Counts the number of times this value occurs in `arr`.
---@param arr any[]
---@param val? any
---@return integer
function Array.count(arr, val)
checkType('Module:Array.count', 1, arr, 'table')
if val == nil then val = function(item) return item end end
if type(val) ~= 'function' then
local _val = val
val = function(item) return item == _val end
end
end
local count = 0
local count = 0
for i = 1, len(arr) do
for i = 1, #array do
if val(arr[i]) then
if fn(array[i]) then
count = count + 1
count = count + 1
end
end
Line 338: Line 203:
end
end


---Differentiate the array
function arr.diff(array, order)
---@generic T: number[]
checkType('Module:Array.diff', 1, array, 'table')
---@param arr T
---@param order number? # Oder of the differentiation. Default is 1.
---@return T # Length is `#arr - order`
function Array.diff(arr, order)
checkType('Module:Array.diff', 1, arr, 'table')
checkType('Module:Array.diff', 2, order, 'number', true)
checkType('Module:Array.diff', 2, order, 'number', true)
local res = {}
local res = setmetatable({}, getmetatable(array))
for i = 1, len(arr) - 1 do
for i = 1, #array - 1 do
res[i] = arr[i+1] - arr[i]
res[i] = array[i+1] - array[i]
end
end
if order and order > 1 then
if order and order > 1 then
return Array.diff(res, order - 1)
return arr.diff(res, order - 1)
end
end
return setmetatable(res, getmetatable(arr))
return res
end
end


---Loops over `arr` and passes each element as the first argument to `fn`. This function returns nothing.
function arr.each(array, fn)
---@param arr any[]
checkType('Module:Array.each', 1, array, 'table')
---@param fn fun(elem: any, i?: integer)
function Array.each(arr, fn)
checkType('Module:Array.each', 1, arr, 'table')
checkType('Module:Array.each', 2, fn, 'function')
checkType('Module:Array.each', 2, fn, 'function')
for i = 1, len(arr) do
local i = 1
fn(arr[i], i)
while array[i] ~= nil do
fn(array[i], i)
i = i + 1
end
end
end
end


---Makes a copy of `arr` with only elements for which `fn` returned **true**.
function arr.filter(array, fn)
---@generic T: any[]
checkType('Module:Array.filter', 1, array, 'table')
---@param arr T
if fn == nil then fn = function(item) return item end end
---@param fn fun(elem: any, i?: integer): boolean
if type(fn) ~= 'function' then
---@return T
local val = fn
function Array.filter(arr, fn)
fn = function(item) return item == val end
checkType('Module:Array.filter', 1, arr, 'table')
end
checkType('Module:Array.filter', 2, fn, 'function')
local r = setmetatable({}, getmetatable(array))
local r = {}
local len = 0
local l = 0
local i = 1
for i = 1, len(arr) do
while array[i] ~= nil do
if fn(arr[i], i) then
if fn(array[i], i) then
l = l + 1
len = len + 1
r[l] = arr[i]
r[len] = array[i]
end
end
i = i + 1
end
end
return setmetatable(r, getmetatable(arr))
return r
end
end


---Find the first elements for which `fn` returns **true**.
function arr.find(array, fn, default)
---@param arr any[]
checkType('Module:Array.find', 1, array, 'table')
---@param fn any # A value to look for or a function of the form `fun(elem: any, i?: integer): boolean`.
---@param default? any # Value to return if no element passes the test.
---@return any? elem # The first element that passed the test.
---@return integer? i # The index of the item that passed the test.
function Array.find(arr, fn, default)
checkType('Module:Array.find', 1, arr, 'table')
checkTypeMulti('Module:Array.find_index', 2, fn, {'function', 'table', 'number', 'boolean'})
checkTypeMulti('Module:Array.find_index', 2, fn, {'function', 'table', 'number', 'boolean'})
if type(fn) ~= 'function' then
if type(fn) ~= 'function' then
local _val = fn
local val = fn
fn = function(item) return item == _val end
fn = function(item) return item == val end
end
end
for i = 1, len(arr) do
local i = 1
---@diagnostic disable-next-line: redundant-parameter
while array[i] ~= nil do
if fn(arr[i], i) then
if fn(array[i], i) then
return arr[i], i
return array[i], i
end
end
i = i + 1
end
end
return default, nil
return default
end
end


---Find the index of `val`.
function arr.find_index(array, fn, default)
---@param arr any[]
checkType('Module:Array.find_index', 1, array, 'table')
---@param val any # A value to look for or a function of the form `fun(elem: any, i?: integer): boolean`.
checkTypeMulti('Module:Array.find_index', 2, fn, {'function', 'table', 'number', 'boolean'})
---@param default? any # Value to return if no element passes the test.
if type(fn) ~= 'function' then
---@return integer?
local val = fn
function Array.find_index(arr, val, default)
fn = function(item) return item == val end
checkType('Module:Array.find_index', 1, arr, 'table')
checkTypeMulti('Module:Array.find_index', 2, val, {'function', 'table', 'number', 'boolean'})
if type(val) ~= 'function' then
local _val = val
val = function(item) return item == _val end
end
end
for i = 1, len(arr) do
local i = 1
---@diagnostic disable-next-line: redundant-parameter
while array[i] ~= nil do
if val(arr[i], i) then
if fn(array[i], i) then
return i
return i
end
end
i = i + 1
end
end
return default
return default
end
end


---Extracts a subset of `arr`.
function arr.newIncrementor(start, step)
---@generic T: any[]
checkType('Module:Array.newIncrementor', 1, start, 'number', true)
---@param arr T
checkType('Module:Array.newIncrementor', 2, step, 'number', true)
---@param indexes integer|integer[] # Indexes of the elements.
step = step or 1
---@return T
local n = (start or 1) - step
function Array.get(arr, indexes)
local obj = {}
checkType('Module:Array.set', 1, arr, 'table')
return setmetatable(obj, {
checkTypeMulti('Module:Array.set', 2, indexes, {'table', 'number'})
__call = function() n = n + step return n end,
if type(indexes) == 'number' then
__tostring = function() return n end,
indexes = {indexes}
__index = function() return n end,
end
__newindex = function(self, k, v)
local res = {}
if k == 'step' and type(v) == 'number' then
for i = 1, len(indexes) do
step = v
res[i] = arr[indexes[i]]
elseif type(v) == 'number' then
end
n = v
return setmetatable(res, getmetatable(arr))
end
end,
__concat = function(x, y) return tostring(x) .. tostring(y) end
})
end
end


---Integrates the array. Effectively does $\left\{\sum^{n}_{start}{arr[n]} \,\Bigg|\, n \in [start, stop]\right\}$.
function arr.int(array, start, stop)
---@generic T: number[]
checkType('Module:Array.int', 1, array, 'table')
---@param arr T # number[]
---@param start? integer # Index where to start the summation. Defaults to 1.
---@param stop? integer # Index where to stop the summation. Defaults to #arr.
---@return T
function Array.int(arr, start, stop)
checkType('Module:Array.int', 1, arr, 'table')
checkType('Module:Array.int', 2, start, 'number', true)
checkType('Module:Array.int', 2, start, 'number', true)
checkType('Module:Array.int', 3, stop, 'number', true)
checkType('Module:Array.int', 3, stop, 'number', true)
local res = {}
local res = setmetatable({}, getmetatable(array))
start = start or 1
start = start or 1
stop = stop or len(arr)
stop = stop or #array
res[1] = arr[start]
res[1] = array[start]
for i = 1, stop - start do
for i = 1, stop - start do
res[i+1] = res[i] + arr[start + i]
res[i+1] = res[i] + array[start + i]
end
end
return setmetatable(res, getmetatable(arr))
return res
end
end


---Returns an array with elements that are present in both tables.
function arr.intersect(array1, array2)
---@generic T: any[]
checkType('Module:Array.intersect', 1, array1, 'table')
---@param arr1 T
checkType('Module:Array.intersect', 2, array2, 'table')
---@param arr2 T
local array2Elements = {}
---@return T
local res = setmetatable({}, getmetatable(array1) or getmetatable(array2))
function Array.intersect(arr1, arr2)
local len = 0
checkType('Module:Array.intersect', 1, arr1, 'table')
arr.each(array2, function(item) array2Elements[item] = true end)
checkType('Module:Array.intersect', 2, arr2, 'table')
arr.each(array1, function(item)
local arr2Elements = {}
if array2Elements[item] then
local res = {}
len = len + 1
local l = 0
res[len] = item
Array.each(arr2, function(item) arr2Elements[item] = true end)
Array.each(arr1, function(item)
if arr2Elements[item] then
l = l + 1
res[l] = item
end
end
end)
end)
return setmetatable(res, getmetatable(arr1) or getmetatable(arr2))
return res
end
end


---Checks if the two inputs have at least one element in common.
function arr.intersects(array1, array2)
---@param arr1 any[]
checkType('Module:Array.intersects', 1, array1, 'table')
---@param arr2 any[]
checkType('Module:Array.intersects', 2, array2, 'table')
---@return boolean
function Array.intersects(arr1, arr2)
checkType('Module:Array.intersects', 1, arr1, 'table')
checkType('Module:Array.intersects', 2, arr2, 'table')
local small = {}
local small = {}
local large
local large
if len(arr1) <= len(arr2) then
if #array1 <= #array2 then
Array.each(arr1, function(item) small[item] = true end)
arr.each(array1, function(item) small[item] = true end)
large = arr2
large = array2
else
else
Array.each(arr2, function(item) small[item] = true end)
arr.each(array2, function(item) small[item] = true end)
large = arr1
large = array1
end
end
return Array.any(large, function(item) return small[item] end)
return arr.any(large, function(item) return small[item] end)
end
end


---Inserts values into `arr`.
function arr.insert(array, val, index, unpackVal)
---@generic T: any[]
checkType('Module:Array.insert', 1, array, 'table')
---@param arr T
checkType('Module:Array.insert', 3, index, 'number', true)
---@param val any # If `val` is an array and `unpackVal` is **true** then the individual elements of `val` are inserted.
---@param index? integer # Location to start the insertion. Default is at the end of `arr`.
---@param unpackVal? boolean # Default is **false**.
---@return T
---@overload fun(arr: T, val: any, unpackVal: boolean): T
function Array.insert(arr, val, index, unpackVal)
checkType('Module:Array.insert', 1, arr, 'table')
checkTypeMulti('Module:Array.insert', 3, index, {'number', 'boolean', 'nil'})
checkType('Module:Array.insert', 4, unpackVal, 'boolean', true)
checkType('Module:Array.insert', 4, unpackVal, 'boolean', true)
if type(index) == 'boolean'  then
local len = #array
unpackVal, index = index, nil
index = index or (len + 1)
end
local l = len(arr)
index = index or (l + 1)
local mt = getmetatable(arr)
setmetatable(arr, nil)


if unpackVal and type(val) == 'table' then
if type(val) == 'table' and unpackVal ~= false then
local l2 = len(val)
local len2 = #val
for i = 0, l - index do
for i = 0, len - index do
arr[l + l2 - i] = arr[l - i]
array[len + len2 - i] = array[len - i]
end
end
for i = 0, l2 - 1 do
for i = 0, len2 - 1 do
arr[index + i] = val[i + 1]
array[index + i] = val[i + 1]
end
end
else
else
table.insert(arr, index, val)
table.insert(array, index, val)
end
end


return setmetatable(arr, mt)
return array
end
 
---Returns the last element of `arr`.
---@param arr any[]
---@param offset? integer
---@return any
function Array.last(arr, offset)
checkType('Module:Array.last', 1, arr, 'table')
checkType('Module:Array.last', 2, offset, 'number', true)
return arr[len(arr) + offset]
end
end


---Returns a new table were each element of `arr` is modified by `fn`.
function arr.map(array, fn)
---@generic T: any[]
checkType('Module:Array.map', 1, array, 'table')
---@param arr T
---@param fn fun(elem: any, i?: integer): any # First argument is the current element, the second argument is the index of the current element.
---@return T
function Array.map(arr, fn)
checkType('Module:Array.map', 1, arr, 'table')
checkType('Module:Array.map', 2, fn, 'function')
checkType('Module:Array.map', 2, fn, 'function')
local l = 0
local len = 0
local r = {}
local r = setmetatable({}, getmetatable(array))
for i = 1, len(arr) do
local i = 1
local tmp = fn(arr[i], i)
while array[i] ~= nil do
local tmp = fn(array[i], i)
if tmp ~= nil then
if tmp ~= nil then
l = l + 1
len = len + 1
r[l] = tmp
r[len] = tmp
end
end
i = i + 1
end
end
return setmetatable(r, getmetatable(arr))
return r
end
end


---Find the element for which `fn` returned the largest value.
function arr.max_by(array, fn)
---@param arr any[]
checkType('Module:Array.max_by', 1, array, 'table')
---@param fn fun(elem: any): any # The returned value needs to be comparable using the `<` operator.
---@return any elem # The element with the largest `fn` value.
---@return integer i # The index of this element.
function Array.max_by(arr, fn)
checkType('Module:Array.max_by', 1, arr, 'table')
checkType('Module:Array.max_by', 2, fn, 'function')
checkType('Module:Array.max_by', 2, fn, 'function')
return unpack(Array.reduce(arr, function(new, old, i)
return unpack(arr.reduce(array, function(new, old, i)
local y = fn(new)
local y = fn(new)
return y > old[2] and {new, y, i} or old
return y > old[2] and {new, y, i} or old
Line 586: Line 394:
end
end


---Find the largest value in the array.
function arr.max(array)
---@param arr any[] # The values need to be comparable using the `<` operator.
checkType('Module:Array.max', 1, array, 'table')
---@return any elem
local val, _, i = arr.max_by(array, function(x) return x end)
---@return integer i # The index of the largest value.
function Array.max(arr)
checkType('Module:Array.max', 1, arr, 'table')
local val, _, i = Array.max_by(arr, function(x) return x end)
return val, i
return val, i
end
end


---Find the smallest value in the array.
function arr.min(array)
---@param arr any[] # The values need to be comparable using the `<` operator.
checkType('Module:Array.min', 1, array, 'table')
---@return any elem
local val, _, i = arr.max_by(array, function(x) return -x end)
---@return integer i # The index of the smallest value.
function Array.min(arr)
checkType('Module:Array.min', 1, arr, 'table')
local val, _, i = Array.max_by(arr, function(x) return -x end)
return val, i
return val, i
end
end


---Turn the input table into an Array. This makes it possible to use the colon `:` operator to access the Array methods.
function arr.new(array)
---
array = array or {}
---It also enables the use of math operators with the array.
for _, v in pairs(array) do
---```
---local x = arr.new{ 1, 2, 3 }
---local y = arr{ 4, 5, 6 } -- Alternative notation
---
---print( -x ) --> { -1, -2, -3 }
---print( x + 2 ) --> { 3, 4, 5 }
---print( x - 2 ) --> { -1, 0, 1 }
---print( x * 2 ) --> { 2, 4, 6 }
---print( x / 2 ) --> { 0.5, 1, 1.5 }
---print( x ^ 2 ) --> { 1, 4, 9 }
---
---print( x + y ) --> { 5, 7, 9 }
---print( x .. y ) --> { 1, 2, 3, 4, 5, 6 }
---print( (x .. y):reject{3, 4, 5} ) --> { 1, 2, 6 }
---print( x:sum() ) --> 6
---
---print( x:update( {1, 3}, y:get{2, 3} * 2 ) ) --> { 10, 2, 12 }
---```
---@param arr? any[]
---@return Array
function Array.new(arr)
local obj = arr or {}
for _, v in pairs(obj) do
if type(v) == 'table' then
if type(v) == 'table' then
Array.new(v)
arr.new(v)
end
end
end
end


if getmetatable(obj) == nil then
if getmetatable(array) == nil then
setmetatable(obj, Array)
setmetatable(array, arr)
end
end


return obj
return array
end
end


---Creates an object that returns a value that is `step` higher than the previous value each time it gets called.
function arr.range(start, stop, step)
---
---The stored value can be read without incrementing by reading the `val` field.
---
---A new stored value can be set through the `val` field.
---
---A new step size can be set through the `step` field.
---```
---local inc = arr.newIncrementor(10, 5)
---print( inc() ) --> 10
---print( inc() ) --> 15
---print( inc.val ) --> 15
---inc.val = 100
---inc.step = 20
---print( inc.val ) --> 100
---print( inc() ) --> 120
---```
---@param start? number # Default is 1.
---@param step? number # Default is 1.
---@return Incrementor
function Array.newIncrementor(start, step)
checkType('Module:Array.newIncrementor', 1, start, 'number', true)
checkType('Module:Array.newIncrementor', 2, step, 'number', true)
step = step or 1
local n = (start or 1) - step
---@class Incrementor
local obj = {}
return setmetatable(obj, {
__call = function() n = n + step return n end,
__tostring = function() return tostring(n) end,
__index = function() return n end,
__newindex = function(self, k, v)
if k == 'step' and type(v) == 'number' then
step = v
elseif type(v) == 'number' then
n = v
end
end,
__concat = function(x, y) return tostring(x) .. tostring(y) end
})
end
 
---Returns a range of numbers.
---@param start number # Start value inclusive.
---@param stop number # Stop value inclusive for integers, exclusive for floats.
---@param step? number # Default is 1.
---@return Array
---@overload fun(stop: number): Array
function Array.range(start, stop, step)
checkType('Module:Array.range', 1, start, 'number')
checkType('Module:Array.range', 1, start, 'number')
checkType('Module:Array.range', 2, stop, 'number', true)
checkType('Module:Array.range', 2, stop, 'number', true)
checkType('Module:Array.range', 3, step, 'number', true)
checkType('Module:Array.range', 3, step, 'number', true)
local arr = {}
local array = setmetatable({}, arr)
local len = 0
local len = 0
if not stop then
if not stop then
Line 704: Line 433:
for i = start, stop, step or 1 do
for i = start, stop, step or 1 do
len = len + 1
len = len + 1
arr[len] = i
array[len] = i
end
end
return setmetatable(arr, Array)
return array
end
end


---Condenses the array into a single value.
function arr.reduce(array, fn, accumulator)
---
checkType('Module:Array.reduce', 1, array, 'table')
---For each element `fn` is called with the current element, the current accumulator, and the current element index. The returned value of `fn` becomes the accumulator for the next element.
---
---If no `accumulator` value is given at the start then the first element off `arr` becomes the accumulator and the iteration starts from the second element.
---```
---local t = { 1, 2, 3, 4 }
---local sum = arr.reduce( t, function(elem, acc) return acc + elem end ) -- sum == 10
---```
---@param arr any[]
---@param fn fun(elem: any, acc: any, i?: integer): any # The result of this function becomes the `acc` for the next element.
---@param accumulator? any
---@return any # This is the last accumulator value.
function Array.reduce(arr, fn, accumulator)
checkType('Module:Array.reduce', 1, arr, 'table')
checkType('Module:Array.reduce', 2, fn, 'function')
checkType('Module:Array.reduce', 2, fn, 'function')
local acc = accumulator
local acc = accumulator
local start = 1
local i = 1
if acc == nil then
if acc == nil then
acc = arr[1]
acc = array[1]
start = 2
i = 2
end
end
for i = start, len(arr) do
while array[i] ~= nil do
acc = fn(arr[i], acc, i)
acc = fn(array[i], acc, i)
i = i + 1
end
end
return acc
return acc
end
end


---Make a copy off `arr` with certain values removed.
function arr.reject(array, fn)
---
checkType('Module:Array.reject', 1, array, 'table')
---Behaviour for different values of `val`:
checkTypeMulti('Module:Array.reject', 2, fn, {'function', 'table', 'number', 'boolean'})
---* `boolean` | `number` - Remove values equal to this.
if fn == nil then fn = function(item) return item end end
---* `table` - Remove all values in this table.
if type(fn) ~= 'function' and type(fn) ~= 'table' then
---* `fun(elem: any, i?: integer): boolean` - Remove elements for which the functions returns **true**.
fn = {fn}
---@generic T: any[]
---@param arr T
---@param val table|function|number|boolean
---@return T
function Array.reject(arr, val)
checkType('Module:Array.reject', 1, arr, 'table')
checkTypeMulti('Module:Array.reject', 2, val, {'function', 'table', 'number', 'boolean'})
if type(val) ~= 'function' and type(val) ~= 'table' then
val = {val}
end
end
local r = {}
local r = setmetatable({}, getmetatable(array))
local l = 0
local len = 0
if type(val) == 'function' then
if type(fn) == 'function' then
for i = 1, len(arr) do
local i = 1
if not val(arr[i], i) then
while array[i] ~= nil do
l = l + 1
if not fn(array[i], i) then
r[l] = arr[i]
len = len + 1
r[len] = array[i]
end
end
i = i + 1
end
end
else
else
local rejectMap = {}
local rejectMap = {}
Array.each(val --[[@as any[] ]], function(item) rejectMap[item] = true end)
arr.each(fn, function(item) rejectMap[item] = true end)
for i = 1, len(arr) do
local i = 1
if not rejectMap[arr[i]] then
while array[i] ~= nil do
l = l + 1
if not rejectMap[array[i]] then
r[l] = arr[i]
len = len + 1
r[len] = array[i]
end
end
i = i + 1
end
end
end
end
return setmetatable(r, getmetatable(arr))
return r
end
end


---Returns an Array with `val` repeated `n` times.
function arr.rep(val, n)
---@param val any
---@param n integer
---@return Array
function Array.rep(val, n)
checkType('Module:Array.rep', 2, n, 'number')
checkType('Module:Array.rep', 2, n, 'number')
local r = {}
local r = setmetatable({}, arr)
for i = 1, n do
for i = 1, n do
r[i] = val
r[i] = val
end
end
return setmetatable(r, Array)
return r
end
end


---Condenses the array into a single value while saving every accumulator value.
function arr.scan(array, fn, accumulator)
---
checkType('Module:Array.scan', 1, array, 'table')
---For each element `fn` is called with the current element, the current accumulator, and the current element index. The returned value of `fn` becomes the accumulator for the next element.
---
---If no `accumulator` value is given at the start then the first element off `arr` becomes the accumulator and the iteration starts from the second element.
---```
---local t = { 1, 2, 3, 4 }
---local x = arr.scan( t, function(elem, acc) return acc + elem end ) -- x = { 1, 3, 6, 10 }
---```
---@generic T: any[]
---@param arr T
---@param fn fun(elem: any, acc: any, i?: integer): any # Returned value becomes the accumulator for the next element.
---@param accumulator? any
---@return T
function Array.scan(arr, fn, accumulator)
checkType('Module:Array.scan', 1, arr, 'table')
checkType('Module:Array.scan', 2, fn, 'function')
checkType('Module:Array.scan', 2, fn, 'function')
local acc = accumulator
local acc = accumulator
local r = {}
local r = setmetatable({}, getmetatable(array))
for i = 1, len(arr) do
local i = 1
while array[i] ~= nil do
if i == 1 and not accumulator then
if i == 1 and not accumulator then
acc = arr[i]
acc = array[i]
else
else
acc = fn(arr[i], acc, i)
acc = fn(array[i], acc)
end
end
r[i] = acc
r[i] = acc
i = i + 1
end
end
return setmetatable(r, getmetatable(arr))
return r
end
 
---Update a range of index with a range of values.
---
---If if only one value is given but multiple indexes than that value is set for all those indexes.
---
---If `values` is a table then it must of the same length as `indexes`.
---@generic T: any[]
---@param arr T
---@param indexes integer|integer[]
---@param values any|any[]
---@return T
function Array.set(arr, indexes, values)
checkType('Module:Array.set', 1, arr, 'table')
checkTypeMulti('Module:Array.set', 2, indexes, {'table', 'number'})
local mt = getmetatable(arr)
setmetatable(arr, nil)
if type(indexes) == 'number' then
indexes = {indexes}
end
if type(values) == 'table' then
assert(len(indexes) == len(values), string.format("Module:Array.set: 'indexes' and 'values' arrays are not equal length (#indexes = %d, #values = %d)", len(indexes), len(values)))
for i = 1, len(indexes) do
arr[indexes[i]] = values[i]
end
else
for i = 1, len(indexes) do
arr[indexes[i]] = values
end
end
return setmetatable(arr, mt)
end
end


---Extract a subtable from `arr`.
function arr.slice(array, start, finish)
---@generic T: any[]
checkType('Module:Array.slice', 1, array, 'table')
---@param arr T
---@param start integer # Start index. Use negative values to count form the end of the array.
---@param stop integer # Stop index. Use negative values to count form the end of the array.
---@return T
---@overload fun(arr: T, stop: integer): T
function Array.slice(arr, start, stop)
checkType('Module:Array.slice', 1, arr, 'table')
checkType('Module:Array.slice', 2, start, 'number', true)
checkType('Module:Array.slice', 2, start, 'number', true)
checkType('Module:Array.slice', 3, stop, 'number', true)
checkType('Module:Array.slice', 3, finish, 'number', true)
start = start or len(arr)
start = start or 1
if start < 0 then
finish = finish or #array
start = len(arr) + start
if start < 0 and finish == nil then
end
finish = #array + start
if stop == nil then
stop = start
start = 1
start = 1
elseif start < 0 then
start = #array + start
end
end
if stop < 0 then
if finish < 0 then
stop = len(arr) + stop
finish = #array + finish
end
end
local r = {}
local r = setmetatable({}, getmetatable(array))
local len = 0
local len = 0
for i = start, stop do
for i = start, finish do
len = len + 1
len = len + 1
r[len] = arr[i]
r[len] = array[i]
end
end
return setmetatable(r, getmetatable(arr))
return r
end
end


---Split `arr` into two arrays.
function arr.split(array, count)
---@generic T: any[]
checkType('Module:Array.split', 1, array, 'table')
---@param arr T
checkType('Module:Array.split', 2, count, 'number')
---@param index integer # Index to split on.
local x = setmetatable({}, getmetatable(array))
---@return T x # [1, index]
local y = setmetatable({}, getmetatable(array))
---@return T y # [index + 1, #arr]
for i = 1, #array do
function Array.split(arr, index)
table.insert(i <= count and x or y, array[i])
checkType('Module:Array.split', 1, arr, 'table')
checkType('Module:Array.split', 2, index, 'number')
local x = {}
local y = {}
for i = 1, len(arr) do
table.insert(i <= index and x or y, arr[i])
end
end
return setmetatable(x, getmetatable(arr)), setmetatable(y, getmetatable(arr))
return x, y
end
end


---Returns the sum of all elements of `arr`.
function arr.sum(array)
---@param arr number[]
checkType('Module:Array.sum', 1, array, 'table')
---@return number
function Array.sum(arr)
checkType('Module:Array.sum', 1, arr, 'table')
local res = 0
local res = 0
for i = 1, len(arr) do
for i = 1, #array do
res = res + arr[i]
res = res + array[i]
end
end
return res
return res
end
end


---Extract a subtable from `arr`.
function arr.take(array, count, offset)
---@generic T: any[]
checkType('Module:Array.take', 1, array, 'table')
---@param arr T
---@param count integer # Length of the subtable.
---@param start? integer # Start index. Default is 1.
---@return T
function Array.take(arr, count, start)
checkType('Module:Array.take', 1, arr, 'table')
checkType('Module:Array.take', 2, count, 'number')
checkType('Module:Array.take', 2, count, 'number')
checkType('Module:Array.take', 3, start, 'number', true)
checkType('Module:Array.take', 3, offset, 'number', true)
local x = {}
local x = setmetatable({}, getmetatable(array))
start = start or 1
for i = offset or 1, #array do
for i = start, math.min(len(arr), count + start - 1) do
if i <= count then
table.insert(x, arr[i])
table.insert(x, array[i])
end
end
end
return setmetatable(x, getmetatable(arr))
return x
end
end


---Extract a subtable from `arr`.
function arr.take_every(array, n, offset)
---```
checkType('Module:Array.take_every', 1, array, 'table')
---local t = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
---local x = arr.take_every( t, 2 )      --> x = { 1, 3, 5, 7, 9 }
---local x = arr.take_every( t, 2, 3 )    --> x = { 3, 5, 7, 9 }
---local x = arr.take_every( t, 2, 3, 2 ) --> x = { 3, 5 }
--- ```
---@generic T: any[]
---@param arr T
---@param n integer # Step size.
---@param start? integer # Start index.
---@param count? integer # Max amount of elements to get.
---@return T
function Array.take_every(arr, n, start, count)
checkType('Module:Array.take_every', 1, arr, 'table')
checkType('Module:Array.take_every', 2, n, 'number')
checkType('Module:Array.take_every', 2, n, 'number')
checkType('Module:Array.take_every', 3, start, 'number', true)
checkType('Module:Array.take_every', 3, offset, 'number', true)
checkType('Module:Array.take_every', 4, count, 'number', true)
local r = setmetatable({}, getmetatable(array))
count = count or len(arr)
local len = 0
start = start or 1
local i = offset or 1
local stop = math.min(len(arr), start + n * (count - 1))
while array[i] ~= nil do
local r = {}
len = len + 1
local l = 0
r[len] = array[i]
for i = start, stop, n do
i = i + n
l = l + 1
r[l] = arr[i]
end
end
return setmetatable(r, getmetatable(arr))
return r
end
end


---Return a new table with all duplicates removed.
function arr.unique(array, fn)
---@generic T: any[]
checkType('Module:Array.unique', 1, array, 'table')
---@param arr T
---@param fn? fun(elem: any): any # Function to generate an id for each element. The result will then contain elements that generated unique ids.
---@return T
function Array.unique(arr, fn)
checkType('Module:Array.unique', 1, arr, 'table')
checkType('Module:Array.unique', 2, fn, 'function', true)
checkType('Module:Array.unique', 2, fn, 'function', true)
fn = fn or function(item) return item end
fn = fn or function(item) return item end
local r = {}
local r = setmetatable({}, getmetatable(array))
local l = 0
local len = 0
local hash = {}
local hash = {}
for i = 1, len(arr) do
local i = 1
local id = fn(arr[i])
while array[i] ~= nil do
local id = fn(array[i])
if not hash[id] then
if not hash[id] then
l = l + 1
len = len + 1
r[l] = arr[i]
r[len] = array[i]
hash[id] = true
hash[id] = true
end
end
i = i + 1
end
end
return setmetatable(r, getmetatable(arr))
return r
end
end


---Combine elements with the same index from multiple arrays.
function arr.update(array, indexes, values)
---```
checkType('Module:Array.update', 1, array, 'table')
---local x = {1, 2, 3}
checkTypeMulti('Module:Array.update', 2, indexes, {'table', 'number'})
---local y = {4, 5, 6, 7}
if type(indexes) == 'number' then
---local z = arr.zip( x, y ) --> z = { { 1, 4 }, { 2, 5 }, { 3, 6 }, { 7 } }
indexes = {indexes}
---```
---@param ... any[]
---@return Array
function Array.zip(...)
local arrs = { ... }
checkType('Module:Array.zip', 1, arrs[1], 'table')
local r = {}
local _, longest = Array.max_by(arrs, function(arr) return len(arr) end)
for i = 1, longest do
local q = {}
for j = 1, len(arrs) do
table.insert(q, arrs[j][i])
end
table.insert(r, setmetatable(q, Array))
end
end
return setmetatable(r, Array)
if type(values) == 'table' then
end
assert(#indexes == #values, 'Values array must be of equal length as index array')
 
for i = 1, #indexes do
-- Range indexing has a performance impact so this is placed in a separate subclass
array[indexes[i]] = values[i]
Array.RI_mt = {}
for k, v in pairs(Array) do
Array.RI_mt[k] = v
end
 
function Array.RI_mt.__index(t, k)
if type(k) == 'table' then
local res = {}
for i = 1, len(k) do
res[i] = t[k[i]]
end
end
return setmetatable(res, Array)
else
else
return Array[k]
for i = 1, #indexes do
end
array[indexes[i]] = values
end
 
function Array.RI_mt.__newindex(t, k, v)
if type(k) == 'table' then
if type(v) == 'table' then
for i = 1, len(k) do
t[k[i]] = v[i]
end
else
for i = 1, len(k) do
t[k[i]] = v
end
end
end
else
rawset(t, k, v)
end
end
return array
end
end


---Enable range indexing on the input array.
function arr.zip(...)
---
local arrays = { ... }
---This has a performance impact on reads and writes to the table.
checkType('Module:Array.zip', 1, arrays[1], 'table')
---```
local r = setmetatable({}, getmetatable(arrays[1]))
---local t = arr{10, 11, 12, 13, 14, 15}:ri()
local _, longest = arr.max_by(arrays, function(array) return #array end)
---print( t[{2, 3}] ) --> { 11, 12 }
for i = 1, longest do
---```
local q = {}
---@param arr any[]
for j = 1, #arrays do
---@param recursive? boolean # Default is false.
table.insert(q, arrays[j][i])
---@return Array
function Array.ri(arr, recursive)
checkType('Module:Array.ri', 1, arr, 'table')
checkType('Module:Array.ri', 2, recursive, 'boolean', true)
arr = arr or {}
if recursive then
for _, v in pairs(arr) do
if type(v) == 'table' then
Array.ri(v, true)
end
end
end
table.insert(r, q)
end
end
 
return r
if getmetatable(arr) == nil or getmetatable(arr) == Array then
setmetatable(arr, Array.RI_mt)
end
 
return arr
end
 
---Globally enable range indexing on all Array objects by default.
---@param set boolean
function Array.allwaysAllowRangeIndexing(set)
checkType('Module:Array.allwaysAllowRangeIndexing', 1, set, 'boolean')
if set then
Array.__index = Array.RI_mt.__index
Array.__newindex = Array.RI_mt.__newindex
else
Array.__index = Array
Array.__newindex = nil
end
end
end


return Array
return arr
-- </nowiki>
Please note that all contributions to The Deadlock Wiki are considered to be released under the Creative Commons Attribution-NonCommercial-ShareAlike (see Deadlock:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!
Cancel Editing help (opens in new window)
Preview page with this template

Page included on this page:

Retrieved from "https://deadlock.wiki/Module:Array"