binary tree

R=rsc
DELTA=324  (323 added, 0 deleted, 1 changed)
OCL=32759
CL=32768

1 files changed, 93 insertions, 0 deletions

diff --git a/test/bench/binary-tree.go b/test/bench/binary-tree.go
new file mode 100644
index 000000000..030e6acb0
--- /dev/null
+++ b/test/bench/binary-tree.go
@@ -0,0 +1,93 @@
+/*
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+    notice, this list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright
+    notice, this list of conditions and the following disclaimer in the
+    documentation and/or other materials provided with the distribution.
+
+    * Neither the name of "The Computer Language Benchmarks Game" nor the
+    name of "The Computer Language Shootout Benchmarks" nor the names of
+    its contributors may be used to endorse or promote products derived
+    from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/* The Computer Language Benchmarks Game
+ * http://shootout.alioth.debian.org/
+ *
+ * contributed by The Go Authors.
+ * based on C program by Kevin Carson
+ */
+
+package main
+
+import (
+	"flag";
+	"fmt";
+	"os";
+)
+
+var n = flag.Int("n", 20, "depth")
+
+type Node struct {
+	  item	int;
+	  left, right	*Node;
+}
+
+func  bottomUpTree(item, depth int) *Node {
+	if depth <= 0 {
+		return &Node{item: item}
+	}
+	return &Node{ item, bottomUpTree(2*item-1, depth-1), bottomUpTree(2*item, depth-1) }
+}
+
+func (n *Node) itemCheck() int {
+	if n.left == nil {
+		return n.item
+	}
+	return n.item + n.left.itemCheck() - n.right.itemCheck();
+}
+
+const minDepth = 4;
+
+func main() {
+	flag.Parse();
+
+	maxDepth := *n;
+	if minDepth + 2 > *n {
+		maxDepth = minDepth + 2
+	}
+	stretchDepth := maxDepth + 1;
+
+	check := bottomUpTree(0, stretchDepth).itemCheck();
+	fmt.Println("stretch tree of depth ", stretchDepth, "\t check:", check);
+
+	longLivedTree := bottomUpTree(0, maxDepth);
+
+	for depth := minDepth; depth <= maxDepth; depth+=2 {
+		iterations := 1 << uint(maxDepth - depth + minDepth);
+		check = 0;
+
+		for i := 1; i <= iterations; i++ {
+			check += bottomUpTree(i,depth).itemCheck();
+			check += bottomUpTree(-i,depth).itemCheck();
+		}
+		fmt.Println(iterations*2, "\t trees of depth ", depth, "\t check: ", check);
+	}
+	fmt.Println("long lived tree of depth", maxDepth, "\t check:", longLivedTree.itemCheck());
+}