Asp Forum - Tree reading - comp.lang.ruby

Martin DeMello

6/12/2006 9:39:00 AM

The problem is simple enough - I want to represent a tree in the form
[a, b, [c, d, [e, f], [g, h], [i, j]], [k, l]]

where any given array can contain a sequence of atoms followed by a
sequence of arrays, corresponding to nodedata and children respectively.
However, the code to read it got a bit ugly - can anyone improve on
this:

def import_tree_at(parent, tree)
ary = tree.find {|i| Array === i}
p = ary ? tree.index(ary) : nil
if p.nil?
tree.each_with_index {|d, i| parent[i] = d}
else
tree[0...p].each_with_index {|d, i| parent[i] = d}
tree[p..-1].each {|d|
node = @store.append(parent)
import_tree_at(node, d) if Array === d
}
end
end

(If nothing else, I think it shows the need for an Array#index {|i|
pred?(i)}) to replace the index(find {pred}) double-pass.)

martin

13 Answers

Robert Klemme

6/12/2006 12:28:00 PM

Martin DeMello wrote:
> The problem is simple enough - I want to represent a tree in the form
> [a, b, [c, d, [e, f], [g, h], [i, j]], [k, l]]
>
> where any given array can contain a sequence of atoms followed by a
> sequence of arrays, corresponding to nodedata and children respectively.
> However, the code to read it got a bit ugly - can anyone improve on
> this:
>
> def import_tree_at(parent, tree)
> ary = tree.find {|i| Array === i}
> p = ary ? tree.index(ary) : nil
> if p.nil?
> tree.each_with_index {|d, i| parent[i] = d}
> else
> tree[0...p].each_with_index {|d, i| parent[i] = d}
> tree[p..-1].each {|d|
> node = @store.append(parent)
> import_tree_at(node, d) if Array === d
> }
> end
> end
>
> (If nothing else, I think it shows the need for an Array#index {|i|
> pred?(i)}) to replace the index(find {pred}) double-pass.)

I don't fully understand what your code does. I'm especially wondering
where from it gets the input. I'd probably create a proper tree class
with references to parent and children and do the import on top of that.
If you need to, you can still create nested arrays from that.

14:21:23 [~]: irbs -r enumerator
>> %w{aa bb cc}.to_enum(:each_with_index).find {|a,i| a == "bb"}
=> ["bb", 1]

Thusly

>> el, idx = %w{aa bb cc}.to_enum(:each_with_index).find {|a,i| a == "bb"}
=> ["bb", 1]
>> el
=> "bb"
>> idx
=> 1

Cheers

robert

Martin DeMello

6/12/2006 1:35:00 PM

Robert Klemme <bob.news@gmx.net> wrote:
> Martin DeMello wrote:
> >
> > def import_tree_at(parent, tree)
> > ary = tree.find {|i| Array === i}
> > p = ary ? tree.index(ary) : nil
> > if p.nil?
> > tree.each_with_index {|d, i| parent[i] = d}
> > else
> > tree[0...p].each_with_index {|d, i| parent[i] = d}
> > tree[p..-1].each {|d|
> > node = @store.append(parent)
> > import_tree_at(node, d) if Array === d
> > }
> > end
> > end
>
> I don't fully understand what your code does. I'm especially wondering
> where from it gets the input.

It's from a Gtk::SimpleTree class I'm writing; the point is to have the
input in as lightweight a form as possible. Here's some sample client
code:

# define the tree
s = Gtk::SimpleTree.new([String, String, Integer],
["First Name", 0],
["Last Name", 1,
{:weight => Pango::FontDescription::WEIGHT_BOLD}],
["Age", format_age, {:foreground => "red"}],
["Age", simple_age])

# define the initial data
treedata = [
['Maria', 'Incognito'],
['Jane', 'Average', 1962,
['Janinita', 'Average', 1985]]]

s.import_tree(treedata)

> I'd probably create a proper tree class
> with references to parent and children and do the import on top of that.
> If you need to, you can still create nested arrays from that.

The point is to enter the initial tree inline; there's already a proper
tree class at the back end.

> >> el, idx = %w{aa bb cc}.to_enum(:each_with_index).find {|a,i| a == "bb"}
> => ["bb", 1]
> >> el
> => "bb"
> >> idx
> => 1

Ah, very nice! I keep forgetting about the new stuff from enumerator.

martin

Robert Klemme

6/12/2006 7:55:00 PM

Martin DeMello wrote:
> Robert Klemme <bob.news@gmx.net> wrote:
>> Martin DeMello wrote:
>>> def import_tree_at(parent, tree)
>>> ary = tree.find {|i| Array === i}
>>> p = ary ? tree.index(ary) : nil
>>> if p.nil?
>>> tree.each_with_index {|d, i| parent[i] = d}
>>> else
>>> tree[0...p].each_with_index {|d, i| parent[i] = d}
>>> tree[p..-1].each {|d|
>>> node = @store.append(parent)
>>> import_tree_at(node, d) if Array === d
>>> }
>>> end
>>> end
>> I don't fully understand what your code does. I'm especially wondering
>> where from it gets the input.
>
> It's from a Gtk::SimpleTree class I'm writing; the point is to have the
> input in as lightweight a form as possible. Here's some sample client
> code:
>
> # define the tree
> s = Gtk::SimpleTree.new([String, String, Integer],
> ["First Name", 0],
> ["Last Name", 1,
> {:weight => Pango::FontDescription::WEIGHT_BOLD}],
> ["Age", format_age, {:foreground => "red"}],
> ["Age", simple_age])
>
> # define the initial data
> treedata = [
> ['Maria', 'Incognito'],
> ['Jane', 'Average', 1962,
> ['Janinita', 'Average', 1985]]]
>
> s.import_tree(treedata)
>
>
>> I'd probably create a proper tree class
>> with references to parent and children and do the import on top of that.
>> If you need to, you can still create nested arrays from that.
>
> The point is to enter the initial tree inline; there's already a proper
> tree class at the back end.

Ok, I though you were going to parse the tree from some representation.
If you still feel your code is awkward you can still create a helper
class for the import process. Just an idea. The one thing that struck
me odd about your code was this array referencing and indexing. But
that's probably necessary because your input is already a tree.

Kind regards

robert

Martin DeMello

6/12/2006 9:08:00 PM

Robert Klemme <bob.news@gmx.net> wrote:
>
> Ok, I though you were going to parse the tree from some representation.
> If you still feel your code is awkward you can still create a helper
> class for the import process. Just an idea. The one thing that struck
> me odd about your code was this array referencing and indexing. But
> that's probably necessary because your input is already a tree.

The awkwardness is specifically this: in C what I'd do is scan through
the array element by element, checking that the element was not an array
and adding it to the node's propertes. If I find an array, I set the
reading_children flag, and continue iterating, passing every array to
the recursive call and ignoring everything that isn't an array (just for
some extra safety). It's nice because it only involves a single pass
through the array.

