Mercurial > repos > rhope
view binary_trees.rhope @ 93:09831a71a4bc
Added binary trees benchmark
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Mon, 02 Aug 2010 00:59:27 -0400 |
parents | |
children | f4fd8962c385 |
line wrap: on
line source
Blueprint Tree { Left Right Item } Blueprint Empty { } Make Tree[item,depth:out] { If[depth] { dbl <- [item]+[item] ndepth <- [depth]-[1] out <- [[[Build[Tree()]]Left <<[ Make Tree[[dbl]-[1], ndepth] ]]Right <<[ Make Tree[dbl, ndepth] ]]Item <<[item] }{ out <- [[[Build[Tree()]]Left <<[Build[Empty()]]]Right <<[Build[Empty()]]]Item <<[item] } } Check Tree@Tree[node:out] { out <- [[[node]Item >>]+[Check Tree[[node]Left >>]]] - [Check Tree[[node]Right >>]] } Check Tree@Empty[node:out] { out <- 0 } Step[num, depth: out] { out <- [Check Tree[Make Tree[num, depth]]] + [Check Tree[Make Tree[[0]-[num], depth]]] } Test Size[sum, current,iterations,depth:out] { nsum <- [sum]+[Step[current, depth]] If[[current]=[iterations]] { out <- Val[nsum] }{ out <- Test Size[nsum, [current]+[1], iterations, depth] } } Test Sizes[current,max,iterations:out] { sum <- Test Size[0, 1, iterations, current] { Print[[iterations]*[2]] { Print["trees of depth"] { Print[current] { Print["check"] { Print[sum] { If[[current]=[max]] { out <- 1 }{ out <- Test Sizes[[current]+[2], max, [iterations]/[4]] } }}}}} } } Main[] { min depth <- 4 max depth <- 16 Print["stretch tree of depth 17 check:"] { Print[Check Tree[Make Tree[0, 17]]] { long lived <- Make Tree[0, max depth] { Test Sizes[min depth, max depth, [1]LShift[max depth]] { Print["long lived tree of depth 16 check:"] { Print[Check Tree[long lived]] }}}}} }