From: "Eric I." <rubytraining@...>
Date: 2007-12-15T03:39:59+09:00
Subject: Re: Programmer Ping-Pong (#150)

avl_tree.rb
__BEGIN__
#!/usr/bin/env ruby -wKU
class AVLTree
  def initialize
    @contents = []
  end

  def empty?
    @contents.empty?
  end

  def include?(obj)
    @contents.include?(obj)
  end

  def <<(obj)
    @contents << obj
  end

  def height
    (Math.log(@contents.size + 1) / Math.log(2)).round
  end

  def to_a
  end
end
__END__

test_avl_tree.rb
__BEGIN__
#!/usr/bin/env ruby -wKU
require "test/unit"
require "avl_tree"
class TestAVLTree < Test::Unit::TestCase
  def setup
    @tree = AVLTree.new
  end

  def test_tree_membership
    assert_equal(true,  @tree.empty?)
    assert_equal(false, @tree.include?(3))
    @tree << 3
    assert_equal(false, @tree.empty?)
    assert_equal(true,  @tree.include?(3))
  end

  def test_tree_should_allow_more_than_one_element
    @tree << 3
    @tree << 4
    assert(@tree.include?(4))
    assert(@tree.include?(3))
  end

  def test_tree_height_of_one_node_is_one
    @tree << 5
    assert_equal 1, @tree.height
  end

  def test_tree_height_of_two_or_three_nodes_is_two
    @tree << 5
    @tree << 6
    assert_equal 2, @tree.height
    @tree << 3
    assert_equal 2, @tree.height
  end

  def test_tree_height_of_two_or_three_nodes_is_two
    @tree << 5
    @tree << 6
    assert_equal 2, @tree.height
    @tree << 3
    assert_equal 2, @tree.height
  end

  def test_to_a_returns_items_in_order
    @tree << 5
    @tree << 6
    @tree << 3

    assert_equal [3, 5, 6], @tree.to_a
  end

  # defunct tests no longer used

  def defunct_test_tree_height_of_one_or_two_nodes_is_one
    @tree << 5
    assert_equal 1, @tree.height
    @tree << 6
    assert_equal 1, @tree.height
  end

  def defunct_test_tree_height_of_three_nodes_is_two
    @tree << 5
    @tree << 6
    @tree << 7
    assert_equal 2, @tree.height
  end
end