local-lib5/lib/perl5/Tree/Simple/Visitor/PostOrderTraversal.pm

   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