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

tree_node = new
tree_node.init = { left, data, right |
  my.left = left
  my.right = right
  my.data = data
}

item_check = { node |
  null? (node.left)
    { node.data }
    { node.data + (item_check(node.left) - item_check(node.right)) }
}

bottom_up_tree = { data, depth |
  false? depth > 0
    { tree_node.new null, data, null }
    {
      data_item = 2 * data
      depth = depth - 1
      tree_node.new bottom_up_tree(data_item - 1, depth), data, bottom_up_tree(data_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)}"
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)

      temp_tree = bottom_up_tree(-i, depth)
      check = check + item_check(temp_tree)
    }
    
    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)}"