1 .\" Automatically generated by Pod::Man v1.37, Pod::Parser v1.3
4 .\" ========================================================================
5 .de Sh \" Subsection heading
13 .de Sp \" Vertical space (when we can't use .PP)
17 .de Vb \" Begin verbatim text
22 .de Ve \" End verbatim text
26 .\" Set up some character translations and predefined strings. \*(-- will
27 .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
28 .\" double quote, and \*(R" will give a right double quote. | will give a
29 .\" real vertical bar. \*(C+ will give a nicer C++. Capital omega is used to
30 .\" do unbreakable dashes and therefore won't be available. \*(C` and \*(C'
31 .\" expand to `' in nroff, nothing in troff, for use with C<>.
33 .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
37 . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
38 . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch
51 .\" If the F register is turned on, we'll generate index entries on stderr for
52 .\" titles (.TH), headers (.SH), subsections (.Sh), items (.Ip), and index
53 .\" entries marked with X<> in POD. Of course, you'll have to process the
54 .\" output yourself in some meaningful fashion.
57 . tm Index:\\$1\t\\n%\t"\\$2"
63 .\" For nroff, turn off justification. Always turn off hyphenation; it makes
64 .\" way too many mistakes in technical documents.
68 .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
69 .\" Fear. Run. Save yourself. No user-serviceable parts.
70 . \" fudge factors for nroff and troff
79 . ds #H ((1u-(\\\\n(.fu%2u))*.13m)
85 . \" simple accents for nroff and troff
95 . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
96 . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
97 . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
98 . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
99 . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
100 . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
102 . \" troff and (daisy-wheel) nroff accents
103 .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
104 .ds 8 \h'\*(#H'\(*b\h'-\*(#H'
105 .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
106 .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
107 .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
108 .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
109 .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
110 .ds ae a\h'-(\w'a'u*4/10)'e
111 .ds Ae A\h'-(\w'A'u*4/10)'E
112 . \" corrections for vroff
113 .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
114 .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
115 . \" for low resolution devices (crt and lpr)
116 .if \n(.H>23 .if \n(.V>19 \
129 .\" ========================================================================
131 .IX Title "Tree::Simple 3"
132 .TH Tree::Simple 3 "2007-11-11" "perl v5.8.7" "User Contributed Perl Documentation"
134 Tree::Simple \- A simple tree object
136 .IX Header "SYNOPSIS"
142 \& # make a tree root
143 \& my $tree = Tree::Simple\->new("0", Tree::Simple\->ROOT);
147 \& # explicity add a child to it
148 \& $tree\->addChild(Tree::Simple\->new("1"));
152 \& # specify the parent when creating
153 \& # an instance and it adds the child implicity
154 \& my $sub_tree = Tree::Simple\->new("2", $tree);
158 \& # chain method calls
159 \& $tree\->getChild(0)\->addChild(Tree::Simple\->new("1.1"));
163 \& # add more than one child at a time
164 \& $sub_tree\->addChildren(
165 \& Tree::Simple\->new("2.1"),
166 \& Tree::Simple\->new("2.2")
172 \& $sub_tree\->addSibling(Tree::Simple\->new("3"));
176 \& # insert children a specified index
177 \& $sub_tree\->insertChild(1, Tree::Simple\->new("2.1a"));
181 \& # clean up circular references
182 \& $tree\->DESTROY();
185 .IX Header "DESCRIPTION"
186 This module in an fully object-oriented implementation of a simple n\-ary
187 tree. It is built upon the concept of parent-child relationships, so
188 therefore every \fBTree::Simple\fR object has both a parent and a set of
189 children (who themselves may have children, and so on). Every \fBTree::Simple\fR
190 object also has siblings, as they are just the children of their immediate
193 It is can be used to model hierarchal information such as a file\-system,
194 the organizational structure of a company, an object inheritance hierarchy,
195 versioned files from a version control system or even an abstract syntax
196 tree for use in a parser. It makes no assumptions as to your intended usage,
197 but instead simply provides the structure and means of accessing and
198 traversing said structure.
200 This module uses exceptions and a minimal Design By Contract style. All method
201 arguments are required unless specified in the documentation, if a required
202 argument is not defined an exception will usually be thrown. Many arguments
203 are also required to be of a specific type, for instance the \f(CW$parent\fR
204 argument to the constructor \fBmust\fR be a \fBTree::Simple\fR object or an object
205 derived from \fBTree::Simple\fR, otherwise an exception is thrown. This may seems
206 harsh to some, but this allows me to have the confidence that my code works as
207 I intend, and for you to enjoy the same level of confidence when using this
208 module. Note however that this module does not use any Exception or Error module,
209 the exceptions are just strings thrown with \f(CW\*(C`die\*(C'\fR.
211 I consider this module to be production stable, it is based on a module which has
212 been in use on a few production systems for approx. 2 years now with no issue.
213 The only difference is that the code has been cleaned up a bit, comments added and
214 the thorough tests written for its public release. I am confident it behaves as
215 I would expect it to, and is (as far as I know) bug\-free. I have not stress-tested
216 it under extreme duress, but I don't so much intend for it to be used in that
217 type of situation. If this module cannot keep up with your Tree needs, i suggest
218 switching to one of the modules listed in the \*(L"\s-1OTHER\s0 \s-1TREE\s0 \s-1MODULES\s0\*(R" section below.
220 .IX Header "CONSTANTS"
221 .IP "\fB\s-1ROOT\s0\fR" 4
223 This class constant serves as a placeholder for the root of our tree. If a tree
224 does not have a parent, then it is considered a root.
228 .IX Subsection "Constructor"
229 .ie n .IP "\fBnew ($node, \fB$parent\fB)\fR" 4
230 .el .IP "\fBnew ($node, \f(CB$parent\fB)\fR" 4
231 .IX Item "new ($node, $parent)"
232 The constructor accepts two arguments a \f(CW$node\fR value and an optional \f(CW$parent\fR.
233 The \f(CW$node\fR value can be any scalar value (which includes references and objects).
234 The optional \f(CW$parent\fR value must be a \fBTree::Simple\fR object, or an object
235 derived from \fBTree::Simple\fR. Setting this value implies that your new tree is a
236 child of the parent tree, and therefore adds it to the parent's children. If the
237 \&\f(CW$parent\fR is not specified then its value defaults to \s-1ROOT\s0.
238 .Sh "Mutator Methods"
239 .IX Subsection "Mutator Methods"
240 .IP "\fBsetNodeValue ($node_value)\fR" 4
241 .IX Item "setNodeValue ($node_value)"
242 This sets the node value to the scalar \f(CW$node_value\fR, an exception is thrown if
243 \&\f(CW$node_value\fR is not defined.
244 .IP "\fBsetUID ($uid)\fR" 4
245 .IX Item "setUID ($uid)"
246 This allows you to set your own unique \s-1ID\s0 for this specific Tree::Simple object.
247 A default value derived from the object's hex address is provided for you, so use
248 of this method is entirely optional. It is the responsibility of the user to
249 ensure the value's uniqueness, all that is tested by this method is that \f(CW$uid\fR
250 is a true value (evaluates to true in a boolean context). For even more information
251 about the Tree::Simple \s-1UID\s0 see the \f(CW\*(C`getUID\*(C'\fR method.
252 .IP "\fBaddChild ($tree)\fR" 4
253 .IX Item "addChild ($tree)"
254 This method accepts only \fBTree::Simple\fR objects or objects derived from
255 \&\fBTree::Simple\fR, an exception is thrown otherwise. This method will append
256 the given \f(CW$tree\fR to the end of it's children list, and set up the correct
257 parent-child relationships. This method is set up to return its invocant so
258 that method call chaining can be possible. Such as:
261 \& my $tree = Tree::Simple\->new("root")\->addChild(Tree::Simple\->new("child one"));
267 \& my $tree = Tree::Simple\->new("root")\->addChild(
268 \& Tree::Simple\->new("1.0")\->addChild(
269 \& Tree::Simple\->new("1.0.1")
273 .IP "\fBaddChildren (@trees)\fR" 4
274 .IX Item "addChildren (@trees)"
275 This method accepts an array of \fBTree::Simple\fR objects, and adds them to
276 it's children list. Like \f(CW\*(C`addChild\*(C'\fR this method will return its invocant
277 to allow for method call chaining.
278 .ie n .IP "\fBinsertChild ($index, \fB$tree\fB)\fR" 4
279 .el .IP "\fBinsertChild ($index, \f(CB$tree\fB)\fR" 4
280 .IX Item "insertChild ($index, $tree)"
281 This method accepts a numeric \f(CW$index\fR and a \fBTree::Simple\fR object (\f(CW$tree\fR),
282 and inserts the \f(CW$tree\fR into the children list at the specified \f(CW$index\fR.
283 This results in the shifting down of all children after the \f(CW$index\fR. The
284 \&\f(CW$index\fR is checked to be sure it is the bounds of the child list, if it
285 out of bounds an exception is thrown. The \f(CW$tree\fR argument's type is
286 verified to be a \fBTree::Simple\fR or \fBTree::Simple\fR derived object, if
287 this condition fails, an exception is thrown.
288 .ie n .IP "\fBinsertChildren ($index, \fB@trees\fB)\fR" 4
289 .el .IP "\fBinsertChildren ($index, \f(CB@trees\fB)\fR" 4
290 .IX Item "insertChildren ($index, @trees)"
291 This method functions much as insertChild does, but instead of inserting a
292 single \fBTree::Simple\fR, it inserts an array of \fBTree::Simple\fR objects. It
293 too bounds checks the value of \f(CW$index\fR and type checks the objects in
294 \&\f(CW@trees\fR just as \f(CW\*(C`insertChild\*(C'\fR does.
295 .ie n .IP "\fBremoveChild\fR ($child | $index)>" 4
296 .el .IP "\fBremoveChild\fR ($child | \f(CW$index\fR)>" 4
297 .IX Item "removeChild ($child | $index)>"
298 Accepts two different arguemnts. If given a \fBTree::Simple\fR object (\f(CW$child\fR),
299 this method finds that specific \f(CW$child\fR by comparing it with all the other
300 children until it finds a match. At which point the \f(CW$child\fR is removed. If
301 no match is found, and exception is thrown. If a non\-\fBTree::Simple\fR object
302 is given as the \f(CW$child\fR argument, an exception is thrown.
304 This method also accepts a numeric \f(CW$index\fR and removes the child found at
305 that index from it's list of children. The \f(CW$index\fR is bounds checked, if
306 this condition fail, an exception is thrown.
308 When a child is removed, it results in the shifting up of all children after
309 it, and the removed child is returned. The removed child is properly
310 disconnected from the tree and all its references to its old parent are
311 removed. However, in order to properly clean up and circular references
312 the removed child might have, it is advised to call it's \f(CW\*(C`DESTROY\*(C'\fR method.
313 See the \*(L"\s-1CIRCULAR\s0 \s-1REFERENCES\s0\*(R" section for more information.
314 .IP "\fBaddSibling ($tree)\fR" 4
315 .IX Item "addSibling ($tree)"
317 .IP "\fBaddSiblings (@trees)\fR" 4
318 .IX Item "addSiblings (@trees)"
319 .ie n .IP "\fBinsertSibling ($index, \fB$tree\fB)\fR" 4
320 .el .IP "\fBinsertSibling ($index, \f(CB$tree\fB)\fR" 4
321 .IX Item "insertSibling ($index, $tree)"
322 .ie n .IP "\fBinsertSiblings ($index, \fB@trees\fB)\fR" 4
323 .el .IP "\fBinsertSiblings ($index, \f(CB@trees\fB)\fR" 4
324 .IX Item "insertSiblings ($index, @trees)"
326 The \f(CW\*(C`addSibling\*(C'\fR, \f(CW\*(C`addSiblings\*(C'\fR, \f(CW\*(C`insertSibling\*(C'\fR and \f(CW\*(C`insertSiblings\*(C'\fR
327 methods pass along their arguments to the \f(CW\*(C`addChild\*(C'\fR, \f(CW\*(C`addChildren\*(C'\fR,
328 \&\f(CW\*(C`insertChild\*(C'\fR and \f(CW\*(C`insertChildren\*(C'\fR methods of their parent object
329 respectively. This eliminates the need to overload these methods in subclasses
330 which may have specialized versions of the *Child(ren) methods. The one
331 exceptions is that if an attempt it made to add or insert siblings to the
332 \&\fB\s-1ROOT\s0\fR of the tree then an exception is thrown.
335 There is no \f(CW\*(C`removeSibling\*(C'\fR method as I felt it was probably a bad idea.
336 The same effect can be achieved by manual upwards traversal.
337 .Sh "Accessor Methods"
338 .IX Subsection "Accessor Methods"
339 .IP "\fBgetNodeValue\fR" 4
340 .IX Item "getNodeValue"
341 This returns the value stored in the object's node field.
344 This returns the unique \s-1ID\s0 associated with this particular tree. This can
345 be custom set using the \f(CW\*(C`setUID\*(C'\fR method, or you can just use the default.
346 The default is the hex-address extracted from the stringified Tree::Simple
347 object. This may not be a \fIuniversally\fR unique identifier, but it should
348 be adequate for at least the current instance of your perl interpreter. If
349 you need a \s-1UUID\s0, one can be generated with an outside module (there are
350 many to choose from on \s-1CPAN\s0) and the \f(CW\*(C`setUID\*(C'\fR method (see above).
351 .IP "\fBgetChild ($index)\fR" 4
352 .IX Item "getChild ($index)"
353 This returns the child (a \fBTree::Simple\fR object) found at the specified
354 \&\f(CW$index\fR. Note that we do use standard zero-based array indexing.
355 .IP "\fBgetAllChildren\fR" 4
356 .IX Item "getAllChildren"
357 This returns an array of all the children (all \fBTree::Simple\fR objects).
358 It will return an array reference in scalar context.
359 .IP "\fBgetSibling ($index)\fR" 4
360 .IX Item "getSibling ($index)"
362 .IP "\fBgetAllSiblings\fR" 4
363 .IX Item "getAllSiblings"
365 Much like \f(CW\*(C`addSibling\*(C'\fR and \f(CW\*(C`addSiblings\*(C'\fR, these two methods simply call
366 \&\f(CW\*(C`getChild\*(C'\fR and \f(CW\*(C`getAllChildren\*(C'\fR on the invocant's parent.
367 .IP "\fBgetDepth\fR" 4
369 Returns a number representing the invocant's depth within the hierarchy of
370 \&\fBTree::Simple\fR objects.
372 \&\fB\s-1NOTE:\s0\fR A \f(CW\*(C`ROOT\*(C'\fR tree has the depth of \-1. This be because Tree::Simple
373 assumes that a tree's root will usually not contain data, but just be an
374 anchor for the data-containing branches. This may not be intuitive in all
375 cases, so I mention it here.
376 .IP "\fBgetParent\fR" 4
378 Returns the invocant's parent, which could be either \fB\s-1ROOT\s0\fR or a
379 \&\fBTree::Simple\fR object.
380 .IP "\fBgetHeight\fR" 4
382 Returns a number representing the length of the longest path from the current
383 tree to the furthest leaf node.
384 .IP "\fBgetWidth\fR" 4
386 Returns the a number representing the breadth of the current tree, basically
387 it is a count of all the leaf nodes.
388 .IP "\fBgetChildCount\fR" 4
389 .IX Item "getChildCount"
390 Returns the number of children the invocant contains.
391 .IP "\fBgetIndex\fR" 4
393 Returns the index of this tree within its parent's child list. Returns \-1 if
394 the tree is the root.
395 .Sh "Predicate Methods"
396 .IX Subsection "Predicate Methods"
399 Returns true (1) if the invocant does not have any children, false (0) otherwise.
402 Returns true (1) if the invocant's \*(L"parent\*(R" field is \fB\s-1ROOT\s0\fR, returns false
404 .Sh "Recursive Methods"
405 .IX Subsection "Recursive Methods"
406 .IP "\fBtraverse ($func, ?$postfunc)\fR" 4
407 .IX Item "traverse ($func, ?$postfunc)"
408 This method accepts two arguments a mandatory \f(CW$func\fR and an optional
409 \&\f(CW$postfunc\fR. If the argument \f(CW$func\fR is not defined then an exception
410 is thrown. If \f(CW$func\fR or \f(CW$postfunc\fR are not in fact \s-1CODE\s0 references
411 then an exception is thrown. The function \f(CW$func\fR is then applied
412 recursively to all the children of the invocant. If given, the function
413 \&\f(CW$postfunc\fR will be applied to each child after the child's children
416 Here is an example of a traversal function that will print out the
417 hierarchy as a tabbed in list.
420 \& $tree\->traverse(sub {
422 \& print (("\et" x $_tree\->getDepth()), $_tree\->getNodeValue(), "\en");
426 Here is an example of a traversal function that will print out the
427 hierarchy in an XML-style format.
430 \& $tree\->traverse(sub {
432 \& print ((' ' x $_tree\->getDepth()),
433 \& '<', $_tree\->getNodeValue(),'>',"\en");
437 \& print ((' ' x $_tree\->getDepth()),
438 \& '</', $_tree\->getNodeValue(),'>',"\en");
443 Returns the total number of nodes in the current tree and all its sub\-trees.
446 This method has also been \fBdeprecated\fR in favor of the \f(CW\*(C`getHeight\*(C'\fR method above,
447 it remains as an alias to \f(CW\*(C`getHeight\*(C'\fR for backwards compatability.
449 \&\fB\s-1NOTE:\s0\fR This is also no longer a recursive method which get's it's value on demand,
450 but a value stored in the Tree::Simple object itself, hopefully making it much
451 more efficient and usable.
452 .Sh "Visitor Methods"
453 .IX Subsection "Visitor Methods"
454 .IP "\fBaccept ($visitor)\fR" 4
455 .IX Item "accept ($visitor)"
456 It accepts either a \fBTree::Simple::Visitor\fR object (which includes classes derived
457 from \fBTree::Simple::Visitor\fR), or an object who has the \f(CW\*(C`visit\*(C'\fR method available
458 (tested with \f(CW\*(C`$visitor\->can('visit')\*(C'\fR). If these qualifications are not met,
459 and exception will be thrown. We then run the Visitor's \f(CW\*(C`visit\*(C'\fR method giving the
460 current tree as its argument.
462 I have also created a number of Visitor objects and packaged them into the
463 \&\fBTree::Simple::VisitorFactory\fR.
464 .Sh "Cloning Methods"
465 .IX Subsection "Cloning Methods"
466 Cloning a tree can be an extremly expensive operation for large trees, so we provide
467 two options for cloning, a deep clone and a shallow clone.
469 When a Tree::Simple object is cloned, the node is deep-copied in the following manner.
470 If we find a normal scalar value (non\-reference), we simply copy it. If we find an
471 object, we attempt to call \f(CW\*(C`clone\*(C'\fR on it, otherwise we just copy the reference (since
472 we assume the object does not want to be cloned). If we find a \s-1SCALAR\s0, \s-1REF\s0 reference we
473 copy the value contained within it. If we find a \s-1HASH\s0 or \s-1ARRAY\s0 reference we copy the
474 reference and recursively copy all the elements within it (following these exact
475 guidelines). We also do our best to assure that circular references are cloned
476 only once and connections restored correctly. This cloning will not be able to copy
477 \&\s-1CODE\s0, RegExp and \s-1GLOB\s0 references, as they are pretty much impossible to clone. We
478 also do not handle \f(CW\*(C`tied\*(C'\fR objects, and they will simply be copied as plain
479 references, and not re\-\f(CW\*(C`tied\*(C'\fR.
482 The clone method does a full deep-copy clone of the object, calling \f(CW\*(C`clone\*(C'\fR recursively
483 on all its children. This does not call \f(CW\*(C`clone\*(C'\fR on the parent tree however. Doing
484 this would result in a slowly degenerating spiral of recursive death, so it is not
485 recommended and therefore not implemented. What happens is that the tree instance
486 that \f(CW\*(C`clone\*(C'\fR is actually called upon is detached from the tree, and becomes a root
487 node, all if the cloned children are then attached as children of that tree. I personally
488 think this is more intuitive then to have the cloning crawl back \fIup\fR the tree is not
489 what I think most people would expect.
490 .IP "\fBcloneShallow\fR" 4
491 .IX Item "cloneShallow"
492 This method is an alternate option to the plain \f(CW\*(C`clone\*(C'\fR method. This method allows the
493 cloning of single \fBTree::Simple\fR object while retaining connections to the rest of the
496 .IX Subsection "Misc. Methods"
497 .IP "\fB\s-1DESTROY\s0\fR" 4
499 To avoid memory leaks through uncleaned-up circular references, we implement the
500 \&\f(CW\*(C`DESTROY\*(C'\fR method. This method will attempt to call \f(CW\*(C`DESTROY\*(C'\fR on each of its
501 children (if it has any). This will result in a cascade of calls to \f(CW\*(C`DESTROY\*(C'\fR on
502 down the tree. It also cleans up it's parental relations as well.
504 Because of perl's reference counting scheme and how that interacts with circular
505 references, if you want an object to be properly reaped you should manually call
506 \&\f(CW\*(C`DESTROY\*(C'\fR. This is especially nessecary if your object has any children. See the
507 section on \*(L"\s-1CIRCULAR\s0 \s-1REFERENCES\s0\*(R" for more information.
508 .IP "\fBfixDepth\fR" 4
510 Tree::Simple will manage your tree's depth field for you using this method. You
511 should never need to call it on your own, however if you ever did need to, here
512 is it. Running this method will traverse your all the invocant's sub-trees
513 correcting the depth as it goes.
514 .IP "\fBfixHeight\fR" 4
516 Tree::Simple will manage your tree's height field for you using this method.
517 You should never need to call it on your own, however if you ever did need to,
518 here is it. Running this method will correct the heights of the current tree
519 and all it's ancestors.
520 .IP "\fBfixWidth\fR" 4
522 Tree::Simple will manage your tree's width field for you using this method. You
523 should never need to call it on your own, however if you ever did need to,
524 here is it. Running this method will correct the widths of the current tree
525 and all it's ancestors.
526 .Sh "Private Methods"
527 .IX Subsection "Private Methods"
528 I would not normally document private methods, but in case you need to subclass
529 Tree::Simple, here they are.
530 .ie n .IP "\fB_init ($node, \fB$parent\fB, \f(BI$children\fB)\fR" 4
531 .el .IP "\fB_init ($node, \f(CB$parent\fB, \f(CB$children\fB)\fR" 4
532 .IX Item "_init ($node, $parent, $children)"
533 This method is here largely to facilitate subclassing. This method is called by
534 new to initialize the object, where new's primary responsibility is creating
536 .IP "\fB_setParent ($parent)\fR" 4
537 .IX Item "_setParent ($parent)"
538 This method sets up the parental relationship. It is for internal use only.
539 .IP "\fB_setHeight ($child)\fR" 4
540 .IX Item "_setHeight ($child)"
541 This method will set the height field based upon the height of the given \f(CW$child\fR.
542 .SH "CIRCULAR REFERENCES"
543 .IX Header "CIRCULAR REFERENCES"
544 I have revised the model by which Tree::Simple deals with ciruclar references.
545 In the past all circular references had to be manually destroyed by calling
546 \&\s-1DESTROY\s0. The call to \s-1DESTROY\s0 would then call \s-1DESTROY\s0 on all the children, and
547 therefore cascade down the tree. This however was not always what was needed,
548 nor what made sense, so I have now revised the model to handle things in what
549 I feel is a more consistent and sane way.
551 Circular references are now managed with the simple idea that the parent makes
552 the descisions for the child. This means that child-to-parent references are
553 weak, while parent-to-child references are strong. So if a parent is destroyed
554 it will force all it's children to detach from it, however, if a child is
555 destroyed it will not be detached from it's parent.
556 .Sh "Optional Weak References"
557 .IX Subsection "Optional Weak References"
558 By default, you are still required to call \s-1DESTROY\s0 in order for things to
559 happen. However I have now added the option to use weak references, which
560 alleviates the need for the manual call to \s-1DESTROY\s0 and allows Tree::Simple
561 to manage this automatically. This is accomplished with a compile time
565 \& use Tree::Simple 'use_weak_refs';
568 And from that point on Tree::Simple will use weak references to allow for
569 perl's reference counting to clean things up properly.
571 For those who are unfamilar with weak references, and how they affect the
572 reference counts, here is a simple illustration. First is the normal model
573 that Tree::Simple uses:
576 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+
577 \& | Tree::Simple1 |<\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+
578 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ |
581 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ | |
583 \& | +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ |
584 \& +\->| Tree::Simple2 | |
585 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ |
588 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+
591 Here, Tree::Simple1 has a reference count of 2 (one for the original
592 variable it is assigned to, and one for the parent reference in
593 Tree::Simple2), and Tree::Simple2 has a reference count of 1 (for the
594 child reference in Tree::Simple2).
596 Now, with weak references:
599 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+
600 \& | Tree::Simple1 |.......................
601 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ :
603 \& | children |\-+ : <\-\-[ weak reference ]
604 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ | :
606 \& | +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ :
607 \& +\->| Tree::Simple2 | :
608 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ :
611 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+
614 Now Tree::Simple1 has a reference count of 1 (for the variable it is
615 assigned to) and 1 weakened reference (for the parent reference in
616 Tree::Simple2). And Tree::Simple2 has a reference count of 1, just
620 None that I am aware of. The code is pretty thoroughly tested (see
621 \&\*(L"\s-1CODE\s0 \s-1COVERAGE\s0\*(R" below) and is based on an (non\-publicly released)
622 module which I had used in production systems for about 3 years without
623 incident. Of course, if you find a bug, let me know, and I will be sure
626 .IX Header "CODE COVERAGE"
627 I use Devel::Cover to test the code coverage of my tests, below
628 is the Devel::Cover report on this module's test suite.
631 \& \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\-
632 \& File stmt branch cond sub pod time total
633 \& \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\-
634 \& Tree/Simple.pm 99.6 96.0 92.3 100.0 97.0 95.5 98.0
635 \& Tree/Simple/Visitor.pm 100.0 96.2 88.2 100.0 100.0 4.5 97.7
636 \& \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\-
637 \& Total 99.7 96.1 91.1 100.0 97.6 100.0 97.9
638 \& \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\- \-\-\-\-\-\-
641 .IX Header "SEE ALSO"
642 I have written a number of other modules which use or augment this
643 module, they are describes below and available on \s-1CPAN\s0.
644 .IP "Tree::Parser \- A module for parsing formatted files into Tree::Simple hierarchies." 4
645 .IX Item "Tree::Parser - A module for parsing formatted files into Tree::Simple hierarchies."
647 .IP "Tree::Simple::View \- A set of classes for viewing Tree::Simple hierarchies in various output formats." 4
648 .IX Item "Tree::Simple::View - A set of classes for viewing Tree::Simple hierarchies in various output formats."
649 .IP "Tree::Simple::VisitorFactory \- A set of several useful Visitor objects for Tree::Simple objects." 4
650 .IX Item "Tree::Simple::VisitorFactory - A set of several useful Visitor objects for Tree::Simple objects."
651 .IP "Tree::Binary \- If you are looking for a binary tree, this you might want to check this one out." 4
652 .IX Item "Tree::Binary - If you are looking for a binary tree, this you might want to check this one out."
655 Also, the author of Data::TreeDumper and I have worked together
656 to make sure that \fBTree::Simple\fR and his module work well together.
657 If you need a quick and handy way to dump out a Tree::Simple heirarchy,
658 this module does an excellent job (and plenty more as well).
660 I have also recently stumbled upon some packaged distributions of
661 Tree::Simple for the various Unix flavors. Here are some links:
662 .IP "FreeBSD Port \- <http://www.freshports.org/devel/p5\-Tree\-Simple/>" 4
663 .IX Item "FreeBSD Port - <http://www.freshports.org/devel/p5-Tree-Simple/>"
665 .IP "Debian Package \- <http://packages.debian.org/unstable/perl/libtree\-simple\-perl>" 4
666 .IX Item "Debian Package - <http://packages.debian.org/unstable/perl/libtree-simple-perl>"
667 .IP "Linux \s-1RPM\s0 \- <http://rpmpan.sourceforge.net/Tree.html>" 4
668 .IX Item "Linux RPM - <http://rpmpan.sourceforge.net/Tree.html>"
670 .SH "OTHER TREE MODULES"
671 .IX Header "OTHER TREE MODULES"
672 There are a few other Tree modules out there, here is a quick comparison
673 between \fBTree::Simple\fR and them. Obviously I am biased, so take what I say
674 with a grain of salt, and keep in mind, I wrote \fBTree::Simple\fR because I
675 could not find a Tree module that suited my needs. If \fBTree::Simple\fR does
676 not fit your needs, I recommend looking at these modules. Please note that
677 I am only listing Tree::* modules I am familiar with here, if you think I
678 have missed a module, please let me know. I have also seen a few tree-ish
679 modules outside of the Tree::* namespace, but most of them are part of
680 another distribution (\fBHTML::Tree\fR, \fBPod::Tree\fR, etc) and are likely
681 specialized in purpose.
682 .IP "Tree::DAG_Node" 4
683 .IX Item "Tree::DAG_Node"
684 This module seems pretty stable and very robust with a lot of functionality.
685 However, \fBTree::DAG_Node\fR does not come with any automated tests. It's
686 \&\fItest.pl\fR file simply checks the module loads and nothing else. While I
687 am sure the author tested his code, I would feel better if I was able to
688 see that. The module is approx. 3000 lines with \s-1POD\s0, and 1,500 without the
689 \&\s-1POD\s0. The shear depth and detail of the documentation and the ratio of code
690 to documentation is impressive, and not to be taken lightly. But given that
691 it is a well known fact that the likeliness of bugs increases along side the
692 size of the code, I do not feel comfortable with large modules like this
695 All this said, I am not a huge fan of the \s-1API\s0 either, I prefer the gender
696 neutral approach in \fBTree::Simple\fR to the mother/daughter style of \fBTree::DAG_Node\fR.
697 I also feel very strongly that \fBTree::DAG_Node\fR is trying to do much more
698 than makes sense in a single module, and is offering too many ways to do
699 the same or similar things.
701 However, of all the Tree::* modules out there, \fBTree::DAG_Node\fR seems to
702 be one of the favorites, so it may be worth investigating.
703 .IP "Tree::MultiNode" 4
704 .IX Item "Tree::MultiNode"
705 I am not very familiar with this module, however, I have heard some good
706 reviews of it, so I thought it deserved mention here. I believe it is
707 based upon \*(C+ code found in the book \fIAlgorithms in \*(C+\fR by Robert Sedgwick.
708 It uses a number of interesting ideas, such as a ::Handle object to traverse
709 the tree with (similar to Visitors, but also seem to be to be kind of like
710 a cursor). However, like \fBTree::DAG_Node\fR, it is somewhat lacking in tests
711 and has only 6 tests in its suite. It also has one glaring bug, which is
712 that there is currently no way to remove a child node.
714 .IX Item "Tree::Nary"
715 It is a (somewhat) direct translation of the N\-ary tree from the \s-1GLIB\s0
716 library, and the \s-1API\s0 is based on that. \s-1GLIB\s0 is a C library, which means
717 this is a very C\-ish \s-1API\s0. That doesn't appeal to me, it might to you, to
720 This module is similar in intent to \fBTree::Simple\fR. It implements a tree
721 with \fIn\fR branches and has polymorphic node containers. It implements much
722 of the same methods as \fBTree::Simple\fR and a few others on top of that, but
723 being based on a C library, is not very \s-1OO\s0. In most of the method calls
724 the \f(CW$self\fR argument is not used and the second argument \f(CW$node\fR is.
725 \&\fBTree::Simple\fR is a much more \s-1OO\s0 module than \fBTree::Nary\fR, so while they
726 are similar in functionality they greatly differ in implementation style.
729 This module is pretty old, it has not been updated since Oct. 31, 1999 and
730 is still on version 0.01. It also seems to be (from the limited documentation)
731 a binary and a balanced binary tree, \fBTree::Simple\fR is an \fIn\fR\-ary tree, and
732 makes no attempt to balance anything.
733 .IP "Tree::Ternary" 4
734 .IX Item "Tree::Ternary"
735 This module is older than \fBTree\fR, last update was Sept. 24th, 1999. It
736 seems to be a special purpose tree, for storing and accessing strings,
737 not general purpose like \fBTree::Simple\fR.
738 .IP "Tree::Ternary_XS" 4
739 .IX Item "Tree::Ternary_XS"
740 This module is an \s-1XS\s0 implementation of the above tree type.
742 .IX Item "Tree::Trie"
743 This too is a specialized tree type, it sounds similar to the \fBTree::Ternary\fR,
744 but it much newer (latest release in 2003). It seems specialized for the lookup
745 and retrieval of information like a hash.
748 Is a wrapper for a \*(C+ library, whereas \fBTree::Simple\fR is pure\-perl. It also
749 seems to be a more specialized implementation of a tree, therefore not really
750 the same as \fBTree::Simple\fR.
753 Is a wrapper around a C library, again \fBTree::Simple\fR is pure\-perl. The author
754 describes FAT-trees as a combination of a Tree and an array. It looks like a
755 pretty mean and lean module, and good if you need speed and are implementing a
756 custom data-store of some kind. The author points out too that the module is
757 designed for embedding and there is not default embedding, so you can't really
758 use it \*(L"out of the box\*(R".
759 .SH "ACKNOWLEDGEMENTS"
760 .IX Header "ACKNOWLEDGEMENTS"
761 .IP "Thanks to Nadim Ibn Hamouda El Khemir for making Data::TreeDumper work with \fBTree::Simple\fR." 4
762 .IX Item "Thanks to Nadim Ibn Hamouda El Khemir for making Data::TreeDumper work with Tree::Simple."
764 .ie n .IP "Thanks to Brett Nuske for his idea for the ""getUID""\fR and \f(CW""setUID"" methods." 4
765 .el .IP "Thanks to Brett Nuske for his idea for the \f(CWgetUID\fR and \f(CWsetUID\fR methods." 4
766 .IX Item "Thanks to Brett Nuske for his idea for the getUID and setUID methods."
767 .IP "Thanks to whomever submitted the memory leak bug to \s-1RT\s0 (#7512)." 4
768 .IX Item "Thanks to whomever submitted the memory leak bug to RT (#7512)."
769 .IP "Thanks to Mark Thomas for his insight into how to best handle the \fIheight\fR and \fIwidth\fR properties without unessecary recursion." 4
770 .IX Item "Thanks to Mark Thomas for his insight into how to best handle the height and width properties without unessecary recursion."
771 .IP "Thanks for Mark Lawrence for the &traverse post-func patch, tests and docs." 4
772 .IX Item "Thanks for Mark Lawrence for the &traverse post-func patch, tests and docs."
776 Stevan Little, <stevan@iinteractive.com>
778 Rob Kinyon, <rob@iinteractive.com>
779 .SH "COPYRIGHT AND LICENSE"
780 .IX Header "COPYRIGHT AND LICENSE"
781 Copyright 2004\-2006 by Infinity Interactive, Inc.
783 <http://www.iinteractive.com>
785 This library is free software; you can redistribute it and/or modify
786 it under the same terms as Perl itself.
projects / catagits/Gitalist.git / blob