ruby : array structure equality

gistfile1.rb

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