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()",
62 then 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
69 "new($value)".
70 NOTE: the "value" is merely a shallow copy. This means that all
72 references will be kept, but the "meta" data attached to each node is
73 not copied.
74 See Tree::DeepClone and t/Tree_DeepClone/*.t if you want deep cloning,
76 which is defined to mean that the "meta" data attached to each node is
77 also copied into the clone.
78 Behaviors
80 add_child([$options], @nodes)
81 This will add all the @nodes as children of $tree. $options is a
82 optional unblessed hashref that specifies options for "add_child()".
83 The optional parameters are:
84 • at
86 This specifies the index to add @nodes at. If specified, this will
88 be passed into splice(). The only exceptions are if this is 0, it
89 will act as an unshift(). If it is unset or undefined, it will act
90 as a push(). Lastly, if it is out of range (too negative or too big
91 [beyond the number of children]) the child is not added, and an
92 error msg will be available in "last_error()".
93 add_child() resets last_error() upon entry.
95 remove_child([$options], @nodes)
97 Here, [] indicate an optional parameter.
98 This will remove all the @nodes from the children of $tree. You can
100 either pass in the actual child object you wish to remove, the index of
101 the child you wish to remove, or a combination of both.
102 $options is a optional unblessed hashref that specifies parameters for
104 remove_child(). Currently, no parameters are used.
105 remove_child() resets last_error() upon entry.
107 mirror()
109 This will modify the tree such that it is a mirror of what it was
110 before. This means that the order of all children is reversed.
111 NOTE: This is a destructive action. It will modify the internal
113 structure of the tree. If you wish to get a mirror, yet keep the
114 original tree intact, use "my $mirror = $tree->clone->mirror".
115 mirror() does not reset last_error() because it (mirror() ) is
117 implemented in Tree::Fast, which has no error handling.
118 traverse([$order])
120 Here, [] indicate an optional parameter.
121 This will return a list of the nodes in the given traversal order. The
123 default traversal order is pre-order.
124 The various traversal orders do the following steps:
126 • Pre-order
128 This will return the node, then the first sub tree in pre-order
130 traversal, then the next sub tree, etc.
131 Use "$tree->PRE_ORDER" as the $order.
133 • Post-order
135 This will return the each sub-tree in post-order traversal, then
137 the node.
138 Use "$tree->POST_ORDER" as the $order.
140 • Level-order
142 This will return the node, then the all children of the node, then
144 all grandchildren of the node, etc.
145 Use "$tree->LEVEL_ORDER" as the $order.
147 traverse() does not reset last_error() because it (traverse() ) is
149 implemented in Tree::Fast, which has no error handling.
150 tree2string($options)
152 Returns an arrayref of lines, suitable for printing. These lines do not
153 end in "\n".
154 Draws a nice ASCII-art representation of the tree structure.
156 The tree looks like:
158 Root. Attributes: {uid => "0"}
160 |--- H. Attributes: {uid => "1"}
161 | |--- I. Attributes: {uid => "2"}
162 | | |--- J. Attributes: {uid => "3"}
163 | |--- K. Attributes: {uid => "4"}
164 | |--- L. Attributes: {uid => "5"}
165 |--- M. Attributes: {uid => "6"}
166 |--- N. Attributes: {uid => "7"}
167 |--- O. Attributes: {uid => "8"}
168 |--- P. Attributes: {uid => "9"}
169 |--- Q. Attributes: {uid => "10"}
170 Or, without attributes:
172 Root
174 |--- H
175 | |--- I
176 | | |--- J
177 | |--- K
178 | |--- L
179 |--- M
180 |--- N
181 |--- O
182 |--- P
183 |--- Q
184 See scripts/print.tree.pl.
186 Example usage:
188 print map("$_\n", @{$tree -> tree2string});
190 If you do not wish to supply options, use "tree2string()" or
192 "tree2string({})".
193 Possible keys in the $options hashref (which defaults to {}):
195 o no_attributes => $Boolean
197 If 1, the node attributes are not included in the string returned.
198 Default: 0 (include attributes).
200 Calls "node2string($options, $node, $vert_dashes)".
202 State Queries
204 is_root()
205 This will return true if $tree has no parent and false otherwise.
206 is_leaf()
208 This will return true if $tree has no children and false otherwise.
209 has_child(@nodes)
211 This will return true if $tree has each of the @nodes as a child.
212 Otherwise, it will return false.
213 The test to see if a node is in the tree uses refaddr() from
215 Scalar::Util, not the value of the node. This means @nodes must be an
216 array of "Tree" objects.
217 get_index_for(@nodes)
219 This will return the index into the children list of $tree for each of
220 the @nodes passed in.
221 Accessors
223 parent()
224 This will return the parent of $tree.
225 children( [ $idx, [$idx, ..] ] )
227 Here, [] indicate optional parameters.
228 This will return the children of $tree. If called in list context, it
230 will return all the children. If called in scalar context, it will
231 return the number of children.
232 You may optionally pass in a list of indices to retrieve. This will
234 return the children in the order you asked for them. This is very much
235 like an arrayslice.
236 root()
238 This will return the root node of the tree that $tree is in. The root
239 of the root node is itself.
240 height()
242 This will return the height of $tree. A leaf has a height of 1. A
243 parent has a height of its tallest child, plus 1.
244 width()
246 This will return the width of $tree. A leaf has a width of 1. A parent
247 has a width equal to the sum of all the widths of its children.
248 depth()
250 This will return the depth of $tree. A root has a depth of 0. A child
251 has the depth of its parent, plus 1.
252 This is the distance from the root. It is useful for things like
254 pretty-printing the tree.
255 size()
257 This will return the number of nodes within $tree. A leaf has a size of
258 1. A parent has a size equal to the 1 plus the sum of all the sizes of
259 its children.
260 value()
262 This will return the value stored in the node.
263 set_value([$value])
265 Here, [] indicate an optional parameter.
266 This will set the value stored in the node to $value, then return
268 $self.
269 If $value is not provided, undef is used.
271 meta()
273 This will return a hashref that can be used to store whatever metadata
274 the client wishes to store. For example, Tree::Persist::DB uses this to
275 store database row ids.
276 It is recommended that you store your metadata in a subhashref and not
278 in the top-level metadata hashref, keyed by your package name.
279 Tree::Persist does this, using a unique key for each persistence layer
280 associated with that tree. This will help prevent clobbering of
281 metadata.
282 format_node($options, $node)
284 Returns a string consisting of the node's name and, optionally, it's
285 attributes.
286 Possible keys in the $options hashref:
288 o no_attributes => $Boolean
290 If 1, the node attributes are not included in the string returned.
291 Default: 0 (include attributes).
293 Calls "hashref2string($hashref)".
295 Called by "node2string($options, $node, $vert_dashes)".
297 You would not normally call this method.
299 If you do not wish to supply options, use format_node({}, $node).
301 hashref2string($hashref)
303 Returns the given hashref as a string.
304 Called by "format_node($options, $node)".
306 node2string($options, $node, $vert_dashes)
308 Returns a string of the node name and attributes, with a leading
309 indent, suitable for printing.
310 Possible keys in the $options hashref:
312 o no_attributes => $Boolean
314 If 1, the node attributes are not included in the string returned.
315 Default: 0 (include attributes).
317 Ignore the parameter $vert_dashes. The code uses it as temporary
319 storage.
320 Calls "format_node($options, $node)".
322 Called by "tree2string($options)".
324
326 Describe what the default error handlers do and what a custom error
327 handler is expected to do.
328 Error-related methods
330 error_handler( [ $handler ] )
331 This will return the current error handler for the tree. If a value is
332 passed in, then it will be used to set the error handler for the tree.
333 If called as a class method, this will instead work with the default
335 error handler.
336 error( $error, [ arg1 [, arg2 ...] ] )
338 Call this when you wish to report an error using the currently defined
339 error_handler for the tree. The only guaranteed parameter is an error
340 string describing the issue. There may be other arguments, and you may
341 certainly provide other arguments in your subclass to be passed to your
342 custom handler.
343 last_error()
345 If an error occurred during the last behavior, this will return the
346 error string. It is reset only by add_child() and remove_child().
347 Default error handlers
349 QUIET
350 Use this error handler if you want to have quiet error-handling.
351 The "last_error()" method will retrieve the error from the last
352 operation, if there was one. If an error occurs, the operation will
353 return undefined.
354 WARN
356 DIE
357
359 Tree provides for basic event handling. You may choose to register one
360 or more callbacks to be called when the appropriate event occurs. The
361 events are:
362 • add_child
364 This event will trigger as the last step in an
366 "add_child([$options], @nodes)" call.
367 The parameters will be "( $self, @args )" where @args is the
369 arguments passed into the add_child() call.
370 • remove_child
372 This event will trigger as the last step in an
374 "remove_child([$options], @nodes)" call.
375 The parameters will be "( $self, @args )" where @args is the
377 arguments passed into the remove_child() call.
378 • value
380 This event will trigger as the last step in a set_value() call.
382 The parameters will be "( $self, $old_value )" where $old_value is
384 what the value was before it was changed. The new value can be
385 accessed through "$self->value()".
386 Event handling methods
388 add_event_handler( {$type => $callback [, $type => $callback, ... ]} )
389 You may choose to add event handlers for any known type. Callbacks must
390 be references to subroutines. They will be called in the order they are
391 defined.
392 event( $type, $actor, @args )
394 This will trigger an event of type $type. All event handlers registered
395 on $tree will be called with parameters of "($actor, @args)". Then, the
396 parent will be notified of the event and its handlers will be called,
397 on up to the root.
398 This allows you specify an event handler on the root and be guaranteed
400 that it will fire every time the appropriate event occurs anywhere in
401 the tree.
402
404 If you call "$self->parent" on a root node, it will return a Tree::Null
405 object. This is an implementation of the Null Object pattern optimized
406 for usage with Tree. It will evaluate as false in every case (using
407 overload) and all methods called on it will return a Tree::Null object.
408 Notes
410 • Tree::Null does not inherit from Tree. This is so that all the
411 methods will go through AUTOLOAD vs. the actual method.
412 • However, calling isa() on a Tree::Null object will report that it
414 is-a any object that is either Tree or in the Tree:: hierarchy.
415 • The Tree::Null object is a singleton.
417 • The Tree::Null object is defined, though. I could not find a way to
419 make it evaluate as undefined. That may be a good thing.
420
422 Please q.v. Forest for more info on this topic.
423
425 Which is the best tree processing module?
426 Tree::DAG_Node. More details: "SEE ALSO".
427 How do I implement the visitor pattern?
429 I have deliberately chosen to not implement the Visitor pattern as
430 described by Gamma et al. Given a sufficiently powerful "traverse()"
431 and the capabilities of Perl, an explicit visitor object is almost
432 always unneeded. If you want one, it is easy to write one yourself.
433 Here is a simple one I wrote in 5 minutes:
434 package My::Visitor;
436 sub new {
438 my $class = shift;
439 my $opts = @_;
440 return bless {
442 tree => $opts->{tree},
443 action => $opts->{action},
444 }, $class;
445 }
446 sub visit {
448 my $self = shift;
449 my ($mode) = @_;
450 foreach my $node ( $self->{tree}->traverse( $mode ) ) {
452 $self->{action}->( $node );
453 }
454 }
455 Should I implement the visitor pattern?
457 No. You are better off using the "walk_down($options)" in
458 Tree::DAG_Node method.
459
461 o Tree::Binary
462 Lightweight.
463 o Tree::DAG_Node
465 Lightweight, and with a long list of methods.
466 o Tree::DAG_Node::Persist
468 Lightweight.
469 o Tree::Persist
471 Lightweight.
472 o Forest
474 Uses Moose.
475 "Tree" itself is also lightweight.
477
479 These statistics are as of V 1.01.
480 We use Devel::Cover to test the code coverage of our tests. Below is
482 the Devel::Cover report on the test suite of this module.
483 ---------------------------- ------ ------ ------ ------ ------ ------ ------
485 File stmt bran cond sub pod time total
486 ---------------------------- ------ ------ ------ ------ ------ ------ ------
487 blib/lib/Tree.pm 100.0 100.0 94.4 100.0 100.0 67.3 99.7
488 blib/lib/Tree/Binary.pm 96.4 95.0 100.0 100.0 100.0 10.7 96.7
489 blib/lib/Tree/Fast.pm 99.4 95.5 91.7 100.0 100.0 22.0 98.6
490 Total 98.9 96.8 94.9 100.0 100.0 100.0 98.5
491 ---------------------------- ------ ------ ------ ------ ------ ------ ------
492
494 • Stevan Little for writing Tree::Simple, upon which Tree is based.
495
497 <https://github.com/ronsavage/Tree>
498
500 Bugs should be reported via the CPAN bug tracker at
501 <https://github.com/ronsavage/Tree/issues>
503
505 Rob Kinyon <rob.kinyon@iinteractive.com>
506 Stevan Little <stevan.little@iinteractive.com>
508 Thanks to Infinity Interactive for generously donating our time.
510 Co-maintenance since V 1.02 is by Ron Savage <rsavage@cpan.org>. Uses
512 of 'I' in previous versions is not me, but will be hereafter.
513
515 Copyright 2004, 2005 by Infinity Interactive, Inc.
516 <http://www.iinteractive.com>
518 This library is free software; you can redistribute it and/or modify it
520 under the same terms as Perl itself.
521perl v5.34.0 2022-01-21 Tree(3)