micro/sbtree.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, fixed some stylistic issues)
   5
   6 import tango.util.Convert;
   7
   8 alias char[] string;
   9
  10 int main(string[] args)
  11 {
  12    int N = args.length > 1 ? to!(int)(args[1]) : 1;
  13
  14    int minDepth = 4;
  15    int maxDepth = (minDepth + 2) > N ? minDepth + 2 : N;
  16    int stretchDepth = maxDepth + 1;
  17
  18    int check = TreeNode.BottomUpTree(0, stretchDepth).ItemCheck;
  19    TreeNode longLivedTree = TreeNode.BottomUpTree(0, maxDepth);
  20
  21    for (int depth = minDepth; depth <= maxDepth; depth += 2) {
  22       int iterations = 1 << (maxDepth - depth + minDepth);
  23       check = 0;
  24
  25       for (int i = 1; i <= iterations; i++) {
  26          check += TreeNode.BottomUpTree(i, depth).ItemCheck;
  27          check += TreeNode.BottomUpTree(-i, depth).ItemCheck;
  28       }
  29
  30    }
  31
  32    return 0;
  33 }
  34
  35 class TreeNode
  36 {
  37    TreeNode left, right;
  38    int item;
  39
  40    this(int item, TreeNode left = null, TreeNode right = null)
  41    {
  42       this.item = item;
  43       this.left = left;
  44       this.right = right;
  45    }
  46
  47    static TreeNode BottomUpTree(int item, int depth)
  48    {
  49       if (depth > 0)
  50          return new TreeNode(item,
  51                BottomUpTree(2 * item - 1, depth - 1),
  52                BottomUpTree(2 * item, depth - 1));
  53       return new TreeNode(item);
  54    }
  55
  56    int ItemCheck()
  57    {
  58       if (left)
  59          return item + left.ItemCheck() - right.ItemCheck();
  60       return item;
  61    }
  62 }
  63