Forum: Ruby-Gnome 2 Recursive TreeStore problem

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Miles K. (Guest)
on 2009-03-11 13:55
I've built this recursive bit of code to take an array of arrays and
create a treestore from it.  It seems to do what it supposed to do
except, child nodes are not appended to parent nodes.  I suspect it has
something to do with passing the "new" (treestore.append()) value.  Any
help would be appreciated.

def add_nodes(treestore, parent_id, parent)
  0.upto(@gallerybox.length-1) do |i|
      if t.to_i == parent_id
         new = treestore.append(parent)
         new[0] = @gallerybox[i][0].to_i
         new[1] = @gallerybox[i][1].to_i
         new[2] = @gallerybox[i][2]
         new[3] = @gallerybox[i][3]
         add_nodes(treestore, @gallerybox[i][0], new)
         puts "new node done"
      end
   end
end
Miles K. (Guest)
on 2009-03-11 17:25
Ok, I'm an idiot.  Trying to make something simple hard.....Here's the
solution :

def populate_tree(node, parentid)
   @gallerybox.each { |gallery|
      id=gallery[0].to_i
      parent=gallery[1].to_i
      name=gallery[2]
      created = gallery[3]
      if parent == parentid
         child=@treestore.append(node)
         child[0] = id
         child[1] = parent
         child[2] = name
         child[3] = created
         populate_tree(child, id)
      end
   }
end
Igor P. (Guest)
on 2009-03-11 18:28
Miles K. wrote:
> Ok, I'm an idiot.  Trying to make something simple hard.....Here's the
> solution :
>
> def populate_tree(node, parentid)
>    @gallerybox.each { |gallery|
>       id=gallery[0].to_i
>       parent=gallery[1].to_i
>       name=gallery[2]
>       created = gallery[3]
>       if parent == parentid
>          child=@treestore.append(node)
>          child[0] = id
>          child[1] = parent
>          child[2] = name
>          child[3] = created
>          populate_tree(child, id)
>       end
>    }
> end

Though your {{ if parent == parentid }} looks problematic, assuming it
would, when fixed identify parent nodes properly, unless you have
created parents elsewhere, I suggest you do the following:

def populate_tree(node, parentid)
   @gallerybox.each do |gallery|
      if parent == parentid
         child=@treestore.append(nil)
         child[0] = gallery[0].to_i
         child[1] = gallery[1].to_i
         child[2] = gallery[2]
         child[3] = gallery[3]
         populate_tree(child, id)
      else
         child=@treestore.append(node)
         child[0] = gallery[0].to_i
         child[1] = gallery[1].to_i
         child[2] = gallery[2]
         child[3] = gallery[3]
         populate_tree(child, id)
      end
   end
end
Miles K. (Guest)
on 2009-03-11 19:09
Igor P. wrote:
> Though your {{ if parent == parentid }} looks problematic, assuming it
> would, when fixed identify parent nodes properly, unless you have
> created parents elsewhere, I suggest you do the following:
>
> def populate_tree(node, parentid)
>    @gallerybox.each do |gallery|
>       if parent == parentid
>          child=@treestore.append(nil)
>          child[0] = gallery[0].to_i
>          child[1] = gallery[1].to_i
>          child[2] = gallery[2]
>          child[3] = gallery[3]
>          populate_tree(child, id)
>       else
>          child=@treestore.append(node)
>          child[0] = gallery[0].to_i
>          child[1] = gallery[1].to_i
>          child[2] = gallery[2]
>          child[3] = gallery[3]
>          populate_tree(child, id)
>       end
>    end
> end

I have a mysql table like :

key_id
parent_id
data
created

gallerybox is an array of rows of this table.

parent in the code refers to parent_id from this table
and parentid is the key_id.

Initially I pass ( 0,nil ) to this function so that the inital pass
builds the root level of the tree, the recursive builds all lower
levels.

