micro/tree.d

   1 // Written by Piotr Modzelewski <http://petermodzelewski.blogspot.com/>
   2 // Found at http://www.dsource.org/projects/tango/wiki/GCBenchmark
   3
   4 class TreeNode {
   5         int item;
   6         TreeNode left, right;
   7
   8         this(int item, TreeNode left=null, TreeNode right=null) {
   9                 this.item = item;
  10                 this.left = left;
  11                 this.right = right;
  12         }
  13
  14         int check() {
  15                 return left is null ? item : item + left.check - right.check;
  16         }
  17 }
  18
  19 TreeNode makeTree(int item, int depth) {
  20         if (depth > 0)
  21                 return new TreeNode(item, makeTree(2*item-1, depth-1),
  22                                 makeTree(2*item, depth-1));
  23         else
  24                 return new TreeNode(item);
  25 }
  26
  27 void main(char[][] args) {
  28         const minDepth = 4;
  29         int n = 6; // 13;
  30         int maxDepth = (minDepth + 2) > n ? minDepth + 2 : n;
  31
  32         int check = makeTree(0, maxDepth + 1).check;
  33
  34         auto longLivedTree = makeTree(0, maxDepth);
  35
  36         for (int depth = minDepth; depth <= maxDepth; depth += 2) {
  37                 int iterations = 1 << (maxDepth - depth + minDepth);
  38                 check = 0;
  39
  40                 for (int i = 1; i <= iterations; i++)
  41                         check += (makeTree(i, depth)).check
  42                                         + (makeTree(-i, depth)).check;
  43         }
  44
  45 }
  46