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
|
/*
The Computer Language Shootout
http://shootout.alioth.debian.org/
- tree: disjoint union type
- loop: "for" loop over iterator range
Contributed by Kannan Goundan
De-optimized by Isaac Gouy
*/
object binarytrees {
abstract class Tree;
case class Node(i: Int, left: Tree, right: Tree) extends Tree
case class Empty() extends Tree
def check(tree: Tree) : Int = tree match {
case Node(i, left, right) => i + check(left) - check(right)
case Empty() => 0
}
def make(i: Int, depth: Int) : Tree = depth match {
/* case 0 => Empty() */
case 0 => Node(i, Empty(), Empty())
case _ => Node(i, make((2*i)-1, depth-1), make(2*i, depth-1))
}
def main(args: Array[String]) = {
val n = try { Integer.parseInt(args(0)) } catch { case _ => 1 }
val minDepth = 4
val maxDepth = Math.max(minDepth+2, n)
print("stretch tree", maxDepth+1, check(make(0, maxDepth+1)))
val longLived = make(0, maxDepth)
for (val depth <- Iterator.range(minDepth, maxDepth+1, 2)) {
val iterations = 1 << (maxDepth - depth + minDepth)
var sum = 0
for (val i <- Iterator.range(1, iterations+1))
sum = sum + check(make(i, depth)) + check(make(-i, depth))
print(iterations*2 + "\t trees", depth, sum)
}
print("long lived tree", maxDepth, check(longLived))
}
def print(name: String, depth: Int, check: Int) =
Console.println(name + " of depth " + depth + "\t check: " + check)
}
|
