Tree(3)

📦
version 1.16 · 4 versions
, in fedora 43

okay bestie, welcome to Tree(3) — User Contributed Perl Documentation. It's giving N-ary tree, no cap.

✨ NAME ✨

Tree — an N-ary tree. That's the whole name, periodt.

🌈 SYNOPSIS 🌈

Here's the group chat in code form, fr fr:

         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; # See remarks under clone() re deep cloning.
         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 💅

Okay so this module is meant to be a full-featured N-ary tree representation. It's got configurable error-handling and a simple events system that lets you do transparent persistence to a whole variety of datastores. It's derived from Tree::Simple, but lowkey has a simpler interface and much, much more. Periodt.

🌸 METHODS 🌸

🎀 Constructors 🎀

🌟 new([$value]) 🌟

Here, [] indicate an optional parameter. iykyk.

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. Not me ignoring extra args, but okay.

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, but the meta data attached to each node is not copied. Don't get it twisted.

See Tree::DeepClone and t/Tree_DeepClone/*.t if you want deep cloning, which is defined to mean that the meta data attached to each node is also copied into the clone. Slay.

🎀 Behaviors 🎀

🌟 add_child([$options], @nodes) 🌟

This will add all the @nodes as children of $tree. $options is an 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(). So watch that range, bestie.

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. Mix and match, it's giving flexible.

$options is an optional unblessed hashref that specifies parameters for remove_child(). Currently, no parameters are used. So it's just vibing there.

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. Flip it, reverse it.

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. Protect your original, bestie.

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

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 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 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". So don't add your own newlines, bestie.

Draws a nice ASCII-art representation of the tree structure. It's giving art, literally.

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 {}):

  • no_attributes => $Boolean — If 1, the node attributes are not included in the string returned. Default: 0 (include attributes). So default is to show them 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. No cap, it's identity-based.

🌟 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. Context is everything, bestie.

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. Ordered, iconic.

🌟 root() 🌟

This will return the root node of the tree that $tree is in. The root of the root node is itself. Main character energy.

🌟 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. Default undef, periodt.

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

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. Don't clobber, bestie.

🌟 format_node($options, $node) 🌟

Returns a string consisting of the node's name and, optionally, its attributes.

Possible keys in the $options hashref:

  • 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. So maybe don't, bestie.

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:

  • 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. It's just internal storage, no cap.

Calls format_node($options, $node).

Called by tree2string($options).

💖 ERROR HANDLING 💖

okay so real talk: this is where you find out what the default error handlers actually do, and what a custom error handler is expected to do. that's the whole vibe of this section. bestie, read it before you go writing your own.

  • error_handler( [ $handler ] ) — returns the error handler the tree is currently using, no cap. pass a value in and it sets the error handler for the tree instead. plot twist: if you call this as a class method, it works with the default error handler instead. iykyk.
  • error( $error, [ arg1 [, arg2 ...] ] ) — call this when you wanna report an error using the tree's currently defined error_handler. the only parameter that's guaranteed is an error string describing the issue — everything else is extra. there may be other arguments, and you can absolutely provide your own extra arguments in your subclass to pass along to your custom handler. slay.
  • last_error() — if an error happened during the last behavior, this hands you back the error string. heads up: it's reset only by add_child() and remove_child(). periodt.

💅 Default error handlers 💅

  • QUIET — use this one when you want quiet error-handling. the last_error() method will retrieve the error from the last operation, if there was one. and if an error occurs? the operation just returns undefined. no drama, no noise.
  • WARN
  • DIE
that's genuinely the whole list, bestie — QUIET, WARN, DIE. the source only spells out QUIET, so i'm not gonna make stuff up about the other two. 💀

🎀 EVENT HANDLING 🎀

Tree provides for basic event handling. you may choose to register one or more callbacks that get called when the appropriate event occurs. the events are:

  • add_child

this event triggers 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 triggers 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 triggers 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. no queue-jumping. 🙈
  • event( $type, $actor, @args ) — this triggers an event of type $type. all event handlers registered on $tree will be called with parameters of ($actor, @args). then the parent gets notified of the event and its handlers get called, on up to the root. this is the iconic part: it lets 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. main character energy fr fr. 👑

🌈 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. it's giving "yes, and?" forever. 💅

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." — direct quote from the source, and honestly? mood. 💜

💀 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: check SEE ALSO. 🫶

How do I implement the visitor pattern?

the author deliberately chose 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's easy to write one yourself. here's a simple one the author 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. sorry bestie, that's the verdict. 😭

🌸 SEE ALSO 🌸

  • Tree::Binary — lightweight.
  • Tree::DAG_Node — lightweight, and with a long list of methods.
  • Tree::DAG_Node::Persist — lightweight.
  • Tree::Persist — lightweight.
  • Forest — uses Moose.

Tree itself is also lightweight. tiny king behavior. 👑

🧚 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 the test suite of this module.

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

bugs should be reported via the CPAN bug tracker at

https://github.com/ronsavage/Tree/issues

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

and that's the whole page, bestie — no notes. this was Tree(3) from perl v5.42.0, dated 2025-07-25. go build some trees, you absolute icon. 🌈✨💅

📦 where this page comes from