[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Basic Tree Data Structure

Justin To

6/10/2008 5:04:00 PM

class Tree
attr_reader :value
def initialize(value)
@value = value
@children = []
end

def <<(value)
subtree = Tree.new(value)
@children << subtree
return subtree
end

end

t = Tree.new("Parent")
child1 = t << "Child 1"
child2 = t << "Child 2"
child2 << "Grandchild 2.1"
ggc1 = child1 << "Grandchild 1.1"
ggc1 << "Great Grand Child 1.1.1"
ggc2 = child1 << "Grandchild 1.2"
ggc2 << "Great Grand Child 1.2.1"

class Tree
def each
yield value
@children.each do |child_node|
child_node.each { |e| yield e } # mainly confuesd at this point
end
end
end

t.each { |x| puts x }


Hi, I'm a little confused about the algorithm used to display each item
in a tree...

at: child_node.each { |e| yield e }

when does the block { |e| yield e } come into play? Does the each method
for child_node occur first?

Thanks in advance!
--
Posted via http://www.ruby-....
13 Answers

Justin To

6/10/2008 5:47:00 PM

0

class Tree
attr_reader :value
def initialize(value)
@value = value
@children = []
end

def <<(value)
subtree = Tree.new(value)
@children << subtree
return subtree
end

end

t = Tree.new("Parent")
child1 = t << "Child 1"
child2 = t << "Child 2"
gc1 = child1 << "GC 1.1"

class Tree
def each
puts "1"
yield value
puts "2"
@children.each do |child_node|
puts "in child_node"
child_node.each { |e| puts "3"; yield e; }
end
end
end

t.each { |x| puts "t.each"; puts x }


OUTPUT:

1
t.each
Parent
2
in child_node
1
3
t.each
Child 1
2
in child_node
1
3 # why are there two 3's here??
3 # ????? Doesn't Child 1 only have one child in its array
@children??
t.each
GC 1.1
2
in child_node
1
3
t.each
Child 2
2


(^ comment)


Thanks in advance
--
Posted via http://www.ruby-....

Dustin Barker

6/10/2008 6:14:00 PM

0

Hi Justin,

The second 3 is the second iteration of the parent's child_nodes.each
- try replacing:

child_node.each { |e| puts "3"; yield e; }

with this:

child_node.each { |e| puts "3 #{value}"; yield e; }

to see which iteration belongs to which node.

-Dustin

On Jun 10, 2008, at 1:46 PM, Justin To wrote:

> class Tree
> attr_reader :value
> def initialize(value)
> @value = value
> @children = []
> end
>
> def <<(value)
> subtree = Tree.new(value)
> @children << subtree
> return subtree
> end
>
> end
>
> t = Tree.new("Parent")
> child1 = t << "Child 1"
> child2 = t << "Child 2"
> gc1 = child1 << "GC 1.1"
>
> class Tree
> def each
> puts "1"
> yield value
> puts "2"
> @children.each do |child_node|
> puts "in child_node"
> child_node.each { |e| puts "3"; yield e; }
> end
> end
> end
>
> t.each { |x| puts "t.each"; puts x }
>
>
> OUTPUT:
>
> 1
> t.each
> Parent
> 2
> in child_node
> 1
> 3
> t.each
> Child 1
> 2
> in child_node
> 1
> 3 # why are there two 3's here??
> 3 # ????? Doesn't Child 1 only have one child in its array
> @children??
> t.each
> GC 1.1
> 2
> in child_node
> 1
> 3
> t.each
> Child 2
> 2
>
>
> (^ comment)
>
>
> Thanks in advance
> --
> Posted via http://www.ruby-....
>

Justin To

6/10/2008 7:04:00 PM

0

Thanks Dustin, that clarifies one bit of the confusion, but I'm still
puzzled:

Output: Parent
in child node
3 Parent
Output: Child 1
in child node
3 Child 1
3 Parent # Q1: Why does it go through the Parent again?
Output: Grandchild 1.1

class Tree
def each
puts "1"
yield value # Q2: Which block does this invoke?
puts "2"
@children.each do |child_node|
puts "in child_node"
child_node.each { |e| puts "3"; yield e; } # Q3: Which block
does this
# yield invoke?
end
end
end

t.each { |x| puts "t.each"; puts x }

I'm trying hard to understand!! =D Thanks for the help!
--
Posted via http://www.ruby-....

Dustin Barker

6/10/2008 8:02:00 PM

0


No problem - so try out this snippet:

t = Tree.new("a")
t1 = t << "b"
t1 << "c"
t << "d"

class Tree
def each
yield value
@children.each do |child_node|
child_node.each { |e| yield "node:#{value} yields:#{e}" }
end
end
end

t.each { |x| puts "each:#{x}" }

here's some annotated output:

each:a # (a)
yield value
each:node:a yields:b # (b) yield value -
> (a) yield e
each:node:a yields:node:b yields:c # (c) yield value -> (b) yield
e -> (a) yield e
each:node:a yields:d # (d) yield value -
> (a) yield e

Seems like you're traversing correctly, I think the 1,2,3 output
might've been confusing. The output of this snippet illustrates how
the calls stack up - each yield returns to the caller, which in turn
yields to it's caller, and so on.

-Dustin

On Jun 10, 2008, at 3:04 PM, Justin To wrote:

> Thanks Dustin, that clarifies one bit of the confusion, but I'm still
> puzzled:
>
> Output: Parent
> in child node
> 3 Parent
> Output: Child 1
> in child node
> 3 Child 1
> 3 Parent # Q1: Why does it go through the Parent again?
> Output: Grandchild 1.1
>
> class Tree
> def each
> puts "1"
> yield value # Q2: Which block does this invoke?
> puts "2"
> @children.each do |child_node|
> puts "in child_node"
> child_node.each { |e| puts "3"; yield e; } # Q3: Which block
> does this
> # yield invoke?
> end
> end
> end
>
> t.each { |x| puts "t.each"; puts x }
>
> I'm trying hard to understand!! =D Thanks for the help!
> --
> Posted via http://www.ruby-....
>

Justin To

6/10/2008 8:59:00 PM

0

Output:
each:a
each: node:a yields:b
each: node:a yields: node:b yields:c
each: node:a yields:d

Ok, from this example, I don't know how the #{e} in "child_node.each {
|e| yield
"node:#{value} yields:#{e}" }" turns into "node:b yields:c" because the
#{e} isn't calling yield is it?

Sorry for the trouble, I just can't seem to understand...when I walk
through the algorithm with my logic it seems that it should just say
"each: node b yields c"...which is obviously not the correct output.

I'll continue reviewing your example, though, but if you can explain in
any other way, that'd be great. Thanks again!

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

Dustin Barker

6/10/2008 9:39:00 PM

0


On Jun 10, 2008, at 4:58 PM, Justin To wrote:

> Output:
> each:a
> each: node:a yields:b
> each: node:a yields: node:b yields:c
> each: node:a yields:d
>
> Ok, from this example, I don't know how the #{e} in "child_node.each {
> |e| yield
> "node:#{value} yields:#{e}" }" turns into "node:b yields:c" because
> the
> #{e} isn't calling yield is it?

That's right, the e doesn't call yield - the 'each' in child_node.each
does. Remember that you're calling Tree#each here, so the value of 'e'
is whatever is yielded by the 'each' method. You'll have as many e's
as you have yields.

> Sorry for the trouble, I just can't seem to understand...when I walk
> through the algorithm with my logic it seems that it should just say
> "each: node b yields c"...which is obviously not the correct output.

So if remove the debug statements:

class Tree
def each
yield value
@children.each do |child_node|
child_node.each { |e| yield e }
end
end
end

t.each { |x| puts x }

I get:

a
b
c
d

Is that the iteration you're looking for? If so - let's walk through it:

t.each
-- yield value # node a is
yielding 'a' to t.each
puts x #
t.each outputs 'a'
-- @children.each do |child_node| # iterating children of node a
---- child_node.each # calling
Tree#each for first child of a, which is node b
------ yield value # node b is
yielding 'b'
---- yield e # node a
got e='b', so yielding 'b' to t.each
puts x #
t.each outputs 'b'
------ @children.each do |child_node| # iterating children of node b
-------- child_node.each # calling Tree#each
for first child of b, which is node c
---------- yield value # node c is
yielding 'c'
------ yield e # node b
got e='c', so yielding 'c' to node a
---- yield e # node
a got e='c', so yielding 'c' to t.each
puts x #
outputs 'c'

>
>
> I'll continue reviewing your example, though, but if you can explain
> in
> any other way, that'd be great. Thanks again!
>

No problem - it's a tough topic, hopefully the illustration of the
calls above helps!

-Dustin

Dustin Barker

6/10/2008 9:47:00 PM

0

Reposting - forgot to send as plain text and the message was
illegible! ;-)

On Jun 10, 2008, at 4:58 PM, Justin To wrote:

> Output:
> each:a
> each: node:a yields:b
> each: node:a yields: node:b yields:c
> each: node:a yields:d
>
> Ok, from this example, I don't know how the #{e} in "child_node.each {
> |e| yield
> "node:#{value} yields:#{e}" }" turns into "node:b yields:c" because
> the
> #{e} isn't calling yield is it?

That's right, the e doesn't call yield - the 'each' in child_node.each
does. Remember that you're calling Tree#each here, so the value of 'e'
is whatever is yielded by the 'each' method. You'll have as many e's
as you have yields.

> Sorry for the trouble, I just can't seem to understand...when I walk
> through the algorithm with my logic it seems that it should just say
> "each: node b yields c"...which is obviously not the correct output.

So if remove the debug statements:

class Tree
def each
yield value
@children.each do |child_node|
child_node.each { |e| yield e }
end
end
end

t.each { |x| puts x }

I get:

a
b
c
d

Is that the iteration you're looking for? If so - let's walk through it:

t.each
-- yield value # node a is yielding 'a' to t.each
puts x # t.each outputs 'a'
-- @children.each do |child_node| # iterating children of node a
---- child_node.each # calling Tree#each for first
child of a, which is node b
------ yield value # node b is yielding 'b'
---- yield e # node a got e='b', so yielding
'b' to t.each
puts x # t.each outputs 'b'
------ @children.each do |child_node| # iterating children of node b
-------- child_node.each # calling Tree#each for first
child of b, which is node c
---------- yield value # node c is yielding 'c'
------ yield e # node b got e='c', so yielding
'c' to node a
---- yield e # node a got e='c', so yielding
'c' to t.each
puts x # outputs 'c'

>
>
> I'll continue reviewing your example, though, but if you can explain
> in
> any other way, that'd be great. Thanks again!

No problem - it's a tough topic, hopefully the illustration of the
calls above helps!

-Dustin

Justin To

6/10/2008 10:16:00 PM

0

Your illustration definetely helps. I guess my ultimate confusion comes
from the last two yields to e:

1. yield e # node b got e='c', so yielding #yielding to t.teach?
2. yield e # node a got e='c', so yielding

For #1, e='c' so why doesn't it yield that 'c' to t.each and puts 'c'

You've helped a lot and done all you could. It'll just be up to me to
try to wrap my mind around it.

Thanks for the extended help...will definitely post back when I figure
it out! =)
--
Posted via http://www.ruby-....

Dustin Barker

6/10/2008 11:16:00 PM

0


On Jun 10, 2008, at 6:16 PM, Justin To wrote:

> Your illustration definetely helps. I guess my ultimate confusion
> comes
> from the last two yields to e:
>
>
> 1. yield e # node b got e='c', so yielding #yielding to t.teach?
> 2. yield e # node a got e='c', so yielding

---------- yield value # node c is yielding 'c'
------ yield e # node b got e='c', so yielding 'c' to node a
---- yield e # node a got e='c', so yielding 'c' to t.each

>
>
> For #1, e='c' so why doesn't it yield that 'c' to t.each and puts 'c'

It does, but by way of node b and node a. So let's try with different
code:

def foo
bar { |x| yield "foo #{x}" }
end

def bar
baz { |x| yield "bar #{x}" }
end

def baz
yield "baz"
end

foo { |x| puts x }

output: foo bar baz

>
>
> You've helped a lot and done all you could. It'll just be up to me to
> try to wrap my mind around it.

No problem - good luck!

-Dustin

Justin To

6/10/2008 11:41:00 PM

0

GREAT!! That new example demystified the whole problem for me! Finally!!
=D

Thanks a bunch Dustin!
--
Posted via http://www.ruby-....