tests/bench_bintree_gen.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 class GenTreeNode[E]
  16         type SUBTREE: GenTreeNode[E]
  17         var left: nullable SUBTREE
  18         var right: nullable SUBTREE
  19         var item: E
  20
  21
  22         init(left: nullable SUBTREE, right: nullable SUBTREE, item: E)
  23         do
  24                 self.left = left
  25                 self.right = right
  26                 self.item = item
  27         end
  28 end
  29
  30 class TreeNode
  31         super GenTreeNode[Int]
  32         redef type SUBTREE: TreeNode
  33         fun item_check: Int
  34         do
  35                 if left == null then
  36                         return item
  37                 else
  38                         return item + left.item_check - right.item_check
  39                 end
  40         end
  41 end
  42
  43 fun bottom_up_tree(item: Int, depth: Int): TreeNode
  44 do
  45         if depth > 0 then
  46                 var item_item = 2 * item
  47                 depth = depth - 1
  48                 return new TreeNode(bottom_up_tree(item_item - 1, depth), bottom_up_tree(item_item, depth), item)
  49         else
  50                 return new TreeNode(null, null, item)
  51         end
  52 end
  53
  54 var max_depth = 4
  55 if not args.is_empty then
  56         max_depth = args.first.to_i
  57 end
  58 var min_depth = 4
  59
  60 if min_depth + 2 > max_depth then
  61         max_depth = min_depth + 2
  62 end
  63
  64 var stretch_depth = max_depth + 1
  65 var stretch_tree: nullable TreeNode = bottom_up_tree(0, stretch_depth)
  66
  67 print("stretch tree of depth {stretch_depth}\t check: {stretch_tree.item_check}")
  68
  69 stretch_tree = null
  70
  71 var long_lived_tree = bottom_up_tree(0, max_depth)
  72
  73 var depth = min_depth
  74 while depth <= max_depth do
  75         var iterations = 1 << (max_depth - depth + min_depth)
  76         var check_res = 0
  77
  78         for i in [1..(iterations+1)[ do
  79                 var temp_tree = bottom_up_tree(i, depth)
  80                 check_res = check_res + temp_tree.item_check
  81
  82                 temp_tree = bottom_up_tree(-i, depth)
  83                 check_res = check_res + temp_tree.item_check
  84         end
  85
  86         print("{iterations * 2}\t trees of depth {depth}\t check: {check_res}")
  87
  88         depth = depth + 2
  89 end
  90
  91 print("long lived tree of depth {max_depth}\t check: {long_lived_tree.item_check}")