Introduce a version of SunSpider that runs for a really long time (about 1 sec on...
[WebKit-https.git] / PerformanceTests / LongSpider / 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 = 0;
30
31 for ( var n = 4; n <= 16; 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 }
51
52 var expected = -13;
53 if (ret != expected)
54     throw "ERROR: bad result: expected " + expected + " but got " + ret;