Skip to content

Instantly share code, notes, and snippets.

@mccraigmccraig
Created July 1, 2009 13:27
Show Gist options
  • Save mccraigmccraig/138776 to your computer and use it in GitHub Desktop.
Save mccraigmccraig/138776 to your computer and use it in GitHub Desktop.
ruby : array structure equality
class Array
class Val
attr_reader :i
def initialize(i)
@i = i
end
def eql?(other)
other.is_a?(Val) && @i==other.i
end
end
class EqlContext
attr_reader :i_left
attr_reader :left_id_vals
attr_reader :i_right
attr_reader :right_id_vals
def initialize
@i_left = -1
@left_id_vals = {}
@i_right = -1
@right_id_vals = {}
end
# returns true if both l and r have been seen before
def see(l,r)
seen = @left_id_vals.has_key?(l.object_id) && @right_id_vals.has_key?(r.object_id)
left(l)
right(r)
seen
end
def compare(l,r)
left(l).eql?(right(r))
end
def left(o)
@left_id_vals[o.object_id] || (@i_left += 1 ; @left_id_vals[o.object_id] = Val.new(@i_left))
end
def right(o)
@right_id_vals[o.object_id] || (@i_right += 1 ; @right_id_vals[o.object_id] = Val.new(@i_right) )
end
end
class << self
def with_eql_context
if !Thread.current[:eql_context]
begin
yield( Thread.current[:eql_context] = EqlContext.new )
ensure
Thread.current[:eql_context] = nil
end
else
yield( Thread.current[:eql_context] )
end
end
end
def eql?(other)
Array.with_eql_context do |ctx|
return false if !other.is_a? Array
return false if length != other.length
each_index do |i|
return false if !ctx.see(self[i], other[i]) && !self[i].eql?(other[i])
return false if !ctx.compare(self[i], other[i])
end
true
end
end
end
require 'test/unit'
include Test::Unit::Assertions
a=[] ; b=[] ; c=[]
a << b ; b << c ; c << a
aa=[] ; ab=[] ; ac=[]
aa << ab ; ab << ac ; ac << aa
assert(a.eql?(aa))
a=[] ; b=[] ; c=[] ; d=[]
a << b ; b << c ; c << d ; d << a
aa=[] ; ab=[] ; ac=[]
aa << ab ; ab << ac ; ac << aa
assert(!a.eql?(aa))
a=[1,2] ; b=[4,5]
a << b ; b << a
aa=[1,2] ; ab=[4,5]
aa << ab ; ab << aa
assert(a.eql?(aa))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment