Modul:TableTools

------------------------------------------------------------------------------------
--                                   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.                                               --
------------------------------------------------------------------------------------
locallibraryUtil=require('libraryUtil')
localp={}
-- Define often-used variables and functions.
localfloor=math.floor
localinfinity=math.huge
localcheckType=libraryUtil.checkType
localcheckTypeMulti=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.
------------------------------------------------------------------------------------
functionp.isPositiveInteger(v)
returntype(v)=='number'andv>=1andfloor(v)==vandv<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.
------------------------------------------------------------------------------------
functionp.isNan(v)
returntype(v)=='number'andv~=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.
------------------------------------------------------------------------------------
functionp.shallowClone(t)
checkType('shallowClone',1,t,'table')
localret={}
fork,vinpairs(t)do
ret[k]=v
end
returnret
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.
------------------------------------------------------------------------------------
functionp.removeDuplicates(arr)
checkType('removeDuplicates',1,arr,'table')
localisNan=p.isNan
localret,exists={},{}
for_,vinipairs(arr)do
ifisNan(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
elseifnotexists[v]then
ret[#ret+1]=v
exists[v]=true
end
end
returnret
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.
------------------------------------------------------------------------------------
functionp.numKeys(t)
checkType('numKeys',1,t,'table')
localisPositiveInteger=p.isPositiveInteger
localnums={}
forkinpairs(t)do
ifisPositiveInteger(k)then
nums[#nums+1]=k
end
end
table.sort(nums)
returnnums
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}.
------------------------------------------------------------------------------------
functionp.affixNums(t,prefix,suffix)
checkType('affixNums',1,t,'table')
checkType('affixNums',2,prefix,'string',true)
checkType('affixNums',3,suffix,'string',true)
localfunctioncleanPattern(s)
-- Cleans a pattern so that the magic characters ()%.[]*+-?^$ are interpreted literally.
returns:gsub('([%(%)%%%.%[%]%*%+%-%?%^%$])','%%%1')
end
prefix=prefixor''
suffix=suffixor''
prefix=cleanPattern(prefix)
suffix=cleanPattern(suffix)
localpattern='^'..prefix..'([1-9]%d*)'..suffix..'$'
localnums={}
forkinpairs(t)do
iftype(k)=='string'then
localnum=mw.ustring.match(k,pattern)
ifnumthen
nums[#nums+1]=tonumber(num)
end
end
end
table.sort(nums)
returnnums
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.
------------------------------------------------------------------------------------
functionp.numData(t,compress)
checkType('numData',1,t,'table')
checkType('numData',2,compress,'boolean',true)
localret={}
fork,vinpairs(t)do
localprefix,num=mw.ustring.match(tostring(k),'^([^0-9]*)([1-9][0-9]*)$')
ifnumthen
num=tonumber(num)
localsubtable=ret[num]or{}
ifprefix==''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
localsubtable=ret.otheror{}
subtable[k]=v
ret.other=subtable
end
end
ifcompressthen
localother=ret.other
ret=p.compressSparseArray(ret)
ret.other=other
end
returnret
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.
------------------------------------------------------------------------------------
functionp.compressSparseArray(t)
checkType('compressSparseArray',1,t,'table')
localret={}
localnums=p.numKeys(t)
for_,numinipairs(nums)do
ret[#ret+1]=t[num]
end
returnret
end
------------------------------------------------------------------------------------
-- sparseIpairs
--
-- This is an iterator for sparse arrays. It can be used like ipairs, but can
-- handle nil values.
------------------------------------------------------------------------------------
functionp.sparseIpairs(t)
checkType('sparseIpairs',1,t,'table')
localnums=p.numKeys(t)
locali=0
locallim=#nums
returnfunction()
i=i+1
ifi<=limthen
localkey=nums[i]
returnkey,t[key]
else
returnnil,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.
------------------------------------------------------------------------------------
functionp.size(t)
checkType('size',1,t,'table')
locali=0
for_inpairs(t)do
i=i+1
end
returni
end
localfunctiondefaultKeySort(item1,item2)
-- "number" < "string", so numbers will be sorted before strings.
localtype1,type2=type(item1),type(item2)
iftype1~=type2then
returntype1<type2
elseiftype1=='table'ortype1=='boolean'ortype1=='function'then
returntostring(item1)<tostring(item2)
else
returnitem1<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.
------------------------------------------------------------------------------------
functionp.keysToList(t,keySort,checked)
ifnotcheckedthen
checkType('keysToList',1,t,'table')
checkTypeMulti('keysToList',2,keySort,{'function','boolean','nil'})
end
localarr={}
localindex=1
forkinpairs(t)do
arr[index]=k
index=index+1
end
ifkeySort~=falsethen
keySort=type(keySort)=='function'andkeySortordefaultKeySort
table.sort(arr,keySort)
end
returnarr
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.
------------------------------------------------------------------------------------
functionp.sortedPairs(t,keySort)
checkType('sortedPairs',1,t,'table')
checkType('sortedPairs',2,keySort,'function',true)
localarr=p.keysToList(t,keySort,true)
locali=0
returnfunction()
i=i+1
localkey=arr[i]
ifkey~=nilthen
returnkey,t[key]
else
returnnil,nil
end
end
end
------------------------------------------------------------------------------------
-- isArray
--
-- Returns true if the given value is a table and all keys are consecutive
-- integers starting at 1.
------------------------------------------------------------------------------------
functionp.isArray(v)
iftype(v)~='table'then
returnfalse
end
locali=0
for_inpairs(v)do
i=i+1
ifv[i]==nilthen
returnfalse
end
end
returntrue
end
------------------------------------------------------------------------------------
-- isArrayLike
--
-- Returns true if the given value is iterable and all keys are consecutive
-- integers starting at 1.
------------------------------------------------------------------------------------
functionp.isArrayLike(v)
ifnotpcall(pairs,v)then
returnfalse
end
locali=0
for_inpairs(v)do
i=i+1
ifv[i]==nilthen
returnfalse
end
end
returntrue
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.
------------------------------------------------------------------------------------
functionp.invert(arr)
checkType("invert",1,arr,"table")
localisNan=p.isNan
localmap={}
fori,vinipairs(arr)do
ifnotisNan(v)then
map[v]=i
end
end
returnmap
end
------------------------------------------------------------------------------------
-- listToSet
--
-- Creates a set from the array part of the table. Indexing the set by any of the
-- values of the array returns true. For example, {"a", "b", "c"} ->
-- {a = true, b = true, c = true}. NaN values are ignored as Lua considers them
-- never equal to any value (including other NaNs or even themselves).
------------------------------------------------------------------------------------
functionp.listToSet(arr)
checkType("listToSet",1,arr,"table")
localisNan=p.isNan
localset={}
for_,vinipairs(arr)do
ifnotisNan(v)then
set[v]=true
end
end
returnset
end
------------------------------------------------------------------------------------
-- deepCopy
--
-- Recursive deep copy function. Preserves identities of subtables.
------------------------------------------------------------------------------------
localfunction_deepCopy(orig,includeMetatable,already_seen)
iftype(orig)~="table"then
returnorig
end
-- already_seen stores copies of tables indexed by the original table.
localcopy=already_seen[orig]
ifcopy~=nilthen
returncopy
end
copy={}
already_seen[orig]=copy-- memoize before any recursion, to avoid infinite loops
fororig_key,orig_valueinpairs(orig)do
copy[_deepCopy(orig_key,includeMetatable,already_seen)]=_deepCopy(orig_value,includeMetatable,already_seen)
end
ifincludeMetatablethen
localmt=getmetatable(orig)
ifmt~=nilthen
setmetatable(copy,_deepCopy(mt,true,already_seen))
end
end
returncopy
end
functionp.deepCopy(orig,noMetatable,already_seen)
checkType("deepCopy",3,already_seen,"table",true)
return_deepCopy(orig,notnoMetatable,already_seenor{})
end
------------------------------------------------------------------------------------
-- sparseConcat
--
-- Concatenates all values in the table that are indexed by a number, in order.
-- sparseConcat{a, nil, c, d}  =>  "acd"
-- sparseConcat{nil, b, c, d}  =>  "bcd"
------------------------------------------------------------------------------------
functionp.sparseConcat(t,sep,i,j)
localarr={}
localarr_i=0
for_,vinp.sparseIpairs(t)do
arr_i=arr_i+1
arr[arr_i]=v
end
returntable.concat(arr,sep,i,j)
end
------------------------------------------------------------------------------------
-- length
--
-- Finds the length of an array, or of a quasi-array with keys such as "data1",
-- "data2", etc., using an exponential search algorithm. It is similar to the
-- operator #, but may return a different value when there are gaps in the array
-- portion of the table. Intended to be used on data loaded with mw.loadData. For
-- other tables, use #.
-- Note: #frame.args in frame object always be set to 0, regardless of  the number
-- of unnamed template parameters, so use this function for frame.args.
------------------------------------------------------------------------------------
functionp.length(t,prefix)
-- requiring module inline so that [[Module:Exponential search]] which is
-- only needed by this one function doesn't get millions of transclusions
localexpSearch=require("Module:Exponential search")
checkType('length',1,t,'table')
checkType('length',2,prefix,'string',true)
returnexpSearch(function(i)
localkey
ifprefixthen
key=prefix..tostring(i)
else
key=i
end
returnt[key]~=nil
end)or0
end
------------------------------------------------------------------------------------
-- inArray
--
-- Returns true if searchElement is a member of the array, and false otherwise.
-- Equivalent to JavaScript array.includes(searchElement) or
-- array.includes(searchElement, fromIndex), except fromIndex is 1 indexed
------------------------------------------------------------------------------------
functionp.inArray(array,searchElement,fromIndex)
checkType("inArray",1,array,"table")
-- if searchElement is nil, error?
fromIndex=tonumber(fromIndex)
iffromIndexthen
if(fromIndex<0)then
fromIndex=#array+fromIndex+1
end
iffromIndex<1thenfromIndex=1end
for_,vinipairs({unpack(array,fromIndex)})do
ifv==searchElementthen
returntrue
end
end
else
for_,vinpairs(array)do
ifv==searchElementthen
returntrue
end
end
end
returnfalse
end
------------------------------------------------------------------------------------
-- merge
--
-- Given the arrays, returns an array containing the elements of each input array
-- in sequence.
------------------------------------------------------------------------------------
functionp.merge(...)
localarrays={...}
localret={}
fori,arrinipairs(arrays)do
checkType('merge',i,arr,'table')
for_,vinipairs(arr)do
ret[#ret+1]=v
end
end
returnret
end
------------------------------------------------------------------------------------
-- extend
--
-- Extends the first array in place by appending all elements from the second
-- array.
------------------------------------------------------------------------------------
functionp.extend(arr1,arr2)
checkType('extend',1,arr1,'table')
checkType('extend',2,arr2,'table')
for_,vinipairs(arr2)do
arr1[#arr1+1]=v
end
end
returnp