micro/shootout_binarytrees.d

   1 // Written by Andrey Khropov <andkhropov_nosp@m_mtu-net.ru>
   2 // Found at http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=43991
   3 // Modified by Leandro Lucarella
   4 // (ported to Tango)
   5
   6 import tango.io.Stdout;
   7 import tango.util.Convert;
   8
   9 alias char[] string;
  10
  11 int main(string[] args)
  12 {
  13         int N = args.length > 1 ? to!(int)(args[1]) : 1;
  14
  15         int minDepth = 4;
  16         int maxDepth = (minDepth + 2) > N ? minDepth + 2 : N;
  17         int stretchDepth = maxDepth + 1;
  18
  19         TreeNode stretchTree = TreeNode.BottomUpTree(0, stretchDepth);
  20         //Stdout("stretch tree of depth ")(stretchDepth)("\t check: ")
  21         //              (stretchTree.ItemCheck);
  22
  23         TreeNode longLivedTree = TreeNode.BottomUpTree(0, maxDepth);
  24
  25         int depth;
  26         for(depth = minDepth; depth <= maxDepth; depth += 2)
  27         {
  28                 int check, iterations = 1 << (maxDepth - depth + minDepth);
  29
  30                 for(int i = 1; i <= iterations; i++)
  31                 {
  32                         auto tempTree = TreeNode.BottomUpTree(i, depth);
  33                         check += tempTree.ItemCheck;
  34                         //delete tempTree;
  35
  36                         tempTree = TreeNode.BottomUpTree(-i, depth);
  37                         check += tempTree.ItemCheck;
  38                         //delete tempTree;
  39                 }
  40
  41                 //Stdout(iterations * 2)("\t trees of depth ")(depth)
  42                 //              ("\t check: ")(check);
  43         }
  44
  45         //Stdout("long lived tree of depth ")(maxDepth)("\t check: ")
  46         //              (longLivedTree.ItemCheck);
  47
  48         return 0;
  49 }
  50
  51 class TreeNode
  52 {
  53 public:
  54         this(int item, TreeNode left = null, TreeNode right = null)
  55         {
  56                 this.item  = item;
  57                 this.left  = left;
  58                 this.right = right;
  59         }
  60
  61         static TreeNode BottomUpTree(int item, int depth)
  62         {
  63                 if(depth > 0)
  64                         return new TreeNode(item
  65                                         ,BottomUpTree(2 * item - 1, depth - 1)
  66                                         ,BottomUpTree(2 * item, depth - 1));
  67                 return new TreeNode(item);
  68         }
  69
  70         int ItemCheck()
  71         {
  72                 if(left)
  73                         return item + left.ItemCheck() - right.ItemCheck();
  74                 return item;
  75         }
  76 private:
  77         TreeNode            left, right;
  78         int                 item;
  79 }
  80