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