Commit | Line | Data |
3fea05b9 |
1 | |
2 | package Tree::Simple::Visitor::BreadthFirstTraversal; |
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 _init { |
23 | my ($self) = @_; |
24 | $self->SUPER::_init(); |
25 | } |
26 | |
27 | sub 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 | |
65 | 1; |
66 | |
67 | __END__ |
68 | |
69 | =head1 NAME |
70 | |
71 | Tree::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 | |
100 | This 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 | |
108 | 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. |
109 | |
110 | =item B<includeTrunk ($boolean)> |
111 | |
112 | Based 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 | |
116 | 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. |
117 | |
118 | =item B<visit ($tree)> |
119 | |
120 | 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. |
121 | |
122 | =item B<getResults> |
123 | |
124 | This method returns the accumulated results of the application of the node filter to the tree. |
125 | |
126 | =back |
127 | |
128 | =head1 BUGS |
129 | |
130 | None 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 | |
134 | See the B<CODE COVERAGE> section in L<Tree::Simple::VisitorFactory> for more inforamtion. |
135 | |
136 | =head1 SEE ALSO |
137 | |
138 | 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. |
139 | |
140 | =head1 AUTHOR |
141 | |
142 | stevan little, E<lt>stevan@iinteractive.comE<gt> |
143 | |
144 | =head1 COPYRIGHT AND LICENSE |
145 | |
146 | Copyright 2004, 2005 by Infinity Interactive, Inc. |
147 | |
148 | L<http://www.iinteractive.com> |
149 | |
150 | This library is free software; you can redistribute it and/or modify |
151 | it under the same terms as Perl itself. |
152 | |
153 | =cut |
154 | |