Provided by: libtree-perl_1.10-0ubuntu2_all bug

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 { ... },
         });

         my $old_default_error_handler = $tree->error_handler(Tree->DIE);
         my $old_object_error_handler  = $tree->error_handler($tree->DIE);

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

   Constructors
   new([$value])
       Here, [] indicate an optional parameter.

       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($value).

       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(). Lastly, if it is out of range (too
           negative or too big [beyond the number of children]) the child is not added, and an
           error msg will be available in "last_error()".

       add_child() resets last_error() upon entry.

   remove_child([$options], @nodes)
       Here, [] indicate an optional parameter.

       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.

       remove_child() resets last_error() upon entry.

   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 internal structure of the tree. If
       you wish to get a mirror, yet keep the original tree intact, use "my $mirror =
       $tree->clone->mirror".

       mirror() does not reset last_error() because it (mirror() ) is implemented in Tree::Fast,
       which has no error handling.

   traverse([$order])
       Here, [] indicate an optional parameter.

       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

           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

           This will return the each sub-tree in post-order traversal, then the node.

           Use "$tree->POST_ORDER" as the $order.

       •   Level-order

           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.

       traverse() does not reset last_error() because it (traverse() ) is implemented in
       Tree::Fast, which has no error handling.

   tree2string($options)
       Returns an arrayref of lines, suitable for printing. These lines do not end in "\n".

       Draws a nice ASCII-art representation of the tree structure.

       The tree looks like:

               Root. Attributes: {uid => "0"}
                   |--- H. Attributes: {uid => "1"}
                   |    |--- I. Attributes: {uid => "2"}
                   |    |    |--- J. Attributes: {uid => "3"}
                   |    |--- K. Attributes: {uid => "4"}
                   |    |--- L. Attributes: {uid => "5"}
                   |--- M. Attributes: {uid => "6"}
                   |--- N. Attributes: {uid => "7"}
                        |--- O. Attributes: {uid => "8"}
                             |--- P. Attributes: {uid => "9"}
                                  |--- Q. Attributes: {uid => "10"}

       Or, without attributes:

               Root
                   |--- H
                   |    |--- I
                   |    |    |--- J
                   |    |--- K
                   |    |--- L
                   |--- M
                   |--- N
                        |--- O
                             |--- P
                                  |--- Q

       See scripts/print.tree.pl.

       Example usage:

         print map("$_\n", @{$tree -> tree2string});

       If you do not wish to supply options, use tree2string() or tree2string({}).

       Possible keys in the $options hashref (which defaults to {}):

       o no_attributes => $Boolean
           If 1, the node attributes are not included in the string returned.

           Default: 0 (include attributes).

       Calls "node2string($options, $node, $vert_dashes)".

   State Queries
   is_root()
       This will return true if $tree has no parent and false otherwise.

   is_leaf()
       This will return true if $tree has no children and false otherwise.

   has_child(@nodes)
       This will return true if $tree has each of the @nodes as a child.  Otherwise, it will
       return false.

       The test to see if a node is in the tree uses refaddr() from Scalar::Util, not the value
       of the node.  This means @nodes must be an array of "Tree" objects.

   get_index_for(@nodes)
       This will return the index into the children list of $tree for each of the @nodes passed
       in.

   Accessors
   parent()
       This will return the parent of $tree.

   children( [ $idx, [$idx, ..] ] )
       Here, [] indicate optional parameters.

       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 is 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])
       Here, [] indicate an optional parameter.

       This will set the value stored in the node to $value, then return $self.

       If $value is not provided, undef is used.

   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.

   format_node($options, $node)
       Returns a string consisting of the node's name and, optionally, it's attributes.

       Possible keys in the $options hashref:

       o no_attributes => $Boolean
           If 1, the node attributes are not included in the string returned.

           Default: 0 (include attributes).

       Calls "hashref2string($hashref)".

       Called by "node2string($options, $node, $vert_dashes)".

       You would not normally call this method.

       If you do not wish to supply options, use format_node({}, $node).

   hashref2string($hashref)
       Returns the given hashref as a string.

       Called by "format_node($options, $node)".

   node2string($options, $node, $vert_dashes)
       Returns a string of the node name and attributes, with a leading indent, suitable for
       printing.

       Possible keys in the $options hashref:

       o no_attributes => $Boolean
           If 1, the node attributes are not included in the string returned.

           Default: 0 (include attributes).

       Ignore the parameter $vert_dashes. The code uses it as temporary storage.

       Calls "format_node($options, $node)".

       Called by "tree2string($options)".

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 by add_child() and remove_child().

   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

       Tree 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([$options], @nodes)" 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([$options], @nodes)"
           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 could not 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.

FAQ

   Which is the best tree processing module?
       Tree::DAG_Node. More details: "SEE ALSO".

   How do I implement 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 the capabilities of Perl, an explicit
       visitor object is almost always unneeded. If you want one, it is easy to write one
       yourself. Here is 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 );
             }
         }

   Should I implement the visitor pattern?
       No. You are better off using the "walk_down($options)" in Tree::DAG_Node method.

SEE ALSO

       o Tree::Binary
           Lightweight.

       o Tree::DAG_Node
           Lightweight, and with a long list of methods.

       o Tree::DAG_Node::Persist
           Lightweight.

       o Tree::Persist
           Lightweight.

       o Forest
           Uses Moose.

       "Tree" itself is also lightweight.

CODE COVERAGE

       These statistics are as of V 1.01.

       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.

Repository

       <https://github.com/ronsavage/Tree>

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.

       Co-maintenance since V 1.02 is by Ron Savage <rsavage@cpan.org>.  Uses of 'I' in previous
       versions is not me, but will be hereafter.

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.