1 2package Tree::Simple::Visitor::BreadthFirstTraversal; 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 _init { 23 my ($self) = @_; 24 $self->SUPER::_init(); 25} 26 27sub visit { 28 my ($self, $tree) = @_; 29 (blessed($tree) && $tree->isa("Tree::Simple")) 30 || die "Insufficient Arguments : You must supply a valid Tree::Simple object"; 31 # create a holder for our results 32 my @results; 33 # get our filter function 34 my $filter_function = $self->getNodeFilter(); 35 # now create a queue for 36 # processing depth first 37 my @queue; 38 # if we are to include the trunk 39 if ($self->includeTrunk()) { 40 # then enqueue that 41 @queue = ($tree); 42 } 43 # if we are not including the trunk 44 else { 45 # then we enqueue all the 46 # trunks children instead 47 @queue = ($tree->getAllChildren()); 48 } 49 # until our queue is empty 50 while (scalar(@queue) != 0){ 51 # get the first item off the queue 52 my $current_tree = shift @queue; 53 # enqueue all the current tree's children 54 push @queue => $current_tree->getAllChildren(); 55 # now collect the results 56 push @results => (($filter_function) ? 57 $filter_function->($current_tree) 58 : 59 $current_tree->getNodeValue()); 60 } 61 # store our results 62 $self->setResults(@results); 63} 64 651; 66 67__END__ 68 69=head1 NAME 70 71Tree::Simple::Visitor::BreadthFirstTraversal - A Visitor for breadth-first traversal a Tree::Simple hierarchy 72 73=head1 SYNOPSIS 74 75 use Tree::Simple::Visitor::BreadthFirstTraversal; 76 77 # create an visitor 78 my $visitor = Tree::Simple::Visitor::BreadthFirstTraversal->new(); 79 80 # pass our visitor to the tree 81 $tree->accept($visitor); 82 83 # print our results 84 print join ", " => $visitor->getResults(); 85 86 # this will print this: 87 # 1, 2, 3, 1.1, 1.2, 2.1, 3.1, 1.1.1 88 # assuming your tree is like this: 89 # 1 90 # 1.1 91 # 1.1.1 92 # 1.2 93 # 2 94 # 2.1 95 # 3 96 # 3.1 97 98=head1 DESCRIPTION 99 100This implements a breadth-first traversal of a Tree::Simple hierarchy. This can be an alternative to the built in depth-first traversal of the Tree::Simple C<traverse> method. 101 102=head1 METHODS 103 104=over 4 105 106=item B<new> 107 108There 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. 109 110=item B<includeTrunk ($boolean)> 111 112Based upon the value of C<$boolean>, this will tell the visitor to include the trunk of the tree in the traversal as well. 113 114=item B<setNodeFilter ($filter_function)> 115 116This 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. 117 118=item B<visit ($tree)> 119 120This 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. 121 122=item B<getResults> 123 124This method returns the accumulated results of the application of the node filter to the tree. 125 126=back 127 128=head1 BUGS 129 130None that I am aware of. Of course, if you find a bug, let me know, and I will be sure to fix it. 131 132=head1 CODE COVERAGE 133 134See the B<CODE COVERAGE> section in L<Tree::Simple::VisitorFactory> for more inforamtion. 135 136=head1 SEE ALSO 137 138These 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. 139 140=head1 AUTHOR 141 142stevan little, E<lt>stevan@iinteractive.comE<gt> 143 144=head1 COPYRIGHT AND LICENSE 145 146Copyright 2004, 2005 by Infinity Interactive, Inc. 147 148L<http://www.iinteractive.com> 149 150This library is free software; you can redistribute it and/or modify 151it under the same terms as Perl itself. 152 153=cut 154 155