1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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
|
