require 'test/unit'
require 'binarytree'

class TestBinaryTree < Test::Unit::TestCase
  def setup
    @tree = BinaryTree.new
  end

  def test_mixins
    assert_kind_of(Enumerable, @tree, "BinaryTree should mix in Enumerable")
  end

  def test_balancing
    100.times do |i| @tree.add(i) end
    assert_equal(99, @tree.height)
    @tree.balance
    assert_equal(6, @tree.height)
  end

  def test_balancing_to_a
    100.times do |i| @tree.add(i) end
    arr = (0..99).to_a
    assert_equal(arr, @tree.to_a)
    @tree.balance
    assert_equal(arr, @tree.to_a)
  end
  
  def test_empty_tree
    assert_equal([], @tree.to_a)
    assert(@tree.empty?, "Initial tree should be empty.")
  end

  def test_size
    assert_equal(0, @tree.size)
    100.times do @tree.add(5) end
    assert_equal(1, @tree.size)
    (1..100).to_a.sort_by{rand}.each {|n| @tree.add(n)}
    assert_equal(100, @tree.size)
  end

  def test_uniqueness
    100.times do @tree.add(5) end
    assert_equal([5], @tree.to_a)
  end

  def test_max_min
    (1..100).to_a.sort_by{rand}.each {|n| @tree.add(n)}
    assert_equal(1, @tree.min)
    assert_equal(100, @tree.max)
  end

  def test_include
    (1..100).to_a.sort_by{rand}.each {|n| @tree.add(n)}
    test_num = rand(101)
    assert(@tree.include?(test_num), 
           "Expected the tree to include #{test_num}.")
  end

  def test_delete
    curr = Time.now.to_i
    @tree.add(root = Time.at(curr))
    @tree.add(Time.at(curr - 10))
    @tree.add(Time.at(curr + 10))
    @tree.add(Time.at(curr - 5))
    @tree.add(node1 = Time.at(curr + 5))
    @tree.add(Time.at(curr - 15))
    @tree.add(Time.at(curr + 15))
    @tree.add(leaf1 = Time.at(curr - 3))
    @tree.add(Time.at(curr + 3))
    @tree.add(Time.at(curr - 7))
    @tree.add(leaf2 = Time.at(curr + 7))
    @tree.add(Time.at(curr - 13))
    @tree.add(Time.at(curr + 13))
    @tree.add(Time.at(curr - 17))
    @tree.add(Time.at(curr + 17))
    
    assert_equal(3, @tree.height)
    
    assert_equal(leaf1.object_id,
                 @tree.delete(leaf1).object_id,
                 "Object ID of returned object not equal to deleted object!")
    assert(!@tree.include?(leaf1), "Tree should not include deleted item.")
    assert_equal(14, @tree.size)
    
    assert_equal(leaf2.object_id,
                 @tree.delete(leaf2).object_id,
                 "Object ID of returned object not equal to deleted object!")
    assert(!@tree.include?(leaf2), "Tree should not include deleted item.")
    assert_equal(13, @tree.size)
    
    assert_equal(node1.object_id,
                 @tree.delete(node1).object_id,
                 "Object ID of returned object not equal to deleted object!")
    assert(!@tree.include?(node1), "Tree should not include deleted item.")
    assert_equal(12, @tree.size)
    
    assert_equal(root.object_id,
                 @tree.delete(root).object_id,
                 "Object ID of returned object not equal to deleted object!")
    assert(!@tree.include?(root), "Tree should not include deleted item.")
    assert_equal(11, @tree.size)
    
    assert_equal(3, @tree.height)
  end

  def test_each
    (1..100).to_a.sort_by{rand}.each {|n| @tree.add(n)}
    ary = []
    @tree.each {|n| ary.push n}
    assert_equal(ary, (1..100).to_a, 
                 "The 'each' method is not implemented properly.")
  end
end