Commit | Line | Data |
3fea05b9 |
1 | |
2 | package Tree::Simple::Visitor::PostOrderTraversal; |
3 | |
4 | use strict; |
5 | use warnings; |
6 | |
7 | our $VERSION = '0.02'; |
8 | |
9 | use Scalar::Util qw(blessed); |
10 | |
11 | use base qw(Tree::Simple::Visitor); |
12 | |
13 | sub new { |
14 | my ($_class) = @_; |
15 | my $class = ref($_class) || $_class; |
16 | my $visitor = {}; |
17 | bless($visitor, $class); |
18 | $visitor->_init(); |
19 | return $visitor; |
20 | } |
21 | |
22 | sub visit { |
23 | my ($self, $tree) = @_; |
24 | (blessed($tree) && $tree->isa("Tree::Simple")) |
25 | || die "Insufficient Arguments : You must supply a valid Tree::Simple object"; |
26 | # get our filter function |
27 | my $filter_function = $self->getNodeFilter(); |
28 | # use an inner subroutine to accomplish |
29 | # this traversal using recursion |
30 | my $_postOrderTraversal = sub { |
31 | my ($current_tree, $traversal_function) = @_; |
32 | # get a temporary results container |
33 | my @results; |
34 | # process each child |
35 | foreach my $child ($current_tree->getAllChildren()) { |
36 | # recurse our inner subroutine by passing itself |
37 | # to itself, and then collect the results of this |
38 | # recursion |
39 | push @results => $traversal_function->($child, $traversal_function); |
40 | } |
41 | # if we are root and we are not including the trunk then |
42 | # we can return our results now |
43 | return @results if $current_tree->isRoot() && !$self->includeTrunk(); |
44 | # however, if we dont meet those conditions, then we |
45 | # need to process the current tree and add it to our |
46 | # results |
47 | push @results => (($filter_function) ? |
48 | $filter_function->($current_tree) |
49 | : |
50 | $current_tree->getNodeValue()); |
51 | # and then return the results |
52 | return @results; |
53 | }; |
54 | # now store the results in our object |
55 | $self->setResults($_postOrderTraversal->($tree, $_postOrderTraversal)); |
56 | } |
57 | |
58 | 1; |
59 | |
60 | __END__ |
61 | |
62 | =head1 NAME |
63 | |
64 | Tree::Simple::Visitor::PostOrderTraversal - A Visitor for post-order traversal a Tree::Simple hierarchy |
65 | |
66 | =head1 SYNOPSIS |
67 | |
68 | use Tree::Simple::Visitor::PostOrderTraversal; |
69 | |
70 | # create an visitor |
71 | my $visitor = Tree::Simple::Visitor::PostOrderTraversal->new(); |
72 | |
73 | # pass our visitor to the tree |
74 | $tree->accept($visitor); |
75 | |
76 | # print our results |
77 | print join ", " => $visitor->getResults(); |
78 | |
79 | # this will print this: |
80 | # 1.1.1 1.1 1.2 1 2.1 2 3.1 3 |
81 | # assuming your tree is like this: |
82 | # 1 |
83 | # 1.1 |
84 | # 1.1.1 |
85 | # 1.2 |
86 | # 2 |
87 | # 2.1 |
88 | # 3 |
89 | # 3.1 |
90 | |
91 | =head1 DESCRIPTION |
92 | |
93 | Post-order traversal is a variation of the depth-first traversal in which the sub-tree's are processed I<before> the parent. It is another alternative to Tree::Simple's C<traverse> method which implements a depth-first, pre-order traversal. |
94 | |
95 | =head1 METHODS |
96 | |
97 | =over 4 |
98 | |
99 | =item B<new> |
100 | |
101 | There are no arguments to the constructor the object will be in its default state. You can use the C<setNodeFilter> method to customize its behavior. |
102 | |
103 | =item B<includeTrunk ($boolean)> |
104 | |
105 | Based upon the value of C<$boolean>, this will tell the visitor to include the trunk of the tree in the traversal as well. |
106 | |
107 | =item B<setNodeFilter ($filter_function)> |
108 | |
109 | This method accepts a CODE reference as its C<$filter_function> argument and throws an exception if it is not a code reference. This code reference is used to filter the tree nodes as they are collected. This can be used to customize output, or to gather specific information from a more complex tree node. The filter function should accept a single argument, which is the current Tree::Simple object. |
110 | |
111 | =item B<visit ($tree)> |
112 | |
113 | This is the method that is used by Tree::Simple's C<accept> method. It can also be used on its own, it requires the C<$tree> argument to be a Tree::Simple object (or derived from a Tree::Simple object), and will throw and exception otherwise. |
114 | |
115 | =item B<getResults> |
116 | |
117 | This method returns the accumulated results of the application of the node filter to the tree. |
118 | |
119 | =back |
120 | |
121 | =head1 BUGS |
122 | |
123 | None that I am aware of. Of course, if you find a bug, let me know, and I will be sure to fix it. |
124 | |
125 | =head1 CODE COVERAGE |
126 | |
127 | See the B<CODE COVERAGE> section in L<Tree::Simple::VisitorFactory> for more inforamtion. |
128 | |
129 | =head1 SEE ALSO |
130 | |
131 | These Visitor classes are all subclasses of B<Tree::Simple::Visitor>, which can be found in the B<Tree::Simple> module, you should refer to that module for more information. |
132 | |
133 | =head1 AUTHOR |
134 | |
135 | stevan little, E<lt>stevan@iinteractive.comE<gt> |
136 | |
137 | =head1 COPYRIGHT AND LICENSE |
138 | |
139 | Copyright 2004, 2005 by Infinity Interactive, Inc. |
140 | |
141 | L<http://www.iinteractive.com> |
142 | |
143 | This library is free software; you can redistribute it and/or modify |
144 | it under the same terms as Perl itself. |
145 | |
146 | =cut |
147 | |