Ruby array intersection

Question

Two arrays containing objects, is not returning intersect when using '&' between the arrays. Please take a look at the snippet below:

ruby-1.9.2-p290 :001 > class A
ruby-1.9.2-p290 :002?>   include Comparable
ruby-1.9.2-p290 :003?>   attr_reader :key
ruby-1.9.2-p290 :004?>   def initialize(key)
ruby-1.9.2-p290 :005?>     @key = key
ruby-1.9.2-p290 :006?>     end
ruby-1.9.2-p290 :007?>   def <=> obj
ruby-1.9.2-p290 :008?>     @key <=> obj.key
ruby-1.9.2-p290 :009?>     end
ruby-1.9.2-p290 :010?>   end
 => nil 
ruby-1.9.2-p290 :011 > class B
ruby-1.9.2-p290 :012?>   attr_reader :key
ruby-1.9.2-p290 :013?>   def initialize(key)
ruby-1.9.2-p290 :014?>     @key = key
ruby-1.9.2-p290 :015?>     end
ruby-1.9.2-p290 :016?>   end
 => nil 
ruby-1.9.2-p290 :017 > A.new(1) == A.new(1)
 => true 
ruby-1.9.2-p290 :019 > B.new(1) == B.new(1)
 => false 
ruby-1.9.2-p290 :020 > a1 = [A.new(1), A.new(2), A.new(3)]
 => [#<A:0x000001009e2f68 @key=1>, #<A:0x000001009e2f40 @key=2>, #<A:0x000001009e2f18 @key=3>] 
ruby-1.9.2-p290 :021 > a2 = [A.new(3), A.new(4), A.new(5)]
 => [#<A:0x000001009d44e0 @key=3>, #<A:0x000001009d44b8 @key=4>, #<A:0x000001009d4490 @key=5>] 
ruby-1.9.2-p290 :023 > a1 | a2
 => [#<A:0x000001009e2f68 @key=1>, #<A:0x000001009e2f40 @key=2>, #<A:0x000001009e2f18 @key=3>, #<A:0x000001009d44e0 @key=3>, #<A:0x000001009d44b8 @key=4>, #<A:0x000001009d4490 @key=5>] 
ruby-1.9.2-p290 :024 > a1 & a2
 => []

shouldn't a1 & a2 return:

[#<A:0x000001009e2f18 @key=3>]

or, I am just missing something...

Mon ouïe · Accepted Answer · 2011-10-12 17:34:37Z

9

No, you need to implement hash equality for Array#& and Array#| to work (implementing it only with normal comparisons would be O(n * m)). Notice Array#| returned the wrong result too: it includes duplicates.

Such equality method can be implemented this way :

 def hash
   @key.hash ^ A.hash # just to get a different hash than the key
 end

 alias eql? ==

Also, your <=> fails if the other object doesn't respond to #key. == should not fail, it should return false if the two objects can't be compared. It's also one of those methods where you don't want to use respond_to?, but rather is_a? : you don't want a film to be equal to a book because they happen to have the same title.

def <=>(other)
  @key <=> other.key if other.is_a? A
end

answered Oct 12, 2011 at 17:34

Mon ouïe

9585 silver badges6 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Mohammad Khan Over a year ago

Thanks for helping to me figure this out... Do we need a XOR in #hash, since I am comparing two A by it's #key. I think, we can keep only @key.hash

Mon ouïe Over a year ago

It would work, because eql? will be called anyway. The xor is just there to avoid collisions with the hash's key. Even def hash; 1; end would work, but performance would be awful.

Collectives™ on Stack Overflow

Ruby array intersection

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related