Perhaps my variable naming is poor but I think the original method
works.
Igor P. (Guest)
on 2009-03-11 19:21
Sorry for repeating my post but this is more eligible and better reveals
some issues earlier hidden:

def populate_tree(node, parentid)
   @gallerybox.each do |gallery|
      if parent_identification == parentid
         parent = @treestore.append(nil)
         parent[0] = gallery[0].to_i
         parent[1] = gallery[1].to_i
         parent[2] = gallery[2]
         parent[3] = gallery[3]
         populate_tree(parent, id)
      else
         child = @treestore.append(node)
         child[0] = gallery[0].to_i
         child[1] = gallery[1].to_i
         child[2] = gallery[2]
         child[3] = gallery[3]
         populate_tree(child, id)
      end
   end
end

However, I still do have an issue with {{ if parent_identification ==
parentid }}. I have tested this recursive method in a full-blown
Ruby/Gtk GUI application and it works fine.

Cheers, Igor
Guillaume C. (Guest)
on 2009-03-11 19:25
(Received via mailing list)
>         child=@treestore.append(node)
>         child[0] = gallery[0].to_i
>         child[1] = gallery[1].to_i
>         child[2] = gallery[2]
>         child[3] = gallery[3]
>         populate_tree(child, id)
>      end
>   end
> end

Any reason to duplicate so much code? I routinely hurt my eyes,
nowadays..

def populate_tree(node, parentid)
  @gallerybox.each do |gallery|
        child=@treestore.append(parent == parentid ? nil : node)
        child[0] = gallery[0].to_i
        child[1] = gallery[1].to_i
        child[2] = gallery[2]
        child[3] = gallery[3]
        populate_tree(child, id)
  end
end

--
Guillaume C. - http://zarb.org/~gc/
Igor P. (Guest)
on 2009-03-11 19:29
Miles K. wrote:

> Initially I pass ( 0,nil ) to this function so that the inital pass
> builds the root level of the tree, the recursive builds all lower
> levels.

You may have multiple root levels each with its own children. Look at
the example in Ruby/Gtk tutorial at
http://ruby-gnome2.sourceforge.jp/hiki.cgi?tut-gtk..., where
"Cleaning supplies" and "Food" rows represent root levels. In fact I
have tested your recursive method in this application.
Miles K. (Guest)
on 2009-03-11 19:31
Guillaume C. wrote:

> Any reason to duplicate so much code? I routinely hurt my eyes,
> nowadays..
>
> def populate_tree(node, parentid)
>   @gallerybox.each do |gallery|
>         child=@treestore.append(parent == parentid ? nil : node)
>         child[0] = gallery[0].to_i
>         child[1] = gallery[1].to_i
>         child[2] = gallery[2]
>         child[3] = gallery[3]
>         populate_tree(child, id)
>   end
> end

True enough.  I should have cleaned that up a bit.  Verbosity sometimes
helps me think through things.

Cheers.
Igor P. (Guest)
on 2009-03-11 19:34
Igor P. wrote:
> Look at the example in Ruby/Gtk tutorial at
> http://ruby-gnome2.sourceforge.jp/hiki.cgi?tut-gtk..., where
> "Cleaning supplies" and "Food" rows represent root levels. In fact I
> have tested your recursive method in this application.

Comma, at the end of the link should be avoided, so try this:
http://ruby-gnome2.sourceforge.jp/hiki.cgi?tut-gtk...
Igor P. (Guest)
on 2009-03-11 22:00
Miles K. wrote:

> def populate_tree(node, parentid)
>   @gallerybox.each do |gallery|
>         child=@treestore.append(parent == parentid ? nil : node)
>         child[0] = gallery[0].to_i
>         child[1] = gallery[1].to_i
>         child[2] = gallery[2]
>         child[3] = gallery[3]
>         populate_tree(child, id)
>   end
> end

