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


 

Forums >

comp.lang.ruby

Tree structure - how do we link nodes together?

aldric[removeme]

2/18/2009 1:25:00 AM

I know I could just use rubytree, which looks quite nice, but I'd like
to see what you guys would do about creating a tree and linking the
nodes together.
In C++ we'd just make pointers, so how would we do the equivalent in Ruby?

--Aldric
18 Answers

Dylan Evans

2/18/2009 4:10:00 AM

0

[Note: parts of this message were removed to make it a legal post.]

I would be inclined to use an array, part of the beauty of dynamic languages
is the typeless nature of arrays which does away with a lot of management
code, in c++ trees i normally write a base node class then branch and leaf
nodes which is a lot of work compared to [x, [y, z]]
Of course if you wanted to create branch nodes for some custom purpose then
you could just assign the children to it since they are passed by reference.

On Wed, Feb 18, 2009 at 11:30 AM, Aldric Giacomoni <"aldric[removeme]"@
trevoke.net> wrote:

> I know I could just use rubytree, which looks quite nice, but I'd like
> to see what you guys would do about creating a tree and linking the
> nodes together.
> In C++ we'd just make pointers, so how would we do the equivalent in Ruby?
>
> --Aldric
>
>


--
The UNIX system has a command, nice ... in order to be nice to the other
users. Nobody ever uses it." - Andrew S. Tanenbaum

Robert Klemme

2/18/2009 12:13:00 PM

0

2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:
> I know I could just use rubytree, which looks quite nice, but I'd like
> to see what you guys would do about creating a tree and linking the
> nodes together.
> In C++ we'd just make pointers, so how would we do the equivalent in Ruby?

We use object references - as always when referring other objects.
Ruby does not have the multitude of options that C++ has.

Cheers

robert


--
remember.guy do |as, often| as.you_can - without end

aldric[removeme]

2/18/2009 2:18:00 PM

0

Robert Klemme wrote:
> 2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:
>
>> I know I could just use rubytree, which looks quite nice, but I'd like
>> to see what you guys would do about creating a tree and linking the
>> nodes together.
>> In C++ we'd just make pointers, so how would we do the equivalent in Ruby?
>>
>
> We use object references - as always when referring other objects.
> Ruby does not have the multitude of options that C++ has.
>
> Cheers
>
> robert
>
>
>
Alright, Robert - I don't know how that works in Ruby! Would you provide
me with a simple example, explain it, or point me to something that
explains it, please?

Thanks,

--Aldric

aldric[removeme]

2/18/2009 2:28:00 PM

0

Dylan Evans wrote:
> [Note: parts of this message were removed to make it a legal post.]
>
> I would be inclined to use an array, part of the beauty of dynamic languages
> is the typeless nature of arrays which does away with a lot of management
> code, in c++ trees i normally write a base node class then branch and leaf
> nodes which is a lot of work compared to [x, [y, z]]
> Of course if you wanted to create branch nodes for some custom purpose then
> you could just assign the children to it since they are passed by reference.
>
>
How would .. passing the children by reference work? Is that the same
thing that Robert is talking about?
The idea of an array is simple enough that it might work.. I should be
able to write something to handle however many layers deep the arrays
go.. But I think a tree may be a little handier to handle things like
deleting a node and its children.
--Aldric

Glen Holcomb

2/18/2009 2:30:00 PM

0

[Note: parts of this message were removed to make it a legal post.]

On Wed, Feb 18, 2009 at 7:20 AM, Aldric Giacomoni <"aldric[removeme]"@
trevoke.net> wrote:

> Robert Klemme wrote:
> > 2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:
> >
> >> I know I could just use rubytree, which looks quite nice, but I'd like
> >> to see what you guys would do about creating a tree and linking the
> >> nodes together.
> >> In C++ we'd just make pointers, so how would we do the equivalent in
> Ruby?
> >>
> >
> > We use object references - as always when referring other objects.
> > Ruby does not have the multitude of options that C++ has.
> >
> > Cheers
> >
> > robert
> >
> >
> >
> Alright, Robert - I don't know how that works in Ruby! Would you provide
> me with a simple example, explain it, or point me to something that
> explains it, please?
>
> Thanks,
>
> --Aldric
>
>
Pretty Simple really:

class Node
attr_accessor :data
attr_accessor :left
attr_accessor :right
end

root = Node.new

node1 = Node.new

root.data = "rob"
node1.data = "tim"
root.right = node1

Rick DeNatale

2/18/2009 4:55:00 PM

0

[Note: parts of this message were removed to make it a legal post.]

On Wed, Feb 18, 2009 at 9:29 AM, Aldric Giacomoni <"aldric[removeme]"@
trevoke.net> wrote:

> Dylan Evans wrote:
> > [Note: parts of this message were removed to make it a legal post.]
> >
> > I would be inclined to use an array, part of the beauty of dynamic
> languages
> > is the typeless nature of arrays which does away with a lot of management
> > code, in c++ trees i normally write a base node class then branch and
> leaf
> > nodes which is a lot of work compared to [x, [y, z]]
> > Of course if you wanted to create branch nodes for some custom purpose
> then
> > you could just assign the children to it since they are passed by
> reference.
> >
> >
> How would .. passing the children by reference work?


Ruby is a uniformly object oriented language, all values are object
references. Variables, and parameters are simply named references to
objects, not the objects themselves. Individual slots in an array also hold
reverences to objects rather than the objects themselves, they just don't
have names.

So everything is passed by object reference. This is not the same thing as
passing by referernce in a language like C, although the differences can be
subtle.

Here's an oldie but goody of mine which might help understand the
relationship between variables, values, and objects.

http://talklikeaduck.denh...articles/2006/09/13/on-variables-values-a...


--
Rick DeNatale

Blog: http://talklikeaduck.denh...
Twitter: http://twitter.com/Ri...

Robert Klemme

2/18/2009 9:53:00 PM

0

On 18.02.2009 15:18, Aldric Giacomoni wrote:
> Robert Klemme wrote:
>> 2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:
>>
>>> I know I could just use rubytree, which looks quite nice, but I'd like
>>> to see what you guys would do about creating a tree and linking the
>>> nodes together.
>>> In C++ we'd just make pointers, so how would we do the equivalent in Ruby?
>>>
>> We use object references - as always when referring other objects.
>> Ruby does not have the multitude of options that C++ has.

> Alright, Robert - I don't know how that works in Ruby! Would you provide
> me with a simple example, explain it, or point me to something that
> explains it, please?

I wasn't aware that you were after _such_ basic information. Actually,
since you mentioned using rubytree I assumed that you are familiar with
the language. The simplest and most basic form of a relation between
two objects is probably:

class Foo
def set(x)
@the_other = x
end
end

f = Foo.new
x = Foo.new
f.set(x)

Now f references x.

I suggest you get your hands on David's new book once it is out and in
the meantime consult those various introductory documents (can be found
via http://www.rub...).

Cheers

robert

Michael Malone

2/18/2009 10:09:00 PM

0

Robert Klemme wrote:
> On 18.02.2009 15:18, Aldric Giacomoni wrote:
>> Robert Klemme wrote:
>>> 2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:
>>>
>>>> I know I could just use rubytree, which looks quite nice, but I'd like
>>>> to see what you guys would do about creating a tree and linking the
>>>> nodes together.
>>>> In C++ we'd just make pointers, so how would we do the equivalent
>>>> in Ruby?
>>>>
>>> We use object references - as always when referring other objects.
>>> Ruby does not have the multitude of options that C++ has.
>
>> Alright, Robert - I don't know how that works in Ruby! Would you provide
>> me with a simple example, explain it, or point me to something that
>> explains it, please?
>
> I wasn't aware that you were after _such_ basic information.
> Actually, since you mentioned using rubytree I assumed that you are
> familiar with the language. The simplest and most basic form of a
> relation between two objects is probably:
>
> class Foo
> def set(x)
> @the_other = x
> end
> end
>
> f = Foo.new
> x = Foo.new
> f.set(x)
>
> Now f references x.
>
> I suggest you get your hands on David's new book once it is out and in
> the meantime consult those various introductory documents (can be
> found via http://www.rub...).
>
> Cheers
>
> robert
>
Essentially, the main information you require is that, everything in
Ruby is an object, and every object is actually a reference to an object.

so
class Foo

attr_reader :the_other

def set(x)
@the_other = x
end
end

f = Foo.new
bar = f
bar.the_other => nil
x = Foo.new
f.set(x)
bar.the_other => x

It helps me to think of references and the objects they point to as
separate entities (I'm unsure of the truthfulness of this). It's the
opposite of c++ really. c++ requires you to explicitly state you want
pass-by-reference and Ruby requires you to state pass-by-value (which
ends up in the form of a .dup call all the times I've ever wanted to use
it, which is less often than you might think)

Cheers,
Michael

=======================================================================
This email, including any attachments, is only for the intended
addressee. It is subject to copyright, is confidential and may be
the subject of legal or other privilege, none of which is waived or
lost by reason of this transmission.
If the receiver is not the intended addressee, please accept our
apologies, notify us by return, delete all copies and perform no
other act on the email.
Unfortunately, we cannot warrant that the email has not been
altered or corrupted during transmission.
=======================================================================

Rick DeNatale

2/18/2009 10:34:00 PM

0

[Note: parts of this message were removed to make it a legal post.]

On Wed, Feb 18, 2009 at 5:08 PM, Michael Malone
<michael.malone@tait.co.nz>wrote:

> Essentially, the main information you require is that, everything in Ruby
> is an object, and every object is actually a reference to an object.
>

Actually, no.

The value of any expression is an object.

Every object consists of references to objects.

Variables and parameters are named references to objects.

Assignment transfers the reference to the object, not the object itself.

--
Rick DeNatale

Blog: http://talklikeaduck.denh...
Twitter: http://twitter.com/Ri...
WWR: http://www.workingwithrails.com/person/9021-ric...
LinkedIn: http://www.linkedin.com/in/ri...

Gary Wright

2/18/2009 10:48:00 PM

0


On Feb 18, 2009, at 5:33 PM, Rick DeNatale wrote:
> Actually, no.
>
> The value of any expression is an object.

I thought you were pretty clear in

<http://talklikeaduck.denhaven2.com/articles/2006/09/13/on-variables-values-a...
>

that values in Ruby are references, not objects. That
posting is one of the nicest expositions on Ruby's object
model that I've seen.

It took me quite a while to get a good mental picture of
Ruby's object model. Part of the problem was that the
community doesn't (or didn't) seem to have a consensus
on terminology in this area. Discussions about values,
references, expressions, objects, assignment semantics,
immutable types, symbols, identity,
and so on often resemble a druken sailor's random walk
rather than an simple, easily followed narrative.