On 2007-12-14, Adam Shelly <adam.shelly / gmail.com> wrote:
> On 12/14/07, Rick DeNatale <rick.denatale / gmail.com> wrote:
>> On 12/14/07, Rob Biedenharn <Rob / agileconsultingllc.com> wrote:
>>
>> > I'll settle that.  Since your tests were equivalent, I went with
>> > Rick's since I saw it first:
>>
>
> I'm pinging Rick's last pong. But I am changing one of Ken's tests to
> agree with Paul - A tree with one node has height 1, and a tree with
> two or three has height 2.
Then its settled.

> (I think the zip file is a bad idea - I don't want to have to download
> each submission. I'm sticking with cut and paste).
Me too.

Here's my pong mister:

The lib:

#!/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.length).ceil
  end

  def remove(node)
  end

end

Test case:

#!/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

#disabled this test case as it is order dependent and not valid
# def test_tree_height_of_one_or_two_nodes_is_N
#   @tree << 5
#   assert_equal 1, @tree.height
#   @tree << 6
#   assert_equal 2, @tree.height     #changed from 1
# end


 def test_tree_height_of_three_nodes_should_be_greater_than_1
   @tree << 5
   @tree << 6
   @tree << 7
   assert(@tree.height > 1, "Tree appears to have stunted growth.")
 end

 def test_tree_growth_limit_is_1pt44_log_N
   (1..10).each{|i|
      @tree << i
      limit = (1.44 * Math::log(i)).ceil+1
      assert( @tree.height <= limit, "Tree of #{i} nodes is too tall
by #{@tree.height - limit}")
    }
 end

 def test_remove_node

   @tree << 314
   @tree.remove(314)
   assert(!@tree.include?(314))
 end

end



-- 
everything is simple, we're stupid
contact at gmail