Mercurial > repos > icfp2014

comparison code/tree.lm @ 40:d5ccb66ae98b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }