Asp Forum - Puzzling bug with yielded array

A. S. Bradbury

9/8/2006 1:26:00 PM

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:

> Results when making an array then flattening it
> Yielded [Ariel::Node - node_name=:child1; parent=:root;
> children=[:child1_1];, Ariel::Node - node_name=:child2; parent=:root;
> children=[];]
>
> Yielded [Ariel::Node - node_name=:child1_1; parent=:child1; children=[];]
>
> results=[[Ariel::Node - node_name=:child1; parent=:root;
> children=[:child1_1];, Ariel::Node - node_name=:child2; parent=:root;
> children=[];], [Ariel::Node - node_name=:child1_1; parent=:child1;
> children=[];]]
>
> Results when just adding the array
> Yielded [Ariel::Node - node_name=:child1; parent=:root;
> children=[:child1_1];, Ariel::Node - node_name=:child2; parent=:root;
> children=[];]
>
> Yielded [Ariel::Node - node_name=:child1_1; parent=:child1; children=[];]
>
> results=[[Ariel::Node - node_name=:child1_1; parent=:child1;
> children=[];], [Ariel::Node - node_name=:child1_1; parent=:child1;
> 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

10 Answers

William Crawford

9/8/2006 1:51:00 PM

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.

--
Posted via http://www.ruby-....

William Crawford

9/8/2006 1:53:00 PM

William Crawford 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.

--
Posted via http://www.ruby-....

A. S. Bradbury

9/8/2006 1:56:00 PM

On Friday 08 September 2006 14:51, William Crawford 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-t...

Regards,
Alex

Ara.T.Howard

9/8/2006 1:59:00 PM

Michael Ulm

9/8/2006 2:02:00 PM

A. S. Bradbury wrote:

--snip--
> results << level # doesn't work

results << level.dup

HTH,

Michael

--
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: michael.ulm@isis-papyrus.com
Visit our Website: www.isis-papyrus.com

A. S. Bradbury

9/8/2006 2:45:00 PM

On Friday 08 September 2006 14:59, ara.t.howard@noaa.gov 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

Rick DeNatale

9/8/2006 8:59:00 PM

On 9/8/06, A. S. Bradbury <asbradbury@tekcentral.org> 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.denh...

e

9/8/2006 11:46:00 PM

Rick Denatale wrote:
> On 9/8/06, A. S. Bradbury <asbradbury@tekcentral.org> 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

--
Posted via http://www.ruby-....

A. S. Bradbury

9/9/2006 10:47:00 AM

On Saturday 09 September 2006 00:46, Eero Saynatkari wrote:
> Rick Denatale wrote:
> > On 9/8/06, A. S. Bradbury <asbradbury@tekcentral.org> 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

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

9/10/2006 3:25:00 PM

On 9/9/06, A. S. Bradbury <asbradbury@tekcentral.org> 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.denh...

comp.lang.ruby

Puzzling bug with yielded array

A. S. Bradbury

William Crawford

William Crawford

A. S. Bradbury

Ara.T.Howard

Michael Ulm

A. S. Bradbury

Rick DeNatale

e

A. S. Bradbury

Rick DeNatale

x Login to ForumsZone