michael@0: /* The Great Computer Language Shootout
michael@0:    http://shootout.alioth.debian.org/
michael@0:    contributed by Isaac Gouy */
michael@0: 
michael@0: function TreeNode(left,right,item){
michael@0:    this.left = left;
michael@0:    this.right = right;
michael@0:    this.item = item;
michael@0: }
michael@0: 
michael@0: TreeNode.prototype.itemCheck = function(){
michael@0:    if (this.left==null) return this.item;
michael@0:    else return this.item + this.left.itemCheck() - this.right.itemCheck();
michael@0: }
michael@0: 
michael@0: function bottomUpTree(item,depth){
michael@0:    if (depth>0){
michael@0:       return new TreeNode(
michael@0:           bottomUpTree(2*item-1, depth-1)
michael@0:          ,bottomUpTree(2*item, depth-1)
michael@0:          ,item
michael@0:       );
michael@0:    }
michael@0:    else {
michael@0:       return new TreeNode(null,null,item);
michael@0:    }
michael@0: }
michael@0: 
michael@0: var ret;
michael@0: 
michael@0: /* BEGIN LOOP */
michael@0: for ( var n = 4; n <= 7; n += 1 ) {
michael@0:     var minDepth = 4;
michael@0:     var maxDepth = Math.max(minDepth + 2, n);
michael@0:     var stretchDepth = maxDepth + 1;
michael@0:     
michael@0:     var check = bottomUpTree(0,stretchDepth).itemCheck();
michael@0:     
michael@0:     var longLivedTree = bottomUpTree(0,maxDepth);
michael@0:     /* BEGIN LOOP */
michael@0:     for (var depth=minDepth; depth<=maxDepth; depth+=2){
michael@0:         var iterations = 1 << (maxDepth - depth + minDepth);
michael@0: 
michael@0:         check = 0;
michael@0:         /* BEGIN LOOP */
michael@0:         for (var i=1; i<=iterations; i++){
michael@0:             check += bottomUpTree(i,depth).itemCheck();
michael@0:             check += bottomUpTree(-i,depth).itemCheck();
michael@0:         }
michael@0:         /* END LOOP */
michael@0:     }
michael@0:     /* END LOOP */
michael@0: 
michael@0:     ret = longLivedTree.itemCheck();
michael@0: }
michael@0: /* END LOOP */