Asp Forum - Re: [QUIZ] Programmer Ping-Pong (#150

James Koppel

12/19/2007 3:35:00 AM

I just realized that it might be a good idea to change my test to make each accept an options hash rather than ordered arguments, since my change and my new test will cause each to accept two keyword arguments. That is, rather than having calls like

@tree.each(:postorder,:node){...}

having something along the lines of

@ree.each(:traversal=>:postorder,:val=>:node)

----- Original Message ----
From: James Koppel <jamesbkoppel@yahoo.com>
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Sent: Tuesday, December 18, 2007 8:23:35 PM
Subject: Re: [QUIZ] Programmer Ping-Pong (#150)

On 12/18/07, Adam Shelly wrote:
>I added test_remove_multiple_nodes - there are definitely a few
>mistakes in the current remove :)

Seems the only mistake was that remove was expecting AVLTree#each to
return the node traversed, but it was instead returning the node's data.
I modified each to accept the name of a function to be passed to
itself, which defaults to data. I made an "identity" method called node, and
the passed it in when each is called within remove.

For my test, each and to_a must now accept symbols denoting the type of
traversal to be performed, including inorder (the current traversal),
preorder, postorder, and level-by-level.

==>avl_tree.rb<==
class AVLTree

include Enumerable

# Need something smarter than nil for external nodes
class ExternalNode
attr_accessor :parent
def initialize(parent)
@parent = parent
end
def include?(_) false end
def <<(_) raise RuntimeError end
def height; 0 end
def balance_factor; 0 end
def left; self end
def right; self end
def each(*args,&iter) end
def left=(node)
raise(NotImplementedError,
"external node of #{@parent}")
end
def right=(node)
raise(NotImplementedError,
"external node of #{@parent}")
end
def to_s; '' end
def to_a; [] end
end

class Node
attr_accessor :data, :parent
attr_reader :left, :right

def initialize obj, sortblock
@parent = nil
@data = obj
@left = ExternalNode.new(self)
@right = ExternalNode.new(self)
@height = 1
@compare = sortblock
end

def left=(node)
@height = nil
@left = node
node.parent = self
end

def right=(node)
@height = nil
@right = node
node.parent = self
end

def each(returns=:data,&iter)
@left.each(&iter)
iter[self.send(returns)]
@right.each(&iter)
end

def node
self
end

def height
@height || ( [ @left.height, @right.height ].max + 1)
end

def << node
case @compare[node.data,@data]
when -1
if Node === @left
@left << node
else
self.left = node
end
when 0
return self # no dups
when +1
if Node === @right
@right << node
else
self.right = node
end
end
rebalance if balance_factor.abs > 1
@height = nil
end

def remove obj
@height = nil
case @compare[obj,@data]
when -1
if Node === @left
@left.remove(obj)
else
nil
end
when 0
if Node === @left
largest = nil
AVLTree.new(@left).each(:node) do |n|
largest = n if largest.nil? or n.data > largest.data
largest = n if largest.nil? or n.data > largest.data
end
self.data = largest.data
self.left = largest.left
elsif Node === @right
smallest = nil
AVLTree.new(@right).each(:node) do |n|
smallest = n if smallest.nil? or n.data < smallest.data
smallest = n if smallest.nil? or n.data < smallest.data
end
self.data = smallest.data
self.right = smallest.right
else
parent.send :replace_child, self, ExternalNode.new(parent)
end
path = self
while Node === (path = path.parent)
path.rebalance if path.balance_factor.abs > 1
end
self
when +1
if Node === @right
@right.remove(obj)
else
nil
end
end
end

def include? obj
case obj <=> @data
when -1 : @left.include?(obj)
when 0 : true
when +1 : @right.include?(obj)
end
end

def to_a
result = @left.to_a
result << @data
result.concat @right.to_a
result
end

def [](idx)
if idx < (leftheight = @left.height)
@left[idx]
elsif (idx== leftheight)
@data
elsif (idx-=(leftheight+1)) < @right.height
@right[idx]
end
end

def to_s
bf = case balance_factor <=> 0
when -1 : '-' * -balance_factor
when 0 : '.'
when 1 : '+' * balance_factor
end
"[#{left} "+
"(#{@data}{#{height}#{bf}}^#{parent.data})"+
" #{right}]"
end

protected

def balance_factor
@right.height - @left.height
end

def rotate_left
my_parent, from, to = @parent, self, @right
temp = @right.left
@right.left = self
self.right = temp
my_parent.send :replace_child, from, to
to.parent = my_parent
end

def rotate_right
my_parent, from, to = @parent, self, @left
temp = @left.right
@left.right = self
self.left = temp
my_parent.send :replace_child, from, to
to.parent = my_parent
end

def rebalance
if (bf = balance_factor) > 1 # right is too high
if @right.balance_factor < 0
# double rotate right-left
# - first the right subtree
@right.rotate_right
end
rotate_left # single rotate left
elsif bf < -1 # left must be too high
if @left.balance_factor > 0
# double rotate left-right
# - first force left subtree
@left.rotate_left
end
rotate_right # single rotate right
end
end

def replace_child(from, to)
if from.eql? @left
@left = to
elsif from.eql? @right
@right = to
else
raise(ArgumentError,
"#{from} is not a branch of #{self}")
end
end

end

def initialize(root = nil, &block)
@root = root
if block
raise(ArgumentError,
"Block argument for #{self.class.name} must" +
" take 2 arguments and act as sort function"
) unless block.arity == 2
else
block = proc{|a,b| a<=>b}
end
@compare = block
end

def empty?
@root.nil?
end

def include?(obj)
empty? ? false : @root.include?(obj)
end

def <<(obj)
raise(ArgumentError,
"Objects added to #{self.class.name} must" +
" respond to <=>"
) unless obj.respond_to?(:<=>)

if empty?
@root = Node.new(obj, @compare)
@root.parent = self
else
@root << Node.new(obj, @compare)
end
self
end

def remove(obj)
@root.remove(obj) unless empty?
end

def height
empty? ? 0 : @root.height
end

def [](idx)
@root[idx]
end

def to_a
empty? ? [] : @root.to_a
end

def each(*args,&iter)
@root.each(*args,&iter) unless empty?
end

def to_s
empty? ? "[]" : @root.to_s
end

# Indicates that parent is root in to_s
def data; '*'; end

protected

def replace_child(from, to)
if @root.eql? from
@root = to
else
raise(ArgumentError,
"#{from} is not a branch of #{self}")
end
end

end
_END_

==>test_avl_tree.rb<==

require "test/unit"
require "avl_tree"

class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

##################################################
# Membership tests
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), "4 not in #{@tree}")
assert(@tree.include?(3), "3 not in #{@tree}")
end

