Snapshot

1 files changed, 52 insertions, 0 deletions

diff --git a/util.lua b/util.lua
new file mode 100644
index 0000000..bb9b2e8
--- /dev/null
+++ b/util.lua
@@ -0,0 +1,52 @@
+-- https://pico-8.fandom.com/wiki/Qsort
+function qsort(a,c,l,r)
+	c,l,r=c or function(a,b) return a<b end,l or 1,r or #a
+	if l<r then
+		if c(a[r],a[l]) then
+			a[l],a[r]=a[r],a[l]
+		end
+		local lp,k,rp,p,q=l+1,l+1,r-1,a[l],a[r]
+		while k<=rp do
+			local swaplp=c(a[k],p)
+			-- "if a or b then else"
+			-- saves a token versus
+			-- "if not (a or b) then"
+			if swaplp or c(a[k],q) then
+			else
+				while c(q,a[rp]) and k<rp do
+					rp-=1
+				end
+				a[k],a[rp],swaplp=a[rp],a[k],c(a[rp],p)
+				rp-=1
+			end
+			if swaplp then
+				a[k],a[lp]=a[lp],a[k]
+				lp+=1
+			end
+			k+=1
+		end
+		lp-=1
+		rp+=1
+		-- sometimes lp==rp, so 
+		-- these two lines *must*
+		-- occur in sequence;
+		-- don't combine them to
+		-- save a token!
+		a[l],a[lp]=a[lp],a[l]
+		a[r],a[rp]=a[rp],a[r]
+		qsort(a,c,l,lp-1       )
+		qsort(a,c,  lp+1,rp-1  )
+		qsort(a,c,       rp+1,r)
+	end
+    return a
+end
+
+function filter(a, pred)
+    filtered = {}
+    for k,v in ipairs(a) do
+        if pred(v) then
+            filtered[k] = v
+        end
+    end
+    return filtered
+end
\ No newline at end of file