Clone an Enumerator in Ruby?

Question

I have a tree that I'm trying to traverse. As I traverse it, I keep a stack of enumerators in which each enumerator is used to enumerate over a tree's children.

I'd like to be able to duplicate this stack of enumerators and hand it to another object so it may traverse the tree starting in the place indicated by the state of the stack.

When I attempt to call #dup on Enumerator, I get an error. Is it possible to duplicate an Enumerator? If not, how could I accomplish the same thing? (I've considered a stack of integers as indices, but am worried about the efficiency.

Here's some code to show what I'm seeing...

Once the first enumerator has started, you cannot duplicate it. That is my situation.

a = [1,2,3].each
 => #<Enumerator: [1, 2, 3]:each> 
a.next
 => 1 
b = a.dup
TypeError: can't copy execution context
    from (irb):3:in `initialize_copy'
    from (irb):3:in `initialize_dup'
    from (irb):3:in `dup'
    from (irb):3

Thao

Call @dup? You mean call dup? – Sennacherib

Is this an academic exercise or would you benefit from the RubyTree gem? – Cultivation

#next is not preferred way to use enumerators in ruby. I believe it is defined using fibers, and stackframes cannot be duplicated. Can you elaborate what do you need this for? Maybe we could suggest more ruby-way of solving your problem. – Nixie

@samuil: #next is the preferred way to do external iteration. And yes, enumerators can be duplicated before they are iterated. – Senecal

Are you trying to do a depth first tree traversal with numerators? – Blear

@Catnapper: external iteration is not preferred way of iterating in functional languages. Ruby, as a multi-paradigm language can be treated as such. External iteration needs enumerator to keep its state and is not easily threadsafe. – Nixie

@samuil: Fibers are no less thread safe than any other data structure in Ruby. The original poster said nothing about solving this problem in a functional way, nothing about multithreading, and Fiber-backed routines are not exclusively a threaded or functional programming technique. Spreading bad info like "#next is not preferred" is simply wrong. – Senecal

@Catnapper: I can't agree with you. I understand that #next is provided by standard ruby libraries, as there are tasks quite hard to solve in functional approach, but it is not preferred way to use them. Enumerators are internally built around #each method, and this is correct way to use them. – Nixie

@samuil: For the case where several Enumerators are being iterated simultaneously, #next is invaluable; I agree that #next is not generally as useful as #each for iterating single Enumerators. I don't agree with the blanket statement that #next is not preferred. I've used external iterators in several projects to good effect, and the code that uses them has proven to be very maintainable (the highest calling code can aspire to, in my opinion). – Senecal

@Catnapper: I also have been working in ruby for several years now, and since I got familiar with #zip method from Enumerable module I haven't found single case in which I could use external enumeration. Anyway -- I believe that we agree with each other deep inside :) It is just matter of single sentence ripped out of context: "#next is not preferred way to iterate in ruby". – Nixie

Hi everyone. Thanks for your comments. I am indeed trying to do depth-first tree traversal with Enumerators. And it will be multithreaded in the sense that when a thread knows that it will wait, it will spawn a new thread with a copy of the stack of enumerators so it can pick up where the first thread left off. – Thao

FYI: How to create a "clone"-able enumerator for external iteration? – Rileyrilievo

Answer 1

Implement your own enumerator class.

There’s not much magic to an enumerator beyond incrementing an internal counter.

class MyArrayEnumerator
  def initialize(array)
    @ary,@n=array,0
  end
  def next
    raise StopIteration if @n == @ary.length
    a=@ary[@n];@n+=1;a
  end
end

class Array
  def my_each
    MyArrayEnumerator.new(self)
  end
end

a = [1,2,3].my_each # => #<MyArrayEnumerator:0x101c96588 @n=0, @array=[1, 2, 3]>
a.next # => 1
b = a.dup # => #<MyArrayEnumerator:0x101c95ae8 @n=1, @array=[1, 2, 3]>
a.next # => 2
b.next # => 2

Mellicent

Answer 2

Use clone instead:

e1 = [1,2,3].each
e1.dup # TypeError: can't copy execution context
e2 = e1.clone
e1.next #=> 1
e2.next #=> 1

Thimble

You can dup and clone as long as the enumerator is pristine. Once you start enumerating (e.g. via next) they both raise that TypeError. – Rileyrilievo

Answer 3

keep one "head" amongst Enumerator's instances, and store history for behind copies:

class Enum

  def initialize()
    @history = [] # history will be shared between instances
    @history_cursor = -1
    @head = Enumerator.new do |yielder|
      @yielder = yielder
      enumerate
    end
  end

  def next
    if @history_cursor < @history.count - 1
      @history[@history_cursor += 1]
    else
      new_item @head.next
    end
  end

  private

  def new_item item
    @history << item
    @history_cursor = @history.count - 1
    item
  end

  def enumerate
    13.times do |i|
      @yielder << i # yielder is shared between instances
    end
  end

end

Usage:

enum1 = Enum.new
p enum1.next # 0
enum2 = enum1.clone
p enum2.next # 1
p enum1.next # 1

Stat