Module:ListUtil

From Fire Emblem Heroes Wiki
Jump to: navigation, search
Template-info.svg Documentation

Test cases

Lua metamodule containing higher-order functions for lists.
  • t: A valid Lua sequence; that is, a Lua table that contains values from only t[1] to t[N] for some positive integer N.
    • Examples: {-1, 0, 1}, {}, {3, 'a', false, {b = 0.5}}
  • f: Function which accepts a value from a table as its first argument and the value's corresponding key as its second argument.
    • Examples: function (v) return v + 5 end, function (v, k) return k .. ': ' .. v end
  • pr: Predicate which accepts a value from a table as its first argument and the value's corresponding key as its second argument. Only truthiness of the return value is considered.
    • Examples: function (v) return v > 3 end, function (v, k) return v.mem[k] end
  • op: Function which accepts two table values.
    • Examples: function (x, y) return x < y end, function (x, y) return math.sqrt(x * x + y * y) end

Most functions in this module that accept lists will invoke Lua's built-in # operator to obtain their lengths. This is problematic for list-like objects which have an __index metamethod, such as mw.getCurrentFrame().args, as the __len metamethod does not work for Lua tables in Scribunto's current Lua version (5.1). Functions that work without invoking # are explicitly noted.

Generation[edit source]

  • range (i, j, k)
Returns a list whose entries are the values produced by the Lua for-loop for x = i, j, k. k defaults to 1 if i >= j and -1 otherwise if not given.
  • generate (n, f)
Returns {f(1), f(2), ..., f(n)}.
  • array (x, ...)
Returns a multi-dimensional array with ranks ... and all elements x.

Counting[edit source]

  • any (t, pr)
Returns true if pr is true for any element of t.
  • all (t, pr)
Returns true if pr is true for all elements of t.
  • none (t, pr)
Returns true if pr is true for none of the elements of t.
  • count (t, x)
Returns the number of elements of t that compare equal to x.
  • count_if (t, pr)
Returns the number of elements of t that satisfy pr.

Searching[edit source]

  • find (t, x, b = 1)
Returns the key-value pair of the list's first element that compares equal to x, or nil if none can be found, starting from the b-th element (negative indices count from the end of the table).
  • find_if (t, pr, b = 1)
Returns the key-value pair of the list's first element that satisfies pr, or nil if none can be found, starting from the b-th element (negative indices count from the end of the table).
  • rfind (t, x, e = -1)
Returns the key-value pair of the list's last element that compares equal to x, or nil if none can be found, starting from the e-th element (negative indices count from the end of the table). t may be any list-like object as long as e is positive.
  • rfind_if (t, pr, e = -1)
Returns the key-value pair of the list's last element that satisfies pr, or nil if none can be found, starting from the e-th element (negative indices count from the end of the table). t may be any list-like object as long as e is positive.
  • min (t, op)
Returns the key-value pair of the list's smallest element. op(x, y) should return true if x compares less than y; if not given, it defaults to Lua's less-than operator.
  • max (t, op)
Returns the key-value pair of the list's largest element. op(x, y) should return true if x compares less than y; if not given, it defaults to Lua's less-than operator.
  • minmax (t, op)
Returns the list's smallest and largest values. Keys of the values are not returned. op(x, y) should return true if x compares less than y; if not given, it defaults to Lua's less-than operator.

Comparison[edit source]

  • equal (t1, t2)
Returns true if the two lists have equal sizes and their elements compare equal to each other.
  • compare (t1, t2)
Returns the lexicographic order between the two lists: -1 if t1 < t2, 1 if t1 > t2, 0 if the two lists compare equal. Element-wise comparison is done using Lua's less-than operator.
  • equality_mixin ()
Returns a metatable where the __eq metamethod wraps equal, such that lists using this metatable can be compared with each other for equality.
  • ordering_mixin ()
Returns a metatable where the __eq metamethod wraps equal, and the __lt and __le metamethods wrap compare, such that lists using this metatable can be ordered against each other using all of Lua's relational operators.

Selection[edit source]

  • sub (t, i, j)
