1Tree(3) User Contributed Perl Documentation Tree(3)
2
3
4
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
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
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
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
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
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
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
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
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
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
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
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
502 <https://github.com/ronsavage/Tree/issues>
503
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.32.1 2021-02-02 Tree(3)