def test_tree_include_many
0.upto(10) do |i|
assert_equal(false, @tree.include?(i),
"Tree should not include #{i} yet.")
@tree << i
0.upto(i) do |j|
assert_equal(true, @tree.include?(j),
"Tree should have 0..#{i},"+
" where's #{j}? ")
end
end
end

# This sits at the intersection of membership
# and height tests. We know one node has height 1,
# and two nodes has height 2, so if we insert one
# object twice and the height is 1, there must
# only be one node in the tree.
def test_tree_does_not_keep_duplicates
@tree << 'a'
@tree << 'a'
assert_equal 1, @tree.height, "one node: #{@tree}"
end

##################################################
# Height tests
def test_tree_height_of_one_or_two_nodes_is_N
@tree << 5
assert_equal 1, @tree.height, "one node: #{@tree}"
@tree << 6
assert_equal 2, @tree.height, "two nodes: #{@tree}"
end

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

# RobB: The more precise limit given in [Knuth] is
# used rather than that from [Wikipedia]
def test_tree_growth_limit_is_1pt44_log_N
(1..10).each do |i|
@tree << i
limit = ((1.4405 *
Math::log(i+2.0)/Math::log(2.0)
) - 0.3277).ceil
assert(@tree.height <= limit,
"Tree of #{i} nodes is too tall by" +
" #{@tree.height - limit}" +
" #{@tree}")
end
end

def test_balances_left
4.downto(1) { |i| @tree << i }
assert(@tree.height < 4,
"expected tree height #{@tree.height} < 4")
end

def test_balances_right
1.upto(4) { |i| @tree << i }
assert(@tree.height < 4,
"expected tree height #{@tree.height} < 4")
end

def test_non_sequential_insertion__part_1
items = [ 1, 3, 2 ]
items.each do |i|
@tree << i
end
items.each do |i|
assert_equal(true, @tree.include?(i),
"where is #{i}? ")
end
end

def test_non_sequential_insertion__part_2
items = [ 3, 1, 2 ]
items.each do |i|
@tree << i
end
items.each do |i|
assert_equal(true, @tree.include?(i),
"where is #{i}? ")
end
end

