source/blog/posts/2010/08/14-memory-allocation/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)
   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         TreeNode stretchTree = TreeNode.BottomUpTree(0, stretchDepth);
  19
  20         TreeNode longLivedTree = TreeNode.BottomUpTree(0, maxDepth);
  21
  22         int depth;
  23         for(depth = minDepth; depth <= maxDepth; depth += 2)
  24         {
  25                 int check, iterations = 1 << (maxDepth - depth + minDepth);
  26
  27                 for(int i = 1; i <= iterations; i++)
  28                 {
  29                         auto tempTree = TreeNode.BottomUpTree(i, depth);
  30                         check += tempTree.ItemCheck;
  31                         //delete tempTree;
  32
  33                         tempTree = TreeNode.BottomUpTree(-i, depth);
  34                         check += tempTree.ItemCheck;
  35                         //delete tempTree;
  36                 }
  37
  38         }
  39
  40         return 0;
  41 }
  42
  43 class TreeNode
  44 {
  45 public:
  46         this(int item, TreeNode left = null, TreeNode right = null)
  47         {
  48                 this.item  = item;
  49                 this.left  = left;
  50                 this.right = right;
  51         }
  52
  53         static TreeNode BottomUpTree(int item, int depth)
  54         {
  55                 if(depth > 0)
  56                         return new TreeNode(item
  57                                         ,BottomUpTree(2 * item - 1, depth - 1)
  58                                         ,BottomUpTree(2 * item, depth - 1));
  59                 return new TreeNode(item);
  60         }
  61
  62         int ItemCheck()
  63         {
  64                 if(left)
  65                         return item + left.ItemCheck() - right.ItemCheck();
  66                 return item;
  67         }
  68 private:
  69         TreeNode            left, right;
  70         int                 item;
  71 }
  72