benchmark/bench/binarytrees.groovy

/*
 * 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()}"