/sorter.bend Secret
Last active
May 20, 2024 07:37
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(18, sort(18, 0, gen(18, 0))) |
It looks like sorting direction - "ascending" when s = 0; "descending" otherwise.
im guessing no build in boolean type?
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Why do all the functions have an
sparameter, when onlyswapuses it? Why is it added to the comparison, on line 25?