モジュール:TableTools
このモジュールについての説明文ページを モジュール:TableTools/doc に作成できます
1 ------------------------------------------------------------------------------------
2 -- TableTools --
3 -- --
4 -- This module includes a number of functions for dealing with Lua tables. --
5 -- It is a meta-module, meant to be called from other Lua modules, and should not --
6 -- be called directly from #invoke. --
7 ------------------------------------------------------------------------------------
8
9 local libraryUtil = require('libraryUtil')
10
11 local p = {}
12
13 -- Define often-used variables and functions.
14 local floor = math.floor
15 local infinity = math.huge
16 local checkType = libraryUtil.checkType
17 local checkTypeMulti = libraryUtil.checkTypeMulti
18
19 ------------------------------------------------------------------------------------
20 -- isPositiveInteger
21 --
22 -- This function returns true if the given value is a positive integer, and false
23 -- if not. Although it doesn't operate on tables, it is included here as it is
24 -- useful for determining whether a given table key is in the array part or the
25 -- hash part of a table.
26 ------------------------------------------------------------------------------------
27 function p.isPositiveInteger(v)
28 return type(v) == 'number' and v >= 1 and floor(v) == v and v < infinity
29 end
30
31 ------------------------------------------------------------------------------------
32 -- isNan
33 --
34 -- This function returns true if the given number is a NaN value, and false if
35 -- not. Although it doesn't operate on tables, it is included here as it is useful
36 -- for determining whether a value can be a valid table key. Lua will generate an
37 -- error if a NaN is used as a table key.
38 ------------------------------------------------------------------------------------
39 function p.isNan(v)
40 return type(v) == 'number' and v ~= v
41 end
42
43 ------------------------------------------------------------------------------------
44 -- shallowClone
45 --
46 -- This returns a clone of a table. The value returned is a new table, but all
47 -- subtables and functions are shared. Metamethods are respected, but the returned
48 -- table will have no metatable of its own.
49 ------------------------------------------------------------------------------------
50 function p.shallowClone(t)
51 checkType('shallowClone', 1, t, 'table')
52 local ret = {}
53 for k, v in pairs(t) do
54 ret[k] = v
55 end
56 return ret
57 end
58
59 ------------------------------------------------------------------------------------
60 -- removeDuplicates
61 --
62 -- This removes duplicate values from an array. Non-positive-integer keys are
63 -- ignored. The earliest value is kept, and all subsequent duplicate values are
64 -- removed, but otherwise the array order is unchanged.
65 ------------------------------------------------------------------------------------
66 function p.removeDuplicates(arr)
67 checkType('removeDuplicates', 1, arr, 'table')
68 local isNan = p.isNan
69 local ret, exists = {}, {}
70 for _, v in ipairs(arr) do
71 if isNan(v) then
72 -- NaNs can't be table keys, and they are also unique, so we don't need to check existence.
73 ret[#ret + 1] = v
74 elseif not exists[v] then
75 ret[#ret + 1] = v
76 exists[v] = true
77 end
78 end
79 return ret
80 end
81
82 ------------------------------------------------------------------------------------
83 -- numKeys
84 --
85 -- This takes a table and returns an array containing the numbers of any numerical
86 -- keys that have non-nil values, sorted in numerical order.
87 ------------------------------------------------------------------------------------
88 function p.numKeys(t)
89 checkType('numKeys', 1, t, 'table')
90 local isPositiveInteger = p.isPositiveInteger
91 local nums = {}
92 for k in pairs(t) do
93 if isPositiveInteger(k) then
94 nums[#nums + 1] = k
95 end
96 end
97 table.sort(nums)
98 return nums
99 end
100
101 ------------------------------------------------------------------------------------
102 -- affixNums
103 --
104 -- This takes a table and returns an array containing the numbers of keys with the
105 -- specified prefix and suffix. For example, for the table
106 -- {a1 = 'foo', a3 = 'bar', a6 = 'baz'} and the prefix "a", affixNums will return
107 -- {1, 3, 6}.
108 ------------------------------------------------------------------------------------
109 function p.affixNums(t, prefix, suffix)
110 checkType('affixNums', 1, t, 'table')
111 checkType('affixNums', 2, prefix, 'string', true)
112 checkType('affixNums', 3, suffix, 'string', true)
113
114 local function cleanPattern(s)
115 -- Cleans a pattern so that the magic characters ()%.[]*+-?^$ are interpreted literally.
116 return s:gsub('([%(%)%%%.%[%]%*%+%-%?%^%$])', '%%%1')
117 end
118
119 prefix = prefix or ''
120 suffix = suffix or ''
121 prefix = cleanPattern(prefix)
122 suffix = cleanPattern(suffix)
123 local pattern = '^' .. prefix .. '([1-9]%d*)' .. suffix .. '$'
124
125 local nums = {}
126 for k in pairs(t) do
127 if type(k) == 'string' then
128 local num = mw.ustring.match(k, pattern)
129 if num then
130 nums[#nums + 1] = tonumber(num)
131 end
132 end
133 end
134 table.sort(nums)
135 return nums
136 end
137
138 ------------------------------------------------------------------------------------
139 -- numData
140 --
141 -- Given a table with keys like {"foo1", "bar1", "foo2", "baz2"}, returns a table
142 -- of subtables in the format
143 -- {[1] = {foo = 'text', bar = 'text'}, [2] = {foo = 'text', baz = 'text'}}.
144 -- Keys that don't end with an integer are stored in a subtable named "other". The
145 -- compress option compresses the table so that it can be iterated over with
146 -- ipairs.
147 ------------------------------------------------------------------------------------
148 function p.numData(t, compress)
149 checkType('numData', 1, t, 'table')
150 checkType('numData', 2, compress, 'boolean', true)
151 local ret = {}
152 for k, v in pairs(t) do
153 local prefix, num = mw.ustring.match(tostring(k), '^([^0-9]*)([1-9][0-9]*)$')
154 if num then
155 num = tonumber(num)
156 local subtable = ret[num] or {}
157 if prefix == '' then
158 -- Positional parameters match the blank string; put them at the start of the subtable instead.
159 prefix = 1
160 end
161 subtable[prefix] = v
162 ret[num] = subtable
163 else
164 local subtable = ret.other or {}
165 subtable[k] = v
166 ret.other = subtable
167 end
168 end
169 if compress then
170 local other = ret.other
171 ret = p.compressSparseArray(ret)
172 ret.other = other
173 end
174 return ret
175 end
176
177 ------------------------------------------------------------------------------------
178 -- compressSparseArray
179 --
180 -- This takes an array with one or more nil values, and removes the nil values
181 -- while preserving the order, so that the array can be safely traversed with
182 -- ipairs.
183 ------------------------------------------------------------------------------------
184 function p.compressSparseArray(t)
185 checkType('compressSparseArray', 1, t, 'table')
186 local ret = {}
187 local nums = p.numKeys(t)
188 for _, num in ipairs(nums) do
189 ret[#ret + 1] = t[num]
190 end
191 return ret
192 end
193
194 ------------------------------------------------------------------------------------
195 -- sparseIpairs
196 --
197 -- This is an iterator for sparse arrays. It can be used like ipairs, but can
198 -- handle nil values.
199 ------------------------------------------------------------------------------------
200 function p.sparseIpairs(t)
201 checkType('sparseIpairs', 1, t, 'table')
202 local nums = p.numKeys(t)
203 local i = 0
204 local lim = #nums
205 return function ()
206 i = i + 1
207 if i <= lim then
208 local key = nums[i]
209 return key, t[key]
210 else
211 return nil, nil
212 end
213 end
214 end
215
216 ------------------------------------------------------------------------------------
217 -- size
218 --
219 -- This returns the size of a key/value pair table. It will also work on arrays,
220 -- but for arrays it is more efficient to use the # operator.
221 ------------------------------------------------------------------------------------
222 function p.size(t)
223 checkType('size', 1, t, 'table')
224 local i = 0
225 for _ in pairs(t) do
226 i = i + 1
227 end
228 return i
229 end
230
231 local function defaultKeySort(item1, item2)
232 -- "number" < "string", so numbers will be sorted before strings.
233 local type1, type2 = type(item1), type(item2)
234 if type1 ~= type2 then
235 return type1 < type2
236 elseif type1 == 'table' or type1 == 'boolean' or type1 == 'function' then
237 return tostring(item1) < tostring(item2)
238 else
239 return item1 < item2
240 end
241 end
242 ------------------------------------------------------------------------------------
243 -- keysToList
244 --
245 -- Returns an array of the keys in a table, sorted using either a default
246 -- comparison function or a custom keySort function.
247 ------------------------------------------------------------------------------------
248 function p.keysToList(t, keySort, checked)
249 if not checked then
250 checkType('keysToList', 1, t, 'table')
251 checkTypeMulti('keysToList', 2, keySort, {'function', 'boolean', 'nil'})
252 end
253
254 local arr = {}
255 local index = 1
256 for k in pairs(t) do
257 arr[index] = k
258 index = index + 1
259 end
260
261 if keySort ~= false then
262 keySort = type(keySort) == 'function' and keySort or defaultKeySort
263 table.sort(arr, keySort)
264 end
265
266 return arr
267 end
268
269 ------------------------------------------------------------------------------------
270 -- sortedPairs
271 --
272 -- Iterates through a table, with the keys sorted using the keysToList function.
273 -- If there are only numerical keys, sparseIpairs is probably more efficient.
274 ------------------------------------------------------------------------------------
275 function p.sortedPairs(t, keySort)
276 checkType('sortedPairs', 1, t, 'table')
277 checkType('sortedPairs', 2, keySort, 'function', true)
278
279 local arr = p.keysToList(t, keySort, true)
280
281 local i = 0
282 return function ()
283 i = i + 1
284 local key = arr[i]
285 if key ~= nil then
286 return key, t[key]
287 else
288 return nil, nil
289 end
290 end
291 end
292
293 ------------------------------------------------------------------------------------
294 -- isArray
295 --
296 -- Returns true if the given value is a table and all keys are consecutive
297 -- integers starting at 1.
298 ------------------------------------------------------------------------------------
299 function p.isArray(v)
300 if type(v) ~= 'table' then
301 return false
302 end
303 local i = 0
304 for _ in pairs(v) do
305 i = i + 1
306 if v[i] == nil then
307 return false
308 end
309 end
310 return true
311 end
312
313 ------------------------------------------------------------------------------------
314 -- isArrayLike
315 --
316 -- Returns true if the given value is iterable and all keys are consecutive
317 -- integers starting at 1.
318 ------------------------------------------------------------------------------------
319 function p.isArrayLike(v)
320 if not pcall(pairs, v) then
321 return false
322 end
323 local i = 0
324 for _ in pairs(v) do
325 i = i + 1
326 if v[i] == nil then
327 return false
328 end
329 end
330 return true
331 end
332
333 ------------------------------------------------------------------------------------
334 -- invert
335 --
336 -- Transposes the keys and values in an array. For example, {"a", "b", "c"} ->
337 -- {a = 1, b = 2, c = 3}. Duplicates are not supported (result values refer to
338 -- the index of the last duplicate) and NaN values are ignored.
339 ------------------------------------------------------------------------------------
340 function p.invert(arr)
341 checkType("invert", 1, arr, "table")
342 local isNan = p.isNan
343 local map = {}
344 for i, v in ipairs(arr) do
345 if not isNan(v) then
346 map[v] = i
347 end
348 end
349
350 return map
351 end
352
353 ------------------------------------------------------------------------------------
354 -- listToSet
355 --
356 -- Creates a set from the array part of the table. Indexing the set by any of the
357 -- values of the array returns true. For example, {"a", "b", "c"} ->
358 -- {a = true, b = true, c = true}. NaN values are ignored as Lua considers them
359 -- never equal to any value (including other NaNs or even themselves).
360 ------------------------------------------------------------------------------------
361 function p.listToSet(arr)
362 checkType("listToSet", 1, arr, "table")
363 local isNan = p.isNan
364 local set = {}
365 for _, v in ipairs(arr) do
366 if not isNan(v) then
367 set[v] = true
368 end
369 end
370
371 return set
372 end
373
374 ------------------------------------------------------------------------------------
375 -- deepCopy
376 --
377 -- Recursive deep copy function. Preserves identities of subtables.
378 ------------------------------------------------------------------------------------
379 local function _deepCopy(orig, includeMetatable, already_seen)
380 if type(orig) ~= "table" then
381 return orig
382 end
383
384 -- already_seen stores copies of tables indexed by the original table.
385 local copy = already_seen[orig]
386 if copy ~= nil then
387 return copy
388 end
389
390 copy = {}
391 already_seen[orig] = copy -- memoize before any recursion, to avoid infinite loops
392
393 for orig_key, orig_value in pairs(orig) do
394 copy[_deepCopy(orig_key, includeMetatable, already_seen)] = _deepCopy(orig_value, includeMetatable, already_seen)
395 end
396
397 if includeMetatable then
398 local mt = getmetatable(orig)
399 if mt ~= nil then
400 setmetatable(copy, _deepCopy(mt, true, already_seen))
401 end
402 end
403
404 return copy
405 end
406
407 function p.deepCopy(orig, noMetatable, already_seen)
408 checkType("deepCopy", 3, already_seen, "table", true)
409 return _deepCopy(orig, not noMetatable, already_seen or {})
410 end
411
412 ------------------------------------------------------------------------------------
413 -- sparseConcat
414 --
415 -- Concatenates all values in the table that are indexed by a number, in order.
416 -- sparseConcat{a, nil, c, d} => "acd"
417 -- sparseConcat{nil, b, c, d} => "bcd"
418 ------------------------------------------------------------------------------------
419 function p.sparseConcat(t, sep, i, j)
420 local arr = {}
421
422 local arr_i = 0
423 for _, v in p.sparseIpairs(t) do
424 arr_i = arr_i + 1
425 arr[arr_i] = v
426 end
427
428 return table.concat(arr, sep, i, j)
429 end
430
431 ------------------------------------------------------------------------------------
432 -- length
433 --
434 -- Finds the length of an array, or of a quasi-array with keys such as "data1",
435 -- "data2", etc., using an exponential search algorithm. It is similar to the
436 -- operator #, but may return a different value when there are gaps in the array
437 -- portion of the table. Intended to be used on data loaded with mw.loadData. For
438 -- other tables, use #.
439 -- Note: #frame.args in frame object always be set to 0, regardless of the number
440 -- of unnamed template parameters, so use this function for frame.args.
441 ------------------------------------------------------------------------------------
442 function p.length(t, prefix)
443 -- requiring module inline so that [[Module:Exponential search]] which is
444 -- only needed by this one function doesn't get millions of transclusions
445 local expSearch = require("Module:Exponential search")
446 checkType('length', 1, t, 'table')
447 checkType('length', 2, prefix, 'string', true)
448 return expSearch(function (i)
449 local key
450 if prefix then
451 key = prefix .. tostring(i)
452 else
453 key = i
454 end
455 return t[key] ~= nil
456 end) or 0
457 end
458
459 ------------------------------------------------------------------------------------
460 -- inArray
461 --
462 -- Returns true if searchElement is a member of the array, and false otherwise.
463 -- Equivalent to JavaScript array.includes(searchElement) or
464 -- array.includes(searchElement, fromIndex), except fromIndex is 1 indexed
465 ------------------------------------------------------------------------------------
466 function p.inArray(array, searchElement, fromIndex)
467 checkType("inArray", 1, array, "table")
468 -- if searchElement is nil, error?
469
470 fromIndex = tonumber(fromIndex)
471 if fromIndex then
472 if (fromIndex < 0) then
473 fromIndex = #array + fromIndex + 1
474 end
475 if fromIndex < 1 then fromIndex = 1 end
476 for _, v in ipairs({unpack(array, fromIndex)}) do
477 if v == searchElement then
478 return true
479 end
480 end
481 else
482 for _, v in pairs(array) do
483 if v == searchElement then
484 return true
485 end
486 end
487 end
488 return false
489 end
490
491 ------------------------------------------------------------------------------------
492 -- merge
493 --
494 -- Given the arrays, returns an array containing the elements of each input array
495 -- in sequence.
496 ------------------------------------------------------------------------------------
497 function p.merge(...)
498 local arrays = {...}
499 local ret = {}
500 for i, arr in ipairs(arrays) do
501 checkType('merge', i, arr, 'table')
502 for _, v in ipairs(arr) do
503 ret[#ret + 1] = v
504 end
505 end
506 return ret
507 end
508
509 ------------------------------------------------------------------------------------
510 -- extend
511 --
512 -- Extends the first array in place by appending all elements from the second
513 -- array.
514 ------------------------------------------------------------------------------------
515 function p.extend(arr1, arr2)
516 checkType('extend', 1, arr1, 'table')
517 checkType('extend', 2, arr2, 'table')
518
519 for _, v in ipairs(arr2) do
520 arr1[#arr1 + 1] = v
521 end
522 end
523
524 return p