|
#!/usr/bin/env ruby
|
|
$VERBOSE = true
|
|
|
|
class Tree
|
|
def initialize
|
|
@root = nil
|
|
end
|
|
# if this is enabled -- recovery is instantaneous
|
|
# def wutwut
|
|
# raise NoMethodError.new('wutwut') # does not trigger issue
|
|
# #whutwhut # without raise above, this triggers issue
|
|
# #raise 'huh?' # direct raise does not trigger issue
|
|
# end
|
|
def add(i_key,i_val)
|
|
if @root
|
|
@root.add(i_key,i_val)
|
|
|
|
if @root.right_weight - @root.left_weight >= 2
|
|
t_new_root = @root.right
|
|
rl = @root.right.left
|
|
@root.right.left = @root
|
|
@root = t_new_root
|
|
@root.left.right = rl
|
|
|
|
@root.left&.calc_weight
|
|
@root.right&.calc_weight
|
|
@root.calc_weight
|
|
|
|
elsif @root.right_weight - @root.left_weight <= -2
|
|
raise 'should not happen for this testcase'
|
|
end
|
|
else
|
|
@root = Node.new(i_key,i_val)
|
|
end
|
|
self
|
|
end
|
|
end
|
|
|
|
class Node
|
|
attr_accessor :key, :value
|
|
attr_accessor :left, :right, :back, :fore
|
|
attr_accessor :weight
|
|
def initialize(i_key,i_val)
|
|
@key = i_key
|
|
@value = i_val
|
|
@left = nil
|
|
@right = nil
|
|
@weight = 1
|
|
@back = nil
|
|
@fore = nil
|
|
end
|
|
def add(i_key,i_val)
|
|
if i_key < key
|
|
raise 'should not happen for this testcase'
|
|
elsif i_key >= key
|
|
if @right
|
|
@right.add(i_key,i_val)
|
|
if @right.right_weight - @right.left_weight >= 2
|
|
t_new_right = @right.right
|
|
rl = @right.right.left
|
|
@right.right.left = @right
|
|
@right = t_new_right
|
|
@right.left.right = rl
|
|
|
|
@right.left&.calc_weight
|
|
@right.right&.calc_weight
|
|
@right.calc_weight
|
|
end
|
|
else
|
|
@right = Node.new(i_key,i_val)
|
|
t_fore = fore
|
|
@fore = @right
|
|
@right.back = self
|
|
@right.fore = t_fore
|
|
t_fore&.back = @right
|
|
end
|
|
end
|
|
|
|
calc_weight
|
|
nil
|
|
end
|
|
def calc_weight
|
|
@weight =
|
|
[@left&.weight,@right&.weight].
|
|
find_all { |v| !v.nil? }.
|
|
max.
|
|
then { |v| v.nil? ? 1 : v + 1 }
|
|
self
|
|
end
|
|
def left_weight
|
|
(@left&.weight)||0
|
|
end
|
|
def right_weight
|
|
(@right&.weight)||0
|
|
end
|
|
end
|
|
|
|
|
|
###############################################################################
|
|
t_tree = Tree.new
|
|
(1..100).each { |k| t_tree.add(k,k*10) }
|
|
puts 'invoking NoMethodError'
|
|
#begin
|
|
t_tree.wutwut # NoMethodError -- VM goes crazy deallocating (?)
|
|
#rescue NoMethodError
|
|
#rescue Exception # capturing and NOT re-raising avoids issue
|
|
# raise
|
|
#end
|
|
|