NAME

Tree::Simple - A simple recursive tree object

SYNOPSIS

  use Tree::Simple;
  
  # make a tree root
  my $tree = Tree::Simple->new(Tree::Simple->ROOT);
  
  # explicity add a child to it
  $tree->addChild(Tree::Simple->new("1"));
  
  # specify the parent when creating
  # the child and add the child implicity
  my $sub_tree = Tree::Simple->new("2", $tree);
  
  # chain method calls
  $tree->getChild(0)->addChild(Tree::Simple->new("1.1"));
  
  # add more than one child at a time
  $sub_tree->addChildren(
            Tree::Simple->new("2.1"),
            Tree::Simple->new("2.2")
            );

  # add siblings
  $sub_tree->addSibling(Tree::Simple->new("3"));
  
  # insert children a specified index
  $sub_tree->insertChild(1, Tree::Simple->new("2.1a"));

DESCRIPTION

This module implements a simple recursive hierarchal tree-like object structure. It is built upon the idea of parent-child relationships, so therefore every Tree::Simple object has both a parent and a set of children (who themselves have children, and so on).

CONSTANTS

ROOT

This class constant serves as a placeholder for the root of our tree.

METHODS

Constructor

new ($node, $parent)

The constructor accepts two arguments a $node value and an optional $parent. The $node value can be any scalar value (which includes references and objects). The optional $parent value must be a Tree::Simple object, or an object derived from Tree::Simple. Setting this value implies that your new tree is a child of the parent tree, and therefore adds it to the parent's children. If the $parent is not specified then its value defaults to ROOT.

Private Methods

_init ($node, $parent, $children)

This method is here largely to facilitate subclassing. This method is called by new to initialize the object, where new's primary responsibility is creating the instance.

_setParent ($parent)

This method sets up the parental relationship. It is for internal use only.

Mutators

setNodeValue ($node_value)

This sets the node value to the scalar $node_value, an exception is thrown if $node_value is not defined.

addChild ($tree)

This method accepts only Tree::Simple objects or objects derived from Tree::Simple, an exception is thrown otherwise. This method will append the given $tree to the end of the children list, and set up the correct parent-child relationships. This method is set up to return its invocant so that method call chaining can be possible. Such as:

  my $tree = Tree::Simple->new("root")->addChild(Tree::Simple->new("child one"));

Or the more complex:

  my $tree = Tree::Simple->new("root")->addChild(
                         Tree::Simple->new("1.0")->addChild(
                                     Tree::Simple->new("1.0.1")     
                                     )
                         );

addChildren (@trees)

This method accepts an array of Tree::Simple objects, and adds them to the children list. Like addChild this method will return its invocant to allow for method call chaining.

insertChild ($index, $tree)

This method accepts a numeric $index and a Tree::Simple object ($tree), and inserts the $tree into the children list at the specified $index. This results in the shifting down of all children after the $index. The $index is checked to be sure it is the bounds of the child list. The $tree argument's type is verified to be a Tree::Simple or Tree::Simple derived object. If either of these two conditions fail, an exception is thrown.

insertChildren ($index, @trees)

This method functions much as insertChild does, but instead of inserting a single Tree::Simple, it inserts an array of Tree::Simple objects. It too bounds checks the value of $index and type checks the objects in @trees.

removeChild ($index)

This method accepts a numeric $index and removes the $tree from the children list at the specified $index. This results in the shifting up of all children after the $index. The $index is checked to be sure it is the bounds of the child list, if this condition fail, an exception is thrown. The removed child is then returned.

addSibling ($tree)

addSiblings (@trees)

insertSibling ($index, $tree)

insertSiblings ($index, @trees)

The addSibling, addSiblings, insertSibling and insertSiblings methods pass along their arguments to the addChild, addChildren, insertChild and insertChildren methods of their parent object respectively. This eliminates the need to overload these methods in subclasses which may have specialized versions of the *Child(ren) methods. The one execeptions is that if an attempt it made to add or insert siblings to the ROOT of the tree then an exception is thrown.

NOTE: There is no removeSibling method as I felt it was probably a bad idea. The same effect can be achieved by manual upwards traversal.

Accessors

getNodeValue

This returns the value stored in the object's node field.

getChild ($index)

This returns the child (a Tree::Simple object) found at the specified $index. Note that we do use standard zero-based array indexing.

getAllChildren

This returns an array of all the children (all Tree::Simple objects). It will return an array reference in scalar context.

getSibling ($index)

getAllSiblings

Much like addSibling and addSiblings, these two methods simply call getChild and getAllChildren on the invocant's parent.

getDepth

Returns a number representing the invocant's depth within the heirarchy of Tree::Simple objects.

getParent

Returns the invocant's parent, which could be either ROOT or a Tree::Simple object.

getChildCount

Returns the number of children the invocant contains.

Predicates

isLeaf

Returns true (1) if the invocant does not have any children, false (0) otherwise.

isRoot

Returns true (1) if the invocant's parent is ROOT, returns false (0) otherwise.

Misc. Functions

traverse (CODE)

This method takes a single arguement of a subroutine reference $func. If the argument is not defined and is not infact a CODE reference then an exception is thrown. The function is them applied recursively to all the children of the invocant. Here is an example of a traversal function that will print out the hierarchy as a tabed in list.

  $tree->traverse(sub {
        my ($_tree) = @_;
        print (("\t" x $_tree->getDepth()), $_tree->getNodeValue(), "\n");
        });

accept ($visitor)

It accepts a Tree::Simple::Visitor object (or somethings derived from a Tree::Simple::Visitor) and runs the Visitor's visit method. We verify with an assertion that it is in fact a valid Tree::Simple::Visitor object and that it does have a method visit at its disposal.

clone

The clone method does a full deep-copy clone of the object, calling clone recursively on all its children. This does not call clone on the parent object however. Doing this would result in a slowly degenerating spiral of recursive death, so it is not recommended and therefore not implemented. What it does do is to copy the parent reference, which is a much more sensable act, and tends to be closer to what we are looking for. This can be a very expensive operation, and should only be undertaken with great care. More often than not, this method will not be appropriate. I recommend using the cloneShallow method instead.

cloneShallow

This method is an alternate option to the plain clone method. This method allows the cloning of single Tree::Simple object while retaining connections to the rest of the tree/heirarchy. This will attempt to call clone on the invocant's node if the node is an object (and responds to $obj-can('clone')>) otherwise it will just copy it.

DESTROY

To avoid memory leaks through uncleaned-up circular references, we implement the DESTROY method. This method will attempt to call DESTROY on each of its children (if it as any). This will result in a cascade of calls to DESTORY on down the tree. This may not be a good idea, we will have to see how it works out in practice.

SEE ALSO

Tree::Simple::Visitor

AUTHOR

stevan little, <stevan@iinteractive.com>

COPYRIGHT AND LICENSE

Copyright 2004 by Infinity Interactive, Inc.

http://www.iinteractive.com

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.