Module: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