gistfile1.txt

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;

	class BinaryTrees
	{
		const int minDepth = 4;
		public static void Main(String[] args)
		{
			int n = 0;
			if (args.Length > 0) n = Int32.Parse(args[0]);
			int maxDepth = Math.Max(minDepth + 2, n);
			int stretchDepth = maxDepth + 1;
			int check = (TreeNode.bottomUpTree(0, stretchDepth)).itemCheck();
			Console.WriteLine("stretch tree of depth {0}\t check: {1}", stretchDepth, check);
			TreeNode 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();
                }
                
				/*
				Parallel.For(1, iterations + 1,
				             () => 0,
				             (i, loop, localCheck) =>
				{
					return localCheck + (TreeNode.bottomUpTree(i, depth)).itemCheck() + (TreeNode.bottomUpTree(-i, depth)).itemCheck();
				},
				             localCheck => Interlocked.Add(ref check, localCheck)
				            );
*/
				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());
		}

		class TreeNode
		{
			private TreeNode left, right;
			private int item;
			TreeNode(int item)
			{
				this.item = item;
			}
			internal static TreeNode bottomUpTree(int item, int depth)
			{
				
				return ChildTreeNodes(item, depth - 1);
			}
			static TreeNode ChildTreeNodes(int item, int depth)
			{
				var node = new TreeNode(item);
				if (depth > 0)
				{
					node.left = ChildTreeNodes(2 * item - 1, depth - 1);
					node.right = ChildTreeNodes(2 * item, depth - 1);
				}
				return node;
			}
			internal int itemCheck()
			{
				if (right == null) return item;
				else return item + left.itemCheck() - right.itemCheck();
			}
		}
	}
}