1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
/*
* The Computer Language Benchmarks Game
* http://shootout.alioth.debian.org/
*
* contributed by Jochen Hinrichsen
* modified by Marko Kocic
*/
final class TreeNode {
private final left, right, item
TreeNode(item) {
this.item = item
}
private static bottomUpTree(item, depth) {
if (depth > 0) {
return new TreeNode(
bottomUpTree(2*item-1, depth-1),
bottomUpTree(2*item, depth-1),
item
)
} else {
return new TreeNode(item)
}
}
TreeNode(left, right, item) {
this.left = left
this.right = right
this.item = item
}
private itemCheck() {
// if necessary deallocate here
if (left == null) return item
else return item + left.itemCheck() - right.itemCheck()
}
}
def n = (args.length == 0) ? 10 : args[0].toInteger()
def minDepth = 4
def maxDepth = [minDepth + 2, n].max()
def stretchDepth = maxDepth + 1
def check = (TreeNode.bottomUpTree(0, stretchDepth)).itemCheck()
println "stretch tree of depth ${stretchDepth}\t check: ${check}"
def longLivedTree = TreeNode.bottomUpTree(0, maxDepth)
def depth = minDepth
while (depth <= maxDepth) {
def iterations = 1 << (maxDepth - depth + minDepth)
check = 0
for (i in 1..iterations) {
check += (TreeNode.bottomUpTree(i, depth)).itemCheck()
check += (TreeNode.bottomUpTree(-i,depth)).itemCheck()
}
println "${iterations*2}\t trees of depth ${depth}\t check: ${check}"
depth += 2
}
println "long lived tree of depth ${maxDepth}\t check: ${longLivedTree.itemCheck()}"
|
