1Tree::Simple(3) User Contributed Perl Documentation Tree::Simple(3)
2
6 Tree::Simple - A simple tree object
7
9 use Tree::Simple;
10 # make a tree root
12 my $tree = Tree::Simple->new("0", Tree::Simple->ROOT);
13 # explicity add a child to it
15 $tree->addChild(Tree::Simple->new("1"));
16 # specify the parent when creating
18 # an instance and it adds the child implicity
19 my $sub_tree = Tree::Simple->new("2", $tree);
20 # chain method calls
22 $tree->getChild(0)->addChild(Tree::Simple->new("1.1"));
23 # add more than one child at a time
25 $sub_tree->addChildren(
26 Tree::Simple->new("2.1"),
27 Tree::Simple->new("2.2")
28 );
29 # add siblings
31 $sub_tree->addSibling(Tree::Simple->new("3"));
32 # insert children a specified index
34 $sub_tree->insertChild(1, Tree::Simple->new("2.1a"));
35 # clean up circular references
37 $tree->DESTROY();
38
40 This module in an fully object-oriented implementation of a simple
41 n-ary tree. It is built upon the concept of parent-child relationships,
42 so therefore every Tree::Simple object has both a parent and a set of
43 children (who themselves may have children, and so on). Every
44 Tree::Simple object also has siblings, as they are just the children of
45 their immediate parent.
46 It is can be used to model hierarchal information such as a file-sys‐
48 tem, the organizational structure of a company, an object inheritance
49 hierarchy, versioned files from a version control system or even an
50 abstract syntax tree for use in a parser. It makes no assumptions as to
51 your intended usage, but instead simply provides the structure and
52 means of accessing and traversing said structure.
53 This module uses exceptions and a minimal Design By Contract style. All
55 method arguments are required unless specified in the documentation, if
56 a required argument is not defined an exception will usually be thrown.
57 Many arguments are also required to be of a specific type, for instance
58 the $parent argument to the constructor must be a Tree::Simple object
59 or an object derived from Tree::Simple, otherwise an exception is
60 thrown. This may seems harsh to some, but this allows me to have the
61 confidence that my code works as I intend, and for you to enjoy the
62 same level of confidence when using this module. Note however that this
63 module does not use any Exception or Error module, the exceptions are
64 just strings thrown with "die".
65 I consider this module to be production stable, it is based on a module
67 which has been in use on a few production systems for approx. 2 years
68 now with no issue. The only difference is that the code has been
69 cleaned up a bit, comments added and the thorough tests written for its
70 public release. I am confident it behaves as I would expect it to, and
71 is (as far as I know) bug-free. I have not stress-tested it under
72 extreme duress, but I don't so much intend for it to be used in that
73 type of situation. If this module cannot keep up with your Tree needs,
74 i suggest switching to one of the modules listed in the "OTHER TREE
75 MODULES" section below.
76
78 ROOT
79 This class constant serves as a placeholder for the root of our
80 tree. If a tree does not have a parent, then it is considered a
81 root.
82
84 Constructor
85 new ($node, $parent)
87 The constructor accepts two arguments a $node value and an optional
88 $parent. The $node value can be any scalar value (which includes
89 references and objects). The optional $parent value must be a
90 Tree::Simple object, or an object derived from Tree::Simple. Set‐
91 ting this value implies that your new tree is a child of the parent
92 tree, and therefore adds it to the parent's children. If the $par‐
93 ent is not specified then its value defaults to ROOT.
94 Mutator Methods
96 setNodeValue ($node_value)
98 This sets the node value to the scalar $node_value, an exception is
99 thrown if $node_value is not defined.
100 setUID ($uid)
102 This allows you to set your own unique ID for this specific
103 Tree::Simple object. A default value derived from the object's hex
104 address is provided for you, so use of this method is entirely
105 optional. It is the responsibility of the user to ensure the
106 value's uniqueness, all that is tested by this method is that $uid
107 is a true value (evaluates to true in a boolean context). For even
108 more information about the Tree::Simple UID see the "getUID"
109 method.
110 addChild ($tree)
112 This method accepts only Tree::Simple objects or objects derived
113 from Tree::Simple, an exception is thrown otherwise. This method
114 will append the given $tree to the end of it's children list, and
115 set up the correct parent-child relationships. This method is set
116 up to return its invocant so that method call chaining can be pos‐
117 sible. Such as:
118 my $tree = Tree::Simple->new("root")->addChild(Tree::Simple->new("child one"));
120 Or the more complex:
122 my $tree = Tree::Simple->new("root")->addChild(
124 Tree::Simple->new("1.0")->addChild(
125 Tree::Simple->new("1.0.1")
126 )
127 );
128 addChildren (@trees)
130 This method accepts an array of Tree::Simple objects, and adds them
131 to it's children list. Like "addChild" this method will return its
132 invocant to allow for method call chaining.
133 insertChild ($index, $tree)
135 This method accepts a numeric $index and a Tree::Simple object
136 ($tree), and inserts the $tree into the children list at the speci‐
137 fied $index. This results in the shifting down of all children
138 after the $index. The $index is checked to be sure it is the bounds
139 of the child list, if it out of bounds an exception is thrown. The
140 $tree argument's type is verified to be a Tree::Simple or
141 Tree::Simple derived object, if this condition fails, an exception
142 is thrown.
143 insertChildren ($index, @trees)
145 This method functions much as insertChild does, but instead of
146 inserting a single Tree::Simple, it inserts an array of Tree::Sim‐
147 ple objects. It too bounds checks the value of $index and type
148 checks the objects in @trees just as "insertChild" does.
149 removeChild ($child ⎪ $index)>
151 Accepts two different arguemnts. If given a Tree::Simple object
152 ($child), this method finds that specific $child by comparing it
153 with all the other children until it finds a match. At which point
154 the $child is removed. If no match is found, and exception is
155 thrown. If a non-Tree::Simple object is given as the $child argu‐
156 ment, an exception is thrown.
157 This method also accepts a numeric $index and removes the child
159 found at that index from it's list of children. The $index is
160 bounds checked, if this condition fail, an exception is thrown.
161 When a child is removed, it results in the shifting up of all chil‐
163 dren after it, and the removed child is returned. The removed child
164 is properly disconnected from the tree and all its references to
165 its old parent are removed. However, in order to properly clean up
166 and circular references the removed child might have, it is advised
167 to call it's "DESTROY" method. See the "CIRCULAR REFERENCES" sec‐
168 tion for more information.
169 addSibling ($tree)
171 addSiblings (@trees)
172 insertSibling ($index, $tree)
173 insertSiblings ($index, @trees)
174 The "addSibling", "addSiblings", "insertSibling" and "insertSib‐
175 lings" methods pass along their arguments to the "addChild", "add‐
176 Children", "insertChild" and "insertChildren" methods of their par‐
177 ent object respectively. This eliminates the need to overload these
178 methods in subclasses which may have specialized versions of the
179 *Child(ren) methods. The one exceptions is that if an attempt it
180 made to add or insert siblings to the ROOT of the tree then an
181 exception is thrown.
182 NOTE: There is no "removeSibling" method as I felt it was probably a
184 bad idea. The same effect can be achieved by manual upwards traversal.
185 Accessor Methods
187 getNodeValue
189 This returns the value stored in the object's node field.
190 getUID
192 This returns the unique ID associated with this particular tree.
193 This can be custom set using the "setUID" method, or you can just
194 use the default. The default is the hex-address extracted from the
195 stringified Tree::Simple object. This may not be a universally
196 unique identifier, but it should be adequate for at least the cur‐
197 rent instance of your perl interpreter. If you need a UUID, one can
198 be generated with an outside module (there are
199 many to choose from on CPAN) and the "setUID" method (see
200 above).
201 getChild ($index)
203 This returns the child (a Tree::Simple object) found at the speci‐
204 fied $index. Note that we do use standard zero-based array index‐
205 ing.
206 getAllChildren
208 This returns an array of all the children (all Tree::Simple
209 objects). It will return an array reference in scalar context.
210 getSibling ($index)
212 getAllSiblings
213 Much like "addSibling" and "addSiblings", these two methods simply
214 call "getChild" and "getAllChildren" on the invocant's parent.
215 getDepth
217 Returns a number representing the invocant's depth within the hier‐
218 archy of Tree::Simple objects.
219 NOTE: A "ROOT" tree has the depth of -1. This be because Tree::Sim‐
221 ple assumes that a tree's root will usually not contain data, but
222 just be an anchor for the data-containing branches. This may not be
223 intuitive in all cases, so I mention it here.
224 getParent
226 Returns the invocant's parent, which could be either ROOT or a
227 Tree::Simple object.
228 getHeight
230 Returns a number representing the length of the longest path from
231 the current tree to the furthest leaf node.
232 getWidth
234 Returns the a number representing the breadth of the current tree,
235 basically it is a count of all the leaf nodes.
236 getChildCount
238 Returns the number of children the invocant contains.
239 getIndex
241 Returns the index of this tree within its parent's child list.
242 Returns -1 if the tree is the root.
243 Predicate Methods
245 isLeaf
247 Returns true (1) if the invocant does not have any children, false
248 (0) otherwise.
249 isRoot
251 Returns true (1) if the invocant's "parent" field is ROOT, returns
252 false (0) otherwise.
253 Recursive Methods
255 traverse ($func, ?$postfunc)
257 This method accepts two arguments a mandatory $func and an optional
258 $postfunc. If the argument $func is not defined then an exception
259 is thrown. If $func or $postfunc are not in fact CODE references
260 then an exception is thrown. The function $func is then applied
261 recursively to all the children of the invocant. If given, the
262 function $postfunc will be applied to each child after the child's
263 children have been traversed.
264 Here is an example of a traversal function that will print out the
266 hierarchy as a tabbed in list.
267 $tree->traverse(sub {
269 my ($_tree) = @_;
270 print (("\t" x $_tree->getDepth()), $_tree->getNodeValue(), "\n");
271 });
272 Here is an example of a traversal function that will print out the
274 hierarchy in an XML-style format.
275 $tree->traverse(sub {
277 my ($_tree) = @_;
278 print ((' ' x $_tree->getDepth()),
279 '<', $_tree->getNodeValue(),'>',"\n");
280 },
281 sub {
282 my ($_tree) = @_;
283 print ((' ' x $_tree->getDepth()),
284 '</', $_tree->getNodeValue(),'>',"\n");
285 });
286 size
288 Returns the total number of nodes in the current tree and all its
289 sub-trees.
290 height
292 This method has also been deprecated in favor of the "getHeight"
293 method above, it remains as an alias to "getHeight" for backwards
294 compatability.
295 NOTE: This is also no longer a recursive method which get's it's
297 value on demand, but a value stored in the Tree::Simple object
298 itself, hopefully making it much more efficient and usable.
299 Visitor Methods
301 accept ($visitor)
303 It accepts either a Tree::Simple::Visitor object (which includes
304 classes derived
305 from Tree::Simple::Visitor), or an object who has the "visit"
306 method available
307 (tested with "$visitor->can('visit')"). If these qualifications
308 are not met,
309 and exception will be thrown. We then run the Visitor's "visit"
310 method giving the
311 current tree as its argument.
312 I have also created a number of Visitor objects and packaged them
314 into the Tree::Simple::VisitorFactory.
315 Cloning Methods
317 Cloning a tree can be an extremly expensive operation for large trees,
319 so we provide two options for cloning, a deep clone and a shallow
320 clone.
321 When a Tree::Simple object is cloned, the node is deep-copied in the
323 following manner. If we find a normal scalar value (non-reference), we
324 simply copy it. If we find an object, we attempt to call "clone" on it,
325 otherwise we just copy the reference (since we assume the object does
326 not want to be cloned). If we find a SCALAR, REF reference we copy the
327 value contained within it. If we find a HASH or ARRAY reference we copy
328 the reference and recursively copy all the elements within it (follow‐
329 ing these exact guidelines). We also do our best to assure that circu‐
330 lar references are cloned only once and connections restored correctly.
331 This cloning will not be able to copy CODE, RegExp and GLOB references,
332 as they are pretty much impossible to clone. We also do not handle
333 "tied" objects, and they will simply be copied as plain references, and
334 not re-"tied".
335 clone
337 The clone method does a full deep-copy clone of the object, calling
338 "clone" recursively on all its children. This does not call "clone"
339 on the parent tree however. Doing this would result in a slowly
340 degenerating spiral of recursive death, so it is not recommended
341 and therefore not implemented. What happens is that the tree
342 instance that "clone" is actually called upon is detached from the
343 tree, and becomes a root node, all if the cloned children are then
344 attached as children of that tree. I personally think this is more
345 intuitive then to have the cloning crawl back up the tree is not
346 what I think most people would expect.
347 cloneShallow
349 This method is an alternate option to the plain "clone" method.
350 This method allows the cloning of single Tree::Simple object while
351 retaining connections to the rest of the tree/hierarchy.
352 Misc. Methods
354 DESTROY
356 To avoid memory leaks through uncleaned-up circular references, we
357 implement the "DESTROY" method. This method will attempt to call
358 "DESTROY" on each of its children (if it has any). This will result
359 in a cascade of calls to "DESTROY" on down the tree. It also cleans
360 up it's parental relations as well.
361 Because of perl's reference counting scheme and how that interacts
363 with circular references, if you want an object to be properly
364 reaped you should manually call "DESTROY". This is especially
365 nessecary if your object has any children. See the section on "CIR‐
366 CULAR REFERENCES" for more information.
367 fixDepth
369 Tree::Simple will manage your tree's depth field for you using this
370 method. You should never need to call it on your own, however if
371 you ever did need to, here is it. Running this method will traverse
372 your all the invocant's sub-trees correcting the depth as it goes.
373 fixHeight
375 Tree::Simple will manage your tree's height field for you using
376 this method. You should never need to call it on your own, however
377 if you ever did need to, here is it. Running this method will cor‐
378 rect the heights of the current tree and all it's ancestors.
379 fixWidth
381 Tree::Simple will manage your tree's width field for you using this
382 method. You should never need to call it on your own, however if
383 you ever did need to, here is it. Running this method will correct
384 the widths of the current tree and all it's ancestors.
385 Private Methods
387 I would not normally document private methods, but in case you need to
389 subclass Tree::Simple, here they are.
390 _init ($node, $parent, $children)
392 This method is here largely to facilitate subclassing. This method
393 is called by new to initialize the object, where new's primary
394 responsibility is creating the instance.
395 _setParent ($parent)
397 This method sets up the parental relationship. It is for internal
398 use only.
399 _setHeight ($child)
401 This method will set the height field based upon the height of the
402 given $child.
403
405 I have revised the model by which Tree::Simple deals with ciruclar ref‐
406 erences. In the past all circular references had to be manually
407 destroyed by calling DESTROY. The call to DESTROY would then call
408 DESTROY on all the children, and therefore cascade down the tree. This
409 however was not always what was needed, nor what made sense, so I have
410 now revised the model to handle things in what I feel is a more consis‐
411 tent and sane way.
412 Circular references are now managed with the simple idea that the par‐
414 ent makes the descisions for the child. This means that child-to-parent
415 references are weak, while parent-to-child references are strong. So if
416 a parent is destroyed it will force all it's children to detach from
417 it, however, if a child is destroyed it will not be detached from it's
418 parent.
419 Optional Weak References
421 By default, you are still required to call DESTROY in order for things
423 to happen. However I have now added the option to use weak references,
424 which alleviates the need for the manual call to DESTROY and allows
425 Tree::Simple to manage this automatically. This is accomplished with a
426 compile time setting like this:
427 use Tree::Simple 'use_weak_refs';
429 And from that point on Tree::Simple will use weak references to allow
431 for perl's reference counting to clean things up properly.
432 For those who are unfamilar with weak references, and how they affect
434 the reference counts, here is a simple illustration. First is the nor‐
435 mal model that Tree::Simple uses:
436 +---------------+
438 ⎪ Tree::Simple1 ⎪<---------------------+
439 +---------------+ ⎪
440 ⎪ parent ⎪ ⎪
441 ⎪ children ⎪-+ ⎪
442 +---------------+ ⎪ ⎪
443 ⎪ ⎪
444 ⎪ +---------------+ ⎪
445 +->⎪ Tree::Simple2 ⎪ ⎪
446 +---------------+ ⎪
447 ⎪ parent ⎪-+
448 ⎪ children ⎪
449 +---------------+
450 Here, Tree::Simple1 has a reference count of 2 (one for the original
452 variable it is assigned to, and one for the parent reference in
453 Tree::Simple2), and Tree::Simple2 has a reference count of 1 (for the
454 child reference in Tree::Simple2).
455 Now, with weak references:
457 +---------------+
459 ⎪ Tree::Simple1 ⎪.......................
460 +---------------+ :
461 ⎪ parent ⎪ :
462 ⎪ children ⎪-+ : <--[ weak reference ]
463 +---------------+ ⎪ :
464 ⎪ :
465 ⎪ +---------------+ :
466 +->⎪ Tree::Simple2 ⎪ :
467 +---------------+ :
468 ⎪ parent ⎪..
469 ⎪ children ⎪
470 +---------------+
471 Now Tree::Simple1 has a reference count of 1 (for the variable it is
473 assigned to) and 1 weakened reference (for the parent reference in
474 Tree::Simple2). And Tree::Simple2 has a reference count of 1, just as
475 before.
476
478 None that I am aware of. The code is pretty thoroughly tested (see
479 "CODE COVERAGE" below) and is based on an (non-publicly released) mod‐
480 ule which I had used in production systems for about 3 years without
481 incident. Of course, if you find a bug, let me know, and I will be sure
482 to fix it.
483
485 I use Devel::Cover to test the code coverage of my tests, below is the
486 Devel::Cover report on this module's test suite.
487 ---------------------------- ------ ------ ------ ------ ------ ------ ------
489 File stmt branch cond sub pod time total
490 ---------------------------- ------ ------ ------ ------ ------ ------ ------
491 Tree/Simple.pm 99.6 96.0 92.3 100.0 97.0 95.5 98.0
492 Tree/Simple/Visitor.pm 100.0 96.2 88.2 100.0 100.0 4.5 97.7
493 ---------------------------- ------ ------ ------ ------ ------ ------ ------
494 Total 99.7 96.1 91.1 100.0 97.6 100.0 97.9
495 ---------------------------- ------ ------ ------ ------ ------ ------ ------
496
498 I have written a number of other modules which use or augment this mod‐
499 ule, they are describes below and available on CPAN.
500 Tree::Parser - A module for parsing formatted files into Tree::Simple
502 hierarchies.
503 Tree::Simple::View - A set of classes for viewing Tree::Simple hierar‐
504 chies in various output formats.
505 Tree::Simple::VisitorFactory - A set of several useful Visitor objects
506 for Tree::Simple objects.
507 Tree::Binary - If you are looking for a binary tree, this you might
508 want to check this one out.
509 Also, the author of Data::TreeDumper and I have worked together to make
511 sure that Tree::Simple and his module work well together. If you need
512 a quick and handy way to dump out a Tree::Simple heirarchy, this module
513 does an excellent job (and plenty more as well).
514 I have also recently stumbled upon some packaged distributions of
516 Tree::Simple for the various Unix flavors. Here are some links:
517 FreeBSD Port - <http://www.freshports.org/devel/p5-Tree-Simple/>
519 Debian Package - <http://packages.debian.org/unstable/perl/libtree-sim‐
520 ple-perl>
521 Linux RPM - <http://rpmpan.sourceforge.net/Tree.html>
522
524 There are a few other Tree modules out there, here is a quick compari‐
525 son between Tree::Simple and them. Obviously I am biased, so take what
526 I say with a grain of salt, and keep in mind, I wrote Tree::Simple
527 because I could not find a Tree module that suited my needs. If
528 Tree::Simple does not fit your needs, I recommend looking at these mod‐
529 ules. Please note that I am only listing Tree::* modules I am familiar
530 with here, if you think I have missed a module, please let me know. I
531 have also seen a few tree-ish modules outside of the Tree::* namespace,
532 but most of them are part of another distribution (HTML::Tree,
533 Pod::Tree, etc) and are likely specialized in purpose.
534 Tree::DAG_Node
536 This module seems pretty stable and very robust with a lot of func‐
537 tionality. However, Tree::DAG_Node does not come with any auto‐
538 mated tests. It's test.pl file simply checks the module loads and
539 nothing else. While I am sure the author tested his code, I would
540 feel better if I was able to see that. The module is approx. 3000
541 lines with POD, and 1,500 without the POD. The shear depth and
542 detail of the documentation and the ratio of code to documentation
543 is impressive, and not to be taken lightly. But given that it is a
544 well known fact that the likeliness of bugs increases along side
545 the size of the code, I do not feel comfortable with large modules
546 like this which have no tests.
547 All this said, I am not a huge fan of the API either, I prefer the
549 gender neutral approach in Tree::Simple to the mother/daughter
550 style of Tree::DAG_Node. I also feel very strongly that
551 Tree::DAG_Node is trying to do much more than makes sense in a sin‐
552 gle module, and is offering too many ways to do the same or similar
553 things.
554 However, of all the Tree::* modules out there, Tree::DAG_Node seems
556 to be one of the favorites, so it may be worth investigating.
557 Tree::MultiNode
559 I am not very familiar with this module, however, I have heard some
560 good reviews of it, so I thought it deserved mention here. I
561 believe it is based upon C++ code found in the book Algorithms in
562 C++ by Robert Sedgwick. It uses a number of interesting ideas,
563 such as a ::Handle object to traverse the tree with (similar to
564 Visitors, but also seem to be to be kind of like a cursor). How‐
565 ever, like Tree::DAG_Node, it is somewhat lacking in tests and has
566 only 6 tests in its suite. It also has one glaring bug, which is
567 that there is currently no way to remove a child node.
568 Tree::Nary
570 It is a (somewhat) direct translation of the N-ary tree from the
571 GLIB library, and the API is based on that. GLIB is a C library,
572 which means this is a very C-ish API. That doesn't appeal to me, it
573 might to you, to each their own.
574 This module is similar in intent to Tree::Simple. It implements a
576 tree with n branches and has polymorphic node containers. It imple‐
577 ments much of the same methods as Tree::Simple and a few others on
578 top of that, but being based on a C library, is not very OO. In
579 most of the method calls the $self argument is not used and the
580 second argument $node is. Tree::Simple is a much more OO module
581 than Tree::Nary, so while they are similar in functionality they
582 greatly differ in implementation style.
583 Tree
585 This module is pretty old, it has not been updated since Oct. 31,
586 1999 and is still on version 0.01. It also seems to be (from the
587 limited documentation) a binary and a balanced binary tree,
588 Tree::Simple is an n-ary tree, and makes no attempt to balance any‐
589 thing.
590 Tree::Ternary
592 This module is older than Tree, last update was Sept. 24th, 1999.
593 It seems to be a special purpose tree, for storing and accessing
594 strings, not general purpose like Tree::Simple.
595 Tree::Ternary_XS
597 This module is an XS implementation of the above tree type.
598 Tree::Trie
600 This too is a specialized tree type, it sounds similar to the
601 Tree::Ternary, but it much newer (latest release in 2003). It seems
602 specialized for the lookup and retrieval of information like a
603 hash.
604 Tree::M
606 Is a wrapper for a C++ library, whereas Tree::Simple is pure-perl.
607 It also seems to be a more specialized implementation of a tree,
608 therefore not really the same as Tree::Simple.
609 Tree::Fat
611 Is a wrapper around a C library, again Tree::Simple is pure-perl.
612 The author describes FAT-trees as a combination of a Tree and an
613 array. It looks like a pretty mean and lean module, and good if you
614 need speed and are implementing a custom data-store of some kind.
615 The author points out too that the module is designed for embedding
616 and there is not default embedding, so you can't really use it "out
617 of the box".
618
620 Thanks to Nadim Ibn Hamouda El Khemir for making Data::TreeDumper work
621 with Tree::Simple.
622 Thanks to Brett Nuske for his idea for the "getUID" and "setUID" meth‐
623 ods.
624 Thanks to whomever submitted the memory leak bug to RT (#7512).
625 Thanks to Mark Thomas for his insight into how to best handle the
626 height and width properties without unessecary recursion.
627 Thanks for Mark Lawrence for the &traverse post-func patch, tests and
628 docs.
629
631 Stevan Little, <stevan@iinteractive.com>
632 Rob Kinyon, <rob@iinteractive.com>
634
636 Copyright 2004-2006 by Infinity Interactive, Inc.
637 <http://www.iinteractive.com>
639 This library is free software; you can redistribute it and/or modify it
641 under the same terms as Perl itself.
642perl v5.8.8 2007-11-11 Tree::Simple(3)