Module:Set

 --[[
 ------------------------------------------------------------------------------------
 -- Set --
 -- --
 -- This module includes a number of set operations for dealing with Lua tables. --
 -- It currently has union, intersection and complement functions for both --
 -- key/value pairs and for values only. --
 ------------------------------------------------------------------------------------
 --]]

 -- Get necessary libraries and functions
 locallibraryUtil=require('libraryUtil')
 localcheckType=libraryUtil.checkType
 localtableTools=require('Module:TableTools')

 localp={}

 --[[
 ------------------------------------------------------------------------------------
 -- Helper functions
 ------------------------------------------------------------------------------------
 --]]

 -- Makes a set from a table's values. Returns an array of all values with
 -- duplicates removed.
 localfunctionmakeValueSet(t)
 localisNan=tableTools.isNan
 localret,exists={},{}
 fork,vinpairs(t)do
 ifisNan(v)then
 -- NaNs are always unique, and they can't be table keys, so don't
 -- check for existence.
 ret[#ret+1]=v
 elseifnotexists[v]then
 exists[v]=true
 ret[#ret+1]=v
 end
 end
 returnret
 end

 --[[
 ------------------------------------------------------------------------------------
 -- union
 --
 -- This returns the union of the key/value pairs of n tables. If any of the tables
 -- contain different values for the same table key, the table value is converted
 -- to an array holding all of the different values.
 ------------------------------------------------------------------------------------
 --]]
 functionp.union(...)
 locallim=select('#',...)
 iflim<2then
 error("too few arguments to 'union' (minimum is 2, received "..lim..')',2)
 end
 localret,trackArrays={},{}
 fori=1,limdo
 localt=select(i,...)
 checkType('union',i,t,'table')
 fork,vinpairs(t)do
 localretKey=ret[k]
 ifretKey==nilthen
 ret[k]=v
 elseifretKey~=vthen
 iftrackArrays[k]then
 localarray=ret[k]
 localvalExists
 for_,arrayValinipairs(array)do
 ifarrayVal==vthen
 valExists=true
 break
 end
 end
 ifnotvalExiststhen
 array[#array+1]=v
 ret[k]=array
 end
 else
 ret[k]={ret[k],v}
 trackArrays[k]=true
 end
 end
 end
 end
 returnret
 end

 --[[
 ------------------------------------------------------------------------------------
 -- valueUnion
 --
 -- This returns the union of the values of n tables, as an array. For example, for
 -- the tables {1, 3, 4, 5, foo = 7} and {2, bar = 3, 5, 6}, union will return
 -- {1, 2, 3, 4, 5, 6, 7}.
 ------------------------------------------------------------------------------------
 --]]
 functionp.valueUnion(...)
 locallim=select('#',...)
 iflim<2then
 error("too few arguments to 'valueUnion' (minimum is 2, received "..lim..')',2)
 end
 localisNan=tableTools.isNan
 localret,exists={},{}
 fori=1,limdo
 localt=select(i,...)
 checkType('valueUnion',i,t,'table')
 fork,vinpairs(t)do
 ifisNan(v)then
 ret[#ret+1]=v
 elseifnotexists[v]then
 ret[#ret+1]=v
 exists[v]=true
 end
 end
 end
 returnret
 end

 --[[
 ------------------------------------------------------------------------------------
 -- intersection
 --
 -- This returns the intersection of the key/value pairs of n tables. Both the key
 -- and the value must match to be included in the resulting table.
 ------------------------------------------------------------------------------------
 --]]
 functionp.intersection(...)
 locallim=select('#',...)
 iflim<2then
 error("too few arguments to 'intersection' (minimum is 2, received "..lim..')',2)
 end
 localret,track,pairCounts={},{},{}
 fori=1,limdo
 localt=select(i,...)
 checkType('intersection',i,t,'table')
 fork,vinpairs(t)do
 localtrackVal=track[k]
 iftrackVal==nilthen
 track[k]=v
 pairCounts[k]=1
 elseiftrackVal==vthen
 pairCounts[k]=pairCounts[k]+1
 end
 end
 end
 fork,vinpairs(track)do
 ifpairCounts[k]==limthen
 ret[k]=v
 end
 end
 returnret
 end

 --[[
 ------------------------------------------------------------------------------------
 -- valueIntersection
 --
 -- This returns the intersection of the values of n tables, as an array. For
 -- example, for the tables {1, 3, 4, 5, foo = 7} and {2, bar = 3, 5, 6}, 
 -- intersection will return {3, 5}.
 ------------------------------------------------------------------------------------
 --]]

 functionp.valueIntersection(...)
 locallim=select('#',...)
 iflim<2then
 error("too few arguments to 'valueIntersection' (minimum is 2, received "..lim..')',2)
 end
 localisNan=tableTools.isNan
 localvals,ret={},{}
 localisSameTable=true-- Tracks table equality.
 localtableTemp-- Used to store the table from the previous loop so that we can check table equality.
 fori=1,limdo
 localt=select(i,...)
 checkType('valueIntersection',i,t,'table')
 iftableTempandt~=tableTempthen
 isSameTable=false
 end
 tableTemp=t
 t=makeValueSet(t)-- Remove duplicates
 fork,vinpairs(t)do
 -- NaNs are never equal to any other value, so they can't be in the intersection.
 -- Which is lucky, as they also can't be table keys.
 ifnotisNan(v)then
 localvalCount=vals[v]or0
 vals[v]=valCount+1
 end
 end
 end
 ifisSameTablethen
 -- If all the tables are equal, then the intersection is that table (including NaNs).
 -- All we need to do is convert it to an array and remove duplicate values.
 returnmakeValueSet(tableTemp)
 end
 forval,countinpairs(vals)do
 ifcount==limthen
 ret[#ret+1]=val
 end
 end
 returnret
 end

 --[[
 ------------------------------------------------------------------------------------
 -- complement
 --
 -- This returns the relative complement of t1, t2, ..., in tn. The complement
 -- is of key/value pairs. This is equivalent to all the key/value pairs that are in
 -- tn but are not in t1, t2, ... tn-1.
 ------------------------------------------------------------------------------------
 --]]
 functionp.complement(...)
 locallim=select('#',...)
 iflim<2then
 error("too few arguments to 'complement' (minimum is 2, received "..lim..')',2)
 end
 --[[
 	-- Now we know that we have at least two sets.
 	-- First, get all the key/value pairs in tn. We can't simply make ret equal to tn,
 	-- as that will affect the value of tn for the whole module.
 	--]]
 localtn=select(lim,...)
 checkType('complement',lim,tn,'table')
 localret=tableTools.shallowClone(tn)
 -- Remove all the key/value pairs in t1, t2, ..., tn-1.
 fori=1,lim-1do
 localt=select(i,...)
 checkType('complement',i,t,'table')
 fork,vinpairs(t)do
 ifret[k]==vthen
 ret[k]=nil
 end
 end
 end
 returnret
 end

 --[[
 ------------------------------------------------------------------------------------
 -- valueComplement
 --
 -- This returns an array containing the relative complement of t1, t2, ..., in tn.
 -- The complement is of values only. This is equivalent to all the values that are
 -- in tn but are not in t1, t2, ... tn-1.
 ------------------------------------------------------------------------------------
 --]]
 functionp.valueComplement(...)
 locallim=select('#',...)
 iflim<2then
 error("too few arguments to 'valueComplement' (minimum is 2, received "..lim..')',2)
 end
 localisNan=tableTools.isNan
 localret,exists={},{}
 fori=1,lim-1do
 localt=select(i,...)
 checkType('valueComplement',i,t,'table')
 t=makeValueSet(t)-- Remove duplicates
 fork,vinpairs(t)do
 ifnotisNan(v)then
 -- NaNs cannot be table keys, and they are also unique so cannot be equal to anything in tn.
 exists[v]=true
 end
 end
 end
 localtn=select(lim,...)
 checkType('valueComplement',lim,tn,'table')
 tn=makeValueSet(tn)-- Remove duplicates
 fork,vinpairs(tn)do
 ifisNan(v)orexists[v]==nilthen
 ret[#ret+1]=v
 end
 end
 returnret
 end

 --[[
 ------------------------------------------------------------------------------------
 -- symmDiff
 --
 -- This returns the symmetric difference of key/value pairs of t1, t2, ..., tn.
 -- The symmetric difference of two tables consists of the key/value pairs
 -- that appear in set 1 but not set 2, together with the key/value pairs that
 -- appear in set 2 but not in set 1. This is the same as the union of the two
 -- minus the intersection. If either of the tables contain different values for the
 -- same table key, the table value is converted to an array holding all of the
 -- different values.For more than two tables, this can get confusing - see the 
 -- "Symmetric difference" article for details.
 ------------------------------------------------------------------------------------
 --]]

 --[[ -- This is a rough work in progress.
 function p.symmDiff(...)
 	local lim = select('#', ...) 
 	if lim < 2 then
 		error("too few arguments to 'symmDiff' (minimum is 2, received " .. lim .. ')', 2)
 	end

 	local tremove = table.remove
 	local trackArrays = {}

 	local function symmDiffTwo(t1, t2)
 		local ret = {}
 		for k, v in pairs(t1) do
 			local t2val = t2[k]
 			if t2val == nil then
 				ret[k] = v
 			elseif trackArrays[k] then
 				local array = ret[k]
 				local valExists
 				for i, arrayVal in ipairs(array) do
 					if arrayVal == v then
 						valExists = true
 						break
 					end
 				end
 				if not valExists then
 					array[#array + 1] = v
 				end
 			elseif v ~= t2val then
 				ret[k] = {t2val, v}
 				trackArrays[k] = true
 			end
 --]]

 returnp