Returns a sublist. i and j may be negative values and are adjusted in the same way as string.sub. If any out-of-bound index is accessed, nil is inserted into the sublist and the returned table may not be a valid Lua sequence. t may be any list-like object as long as both i and j are positive.
  • select (t, pr)
Returns a new list containing only the elements of t that satisfy pr.
  • keep_if (t, pr)
Removes elements of t that do not satisfy pr. The remaining elements form a valid Lua sequence, and relative order between these elements is preserved. Returns t.
  • delete_if (t, pr)
Removes elements of t that satisfy pr, and returns these removed elements. The removed elements and the remaining elements in t each form a valid Lua sequence, and the relative orders between the elements within each table are preserved.
  • uniq (t, f)
Returns a copy of t with all duplicate elements other than their first occurrences removed. If f is given, uniqueness between elements is determined by the results of calling f on each element.
  • compact (t)
Given an arbitrary Lua table t, returns a new list containing only values corresponding to numeric keys of t, sorted by key in ascending order.

Transformation[edit source]

  • reverse (t)
Returns a new list with the elements of t in reversed order.
  • reverse_self (t)
Reverses the order of the elements of t. Returns t.
  • map (t, f)
Returns a new list with the results of calling f on each element of t.
  • map_self (t, f)
Replaces every element of t with the result of calling f on it. Returns t.
  • zip (t1, t2, op)
Returns a new list with the results of calling op on each element of t1 and the corresponding element of t2 with the same key.
  • sort_by (t, f)
Returns a copy of t sorted by the results of calling f on each element of the table. f is evaluated exactly once for each element. The original table is unmodified.
  • concat (t1, t2)
Returns a new list with all elements from t1 followed by all elements from t2.
  • concat_self (t1, t2)
Appends all elements of t2 to the end of t1 in the same order. Returns t1.
  • to_set (t)
Returns a new table where the elements of t become the keys of the table with all corresponding values true.
  • transpose (t)
Given a list-of-lists t, returns a new table z with row indices and column indices swapped such that z[i][j] == t[j][i] for all elements in lists of t. The elements of z may not be valid Lua sequences if t is a jagged 2D array.

Other[edit source]

  • reduce (t, op)
