I have a Node class, children are stored in a hash with the node’s name
as the
key and the child node object as the value. I have the method
Node#each_level
that yields each level of the node tree as an array:
def each_level(include_self=false)
if include_self
node_queue=[self]
else
node_queue=self.children.values
end
yield node_queue
while node_queue.any? {|node| node.children.empty? == false} do
node_queue.collect! {|node| node.children.values}
node_queue.flatten!
yield node_queue
end
end
Here is the code that demonstrates the problem:
require ‘ariel’
root=Ariel::Node.new :root
child1=Ariel::Node.new :child1
child2=Ariel::Node.new :child2
child1_1=Ariel::Node.new :child1_1
root.add_child child1
root.add_child child2
child1.add_child child1_1
results=[]
puts “Results when making an array then flattening it”
root.each_level do |level|
puts “Yielded #{level.inspect}”
puts
raise StandardError unless level.kind_of? Array
results << [level].flatten # works
end
puts “results=#{results.inspect}”
puts
results=[]
puts “Results when just adding the array”
root.each_level do |level|
puts “Yielded #{level.inspect}”
puts
raise StandardError unless level.kind_of? Array
raise StandardError if level.any? {|val| val.kind_of? Array}
results << level # doesn’t work
end
puts “results=#{results.inspect}”
I’m really, really stumped. Here’s the output:
children=[];]]
children=[];]]
The yielded data is always correct and the same each time, but as you
can see
the second results array is wrong. Can anyone explain what’s going on
here?
Alex
A. S. Bradbury wrote:
The yielded data is always correct and the same each time, but as you
can see
the second results array is wrong. Can anyone explain what’s going on
here?
Alex
I can’t find anything about the ‘each_level’ method, so I’m guessing
it’s in the newest version of Ariel (ie: Not the one I just got from
rubygems) and it’s either not doing what you think, or not working
properly.
each_descendant does seem to do what you want, however, in Ariel 0.1.0.
William C. wrote:
A. S. Bradbury wrote:
The yielded data is always correct and the same each time, but as you
can see
the second results array is wrong. Can anyone explain what’s going on
here?
Alex
I can’t find anything about the ‘each_level’ method, so I’m guessing
it’s in the newest version of Ariel (ie: Not the one I just got from
rubygems) and it’s either not doing what you think, or not working
properly.
each_descendant does seem to do what you want, however, in Ariel 0.1.0.
Wow, totally missed that each_level was yours. -sigh- I really need to
learn to read.
On Friday 08 September 2006 14:51, William C. wrote:
I can’t find anything about the ‘each_level’ method, so I’m guessing
it’s in the newest version of Ariel (ie: Not the one I just got from
rubygems) and it’s either not doing what you think, or not working
properly.
each_descendant does seem to do what you want, however, in Ariel 0.1.0.
Thanks for taking a look. I’m the author of Ariel and I’m working on the
next
version, I included my definition of each_level in the previous email.
It
actually does seem to be doing exactly what I expect it to - see how the
printed level.inspect is always correct. It’s only the results after
each
level has been appended to the array that is wrong.
By the way, if you’re reading this via ruby-forum (which it seems you
are),
ruby-forum.com has eaten most of my pasted output. See the full post at
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/213339
Regards,
Alex
On Friday 08 September 2006 14:59, [email protected] wrote:
your method first returns a list to the caller but, later, munges it in
place without the caller’s consent. this is as evil as returning pointer
to member in c–.
I really appreciate your detailed reply, the problem is very clear now
and
hopefully I’ve learnt from it.
A more general question - how would you (ruby-talk readers) implement
this
method? Two people on #ruby-lang suggested I make it recursive, but I
really
don’t see this sort of tree traversal mapping to a recursive method, am
I
wrong?
Alex
On Fri, 8 Sep 2006, A. S. Bradbury wrote:
yield node_queue
while node_queue.any? {|node| node.children.empty? == false} do
node_queue.collect! {|node| node.children.values}
node_queue.flatten!
yield node_queue
end
end
the problem is here. this illustrates the issue:
harp:~ > cat a.rb
def yields_shared_then_munged_list
list = %w[ forty-two ]
yield list
list.collect!{|elem| elem.upcase}
yield list
end
yields_shared_then_munged_list{|list| p list}
harp:~ > ruby a.rb
[“forty-two”]
[“FORTY-TWO”]
your method first returns a list to the caller but, later, munges it in
place
without the caller’s consent. this is as evil as returning pointer to
member
in c–.
root.add_child child2
child1.add_child child1_1
results=[]
puts “Results when making an array then flattening it”
root.each_level do |level|
puts “Yielded #{level.inspect}”
puts
raise StandardError unless level.kind_of? Array
results << [level].flatten # works
because you are making a copy. so the traversal code does fubar the
elements
of results in place.
puts
raise StandardError unless level.kind_of? Array
raise StandardError if level.any? {|val| val.kind_of? Array}
results << level # doesn’t work
because results contains a reference to the yielded array (not a copy)
so the
subsequent calls to ‘collect!’, etc. scramble it in place.
kind regards.
-a
On 9/8/06, A. S. Bradbury [email protected] wrote:
A more general question - how would you (ruby-talk readers) implement this
method? Two people on #ruby-lang suggested I make it recursive, but I really
don’t see this sort of tree traversal mapping to a recursive method, am I
wrong?
Tree traversal usually lends itself well to a recursive
implementation, but it’s not clear to me exactly what your each_level
method is supposed to do.
But here’s a recursive implementation that might do the same thing.
def each_level(include_self=false, &block)
yield [self] if include_self
kids = children.values
unless kids.empty?
yield kids
kids.each do {|kid| kid.each_level(&block)}
end
end
–
Rick DeNatale
My blog on Ruby
http://talklikeaduck.denhaven2.com/
On Saturday 09 September 2006 00:46, Eero S. wrote:
end
That is a semi-depth-first traversal, though. Apparently
we are looking for breadth-first here 
That would be
simplest to implement with some kind of a storage–say
an Array with an element for each level–which is sort
of what the OP’s method was doing (though only for the
first three levels since it does not recurse).
Rick DeNatale
Indeed, I am implementing a breadth-first or level-by-level traversal. I
don’t
understand your comment about “only for the first three levels”?
I can see other forms of tree traversal lending themselves well to a
recursive
implementation, but not really level by level, particular as I want each
level to be returned as an array.
Alex
Rick Denatale wrote:
On 9/8/06, A. S. Bradbury [email protected] wrote:
A more general question - how would you (ruby-talk readers) implement this
method? Two people on #ruby-lang suggested I make it recursive, but I really
don’t see this sort of tree traversal mapping to a recursive method, am I
wrong?
Tree traversal usually lends itself well to a recursive
implementation, but it’s not clear to me exactly what your each_level
method is supposed to do.
But here’s a recursive implementation that might do the same thing.
def each_level(include_self=false, &block)
yield [self] if include_self
kids = children.values
unless kids.empty?
yield kids
kids.each do {|kid| kid.each_level(&block)}
end
end
That is a semi-depth-first traversal, though. Apparently
we are looking for breadth-first here 
That would be
simplest to implement with some kind of a storage–say
an Array with an element for each level–which is sort
of what the OP’s method was doing (though only for the
first three levels since it does not recurse).
Rick DeNatale
On 9/9/06, A. S. Bradbury [email protected] wrote:
I can see other forms of tree traversal lending themselves well to a recursive
implementation, but not really level by level, particular as I want each
level to be returned as an array.
Here’s a recursive implementation of that then:
def each_level(include_self=false, levels=[[]], depth=0)
levels[depth] << self if include_self
kids = self.children.values
unless kids.empty?
levels << [] unless levels.length > depth + 1
kids.each {|kid| kid.each_level(true, levels,
depth+1)}
end
levels.each {|l| yield l} if depth.zero?
end
Although it might be better to make a public wrapper method to start,
and make the internal recursive method private, so as not to expose
the extra parameters:
def each_level(include_self=false)
levels = []
levels << [self] if include_self
kids = self.children.values
unless kids.empty?
levels << []
kids.each {|kid| kid.each_level_internal(levels,
1)}
end
levels.each {|l| yield l}
end
private
def each_level_internal(levels, depth)
levels[depth] << self
kids = self.children.values
unless kids.empty?
levels << [] unless levels.length > depth + 1
kids.each {|kid|
kid.each_level_internal(levels, depth+1)}
end
end
–
Rick DeNatale
My blog on Ruby
http://talklikeaduck.denhaven2.com/