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

James Koppel

12/19/2007 2:24:00 AM

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...

comp.lang.ruby

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

James Koppel

x Login to ForumsZone