The Computer Language
Benchmarks Game

binary-trees TypeScript program

source code

/* The Computer Language Benchmarks Game
   http://benchmarksgame.alioth.debian.org/
   contributed by Isaac Gouy 
*/

/// <reference path="/usr/local/src/typescript/node.d.ts" />


class TreeNode {

   constructor(
      private left: TreeNode, 
      private right: TreeNode, 
      private item: number
   ) { }

   check(): number {
      if (this.left) {
         return this.item + this.left.check() - this.right.check()
      }
      else {
         return this.item
      }
   }

   static bottomUpTree(item: number, depth: number): TreeNode {
      if (depth > 0) {
         // "new TreeNode(" must be on same line as "return" 
         return new TreeNode(
               TreeNode.bottomUpTree(2*item-1, depth-1),
               TreeNode.bottomUpTree(2*item, depth-1),
               item
            )
      }
      else {
         return new TreeNode(undefined,undefined,item)
      }
   }
}


const n = +process.argv[2]
const minDepth = 4
const maxDepth = n
const stretchDepth = n + 1

let check = TreeNode.bottomUpTree(0,stretchDepth).check()
console.log("stretch tree of depth " + stretchDepth + "\t check: " + check)

const longLivedTree = TreeNode.bottomUpTree(0,maxDepth)
for (let depth=minDepth; depth<=maxDepth; depth+=2) {
   let iterations = 1 << (maxDepth - depth + minDepth)

   check = 0;
   for (let i=1; i<=iterations; i++) {
      check += TreeNode.bottomUpTree(i,depth).check()
      check += TreeNode.bottomUpTree(-i,depth).check()
   }
   console.log(iterations*2 + "\t trees of depth " + depth + "\t check: " + check)
}
console.log("long lived tree of depth " + maxDepth + "\t check: " + longLivedTree.check())

    

notes, command-line, and program output

NOTES:
32-bit Ubuntu one core
Version 2.0.3
node.js v6.9.0


Wed, 19 Oct 2016 19:11:05 GMT

MAKE:
mv binarytrees.typescript binarytrees.ts
/usr/local/src/node-v6.9.0-linux-x86/bin/tsc -t ES2015 binarytrees.ts
../../../../../usr/local/src/typescript/node.d.ts(393,11): error TS2430: Interface 'NodeBuffer' incorrectly extends interface 'Uint8Array'.
  Types of property 'fill' are incompatible.
    Type '(value: any, offset?: number, end?: number) => Buffer' is not assignable to type '(value: number, start?: number, end?: number) => this'.
      Type 'Buffer' is not assignable to type 'this'.
/home/dunham/benchmarksgame/nanobench/makefiles/u32.programs.Makefile:601: recipe for target 'binarytrees.typescript_run' failed
make: [binarytrees.typescript_run] Error 2 (ignored)
/usr/local/src/node-v6.3.0-linux-x86/lib/node_modules/babel-cli/bin/babel.js --plugins transform-es2015-modules-commonjs binarytrees.js -o binarytrees.js
make: /usr/local/src/node-v6.3.0-linux-x86/lib/node_modules/babel-cli/bin/babel.js: Command not found
/home/dunham/benchmarksgame/nanobench/makefiles/u32.programs.Makefile:601: recipe for target 'binarytrees.typescript_run' failed
make: [binarytrees.typescript_run] Error 127 (ignored)
2.95s to complete and log all make actions

COMMAND LINE:
/usr/local/src/node-v6.9.0-linux-x86/bin/node --use_strict binarytrees.js 20

PROGRAM OUTPUT:
stretch tree of depth 21	 check: -1
2097152	 trees of depth 4	 check: -2097152
524288	 trees of depth 6	 check: -524288
131072	 trees of depth 8	 check: -131072
32768	 trees of depth 10	 check: -32768
8192	 trees of depth 12	 check: -8192
2048	 trees of depth 14	 check: -2048
512	 trees of depth 16	 check: -512
128	 trees of depth 18	 check: -128
32	 trees of depth 20	 check: -32
long lived tree of depth 20	 check: -1