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;
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.
73 Behaviors
75 add_child([$options], @nodes)
76 This will add all the @nodes as children of $tree. $options is a
77 optional unblessed hashref that specifies options for "add_child()".
78 The optional parameters are:
79 · at
81 This specifies the index to add @nodes at. If specified, this will
83 be passed into splice(). The only exceptions are if this is 0, it
84 will act as an unshift(). If it is unset or undefined, it will act
85 as a push(). Lastly, if it is out of range (too negative or too big
86 [beyond the number of children]) the child is not added, and an
87 error msg will be available in "last_error()".
88 add_child() resets last_error() upon entry.
90 remove_child([$options], @nodes)
92 Here, [] indicate an optional parameter.
93 This will remove all the @nodes from the children of $tree. You can
95 either pass in the actual child object you wish to remove, the index of
96 the child you wish to remove, or a combination of both.
97 $options is a optional unblessed hashref that specifies parameters for
99 remove_child(). Currently, no parameters are used.
100 remove_child() resets last_error() upon entry.
102 mirror()
104 This will modify the tree such that it is a mirror of what it was
105 before. This means that the order of all children is reversed.
106 NOTE: This is a destructive action. It will modify the internal
108 structure of the tree. If you wish to get a mirror, yet keep the
109 original tree intact, use "my $mirror = $tree->clone->mirror".
110 mirror() does not reset last_error() because it (mirror() ) is
112 implemented in Tree::Fast, which has no error handling.
113 traverse([$order])
115 Here, [] indicate an optional parameter.
116 This will return a list of the nodes in the given traversal order. The
118 default traversal order is pre-order.
119 The various traversal orders do the following steps:
121 · Pre-order
123 This will return the node, then the first sub tree in pre-order
125 traversal, then the next sub tree, etc.
126 Use "$tree->PRE_ORDER" as the $order.
128 · Post-order
130 This will return the each sub-tree in post-order traversal, then
132 the node.
133 Use "$tree->POST_ORDER" as the $order.
135 · Level-order
137 This will return the node, then the all children of the node, then
139 all grandchildren of the node, etc.
140 Use "$tree->LEVEL_ORDER" as the $order.
142 traverse() does not reset last_error() because it (traverse() ) is
144 implemented in Tree::Fast, which has no error handling.
145 tree2string($options)
147 Returns an arrayref of lines, suitable for printing. These lines do not
148 end in "\n".
149 Draws a nice ASCII-art representation of the tree structure.
151 The tree looks like:
153 Root. Attributes: {uid => "0"}
155 |--- H. Attributes: {uid => "1"}
156 | |--- I. Attributes: {uid => "2"}
157 | | |--- J. Attributes: {uid => "3"}
158 | |--- K. Attributes: {uid => "4"}
159 | |--- L. Attributes: {uid => "5"}
160 |--- M. Attributes: {uid => "6"}
161 |--- N. Attributes: {uid => "7"}
162 |--- O. Attributes: {uid => "8"}
163 |--- P. Attributes: {uid => "9"}
164 |--- Q. Attributes: {uid => "10"}
165 Or, without attributes:
167 Root
169 |--- H
170 | |--- I
171 | | |--- J
172 | |--- K
173 | |--- L
174 |--- M
175 |--- N
176 |--- O
177 |--- P
178 |--- Q
179 See scripts/print.tree.pl.
181 Example usage:
183 print map("$_\n", @{$tree -> tree2string});
185 If you do not wish to supply options, use "tree2string()" or
187 "tree2string({})".
188 Possible keys in the $options hashref (which defaults to {}):
190 o no_attributes => $Boolean
192 If 1, the node attributes are not included in the string returned.
193 Default: 0 (include attributes).
195 Calls "node2string($options, $node, $vert_dashes)".
197 State Queries
199 is_root()
200 This will return true if $tree has no parent and false otherwise.
201 is_leaf()
203 This will return true if $tree has no children and false otherwise.
204 has_child(@nodes)
206 This will return true if $tree has each of the @nodes as a child.
207 Otherwise, it will return false.
208 The test to see if a node is in the tree uses refaddr() from
210 Scalar::Util, not the value of the node. This means @nodes must be an
211 array of "Tree" objects.
212 get_index_for(@nodes)
214 This will return the index into the children list of $tree for each of
215 the @nodes passed in.
216 Accessors
218 parent()
219 This will return the parent of $tree.
220 children( [ $idx, [$idx, ..] ] )
222 Here, [] indicate optional parameters.
223 This will return the children of $tree. If called in list context, it
225 will return all the children. If called in scalar context, it will
226 return the number of children.
227 You may optionally pass in a list of indices to retrieve. This will
229 return the children in the order you asked for them. This is very much
230 like an arrayslice.
231 root()
233 This will return the root node of the tree that $tree is in. The root
234 of the root node is itself.
235 height()
237 This will return the height of $tree. A leaf has a height of 1. A
238 parent has a height of its tallest child, plus 1.
239 width()
241 This will return the width of $tree. A leaf has a width of 1. A parent
242 has a width equal to the sum of all the widths of its children.
243 depth()
245 This will return the depth of $tree. A root has a depth of 0. A child
246 has the depth of its parent, plus 1.
247 This is the distance from the root. It is useful for things like
249 pretty-printing the tree.
250 size()
252 This will return the number of nodes within $tree. A leaf has a size of
253 1. A parent has a size equal to the 1 plus the sum of all the sizes of
254 its children.
255 value()
257 This will return the value stored in the node.
258 set_value([$value])
260 Here, [] indicate an optional parameter.
261 This will set the value stored in the node to $value, then return
263 $self.
264 If $value is not provided, undef is used.
266 meta()
268 This will return a hashref that can be used to store whatever metadata
269 the client wishes to store. For example, Tree::Persist::DB uses this to
270 store database row ids.
271 It is recommended that you store your metadata in a subhashref and not
273 in the top-level metadata hashref, keyed by your package name.
274 Tree::Persist does this, using a unique key for each persistence layer
275 associated with that tree. This will help prevent clobbering of
276 metadata.
277 format_node($options, $node)
279 Returns a string consisting of the node's name and, optionally, it's
280 attributes.
281 Possible keys in the $options hashref:
283 o no_attributes => $Boolean
285 If 1, the node attributes are not included in the string returned.
286 Default: 0 (include attributes).
288 Calls "hashref2string($hashref)".
290 Called by "node2string($options, $node, $vert_dashes)".
292 You would not normally call this method.
294 If you do not wish to supply options, use format_node({}, $node).
296 hashref2string($hashref)
298 Returns the given hashref as a string.
299 Called by "format_node($options, $node)".
301 node2string($options, $node, $vert_dashes)
303 Returns a string of the node name and attributes, with a leading
304 indent, suitable for printing.
305 Possible keys in the $options hashref:
307 o no_attributes => $Boolean
309 If 1, the node attributes are not included in the string returned.
310 Default: 0 (include attributes).
312 Ignore the parameter $vert_dashes. The code uses it as temporary
314 storage.
315 Calls "format_node($options, $node)".
317 Called by "tree2string($options)".
319
321 Describe what the default error handlers do and what a custom error
322 handler is expected to do.
323 Error-related methods
325 error_handler( [ $handler ] )
326 This will return the current error handler for the tree. If a value is
327 passed in, then it will be used to set the error handler for the tree.
328 If called as a class method, this will instead work with the default
330 error handler.
331 error( $error, [ arg1 [, arg2 ...] ] )
333 Call this when you wish to report an error using the currently defined
334 error_handler for the tree. The only guaranteed parameter is an error
335 string describing the issue. There may be other arguments, and you may
336 certainly provide other arguments in your subclass to be passed to your
337 custom handler.
338 last_error()
340 If an error occurred during the last behavior, this will return the
341 error string. It is reset only by add_child() and remove_child().
342 Default error handlers
344 QUIET
345 Use this error handler if you want to have quiet error-handling.
346 The "last_error()" method will retrieve the error from the last
347 operation, if there was one. If an error occurs, the operation will
348 return undefined.
349 WARN
351 DIE
352
354 Tree provides for basic event handling. You may choose to register one
355 or more callbacks to be called when the appropriate event occurs. The
356 events are:
357 · add_child
359 This event will trigger as the last step in an
361 "add_child([$options], @nodes)" call.
362 The parameters will be "( $self, @args )" where @args is the
364 arguments passed into the add_child() call.
365 · remove_child
367 This event will trigger as the last step in an
369 "remove_child([$options], @nodes)" call.
370 The parameters will be "( $self, @args )" where @args is the
372 arguments passed into the remove_child() call.
373 · value
375 This event will trigger as the last step in a set_value() call.
377 The parameters will be "( $self, $old_value )" where $old_value is
379 what the value was before it was changed. The new value can be
380 accessed through "$self->value()".
381 Event handling methods
383 add_event_handler( {$type => $callback [, $type => $callback, ... ]} )
384 You may choose to add event handlers for any known type. Callbacks must
385 be references to subroutines. They will be called in the order they are
386 defined.
387 event( $type, $actor, @args )
389 This will trigger an event of type $type. All event handlers registered
390 on $tree will be called with parameters of "($actor, @args)". Then, the
391 parent will be notified of the event and its handlers will be called,
392 on up to the root.
393 This allows you specify an event handler on the root and be guaranteed
395 that it will fire every time the appropriate event occurs anywhere in
396 the tree.
397
399 If you call "$self->parent" on a root node, it will return a Tree::Null
400 object. This is an implementation of the Null Object pattern optimized
401 for usage with Tree. It will evaluate as false in every case (using
402 overload) and all methods called on it will return a Tree::Null object.
403 Notes
405 · Tree::Null does not inherit from Tree. This is so that all the
406 methods will go through AUTOLOAD vs. the actual method.
407 · However, calling isa() on a Tree::Null object will report that it
409 is-a any object that is either Tree or in the Tree:: hierarchy.
410 · The Tree::Null object is a singleton.
412 · The Tree::Null object is defined, though. I could not find a way to
414 make it evaluate as undefined. That may be a good thing.
415
417 Please q.v. Forest for more info on this topic.
418
420 Which is the best tree processing module?
421 Tree::DAG_Node. More details: "SEE ALSO".
422 How do I implement the visitor pattern?
424 I have deliberately chosen to not implement the Visitor pattern as
425 described by Gamma et al. Given a sufficiently powerful "traverse()"
426 and the capabilities of Perl, an explicit visitor object is almost
427 always unneeded. If you want one, it is easy to write one yourself.
428 Here is a simple one I wrote in 5 minutes:
429 package My::Visitor;
431 sub new {
433 my $class = shift;
434 my $opts = @_;
435 return bless {
437 tree => $opts->{tree},
438 action => $opts->{action},
439 }, $class;
440 }
441 sub visit {
443 my $self = shift;
444 my ($mode) = @_;
445 foreach my $node ( $self->{tree}->traverse( $mode ) ) {
447 $self->{action}->( $node );
448 }
449 }
450 Should I implement the visitor pattern?
452 No. You are better off using the "walk_down($options)" in
453 Tree::DAG_Node method.
454
456 o Tree::Binary
457 Lightweight.
458 o Tree::DAG_Node
460 Lightweight, and with a long list of methods.
461 o Tree::DAG_Node::Persist
463 Lightweight.
464 o Tree::Persist
466 Lightweight.
467 o Forest
469 Uses Moose.
470 "Tree" itself is also lightweight.
472
474 These statistics are as of V 1.01.
475 We use Devel::Cover to test the code coverage of our tests. Below is
477 the Devel::Cover report on this module's test suite.
478 ---------------------------- ------ ------ ------ ------ ------ ------ ------
480 File stmt bran cond sub pod time total
481 ---------------------------- ------ ------ ------ ------ ------ ------ ------
482 blib/lib/Tree.pm 100.0 100.0 94.4 100.0 100.0 67.3 99.7
483 blib/lib/Tree/Binary.pm 96.4 95.0 100.0 100.0 100.0 10.7 96.7
484 blib/lib/Tree/Fast.pm 99.4 95.5 91.7 100.0 100.0 22.0 98.6
485 Total 98.9 96.8 94.9 100.0 100.0 100.0 98.5
486 ---------------------------- ------ ------ ------ ------ ------ ------ ------
487
489 · Stevan Little for writing Tree::Simple, upon which Tree is based.
490
492 <https://github.com/ronsavage/Tree>
493
495 The mailing list is at TreeCPAN@googlegroups.com. I also read
496 <http://www.perlmonks.com> on a daily basis.
497
499 Rob Kinyon <rob.kinyon@iinteractive.com>
500 Stevan Little <stevan.little@iinteractive.com>
502 Thanks to Infinity Interactive for generously donating our time.
504 Co-maintenance since V 1.02 is by Ron Savage <rsavage@cpan.org>. Uses
506 of 'I' in previous versions is not me, but will be hereafter.
507
509 Copyright 2004, 2005 by Infinity Interactive, Inc.
510 <http://www.iinteractive.com>
512 This library is free software; you can redistribute it and/or modify it
514 under the same terms as Perl itself.
515perl v5.28.0 2016-09-15 Tree(3)