Beatnik has asked for the wisdom of the Perl Monks concerning the following question:

Hey, I'm deeply interested on how one would build a tree consisting of Objects. The following code actually works (which was kinda a surprise). Are they any pitfalls and hidden doors in the tree building + object concept? 
package Node;
use strict;

sub new {
 my $proto = shift;
 my $class = ref($proto) || $proto;
 my $self = {};
 $self->{NODES} = [];
 $self->{TITLE} = undef;
 bless($self,$class);
 return $self;
}

sub title {
 my $self = shift;
 if (@_) { $self->{TITLE} = shift; }
 return $self->{TITLE};
 }
 
sub add {
 my $self = shift;
 push(@{$self->{NODES}},shift);
}
    
sub nodes {
 my $self = shift;
 return @{$self->{NODES}};
}
    
1;

# -------

#!/usr/bin/perl -w

use strict;
use Node;

my $parent = Node->new();
$parent->title("Parent");
my $child1 = Node->new();
$child1->title("Child 1");
$parent->add($child1);
my $child2 = Node->new();
$child2->title("Child 2");
$parent->add($child2);
foreach my $ref ($parent->nodes)
{ print $ref->title; }

[download]


Greetz
Beatnik
... Quidquid perl dictum sit, altum viditur.

Replies are listed 'Best First'.
Re: Building an object tree
by unixwzrd (Beadle) on Feb 26, 2001 at 02:10 UTC
    You could get into trouble with memory leaks due to the garbage collection in Perl. It counts references to the variable and removes it when the count becomes zero.

    For instance, you might have a child node that was the parent for two other nodes. If were not careful when deleting the child, the childres for which it is the parent might still be allocated memory, and they would be inaccessible.

    I highly recommend Damian Conway's book "Object Oriented Perl". it goes into this subject quite well.

    Mike - mps@discomsys.com

    "The two most common elements in the universe are hydrogen... and stupidity."
    Harlan Ellison

[reply]
      As long as parents point to children, but not vica versa, when the parent goes away, its children will have their counts decremented and they go away as well.

      The problem only comes if children keep track of their parents. For instance consider a directory tree. Each directory uses "." and ".." to keep track of itself and its parent. What this means is that when the last external reference to a directory tree goes away, the tree hangs around because it refers to itself.

      If you wish to get around this you will need to be using Perl 5.6.x or higher, and you will need to install the WeakRef module. (OK, there are other ways, but this one is the simplest.) Then weaken all of the links that cause recursion, and no more memory leaks!

[reply]
        WeakRef looks great -- I've wanted something like this on several occasions. Unfortunately, it seems to require a patch to the Perl core. Any possibility of a weakening function becoming a standard part of Perl?
[reply]
      Thanks.
      I actually have the book (altho I should find more time to read it properly), and I believe it mentions the memory leak issue. The node level wont be as deep as it could get, since I realize loading objects in a tree can get quite resource consuming.

      Greetz
      Beatnik
      ... Quidquid perl dictum sit, altum viditur.
[reply]
Re: Building an object tree
by mirod (Canon) on Feb 26, 2001 at 13:41 UTC

    This is one way to build a tree-like structure, but there are others. My favorite is to have a complete tree, where each node has lonks to its parent, first and last child and previous and next sibling. Of course you then have to take care of circular references and provide a way to purge the tree, but in exchange you get ways to navigate the tree that are, I think, really convenient. In particular if you have a query language on the tree you really need to be able to go from a node to its neighbors. With the kind of tree you build in your example you are pretty much limited to traversing the entire tree any time you want to process any node. In the XML world you can look at the tree mode of XML::Parser or at XML::Simple for the kind of trees you are using, and at XML::DOM, XML::Twig and XML::XPath for the kind of tree I like. XML::XPath is especially interesting as it is based on Orchard, a tree manipulation module build in a C-like language that's supposed to be much faster than pure Perl.

    Here is an example of how to build a "strongly linked" tree:

    # This subroutine will adds a child as last child of parent:
  sub add_child
    { my( $parent, $child)= @_;
      my $prev_sibling= $parent->last_child;
      $child->{parent}= $parent;
      $parent->{last_child}= $child;
      $parent->{first_child}= $child unless( $parent->{first_child});
      if( $prev_sibling)
        { $child->{prev_sibling}= $prev_sibling ; 
          $prev_sibling->{next_sibling}= $child;
        }
    }

    [download]
[reply]
[d/l]

Back to Seekers of Perl Wisdom