Returns the left fold of the first element of the table over the other elements, i.e. op(...op(op(t[1], t[2]), t[3])..., t[#t]).
  • reduce (t, op, z)
Returns the left fold of z over the elements of the table, i.e. op(...op(op(z, t[1]), t[2])..., t[#t]).
  • sum (t)
Returns the sum of the elements of the table, using Lua's built-in addition operator. Equivalent to reduce(t, function (x, y) return x + y end, 0).
  • group_by (t, f)
Returns a new table in which the keys are the results of calling f on the elements of the table, and the values are lists of elements whose results compare equal to the corresponding keys.

See also[edit source]

-- Generation

local range = function (i, j, k)
	local z = {}
	for x = i, j or i, k or (i <= j and 1 or -1) do
		z[#z + 1] = x
	end
	return z
end

local generate = function (n, f)
	local z = {}
	for i = 1, n do
		z[i] = f(i)
	end
	return z
end

local array; do
	local select = select
array = function (x, rank, ...)
	local z = {}
	if select('#', ...) == 0 then
		for i = 1, rank do
			z[i] = x
		end
	else
		for i = 1, rank do
			z[i] = array(x, ...)
		end
	end
	return z
end; end



-- Counting

local any = function (t, pr)
	for i = 1, #t do
		if pr(t[i], i) then
			return true
		end
	end
	return false
end

local all = function (t, pr)
	for i = 1, #t do
		if not pr(t[i], i) then
			return false
		end
	end
	return true
end

local none = function (t, pr)
	for i = 1, #t do
		if pr(t[i], i) then
			return false
		end
	end
	return true
end

local count = function (t, x)
	local z = 0
	for i = 1, #t do
		if t[i] == x then
			z = z + 1
		end
	end
	return z
end

local count_if = function (t, pr)
	local z = 0
	for i = 1, #t do
		if pr(t[i], i) then
			z = z + 1
		end
	end
	return z
end



-- Searching

local find = function (t, x, b)
	b = b or 1
	if b < 0 then
		b = b + #t + 1
	end
	for i = b, #t do
		if t[i] == x then
			return i, t[i]
		end
	end
end

local find_if = function (t, pr, b)
	b = b or 1
	if b < 0 then
		b = b + #t + 1
	end
	for i = b, #t do
		if pr(t[i], i) then
			return i, t[i]
		end
	end
end

local rfind = function (t, x, e)
	e = e or #t
	if e < 0 then
		e = e + #t + 1
	end
	for i = e, 1, -1 do
		if t[i] == x then
			return i, t[i]
		end
	end
end

local rfind_if = function (t, pr, e)
	e = e or #t
	if e < 0 then
		e = e + #t + 1
	end
	for i = e, 1, -1 do
		if pr(t[i], i) then
			return i, t[i]
		end
	end
end

local min = function (t, op)
	if #t > 0 then
		local k = 1
		local v = t[k]
		if op then
			for i = 2, #t do
				local v2 = t[i]
				if op(v2, v) then
					k = i
					v = v2
				end
			end
		else
			for i = 2, #t do
				local v2 = t[i]
				if v2 < v then
					k = i
					v = v2
				end
			end
		end
		return k, v
	end
end

local max = function (t, op)
	if #t > 0 then
		local k = 1
		local v = t[k]
		if op then
			for i = 2, #t do
				local v2 = t[i]
				if op(v, v2) then
					k = i
					v = v2
				end
			end
		else
			for i = 2, #t do
				local v2 = t[i]
				if v < v2 then
					k = i
					v = v2
				end
			end
		end
		return k, v
	end
end

local minmax = function (t, op)
	if #t > 0 then
--		local klo = 1
--		local khi = 1
		local vlo = t[1]
		local vhi = t[1]
		if op then
			for i = 2, #t do
				local v2 = t[i]
				if op(vhi, v2) then
--					khi = i
					vhi = v2
				elseif op(v2, vlo) then
--					klo = i
					vlo = v2
				end
			end
		else
			for i = 2, #t do
				local v2 = t[i]
				if vhi < v2 then
--					khi = i
					vhi = v2
				elseif v2 < vlo then
--					klo = i
					vlo = v2
				end
			end
		end
		return vlo, vhi
	end
end



-- Comparison

local equal = function (t1, t2)
	if #t1 == #t2 then
		for i = 1, #t1 do
			if t1[i] ~= t2[i] then
				return false
			end
		end
		return true
	end
	return false
end

local compare; do
	local mathmin = math.min
compare = function (t1, t2)
	for i = 1, mathmin(#t1, #t2) do
		local a, b = t1[i], t2[i]
		if a < b then
			return -1
		elseif a > b then
			return 1
		end
	end
	return #t1 < #t2 and -1 or #t1 > #t2 and 1 or 0
end end

local equality_mixin = function ()
	return {__eq = equal}
end

local ordering_mixin = function ()
	return {
		__eq = equal,
		__lt = function (x, y) return compare(x, y) < 0 end,
		__le = function (x, y) return compare(x, y) <= 0 end,
	}
end


-- Selection

local sub = function (t, i, j)
	j = j or #t
	if i < 0 then
		i = i + #t + 1
	end
	if j < 0 then
		j = j + #t + 1
	end
	local z = {}
	for k = i, j do
		z[#z + 1] = t[k]
	end
	return z
end

local select = function (t, pr)
	local z = {}
	for i = 1, #t do
		if pr(t[i], i) then
			z[#z + 1] = t[i]
		end
	end
	return z
end

local keep_if = function (t, pr)
	local j = 1
	for i = 1, #t do
		if pr(t[i], i) then
			t[j] = t[i]
			j = j + 1
		end
	end
	for i = #t, j, -1 do
		t[i] = nil
	end
	return t
end

local delete_if = function (t, pr)
	local j = 1
	local z = {}
	for i = 1, #t do
		local v = t[i]
		if pr(v, i) then
			z[#z + 1] = v
		else
			t[j] = v
			j = j + 1
		end
	end
	for i = #t, j, -1 do
		t[i] = nil
	end
	return z
end

local uniq = function (t, f)
	local z = {}
	local set = {}
	if f ~= nil then
		for i = 1, #t do
			local v = t[i]
			local fv = f(v)
			if not set[fv] then
				set[fv] = true
				z[#z + 1] = v
			end
		end
	else
		for i = 1, #t do
			local v = t[i]
			if not set[v] then
				set[v] = true
				z[#z + 1] = v
			end
		end
	end
	return z
end

local compact; do
	local pairs, type, tablesort = pairs, type, table.sort
compact = function (t)
	local z = {}
	local ks = {}
	for k in pairs(t) do
		if type(k) == 'number' then
			ks[#ks + 1] = k
		end
	end
	tablesort(ks)
	for i = 1, #ks do
		z[#z + 1] = t[ks[i]]
	end
	return z
end end



-- Transformation

local reverse = function (t)
	local z = {}
	for i = #t, 1, -1 do
		z[#z + 1] = t[i]
	end
	return z
end

local reverse_self = function (t)
	for i = 1, #t / 2 do
		local j = #t + 1 - i
		t[i], t[j] = t[j], t[i]
	end
	return t
end

local map = function (t, f)
	local z = {}
	for i = 1, #t do
		z[i] = f(t[i], i)
	end
	return z
end

local map_self = function (t, f)
	for i = 1, #t do
		t[i] = f(t[i], i)
	end
	return t
end

local zip = function (t1, t2, op)
	local z = {}
	for i = 1, #t1 do
		z[i] = op(t1[i], t2[i])
	end
	return z
end

local sort_by; do
	local tablesort = table.sort
sort_by = function (t, f)
	local y = map(t, f)
	local indices = range(1, #t)
	tablesort(indices, function (i, j) return y[i] < y[j] end)
	map_self(indices, function (i) return t[i] end)
	return indices
end end

local concat = function (t1, t2)
	local z = {}
	for i = 1, #t1 do
		z[i] = t1[i]
	end
	for i = 1, #t2 do
		z[#z + 1] = t2[i]
	end
	return z
end

local concat_self = function (t1, t2)
	for i = 1, #t2 do
		t1[#t1 + 1] = t2[i]
	end
	return t1
end

local to_set = function (t)
	local z = {}
	for i = 1, #t do
		z[t[i]] = true
	end
	return z
end

local transpose = function (t)
	local maxsize = 0
	for i = 1, #t do
		local s = #t[i]
		if s > maxsize then
			maxsize = s
		end
	end
	local z = {}
	for i = 1, maxsize do
		z[#z + 1] = {}
	end
	for i = 1, #t do
		local v = t[i]
		for j = 1, #v do
			z[j][i] = v[j]
		end
	end
	return z
end



-- Other

local reduce = function (t, op, z)
	if z ~= nil then
		for i = 1, #t do
			z = op(z, t[i])
		end
	else
		z = t[1]
		for i = 2, #t do
			z = op(z, t[i])
		end
	end
	return z
end

local sum = function (t)
	local z = 0
	for i = 1, #t do
		z = z + t[i]
	end
	return z
end

local group_by = function (t, f)
	local z = {}
	for i = 1, #t do
		local v = t[i]
		local k = f(v, i)
		if not z[k] then
			z[k] = {}
		end
		z[k][#z[k] + 1] = v
	end
	return z
end



return {
	range = range,
	generate = generate,
	array = array,

	any = any,
	all = all,
	none = none,
	count = count,
	count_if = count_if,

	find = find,
	find_if = find_if,
	rfind = rfind,
	rfind_if = rfind_if,
	min = min,
	max = max,
	minmax = minmax,

	equal = equal,
	compare = compare,
	equality_mixin = equality_mixin,
	ordering_mixin = ordering_mixin,

	sub = sub,
	select = select,
	keep_if = keep_if,
	delete_if = delete_if,
	uniq = uniq,
	compact = compact,

	reverse = reverse,
	reverse_self = reverse_self,
	map = map,
	map_self = map_self,
	zip = zip,
	sort_by = sort_by,
	concat = concat,
	concat_self = concat_self,
	to_set = to_set,
	transpose = transpose,

	reduce = reduce,
	sum = sum,
	group_by = group_by,
}