# HG changeset patch
# User Mike Pavone <pavone@retrodev.com>
# Date 1280725167 14400
# Node ID 09831a71a4bcd868908976e70a14e96eb85bd178
# Parent  e73a93fb5de1ebaa2c1c4b31e1b353fa2271f053
Added binary trees benchmark

diff -r e73a93fb5de1 -r 09831a71a4bc binary_trees.rhope
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/binary_trees.rhope	Mon Aug 02 00:59:27 2010 -0400
@@ -0,0 +1,84 @@
+
+
+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]] }}}}}
+}
+