Own class with spaceship operator does not work for LCS Diff

Question

I'm trying to implement a custom class including the comparable mixin. Later the class is used to do a diff. The class looks like

class Element
  include Comparable
  attr_reader :name

  def initialize(name)
    @name = name
  end

  def <=>(other)
    @name <=> other.name
  end
end

Now some test values with two added entries compared to a.

a = Array.new
b = Array.new

a.push Element.new('y1')
a.push Element.new('y2')
a.push Element.new('y4')
a.push Element.new('x1')
a.push Element.new('x2')
a.push Element.new('x4')

b.push Element.new('y1')
b.push Element.new('y2')
b.push Element.new('y3')
b.push Element.new('y4')
b.push Element.new('x1')
b.push Element.new('x2')
b.push Element.new('x3')
b.push Element.new('x4')

And now run diff between both arrays

puts Diff::LCS.diff(a, b).inspect

I would expect two added objects now but it finds 8 changes... Any ideas why?

[[["-", 2, #<Element:0x007fa9fb567898 @name="y4">],
  ["-", 3, #<Element:0x007fa9fbc69830 @name="x1">],
  ["-", 4, #<Element:0x007fa9fbca3378 @name="x2">],
  ["+", 2, #<Element:0x007fa9fb5e5e78 @name="y3">],
  ["+", 3, #<Element:0x007fa9fb606920 @name="y4">],
  ["+", 4, #<Element:0x007fa9fb625848 @name="x1">],
  ["+", 5, #<Element:0x007fa9fb647da8 @name="x2">],
  ["+", 6, #<Element:0x007fa9fbde8670 @name="x3">]]]

If we run the test with

a = Array.new
b = Array.new

a.push 'y1'
a.push 'y2'
a.push 'y4'
a.push 'x1'
a.push 'x2'
a.push 'x4'

b.push 'y1'
b.push 'y2'
b.push 'y3'
b.push 'y4'
b.push 'x1'
b.push 'x2'
b.push 'x3'
b.push 'x4'

Everything works as expected:

[[["+", 2, "y3"]],
 [["+", 6, "x3"]]]

Answer 1

Inspecting from source of Diff::LCS, the elements in sequences are used as hash key.

The Element class you wrote mixed the Comparable module, it got the == method there. However, it doesn't have eql? and hash method override, which is used by the Hash to determine the key comparison.

With you Element class, we have

irb(main):013:0> a = Element.new("a")
=> #<Element:0x002ae4ce402da0 @name="a">
irb(main):014:0> b = Element.new("a")
=> #<Element:0x002ae4ce409ec0 @name="a">
irb(main):015:0> a == b
=> true
irb(main):016:0> a.eql? b
=> false
irb(main):017:0> a.hash == b.hash
=> false
irb(main):018:0> h = {}
=> {}
irb(main):019:0> h[a] = 1
=> 1
irb(main):020:0> h[b]
=> nil

This affects the LCS calculation.

The fix is to add the eql? and hash method for the Element class, I think.

class Element
  include Comparable
  attr_reader :name

  def initialize(name)
    @name = name
  end

  def <=>(other)
    @name <=> other.name
  end

  def eql? other
    other.class == Element and self.name == other.name
  end

  def hash
    @name.hash ^ Element.hash
  end
end