-
-
Save VictorTaelin/face210ca4bc30d96b2d5980278d3921 to your computer and use it in GitHub Desktop.
# Sorting Network = just rotate trees! | |
def sort(d, s, tree): | |
switch d: | |
case 0: | |
return tree | |
case _: | |
(x,y) = tree | |
lft = sort(d-1, 0, x) | |
rgt = sort(d-1, 1, y) | |
return rots(d, s, (lft, rgt)) | |
# Rotates sub-trees (Blue/Green Box) | |
def rots(d, s, tree): | |
switch d: | |
case 0: | |
return tree | |
case _: | |
(x,y) = tree | |
return down(d, s, warp(d-1, s, x, y)) | |
# Swaps distant values (Red Box) | |
def warp(d, s, a, b): | |
switch d: | |
case 0: | |
return swap(s ^ (a > b), a, b) | |
case _: | |
(a.a, a.b) = a | |
(b.a, b.b) = b | |
(A.a, A.b) = warp(d-1, s, a.a, b.a) | |
(B.a, B.b) = warp(d-1, s, a.b, b.b) | |
return ((A.a,B.a),(A.b,B.b)) | |
# Propagates downwards | |
def down(d,s,t): | |
switch d: | |
case 0: | |
return t | |
case _: | |
(t.a, t.b) = t | |
return (rots(d-1, s, t.a), rots(d-1, s, t.b)) | |
# Swaps a single pair | |
def swap(s, a, b): | |
switch s: | |
case 0: | |
return (a,b) | |
case _: | |
return (b,a) | |
# Testing | |
# ------- | |
# Generates a big tree | |
def gen(d, x): | |
switch d: | |
case 0: | |
return x | |
case _: | |
return (gen(d-1, x * 2 + 1), gen(d-1, x * 2)) | |
# Sums a big tree | |
def sum(d, t): | |
switch d: | |
case 0: | |
return t | |
case _: | |
(t.a, t.b) = t | |
return sum(d-1, t.a) + sum(d-1, t.b) | |
# Sorts a big tree | |
def main: | |
return sum(20, sort(20, 0, gen(20, 0))) |
It looks like sorting direction - "ascending" when s = 0; "descending" otherwise.
im guessing no build in boolean type?
It looks like sorting direction - "ascending" when s = 0; "descending" otherwise.
That much is clear, it's emulating a boolean, but that wasn't my question
all functions have the s
parameter because it needs to get to the swap
function somehow, so it must be passed down up to that point. i may be missing some optimizations though, if that's what you mean. also, the original code had a small type error that is fixed now. also, adding was a mistake, it should be xor'ing. fixed it
also, adding was a mistake, it should be xor'ing. fixed it
Ah, this way it makes way more sense xd
(I used +
as a placeholder since we didn't have ^
, and forgot to change it)
Why do all the functions have an
s
parameter, when onlyswap
uses it? Why is it added to the comparison, on line 25?