binary-trees Dart program
source code
/* The Computer Language Benchmarks game
http://benchmarksgame.alioth.debian.org/
contributed by Jos Hirth, transliterated from Jarkko Miettinen's Java program
*reset*
*/
final int minDepth = 4;
void main(args){
int n = args.length > 0 ? int.parse(args[0]) : 0;
int maxDepth = (minDepth + 2 > n) ? minDepth + 2 : n;
int stretchDepth = maxDepth + 1;
int check = (TreeNode.bottomUpTree(stretchDepth)).itemCheck();
print("stretch tree of depth $stretchDepth\t check: $check");
TreeNode longLivedTree = TreeNode.bottomUpTree(maxDepth);
for (int depth = minDepth; depth <= maxDepth; depth += 2){
int iterations = 1 << (maxDepth - depth + minDepth);
check = 0;
for (int i = 1; i <= iterations; i++){
check += (TreeNode.bottomUpTree(depth)).itemCheck();
}
print("${iterations}\t trees of depth $depth\t check: $check");
}
print("long lived tree of depth $maxDepth\t check: ${longLivedTree.itemCheck()}");
}
class TreeNode{
TreeNode left, right;
TreeNode([this.left, this.right]);
static TreeNode bottomUpTree(int depth){
if (depth > 0){
return new TreeNode(
bottomUpTree(depth - 1),
bottomUpTree(depth - 1)
);
}
return new TreeNode();
}
int itemCheck(){
if (left == null){
return 1;
}
return 1 + left.itemCheck() + right.itemCheck();
}
}
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
Dart VM version: 1.24.2 (Thu Jun 22 08:43:26 2017) on "linux_x64"
Thu, 26 Oct 2017 21:01:16 GMT
MAKE:
make: 'binarytrees.dart_run' is up to date.
0.01s to complete and log all make actions
COMMAND LINE:
/opt/src/dartsdk-linux-x64-release/dart-sdk/bin/dart binarytrees.dart 21
PROGRAM OUTPUT:
stretch tree of depth 22 check: 8388607
2097152 trees of depth 4 check: 65011712
524288 trees of depth 6 check: 66584576
131072 trees of depth 8 check: 66977792
32768 trees of depth 10 check: 67076096
8192 trees of depth 12 check: 67100672
2048 trees of depth 14 check: 67106816
512 trees of depth 16 check: 67108352
128 trees of depth 18 check: 67108736
32 trees of depth 20 check: 67108832
long lived tree of depth 21 check: 4194303