Mercurial > repos > icfp2014
comparison code/tree.lm @ 40:d5ccb66ae98b
Move some basic library code out of dotScanner.lm into separate files now that import:from works
author | Michael Pavone <pavone@retrodev.com> |
---|---|
date | Sat, 26 Jul 2014 15:29:01 -0700 |
parents | |
children | e1047192610c |
comparison
equal
deleted
inserted
replaced
39:0e1fc2b2832f | 40:d5ccb66ae98b |
---|---|
1 #{ | |
2 makeTree:size <- :lst :size { | |
3 ret <- 0 | |
4 sub <- 0 | |
5 half <- size / 2 | |
6 if: size = 2 { | |
7 ret <- #[(lst value) ((lst tail) value)] | |
8 } else: { | |
9 if: size = 1 { | |
10 ret <- lst | |
11 } else: { | |
12 sub <- split: lst at: half | |
13 ret <- #[ | |
14 (makeTree: (sub value) size: half) | |
15 (makeTree: (sub tail) size: size-half) | |
16 ] | |
17 } | |
18 } | |
19 ret | |
20 } | |
21 | |
22 makeTree <- :lst { | |
23 size <- lst length | |
24 #[size (makeTree: lst size: size)] | |
25 } | |
26 | |
27 get:fromTree:size <- :idx :tree :size { | |
28 ret <- 0 | |
29 half <- size / 2 | |
30 if: size <= 2 { | |
31 if: idx = 0 { | |
32 ret <- tree value | |
33 } else: { | |
34 ret <- tree tail | |
35 } | |
36 } else: { | |
37 if: idx < half { | |
38 ret <- get: idx fromTree: (tree value) size: half | |
39 } else: { | |
40 ret <- get: idx-half fromTree: (tree tail) size: size-half | |
41 } | |
42 } | |
43 ret | |
44 } | |
45 | |
46 get:fromTree <- :idx :tree { | |
47 size <- tree value | |
48 get: idx fromTree: (tree tail) size: size | |
49 } | |
50 | |
51 treeMap:size <- :tree fun :size { | |
52 ret <- 0 | |
53 half <- size / 2 | |
54 if: size = 2 { | |
55 ret <- #[(fun: (tree value)) (fun: (tree tail))] | |
56 } else: { | |
57 if: size = 1 { | |
58 ret <- #[(fun: (tree value)) 0] | |
59 } else: { | |
60 ret <- #[ | |
61 (treeMap: (tree value) fun size: half) | |
62 (treeMap: (tree tail) fun size: size-half) | |
63 ] | |
64 } | |
65 } | |
66 ret | |
67 } | |
68 | |
69 treeMap <- :tree fun { | |
70 #[(tree value) (treeMap: (tree tail) fun size: (tree value))] | |
71 } | |
72 | |
73 tree:size:update:with <- :tree :size :idx :fun { | |
74 ret <- 0 | |
75 half <- size / 2 | |
76 if: size = 2 { | |
77 if: idx = 0 { | |
78 ret <- #[(fun: (tree value)) (tree tail)] | |
79 } else: { | |
80 ret <- #[(tree value) (fun: (tree tail))] | |
81 } | |
82 } else: { | |
83 if: size = 1 { | |
84 ret <- #[(fun: (tree value)) 0] | |
85 } else: { | |
86 if: (idx < half) { | |
87 ret <- #[ | |
88 (tree: (tree value) size: half update: idx with: fun) | |
89 (tree tail) | |
90 ] | |
91 } else: { | |
92 ret <- #[ | |
93 (tree value) | |
94 (tree: (tree tail) size: size-half update: idx-half with: fun) | |
95 ] | |
96 } | |
97 } | |
98 } | |
99 ret | |
100 } | |
101 | |
102 tree:update:with <- :tree :idx :fun { | |
103 #[(tree value) (tree: (tree tail) size: (tree value) update: idx with: fun)] | |
104 } | |
105 | |
106 tree:set:to <- :tree :idx :val { | |
107 tree: tree update: idx with: :el { val } | |
108 } | |
109 } |