#* http://shootout.alioth.debian.org/u32/benchmark.php?test=binarytrees&lang=all
  Binary trees benchmark
*#

item_check = { left, item, right |
  null? (left)
    { item }
    { item + (item_check(left[0], left[1], left[2]) - item_check(right[0], right[1], right[2])) }
}

bottom_up_tree = { item, depth |
  false? depth > 0
    { [null, item, null] }
    {
      item_item = 2 * item 
      depth = depth - 1
      [bottom_up_tree(item_item - 1, depth), item, bottom_up_tree(item_item, depth)]
    }
}

max_depth = 10
min_depth = 4

true? min_depth + 2 > max_depth
  { max_depth = min_depth + 2 }

stretch_depth = max_depth + 1
stretch_tree = bottom_up_tree 0, stretch_depth

p "stretch tree of depth #{stretch_depth}\t check: #{item_check(stretch_tree[0], stretch_tree[1], stretch_tree[2])}"
stretch_tree = null

long_lived_tree = bottom_up_tree 0, max_depth

depth = min_depth
while { depth < max_depth + 1 }
  {
    iterations = 2 ^ (max_depth - depth + min_depth)
  
    check = 0
    1.to iterations, { i |
      temp_tree = bottom_up_tree(i, depth)
      check = check + item_check(temp_tree[0], temp_tree[1], temp_tree[2])

      temp_tree = bottom_up_tree(-i, depth)
      check = check + item_check(temp_tree[0], temp_tree[1], temp_tree[2])
    }
    
    p "#{iterations * 2}\t trees of depth #{depth}\t check: #{check}"

    depth = depth + 2
  }

p "long lived tree of depth #{max_depth}\t check: #{item_check(long_lived_tree[0], long_lived_tree[1], long_lived_tree[2])}"