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-
48 system, the organizational structure of a company, an object
49 inheritance hierarchy, versioned files from a version control system or
50 even an abstract syntax tree for use in a parser. It makes no
51 assumptions as to your intended usage, but instead simply provides the
52 structure and 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)
86 The constructor accepts two arguments a $node value and an optional
87 $parent. The $node value can be any scalar value (which includes
88 references and objects). The optional $parent value must be a
89 Tree::Simple object, or an object derived from Tree::Simple.
90 Setting this value implies that your new tree is a child of the
91 parent tree, and therefore adds it to the parent's children. If the
92 $parent is not specified then its value defaults to ROOT.
93 Mutator Methods
95 setNodeValue ($node_value)
96 This sets the node value to the scalar $node_value, an exception is
97 thrown if $node_value is not defined.
98 setUID ($uid)
100 This allows you to set your own unique ID for this specific
101 Tree::Simple object. A default value derived from the object's hex
102 address is provided for you, so use of this method is entirely
103 optional. It is the responsibility of the user to ensure the
104 value's uniqueness, all that is tested by this method is that $uid
105 is a true value (evaluates to true in a boolean context). For even
106 more information about the Tree::Simple UID see the "getUID"
107 method.
108 addChild ($tree)
110 This method accepts only Tree::Simple objects or objects derived
111 from Tree::Simple, an exception is thrown otherwise. This method
112 will append the given $tree to the end of it's children list, and
113 set up the correct parent-child relationships. This method is set
114 up to return its invocant so that method call chaining can be
115 possible. Such as:
116 my $tree = Tree::Simple->new("root")->addChild(Tree::Simple->new("child one"));
118 Or the more complex:
120 my $tree = Tree::Simple->new("root")->addChild(
122 Tree::Simple->new("1.0")->addChild(
123 Tree::Simple->new("1.0.1")
124 )
125 );
126 addChildren (@trees)
128 This method accepts an array of Tree::Simple objects, and adds them
129 to it's children list. Like "addChild" this method will return its
130 invocant to allow for method call chaining.
131 insertChild ($index, $tree)
133 This method accepts a numeric $index and a Tree::Simple object
134 ($tree), and inserts the $tree into the children list at the
135 specified $index. This results in the shifting down of all
136 children after the $index. The $index is checked to be sure it is
137 the bounds of the child list, if it out of bounds an exception is
138 thrown. The $tree argument's type is verified to be a Tree::Simple
139 or Tree::Simple derived object, if this condition fails, an
140 exception is thrown.
141 insertChildren ($index, @trees)
143 This method functions much as insertChild does, but instead of
144 inserting a single Tree::Simple, it inserts an array of
145 Tree::Simple objects. It too bounds checks the value of $index and
146 type checks the objects in @trees just as "insertChild" does.
147 removeChild ($child | $index)>
149 Accepts two different arguemnts. If given a Tree::Simple object
150 ($child), this method finds that specific $child by comparing it
151 with all the other children until it finds a match. At which point
152 the $child is removed. If no match is found, and exception is
153 thrown. If a non-Tree::Simple object is given as the $child
154 argument, an exception is thrown.
155 This method also accepts a numeric $index and removes the child
157 found at that index from it's list of children. The $index is
158 bounds checked, if this condition fail, an exception is thrown.
159 When a child is removed, it results in the shifting up of all
161 children after it, and the removed child is returned. The removed
162 child is properly disconnected from the tree and all its references
163 to its old parent are removed. However, in order to properly clean
164 up and circular references the removed child might have, it is
165 advised to call it's "DESTROY" method. See the "CIRCULAR
166 REFERENCES" section for more information.
167 addSibling ($tree)
169 addSiblings (@trees)
170 insertSibling ($index, $tree)
171 insertSiblings ($index, @trees)
172 The "addSibling", "addSiblings", "insertSibling" and
173 "insertSiblings" methods pass along their arguments to the
174 "addChild", "addChildren", "insertChild" and "insertChildren"
175 methods of their parent object respectively. This eliminates the
176 need to overload these methods in subclasses which may have
177 specialized versions of the *Child(ren) methods. The one exceptions
178 is that if an attempt it made to add or insert siblings to the ROOT
179 of the tree then an exception is thrown.
180 NOTE: There is no "removeSibling" method as I felt it was probably a
182 bad idea. The same effect can be achieved by manual upwards traversal.
183 Accessor Methods
185 getNodeValue
186 This returns the value stored in the object's node field.
187 getUID
189 This returns the unique ID associated with this particular tree.
190 This can be custom set using the "setUID" method, or you can just
191 use the default. The default is the hex-address extracted from the
192 stringified Tree::Simple object. This may not be a universally
193 unique identifier, but it should be adequate for at least the
194 current instance of your perl interpreter. If you need a UUID, one
195 can be generated with an outside module (there are
196 many to choose from on CPAN) and the "setUID" method (see
197 above).
198 getChild ($index)
200 This returns the child (a Tree::Simple object) found at the
201 specified $index. Note that we do use standard zero-based array
202 indexing.
203 getAllChildren
205 This returns an array of all the children (all Tree::Simple
206 objects). It will return an array reference in scalar context.
207 getSibling ($index)
209 getAllSiblings
210 Much like "addSibling" and "addSiblings", these two methods simply
211 call "getChild" and "getAllChildren" on the invocant's parent.
212 getDepth
214 Returns a number representing the invocant's depth within the
215 hierarchy of Tree::Simple objects.
216 NOTE: A "ROOT" tree has the depth of -1. This be because
218 Tree::Simple assumes that a tree's root will usually not contain
219 data, but just be an anchor for the data-containing branches. This
220 may not be intuitive in all cases, so I mention it here.
221 getParent
223 Returns the invocant's parent, which could be either ROOT or a
224 Tree::Simple object.
225 getHeight
227 Returns a number representing the length of the longest path from
228 the current tree to the furthest leaf node.
229 getWidth
231 Returns the a number representing the breadth of the current tree,
232 basically it is a count of all the leaf nodes.
233 getChildCount
235 Returns the number of children the invocant contains.
236 getIndex
238 Returns the index of this tree within its parent's child list.
239 Returns -1 if the tree is the root.
240 Predicate Methods
242 isLeaf
243 Returns true (1) if the invocant does not have any children, false
244 (0) otherwise.
245 isRoot
247 Returns true (1) if the invocant's "parent" field is ROOT, returns
248 false (0) otherwise.
249 Recursive Methods
251 traverse ($func, ?$postfunc)
252 This method accepts two arguments a mandatory $func and an optional
253 $postfunc. If the argument $func is not defined then an exception
254 is thrown. If $func or $postfunc are not in fact CODE references
255 then an exception is thrown. The function $func is then applied
256 recursively to all the children of the invocant. If given, the
257 function $postfunc will be applied to each child after the child's
258 children have been traversed.
259 Here is an example of a traversal function that will print out the
261 hierarchy as a tabbed in list.
262 $tree->traverse(sub {
264 my ($_tree) = @_;
265 print (("\t" x $_tree->getDepth()), $_tree->getNodeValue(), "\n");
266 });
267 Here is an example of a traversal function that will print out the
269 hierarchy in an XML-style format.
270 $tree->traverse(sub {
272 my ($_tree) = @_;
273 print ((' ' x $_tree->getDepth()),
274 '<', $_tree->getNodeValue(),'>',"\n");
275 },
276 sub {
277 my ($_tree) = @_;
278 print ((' ' x $_tree->getDepth()),
279 '</', $_tree->getNodeValue(),'>',"\n");
280 });
281 size
283 Returns the total number of nodes in the current tree and all its
284 sub-trees.
285 height
287 This method has also been deprecated in favor of the "getHeight"
288 method above, it remains as an alias to "getHeight" for backwards
289 compatability.
290 NOTE: This is also no longer a recursive method which get's it's
292 value on demand, but a value stored in the Tree::Simple object
293 itself, hopefully making it much more efficient and usable.
294 Visitor Methods
296 accept ($visitor)
297 It accepts either a Tree::Simple::Visitor object (which includes
298 classes derived
299 from Tree::Simple::Visitor), or an object who has the "visit"
300 method available
301 (tested with "$visitor->can('visit')"). If these qualifications
302 are not met,
303 and exception will be thrown. We then run the Visitor's "visit"
304 method giving the
305 current tree as its argument.
306 I have also created a number of Visitor objects and packaged them
308 into the Tree::Simple::VisitorFactory.
309 Cloning Methods
311 Cloning a tree can be an extremly expensive operation for large trees,
312 so we provide two options for cloning, a deep clone and a shallow
313 clone.
314 When a Tree::Simple object is cloned, the node is deep-copied in the
316 following manner. If we find a normal scalar value (non-reference), we
317 simply copy it. If we find an object, we attempt to call "clone" on it,
318 otherwise we just copy the reference (since we assume the object does
319 not want to be cloned). If we find a SCALAR, REF reference we copy the
320 value contained within it. If we find a HASH or ARRAY reference we copy
321 the reference and recursively copy all the elements within it
322 (following these exact guidelines). We also do our best to assure that
323 circular references are cloned only once and connections restored
324 correctly. This cloning will not be able to copy CODE, RegExp and GLOB
325 references, as they are pretty much impossible to clone. We also do not
326 handle "tied" objects, and they will simply be copied as plain
327 references, and not re-"tied".
328 clone
330 The clone method does a full deep-copy clone of the object, calling
331 "clone" recursively on all its children. This does not call "clone"
332 on the parent tree however. Doing this would result in a slowly
333 degenerating spiral of recursive death, so it is not recommended
334 and therefore not implemented. What happens is that the tree
335 instance that "clone" is actually called upon is detached from the
336 tree, and becomes a root node, all if the cloned children are then
337 attached as children of that tree. I personally think this is more
338 intuitive then to have the cloning crawl back up the tree is not
339 what I think most people would expect.
340 cloneShallow
342 This method is an alternate option to the plain "clone" method.
343 This method allows the cloning of single Tree::Simple object while
344 retaining connections to the rest of the tree/hierarchy.
345 Misc. Methods
347 DESTROY
348 To avoid memory leaks through uncleaned-up circular references, we
349 implement the "DESTROY" method. This method will attempt to call
350 "DESTROY" on each of its children (if it has any). This will result
351 in a cascade of calls to "DESTROY" on down the tree. It also cleans
352 up it's parental relations as well.
353 Because of perl's reference counting scheme and how that interacts
355 with circular references, if you want an object to be properly
356 reaped you should manually call "DESTROY". This is especially
357 nessecary if your object has any children. See the section on
358 "CIRCULAR REFERENCES" for more information.
359 fixDepth
361 Tree::Simple will manage your tree's depth field for you using this
362 method. You should never need to call it on your own, however if
363 you ever did need to, here is it. Running this method will traverse
364 your all the invocant's sub-trees correcting the depth as it goes.
365 fixHeight
367 Tree::Simple will manage your tree's height field for you using
368 this method. You should never need to call it on your own, however
369 if you ever did need to, here is it. Running this method will
370 correct the heights of the current tree and all it's ancestors.
371 fixWidth
373 Tree::Simple will manage your tree's width field for you using this
374 method. You should never need to call it on your own, however if
375 you ever did need to, here is it. Running this method will correct
376 the widths of the current tree and all it's ancestors.
377 Private Methods
379 I would not normally document private methods, but in case you need to
380 subclass Tree::Simple, here they are.
381 _init ($node, $parent, $children)
383 This method is here largely to facilitate subclassing. This method
384 is called by new to initialize the object, where new's primary
385 responsibility is creating the instance.
386 _setParent ($parent)
388 This method sets up the parental relationship. It is for internal
389 use only.
390 _setHeight ($child)
392 This method will set the height field based upon the height of the
393 given $child.
394
396 I have revised the model by which Tree::Simple deals with ciruclar
397 references. In the past all circular references had to be manually
398 destroyed by calling DESTROY. The call to DESTROY would then call
399 DESTROY on all the children, and therefore cascade down the tree. This
400 however was not always what was needed, nor what made sense, so I have
401 now revised the model to handle things in what I feel is a more
402 consistent and sane way.
403 Circular references are now managed with the simple idea that the
405 parent makes the descisions for the child. This means that child-to-
406 parent references are weak, while parent-to-child references are
407 strong. So if a parent is destroyed it will force all it's children to
408 detach from it, however, if a child is destroyed it will not be
409 detached from it's parent.
410 Optional Weak References
412 By default, you are still required to call DESTROY in order for things
413 to happen. However I have now added the option to use weak references,
414 which alleviates the need for the manual call to DESTROY and allows
415 Tree::Simple to manage this automatically. This is accomplished with a
416 compile time setting like this:
417 use Tree::Simple 'use_weak_refs';
419 And from that point on Tree::Simple will use weak references to allow
421 for perl's reference counting to clean things up properly.
422 For those who are unfamilar with weak references, and how they affect
424 the reference counts, here is a simple illustration. First is the
425 normal model that Tree::Simple uses:
426 +---------------+
428 | Tree::Simple1 |<---------------------+
429 +---------------+ |
430 | parent | |
431 | children |-+ |
432 +---------------+ | |
433 | |
434 | +---------------+ |
435 +->| Tree::Simple2 | |
436 +---------------+ |
437 | parent |-+
438 | children |
439 +---------------+
440 Here, Tree::Simple1 has a reference count of 2 (one for the original
442 variable it is assigned to, and one for the parent reference in
443 Tree::Simple2), and Tree::Simple2 has a reference count of 1 (for the
444 child reference in Tree::Simple2).
445 Now, with weak references:
447 +---------------+
449 | Tree::Simple1 |.......................
450 +---------------+ :
451 | parent | :
452 | children |-+ : <--[ weak reference ]
453 +---------------+ | :
454 | :
455 | +---------------+ :
456 +->| Tree::Simple2 | :
457 +---------------+ :
458 | parent |..
459 | children |
460 +---------------+
461 Now Tree::Simple1 has a reference count of 1 (for the variable it is
463 assigned to) and 1 weakened reference (for the parent reference in
464 Tree::Simple2). And Tree::Simple2 has a reference count of 1, just as
465 before.
466
468 None that I am aware of. The code is pretty thoroughly tested (see
469 "CODE COVERAGE" below) and is based on an (non-publicly released)
470 module which I had used in production systems for about 3 years without
471 incident. Of course, if you find a bug, let me know, and I will be sure
472 to fix it.
473
475 I use Devel::Cover to test the code coverage of my tests, below is the
476 Devel::Cover report on this module's test suite.
477 ---------------------------- ------ ------ ------ ------ ------ ------ ------
479 File stmt branch cond sub pod time total
480 ---------------------------- ------ ------ ------ ------ ------ ------ ------
481 Tree/Simple.pm 99.6 96.0 92.3 100.0 97.0 95.5 98.0
482 Tree/Simple/Visitor.pm 100.0 96.2 88.2 100.0 100.0 4.5 97.7
483 ---------------------------- ------ ------ ------ ------ ------ ------ ------
484 Total 99.7 96.1 91.1 100.0 97.6 100.0 97.9
485 ---------------------------- ------ ------ ------ ------ ------ ------ ------
486
488 I have written a number of other modules which use or augment this
489 module, they are describes below and available on CPAN.
490 Tree::Parser - A module for parsing formatted files into Tree::Simple
492 hierarchies.
493 Tree::Simple::View - A set of classes for viewing Tree::Simple
494 hierarchies in various output formats.
495 Tree::Simple::VisitorFactory - A set of several useful Visitor objects
496 for Tree::Simple objects.
497 Tree::Binary - If you are looking for a binary tree, this you might
498 want to check this one out.
499 Also, the author of Data::TreeDumper and I have worked together to make
501 sure that Tree::Simple and his module work well together. If you need
502 a quick and handy way to dump out a Tree::Simple heirarchy, this module
503 does an excellent job (and plenty more as well).
504 I have also recently stumbled upon some packaged distributions of
506 Tree::Simple for the various Unix flavors. Here are some links:
507 FreeBSD Port - http://www.freshports.org/devel/p5-Tree-Simple/
509 <http://www.freshports.org/devel/p5-Tree-Simple/>
510 Debian Package -
511 http://packages.debian.org/unstable/perl/libtree-simple-perl
512 <http://packages.debian.org/unstable/perl/libtree-simple-perl>
513 Linux RPM - <http://rpmpan.sourceforge.net/Tree.html>
514
516 There are a few other Tree modules out there, here is a quick
517 comparison between Tree::Simple and them. Obviously I am biased, so
518 take what I say with a grain of salt, and keep in mind, I wrote
519 Tree::Simple because I could not find a Tree module that suited my
520 needs. If Tree::Simple does not fit your needs, I recommend looking at
521 these modules. Please note that I am only listing Tree::* modules I am
522 familiar with here, if you think I have missed a module, please let me
523 know. I have also seen a few tree-ish modules outside of the Tree::*
524 namespace, but most of them are part of another distribution
525 (HTML::Tree, Pod::Tree, etc) and are likely specialized in purpose.
526 Tree::DAG_Node
528 This module seems pretty stable and very robust with a lot of
529 functionality. However, Tree::DAG_Node does not come with any
530 automated tests. It's test.pl file simply checks the module loads
531 and nothing else. While I am sure the author tested his code, I
532 would feel better if I was able to see that. The module is approx.
533 3000 lines with POD, and 1,500 without the POD. The shear depth and
534 detail of the documentation and the ratio of code to documentation
535 is impressive, and not to be taken lightly. But given that it is a
536 well known fact that the likeliness of bugs increases along side
537 the size of the code, I do not feel comfortable with large modules
538 like this which have no tests.
539 All this said, I am not a huge fan of the API either, I prefer the
541 gender neutral approach in Tree::Simple to the mother/daughter
542 style of Tree::DAG_Node. I also feel very strongly that
543 Tree::DAG_Node is trying to do much more than makes sense in a
544 single module, and is offering too many ways to do the same or
545 similar things.
546 However, of all the Tree::* modules out there, Tree::DAG_Node seems
548 to be one of the favorites, so it may be worth investigating.
549 Tree::MultiNode
551 I am not very familiar with this module, however, I have heard some
552 good reviews of it, so I thought it deserved mention here. I
553 believe it is based upon C++ code found in the book Algorithms in
554 C++ by Robert Sedgwick. It uses a number of interesting ideas,
555 such as a ::Handle object to traverse the tree with (similar to
556 Visitors, but also seem to be to be kind of like a cursor).
557 However, like Tree::DAG_Node, it is somewhat lacking in tests and
558 has only 6 tests in its suite. It also has one glaring bug, which
559 is that there is currently no way to remove a child node.
560 Tree::Nary
562 It is a (somewhat) direct translation of the N-ary tree from the
563 GLIB library, and the API is based on that. GLIB is a C library,
564 which means this is a very C-ish API. That doesn't appeal to me, it
565 might to you, to each their own.
566 This module is similar in intent to Tree::Simple. It implements a
568 tree with n branches and has polymorphic node containers. It
569 implements much of the same methods as Tree::Simple and a few
570 others on top of that, but being based on a C library, is not very
571 OO. In most of the method calls the $self argument is not used and
572 the second argument $node is. Tree::Simple is a much more OO
573 module than Tree::Nary, so while they are similar in functionality
574 they greatly differ in implementation style.
575 Tree
577 This module is pretty old, it has not been updated since Oct. 31,
578 1999 and is still on version 0.01. It also seems to be (from the
579 limited documentation) a binary and a balanced binary tree,
580 Tree::Simple is an n-ary tree, and makes no attempt to balance
581 anything.
582 Tree::Ternary
584 This module is older than Tree, last update was Sept. 24th, 1999.
585 It seems to be a special purpose tree, for storing and accessing
586 strings, not general purpose like Tree::Simple.
587 Tree::Ternary_XS
589 This module is an XS implementation of the above tree type.
590 Tree::Trie
592 This too is a specialized tree type, it sounds similar to the
593 Tree::Ternary, but it much newer (latest release in 2003). It seems
594 specialized for the lookup and retrieval of information like a
595 hash.
596 Tree::M
598 Is a wrapper for a C++ library, whereas Tree::Simple is pure-perl.
599 It also seems to be a more specialized implementation of a tree,
600 therefore not really the same as Tree::Simple.
601 Tree::Fat
603 Is a wrapper around a C library, again Tree::Simple is pure-perl.
604 The author describes FAT-trees as a combination of a Tree and an
605 array. It looks like a pretty mean and lean module, and good if you
606 need speed and are implementing a custom data-store of some kind.
607 The author points out too that the module is designed for embedding
608 and there is not default embedding, so you can't really use it "out
609 of the box".
610
612 Thanks to Nadim Ibn Hamouda El Khemir for making Data::TreeDumper work
613 with Tree::Simple.
614 Thanks to Brett Nuske for his idea for the "getUID" and "setUID"
615 methods.
616 Thanks to whomever submitted the memory leak bug to RT (#7512).
617 Thanks to Mark Thomas for his insight into how to best handle the
618 height and width properties without unessecary recursion.
619 Thanks for Mark Lawrence for the &traverse post-func patch, tests and
620 docs.
621
623 Stevan Little, <stevan@iinteractive.com>
624 Rob Kinyon, <rob@iinteractive.com>
626
628 Copyright 2004-2006 by Infinity Interactive, Inc.
629 <http://www.iinteractive.com>
631 This library is free software; you can redistribute it and/or modify it
633 under the same terms as Perl itself.
634perl v5.12.0 2007-11-11 Tree::Simple(3)