Mercurial > repos > rhope

comparison binary_trees.rhope @ 93:09831a71a4bc

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added binary trees benchmark
author Mike Pavone <pavone@retrodev.com>
date Mon, 02 Aug 2010 00:59:27 -0400
parents
children f4fd8962c385
comparison
equal deleted inserted replaced
92:e73a93fb5de1 93:09831a71a4bc
1
2
3 Blueprint Tree
4 {
5 Left
6 Right
7 Item
8 }
9
10 Blueprint Empty
11 {
12
13 }
14
15 Make Tree[item,depth:out]
16 {
17 If[depth]
18 {
19 dbl <- [item]+[item]
20 ndepth <- [depth]-[1]
21 out <- [[[Build[Tree()]]Left <<[ Make Tree[[dbl]-[1], ndepth] ]]Right <<[ Make Tree[dbl, ndepth] ]]Item <<[item]
22 }{
23 out <- [[[Build[Tree()]]Left <<[Build[Empty()]]]Right <<[Build[Empty()]]]Item <<[item]
24 }
25 }
26
27 Check Tree@Tree[node:out]
28 {
29 out <- [[[node]Item >>]+[Check Tree[[node]Left >>]]] - [Check Tree[[node]Right >>]]
30 }
31
32 Check Tree@Empty[node:out]
33 {
34 out <- 0
35 }
36
37 Step[num, depth: out]
38 {
39 out <- [Check Tree[Make Tree[num, depth]]] + [Check Tree[Make Tree[[0]-[num], depth]]]
40 }
41
42 Test Size[sum, current,iterations,depth:out]
43 {
44 nsum <- [sum]+[Step[current, depth]]
45 If[[current]=[iterations]]
46 {
47 out <- Val[nsum]
48 }{
49 out <- Test Size[nsum, [current]+[1], iterations, depth]
50 }
51 }
52
53 Test Sizes[current,max,iterations:out]
54 {
55 sum <- Test Size[0, 1, iterations, current]
56 {
57 Print[[iterations]*[2]]
58 { Print["trees of depth"]
59 { Print[current]
60 { Print["check"]
61 { Print[sum]
62 {
63 If[[current]=[max]]
64 {
65 out <- 1
66 }{
67 out <- Test Sizes[[current]+[2], max, [iterations]/[4]]
68 }
69 }}}}}
70 }
71 }
72
73 Main[]
74 {
75 min depth <- 4
76 max depth <- 16
77 Print["stretch tree of depth 17 check:"]
78 { Print[Check Tree[Make Tree[0, 17]]]
79 { long lived <- Make Tree[0, max depth]
80 { Test Sizes[min depth, max depth, [1]LShift[max depth]]
81 { Print["long lived tree of depth 16 check:"]
82 { Print[Check Tree[long lived]] }}}}}
83 }
84