I can do the same thing in ruby, but only by essentially writing C code
with a ruby syntax, conversely, attempts to write it in clean, idiomatic
ruby keep adding hidden constants to the running time (probably doesn't
matter in practice, but it's unsatisfying). What I *want* to write is

ix = ary.while {|i| !(Array === i)} {|i| add i to node data}
ary[ix..-1].select {|i| Array === i} {|i| recursively call self with i}

Which would be possible if methods could take more than one block - I
want one block for the predicate and one to be yielded to if the
predicate returns true. I could still approximate it with enumerators or
lambdas, I guess, but it feels weird to write Array#while and rewrite
Array#select and then only use them once.

martin

billmcn

6/12/2006 11:30:00 PM

Check out http://rubyforge.org/projects....

This is a general purpose tree handling module that has serialization
to and from a bracketed notation similiar to what you are using.

In particular you can look at the source for Treebank::Parser (visible
on rubyforge). I used a shift-reduce parser to initialize my tree
structures inline from strings. It's a very similiar problem. In fact,
you may even be able to use the Treebank::Parser class as is. Your
list of items could be passed into the constructor as the tokens
variable, and you'd have to pass in your own node class.

Even if you don't use that code, I think shift-reduce parsers are the
way to go here.

Martin DeMello wrote:
> Robert Klemme <bob.news@gmx.net> wrote:
> >
> > Ok, I though you were going to parse the tree from some representation.
> > If you still feel your code is awkward you can still create a helper
> > class for the import process. Just an idea. The one thing that struck
> > me odd about your code was this array referencing and indexing. But
> > that's probably necessary because your input is already a tree.
>
> The awkwardness is specifically this: in C what I'd do is scan through
> the array element by element, checking that the element was not an array
> and adding it to the node's propertes. If I find an array, I set the
> reading_children flag, and continue iterating, passing every array to
> the recursive call and ignoring everything that isn't an array (just for
> some extra safety). It's nice because it only involves a single pass
> through the array.
>
> I can do the same thing in ruby, but only by essentially writing C code
> with a ruby syntax, conversely, attempts to write it in clean, idiomatic
> ruby keep adding hidden constants to the running time (probably doesn't
> matter in practice, but it's unsatisfying). What I *want* to write is
>
> ix = ary.while {|i| !(Array === i)} {|i| add i to node data}
> ary[ix..-1].select {|i| Array === i} {|i| recursively call self with i}
>
> Which would be possible if methods could take more than one block - I
> want one block for the predicate and one to be yielded to if the
> predicate returns true. I could still approximate it with enumerators or
> lambdas, I guess, but it feels weird to write Array#while and rewrite
> Array#select and then only use them once.
>
> martin

Jens Auer

6/13/2006 8:11:00 AM

Robert Klemme wrote:
> Ok, I though you were going to parse the tree from some representation.
> If you still feel your code is awkward you can still create a helper
> class for the import process. Just an idea.
In case you want to build a helper class, you should have a look at the
Builder pattern (Gamma et al.). I would prefer it to construct the data
structure.

Robert Klemme

6/13/2006 11:34:00 AM

Martin DeMello wrote:
> Robert Klemme <bob.news@gmx.net> wrote:
>> Ok, I though you were going to parse the tree from some representation.
>> If you still feel your code is awkward you can still create a helper
>> class for the import process. Just an idea. The one thing that struck
>> me odd about your code was this array referencing and indexing. But
>> that's probably necessary because your input is already a tree.
>
> The awkwardness is specifically this: in C what I'd do is scan through
> the array element by element, checking that the element was not an array
> and adding it to the node's propertes. If I find an array, I set the
> reading_children flag, and continue iterating, passing every array to
> the recursive call and ignoring everything that isn't an array (just for
> some extra safety). It's nice because it only involves a single pass
> through the array.
>
> I can do the same thing in ruby, but only by essentially writing C code
> with a ruby syntax, conversely, attempts to write it in clean, idiomatic
> ruby keep adding hidden constants to the running time (probably doesn't
> matter in practice, but it's unsatisfying). What I *want* to write is
>
> ix = ary.while {|i| !(Array === i)} {|i| add i to node data}
> ary[ix..-1].select {|i| Array === i} {|i| recursively call self with i}

Why can't you just do this?

def parse(node, arr)
arr.each do |elem|
if Enumerable === elem
node.add_child_node( parse( Node.new( node ), elem ) )
else
node.add_child_data( elem )
end
end
node
end

> Which would be possible if methods could take more than one block - I
> want one block for the predicate and one to be yielded to if the
> predicate returns true. I could still approximate it with enumerators or
> lambdas, I guess, but it feels weird to write Array#while and rewrite
> Array#select and then only use them once.

I guess I'm overlooking something probably because I don't know the the
tree implementation you are using.

Kind regards

robert

Martin DeMello

6/14/2006 5:15:00 AM

Robert Klemme <bob.news@gmx.net> wrote:
> Martin DeMello wrote:
> > matter in practice, but it's unsatisfying). What I *want* to write is
> >
> > ix = ary.while {|i| !(Array === i)} {|i| add i to node data}
> > ary[ix..-1].select {|i| Array === i} {|i| recursively call self with i}
>
> Why can't you just do this?
>
> def parse(node, arr)
> arr.each do |elem|
> if Enumerable === elem

String includes Enumerable :(

> node.add_child_node( parse( Node.new( node ), elem ) )
> else
> node.add_child_data( elem )
> end
> end
> node
> end

But yeah, that's essentially what I ended up using, with a flag to note
that once you see the first child, you stop accepting node data. I just
disike having an entire loop body wrapped in a switch.

> I guess I'm overlooking something probably because I don't know the the
> tree implementation you are using.

It's not an implementation problem, just the fact that 'flagged'
behaviour in a loop is so ugly to code, and I was wondering if people
had come up with better ideas.

Note that trying to design a nice Array#while (or #take_while if you
prefer) really does present an interface design problem - either
1. you want a block for the predicate and a block to yield values to, or
2. you want to return the collection and the index at which it stopped

#1 can be got around by using foo(lambda {}) {} and #2 by returning the
collection and letting the user perform the extra step of retval.length
to see where it stopped, but both are (in the strictest sense of the
word) less than ideal.

martin

Martin DeMello

6/14/2006 5:28:00 AM

billmcn <billmcn@gmail.com> wrote:
> Check out http://rubyforge.org/projects....

Sounded interesting, but all there was was a gem, and it died with
Install required dependency fsa? [Yn] y
ERROR: While executing gem ... (Gem::GemNotFoundException)
Could not find fsa (> 0.0.0) in the repository

martin

Robert Klemme

6/15/2006 12:59:00 PM

Martin DeMello <martindemello@yahoo.com> wrote:
> Robert Klemme <bob.news@gmx.net> wrote:
>> Martin DeMello wrote:
>>> matter in practice, but it's unsatisfying). What I *want* to write
>>> is
>>>
>>> ix = ary.while {|i| !(Array === i)} {|i| add i to node data}
>>> ary[ix..-1].select {|i| Array === i} {|i| recursively call self
>>> with i}
>>
>> Why can't you just do this?
>>
>> def parse(node, arr)
>> arr.each do |elem|
>> if Enumerable === elem
>
> String includes Enumerable :(

Oh yes, my bad.

>> node.add_child_node( parse( Node.new( node ), elem ) )
>> else
>> node.add_child_data( elem )
>> end
>> end
>> node
>> end
>
> But yeah, that's essentially what I ended up using, with a flag to
> note that once you see the first child, you stop accepting node data.
> I just disike having an entire loop body wrapped in a switch.
>
>> I guess I'm overlooking something probably because I don't know the
>> the tree implementation you are using.
>
> It's not an implementation problem, just the fact that 'flagged'
> behaviour in a loop is so ugly to code, and I was wondering if people
> had come up with better ideas.

I don't find the solution above ugly. I'm not sure why you find it ugly. I
rather dislike the solution where you have to do array indexing because it's
less efficient.

> Note that trying to design a nice Array#while (or #take_while if you
> prefer) really does present an interface design problem - either
> 1. you want a block for the predicate and a block to yield values to,
> or

I'm not sure what exactly you want to achieve with Enumerable#while, but you
know that you can stop an iteration with "break" do you?

>> %w{aa bb cc dd}.each {|w| p w; break if /^b+$/ =~ w}
"aa"
"bb"
=> nil

Note that you can rewrite the method from your first posting simpler and
more efficiently as

def import_tree_at(parent, tree)
idx = tree.each_with_index {|e,i| break i if Array === e}
idx = tree.size unless Numeric === idx
tree.each_with_index do |d, i|
if i < idx
parent[i] = d
else
node = @store.append(parent)
import_tree_at(node, d) if Array === d
end
end
end

> 2. you want to return the collection and the index at which it stopped
>
> #1 can be got around by using foo(lambda {}) {} and #2 by returning
> the collection and letting the user perform the extra step of
> retval.length to see where it stopped, but both are (in the strictest
> sense of the word) less than ideal.

There is an easier and more elegant solution for #2: return multiple values.

coll, pos = arr.whatever

Kind regards

robert

comp.lang.ruby

Tree reading

Martin DeMello

Robert Klemme

Martin DeMello

Robert Klemme

Martin DeMello

billmcn

Jens Auer

Robert Klemme

Martin DeMello

Martin DeMello

Robert Klemme

x Login to ForumsZone