-
-
Save VictorTaelin/face210ca4bc30d96b2d5980278d3921 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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))) |
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)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
all functions have the
s
parameter because it needs to get to theswap
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