tests/shootout_binarytrees.nit

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