1
2package Tree::Simple::Visitor::PostOrderTraversal;
3
4use strict;
5use warnings;
6
7our $VERSION = '0.02';
8
9use Scalar::Util qw(blessed);
10
11use base qw(Tree::Simple::Visitor);
12
13sub 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
22sub 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
581;
59
60__END__
61
62=head1 NAME
63
64Tree::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
93Post-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
101There 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
105Based 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
109This 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
113This 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
117This method returns the accumulated results of the application of the node filter to the tree.
118
119=back
120
121=head1 BUGS
122
123None 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
127See the B<CODE COVERAGE> section in L<Tree::Simple::VisitorFactory> for more inforamtion.
128
129=head1 SEE ALSO
130
131These 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
135stevan little, E<lt>stevan@iinteractive.comE<gt>
136
137=head1 COPYRIGHT AND LICENSE
138
139Copyright 2004, 2005 by Infinity Interactive, Inc.
140
141L<http://www.iinteractive.com>
142
143This library is free software; you can redistribute it and/or modify
144it under the same terms as Perl itself.
145
146=cut
147
148