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
|
# -*- nim -*-
import os, strutils
type
PNode = ref TNode
TNode {.final, acyclic.} = object
left, right: PNode
item: int
proc checkTree(node: PNode): int =
result = node.item
if node.left != nil:
inc result, checkTree(node.left) - checkTree(node.right)
proc makeTreeAux(item, depth: int): PNode =
new(result)
result.item = item
if depth > 0:
result.left = makeTreeAux(2 * item - 1, depth - 1)
result.right = makeTreeAux(2 * item, depth - 1)
proc makeTree(item, depth: int): PNode =
#GC_disable()
result = makeTreeAux(item, depth)
#GC_enable()
proc main =
var n = parseInt(paramStr(1))
const minDepth = 4
var maxDepth = if minDepth+2 > n: minDepth+2 else: n
var stretchDepth = maxDepth + 1
echo("stretch tree of depth ", stretchDepth, "\t check: ", checkTree(
makeTree(0, stretchDepth)))
var longLivedTree = makeTree(0, maxDepth)
var iterations = 1 shl maxDepth
for depth in countup (minDepth, stretchDepth-1, 2):
var check = 0
for i in 1..iterations:
check += checkTree(makeTree(i, depth)) + checkTree(makeTree(-i, depth))
echo(iterations*2, "\t trees of depth ", depth, "\t check: ", check)
iterations = iterations div 4
echo("long lived tree of depth ", maxDepth, "\t check: ",
longLivedTree.checkTree)
echo GC_getstatistics()
main()
|