1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2005-2008 Jean Privat <jean@pryen.org>
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
9 # http://www.apache.org/licenses/LICENSE-2.0
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.
17 # The Comptuer Language Shootout Benchmarks
18 # http://shootout.alioth.debian.org
20 # contributed by Jean Privat
23 var _left
: nullable TreeNode
24 var _right
: nullable TreeNode
28 init(left
: nullable TreeNode, right
: nullable TreeNode, item
: Int)
41 return _item
+ _left
.item_check
- _right
.item_check
46 fun bottom_up_tree
(item
: Int, depth
: Int): TreeNode
49 var item_item
= 2 * item
51 return new TreeNode(bottom_up_tree
(item_item
- 1, depth
), bottom_up_tree
(item_item
, depth
), item
)
53 return new TreeNode(null, null, item
)
58 if not args
.is_empty
then
59 max_depth
= args
.first
.to_i
63 if min_depth
+ 2 > max_depth
then
64 max_depth
= min_depth
+ 2
67 var stretch_depth
= max_depth
+ 1
68 var stretch_tree
: nullable TreeNode = bottom_up_tree
(0, stretch_depth
)
70 print
("stretch tree of depth {stretch_depth}\t check: {stretch_tree.item_check}")
74 var long_lived_tree
= bottom_up_tree
(0, max_depth
)
77 while depth
<= max_depth
do
78 var iterations
= 1.lshift
(max_depth
- depth
+ min_depth
)
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
85 temp_tree
= bottom_up_tree
(-i
, depth
)
86 check_res
= check_res
+ temp_tree
.item_check
89 print
("{iterations * 2}\t trees of depth {depth}\t check: {check_res}")
94 print
("long lived tree of depth {max_depth}\t check: {long_lived_tree.item_check}")