1 # This file is part of NIT ( http://www.nitlanguage.org ).
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
7 # http://www.apache.org/licenses/LICENSE-2.0
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.
16 type SUBTREE: GenTreeNode[E
]
17 var left
: nullable SUBTREE
18 var right
: nullable SUBTREE
22 init(left
: nullable SUBTREE, right
: nullable SUBTREE, item
: E
)
31 super GenTreeNode[Int]
32 redef type SUBTREE: TreeNode
38 return item
+ left
.item_check
- right
.item_check
43 fun bottom_up_tree
(item
: Int, depth
: Int): TreeNode
46 var item_item
= 2 * item
48 return new TreeNode(bottom_up_tree
(item_item
- 1, depth
), bottom_up_tree
(item_item
, depth
), item
)
50 return new TreeNode(null, null, item
)
55 if not args
.is_empty
then
56 max_depth
= args
.first
.to_i
60 if min_depth
+ 2 > max_depth
then
61 max_depth
= min_depth
+ 2
64 var stretch_depth
= max_depth
+ 1
65 var stretch_tree
: nullable TreeNode = bottom_up_tree
(0, stretch_depth
)
67 print
("stretch tree of depth {stretch_depth}\t check: {stretch_tree.item_check}")
71 var long_lived_tree
= bottom_up_tree
(0, max_depth
)
74 while depth
<= max_depth
do
75 var iterations
= 1 << (max_depth
- depth
+ min_depth
)
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
82 temp_tree
= bottom_up_tree
(-i
, depth
)
83 check_res
= check_res
+ temp_tree
.item_check
86 print
("{iterations * 2}\t trees of depth {depth}\t check: {check_res}")
91 print
("long lived tree of depth {max_depth}\t check: {long_lived_tree.item_check}")