1Tree(3) User Contributed Perl Documentation Tree(3)
2
6 Tree - An N-ary tree
7
9 my $tree = Tree->new( 'root' );
10 my $child = Tree->new( 'child' );
11 $tree->add_child( $child );
12 $tree->add_child( { at => 0 }, Tree->new( 'first child' ) );
14 $tree->add_child( { at => -1 }, Tree->new( 'last child' ) );
15 $tree->set_value( 'toor' );
17 my $value = $tree->value;
18 my @children = $tree->children;
20 my @some_children = $tree->children( 0, 2 );
21 my $height = $tree->height;
23 my $width = $tree->width;
24 my $depth = $tree->depth;
25 my $size = $tree->size;
26 if ( $tree->has_child( $child ) ) {
28 $tree->remove_child( $child );
29 }
30 $tree->remove_child( 0 );
32 my @nodes = $tree->traverse( $tree->POST_ORDER );
34 my $clone = $tree->clone; # See remarks under clone() re deep cloning.
35 my $mirror = $tree->clone->mirror;
36 $tree->add_event_handler({
38 add_child => sub { ... },
39 remove_child => sub { ... },
40 value => sub { ... },
41 });
42 my $old_default_error_handler = $tree->error_handler(Tree->DIE);
44 my $old_object_error_handler = $tree->error_handler($tree->DIE);
45
47 This is meant to be a full-featured N-ary tree representation with
48 configurable error-handling and a simple events system that allows for
49 transparent persistence to a variety of datastores. It is derived from
50 Tree::Simple, but has a simpler interface and much, much more.
51
53 Constructors
54 new([$value])
55 Here, [] indicate an optional parameter.
56 This will return a "Tree" object. It will accept one parameter which,
58 if passed, will become the value (accessible by value()). All other
59 parameters will be ignored.
60 If you call "$tree->new([$value])", it will instead call clone(), then
62 set the value of the clone to $value.
63 clone()
65 This will return a clone of $tree. The clone will be a root tree, but
66 all children will be cloned.
67 If you call "Tree->clone([$value])", it will instead call new($value).
69 NOTE: the "value" is merely a shallow copy. This means that all
71 references will be kept, but the "meta" data attached to each node is
72 not copied.
73 See Tree::DeepClone and t/Tree_DeepClone/*.t if you want deep cloning,
75 which is defined to mean that the "meta" data attached to each node is
76 also copied into the clone.
77 Behaviors
79 add_child([$options], @nodes)
80 This will add all the @nodes as children of $tree. $options is a
81 optional unblessed hashref that specifies options for add_child(). The
82 optional parameters are:
83 • at
85 This specifies the index to add @nodes at. If specified, this will
87 be passed into splice(). The only exceptions are if this is 0, it
88 will act as an unshift(). If it is unset or undefined, it will act
89 as a push(). Lastly, if it is out of range (too negative or too big
90 [beyond the number of children]) the child is not added, and an
91 error msg will be available in "last_error()".
92 add_child() resets last_error() upon entry.
94 remove_child([$options], @nodes)
96 Here, [] indicate an optional parameter.
97 This will remove all the @nodes from the children of $tree. You can
99 either pass in the actual child object you wish to remove, the index of
100 the child you wish to remove, or a combination of both.
101 $options is a optional unblessed hashref that specifies parameters for
103 remove_child(). Currently, no parameters are used.
104 remove_child() resets last_error() upon entry.
106 mirror()
108 This will modify the tree such that it is a mirror of what it was
109 before. This means that the order of all children is reversed.
110 NOTE: This is a destructive action. It will modify the internal
112 structure of the tree. If you wish to get a mirror, yet keep the
113 original tree intact, use "my $mirror = $tree->clone->mirror".
114 mirror() does not reset last_error() because it (mirror() ) is
116 implemented in Tree::Fast, which has no error handling.
117 traverse([$order])
119 Here, [] indicate an optional parameter.
120 This will return a list of the nodes in the given traversal order. The
122 default traversal order is pre-order.
123 The various traversal orders do the following steps:
125 • Pre-order
127 This will return the node, then the first sub tree in pre-order
129 traversal, then the next sub tree, etc.
130 Use "$tree->PRE_ORDER" as the $order.
132 • Post-order
134 This will return the each sub-tree in post-order traversal, then
136 the node.
137 Use "$tree->POST_ORDER" as the $order.
139 • Level-order
141 This will return the node, then the all children of the node, then
143 all grandchildren of the node, etc.
144 Use "$tree->LEVEL_ORDER" as the $order.
146 traverse() does not reset last_error() because it (traverse() ) is
148 implemented in Tree::Fast, which has no error handling.
149 tree2string($options)
151 Returns an arrayref of lines, suitable for printing. These lines do not
152 end in "\n".
153 Draws a nice ASCII-art representation of the tree structure.
155 The tree looks like:
157 Root. Attributes: {uid => "0"}
159 |--- H. Attributes: {uid => "1"}
160 | |--- I. Attributes: {uid => "2"}
161 | | |--- J. Attributes: {uid => "3"}
162 | |--- K. Attributes: {uid => "4"}
163 | |--- L. Attributes: {uid => "5"}
164 |--- M. Attributes: {uid => "6"}
165 |--- N. Attributes: {uid => "7"}
166 |--- O. Attributes: {uid => "8"}
167 |--- P. Attributes: {uid => "9"}
168 |--- Q. Attributes: {uid => "10"}
169 Or, without attributes:
171 Root
173 |--- H
174 | |--- I
175 | | |--- J
176 | |--- K
177 | |--- L
178 |--- M
179 |--- N
180 |--- O
181 |--- P
182 |--- Q
183 See scripts/print.tree.pl.
185 Example usage:
187 print map("$_\n", @{$tree -> tree2string});
189 If you do not wish to supply options, use tree2string() or
191 tree2string({}).
192 Possible keys in the $options hashref (which defaults to {}):
194 o no_attributes => $Boolean
196 If 1, the node attributes are not included in the string returned.
197 Default: 0 (include attributes).
199 Calls "node2string($options, $node, $vert_dashes)".
201 State Queries
203 is_root()
204 This will return true if $tree has no parent and false otherwise.
205 is_leaf()
207 This will return true if $tree has no children and false otherwise.
208 has_child(@nodes)
210 This will return true if $tree has each of the @nodes as a child.
211 Otherwise, it will return false.
212 The test to see if a node is in the tree uses refaddr() from
214 Scalar::Util, not the value of the node. This means @nodes must be an
215 array of "Tree" objects.
216 get_index_for(@nodes)
218 This will return the index into the children list of $tree for each of
219 the @nodes passed in.
220 Accessors
222 parent()
223 This will return the parent of $tree.
224 children( [ $idx, [$idx, ..] ] )
226 Here, [] indicate optional parameters.
227 This will return the children of $tree. If called in list context, it
229 will return all the children. If called in scalar context, it will
230 return the number of children.
231 You may optionally pass in a list of indices to retrieve. This will
233 return the children in the order you asked for them. This is very much
234 like an arrayslice.
235 root()
237 This will return the root node of the tree that $tree is in. The root
238 of the root node is itself.
239 height()
241 This will return the height of $tree. A leaf has a height of 1. A
242 parent has a height of its tallest child, plus 1.
243 width()
245 This will return the width of $tree. A leaf has a width of 1. A parent
246 has a width equal to the sum of all the widths of its children.
247 depth()
249 This will return the depth of $tree. A root has a depth of 0. A child
250 has the depth of its parent, plus 1.
251 This is the distance from the root. It is useful for things like
253 pretty-printing the tree.
254 size()
256 This will return the number of nodes within $tree. A leaf has a size of
257 1. A parent has a size equal to the 1 plus the sum of all the sizes of
258 its children.
259 value()
261 This will return the value stored in the node.
262 set_value([$value])
264 Here, [] indicate an optional parameter.
265 This will set the value stored in the node to $value, then return
267 $self.
268 If $value is not provided, undef is used.
270 meta()
272 This will return a hashref that can be used to store whatever metadata
273 the client wishes to store. For example, Tree::Persist::DB uses this to
274 store database row ids.
275 It is recommended that you store your metadata in a subhashref and not
277 in the top-level metadata hashref, keyed by your package name.
278 Tree::Persist does this, using a unique key for each persistence layer
279 associated with that tree. This will help prevent clobbering of
280 metadata.
281 format_node($options, $node)
283 Returns a string consisting of the node's name and, optionally, it's
284 attributes.
285 Possible keys in the $options hashref:
287 o no_attributes => $Boolean
289 If 1, the node attributes are not included in the string returned.
290 Default: 0 (include attributes).
292 Calls "hashref2string($hashref)".
294 Called by "node2string($options, $node, $vert_dashes)".
296 You would not normally call this method.
298 If you do not wish to supply options, use format_node({}, $node).
300 hashref2string($hashref)
302 Returns the given hashref as a string.
303 Called by "format_node($options, $node)".
305 node2string($options, $node, $vert_dashes)
307 Returns a string of the node name and attributes, with a leading
308 indent, suitable for printing.
309 Possible keys in the $options hashref:
311 o no_attributes => $Boolean
313 If 1, the node attributes are not included in the string returned.
314 Default: 0 (include attributes).
316 Ignore the parameter $vert_dashes. The code uses it as temporary
318 storage.
319 Calls "format_node($options, $node)".
321 Called by "tree2string($options)".
323
325 Describe what the default error handlers do and what a custom error
326 handler is expected to do.
327 Error-related methods
329 error_handler( [ $handler ] )
330 This will return the current error handler for the tree. If a value is
331 passed in, then it will be used to set the error handler for the tree.
332 If called as a class method, this will instead work with the default
334 error handler.
335 error( $error, [ arg1 [, arg2 ...] ] )
337 Call this when you wish to report an error using the currently defined
338 error_handler for the tree. The only guaranteed parameter is an error
339 string describing the issue. There may be other arguments, and you may
340 certainly provide other arguments in your subclass to be passed to your
341 custom handler.
342 last_error()
344 If an error occurred during the last behavior, this will return the
345 error string. It is reset only by add_child() and remove_child().
346 Default error handlers
348 QUIET
349 Use this error handler if you want to have quiet error-handling.
350 The "last_error()" method will retrieve the error from the last
351 operation, if there was one. If an error occurs, the operation will
352 return undefined.
353 WARN
355 DIE
356
358 Tree provides for basic event handling. You may choose to register one
359 or more callbacks to be called when the appropriate event occurs. The
360 events are:
361 • add_child
363 This event will trigger as the last step in an
365 "add_child([$options], @nodes)" call.
366 The parameters will be "( $self, @args )" where @args is the
368 arguments passed into the add_child() call.
369 • remove_child
371 This event will trigger as the last step in an
373 "remove_child([$options], @nodes)" call.
374 The parameters will be "( $self, @args )" where @args is the
376 arguments passed into the remove_child() call.
377 • value
379 This event will trigger as the last step in a set_value() call.
381 The parameters will be "( $self, $old_value )" where $old_value is
383 what the value was before it was changed. The new value can be
384 accessed through "$self->value()".
385 Event handling methods
387 add_event_handler( {$type => $callback [, $type => $callback, ... ]} )
388 You may choose to add event handlers for any known type. Callbacks must
389 be references to subroutines. They will be called in the order they are
390 defined.
391 event( $type, $actor, @args )
393 This will trigger an event of type $type. All event handlers registered
394 on $tree will be called with parameters of "($actor, @args)". Then, the
395 parent will be notified of the event and its handlers will be called,
396 on up to the root.
397 This allows you specify an event handler on the root and be guaranteed
399 that it will fire every time the appropriate event occurs anywhere in
400 the tree.
401
403 If you call "$self->parent" on a root node, it will return a Tree::Null
404 object. This is an implementation of the Null Object pattern optimized
405 for usage with Tree. It will evaluate as false in every case (using
406 overload) and all methods called on it will return a Tree::Null object.
407 Notes
409 • Tree::Null does not inherit from Tree. This is so that all the
410 methods will go through AUTOLOAD vs. the actual method.
411 • However, calling isa() on a Tree::Null object will report that it
413 is-a any object that is either Tree or in the Tree:: hierarchy.
414 • The Tree::Null object is a singleton.
416 • The Tree::Null object is defined, though. I could not find a way to
418 make it evaluate as undefined. That may be a good thing.
419
421 Please q.v. Forest for more info on this topic.
422
424 Which is the best tree processing module?
425 Tree::DAG_Node. More details: "SEE ALSO".
426 How do I implement the visitor pattern?
428 I have deliberately chosen to not implement the Visitor pattern as
429 described by Gamma et al. Given a sufficiently powerful traverse() and
430 the capabilities of Perl, an explicit visitor object is almost always
431 unneeded. If you want one, it is easy to write one yourself. Here is a
432 simple one I wrote in 5 minutes:
433 package My::Visitor;
435 sub new {
437 my $class = shift;
438 my $opts = @_;
439 return bless {
441 tree => $opts->{tree},
442 action => $opts->{action},
443 }, $class;
444 }
445 sub visit {
447 my $self = shift;
448 my ($mode) = @_;
449 foreach my $node ( $self->{tree}->traverse( $mode ) ) {
451 $self->{action}->( $node );
452 }
453 }
454 Should I implement the visitor pattern?
456 No. You are better off using the "walk_down($options)" in
457 Tree::DAG_Node method.
458
460 o Tree::Binary
461 Lightweight.
462 o Tree::DAG_Node
464 Lightweight, and with a long list of methods.
465 o Tree::DAG_Node::Persist
467 Lightweight.
468 o Tree::Persist
470 Lightweight.
471 o Forest
473 Uses Moose.
474 "Tree" itself is also lightweight.
476
478 These statistics are as of V 1.01.
479 We use Devel::Cover to test the code coverage of our tests. Below is
481 the Devel::Cover report on the test suite of this module.
482 ---------------------------- ------ ------ ------ ------ ------ ------ ------
484 File stmt bran cond sub pod time total
485 ---------------------------- ------ ------ ------ ------ ------ ------ ------
486 blib/lib/Tree.pm 100.0 100.0 94.4 100.0 100.0 67.3 99.7
487 blib/lib/Tree/Binary.pm 96.4 95.0 100.0 100.0 100.0 10.7 96.7
488 blib/lib/Tree/Fast.pm 99.4 95.5 91.7 100.0 100.0 22.0 98.6
489 Total 98.9 96.8 94.9 100.0 100.0 100.0 98.5
490 ---------------------------- ------ ------ ------ ------ ------ ------ ------
491
493 • Stevan Little for writing Tree::Simple, upon which Tree is based.
494
496 <https://github.com/ronsavage/Tree>
497
499 Bugs should be reported via the CPAN bug tracker at
500 <https://github.com/ronsavage/Tree/issues>
502
504 Rob Kinyon <rob.kinyon@iinteractive.com>
505 Stevan Little <stevan.little@iinteractive.com>
507 Thanks to Infinity Interactive for generously donating our time.
509 Co-maintenance since V 1.02 is by Ron Savage <rsavage@cpan.org>. Uses
511 of 'I' in previous versions is not me, but will be hereafter.
512
514 Copyright 2004, 2005 by Infinity Interactive, Inc.
515 <http://www.iinteractive.com>
517 This library is free software; you can redistribute it and/or modify it
519 under the same terms as Perl itself.
520perl v5.36.1 2023-07-26 Tree(3)