##################################################
# Access tests (getting data back out)

# RobB: this tests too much at one time; I sorted ary.
def test_tree_traverse
ary = [ 3, 5, 17, 30, 42, 54, 1, 2 ].sort

ary.each { |n| @tree << n }
traversal = []
@tree.each { |n| traversal << n }

assert_equal(ary.size, traversal.size)

ary.each do |n|
assert_equal(true, traversal.include?(n),
"#{n} was not visited in tree.")
end
end

def test_alternate_traversals
items = [3,2,4,1,5]
items.each {|el| @tree << el}

preorder_result = [3,2,1,4,5]
assert_equal(@tree.to_a(:preorder),preorder_result)
@tree.each(:preorder) {|el| assert_equal(preorder_result.shift,el)}

inorder_result = [1,2,3,4,5]
assert_equal(@tree.to_a(:inorder),inorder_result)
@tree.each(:inorder) {|el| assert_equal(inorder_result.shift,el)}

postorder_result = [1,2,5,4,3]
assert_equal(@tree.to_a(:postorder),postorder_result)
@tree.each(:postorder) {|el|
assert_equal(postorder_result.shift,el)}

bylevel_result = [3,2,4,1,5]
assert_equal(@tree.to_a(:by_level),bylevel_result)
@tree.each(:by_level) {|el| assert_equal(bylevel_result.shift,el)}
end

def test_tree_find
[1,2,3,4].each{|n| @tree<<n}
assert_equal(1, @tree.find{|v|v>0} )
assert_equal(2, @tree.find{|v|v%2==0} )
end

def test_sequential_access
items = [ 50, 17, 72 ]
items.each { |n| @tree << n }
items.sort.each_with_index do |e,i|
assert_equal(e, @tree[i],
"@tree[#{i}] should be like " +
"#{items.inspect}.sort[#{i}]")
end
end

# [Knuth] p.473: "The problem of deletion can be solved
# in O(log N) steps if we approach it correctly."
def test_remove_node
@tree << 314
@tree.remove(314)
assert_equal(false, @tree.include?(314),
'314 still in the tree')
end

def test_remove_multiple_nodes
items = [ 50, 17, 72, 45, 43, 23 ]
items.each { |n| @tree << n }
puts @tree, @tree.height
@tree.remove(50)
assert_equal(false, @tree.include?(50),
'50 still in the tree')
@tree.remove(72)
assert_equal(false, @tree.include?(72),
'72 still in the tree')
@tree.remove(45)
assert_equal(false, @tree.include?(45),
'45 still in the tree')
assert_equal(2, @tree.height) #tree should have 3 items, height =
2
end

##################################################
# Interface tests

def test_custom_comparison_code
rev_tree = AVLTree.new { |a, b| b <=> a }
values = [3, 2, 1]
values.each { |v| rev_tree << v }
rev_tree.each { |v| assert_equal(values.shift, v) }

len_tree = AVLTree.new { |a, b| a.length <=> b.length }
values = %w[3 22 111]
values.each { |v| len_tree << v }
len_tree.each { |v| assert_equal(values.shift, v) }
end

end
_END_

____________________________________________________________________________________
Never miss a thing. Make Yahoo your home page.
http://www.yaho...

____________________________________________________________________________________
Be a better friend, newshound, and
know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypa...

2 Answers

Adam Shelly

12/20/2007 1:02:00 AM

On 12/18/07, James Koppel <jamesbkoppel@yahoo.com> wrote:
> I just realized that it might be a good idea to change my test to make each accept an options hash rather than ordered arguments, since my change and my new test will cause each to accept two keyword arguments. That is, rather than having calls like
>
> @tree.each(:postorder,:node){...}
>
> having something along the lines of
>
> @ree.each(:traversal=>:postorder,:val=>:node)
>
> ----- Original Message ----
> From: James Koppel <jamesbkoppel@yahoo.com>
> To: ruby-talk ML <ruby-talk@ruby-lang.org>
> Sent: Tuesday, December 18, 2007 8:23:35 PM
> Subject: Re: [QUIZ] Programmer Ping-Pong (#150)
>
>
> On 12/18/07, Adam Shelly wrote:
> >I added test_remove_multiple_nodes - there are definitely a few
> >mistakes in the current remove :)
>
> Seems the only mistake was that remove was expecting AVLTree#each to
> return the node traversed, but it was instead returning the node's data.
> I modified each to accept the name of a function to be passed to
> itself, which defaults to data. I made an "identity" method called node, and
> the passed it in when each is called within remove.
>
> For my test, each and to_a must now accept symbols denoting the type of
> traversal to be performed, including inorder (the current traversal),
> preorder, postorder, and level-by-level.
>

