The Computer Language
24.04 Benchmarks Game

binary-trees Toit program

source code

/* The Computer Language Benchmarks game
   https://salsa.debian.org/benchmarksgame-team/benchmarksgame/

   transliterated from Antoine Pitrou's Python program by Isaac Gouy  
*/  

class Tree:  
  left /Tree? := ?
  right /Tree? := ?
  
  constructor .left .right:  
  
  static with depth/int -> Tree:
    if depth == 0: return Tree null null
    depth -= 1
    return Tree (Tree.with depth) (Tree.with depth)
  
  node-count -> int:
    if not this.left: return 1
    return 1 + this.left.node-count + this.right.node-count
    
main args:
  n := args.size == 1 ? int.parse args[0] : 0
  min-depth := 4
  max-depth := max (min-depth + 2) n
  stretch-depth := max-depth + 1  
  
  print "stretch tree of depth $stretch-depth\t "
      + "check: $((Tree.with stretch-depth).node-count)"     
       
  long-lived-tree := Tree.with max-depth
  
  for depth := min-depth; depth <= max-depth; depth += 2: 
    iterations := 1 << max-depth - depth + min-depth  
    check := 0    
    iterations.repeat: check += (Tree.with depth).node-count     
    print "$iterations\t trees of depth $depth\t check: $check"        
  
  print "long lived tree of depth $max-depth\t "
      + "check: $(long-lived-tree.node-count)"

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
v2.0.0-alpha.146



 Wed, 24 Apr 2024 21:12:55 GMT

MAKE:
cp -r Include/toit/.packages .
cp -r Include/toit/package.lock .
cp -r Include/toit/package.yaml .	
/opt/src/toit/bin/toit.compile -O2 --strip -o binarytrees.toit_run binarytrees.toit 

1.03s to complete and log all make actions

COMMAND LINE:
 ./binarytrees.toit_run 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