Puzzling bug with yielded array

Discussion in 'Ruby' started by A. S. Bradbury, Sep 8, 2006.

  1. 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
    A. S. Bradbury, Sep 8, 2006
    #1
    1. Advertising

  2. 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-forum.com/.
    William Crawford, Sep 8, 2006
    #2
    1. Advertising

  3. 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-forum.com/.
    William Crawford, Sep 8, 2006
    #3
  4. 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-talk/213339

    Regards,
    Alex
    A. S. Bradbury, Sep 8, 2006
    #4
  5. A. S. Bradbury

    Guest

    On Fri, 8 Sep 2006, A. S. Bradbury wrote:

    > 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


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



    > 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


    because you are making a copy. so the traversal code does fubar the elements
    of results in place.

    > 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


    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
    --
    what science finds to be nonexistent, we must accept as nonexistent; but what
    science merely does not find is a completely different matter... it is quite
    clear that there are many, many mysterious things.
    - h.h. the 14th dalai lama
    , Sep 8, 2006
    #5
  6. A. S. Bradbury

    Michael Ulm Guest

    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:
    Visit our Website: www.isis-papyrus.com
    Michael Ulm, Sep 8, 2006
    #6
  7. On Friday 08 September 2006 14:59, 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
    A. S. Bradbury, Sep 8, 2006
    #7
  8. On 9/8/06, A. S. Bradbury <> 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/
    Rick DeNatale, Sep 8, 2006
    #8
  9. Rick Denatale wrote:
    > On 9/8/06, A. S. Bradbury <> 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-forum.com/.
    Eero Saynatkari, Sep 9, 2006
    #9
  10. On Saturday 09 September 2006 00:46, Eero Saynatkari wrote:
    > Rick Denatale wrote:
    > > On 9/8/06, A. S. Bradbury <> 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
    A. S. Bradbury, Sep 9, 2006
    #10
  11. On 9/9/06, A. S. Bradbury <> 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/
    Rick DeNatale, Sep 10, 2006
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. John Salerno
    Replies:
    18
    Views:
    455
    Lonnie Princehouse
    Apr 10, 2006
  2. Michael Press

    Puzzling compiler response to array initialization.

    Michael Press, Oct 4, 2005, in forum: C Programming
    Replies:
    18
    Views:
    443
    Michael Wojcik
    Oct 5, 2005
  3. DanWeaver
    Replies:
    0
    Views:
    256
    DanWeaver
    Apr 7, 2008
  4. Sébastien de Mapias
    Replies:
    3
    Views:
    324
    Roedy Green
    Oct 19, 2008
  5. Ara.T.Howard

    return from yielded block

    Ara.T.Howard, Feb 13, 2004, in forum: Ruby
    Replies:
    10
    Views:
    194
    Yukihiro Matsumoto
    Feb 14, 2004
Loading...

Share This Page