1Tree(3)               User Contributed Perl Documentation              Tree(3)
2
3
4

NAME

6       Tree - An N-ary tree
7

SYNOPSIS

9         my $tree = Tree->new( 'root' );
10         my $child = Tree->new( 'child' );
11         $tree->add_child( $child );
12
13         $tree->add_child( { at => 0 }, Tree->new( 'first child' ) );
14         $tree->add_child( { at => -1 }, Tree->new( 'last child' ) );
15
16         $tree->set_value( 'toor' );
17         my $value = $tree->value;
18
19         my @children = $tree->children;
20         my @some_children = $tree->children( 0, 2 );
21
22         my $height = $tree->height;
23         my $width  = $tree->width;
24         my $depth  = $tree->depth;
25         my $size   = $tree->size;
26
27         if ( $tree->has_child( $child ) ) {
28             $tree->remove_child( $child );
29         }
30
31         $tree->remove_child( 0 );
32
33         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
37         $tree->add_event_handler({
38             add_child    => sub { ... },
39             remove_child => sub { ... },
40             value        => sub { ... },
41         });
42
43         my $old_default_error_handler = $tree->error_handler(Tree->DIE);
44         my $old_object_error_handler  = $tree->error_handler($tree->DIE);
45

DESCRIPTION

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

METHODS

53   Constructors
54   new([$value])
55       Here, [] indicate an optional parameter.
56
57       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
61       If you call "$tree->new([$value])", it will instead call "clone()",
62       then set the value of the clone to $value.
63
64   clone()
65       This will return a clone of $tree. The clone will be a root tree, but
66       all children will be cloned.
67
68       If you call "Tree->clone([$value])", it will instead call
69       "new($value)".
70
71       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
75       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
79   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
85       •   at
86
87           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
94       add_child() resets last_error() upon entry.
95
96   remove_child([$options], @nodes)
97       Here, [] indicate an optional parameter.
98
99       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
103       $options is a optional unblessed hashref that specifies parameters for
104       remove_child(). Currently, no parameters are used.
105
106       remove_child() resets last_error() upon entry.
107
108   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
112       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
116       mirror() does not reset last_error() because it (mirror() ) is
117       implemented in Tree::Fast, which has no error handling.
118
119   traverse([$order])
120       Here, [] indicate an optional parameter.
121
122       This will return a list of the nodes in the given traversal order. The
123       default traversal order is pre-order.
124
125       The various traversal orders do the following steps:
126
127       •   Pre-order
128
129           This will return the node, then the first sub tree in pre-order
130           traversal, then the next sub tree, etc.
131
132           Use "$tree->PRE_ORDER" as the $order.
133
134       •   Post-order
135
136           This will return the each sub-tree in post-order traversal, then
137           the node.
138
139           Use "$tree->POST_ORDER" as the $order.
140
141       •   Level-order
142
143           This will return the node, then the all children of the node, then
144           all grandchildren of the node, etc.
145
146           Use "$tree->LEVEL_ORDER" as the $order.
147
148       traverse() does not reset last_error() because it (traverse() ) is
149       implemented in Tree::Fast, which has no error handling.
150
151   tree2string($options)
152       Returns an arrayref of lines, suitable for printing. These lines do not
153       end in "\n".
154
155       Draws a nice ASCII-art representation of the tree structure.
156
157       The tree looks like:
158
159               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
171       Or, without attributes:
172
173               Root
174                   |--- H
175                   |    |--- I
176                   |    |    |--- J
177                   |    |--- K
178                   |    |--- L
179                   |--- M
180                   |--- N
181                        |--- O
182                             |--- P
183                                  |--- Q
184
185       See scripts/print.tree.pl.
186
187       Example usage:
188
189         print map("$_\n", @{$tree -> tree2string});
190
191       If you do not wish to supply options, use "tree2string()" or
192       "tree2string({})".
193
194       Possible keys in the $options hashref (which defaults to {}):
195
196       o no_attributes => $Boolean
197           If 1, the node attributes are not included in the string returned.
198
199           Default: 0 (include attributes).
200
201       Calls "node2string($options, $node, $vert_dashes)".
202
203   State Queries
204   is_root()
205       This will return true if $tree has no parent and false otherwise.
206
207   is_leaf()
208       This will return true if $tree has no children and false otherwise.
209
210   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
214       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
218   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
222   Accessors
223   parent()
224       This will return the parent of $tree.
225
226   children( [ $idx, [$idx, ..] ] )
227       Here, [] indicate optional parameters.
228
229       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
233       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
237   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
241   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
245   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
249   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
253       This is the distance from the root. It is useful for things like
254       pretty-printing the tree.
255
256   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
261   value()
262       This will return the value stored in the node.
263
264   set_value([$value])
265       Here, [] indicate an optional parameter.
266
267       This will set the value stored in the node to $value, then return
268       $self.
269
270       If $value is not provided, undef is used.
271
272   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
277       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
283   format_node($options, $node)
284       Returns a string consisting of the node's name and, optionally, it's
285       attributes.
286
287       Possible keys in the $options hashref:
288
289       o no_attributes => $Boolean
290           If 1, the node attributes are not included in the string returned.
291
292           Default: 0 (include attributes).
293
294       Calls "hashref2string($hashref)".
295
296       Called by "node2string($options, $node, $vert_dashes)".
297
298       You would not normally call this method.
299
300       If you do not wish to supply options, use format_node({}, $node).
301
302   hashref2string($hashref)
303       Returns the given hashref as a string.
304
305       Called by "format_node($options, $node)".
306
307   node2string($options, $node, $vert_dashes)
308       Returns a string of the node name and attributes, with a leading
309       indent, suitable for printing.
310
311       Possible keys in the $options hashref:
312
313       o no_attributes => $Boolean
314           If 1, the node attributes are not included in the string returned.
315
316           Default: 0 (include attributes).
317
318       Ignore the parameter $vert_dashes. The code uses it as temporary
319       storage.
320
321       Calls "format_node($options, $node)".
322
323       Called by "tree2string($options)".
324

ERROR HANDLING

326       Describe what the default error handlers do and what a custom error
327       handler is expected to do.
328
329   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
334       If called as a class method, this will instead work with the default
335       error handler.
336
337   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
344   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
348   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
355       WARN
356       DIE
357

EVENT HANDLING

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
363       •   add_child
364
365           This event will trigger as the last step in an
366           "add_child([$options], @nodes)" call.
367
368           The parameters will be "( $self, @args )" where @args is the
369           arguments passed into the add_child() call.
370
371       •   remove_child
372
373           This event will trigger as the last step in an
374           "remove_child([$options], @nodes)" call.
375
376           The parameters will be "( $self, @args )" where @args is the
377           arguments passed into the remove_child() call.
378
379       •   value
380
381           This event will trigger as the last step in a set_value() call.
382
383           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
387   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
393   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
399       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

NULL TREE

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
409   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
413       •   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
416       •   The Tree::Null object is a singleton.
417
418       •   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

CIRCULAR REFERENCES

422       Please q.v. Forest for more info on this topic.
423

FAQ

425   Which is the best tree processing module?
426       Tree::DAG_Node. More details: "SEE ALSO".
427
428   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
435         package My::Visitor;
436
437         sub new {
438             my $class = shift;
439             my $opts  = @_;
440
441             return bless {
442                 tree => $opts->{tree},
443                 action => $opts->{action},
444             }, $class;
445         }
446
447         sub visit {
448             my $self = shift;
449             my ($mode) = @_;
450
451             foreach my $node ( $self->{tree}->traverse( $mode ) ) {
452                 $self->{action}->( $node );
453             }
454         }
455
456   Should I implement the visitor pattern?
457       No. You are better off using the "walk_down($options)" in
458       Tree::DAG_Node method.
459

SEE ALSO

461       o Tree::Binary
462           Lightweight.
463
464       o Tree::DAG_Node
465           Lightweight, and with a long list of methods.
466
467       o Tree::DAG_Node::Persist
468           Lightweight.
469
470       o Tree::Persist
471           Lightweight.
472
473       o Forest
474           Uses Moose.
475
476       "Tree" itself is also lightweight.
477

CODE COVERAGE

479       These statistics are as of V 1.01.
480
481       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
484         ---------------------------- ------ ------ ------ ------ ------ ------ ------
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

ACKNOWLEDGEMENTS

494       •   Stevan Little for writing Tree::Simple, upon which Tree is based.
495

Repository

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

SUPPORT

500       Bugs should be reported via the CPAN bug tracker at
501
502       <https://github.com/ronsavage/Tree/issues>
503

AUTHORS

505       Rob Kinyon <rob.kinyon@iinteractive.com>
506
507       Stevan Little <stevan.little@iinteractive.com>
508
509       Thanks to Infinity Interactive for generously donating our time.
510
511       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
517       <http://www.iinteractive.com>
518
519       This library is free software; you can redistribute it and/or modify it
520       under the same terms as Perl itself.
521
522
523
524perl v5.34.0                      2022-01-21                           Tree(3)
Impressum