I was so excited about your "recursive invention" that I wanted to
publish it on Ruby/Gtk2 tutorial web page, and in the process of doing
so I discovered I was not really testing the recursive call with your
populate_tree, which is in fact wrong, because the way you wrote it
makes it an infinite, never-ending recursion. I actually tested the
following strategy:

def populate_tree(parent, parentid)
   @gallerybox.each do |gallery|
      if parent_identification == parentid
         parent = @treestore.append(nil)
         parent[0] = gallery[0].to_i
         parent[1] = gallery[1].to_i
         parent[2] = gallery[2]
         parent[3] = gallery[3]
      else
         child = @treestore.append(parent)
         child[0] = gallery[0].to_i
         child[1] = gallery[1].to_i
         child[2] = gallery[2]
         child[3] = gallery[3]
      end
   end
end

I do believe your code would not work properly even if you take the
recursive call out. You have to retain the value of the last iterator
value across the block iterations and you are loosing that by creating a
block local variable "child". You need to either use method's parameter
like in my example (parent), or you need to define {{ parent = child =
nil }} before entering the block.

And most importantly, your "shortened" or as you say "cleaned-up"
version will also not work properly with multiple root rows, because you
are overriding parent iterators by child iterators. Iterators are
references and by doing what you are doing, you make them point to the
same data items.

I do not exactly know how the internals  of Gtk::TreeStore  work here,
but clearly we have something like the following problem with references
and multi-dimensional arrays:

 +----------------------------+
 | line = %w[ . . . . . ]     |
 | page = [line, line, line]  |
 | puts page.to_s             |
 | page[2][3] = 9             |
 | line[1] = "X"              |
 | puts page.to_s             |
 +----------------------------+
 OUTPUT:
   ...............
   .X.9..X.9..X.9.

Again, sorry for my part of the slip.
Miles K. (Guest)
on 2009-03-11 22:48
Hi Igor,

The recursive function does work given my data set.  The mysql table
that I am drawing from already contains the parent/child relationships.

Table :

[ INDEX ] [ PARENT ] [ DATA ]
    1         0       food        >> ROOT Category
    2         1       cheeses     >> Sub-Category
    3         2       cheddar     >> Item 1
    4         2       brie        >> Item 2
    5         0       beverages   >> ROOT Category

and so forth.

Does this clear it up at all?
Igor P. (Guest)
on 2009-03-12 03:35
Miles K. wrote:

> The recursive function does work given my data set.  The mysql table
> that I am drawing from already contains the parent/child relationships.
>
> Table :
>
> [ INDEX ] [ PARENT ] [ DATA ]
>     1         0       food        >> ROOT Category
>     2         1       cheeses     >> Sub-Category
>     3         2       cheddar     >> Item 1
>     4         2       brie        >> Item 2
>     5         0       beverages   >> ROOT Category
>
> and so forth.
>
> Does this clear it up at all?

Hi Miles,

After what you have said now it does look that recursion is the best
strategy to solve this algorithm. However you are growing it on me
gradually. First you didn't even consider multiple root records, and
from your last post it is clear that you have not only multiple root
records but multiple levels of indentation, i.e. not only
two-dimensional Gtk::TreeStore structure but a multi-dimensional one.

And so I come back to my very first objection, which is your condition
that when looked at superficially seemed to only determine the root
nodes, but is actually the controlling mechanism for the recursion. You
should have given more precise definition of what was only a
hypothetical pseudo-code like condition "if t.to_i == parent_id".

The second issue you have here is the problem which I have already
covered extensively, and would show up only when you actually run a GUI
application, where you would either get root and children nodes properly
indented, or you would only get a two-dimensional layout!

Third minor problem which, indeed, can be programmatically accounted
for, is with your list notation. Your [ INDEX ] [ PARENT ] [ DATA ]
should actually look something like the following:

