1 files changed, 50 insertions, 0 deletions
diff --git a/common/rle.lua b/common/rle.lua
new file mode 100644
index 0000000..2944c4c
--- /dev/null
+++ b/common/rle.lua
@@ -0,0 +1,50 @@
+-- run length encoding
+
+local function encode(l)
+	local out = {}
+
+	local last = l[1]
+	local count = 1
+
+	local function ap()
+		if count == 1 then
+			table.insert(out,last)
+		elseif count == 2 then
+			table.insert(out,last)
+			table.insert(out,last)
+		else
+			table.insert(out,{count,last})
+		end
+	end
+
+	for ix=2,#l do
+		local val = l[ix]
+		if val == last then
+			count = count + 1
+		else
+			ap()
+			last = val
+			count = 1
+		end
+	end
+
+	ap()
+
+	return out
+end
+
+local function decode(l)
+	local out = {}
+	for _,r in ipairs(l) do
+		if type(r) == "table" and #r == 2 then
+			for i = 1,r[1] do
+				table.insert(out,r[2])
+			end
+		else
+			table.insert(out,r)
+		end
+	end
+	return out
+end
+
+return {encode=encode,decode=decode}