Eivind Eklund
12/14/2007 3:32:00 PM
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