Ok, I did the each and the to_a. I did not add the hash as suggested
- I don't think it's a good idea to provide tree users with nodes
directly. And I refactored remove so that it didn't need each(:node)
anyway. I expanded my previous test_remove_multiple_nodes test to
help ensure the refactoring was robust.
It was also bugging me that we were creating so many ExternalNodes
where we didn't care about the data, only the methods, so I moved all
the methods to the class, and removed all the calls to new (I just
realized I should have made new private)

My new test lets you add and subtract trees.

-Adam

==> avl_tree.rb <==
class AVLTree

include Enumerable

# Need something smarter than nil for external nodes
# but we dont need all these separate instances - they are all identical
class ExternalNode
def self::include?(_) false end
def self::height; 0 end
def self::each(*args,&iter) end
def self::each_level(sequence,&iter)
sequence.shift.each_level(sequence,&iter) unless sequence.empty?
end
def self::each_node(&iter) end
def self::to_a(_); [] end
def self::pop; nil end
def self::shift; nil end
def self::parent=(p); nil end
def self::to_s; ''; end
end

class Node
attr_accessor :data, :parent
attr_reader :left, :right

def initialize obj, sortblock
@parent = nil
@data = obj
@left = ExternalNode
@right = ExternalNode
@height = 1
@compare = sortblock
end

def left=(node)
@height = nil
@left = node
node.parent = self
end

def right=(node)
@height = nil
@right = node
node.parent = self
end

def each(traversal, &iter)
case traversal
when :inorder
@left.each(traversal,&iter)
iter[@data]
@right.each(traversal,&iter)
when :preorder
iter[@data]
@left.each(traversal,&iter)
@right.each(traversal,&iter)
when :postorder
@left.each(traversal,&iter)
@right.each(traversal,&iter)
iter[@data]
end
end

def each_level sequence,&iter
iter[@data]
sequence.push @left
sequence.push @right
sequence.shift.each_level(sequence,&iter) unless sequence.empty?
end

def each_node &iter
@left.each_node(&iter)
iter[self]
@right.each_node(&iter)
end

def height
@height || ( [ @left.height, @right.height ].max + 1)
end

def << node
case @compare[node.data,@data]
when -1
if Node === @left
@left << node
else
self.left = node
end
when 0
return self # no dups
when +1
if Node === @right
@right << node
else
self.right = node
end
end
rebalance if balance_factor.abs > 1
@height = nil
end

def remove obj
case @compare[obj,@data]
when -1
@left.remove(obj)
when 0
path = @left.pop || @right.shift || drop_self
self.data = path.data
while Node === (path = path.parent)
break if path.balance_factor.abs == 1
path.rebalance
end
self
when +1
@right.remove(obj)
end
end

def drop_self
parent.send :replace_child, self, ExternalNode#.new(parent)
self
end

def pop
@right.pop || drop_self
end

def shift
@left.shift || drop_self
end

def include? obj
case obj <=> @data
when -1 : @left.include?(obj)
when 0 : true
when +1 : @right.include?(obj)
end
end

def to_a traversal
left,root,right = @left.to_a(traversal), [@data], @right.to_a(traversal)
case traversal
when :inorder
left+root+right
when :preorder
root+left+right
when :postorder
left+right+root
when :by_level
# pad out the left array so zip gets all the right elements too
while (left.size < right.size) do left<<nil end
[root]+left.zip(right).map{|set| set.flatten}
end
end

def [](idx)
if idx < (leftheight = @left.height)
@left[idx]
elsif (idx== leftheight)
@data
elsif (idx-=(leftheight+1)) < @right.height
@right[idx]
end
end

def to_s
bf = case balance_factor <=> 0
when -1 : '-' * -balance_factor
when 0 : '.'
when 1 : '+' * balance_factor
end
"[#{left} "+
"(#{@data}{#{height}#{bf}}^#{parent.data})"+
" #{right}]"
end

protected

def balance_factor
@right.height - @left.height
end

def rotate_left
my_parent, from, to = @parent, self, @right
temp = @right.left
@right.left = self
self.right = temp
my_parent.send :replace_child, from, to
to.parent = my_parent
end

