Tree structure - how do we link nodes together?

ruby-talk
1

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

2

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

3

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

Cheers

robert

···

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?

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

4

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

···

On Tue, 17 Feb 2009 20:25:28 -0500, Aldric Giacomoni 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?

--
Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

5

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

···

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?

6

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

7

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

8

Ken Bloom wrote:

···

On Tue, 17 Feb 2009 20:25:28 -0500, Aldric Giacomoni 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?
    
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 :slight_smile:
--Aldrc

9

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

.
.
.

···

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

--
"Hey brother Christian with your high and mighty errand, Your actions speak
so loud, I can't hear a word you're saying."

-Greg Graffin (Bad Religion)

10

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

···

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?

--
Rick DeNatale

Blog: http://talklikeaduck.denhaven2.com/
Twitter: http://twitter.com/RickDeNatale

11

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

···

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?

12

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

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.

go.. But I think a tree may be a little handier to handle things like
deleting a node and its children.

Check out Array#delete<class Array - RDoc Documentation;

···

On Thu, Feb 19, 2009 at 12:29 AM, Aldric Giacomoni <"aldric[removeme]"@ trevoke.net> wrote:

--Aldric

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

13

Robert Klemme wrote:

Robert Klemme 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?
    

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

···

On 18.02.2009 15:18, Aldric Giacomoni wrote:

2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:

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

14

Glen Holcomb wrote:

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

Robert Klemme 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?
    

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

···

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

2009/2/18 Aldric Giacomoni <"aldric[removeme]"@trevoke.net>:

15

Rick DeNatale wrote:

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

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

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

···

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

16

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

17

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.

···

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.

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

18

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.

···

On Feb 18, 2009, at 5:33 PM, Rick DeNatale wrote:

19

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.

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. :slight_smile:

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. :slight_smile:

Kind regards

  robert

···

On 18.02.2009 23:48, Gary Wright wrote:

On Feb 18, 2009, at 5:33 PM, Rick DeNatale wrote:

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