ArrayDiff gets the difference between to arrays, detecting insertions, removals, swaps, and replacements.

ArrayDiff.lua

--[[ ArrayDiff

Receives two arrays, and gets the difference between them. Returns a list of
steps that will turn the first array into the second.

- Elements in each array should be unique
- Order of elements matters

Ops:
	insert:  {1, index, value}
	remove:  {2, index}
	swap:    {3, index, index}
	replace: {4, index, value}

]]
return function(a,b)
	-- returns whether value `v` is in table `t`, and its index
	local function isin(v,t)
		for i = 1,#t do
			if t[i] == v then
				return i
			end
		end
	end

	-- turn `a` into a copy of `a`, which will have the changes applied as we
	-- go along
	do
		local o = a
		a = {}
		for i = 1,#o do
			a[i] = o[i]
		end
	end

	-- output diff table
	local diffs = {}

	-- detect insertions and removals
	if #b > #a then
		-- there are more elements in `b`, so they must have been inserted
		while #a < #b do
			-- figure out which elements were inserted and insert them into
			-- `a`, until the sizes of `a` and `b` match
			for i = 1,#b do
				if not isin(b[i],a) then
					-- this element in `b` is not found in `a`, so it must
					-- have been inserted
					table.insert(a,i,b[i])
					-- keep track of the insertion
					diffs[#diffs+1] = {1,i,b[i]}
					break
				end
			end
		end
	elseif #b < #a then
		-- there are less elements in `b`, so they must have been removed
		while #a > #b do
			-- figure out which elements were removed and remove them from
			-- `a`, until the sizes of `a` and `b` match
			for i = 1,#a do
				if not isin(a[i],b) then
					-- this element in `a` is not found in `b`, so it must
					-- have been removed
					table.remove(a,i)
					diffs[#diffs+1] = {2,i}
					break
				end
			end
		end
	end

	-- at this point, both arrays have the same size, but there still may be
	-- new elements in `b`, or the positions of matching elements may be
	-- different. To fix this, we'll now detect swaps and replacements
	local continue
	repeat
		continue = false
		for i = 1,#a do
			-- if the two elements at the current position match, then no swap
			-- can possibly occur here, and the element certainly hasn't been
			-- replaced
			if a[i] ~= b[i] then
				-- find the position of a[i] in b, if it exists
				local j = isin(a[i],b)
				if j then
					-- we can just apply the swap without any further
					-- checking; the next full iteration will detect more
					-- swaps
					a[i],a[j] = a[j],a[i]
					diffs[#diffs+1] = {3,i,j}
					continue = true
					break
				else
					-- a[i] doesn't exist in b, so look for b[i] in a instead
					local k = isin(b[i],a)
					if k then
						-- same thing; if there are any more swaps, they will
						-- be detected in the next full iteration
						a[i],a[k] = a[k],a[i]
						diffs[#diffs+1] = {3,i,k}
						continue = true
						break
					else
						-- if neither j nor k were found, but the two elements
						-- at the current position don't match, then it must
						-- be a replacement
						a[i] = b[i]
						diffs[#diffs+1] = {4,i,b[i]}
					end
				end
			end
		end
	until not continue

	return diffs
end

test.lua

local ArrayDiff = require 'ArrayDiff'

local a = {'A','B','C'}
local bs = {
	{'A','B','C'};
	{'A','B'};
	{'B','C'};
	{'A','B','C','D'};
	{'A','D','B','C'};
	{'B','A','C'};
	{'B','C','A'};
	{'A','D','C'};
	{'B'};
	{};
	{'B','D'};
	{'D','E','C'};
	{'D','E','F'};
	{'B','A','C','D'};
	{'B','D','A','C'};
	{'D','A','C'};
	{'D','E','B','F'};
}

local ops = {
	'insert';
	'remove';
	'swap';
	'replace';
}

print("TEST STARTED")
local failed = {}
for i = 1,#bs do
	local b = bs[i]
	local d = ArrayDiff(a,b)
	local c = {}
	for i = 1,#a do
		c[i] = a[i]
	end
	for i = 1,#d do
		local op = d[i]
		op[1] = ops[op[1]]
		if op[1] == 'insert' then
			table.insert(c,op[2],op[3])
		elseif op[1] == 'remove' then
			table.remove(c,op[2])
		elseif op[1] == 'swap' then
			c[op[2]],c[op[3]] = c[op[3]],c[op[2]]
		elseif op[1] == 'replace' then
			c[op[2]] = op[3]
		end
	end
	local equal = true
	if #c ~= #b then
		equal = false
	else
		for i = 1,#c do
			if c[i] ~= b[i] then
				equal = false
				break
			end
		end
	end
	if not equal then
		failed[#failed+1] = i
	end
	print()
	print("TEST "..i..": ["..table.concat(a," ").."] -> ["..table.concat(b," ").."]: "..(equal and "PASSED" or "FAILED"))
	for i = 1,#d do
		print("    " .. table.concat(d[i]," "))
	end
end
print()
print("TEST FINISHED")
if #failed > 0 then
	print("FAILED TESTS: " .. table.concat(failed,", "))
else
	print("ALL TESTS PASSED")
end