Friday, September 14, 2007

Ruby: Array#collect_with_remaining

While looking through our core extensions I found the Array#collect_with_remaining method. The method was designed to yield each element with the other elements of an array and collect the results.

This method (wasn't, but) could be used to find duplicates within an Array*. I would suggest not using it for finding duplicates (since there are other easier ways), but the example should help in understanding what collect_with_remaining can do. If you wanted to implement Array#duplicates using collect_with_remaining you could write the following method.

class Array  
def duplicates
block = lambda { |element, remaining| element if remaining.include?(element) }
self.collect_with_remaining(&block).uniq.compact
end
end

The duplicates method shows that Array#collect_with_remaining yields each element and the remaining elements of the array, then collects the results. The result is a list of the duplicate values when the remaining did contain the element, and nil for each element that was not a duplicate. After the results have been returned the array is uniq(ed) and compact(ed) to remove the nil and duplicate entries. The result is all the duplicate values from the array. The following test verifies that the duplicates method works as expected.

unit_tests do
test "return duplicates" do
assert_equal [1, 3], [1, 2, 3, 1, 4, 3].duplicates
end
end

On to the actual collect_with_remaining implementation, right after we write the tests.

unit_tests do
test "head and tail are collected first" do
assert_equal [1, [2, 3]], [1, 2, 3].collect_with_remaining { |element, remaining| [element, remaining] }.first
end

test "elements and remaining elements are collected" do
expected = [[1, [2, 3]], [2, [1, 3]], [3, [1, 2]]]
assert_equal expected, [1, 2, 3].collect_with_remaining { |element, remaining| [element, remaining] }
end
end

The implementation I chose is straightforward, assuming you are comfortable with Enumerable#enum_with_index.

class Array
def collect_with_remaining
self.enum_with_index.inject([]) do |result, (element, index)|
remaining = self.dup
remaining.delete_at(index)
result << yield(element, remaining)
end
end
end

And, here's all the code if you're interested.

require 'enumerator'
require 'rubygems'
require 'test/unit'
require 'dust'

class Array
def collect_with_remaining
self.enum_with_index.inject([]) do |result, (element, index)|
remaining = self.dup
remaining.delete_at(index)
result << yield(element, remaining)
end
end

def duplicates
block = lambda { |element, remaining| element if remaining.include?(element) }
self.collect_with_remaining(&block).uniq.compact
end
end

unit_tests do
test "head and tail are collected first" do
assert_equal [1, [2, 3]], [1, 2, 3].collect_with_remaining { |element, remaining| [element, remaining] }.first
end

test "elements and remaining elements are collected" do
expected = [[1, [2, 3]], [2, [1, 3]], [3, [1, 2]]]
assert_equal expected, [1, 2, 3].collect_with_remaining { |element, remaining| [element, remaining] }
end

test "return duplicates" do
assert_equal [1, 3], [1, 2, 3, 1, 4, 3].duplicates
end
end

As always, please post alternate suggestions in comments, or better yet, blog them and leave a comment with the link.

* If I actually wanted to check for duplicates I would use Array#duplicates, which is defined in Facets.
Post a Comment