Foo.jl

module Foo

export @timeof, @bench, BinaryTree, Node, Leaf, insert

macro timeof(expr)
         quote
           t1 = time()
           value = $(expr)
           t2 = time()
           t2-t1
         end
end

macro bench(expr,times)
         quote
           median([@timeof $(expr) for i=1:$(times)])
         end
end

abstract BinaryTree{T}

type Node{T} <: BinaryTree{T}
  left::Union(BinaryTree{T},Nothing)
  right
  data::T
end

type Leaf{T} <: BinaryTree{T}
  data::T
end

function getrootvalue{T}(tree::BinaryTree{T})
  return tree.data
end

function insert{T}(tree::Leaf{T},item::T)
  Node(tree,nothing,item)
end

function insert{T}(tree::Node{T},item::T)
  if tree.right == nothing
    return Node(tree.left, Leaf(item),tree.data)
  else
    return Node(tree,nothing,item)
  end
end

import Base.contains
function contains{T}(tree::Leaf{T},t::T)
  tree.data === t
end

function contains{T}(tree::Node{T},t::T)
  t == tree.data || contains(tree.left,t) || contains(tree.right,t)
end

contains(_::Nothing,_t) = false

function test1(x::Int64)
  t = Leaf(2)
  for i=1:x
   t = insert(t,i)
  end
  t
end 

#@show @bench sleep(0.3) 10
@show @bench test1(1000) 10
#@show @bench test1(1000000) 10

end