def rotate_right
my_parent, from, to = @parent, self, @left
temp = @left.right
@left.right = self
self.left = temp
my_parent.send :replace_child, from, to
to.parent = my_parent
end

def rebalance
if (bf = balance_factor) > 1 # right is too high
if @right.balance_factor < 0
# double rotate right-left
# - first the right subtree
@right.rotate_right
end
rotate_left # single rotate left
elsif bf < -1 # left must be too high
if @left.balance_factor > 0
# double rotate left-right
# - first force left subtree
@left.rotate_left
end
rotate_right # single rotate right
end
end

def replace_child(from, to)
if from.eql? @left
@left = to
elsif from.eql? @right
@right = to
else
raise(ArgumentError,
"#{from} is not a branch of #{self}")
end
end

end

def initialize(root = ExternalNode, &block)
@root = root
if block
raise(ArgumentError,
"Block argument for #{self.class.name} must" +
" take 2 arguments and act as sort function"
) unless block.arity == 2
else
block = proc{|a,b| a<=>b}
end
@compare = block
end

def empty?
@root == ExternalNode
end

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

def <<(obj)
raise(ArgumentError,
"Objects added to #{self.class.name} must" +
" respond to <=> (#{obj.inspect})"
) unless obj.respond_to?(:<=>)

if empty?
@root = Node.new(obj, @compare)
@root.parent = self
else
@root << Node.new(obj, @compare)
end
self
end

def remove(obj)
@root.remove(obj).data
end

def height
@root.height
end

def [](idx)
@root[idx]
end

def to_a( traversal=:inorder )
@root.to_a(traversal).flatten.compact
end

def each(traversal=:inorder,&iter)
if traversal==:by_level
@root.each_level([],&iter)
else
@root.each(traversal,&iter)
end
end

def to_s
empty? ? "[]" : @root.to_s
end

# Indicates that parent is root in to_s
def data; '*'; end

protected

def replace_child(from, to)
if @root.eql? from
@root = to
else
raise(ArgumentError,
"#{from} is not a branch of #{self}")
end
end

end
__END__

==> test_avl_tree.rb <==
#!/usr/bin/env ruby -wKU
require "test/unit"
require "avl_tree"

class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

##################################################
# Membership tests
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), "4 not in #{@tree}")
assert(@tree.include?(3), "3 not in #{@tree}")
end

def test_tree_include_many
0.upto(10) do |i|
assert_equal(false, @tree.include?(i),
"Tree should not include #{i} yet.")
@tree << i
0.upto(i) do |j|
assert_equal(true, @tree.include?(j),
"Tree should have 0..#{i},"+
" where's #{j}? ")
end
end
end

# This sits at the intersection of membership
# and height tests. We know one node has height 1,
# and two nodes has height 2, so if we insert one
# object twice and the height is 1, there must
# only be one node in the tree.
def test_tree_does_not_keep_duplicates
@tree << 'a'
@tree << 'a'
assert_equal 1, @tree.height, "one node: #{@tree}"
end

##################################################
# Height tests
def test_tree_height_of_one_or_two_nodes_is_N
@tree << 5
assert_equal 1, @tree.height, "one node: #{@tree}"
@tree << 6
assert_equal 2, @tree.height, "two nodes: #{@tree}"
end

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

# RobB: The more precise limit given in [Knuth] is
# used rather than that from [Wikipedia]
def test_tree_growth_limit_is_1pt44_log_N
(1..10).each do |i|
@tree << i
limit = ((1.4405 *
Math::log(i+2.0)/Math::log(2.0)
) - 0.3277).ceil
assert(@tree.height <= limit,
"Tree of #{i} nodes is too tall by" +
" #{@tree.height - limit}" +
" #{@tree}")
end
end

def test_balances_left
4.downto(1) { |i| @tree << i }
assert(@tree.height < 4,
"expected tree height #{@tree.height} < 4")
end

def test_balances_right
1.upto(4) { |i| @tree << i }
assert(@tree.height < 4,
"expected tree height #{@tree.height} < 4")
end

def test_non_sequential_insertion__part_1
items = [ 1, 3, 2 ]
items.each do |i|
@tree << i
end
items.each do |i|
assert_equal(true, @tree.include?(i),
"where is #{i}? ")
end
end

def test_non_sequential_insertion__part_2
items = [ 3, 1, 2 ]
items.each do |i|
@tree << i
end
items.each do |i|
assert_equal(true, @tree.include?(i),
"where is #{i}? ")
end
end

