Provided by: libtree-perl_1.01-0ubuntu2_all 
NAME
Tree - an N-ary tree
SYNOPSIS
my $tree = Tree->new( 'root' );
my $child = Tree->new( 'child' );
$tree->add_child( $child );
$tree->add_child( { at => 0 }, Tree->new( 'first child' ) );
$tree->add_child( { at => -1 }, Tree->new( 'last child' ) );
$tree->set_value( 'toor' );
my $value = $tree->value;
my @children = $tree->children;
my @some_children = $tree->children( 0, 2 );
my $height = $tree->height;
my $width = $tree->width;
my $depth = $tree->depth;
my $size = $tree->size;
if ( $tree->has_child( $child ) ) {
$tree->remove_child( $child );
}
$tree->remove_child( 0 );
my @nodes = $tree->traverse( $tree->POST_ORDER );
my $clone = $tree->clone;
my $mirror = $tree->clone->mirror;
$tree->add_event_handler({
add_child => sub { ... },
remove_child => sub { ... },
value => sub { ... },
});
DESCRIPTION
This is meant to be a full-featured N-ary tree representation with configurable error-
handling and a simple events system that allows for transparent persistence to a variety
of datastores. It is derived from Tree::Simple, but has a simpler interface and much, much
more.
METHODS
Constructor
new([$value])
This will return a Tree object. It will accept one parameter which, if passed, will
become the value (accessible by "value()"). All other parameters will be ignored.
If you call "$tree->new([$value])", it will instead call "clone()", then set the value
of the clone to $value.
clone()
This will return a clone of $tree. The clone will be a root tree, but all children
will be cloned.
If you call Tree->clone([$value]), it will instead call "new()".
NOTE: the value is merely a shallow copy. This means that all references will be kept.
Behaviors
add_child([$options], @nodes)
This will add all the @nodes as children of $tree. $options is a optional unblessed
hashref that specifies options for add_child(). The optional parameters are:
• at
This specifies the index to add @nodes at. If specified, this will be passed into
splice(). The only exceptions are if this is 0, it will act as an unshift(). If it
is unset or undefined, it will act as a push().
remove_child([$options], @nodes)
This will remove all the @nodes from the children of $tree. You can either pass in the
actual child object you wish to remove, the index of the child you wish to remove, or
a combination of both.
$options is a optional unblessed hashref that specifies parameters for remove_child().
Currently, no parameters are used.
mirror()
This will modify the tree such that it is a mirror of what it was before. This means
that the order of all children is reversed.
NOTE: This is a destructive action. It will modify the tree's internal structure. If
you wish to get a mirror, yet keep the original tree intact, use "my $mirror =
$tree->clone->mirror;"
traverse( [$order] )
This will return a list of the nodes in the given traversal order. The default
traversal order is pre-order.
The various traversal orders do the following steps:
• Pre-order (aka Prefix traversal)
This will return the node, then the first sub tree in pre-order traversal, then
the next sub tree, etc.
Use "$tree->PRE_ORDER" as the $order.
• Post-order (aka Prefix traversal)
This will return the each sub-tree in post-order traversal, then the node.
Use "$tree->POST_ORDER" as the $order.
• Level-order (aka Prefix traversal)
This will return the node, then the all children of the node, then all
grandchildren of the node, etc.
Use "$tree->LEVEL_ORDER" as the $order.
All behaviors will reset last_error().
State Queries
• is_root()
This will return true is $tree has no parent and false otherwise.
• is_leaf()
This will return true is $tree has no children and false otherwise.
• has_child(@nodes)
This will return true is $tree has each of the @nodes as a child. Otherwise, it will
return false.
• get_index_for(@nodes)
This will return the index into the children list for each of the @nodes passed in.
Accessors
• parent()
This will return the parent of $tree.
• children( [ $idx, [$idx, ..] ] )
This will return the children of $tree. If called in list context, it will return all
the children. If called in scalar context, it will return the number of children.
You may optionally pass in a list of indices to retrieve. This will return the
children in the order you asked for them. This is very much like an arrayslice.
• root()
This will return the root node of the tree that $tree is in. The root of the root node
is itself.
• height()
This will return the height of $tree. A leaf has a height of 1. A parent has a height
of its tallest child, plus 1.
• width()
This will return the width of $tree. A leaf has a width of 1. A parent has a width
equal to the sum of all the widths of its children.
• depth()
This will return the depth of $tree. A root has a depth of 0. A child has the depth of
its parent, plus 1.
This is the distance from the root. It's useful for things like pretty-printing the
tree.
• size()
This will return the number of nodes within $tree. A leaf has a size of 1. A parent
has a size equal to the 1 plus the sum of all the sizes of its children.
• value()
This will return the value stored in the node.
• set_value([$value])
This will set the value stored in the node to $value, then return $self.
• meta()
This will return a hashref that can be used to store whatever metadata the client
wishes to store. For example, Tree::Persist::DB uses this to store database row ids.
It is recommended that you store your metadata in a subhashref and not in the top-
level metadata hashref, keyed by your package name. Tree::Persist does this, using a
unique key for each persistence layer associated with that tree. This will help
prevent clobbering of metadata.
ERROR HANDLING
Describe what the default error handlers do and what a custom error handler is expected to
do.
Error-related methods
• error_handler( [ $handler ] )
This will return the current error handler for the tree. If a value is passed in, then
it will be used to set the error handler for the tree.
If called as a class method, this will instead work with the default error handler.
• error( $error, [ arg1 [, arg2 ...] ] )
Call this when you wish to report an error using the currently defined error_handler
for the tree. The only guaranteed parameter is an error string describing the issue.
There may be other arguments, and you may certainly provide other arguments in your
subclass to be passed to your custom handler.
• last_error()
If an error occurred during the last behavior, this will return the error string. It
is reset only when a behavior is called.
Default error handlers
QUIET
Use this error handler if you want to have quiet error-handling. The last_error method
will retrieve the error from the last operation, if there was one. If an error occurs,
the operation will return undefined.
WARN
DIE
EVENT HANDLING
Forest provides for basic event handling. You may choose to register one or more callbacks
to be called when the appropriate event occurs. The events are:
• add_child
This event will trigger as the last step in an add_child() call.
The parameters will be "( $self, @args )" where @args is the arguments passed into the
add_child() call.
• remove_child
This event will trigger as the last step in an remove_child() call.
The parameters will be "( $self, @args )" where @args is the arguments passed into the
remove_child() call.
• value
This event will trigger as the last step in a set_value() call.
The parameters will be "( $self, $old_value )" where $old_value is what the value was
before it was changed. The new value can be accessed through "$self->value()".
Event handling methods
• add_event_handler( $type = $callback [, $type => $callback, ... ])>
You may choose to add event handlers for any known type. Callbacks must be references
to subroutines. They will be called in the order they are defined.
• event( $type, $actor, @args )
This will trigger an event of type $type. All event handlers registered on $tree will
be called with parameters of "($actor, @args)". Then, the parent will be notified of
the event and its handlers will be called, on up to the root.
This allows you specify an event handler on the root and be guaranteed that it will
fire every time the appropriate event occurs anywhere in the tree.
NULL TREE
If you call "$self->parent" on a root node, it will return a Tree::Null object. This is an
implementation of the Null Object pattern optimized for usage with Tree. It will evaluate
as false in every case (using overload) and all methods called on it will return a
Tree::Null object.
Notes
• Tree::Null does not inherit from Tree. This is so that all the methods will go through
AUTOLOAD vs. the actual method.
• However, calling isa() on a Tree::Null object will report that it is-a any object that
is either Tree or in the Tree:: hierarchy.
• The Tree::Null object is a singleton.
• The Tree::Null object is defined, though. I couldn't find a way to make it evaluate as
undefined. That may be a good thing.
CIRCULAR REFERENCES
Please q.v. Forest for more info on this topic.
WHAT'S NOT HERE
• The Visitor pattern
I have deliberately chosen to not implement the Visitor pattern as described by Gamma
et al. Given a sufficiently powerful "traverse()" and Perl's capabilities, an explicit
visitor object is almost always unneeded. If you want one, it's easy to write one
yourself. Here's a simple one I wrote in 5 minutes:
package My::Visitor;
sub new {
my $class = shift;
my $opts = @_;
return bless {
tree => $opts->{tree},
action => $opts->{action},
}, $class;
}
sub visit {
my $self = shift;
my ($mode) = @_;
foreach my $node ( $self->{tree}->traverse( $mode ) ) {
$self->{action}->( $node );
}
}
CODE COVERAGE
We use Devel::Cover to test the code coverage of our tests. Below is the Devel::Cover
report on this module's test suite.
---------------------------- ------ ------ ------ ------ ------ ------ ------
File stmt bran cond sub pod time total
---------------------------- ------ ------ ------ ------ ------ ------ ------
blib/lib/Tree.pm 100.0 100.0 94.4 100.0 100.0 67.3 99.7
blib/lib/Tree/Binary.pm 96.4 95.0 100.0 100.0 100.0 10.7 96.7
blib/lib/Tree/Fast.pm 99.4 95.5 91.7 100.0 100.0 22.0 98.6
Total 98.9 96.8 94.9 100.0 100.0 100.0 98.5
---------------------------- ------ ------ ------ ------ ------ ------ ------
ACKNOWLEDGEMENTS
• Stevan Little for writing Tree::Simple, upon which Tree is based.
SUPPORT
The mailing list is at TreeCPAN@googlegroups.com. I also read <http://www.perlmonks.com>
on a daily basis.
AUTHORS
Rob Kinyon <rob.kinyon@iinteractive.com>
Stevan Little <stevan.little@iinteractive.com>
Thanks to Infinity Interactive for generously donating our time.
COPYRIGHT AND LICENSE
Copyright 2004, 2005 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.