Last active
January 3, 2016 05:49
-
-
Save brett-richardson/8418608 to your computer and use it in GitHub Desktop.
Combined Lazy Enumerator in Ruby 1.9
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# The aim of this class is to take a number of ordered enumerators and then | |
# emit their values in ascending order. | |
# | |
# Some assumptions: | |
# * The enumerators passed in emit their values in ascending order. | |
# * The enumerators emit values which are Comparable[1] with each other. | |
# * The enumerators can be finite *or* infinite. | |
# | |
# This requires Ruby 1.9. The Enumerator[2] documentation might be useful. | |
# | |
# [1] http://www.ruby-doc.org/core-1.9.3/Comparable.html | |
# [2] http://www.ruby-doc.org/core-1.9.3/Enumerator.html | |
# | |
# This is a stub implementation that causes failures in in the test suite, but | |
# no errors. | |
# | |
# You can run the test suite with: `ruby combined_enumerator_test.rb`. | |
class CombinedOrderedEnumerator < Enumerator | |
class UnorderedEnumerator < RuntimeError | |
attr_accessor :enumerator | |
def initialize( enum ) | |
@enumerator = enum | |
end | |
end | |
attr_accessor :last_value | |
def initialize( *args ) | |
@enums = args.map do |e| # Insure each item is enumerable | |
if e.kind_of? Enumerator then e else e.to_enum end | |
end | |
@values = [] | |
fill_values | |
super() do |yielder| | |
yielder.yield self.next while any? | |
end | |
end | |
def next | |
greater_than_previous! *pop_lowest_value_with_index | |
end | |
def any? | |
fill_values | |
@values.compact.any? | |
end | |
#----------------------------------------------------------------------------- | |
protected | |
#----------------------------------------------------------------------------- | |
# Ensure we have an array with the next item from each enum waiting to be "popped" | |
def fill_values | |
@enums.each_with_index do |e, i| | |
@values[i] ||= e.next rescue StopIteration | |
end | |
end | |
# Ensure the value here is greater than the previous one (assuming neither are nil) | |
# by throwing an UnorderedEnumerator error | |
def greater_than_previous!( val, index ) | |
if @last_value && @last_value > val | |
raise UnorderedEnumerator.new @enums[index] | |
end | |
@last_value = val | |
end | |
# Pop the lowest item from @values (with its index) and then refill the value array | |
def pop_lowest_value_with_index | |
lowest = @values.compact.min | |
index = @values.find_index{ |v| v == lowest } | |
@values[index] = nil if index | |
return lowest, index | |
end | |
end | |
#= Tests ======================================================================= | |
if $0 == __FILE__ | |
require 'minitest/autorun' | |
require 'minitest/pride' | |
class CombinedOrderedEnumeratorTest < MiniTest::Unit::TestCase | |
def test_enumerating_nothing | |
enumerator = CombinedOrderedEnumerator.new() | |
assert_equal [], enumerator.take(10) | |
end | |
def test_enumerating_with_a_single_enumerator | |
enumerator = CombinedOrderedEnumerator.new((1..5).to_enum) | |
assert_equal [1, 2, 3, 4, 5], enumerator.take(10) | |
end | |
def test_enumerating_with_two_empty_arrays | |
enumerator = CombinedOrderedEnumerator.new([].to_enum, [].to_enum) | |
assert_equal [], enumerator.take(20) | |
end | |
def test_enumerating_with_one_empty_array_and_finite_sequence | |
enumerator = CombinedOrderedEnumerator.new([].to_enum, (1..10).to_enum) | |
assert_equal [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], enumerator.take(20) | |
end | |
def test_enumerating_with_one_empty_array_and_finite_sequence_with_switched_args | |
enumerator = CombinedOrderedEnumerator.new((1..10).to_enum, [].to_enum) | |
assert_equal [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], enumerator.take(20) | |
end | |
def test_enumerating_an_infinite_sequence_and_finite_one | |
enumerator = CombinedOrderedEnumerator.new(fibonacci, (1..10).to_enum) | |
assert_equal [0, 1, 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 9, 10, 13, 21, 34], enumerator.take(20) | |
end | |
def test_enumerating_two_infinite_sequences | |
enumerator = CombinedOrderedEnumerator.new(fibonacci, sum_of_natural_numbers) | |
assert_equal [0, 1, 1, 1, 2, 3, 3, 5, 6, 8, 10, 13, 15, 21, 21, 28, 34, 36, 45, 55], enumerator.take(20) | |
end | |
def test_enumerating_three_finite_sequences | |
enumerator = CombinedOrderedEnumerator.new((1..5).to_enum, (1..3).to_enum, (4..10).to_enum) | |
assert_equal [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10], enumerator.take(20) | |
end | |
def test_enumerating_three_infinite_sequences | |
enumerator = CombinedOrderedEnumerator.new(fibonacci, fibonacci, fibonacci) | |
assert_equal [0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2], enumerator.take(12) | |
end | |
def test_raises_unordered_enumerator_exception_if_enumerator_isnt_in_ascending_order | |
enumerator = CombinedOrderedEnumerator.new(10.downto(1)) | |
assert_raises(CombinedOrderedEnumerator::UnorderedEnumerator) do | |
enumerator.take(20) | |
end | |
end | |
def test_raising_unordered_enumerator_should_reference_enumerator | |
decending_enumerator = 10.downto(1) | |
enumerator = CombinedOrderedEnumerator.new(decending_enumerator) | |
begin | |
enumerator.take(2) | |
assert false | |
rescue CombinedOrderedEnumerator::UnorderedEnumerator => exception | |
assert_equal decending_enumerator, exception.enumerator | |
end | |
end | |
private | |
class FibonacciEnumerator < Enumerator | |
def initialize | |
super() do |yielder| | |
a, b = 0, 1 | |
loop do | |
yielder.yield a | |
a, b = b, (a + b) | |
end | |
end | |
end | |
end | |
def fibonacci | |
FibonacciEnumerator.new | |
end | |
class SumOfNaturalNumbersEnumerator < Enumerator | |
def initialize | |
super() do |yielder| | |
n = 1 | |
loop do | |
yielder.yield (n * (n + 1)) / 2 | |
n += 1 | |
end | |
end | |
end | |
end | |
def sum_of_natural_numbers | |
SumOfNaturalNumbersEnumerator.new | |
end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment