Tree structure - how do we link nodes together?

[Aldric Giacomoni]

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

 

[Dylan Evans]

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

 

[Robert Klemme]

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

 

[Aldric Giacomoni]

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 Giacomoni]

[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]

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

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]

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

[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.denhaven2.com/articles/2006/09/13/on-variables-values-and-objects

 

[Robert Klemme]

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.ruby-doc.org/).

Cheers

robert

 

[Michael Malone]

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.ruby-doc.org/).

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]

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

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.denhaven2.com/
Twitter: http://twitter.com/RickDeNatale
WWR: http://www.workingwithrails.com/person/9021-rick-denatale
LinkedIn: http://www.linkedin.com/in/rickdenatale

 

[Gary Wright]

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

 

[Ken Bloom]

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?

The easiest equivalence is that essentially everything in Ruby is a
pointer and the . operator in Ruby is the equivalent of C++'s -> (This is
similar to how Java behaves as well.) The = operator changes where the
pointer points.

There's no such thing in Ruby as a pointer to a pointer, nor is there any
such thing as a variable that's not a pointer at all.

--Ken

 

[Robert Klemme]

I thought you were pretty clear in

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

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.

Well, there are several valid notions of "value" in the domain of
programming languages and it partly depends on the context which one you
choose. You could identify these

1. value, technical

These are the the "things" that you really see, i.e. object references.
This is the only thing you'll ever get to see from an object. These
are also the values meant when talking about call semantics (call by value).

2. values, practical

From a practical point of view much more important are objects because
those are the things that really carry state in Ruby. Whenever you
reason about a program and what it should do (or try to find out what it
does) you do this in terms of the objects living in the program -
although you never see one.

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.

Nevertheless, the drunken sailor pretty often reaches the harbour.

Kind regards

robert

 

[Dylan Evans]

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

[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

It's fairly common in the c/c++ world to implement tree's with arrays, a
matter of preference really, or in some cases it may be quicker to access a
node by it's index rather than searching through a linked list, or a pain
reallocating memory. Of course i don't know what your planning so i'm just
guessing, but you should be able to search with a recursive function. You
may also find a hash more convenient for accessing child nodes.

 

[Aldric Giacomoni]

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

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

Oh - DUH !
Thanks. Clearly I wasn't thinking straight.
--Aldric

 

[Aldric Giacomoni]

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

[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.denhaven2.com/articles/2006/09/13/on-variables-values-and-objects

Great little post.. Thanks, I'd forgotten some of the basics

 

[Aldric Giacomoni]

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.ruby-doc.org/).

Cheers

robert

I am .. I just had a complete brain fart on this! I understand perfectly
everything that's been mentioned now. Thank you so much for your help!

--Aldric

 

[Aldric Giacomoni]

The easiest equivalence is that essentially everything in Ruby is a
pointer and the . operator in Ruby is the equivalent of C++'s -> (This is
similar to how Java behaves as well.) The = operator changes where the
pointer points.

There's no such thing in Ruby as a pointer to a pointer, nor is there any
such thing as a variable that's not a pointer at all.

--Ken

Understood now. Thank you
--Aldrc

 

[Michal Suchanek]

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?

It depends .. if you are just making trees for the sake of trees (or
measuring something on them) you can go with the simple Node object or
an array structure that implements the nodes.

On the other hand you may use a hash and forget about trees completely
if your data is one flat value, and use multiple layers of hashes if
you have something like vectors or strings where you can split the
value into multiple parts naturally.

ie {1=>{1=>{0=>[1, 1, 0]}, 2=>{3=>[1, 2, 3]}}, 2=>{3=>{4=>[2, 3, 4]}}}

Thanks

Michal