[ INDEX ] [ PARENT ] [ DATA ]
  0,        0,       "food"          >> ROOT Category
  1,        1,       "cheeses"       >> Sub-Category
  2,        1,       "cheddar"       >> Item 1
  3,        1,       "brie"          >> Item 1
  4,        4,       "beverages"     >> ROOT Category
  5,        5,       "non-alcohol"   >> Sub-Category
  6,        5,       "pepsi"         >> Item 1
  7,        5,       "coke"          >> Item 1
  8,        4,       "alcoholic"     >> Sub-Category
  9,        8,       "wine"          >> Item 1
 10,        8,       "brandy"        >> Item 1

I am really interested to see how you actually handled the problematic
recursion terminating condition.

Cheers, Igor
Igor P. (Guest)
on 2009-03-12 03:39
Ooops, that'll do:

[ INDEX ] [ PARENT ] [ DATA ]
  0,        0,       "food"          >> ROOT Category
  1,        0,       "cheeses"       >> Sub-Category
  2,        1,       "cheddar"       >> Item 1
  3,        1,       "brie"          >> Item 2
  4,        4,       "beverages"     >> ROOT Category
  5,        4,       "non-alcohol"   >> Sub-Category
  6,        5,       "pepsi"         >> Item 1
  7,        5,       "coke"          >> Item 2
  8,        4,       "alcoholic"     >> Sub-Category
  9,        8,       "wine"          >> Item 1
 10,        8,       "brandy"        >> Item 2
Miles K. (Guest)
on 2009-03-12 04:14
Igor P. wrote:
> Ooops, that'll do:
>
> [ INDEX ] [ PARENT ] [ DATA ]
>   0,        0,       "food"          >> ROOT Category
>   1,        0,       "cheeses"       >> Sub-Category
>   2,        1,       "cheddar"       >> Item 1
>   3,        1,       "brie"          >> Item 2
>   4,        4,       "beverages"     >> ROOT Category
>   5,        4,       "non-alcohol"   >> Sub-Category
>   6,        5,       "pepsi"         >> Item 1
>   7,        5,       "coke"          >> Item 2
>   8,        4,       "alcoholic"     >> Sub-Category
>   9,        8,       "wine"          >> Item 1
>  10,        8,       "brandy"        >> Item 2

Hey Igor,

I think I get where you're coming from now.  Let me see if we can't
straighten this out.

The list notation is purely illustrative and represented the way my data
is stored.  It is important to note that the data is derived from a
mysql table.  The index is a self incrementing value that is generated
by mysql as the key for the table.  It will never begin at zero.  If it
were however, you are correct that it would endlessly repeat.

That being said, the above data set should be modified to reflect these
two changes.

1) [Index] needs to start at 1 and increment from there.
2) the parent of "beverages" cannot be itself in order to be a Root
Category. The parent of beverages would need to be 0.

Other than that, it would work fine.

--Miles
Igor P. (Guest)
on 2009-03-12 11:13
Miles K. wrote:

> I think I get where you're coming from now.  Let me see if we can't
> straighten this out.
>
> The list notation is purely illustrative and represented the way my data
> is stored.  It is important to note that the data is derived from a
> mysql table.  The index is a self incrementing value that is generated
> by mysql as the key for the table.  It will never begin at zero.  If it
> were however, you are correct that it would endlessly repeat.
>
> That being said, the above data set should be modified to reflect these
> two changes.
>
> 1) [Index] needs to start at 1 and increment from there.
> 2) the parent of "beverages" cannot be itself in order to be a Root
> Category. The parent of beverages would need to be 0.
>
> Other than that, it would work fine.


Hi Miles,

I agree, with your last and second point, namely root for beverages
should be 0 (I made a hasty mistake there), but I do not entirely agree
with your first point though it is not a fatal problem and can be
accommodated in a programmatic way. Strictly speaking index does start
with zero and is logically the top root node, in fact, that is why you
start your recursion with the nil parameter for the first node or
iteration.

It was fun talking to you!
Igor
This topic is locked and can not be replied to.