--------------------------------------------------------------------------------------                                   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.floorlocalinfinity=math.hugelocalcheckType=libraryUtil.checkTypelocalcheckTypeMulti=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<infinityend-------------------------------------------------------------------------------------- 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~=vend-------------------------------------------------------------------------------------- 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)doret[k]=vendreturnretend-------------------------------------------------------------------------------------- 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.isNanlocalret,exists={},{}for_,vinipairs(arr)doifisNan(v)then-- NaNs can't be table keys, and they are also unique, so we don't need to check existence.ret[#ret+1]=velseifnotexists[v]thenret[#ret+1]=vexists[v]=trueendendendreturnretend-------------------------------------------------------------------------------------- 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.isPositiveIntegerlocalnums={}forkinpairs(t)doifisPositiveInteger(k)thennums[#nums+1]=kendendtable.sort(nums)returnnumsend-------------------------------------------------------------------------------------- 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')endprefix=prefixor''suffix=suffixor''prefix=cleanPattern(prefix)suffix=cleanPattern(suffix)localpattern='^'..prefix..'([1-9]%d*)'..suffix..'$'localnums={}forkinpairs(t)doiftype(k)=='string'thenlocalnum=mw.ustring.match(k,pattern)ifnumthennums[#nums+1]=tonumber(num)endendendtable.sort(nums)returnnumsend-------------------------------------------------------------------------------------- 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)dolocalprefix,num=mw.ustring.match(tostring(k),'^([^0-9]*)([1-9][0-9]*)$')ifnumthennum=tonumber(num)localsubtable=ret[num]or{}ifprefix==''then-- Positional parameters match the blank string; put them at the start of the subtable instead.prefix=1endsubtable[prefix]=vret[num]=subtableelselocalsubtable=ret.otheror{}subtable[k]=vret.other=subtableendendifcompressthenlocalother=ret.otherret=p.compressSparseArray(ret)ret.other=otherendreturnretend-------------------------------------------------------------------------------------- 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)doret[#ret+1]=t[num]endreturnretend-------------------------------------------------------------------------------------- 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=0locallim=#numsreturnfunction()i=i+1ifi<=limthenlocalkey=nums[i]returnkey,t[key]elsereturnnil,nilendendend-------------------------------------------------------------------------------------- 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=0for_inpairs(t)doi=i+1endreturniendlocalfunctiondefaultKeySort(item1,item2)-- "number" < "string", so numbers will be sorted before strings.localtype1,type2=type(item1),type(item2)iftype1~=type2thenreturntype1<type2elseiftype1=='table'ortype1=='boolean'ortype1=='function'thenreturntostring(item1)<tostring(item2)elsereturnitem1<item2endend-------------------------------------------------------------------------------------- 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)ifnotcheckedthencheckType('keysToList',1,t,'table')checkTypeMulti('keysToList',2,keySort,{'function','boolean','nil'})endlocalarr={}localindex=1forkinpairs(t)doarr[index]=kindex=index+1endifkeySort~=falsethenkeySort=type(keySort)=='function'andkeySortordefaultKeySorttable.sort(arr,keySort)endreturnarrend-------------------------------------------------------------------------------------- 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=0returnfunction()i=i+1localkey=arr[i]ifkey~=nilthenreturnkey,t[key]elsereturnnil,nilendendend-------------------------------------------------------------------------------------- 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'thenreturnfalseendlocali=0for_inpairs(v)doi=i+1ifv[i]==nilthenreturnfalseendendreturntrueend-------------------------------------------------------------------------------------- isArrayLike---- Returns true if the given value is iterable and all keys are consecutive-- integers starting at 1.------------------------------------------------------------------------------------functionp.isArrayLike(v)ifnotpcall(pairs,v)thenreturnfalseendlocali=0for_inpairs(v)doi=i+1ifv[i]==nilthenreturnfalseendendreturntrueend-------------------------------------------------------------------------------------- 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.isNanlocalmap={}fori,vinipairs(arr)doifnotisNan(v)thenmap[v]=iendendreturnmapend-------------------------------------------------------------------------------------- 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.isNanlocalset={}for_,vinipairs(arr)doifnotisNan(v)thenset[v]=trueendendreturnsetend-------------------------------------------------------------------------------------- deepCopy---- Recursive deep copy function. Preserves identities of subtables.------------------------------------------------------------------------------------localfunction_deepCopy(orig,includeMetatable,already_seen)-- Stores copies of tables indexed by the original table.already_seen=already_seenor{}localcopy=already_seen[orig]ifcopy~=nilthenreturncopyendiftype(orig)=='table'thencopy={}fororig_key,orig_valueinpairs(orig)docopy[_deepCopy(orig_key,includeMetatable,already_seen)]=_deepCopy(orig_value,includeMetatable,already_seen)endalready_seen[orig]=copyifincludeMetatablethenlocalmt=getmetatable(orig)ifmt~=nilthenlocalmt_copy=_deepCopy(mt,includeMetatable,already_seen)setmetatable(copy,mt_copy)already_seen[mt]=mt_copyendendelse-- number, string, boolean, etccopy=origendreturncopyendfunctionp.deepCopy(orig,noMetatable,already_seen)checkType("deepCopy",3,already_seen,"table",true)return_deepCopy(orig,notnoMetatable,already_seen)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=0for_,vinp.sparseIpairs(t)doarr_i=arr_i+1arr[arr_i]=vendreturntable.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 transclusionslocalexpSearch=require("Module:Exponential search")checkType('length',1,t,'table')checkType('length',2,prefix,'string',true)returnexpSearch(function(i)localkeyifprefixthenkey=prefix..tostring(i)elsekey=iendreturnt[key]~=nilend)or0end-------------------------------------------------------------------------------------- inArray---- Returns true if valueToFind is a member of the array, and false otherwise.------------------------------------------------------------------------------------functionp.inArray(arr,valueToFind)checkType("inArray",1,arr,"table")-- if valueToFind is nil, error?for_,vinipairs(arr)doifv==valueToFindthenreturntrueendendreturnfalseendreturnp