benchmarks_game/binary_trees.fz

# https://benchmarksgame-team.pages.debian.net/benchmarksgame/description/binarytrees.html#binarytrees
# based on the c program by Jeremy Zerfas
binary_trees is

  Node(left Node|unit, right Node|unit) ref is

  create_tree(depth i32) Node is
    if(depth > 0) then
      Node create_tree(depth - 1) create_tree( depth - 1)
    else
      Node Node(unit, unit) unit

  checksum(n Node) i32 is
    match n.left
      unit   => 1
      l Node =>
        match n.right
          unit   => 1
          r Node => (checksum(l) + checksum(r) + 1)

  min_depth := 4
  max_depth := 21
  stretch_tree := create_tree(max_depth+1)
  checksum := checksum(stretch_tree)
  say "stretch tree of depth {max_depth+1}\t check: $checksum"

  long_lived_tree := create_tree(max_depth)

  for depth in (min_depth..max_depth).filter(x -> x % 2 = 0) do
    iterations := (u64 1) << (max_depth - depth + min_depth).as_u64
    total_trees_checksum := mut 0

    for _ in ((u64 1)..iterations) do
      tree := create_tree(depth)
      total_trees_checksum <- total_trees_checksum.get + checksum(tree)

    say "$iterations\t trees of depth {depth}\t check: {total_trees_checksum.get}"

  say "long lived tree of depth $max_depth\t check: {checksum(long_lived_tree)}"