js/src/t/access-binary-trees.js

   1 /* The Great Computer Language Shootout
   2    http://shootout.alioth.debian.org/
   3    contributed by Isaac Gouy */
   4
   5 function TreeNode(left,right,item){
   6    this.left = left;
   7    this.right = right;
   8    this.item = item;
   9 }
  10
  11 TreeNode.prototype.itemCheck = function(){
  12    if (this.left==null) return this.item;
  13    else return this.item + this.left.itemCheck() - this.right.itemCheck();
  14 }
  15
  16 function bottomUpTree(item,depth){
  17    if (depth>0){
  18       return new TreeNode(
  19           bottomUpTree(2*item-1, depth-1)
  20          ,bottomUpTree(2*item, depth-1)
  21          ,item
  22       );
  23    }
  24    else {
  25       return new TreeNode(null,null,item);
  26    }
  27 }
  28
  29 var ret;
  30
  31 for ( var n = 4; n <= 7; n += 1 ) {
  32     var minDepth = 4;
  33     var maxDepth = Math.max(minDepth + 2, n);
  34     var stretchDepth = maxDepth + 1;
  35
  36     var check = bottomUpTree(0,stretchDepth).itemCheck();
  37
  38     var longLivedTree = bottomUpTree(0,maxDepth);
  39     for (var depth=minDepth; depth<=maxDepth; depth+=2){
  40         var iterations = 1 << (maxDepth - depth + minDepth);
  41
  42         check = 0;
  43         for (var i=1; i<=iterations; i++){
  44             check += bottomUpTree(i,depth).itemCheck();
  45             check += bottomUpTree(-i,depth).itemCheck();
  46         }
  47     }
  48
  49     ret = longLivedTree.itemCheck();
  50 }