##################################################
# Access tests (getting data back out)

# RobB: this tests too much at one time; I sorted ary.
def test_tree_traverse
ary = [ 3, 5, 17, 30, 42, 54, 1, 2 ].sort

ary.each { |n| @tree << n }
traversal = []
@tree.each { |n| traversal << n }

assert_equal(ary.size, traversal.size)

ary.each do |n|
assert_equal(true, traversal.include?(n),
"#{n} was not visited in tree.")
end
end

def test_alternate_traversals
items = [3,2,4,1,5]
items.each {|el| @tree << el}

preorder_result = [3,2,1,4,5]
assert_equal(preorder_result,@tree.to_a(:preorder))
@tree.each(:preorder) {|el| assert_equal(preorder_result.shift,el)}

inorder_result = [1,2,3,4,5]
assert_equal(inorder_result,@tree.to_a(:inorder))
@tree.each(:inorder) {|el| assert_equal(inorder_result.shift,el)}

postorder_result = [1,2,5,4,3]
assert_equal(postorder_result,@tree.to_a(:postorder))
@tree.each(:postorder) {|el|
assert_equal(postorder_result.shift,el)}

bylevel_result = [3,2,4,1,5]
assert_equal(bylevel_result,@tree.to_a(:by_level))
@tree.each(:by_level) {|el| assert_equal(bylevel_result.shift,el)}
end

def test_tree_find
[1,2,3,4].each{|n| @tree<<n}
assert_equal(1, @tree.find{|v|v>0} )
assert_equal(2, @tree.find{|v|v%2==0} )
assert_equal([2,4], @tree.find_all{|v|v%2==0} )
end

def test_sequential_access
items = [ 50, 17, 72 ]
items.each { |n| @tree << n }
items.sort.each_with_index do |e,i|
assert_equal(e, @tree[i],
"@tree[#{i}] should be like " +
"#{items.inspect}.sort[#{i}]")
end
end

# [Knuth] p.473: "The problem of deletion can be solved
# in O(log N) steps if we approach it correctly."
def test_remove_node
@tree << 314
@tree.remove(314)
assert_equal(false, @tree.include?(314),
'314 still in the tree')
end

def test_remove_multiple_nodes
#expanded to test rebalancing better
items=[35, 79, 68, 49, 5, 50, 24, 71,
66, 81, 41, 1, 37, 20, 95, 62]
items.each { |n| @tree << n }
items.size.times do
togo = items.shift
@tree.remove(togo)
assert_equal(false, @tree.include?(togo),
'#{togo} still in the tree')
items.each{|i| assert_equal(true, @tree.include?(i),
"tree should still include #{i}")
}
end
assert_equal true, @tree.empty?
@tree<<2
assert_equal true, @tree.include?(2)
end

def test_tree_merge
[1,2,3,4].each{|v| @tree << v}
tree2 = AVLTree.new
[2,4,6,8].each{|v| tree2<<v}
mergedTree = @tree+tree2
assert_equal([1,2,3,4,6,8], mergedTree.to_a)
assert_equal([1,3], (mergedTree-tree2).to_a)
end

##################################################
# Interface tests

def test_custom_comparison_code
rev_tree = AVLTree.new { |a, b| b <=> a }
values = [3, 2, 1]
values.each { |v| rev_tree << v }
rev_tree.each { |v| assert_equal(values.shift, v) }

len_tree = AVLTree.new { |a, b| a.length <=> b.length }
values = %w[3 22 111]
values.each { |v| len_tree << v }
len_tree.each { |v| assert_equal(values.shift, v) }
end

end
=begin
[Knuth] Knuth, Donald Ervin,
The Art of Computer Programming, 2nd ed.
Volume 3, Sorting and Searching,
section 6.2.3 "Balanced Trees", pp. 458-478
[Wikipedia]
AVL Tree, http://en.wikipedia.org/wik...
=end
__END__

James Gray

12/20/2007 1:36:00 PM

On Dec 19, 2007, at 7:01 PM, Adam Shelly wrote:

> It was also bugging me that we were creating so many ExternalNodes
> where we didn't care about the data, only the methods, so I moved all
> the methods to the class, and removed all the calls to new (I just
> realized I should have made new private)

Maybe it should be a singleton. As it is, we could switch it to a
module now too.

James Edward Gray II

comp.lang.ruby

Re: [QUIZ] Programmer Ping-Pong (#150

James Koppel

Adam Shelly

James Gray

x Login to ForumsZone