gistfile1.cs

namespace BenchmarkGameBTrees
{
	/*
          The Computer Language Benchmarks Game
          http://benchmarksgame.alioth.debian.org/ 

          contributed by Marek Safar  
          optimized by kasthack
    */
	using System;
	using System.Threading;
	using System.Threading.Tasks;

	unsafe class BinaryTrees
	{
		const int minDepth = 4;
		public static void Main(string[] args)
		{
			int n = 0;
			if (args.Length > 0) n = int.Parse(args[0]);
			int maxDepth = Math.Max(minDepth + 2, n);
			int stretchDepth = maxDepth + 1;
			var nodeCache = new TreeNode[(1 << stretchDepth)];
			fixed (TreeNode* cache = nodeCache)
			{
				TreeNode.TreeNodeCache = cache;
				int check = (TreeNode.bottomUpTree(0, stretchDepth))->itemCheck();
				Console.WriteLine("stretch tree of depth {0}\t check: {1}", stretchDepth, check);
				var longLivedTree = TreeNode.bottomUpTree(0, maxDepth);
				for (int depth = minDepth; depth <= maxDepth; depth += 2)
				{
					int iterations = 1 << (maxDepth - depth + minDepth);
					check = 0;

					for (int i = 1; i <= iterations; i++)
					{
						check += (TreeNode.bottomUpTree(i, depth))->itemCheck();
						check += (TreeNode.bottomUpTree(-i, depth))->itemCheck();
					}

					Console.WriteLine("{0}\t trees of depth {1}\t check: {2}",
									  iterations * 2, depth, check);
				}
				Console.WriteLine("long lived tree of depth {0}\t check: {1}",
								  maxDepth, longLivedTree->itemCheck());
			}
		}

		unsafe struct TreeNode
		{
			public static TreeNode* TreeNodeCache;
			private TreeNode* left, right;
			private int item;

			internal static TreeNode* bottomUpTree(int item, int depth)
			{
				int n = 1;
				return ChildTreeNodes(ref n, item, depth - 1);
			}

			static TreeNode* ChildTreeNodes(ref int n, int item, int depth)
			{
				var node = (TreeNode*) (TreeNodeCache + (n++));
				node->item = item;
				if (depth > 0)
				{
					node->left = ChildTreeNodes(ref n, 2 * item - 1, depth - 1);
					node->right = ChildTreeNodes(ref n, 2 * item, depth - 1);
				} else {
					node->left = TreeNodeCache;
					node->right = TreeNodeCache;
				}
				return node;
			}

			internal int itemCheck()
			{
				if (right == TreeNodeCache) 
					return item;
				
				return item + left->itemCheck() - right->itemCheck();
			}
		}
	}
}