Converting traversal fn into Enumeration

I’ve not quite wrapped my head around Enumerations, but I suspect I’m
just being dense. Assume the following small code fragment:

TNode = Struct.new(:left, :right, :value)
class TNode

def traverse(&block)
left.traverse(&block) if left
right.traverse(&block) if right
yield(self)
end

end

… which lets me define a method such as:

def find_node(value)
traverse { |node| return node if (node.value == value) } || nil
end

For somewhat didactic reasons, I’d prefer a method TNode#traversal(),
that returns an Enumerable, so I could do something like:

def find_node(value)
traversal.find {|n| n.value == value}
end

… but as I mentioned, I haven’t figured out the right way to structure
this. Any hints? Or is it not worth the effort?

TIA.

  • ff

It’s easier than you think. Just define a method called ‘each’ which
enumerates the objects, and mix-in Enumerable into your class.

class TNode
include Enumerable
alias :each :traverse
end

For somewhat didactic reasons, I’d prefer a method TNode#traversal(),
that returns an Enumerable

You cannot return an Enumerable, because it is a Module, not a Class.
Hence you can’t create instances of Enumerable.

, so I could do something like:


def find_node(value)
traversal.find {|n| n.value == value}
end

What I explained above lets you do it directly on the node:

rootnode.find { |n| n.values == value }

If you don’t want to do this on the node class itself, you can instead
return some other object which has a #each method:

class TNode
class Traversal
include Enumerable
def initialize(root)
@root = root
end
def each
… define it here
end
end
def traversal
Traversal.new(self)
end
end

Or there is class Enumerator in the standard library which you can use
(in 1.8 it’s Enumerable::Enumerator). It just gives a wrapper object
which maps a call to :each to some other method in the underlying
object.

require ‘enumerator’
class TNode
def traversal
Enumerable::Enumerator.new(self, :traverse)
end
end

Brian C. wrote in post #970741:

It’s easier than you think. Just define a method called ‘each’ which
enumerates the objects, and mix-in Enumerable into your class.

Lovely. Perfect. (And I’m saying to myself: whee! this is cool!)
Thank you.

  • ff

On Sun, Dec 26, 2010 at 7:27 PM, Brian C. [email protected]
wrote:

end
The usual way to return enumerators in 1.9 is this:

def traverse
return to_enum(method) unless block_given?
loop{ yield(rand(10)) }
end

traverse.find{|e| e > 1 }

=> 7

On Sun, Dec 26, 2010 at 8:42 AM, Fearless F. [email protected] wrote:

end
Is this really the order that you want? Typically the current node is
visited between left and right to get an in order tree traversal:

def traverse(&block)
left.traverse(&block) if left
yield(self)
right.traverse(&block) if right
end

If you need the result visiting the current node you can store it in a
variable and return it at the end.

Since you yield node instances themselves in #traverse it seems more
natural to implement #each like this:

class TNode
include Enumerable

def each(&b)
left.each(&b) if left
yield value
right.each(&b) if right
self # according to convention of #each
end
end

… but as I mentioned, I haven’t figured out the right way to structure
this. Any hints? Or is it not worth the effort?

See above.

Kind regards

robert

Robert K. wrote in post #970861:

Is this really the order that you want? Typically the current node is
visited between left and right to get an in order tree traversal:
[snip]
Since you yield node instances themselves in #traverse it seems more
natural to implement #each like this:

class TNode
include Enumerable
def each(&b)
left.each(&b) if left
yield value
right.each(&b) if right
self # according to convention of #each
end
end

Hi Robert:

I like your refinement of using each() and returning self – makes good
sense. In this case, I actually want post-order (not in-order)
traversal, but that’s a trivial modification.

Thanks.

  • ff

On Dec 26, 8:23am, Michael F. [email protected] wrote:

end

=> 7

Works in 1.8.7 also.