1Tree::DAG_Node(3) User Contributed Perl Documentation Tree::DAG_Node(3)
2
6 Tree::DAG_Node - An N-ary tree
7
9 Using as a base class:
10 package Game::Tree::Node;
12 use parent 'Tree::DAG_Node';
14 # Now add your own methods overriding/extending the methods in C<Tree::DAG_Node>...
16 Using as a class of its own:
18 use Tree::DAG_Node;
20 my $root = Tree::DAG_Node->new();
22 $root->name("I'm the tops");
24 my $new_daughter = $root->new_daughter;
25 $new_daughter->name("More");
26 ...
27
29 This class encapsulates/makes/manipulates objects that represent nodes
30 in a tree structure. The tree structure is not an object itself, but is
31 emergent from the linkages you create between nodes. This class
32 provides the methods for making linkages that can be used to build up a
33 tree, while preventing you from ever making any kinds of linkages which
34 are not allowed in a tree (such as having a node be its own mother or
35 ancestor, or having a node have two mothers).
36 This is what I mean by a "tree structure", a bit redundantly stated:
38 o A tree is a special case of an acyclic directed graph
40 o A tree is a network of nodes where there's exactly one root node
41 Also, the only primary relationship between nodes is the mother-
42 daughter relationship.
43 o No node can be its own mother, or its mother's mother, etc
45 o Each node in the tree has exactly one parent
46 Except for the root of course, which is parentless.
47 o Each node can have any number (0 .. N) daughter nodes
49 A given node's daughter nodes constitute an ordered list.
50 However, you are free to consider this ordering irrelevant. Some
52 applications do need daughters to be ordered, so I chose to
53 consider this the general case.
54 o A node can appear in only one tree, and only once in that tree
56 Notably (notable because it doesn't follow from the two above
57 points), a node cannot appear twice in its mother's daughter list.
58 o There's an idea of up versus down
60 Up means towards to the root, and down means away from the root
61 (and towards the leaves).
62 o There's an idea of left versus right
64 Left is toward the start (index 0) of a given node's daughter list,
65 and right is toward the end of a given node's daughter list.
66 Trees as described above have various applications, among them:
68 representing syntactic constituency, in formal linguistics;
69 representing contingencies in a game tree; representing abstract syntax
70 in the parsing of any computer language -- whether in expression trees
71 for programming languages, or constituency in the parse of a markup
72 language document. (Some of these might not use the fact that
73 daughters are ordered.)
74 (Note: B-Trees are a very special case of the above kinds of trees, and
76 are best treated with their own class. Check CPAN for modules
77 encapsulating B-Trees; or if you actually want a database, and for some
78 reason ended up looking here, go look at AnyDBM_File.)
79 Many base classes are not usable except as such -- but "Tree::DAG_Node"
81 can be used as a normal class. You can go ahead and say:
82 use Tree::DAG_Node;
84 my $root = Tree::DAG_Node->new();
85 $root->name("I'm the tops");
86 $new_daughter = Tree::DAG_Node->new();
87 $new_daughter->name("More");
88 $root->add_daughter($new_daughter);
89 and so on, constructing and linking objects from "Tree::DAG_Node" and
91 making useful tree structures out of them.
92
94 This class is big and provides lots of methods. If your problem is
95 simple (say, just representing a simple parse tree), this class might
96 seem like using an atomic sledgehammer to swat a fly. But the
97 complexity of this module's bells and whistles shouldn't detract from
98 the efficiency of using this class for a simple purpose. In fact, I'd
99 be very surprised if any one user ever had use for more that even a
100 third of the methods in this class. And remember: an atomic
101 sledgehammer will kill that fly.
102
104 Implementationally, each node in a tree is an object, in the sense of
105 being an arbitrarily complex data structure that belongs to a class
106 (presumably "Tree::DAG_Node", or ones derived from it) that provides
107 methods.
108 The attributes of a node-object are:
110 o mother -- this node's mother. undef if this is a root
112 o daughters -- the (possibly empty) list of daughters of this node
113 o name -- the name for this node
114 Need not be unique, or even printable. This is printed in some of
115 the various dumper methods, but it's up to you if you don't put
116 anything meaningful or printable here.
117 o attributes -- whatever the user wants to use it for
119 Presumably a hashref to whatever other attributes the user wants to
120 store without risk of colliding with the object's real attributes.
121 (Example usage: attributes to an SGML tag -- you definitely
122 wouldn't want the existence of a "mother=foo" pair in such a tag to
123 collide with a node object's 'mother' attribute.)
124 Aside from (by default) initializing it to {}, and having the
126 access method called "attributes" (described a ways below), I don't
127 do anything with the "attributes" in this module. I basically
128 intended this so that users who don't want/need to bother deriving
129 a class from "Tree::DAG_Node", could still attach whatever data
130 they wanted in a node.
131 "mother" and "daughters" are attributes that relate to linkage -- they
133 are never written to directly, but are changed as appropriate by the
134 "linkage methods", discussed below.
135 The other two (and whatever others you may add in derived classes) are
137 simply accessed thru the same-named methods, discussed further below.
138 About The Documented Interface
140 Stick to the documented interface (and comments in the source --
141 especially ones saying "undocumented!" and/or "disfavored!" -- do not
142 count as documentation!), and don't rely on any behavior that's not in
143 the documented interface.
144 Specifically, unless the documentation for a particular method says
146 "this method returns thus-and-such a value", then you should not rely
147 on it returning anything meaningful.
148 A passing acquaintance with at least the broader details of the source
150 code for this class is assumed for anyone using this class as a base
151 class -- especially if you're overriding existing methods, and
152 definitely if you're overriding linkage methods.
153
155 the constructor CLASS->new() or CLASS->new($options)
156 This creates a new node object, calls $object->_init($options) to
157 provide it sane defaults (like: undef name, undef mother, no
158 daughters, 'attributes' setting of a new empty hashref), and
159 returns the object created. (If you just said "CLASS->new()" or
160 "CLASS->new", then it pretends you called "CLASS->new({})".)
161 Currently no options for putting in hashref $options are part of
163 the documented interface, but the options is here in case you want
164 to add such behavior in a derived class.
165 Read on if you plan on using Tree::DAG_New as a base class.
167 (Otherwise feel free to skip to the description of _init.)
168 There are, in my mind, two ways to do object construction:
170 Way 1: create an object, knowing that it'll have certain
172 uninteresting sane default values, and then call methods to change
173 those values to what you want. Example:
174 $node = Tree::DAG_Node->new;
176 $node->name('Supahnode!');
177 $root->add_daughter($node);
178 $node->add_daughters(@some_others)
179 Way 2: be able to specify some/most/all the object's attributes in
181 the call to the constructor. Something like:
182 $node = Tree::DAG_Node->new({
184 name => 'Supahnode!',
185 mother => $root,
186 daughters => \@some_others
187 });
188 After some deliberation, I've decided that the second way is a Bad
190 Thing. First off, it is not markedly more concise than the first
191 way. Second off, it often requires subtly different syntax (e.g.,
192 \@some_others vs @some_others). It just complicates things for the
193 programmer and the user, without making either appreciably happier.
194 See however the comments under "new($hashref)" for options
196 supported in the call to new().
197 (This is not to say that options in general for a constructor are
199 bad -- "random_network($options)", discussed far below, necessarily
200 takes options. But note that those are not options for the default
201 values of attributes.)
202 Anyway, if you use "Tree::DAG_Node" as a superclass, and you add
204 attributes that need to be initialized, what you need to do is
205 provide an _init method that calls $this->SUPER::_init($options) to
206 use its superclass's _init method, and then initializes the new
207 attributes:
208 sub _init {
210 my($this, $options) = @_[0,1];
211 $this->SUPER::_init($options); # call my superclass's _init to
212 # init all the attributes I'm inheriting
213 # Now init /my/ new attributes:
215 $this->{'amigos'} = []; # for example
216 }
217 ...or, as I prefer when I'm being a neat freak:
219 sub _init {
221 my($this, $options) = @_[0,1];
222 $this->SUPER::_init($options);
223 $this->_init_amigos($options);
225 }
226 sub _init_amigos {
228 my $this = $_[0];
229 # Or my($this,$options) = @_[0,1]; if I'm using $options
230 $this->{'amigos'} = [];
231 }
232 In other words, I like to have each attribute initialized thru a
234 method named _init_[attribute], which should expect the object as
235 $_[0] and the options hashref (or {} if none was given) as $_[1].
236 If you insist on having your _init recognize options for setting
237 attributes, you might as well have them dealt with by the
238 appropriate _init_[attribute] method, like this:
239 sub _init {
241 my($this, $options) = @_[0,1];
242 $this->SUPER::_init($options);
243 $this->_init_amigos($options);
245 }
246 sub _init_amigos {
248 my($this,$options) = @_[0,1]; # I need options this time
249 $this->{'amigos'} = [];
250 $this->amigos(@{$options->{'amigos'}}) if $options->{'amigos'};
251 }
252 All this bookkeeping looks silly with just one new attribute in a
254 class derived straight from "Tree::DAG_Node", but if there's lots
255 of new attributes running around, and if you're deriving from a
256 class derived from a class derived from "Tree::DAG_Node", then tidy
257 stratification/modularization like this can keep you sane.
258 the constructor $obj->new() or $obj->new($options)
260 Just another way to get at the "new($hashref)" method. This does
261 not copy $obj, but merely constructs a new object of the same class
262 as it. Saves you the bother of going $class = ref $obj; $obj2 =
263 $class->new;
264 the method $node->_init($options)
266 Initialize the object's attribute values. See the discussion
267 above. Presumably this should be called only by the guts of the
268 "new($hashref)" constructor -- never by the end user.
269 Currently there are no documented options for putting in the
271 $options hashref, but (in case you want to disregard the above
272 rant) the option exists for you to use $options for something
273 useful in a derived class.
274 Please see the source for more information.
276 see also (below) the constructors "new_daughter" and
278 "new_daughter_left"
279
281 add_daughter(LIST)
282 An exact synonym for "add_daughters(LIST)".
283 add_daughters(LIST)
285 This method adds the node objects in LIST to the (right) end of
286 $mother's daughter list. Making a node N1 the daughter of another node
287 N2 also means that N1's mother attribute is "automatically" set to N2;
288 it also means that N1 stops being anything else's daughter as it
289 becomes N2's daughter.
290 If you try to make a node its own mother, a fatal error results. If
292 you try to take one of a node N1's ancestors and make it also a
293 daughter of N1, a fatal error results. A fatal error results if
294 anything in LIST isn't a node object.
295 If you try to make N1 a daughter of N2, but it's already a daughter of
297 N2, then this is a no-operation -- it won't move such nodes to the end
298 of the list or anything; it just skips doing anything with them.
299 add_daughter_left(LIST)
301 An exact synonym for "add_daughters_left(LIST)".
302 add_daughters_left(LIST)
304 This method is just like "add_daughters(LIST)", except that it adds the
305 node objects in LIST to the (left) beginning of $mother's daughter
306 list, instead of the (right) end of it.
307 add_left_sister(LIST)
309 An exact synonym for "add_left_sisters(LIST)".
310 add_left_sisters(LIST)
312 This adds the elements in LIST (in that order) as immediate left
313 sisters of $node. In other words, given that B's mother's daughter-
314 list is (A,B,C,D), calling B->add_left_sisters(X,Y) makes B's mother's
315 daughter-list (A,X,Y,B,C,D).
316 If LIST is empty, this is a no-op, and returns empty-list.
318 This is basically implemented as a call to $node->replace_with(LIST,
320 $node), and so all replace_with's limitations and caveats apply.
321 The return value of $node->add_left_sisters(LIST) is the elements of
323 LIST that got added, as returned by replace_with -- minus the copies of
324 $node you'd get from a straight call to $node->replace_with(LIST,
325 $node).
326 add_right_sister(LIST)
328 An exact synonym for "add_right_sisters(LIST)".
329 add_right_sisters(LIST)
331 Just like add_left_sisters (which see), except that the elements in
332 LIST (in that order) as immediate right sisters of $node;
333 In other words, given that B's mother's daughter-list is (A,B,C,D),
335 calling B->add_right_sisters(X,Y) makes B's mother's daughter-list
336 (A,B,X,Y,C,D).
337 address()
339 address(ADDRESS)
340 With the first syntax, returns the address of $node within its tree,
341 based on its position within the tree. An address is formed by noting
342 the path between the root and $node, and concatenating the daughter-
343 indices of the nodes this passes thru (starting with 0 for the root,
344 and ending with $node).
345 For example, if to get from node ROOT to node $node, you pass thru
347 ROOT, A, B, and $node, then the address is determined as:
348 o ROOT's my_daughter_index is 0
350 o A's my_daughter_index is, suppose, 2
351 A is index 2 in ROOT's daughter list.
352 o B's my_daughter_index is, suppose, 0
354 B is index 0 in A's daughter list.
355 o $node's my_daughter_index is, suppose, 4
357 $node is index 4 in B's daughter list.
358 The address of the above-described $node is, therefore, "0:2:0:4".
360 (As a somewhat special case, the address of the root is always "0"; and
362 since addresses start from the root, all addresses start with a "0".)
363 The second syntax, where you provide an address, starts from the root
365 of the tree $anynode belongs to, and returns the node corresponding to
366 that address. Returns undef if no node corresponds to that address.
367 Note that this routine may be somewhat liberal in its interpretation of
368 what can constitute an address; i.e., it accepts "0.2.0.4", besides
369 "0:2:0:4".
370 Also note that the address of a node in a tree is meaningful only in
372 that tree as currently structured.
373 (Consider how ($address1 cmp $address2) may be magically meaningful to
375 you, if you meant to figure out what nodes are to the right of what
376 other nodes.)
377 ancestors()
379 Returns the list of this node's ancestors, starting with its mother,
380 then grandmother, and ending at the root. It does this by simply
381 following the 'mother' attributes up as far as it can. So if $item IS
382 the root, this returns an empty list.
383 Consider that scalar($node->ancestors) returns the ply of this node
385 within the tree -- 2 for a granddaughter of the root, etc., and 0 for
386 root itself.
387 attribute()
389 attribute(SCALAR)
390 Exact synonyms for "attributes()" and "attributes(SCALAR)".
391 attributes()
393 attributes(SCALAR)
394 In the first form, returns the value of the node object's "attributes"
395 attribute. In the second form, sets it to the value of SCALAR. I
396 intend this to be used to store a reference to a (presumably anonymous)
397 hash the user can use to store whatever attributes he doesn't want to
398 have to store as object attributes. In this case, you needn't ever set
399 the value of this. (_init has already initialized it to {}.) Instead
400 you can just do...
401 $node->attributes->{'foo'} = 'bar';
403 ...to write foo => bar.
405 clear_daughters()
407 This unlinks all $mother's daughters. Returns the list of what used to
408 be $mother's daughters.
409 Not to be confused with "remove_daughters(LIST)".
411 common(LIST)
413 Returns the lowest node in the tree that is ancestor-or-self to the
414 nodes $node and LIST.
415 If the nodes are far enough apart in the tree, the answer is just the
417 root.
418 If the nodes aren't all in the same tree, the answer is undef.
420 As a degenerate case, if LIST is empty, returns $node.
422 common_ancestor(LIST)
424 Returns the lowest node that is ancestor to all the nodes given (in
425 nodes $node and LIST). In other words, it answers the question: "What
426 node in the tree, as low as possible, is ancestor to the nodes given
427 ($node and LIST)?"
428 If the nodes are far enough apart, the answer is just the root --
430 except if any of the nodes are the root itself, in which case the
431 answer is undef (since the root has no ancestor).
432 If the nodes aren't all in the same tree, the answer is undef.
434 As a degenerate case, if LIST is empty, returns $node's mother; that'll
436 be undef if $node is root.
437 copy_at_and_under()
439 copy_at_and_under($options)
440 This returns a copy of the subtree consisting of $node and everything
441 under it.
442 If you pass no options, copy_at_and_under pretends you've passed {}.
444 This works by recursively building up the new tree from the leaves,
446 duplicating nodes using $orig_node->copy($options_ref) and then linking
447 them up into a new tree of the same shape.
448 Options you specify are passed down to calls to $node->copy.
450 copy_tree()
452 copy_tree($options)
453 This returns the root of a copy of the tree that $node is a member of.
454 If you pass no options, copy_tree pretends you've passed {}.
455 This method is currently implemented as just a call to
457 $this->root->copy_at_and_under($options), but magic may be added in the
458 future.
459 Options you specify are passed down to calls to $node->copy.
461 daughters()
463 This returns the (possibly empty) list of daughters for $node.
464 delete_tree()
466 Destroys the entire tree that $node is a member of (starting at the
467 root), by nulling out each node-object's attributes (including, most
468 importantly, its linkage attributes -- hopefully this is more than
469 sufficient to eliminate all circularity in the data structure), and
470 then moving it into the class DEADNODE.
471 Use this when you're finished with the tree in question, and want to
473 free up its memory. (If you don't do this, it'll get freed up anyway
474 when your program ends.)
475 If you try calling any methods on any of the node objects in the tree
477 you've destroyed, you'll get an error like:
478 Can't locate object method "leaves_under"
480 via package "DEADNODE".
481 So if you see that, that's what you've done wrong. (Actually, the
483 class DEADNODE does provide one method: a no-op method "delete_tree".
484 So if you want to delete a tree, but think you may have deleted it
485 already, it's safe to call $node->delete_tree on it (again).)
486 The "delete_tree()" method is needed because Perl's garbage collector
488 would never (as currently implemented) see that it was time to de-
489 allocate the memory the tree uses -- until either you call
490 $node->delete_tree, or until the program stops (at "global destruction"
491 time, when everything is unallocated).
492 Incidentally, there are better ways to do garbage-collecting on a tree,
494 ways which don't require the user to explicitly call a method like
495 "delete_tree()" -- they involve dummy classes, as explained at
496 <http://mox.perl.com/misc/circle-destroy.pod>
497 However, introducing a dummy class concept into "Tree::DAG_Node" would
499 be rather a distraction. If you want to do this with your derived
500 classes, via a DESTROY in a dummy class (or in a tree-metainformation
501 class, maybe), then feel free to.
502 The only case where I can imagine "delete_tree()" failing to totally
504 void the tree, is if you use the hashref in the "attributes" attribute
505 to store (presumably among other things) references to other nodes'
506 "attributes" hashrefs -- which 1) is maybe a bit odd, and 2) is your
507 problem, because it's your hash structure that's circular, not the
508 tree's. Anyway, consider:
509 # null out all my "attributes" hashes
511 $anywhere->root->walk_down({
512 'callback' => sub {
513 $hr = $_[0]->attributes; %$hr = (); return 1;
514 }
515 });
516 # And then:
517 $anywhere->delete_tree;
518 (I suppose "delete_tree()" is a "destructor", or as close as you can
520 meaningfully come for a circularity-rich data structure in Perl.)
521 See also "WHEN AND HOW TO DESTROY THE TREE".
523 depth_under()
525 Returns an integer representing the number of branches between this
526 $node and the most distant leaf under it. (In other words, this
527 returns the ply of subtree starting of $node. Consider
528 scalar($it->ancestors) if you want the ply of a node within the whole
529 tree.)
530 descendants()
532 Returns a list consisting of all the descendants of $node. Returns
533 empty-list if $node is a terminal_node.
534 (Note that it's spelled "descendants", not "descendents".)
536 draw_ascii_tree([$options])
538 Here, the [] refer to an optional parameter.
539 Returns an arrayref of lines suitable for printing.
541 Draws a nice ASCII-art representation of the tree structure.
543 The tree looks like:
545 |
547 <Root>
548 /-------+-----+---+---\
549 | | | | |
550 <I> <H> <D> <E> <B>
551 /---\ /---\ | | |
552 | | | | <F> <F> <C>
553 <J> <J> <J> <J> | |
554 | | | | <G> <G>
555 <K> <L> <K> <L>
556 | |
557 <M> <M>
558 | |
559 <N> <N>
560 | |
561 <O> <O>
562 See scripts/cut.and.paste.subtrees.pl.
564 Example usage:
566 print map("$_\n", @{$tree->draw_ascii_tree});
568 draw_ascii_tree() takes parameters you set in the $options hashref:
570 o h_compact
572 Takes 0 or 1. Sets the extent to which draw_ascii_tree() tries to
573 save horizontal space.
574 If I think of a better scrunching algorithm, there'll be a "2"
576 setting for this.
577 Default: 1.
579 o h_spacing
581 Takes a number 0 or greater. Sets the number of spaces inserted
582 horizontally between nodes (and groups of nodes) in a tree.
583 Default: 1.
585 o no_name
587 If true, draw_ascii_tree() doesn't print the name of the node; it
588 simply prints a "*".
589 Default: 0 (i.e., print the node name.)
591 o v_compact
593 Takes a number 0, 1, or 2. Sets the degree to which
594 draw_ascii_tree() tries to save vertical space. Defaults to 1.
595 The code occasionally returns trees that are a bit cock-eyed in parts;
597 if anyone can suggest a better drawing algorithm, I'd be appreciative.
598 See also "tree2string([$options], [$some_tree])".
600 dump_names($options)
602 Returns an array.
603 Dumps, as an indented list, the names of the nodes starting at $node,
605 and continuing under it. Options are:
606 o _depth -- A nonnegative number
608 Indicating the depth to consider $node as being at (and so the
609 generation under that is that plus one, etc.). You may choose to
610 use set _depth => scalar($node->ancestors).
611 Default: 0.
613 o tick -- a string to preface each entry with
615 This string goes between the indenting-spacing and the node's name.
616 You may prefer "*" or "-> " or something.
617 Default: ''.
619 o indent -- the string used to indent with
621 Another sane value might be '. ' (period, space). Setting it to
622 empty-string suppresses indenting.
623 Default: ' ' x 2.
625 The output is not printed, but is returned as a list, where each item
627 is a line, with a "\n" at the end.
628 Note: Names are converted to a printable form using the undocumented
630 function _dump_quote().
631 format_node([$options], [$node])
633 Here, [] represent optional parameters.
634 Returns a string consisting of the node's name and, optionally, it's
636 attributes.
637 Possible keys in the $options hashref:
639 o no_attributes
641 If given a true value, the node's attributes are not included in
642 the string returned.
643 Default: 0 (include attributes).
645 Calls "hashref2string($hashref)".
647 Called by "node2string([$options], [$node])".
649 You would not normally call this method.
651 If you don't wish to supply options, use format_node({}, $node).
653 generation()
655 Returns a list of all nodes (going left-to-right) that are in $node's
656 generation -- i.e., that are the some number of nodes down from the
657 root. $root->generation() is just $root.
658 Of course, $node is always in its own generation.
660 generation_under($node)
662 Like "generation()", but returns only the nodes in $node's generation
663 that are also descendants of $node -- in other words,
664 @us = $node->generation_under( $node->mother->mother );
666 is all $node's first cousins (to borrow yet more kinship terminology)
668 -- assuming $node does indeed have a grandmother. Actually "cousins"
669 isn't quite an apt word, because @us ends up including $node's siblings
670 and $node.
671 Actually, "generation_under($node)" is just an alias to "generation()",
673 but I figure that this:
674 @us = $node->generation_under($way_upline);
676 is a bit more readable than this:
678 @us = $node->generation($way_upline);
680 But it's up to you.
682 $node->generation_under($node) returns just $node.
684 If you call $node->generation_under($node) but NODE2 is not $node or an
686 ancestor of $node, it behaves as if you called just
687 $node->generation().
688 head2 hashref2string($hashref)
690 Returns the given hashref as a string.
692 Called by "format_node([$options], [$node])".
694 is_daughter_of($node2)
696 Returns true iff $node is a daughter of $node2. Currently implemented
697 as just a test of ($it->mother eq $node2).
698 is_node()
700 This always returns true. More pertinently, $object->can('is_node') is
701 true (regardless of what "is_node()" would do if called) for objects
702 belonging to this class or for any class derived from it.
703 is_root()
705 Returns 1 if the caller is the root, and 0 if it is not.
706 leaves_under()
708 Returns a list (going left-to-right) of all the leaf nodes under $node.
709 ("Leaf nodes" are also called "terminal nodes" -- i.e., nodes that have
710 no daughters.) Returns $node in the degenerate case of $node being a
711 leaf itself.
712 left_sister()
714 Returns the node that's the immediate left sister of $node. If $node
715 is the leftmost (or only) daughter of its mother (or has no mother),
716 then this returns undef.
717 See also "add_left_sisters(LIST)" and "add_right_sisters(LIST)".
719 left_sisters()
721 Returns a list of nodes that're sisters to the left of $node. If $node
722 is the leftmost (or only) daughter of its mother (or has no mother),
723 then this returns an empty list.
724 See also "add_left_sisters(LIST)" and "add_right_sisters(LIST)".
726 lol_to_tree($lol)
728 This must be called as a class method.
729 Converts something like bracket-notation for "Chomsky trees" (or
731 rather, the closest you can come with Perl
732 list-of-lists(-of-lists(-of-lists))) into a tree structure. Returns
733 the root of the tree converted.
734 The conversion rules are that: 1) if the last (possibly the only) item
736 in a given list is a scalar, then that is used as the "name" attribute
737 for the node based on this list. 2) All other items in the list
738 represent daughter nodes of the current node -- recursively so, if they
739 are list references; otherwise, (non-terminal) scalars are considered
740 to denote nodes with that name. So ['Foo', 'Bar', 'N'] is an alternate
741 way to represent [['Foo'], ['Bar'], 'N'].
742 An example will illustrate:
744 use Tree::DAG_Node;
746 $lol =
747 [
748 [
749 [ [ 'Det:The' ],
750 [ [ 'dog' ], 'N'], 'NP'],
751 [ '/with rabies\\', 'PP'],
752 'NP'
753 ],
754 [ 'died', 'VP'],
755 'S'
756 ];
757 $tree = Tree::DAG_Node->lol_to_tree($lol);
758 $diagram = $tree->draw_ascii_tree;
759 print map "$_\n", @$diagram;
760 ...returns this tree:
762 |
764 <S>
765 |
766 /------------------\
767 | |
768 <NP> <VP>
769 | |
770 /---------------\ <died>
771 | |
772 <NP> <PP>
773 | |
774 /-------\ </with rabies\>
775 | |
776 <Det:The> <N>
777 |
778 <dog>
779 By the way (and this rather follows from the above rules), when
781 denoting a LoL tree consisting of just one node, this:
782 $tree = Tree::DAG_Node->lol_to_tree( 'Lonely' );
784 is okay, although it'd probably occur to you to denote it only as:
786 $tree = Tree::DAG_Node->lol_to_tree( ['Lonely'] );
788 which is of course fine, too.
790 mother()
792 This returns what node is $node's mother. This is undef if $node has
793 no mother -- i.e., if it is a root.
794 See also "is_root()" and "root()".
796 my_daughter_index()
798 Returns what index this daughter is, in its mother's "daughter" list.
799 In other words, if $node is ($node->mother->daughters)[3], then
800 $node->my_daughter_index returns 3.
801 As a special case, returns 0 if $node has no mother.
803 name()
805 name(SCALAR)
806 In the first form, returns the value of the node object's "name"
807 attribute. In the second form, sets it to the value of SCALAR.
808 new($hashref)
810 These options are supported in $hashref:
811 o attributes => A hashref of attributes
813 o daughters => An arrayref of nodes
814 o mother => A node
815 o name => A string
816 See also "MAIN CONSTRUCTOR, AND INITIALIZER" for a long discussion on
818 object creation.
819 new_daughter()
821 new_daughter($options)
822 This constructs a new node (of the same class as $mother), and adds it
823 to the (right) end of the daughter list of $mother. This is essentially
824 the same as going
825 $daughter = $mother->new;
827 $mother->add_daughter($daughter);
828 but is rather more efficient because (since $daughter is guaranteed new
830 and isn't linked to/from anything), it doesn't have to check that
831 $daughter isn't an ancestor of $mother, isn't already daughter to a
832 mother it needs to be unlinked from, isn't already in $mother's
833 daughter list, etc.
834 As you'd expect for a constructor, it returns the node-object created.
836 # Note that if you radically change 'mother'/'daughters' bookkeeping, #
838 you may have to change this routine, since it's one of the places #
839 that directly writes to 'daughters' and 'mother'.
840 new_daughter_left()
842 new_daughter_left($options)
843 This is just like $mother->new_daughter, but adds the new daughter to
844 the left (start) of $mother's daughter list.
845 # Note that if you radically change 'mother'/'daughters' bookkeeping, #
847 you may have to change this routine, since it's one of the places #
848 that directly writes to 'daughters' and 'mother'.
849 node2string($options, $t, $vert_dashes)
851 Returns a string of the node's name and attributes, with a leading
852 indent, suitable for printing.
853 Possible keys in the $options hashref:
855 o no_attributes
857 If given a true value, the node's attributes are not included in
858 the string returned.
859 Default: 0 (include attributes).
861 Calls "format_node([$options], [$node])".
863 Called by "tree2string([$options], [$some_tree])".
865 random_network($options)
867 This method can be called as a class method or as an object method.
868 In the first case, constructs a randomly arranged network under a new
870 node, and returns the root node of that tree. In the latter case,
871 constructs the network under $node.
872 Currently, this is implemented a bit half-heartedly, and half-wittedly.
874 I basically needed to make up random-looking networks to stress-test
875 the various tree-dumper methods, and so wrote this. If you actually
876 want to rely on this for any application more serious than that, I
877 suggest examining the source code and seeing if this does really what
878 you need (say, in reliability of randomness); and feel totally free to
879 suggest changes to me (especially in the form of "I rewrote
880 "random_network($options)", here's the code...")
881 It takes four options:
883 o max_node_count -- maximum number of nodes this tree will be allowed
885 to have (counting the root)
886 Default: 25.
887 o min_depth -- minimum depth for the tree
889 Leaves can be generated only after this depth is reached, so the
890 tree will be at least this deep -- unless max_node_count is hit
891 first.
892 Default: 2.
894 o max_depth -- maximum depth for the tree
896 The tree will not be deeper than this.
897 Default: 3 plus min_depth.
899 o max_children -- maximum number of children any mother in the tree can
901 have.
902 Default: 4.
903 remove_daughter(LIST)
905 An exact synonym for "remove_daughters(LIST)".
906 remove_daughters(LIST)
908 This removes the nodes listed in LIST from $mother's daughter list.
909 This is a no-operation if LIST is empty. If there are things in LIST
910 that aren't a current daughter of $mother, they are ignored.
911 Not to be confused with "clear_daughters()".
913 replace_with(LIST)
915 This replaces $node in its mother's daughter list, by unlinking $node
916 and replacing it with the items in LIST. This returns a list
917 consisting of $node followed by LIST, i.e., the nodes that replaced it.
918 LIST can include $node itself (presumably at most once). LIST can also
920 be empty-list. However, if any items in LIST are sisters to $node,
921 they are ignored, and are not in the copy of LIST passed as the return
922 value.
923 As you might expect for any linking operation, the items in LIST cannot
925 be $node's mother, or any ancestor to it; and items in LIST are, of
926 course, unlinked from their mothers (if they have any) as they're
927 linked to $node's mother.
928 (In the special (and bizarre) case where $node is root, this simply
930 calls $this->unlink_from_mother on all the items in LIST, making them
931 roots of their own trees.)
932 Note that the daughter-list of $node is not necessarily affected; nor
934 are the daughter-lists of the items in LIST. I mention this in case
935 you think replace_with switches one node for another, with respect to
936 its mother list and its daughter list, leaving the rest of the tree
937 unchanged. If that's what you want, replacing $Old with $New, then you
938 want:
939 $New->set_daughters($Old->clear_daughters);
941 $Old->replace_with($New);
942 (I can't say $node's and LIST-items' daughter lists are never affected
944 my replace_with -- they can be affected in this case:
945 $N1 = ($node->daughters)[0]; # first daughter of $node
947 $N2 = ($N1->daughters)[0]; # first daughter of $N1;
948 $N3 = Tree::DAG_Node->random_network; # or whatever
949 $node->replace_with($N1, $N2, $N3);
950 As a side affect of attaching $N1 and $N2 to $node's mother, they're
952 unlinked from their parents ($node, and $N1, respectively). But N3's
953 daughter list is unaffected.
954 In other words, this method does what it has to, as you'd expect it to.
956 replace_with_daughters()
958 This replaces $node in its mother's daughter list, by unlinking $node
959 and replacing it with its daughters. In other words, $node becomes
960 motherless and daughterless as its daughters move up and take its
961 place. This returns a list consisting of $node followed by the nodes
962 that were its daughters.
963 In the special (and bizarre) case where $node is root, this simply
965 unlinks its daughters from it, making them roots of their own trees.
966 Effectively the same as $node->replace_with($node->daughters), but more
968 efficient, since less checking has to be done. (And I also think
969 $node->replace_with_daughters is a more common operation in tree-
970 wrangling than $node->replace_with(LIST), so deserves a named method of
971 its own, but that's just me.)
972 # Note that if you radically change 'mother'/'daughters' bookkeeping, #
974 you may have to change this routine, since it's one of the places #
975 that directly writes to 'daughters' and 'mother'.
976 right_sister()
978 Returns the node that's the immediate right sister of $node. If $node
979 is the rightmost (or only) daughter of its mother (or has no mother),
980 then this returns undef.
981 See also "add_left_sisters(LIST)" and "add_right_sisters(LIST)".
983 right_sisters()
985 Returns a list of nodes that're sisters to the right of $node. If $node
986 is the rightmost (or only) daughter of its mother (or has no mother),
987 then this returns an empty list.
988 See also "add_left_sisters(LIST)" and "add_right_sisters(LIST)".
990 root()
992 Returns the root of whatever tree $node is a member of. If $node is
993 the root, then the result is $node itself.
994 Not to be confused with "is_root()".
996 self_and_descendants()
998 Returns a list consisting of itself (as element 0) and all the
999 descendants of $node. Returns just itself if $node is a terminal_node.
1000 (Note that it's spelled "descendants", not "descendents".)
1002 self_and_sisters()
1004 Returns a list of all nodes (going left-to-right) that have the same
1005 mother as $node -- including $node itself. This is just like
1006 $node->mother->daughters, except that that fails where $node is root,
1007 whereas $root->self_and_siblings, as a special case, returns $root.
1008 (Contrary to how you may interpret how this method is named, "self" is
1010 not (necessarily) the first element of what's returned.)
1011 set_daughters(LIST)
1013 This unlinks all $mother's daughters, and replaces them with the
1014 daughters in LIST.
1015 Currently implemented as just $mother->clear_daughters followed by
1017 $mother->add_daughters(LIST).
1018 simple_lol_to_tree($simple_lol)
1020 This must be called as a class method.
1021 This is like lol_to_tree, except that rule 1 doesn't apply -- i.e., all
1023 scalars (or really, anything not a listref) in the LoL-structure end up
1024 as named terminal nodes, and only terminal nodes get names (and, of
1025 course, that name comes from that scalar value). This method is useful
1026 for making things like expression trees, or at least starting them off.
1027 Consider that this:
1028 $tree = Tree::DAG_Node->simple_lol_to_tree(
1030 [ 'foo', ['bar', ['baz'], 'quux'], 'zaz', 'pati' ]
1031 );
1032 converts from something like a Lispish or Iconish tree, if you pretend
1034 the brackets are parentheses.
1035 Note that there is a (possibly surprising) degenerate case of what I'm
1037 calling a "simple-LoL", and it's like this:
1038 $tree = Tree::DAG_Node->simple_lol_to_tree('Lonely');
1040 This is the (only) way you can specify a tree consisting of only a
1042 single node, which here gets the name 'Lonely'.
1043 sisters()
1045 Returns a list of all nodes (going left-to-right) that have the same
1046 mother as $node -- not including $node itself. If $node is root, this
1047 returns empty-list.
1048 tree_to_lol()
1050 Returns that tree (starting at $node) represented as a LoL, like what
1051 $lol, above, holds. (This is as opposed to
1052 "tree_to_lol_notation($options)", which returns the viewable code like
1053 what gets evaluated and stored in $lol, above.)
1054 Lord only knows what you use this for -- maybe for feeding to
1056 Data::Dumper, in case "tree_to_lol_notation($options)" doesn't do just
1057 what you want?
1058 tree_to_lol_notation($options)
1060 Dumps a tree (starting at $node) as the sort of LoL-like bracket
1061 notation you see in the above example code. Returns just one big block
1062 of text. The only option is "multiline" -- if true, it dumps the text
1063 as the sort of indented structure as seen above; if false (and it
1064 defaults to false), dumps it all on one line (with no indenting, of
1065 course).
1066 For example, starting with the tree from the above example, this:
1068 print $tree->tree_to_lol_notation, "\n";
1070 prints the following (which I've broken over two lines for sake of
1072 printability of documentation):
1073 [[[['Det:The'], [['dog'], 'N'], 'NP'], [["/with rabies\x5c"],
1075 'PP'], 'NP'], [['died'], 'VP'], 'S'],
1076 Doing this:
1078 print $tree->tree_to_lol_notation({ multiline => 1 });
1080 prints the same content, just spread over many lines, and prettily
1082 indented.
1083 Note: Names are converted to a printable form using the undocumented
1085 function _dump_quote().
1086 tree_to_simple_lol()
1088 Returns that tree (starting at $node) represented as a simple-LoL --
1089 i.e., one where non-terminal nodes are represented as listrefs, and
1090 terminal nodes are gotten from the contents of those nodes' "name'
1091 attributes.
1092 Note that in the case of $node being terminal, what you get back is the
1094 same as $node->name.
1095 Compare to tree_to_simple_lol_notation.
1097 tree_to_simple_lol_notation($options)
1099 A simple-LoL version of tree_to_lol_notation (which see); takes the
1100 same options.
1101 Note: Names are converted to a printable form using the undocumented
1103 function _dump_quote().
1104 tree2string([$options], [$some_tree])
1106 Here, the [] represent optional parameters.
1107 Returns an arrayref of lines, suitable for printing.
1109 Draws a nice ASCII-art representation of the tree structure.
1111 The tree looks like:
1113 Root. Attributes: {# => "0"}
1115 |---I. Attributes: {# => "1"}
1116 | |---J. Attributes: {# => "3"}
1117 | | |---K. Attributes: {# => "3"}
1118 | |---J. Attributes: {# => "4"}
1119 | |---L. Attributes: {# => "5"}
1120 | |---M. Attributes: {# => "5"}
1121 | |---N. Attributes: {# => "5"}
1122 | |---O. Attributes: {# => "5"}
1123 |---H. Attributes: {# => "2"}
1124 | |---J. Attributes: {# => "3"}
1125 | | |---K. Attributes: {# => "3"}
1126 | |---J. Attributes: {# => "4"}
1127 | |---L. Attributes: {# => "5"}
1128 | |---M. Attributes: {# => "5"}
1129 | |---N. Attributes: {# => "5"}
1130 | |---O. Attributes: {# => "5"}
1131 |---D. Attributes: {# => "6"}
1132 | |---F. Attributes: {# => "8"}
1133 | |---G. Attributes: {# => "8"}
1134 |---E. Attributes: {# => "7"}
1135 | |---F. Attributes: {# => "8"}
1136 | |---G. Attributes: {# => "8"}
1137 |---B. Attributes: {# => "9"}
1138 |---C. Attributes: {# => "9"}
1139 Or, without attributes:
1141 Root
1143 |---I
1144 | |---J
1145 | | |---K
1146 | |---J
1147 | |---L
1148 | |---M
1149 | |---N
1150 | |---O
1151 |---H
1152 | |---J
1153 | | |---K
1154 | |---J
1155 | |---L
1156 | |---M
1157 | |---N
1158 | |---O
1159 |---D
1160 | |---F
1161 | |---G
1162 |---E
1163 | |---F
1164 | |---G
1165 |---B
1166 |---C
1167 See scripts/cut.and.paste.subtrees.pl.
1169 Example usage:
1171 print map("$_\n", @{$tree->tree2string});
1173 Can be called with $some_tree set to any $node, and will print the tree
1175 assuming $node is the root.
1176 If you don't wish to supply options, use tree2string({}, $node).
1178 Possible keys in the $options hashref (which defaults to {}):
1180 o no_attributes
1182 If given a true value, the node's attributes are not included in
1183 the string returned.
1184 Default: 0 (include attributes).
1186 Calls "node2string($options, $t, $vert_dashes)".
1188 See also "draw_ascii_tree([$options])".
1190 unlink_from_mother()
1192 This removes node from the daughter list of its mother. If it has no
1193 mother, this is a no-operation.
1194 Returns the mother unlinked from (if any).
1196 walk_down($options)
1198 Performs a depth-first traversal of the structure at and under $node.
1199 What it does at each node depends on the value of the options hashref,
1200 which you must provide. There are three options, "callback" and
1201 "callbackback" (at least one of which must be defined, as a sub
1202 reference), and "_depth".
1203 This is what walk_down() does, in pseudocode form:
1205 o Starting point
1207 Start at the $node given.
1208 o Callback
1210 If there's a callback, call it with $node as the first argument,
1211 and the options hashref as the second argument (which contains the
1212 potentially useful _depth, remember). This function must return
1213 true or false -- if false, it will block the next step:
1214 o Daughters
1216 If $node has any daughter nodes, increment _depth, and call
1217 $daughter->walk_down($options) for each daughter (in order, of
1218 course), where options_hashref is the same hashref it was called
1219 with. When this returns, decrements _depth.
1220 Callbackback
1222 If there's a callbackback, call just it as with callback (but
1223 tossing out the return value). Note that callback returning false
1224 blocks traversal below $node, but doesn't block calling
1225 callbackback for $node. (Incidentally, in the unlikely case that
1226 $node has stopped being a node object, callbackback won't get
1227 called.)
1228 o Return
1230 $node->walk_down($options) is the way to recursively do things to a
1232 tree (if you start at the root) or part of a tree; if what you're doing
1233 is best done via pre-pre order traversal, use callback; if what you're
1234 doing is best done with post-order traversal, use callbackback.
1235 walk_down() is even the basis for plenty of the methods in this class.
1236 See the source code for examples both simple and horrific.
1237 Note that if you don't specify _depth, it effectively defaults to 0.
1239 You should set it to scalar($node->ancestors) if you want _depth to
1240 reflect the true depth-in-the-tree for the nodes called, instead of
1241 just the depth below $node. (If $node is the root, there's difference,
1242 of course.)
1243 And by the way, it's a bad idea to modify the tree from the callback.
1245 Unpredictable things may happen. I instead suggest having your
1246 callback add to a stack of things that need changing, and then, once
1247 walk_down() is all finished, changing those nodes from that stack.
1248 Note that the existence of walk_down() doesn't mean you can't write you
1250 own special-use traversers.
1251
1253 It should be clear to you that if you've built a big parse tree or
1254 something, and then you're finished with it, you should call
1255 $some_node->delete_tree on it if you want the memory back.
1256 But consider this case: you've got this tree:
1258 A
1260 / | \
1261 B C D
1262 | | \
1263 E X Y
1264 Let's say you decide you don't want D or any of its descendants in the
1266 tree, so you call D->unlink_from_mother. This does NOT automagically
1267 destroy the tree D-X-Y. Instead it merely splits the tree into two:
1268 A D
1270 / \ / \
1271 B C X Y
1272 |
1273 E
1274 To destroy D and its little tree, you have to explicitly call
1276 delete_tree on it.
1277 Note, however, that if you call C->unlink_from_mother, and if you don't
1279 have a link to C anywhere, then it does magically go away. This is
1280 because nothing links to C -- whereas with the D-X-Y tree, D links to X
1281 and Y, and X and Y each link back to D. Note that calling
1282 C->delete_tree is harmless -- after all, a tree of only one node is
1283 still a tree.
1284 So, this is a surefire way of getting rid of all $node's children and
1286 freeing up the memory associated with them and their descendants:
1287 foreach my $it ($node->clear_daughters) { $it->delete_tree }
1289 Just be sure not to do this:
1291 foreach my $it ($node->daughters) { $it->delete_tree }
1293 $node->clear_daughters;
1294 That's bad; the first call to $_->delete_tree will climb to the root of
1296 $node's tree, and nuke the whole tree, not just the bits under $node.
1297 You might as well have just called $node->delete_tree. (Moreavor, once
1298 $node is dead, you can't call clear_daughters on it, so you'll get an
1299 error there.)
1300
1302 If you find a bug in this library, report it to me as soon as possible,
1303 at the address listed in the MAINTAINER section, below. Please try to
1304 be as specific as possible about how you got the bug to occur.
1305
1307 If you develop a given routine for dealing with trees in some way, and
1308 use it a lot, then if you think it'd be of use to anyone else, do email
1309 me about it; it might be helpful to others to include that routine, or
1310 something based on it, in a later version of this module.
1311 It's occurred to me that you might like to (and might yourself develop
1313 routines to) draw trees in something other than ASCII art. If you do
1314 so -- say, for PostScript output, or for output interpretable by some
1315 external plotting program -- I'd be most interested in the results.
1316
1318 This module uses "strict", but I never wrote it with -w warnings in
1319 mind -- so if you use -w, do not be surprised if you see complaints
1320 from the guts of DAG_Node. As long as there is no way to turn off -w
1321 for a given module (instead of having to do it in every single
1322 subroutine with a "local $^W"), I'm not going to change this. However,
1323 I do, at points, get bursts of ambition, and I try to fix code in
1324 DAG_Node that generates warnings, as I come across them -- which is
1325 only occasionally. Feel free to email me any patches for any such
1326 fixes you come up with, tho.
1327 Currently I don't assume (or enforce) anything about the class
1329 membership of nodes being manipulated, other than by testing whether
1330 each one provides a method "is_node()", a la:
1331 die "Not a node!!!" unless UNIVERSAL::can($node, "is_node");
1333 So, as far as I'm concerned, a given tree's nodes are free to belong to
1335 different classes, just so long as they provide/inherit "is_node()",
1336 the few methods that this class relies on to navigate the tree, and
1337 have the same internal object structure, or a superset of it.
1338 Presumably this would be the case for any object belonging to a class
1339 derived from "Tree::DAG_Node", or belonging to "Tree::DAG_Node" itself.
1340 When routines in this class access a node's "mother" attribute, or its
1342 "daughters" attribute, they (generally) do so directly (via
1343 $node->{'mother'}, etc.), for sake of efficiency. But classes derived
1344 from this class should probably do this instead thru a method (via
1345 $node->mother, etc.), for sake of portability, abstraction, and general
1346 goodness.
1347 However, no routines in this class (aside from, necessarily, _init(),
1349 _init_name(), and "name()") access the "name" attribute directly;
1350 routines (like the various tree draw/dump methods) get the "name" value
1351 thru a call to $obj->name(). So if you want the object's name to not
1352 be a real attribute, but instead have it derived dynamically from some
1353 feature of the object (say, based on some of its other attributes, or
1354 based on its address), you can to override the "name()" method, without
1355 causing problems. (Be sure to consider the case of $obj->name as a
1356 write method, as it's used in /lol_to_tree($lol) and
1357 "random_network($options)".)
1358
1360 Which is the best tree processing module?
1361 "Tree::DAG_Node", as it happens. More details: "SEE ALSO".
1362 How to process every node in tree?
1364 See "walk_down($options)". $options normally looks like, assuming we
1365 wish to pass in an arrayref to a stack, for example:
1366 my(@stack);
1368 $tree -> walk_down
1370 ({
1371 callback =>
1372 sub
1373 {
1374 my(@node, $options) = @_;
1375 # Process $node, using $options...
1377 push @{$$options{stack} }, $node -> name;
1379 return 1; # Keep walking.
1381 },
1382 _depth => 0,
1383 stack => \@stack,
1384 });
1385 # Process @stack...
1387 How do I switch from Tree to Tree::DAG_Node?
1389 o The node's name
1390 In "Tree" you use $node -> value and in "Tree::DAG_Node" it's $node
1391 -> name.
1392 o The node's attributes
1394 In "Tree" you use $node -> meta and in "Tree::DAG_Node" it's $node
1395 -> attributes.
1396 Are there techniques for processing lists of nodes?
1398 o Copy the daughter list, and change it
1399 @them = $mother->daughters;
1400 @removed = splice(@them, 0, 2, @new_nodes);
1401 $mother->set_daughters(@them);
1403 o Select a sub-set of nodes
1405 $mother->set_daughters
1406 (
1407 grep($_->name =~ /wanted/, $mother->daughters)
1408 );
1409 Why did you break up the sections of methods in the POD?
1411 Because I want to list the methods in alphabetical order.
1412 Why did you move the POD to the end?
1414 Because the apostrophes in the text confused the syntax hightlighter in
1415 my editor UltraEdit.
1416
1418 o Copy node does not respect the no_attribute_copy option
1419 This is a bug.
1420
1422 o HTML::Element, HTML::Tree and HTML::TreeBuilder
1423 Sean is also the author of these modules.
1424 o Tree
1426 Lightweight.
1427 o Tree::Binary
1429 Lightweight.
1430 o Tree::DAG_Node::Persist
1432 Lightweight.
1433 o Tree::Persist
1435 Lightweight.
1436 o Forest
1438 Uses Moose.
1439 "Tree::DAG_Node" itself is also lightweight.
1441
1443 Wirth, Niklaus. 1976. Algorithms + Data Structures = Programs
1444 Prentice-Hall, Englewood Cliffs, NJ.
1445 Knuth, Donald Ervin. 1997. Art of Computer Programming, Volume 1,
1447 Third Edition: Fundamental Algorithms. Addison-Wesley, Reading, MA.
1448 Wirth's classic, currently and lamentably out of print, has a good
1450 section on trees. I find it clearer than Knuth's (if not quite as
1451 encyclopedic), probably because Wirth's example code is in a block-
1452 structured high-level language (basically Pascal), instead of in
1453 assembler (MIX).
1454 Until some kind publisher brings out a new printing of Wirth's book,
1456 try poking around used bookstores (or "www.abebooks.com") for a copy.
1457 I think it was also republished in the 1980s under the title Algorithms
1458 and Data Structures, and in a German edition called Algorithmen und
1459 Datenstrukturen. (That is, I'm sure books by Knuth were published
1460 under those titles, but I'm assuming that they're just later
1461 printings/editions of Algorithms + Data Structures = Programs.)
1462
1464 The file CHANGES was converted into Changelog.ini by
1465 Module::Metadata::Changes.
1466
1468 Email the author, or log a bug on RT:
1469 <https://rt.cpan.org/Public/Dist/Display.html?Name=Tree::DAG_Node>.
1471
1473 The code to print the tree, in tree2string(), was adapted from
1474 Forest::Tree::Writer::ASCIIWithBranches.
1475
1477 David Hand, "<cogent@cpan.org>" up to V 1.06.
1478 Ron Savage "<rsavage@cpan.org>" from V 1.07.
1480 In this POD, usage of 'I' refers to Sean, up until V 1.07.
1482
1484 Sean M. Burke, "<sburke@cpan.org>"
1485
1487 Copyright 1998-2001, 2004, 2007 by Sean M. Burke and David Hand.
1488 This program is free software. It is released under the Artistic
1490 License 2.0. See <http://opensource.org/licenses/Artistic-2.0>.
1491 This program is distributed in the hope that it will be useful, but
1493 without any warranty; without even the implied warranty of
1494 merchantability or fitness for a particular purpose.
1495perl v5.16.3 2013-07-03 Tree::DAG_Node(3)