I ended up responding to Paul because it looked like a later
submission (and response to the first pong).

On Dec 14, 2007 4:00 PM, Paul Irofti <bulibuta / fakehost.net> wrote:
> On 2007-12-14, Ruby Quiz <james / grayproductions.net> wrote:
> [--snip--]
> >       The Serve
> The Pong
>
> > The initial contents of avl_tree.rb are:
> The altered contents of avl_tree.rb are:
>
> #!/usr/bin/env ruby -wKU
>
> class AVLTree
>   attr_accessor :head
>   def initialize
>     @head = nil
>   end
>   def empty?
>     @head.nil?
>   end
>   def << (thing)
>     @head = thing if empty?
>   end
>   def include?(value)
>     @head == value
>   end
> end
>
> > The test file, test_avl_tree.rb, begins as:
> The test file was altered as:
>
> #!/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_insertion
>     assert_equal(true, @tree.empty?)
>     assert_equal(false, @tree.include?(3))
>     assert_equal(false, @tree.include?(5))
>
>     @tree << 3
>     @tree << 5
>
>     assert_equal(false, @tree.empty?)
>     assert_equal(true, @tree.include?(5))
>     assert_equal(true, @tree.include?(3))
>   end
> end
>
> Hope this follows the rules as the insertion is not actually implemented
> nor is the include?. But I guess in less than 20 lines that's the best a
> `Pong' can do (-:

Here's a ping (or is that now a poing?)

Note that I've joined up the test and tree files using the customary
$0 == __FILE__ hack, to make participation as simple as cut/pasting to
a single file.  You run the tests by "ruby avltree.rb" (or
./avltree.rb if you change modes), and use the library by "require
'avltree'".  The require will NOT run the tests.


#!/usr/bin/env ruby -wKU

class AVLTree
  attr_accessor :head, :left
  def initialize
    @head = nil
    @left = nil
  end
  def empty?
    @head.nil?
  end
  def << (thing)
    if empty?
      @head = thing
    else
      @left = AVLTree.new
      @left << thing
    end
  end
  def include?(value)
    @head == value || (@left != nil && @left.include?(value))
  end
end

if $0 == __FILE__
  require "test/unit"

  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_insertion
      assert_equal(true, @tree.empty?)
      assert_equal(false, @tree.include?(3))
      assert_equal(false, @tree.include?(5))

      @tree << 3
      @tree << 5

      assert_equal(false, @tree.empty?)
      assert_equal(true, @tree.include?(5))
      assert_equal(true, @tree.include?(3))
    end

    def test_tree_include_many
      0.upto(10) do |i|
        assert(false, @tree.include?(i))
        @tree << i
        0.upto(i) do |j|
          assert(true, @tree.include?(j))
        end
      end
    end
  end
end