모듈:table/removeDuplicates

이 모듈에 대한 설명문서는 모듈:table/removeDuplicates/설명문서에서 만들 수 있습니다

local table_deep_equals_module = "Module:table/deepEquals"
local table_get_metamethod_module = "Module:table/getMetamethod"

local rawequal = rawequal
local require = require
local type = type

local function get_metamethod(...)
	get_metamethod = require(table_get_metamethod_module)
	return get_metamethod(...)
end

local deep_equals
local function get_deep_equals()
	deep_equals, get_deep_equals = require(table_deep_equals_module), nil
	return deep_equals
end

local function equal(a, b)
	return a == b
end

-- Sentinel for nil.
local _nil = {}

local __eq_types = {
	table = true,
	userdata = true,
}

local function seen_map_check(seen_map, v_comp, comp_func)
	if not comp_func(v_comp, v_comp) then
		return false, seen_map
	end
	local v_seen_map = v_comp == nil and _nil or v_comp
	if not seen_map then
		seen_map = {[v_seen_map] = true}
		return false, seen_map
	elseif seen_map[v_seen_map] then
		return true, seen_map
	end
	seen_map[v_seen_map] = true
	return false, seen_map
end

-- Differs from [[Module:table/contains]], as keys might be nil.
local function seen_array_contains(v_comp, seen_array, seen_array_n, comp_func)
	for i = 1, seen_array_n do
		if comp_func(v_comp, seen_array[i]) then
			return true
		end
	end
	return false
end

local function default_seen_array_check(v_comp, seen_array, seen_array_n, comp_func)
	local v_comp_type = type(v_comp)
	if not __eq_types[v_comp_type] then
		return false, seen_array, seen_array_n
	elseif not seen_array then
		return false, {v_comp}, 1
	-- If `comp_func` is `deep_equals` and `v_comp` is a table, `seen_array`
	-- must be checked.
	elseif comp_func == deep_equals and v_comp_type == "table" then
		if seen_array_contains(v_comp, seen_array, seen_array_n, comp_func) then
			return true, seen_array, seen_array_n
		end
	else
		-- If `v_comp` has an `__eq` metamethod (or could have one, if it's not
		-- possible to retrieve due to a protected metatable), then check with
		-- `seen_array_contains`.
		local success, __eq = get_metamethod(v_comp, "__eq")
		if (
			not (success and __eq == nil) and
			seen_array_contains(v_comp, seen_array, seen_array_n, comp_func)
		) then
			return true, seen_array, seen_array_n
		end
	end
	seen_array_n = seen_array_n + 1
	seen_array[seen_array_n] = v_comp
	return false, seen_array, seen_array_n
end

local function other_seen_array_check(v_comp, seen_array, seen_array_n, comp_func)
	if not seen_array then
		return false, {v_comp}, 1
	elseif seen_array_contains(v_comp, seen_array, seen_array_n, comp_func) then
		return true, seen_array, seen_array_n
	end
	seen_array_n = seen_array_n + 1
	seen_array[seen_array_n] = v_comp
	return false, seen_array, seen_array_n
end

return function(list, options)
	-- Values are converted to comparison-keys using `key_func`, if supplied, or else the value itself is used as the comparison-key; these are then compared with `comp_func` to determine duplicates.
	-- To avoid comparing all comparison-keys with each other, which is O(n^2), `seen_map`, a lookup table, and `seen_array`, an array, are used as memos to store already-seen comparison-keys.
	-- Comparison-keys are stored in `seen_map` if comp_func(x, x) evaluates as true.
		-- This is always the case if `comp_func` is `rawequal`, `==` or `deep_equals`, unless the comparison-key is NaN.
		-- If `comp_func` is anything else, the value is checked against itself before storing it.
	-- If the comparison-key isn't found in `seen_map`, it's checked against each comparison-key stored in `seen_array`.
		-- This is never needed if `comp_func` is `rawequal`, which only returns true for primitive equality (i.e. `seen_map` is sufficient for everything).
		-- If `comp_func` is `==` or `deep_equals`, `seen_array` is used for data types which could have `__eq` metamethods, which can result in non-primitively equal values being deemed equal (i.e. new comparison-keys need to be compared in turn).
		-- If `comp_func` is anything else, all comparison-keys will need to be stored in `seen_array`.
	local key_func, comp_func, seen_array_check
	if options == nil then
		comp_func, seen_array_check = deep_equals or get_deep_equals(), default_seen_array_check
	else
		key_func, comp_func = options.key, options.comparison
		if comp_func == nil then
			comp_func, seen_array_check = deep_equals or get_deep_equals(), default_seen_array_check
		elseif comp_func == "==" then
			comp_func, seen_array_check = equal, default_seen_array_check
		-- `seen_array_check` is not necessary if `comp_func` is `rawequal`.
		elseif comp_func ~= rawequal then
			if comp_func == (deep_equals or get_deep_equals()) then
				seen_array_check = default_seen_array_check
			else
				seen_array_check = other_seen_array_check
			end
		end
	end
	local output, i, n, seen_map, seen_array, seen_array_n = {}, 1, 0
	while true do
		local v = list[i]
		if v == nil then
			return output
		end
		local v_comp, seen = v
		if key_func ~= nil then
			v_comp = key_func(v_comp)
		end
		seen, seen_map = seen_map_check(seen_map, v_comp, comp_func)
		if not seen then
			if seen_array_check then
				seen, seen_array, seen_array_n = seen_array_check(v_comp, seen_array, seen_array_n, comp_func)
			end
			if not seen then
				n = n + 1
				output[n] = v
			end
		end
		i = i + 1
	end
end