converting traversal fn into Enumeration

[Fearless Fool]

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.newleft, :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

 

[Brian Candler]

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

 

[Fearless Fool]

Brian Candler 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

 

[Michael Fellinger]

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
=C2=A0def traversal
=C2=A0 =C2=A0Enumerable::Enumerator.new(self, :traverse)
=C2=A0end
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 }
# =3D> 7

--=20
Michael Fellinger
CTO, The Rubyists, LLC

 

[Robert Klemme]

I've not quite wrapped my head around Enumerations, but I suspect I'm
just being dense. =A0Assume the following small code fragment:
-----
TNode =3D Struct.newleft, :right, :value)
class TNode

=A0def traverse(&block)
=A0 =A0left.traverse(&block) if left
=A0 =A0right.traverse(&block) if right
=A0 =A0yield(self)
=A0end

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. =A0Any hints? =A0Or is it not worth the effort?

See above.

Kind regards

robert

--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

 

[Fearless Fool]

Robert Klemme 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

 

[w_a_x_man]

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

Works in 1.8.7 also.