blib/lib/Tree/Nary.pm

filter: Statementstmt 64.5% 342 / 530 Branchbran 50.0% 158 / 316 Conditioncond 36.6% 33 / 90 MC/DCmcdc 8.7% 5 / 57 Subroutinesub 77.3% 41 / 53 Podpod 100% 36 / 36 totaltotal 56.8% 615 / 1082 CC 192 SCAR 34.0
CC
192
Cov
57%
_depth_traverse_in_order
156.0
_depth_traverse_children
132.0
_depth_traverse_pre_order
90.0
CRAP 29.9
↑ Summary
1 #####################################################################################
2 # $Id: Nary.pm,v 1.3 2004/01/05 10:32:00 soriano Exp $
3 #####################################################################################
4 #
5 # Tree::Nary
6 #
7 # Author: Frederic Soriano <frederic.soriano@alcatel.fr>
8 # RCS Revision: $Revision: 1.3 $
9 # Date: $Date: 2004/01/05 10:32:00 $
10 #
11 #####################################################################################
12 #
13 # This package is free software and is provided "as is" without express or
14 # implied warranty. It may be used, redistributed and/or modified under the
15 # same terms as Perl itself.
16 #
17 #####################################################################################
18  
19 package Tree::Nary;
20  
21 2 require 5.003;
22 2 require Exporter;
23  
24 2 @ISA = qw(Exporter);
25  
26 2 $VERSION = '1.3';
27  
28 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
29 2 ▶use vars qw($TRUE $FALSE);
Subroutine BEGIN: called CC=1 SCAR=0.0
30 2 ▶use vars qw($TRAVERSE_LEAFS $TRAVERSE_NON_LEAFS $TRAVERSE_ALL $TRAVERSE_MASK);
Subroutine BEGIN: called CC=1 SCAR=0.0
31 2 ▶use vars qw($IN_ORDER $PRE_ORDER $POST_ORDER $LEVEL_ORDER);
Subroutine BEGIN: called CC=1 SCAR=0.0
32  
33 #
34 # Constants
35 #
36  
37 # Booleans
38 2 *TRUE = \1;
39 2 *FALSE = \0;
40  
41 # Tree traverse flags
42 2 *TRAVERSE_LEAFS = \(1 << 0); # Only leaf nodes should be visited.
43 2 *TRAVERSE_NON_LEAFS = \(1 << 1); # Only non-leaf nodes should be visited.
44 2 *TRAVERSE_ALL = \($TRAVERSE_LEAFS | $TRAVERSE_NON_LEAFS); # All nodes should be visited.
45 2 *TRAVERSE_MASK = \0x03;
46  
47 # Tree traverse orders
48 2 *IN_ORDER = \1;
49 2 *PRE_ORDER = \2;
50 2 *POST_ORDER = \3;
51 2 *LEVEL_ORDER = \4;
52  
53 #
54 # Public methods
55 #
56  
57 # Constructors, destructors
58  
59 # Creates a new Tree::Nary node object, containing the given data, if any.
60 # Used to create the first node in a tree.
61 4768 ▶sub new() {
Subroutine new: called CC=3 SCAR=11.1
Pod documented
62  
63 4768 my ($that, $newdata) = (shift, shift);
64 4768 ▶ my $class = ref($that) || $that;
Condition33%1/3
ref $that || $that
l!l&&r!l&&!r
047680
MC/DC0%0/2
ref $that || $that
ref $that $that
Truth table33%1/3
A || B
A= ref $thatB= $that
ABresult
1X1
011
000
65 4768 my $self = {
66 data => undef,
67 next => undef,
68 prev => undef,
69 parent => undef,
70 children => undef,
71 };
72  
73 4768 ▶ if(defined($newdata)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $newdata) 17 4751 4768
74 17 $self->{data} = $newdata;
75 }
76  
77 # Transform $self into an object of class $class
78 4768 bless $self, $class;
79  
80 4768 return($self);
81 }
82  
83 # Frees allocated memory by removing circular references.
84 0 ▶sub _free() {
Subroutine _free: not called CC=4 SCAR=30.0
85  
86 0 my ($self, $node) = (shift, shift);
87 0 my $parent = $self->new();
88  
89 0 $parent = $node;
90  
91 0 ▶ while($TRUE) {
Branch: 1 branch
BranchTrueFalseTotal
if ($Tree::Nary::TRUE) 0 0 0
92 0 ▶ if(defined($parent->{children})) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $parent->{"children"}) 0 0 0
93 0 $self->_free($parent->{children});
94 }
95 0 ▶ if(defined($parent->{next})) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $parent->{'next'}) { } 0 0 0
96 0 $parent = $parent->{next};
97 } else {
98 0 last;
99 }
100 }
101  
102 0 return;
103 }
104  
105 # Removes the node and its children from the tree.
106 2702 ▶sub DESTROY() {
Subroutine DESTROY: called CC=3 SCAR=16.7
107  
108 2702 my ($self, $root) = (shift, shift);
109  
110 2702 ▶ if(!defined($root)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $root) 2702 0 2702
111 2702 return;
112 }
113 0 ▶ if(!$self->is_root($root)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($self->is_root($root)) 0 0 0
114 0 $self->unlink($root);
115 }
116  
117 0 $self->_free($root);
118  
119 0 return;
120 }
121  
122 # Unlinks a node from a tree, resulting in two separate trees.
123 10 ▶sub unlink() {
Subroutine unlink: called CC=5 SCAR=16.3
Pod documented
124  
125 10 my ($self, $node) = (shift, shift);
126  
127 10 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 10 10
128 0 return;
129 }
130  
131 10 ▶ if(defined($node->{prev})) {
Branch: 2 branches
BranchTrueFalseTotal
if (defined $node->{'prev'}) { } 7 3 10
elsif (defined $node->{'parent'}) { } 3 0 3
132 7 $node->{prev}->{next} = $node->{next};
133 } elsif(defined($node->{parent})) {
134 3 $node->{parent}->{children} = $node->{next};
135 }
136  
137 10 $node->{parent} = undef;
138  
139 10 ▶ if(defined($node->{next})) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node->{"next"}) 5 5 10
140 5 $node->{next}->{prev} = $node->{prev};
141 5 $node->{next} = undef;
142 }
143  
144 10 $node->{prev} = undef;
145  
146 10 return;
147 }
148  
149 #
150 # Miscellaneous info methods
151 #
152  
153 # Returns TRUE if the given node is a root node.
154 2077 ▶sub is_root() {
Subroutine is_root: called CC=3 SCAR=14.2
Pod documented
155  
156 2077 my ($self, $node) = (shift, shift);
157  
158 2077 ▶ return(!defined($node->{parent}) && !defined($node->{prev}) && !defined($node->{next}));
Condition33%2/6
defined $node->{'parent'} || defined $node->{'prev'} || defined $node->{'next'}
l!l&&r!l&&!r
002077
defined $node->{"parent"} or defined $node->{"prev"}
l!l&&r!l&&!r
002077
MC/DC0%0/3
defined $node->{'parent'} || defined $node->{'prev'} || defined $node->{'next'}
defined $node->{"parent"} defined $node->{"prev"} defined $node->{'next'}
Truth table25%1/4
A or B || C
A= defined $node->{"parent"}B= defined $node->{"prev"}C= defined $node->{'next'}
ABCresult
1XX1
01X1
0011
0000
159 }
160  
161 # Returns TRUE if the given node is a leaf node.
162 78 ▶sub is_leaf() {
Subroutine is_leaf: called CC=1 SCAR=0.0
Pod documented
163  
164 78 my ($self, $node) = (shift, shift);
165  
166 78 return(!defined($node->{children}));
167 }
168  
169 # Returns TRUE if $node is an ancestor of $descendant.
170 # This is true if node is the parent of descendant, or if node is the grandparent of descendant, etc.
171 2 ▶sub is_ancestor() {
Subroutine is_ancestor: called CC=6 SCAR=18.3
Pod documented
172  
173 2 my ($self, $node, $descendant) = (shift, shift, shift);
174  
175 2 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 2 2
176 0 return($FALSE);
177 }
178 2 ▶ if(!defined($descendant)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $descendant) 0 2 2
179 0 return($FALSE);
180 }
181  
182 2 ▶ while(defined($descendant)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $descendant) 3 1 4
183 3 ▶ if(defined($descendant->{parent}) && ($descendant->{parent} == $node)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $descendant->{"parent"} and $descendant->{"parent"} == $node) 1 2 3
Condition100%3/3
defined $descendant->{"parent"} and $descendant->{"parent"} == $node
!ll&&!rl&&r
111
MC/DC100%2/2
defined $descendant->{"parent"} and $descendant->{"parent"} == $node
defined $descendant->{"parent"} $descendant->{"parent"} == $node
Truth table100%3/3
A and B
A= defined $descendant->{"parent"}B= $descendant->{"parent"} == $node
ABresult
0X0
100
111
184 1 return($TRUE);
185 }
186  
187 2 $descendant = $descendant->{parent};
188 }
189  
190 1 return($FALSE);
191 }
192  
193 # Gets the root of a tree.
194 0 ▶sub get_root() {
Subroutine get_root: not called CC=3 SCAR=24.8
Pod documented
195  
196 0 my ($self, $node) = (shift, shift);
197  
198 0 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 0 0
199 0 return(undef);
200 }
201  
202 0 ▶ while(defined($node->{parent})) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node->{"parent"}) 0 0 0
203 0 $node = $node->{parent};
204 }
205  
206 0 return($node);
207 }
208  
209 # Gets the depth of a node.
210 3 ▶sub depth() {
Subroutine depth: called CC=2 SCAR=6.9
Pod documented
211  
212 3 my ($self, $node) = (shift, shift);
213 3 my $depth = 0;
214  
215 3 ▶ while(defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node) 6 3 9
216 6 $depth++;
217 6 $node = $node->{parent};
218 }
219  
220 3 return($depth);
221 }
222  
223 # Reverses the order of the children of a node.
224 2 ▶sub reverse_children() {
Subroutine reverse_children: called CC=3 SCAR=11.0
Pod documented
225  
226 2 my ($self, $node) = (shift, shift);
227 2 my $child = $self->new();
228 2 my $last = $self->new();
229  
230 2 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 2 2
231 0 return;
232 }
233  
234 2 $child = $node->{children};
235  
236 2 ▶ while(defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child) 7 2 9
237 7 $last = $child;
238 7 $child = $last->{next};
239 7 $last->{next} = $last->{prev};
240 7 $last->{prev} = $child;
241 }
242  
243 2 $node->{children} = $last;
244  
245 2 return;
246 }
247  
248 # Gets the maximum height of all branches beneath a node.
249 # This is the maximum distance from the node to all leaf nodes.
250 2067 ▶sub max_height() {
Subroutine max_height: called CC=4 SCAR=13.9
Pod documented
251  
252 2067 my ($self, $root) = (shift, shift);
253 2067 my $child = $self->new();
254 2067 my $max_height = 0;
255  
256 # <Deep recursion on subroutine "Tree::Nary::max_height">
257 # can be safely ignored.
258 2067 local $^W = 0;
259  
260 2067 ▶ if(!defined($root)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $root) 0 2067 2067
261 0 return(0);
262 }
263  
264 2067 $child = $root->{children};
265  
266 2067 ▶ while(defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child) 2063 2067 4130
267  
268 2063 my $tmp_height = $self->max_height($child);
269  
270 2063 ▶ if($tmp_height > $max_height) {
Branch: 1 branch
BranchTrueFalseTotal
if ($tmp_height > $max_height) 826 1237 2063
271 826 $max_height = $tmp_height;
272 }
273  
274 2063 $child = $child->{next};
275 }
276  
277 2067 return($max_height + 1);
278 }
279  
280 # Gets the number of children of a node.
281 22 ▶sub n_children() {
Subroutine n_children: called CC=3 SCAR=11.1
Pod documented
282  
283 22 my ($self, $node) = (shift, shift);
284 22 my $n = 0;
285  
286 22 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 22 22
287 0 return(0);
288 }
289  
290 22 $node = $node->{children};
291  
292 22 ▶ while(defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node) 46 22 68
293 46 $n++;
294 46 $node = $node->{next};
295 }
296  
297 22 return($n);
298 }
299  
300 # Gets the position of a node with respect to its siblings.
301 # $child must be a child of $node.
302 # The first child is numbered 0, the second 1, and so on.
303 4 ▶sub child_position() {
Subroutine child_position: called CC=7 SCAR=22.2
Pod documented
304  
305 4 my ($self, $node, $child) = (shift, shift, shift);
306 4 my $n = 0;
307  
308 4 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 4 4
309 0 return(-1);
310 }
311 4 ▶ if(!defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $child) 0 4 4
312 0 return(-1);
313 }
314 4 ▶ if(defined($child->{parent}) && !($child->{parent} == $node)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child->{"parent"} and not $child->{"parent"} == $node) 0 4 4
Condition33%1/3
defined $child->{"parent"} and not $child->{"parent"} == $node
!ll&&!rl&&r
040
MC/DC0%0/2
defined $child->{"parent"} and not $child->{"parent"} == $node
defined $child->{"parent"} not $child->{"parent"} == $node
Truth table33%1/3
A and not(B)
A= defined $child->{"parent"}B= not $child->{"parent"} == $node
ABresult
0X0
100
111
315 0 return(-1);
316 }
317  
318 4 $node = $node->{children};
319  
320 4 ▶ while(defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node) 10 0 10
321 10 ▶ if($node == $child) {
Branch: 1 branch
BranchTrueFalseTotal
if ($node == $child) 4 6 10
322 4 return($n);
323 }
324 6 $n++;
325 6 $node = $node->{next};
326 }
327  
328 0 return(-1);
329 }
330  
331 # Gets the position of the first child of a node which contains the given data.
332 0 ▶sub child_index() {
Subroutine child_index: not called CC=4 SCAR=30.0
Pod documented
333  
334 0 my ($self, $node, $data) = (shift, shift, shift);
335 0 my $n = 0;
336  
337 0 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 0 0
338 0 return(-1);
339 }
340  
341 0 $node = $node->{children};
342  
343 0 ▶ while(defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node) 0 0 0
344 0 ▶ if($node->{data} eq $data) {
Branch: 1 branch
BranchTrueFalseTotal
if ($node->{"data"} eq $data) 0 0 0
345 0 return($n);
346 }
347 0 $n++;
348 0 $node = $node->{next};
349 }
350  
351 0 return(-1);
352 }
353  
354 # Gets the first sibling of a node. This could possibly be the node itself.
355 0 ▶sub first_sibling() {
Subroutine first_sibling: not called CC=3 SCAR=24.8
Pod documented
356  
357 0 my ($self, $node) = (shift, shift);
358  
359 0 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 0 0
360 0 return(undef);
361 }
362  
363 0 ▶ while(defined($node->{prev})) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node->{"prev"}) 0 0 0
364 0 $node = $node->{prev};
365 }
366  
367 0 return($node);
368 }
369  
370 # Gets the next sibling of a node.
371 0 ▶sub next_sibling() {
Subroutine next_sibling: not called CC=2 SCAR=17.9
Pod documented
372  
373 0 my ($self, $node) = (shift, shift);
374  
375 0 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 0 0
376 0 return(undef);
377 }
378  
379 0 return($node->{next});
380 }
381  
382 # Gets the previous sibling of a node.
383 0 ▶sub prev_sibling() {
Subroutine prev_sibling: not called CC=2 SCAR=17.9
Pod documented
384  
385 0 my ($self, $node) = (shift, shift);
386  
387 0 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 0 0
388 0 return(undef);
389 }
390  
391 0 return($node->{prev});
392 }
393  
394 # Gets the last sibling of a node. This could possibly be the node itself.
395 0 ▶sub last_sibling() {
Subroutine last_sibling: not called CC=3 SCAR=24.8
Pod documented
396  
397 0 my ($self, $node) = (shift, shift);
398  
399 0 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 0 0
400 0 return(undef);
401 }
402  
403 0 ▶ while(defined($node->{next})) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node->{"next"}) 0 0 0
404 0 $node = $node->{next};
405 }
406  
407 0 return($node);
408 }
409  
410 2082 ▶sub _count_func() {
Subroutine _count_func: called CC=5 SCAR=16.1
411  
412 2082 my ($self, $node, $flags, $nref) = (shift, shift, shift, shift);
413  
414 # <Deep recursion on subroutine "Tree::Nary::_count_func"> warnings
415 # can be safely ignored.
416 2082 local $^W = 0;
417  
418 2082 ▶ if(defined($node->{children})) {
Branch: 2 branches
BranchTrueFalseTotal
if (defined $node->{'children'}) { } 422 1660 2082
elsif ($flags & $Tree::Nary::TRAVERSE_LEAFS) { } 1653 7 1660
419  
420 422 my $child = $self->new();
421  
422 422 ▶ if($flags & $TRAVERSE_NON_LEAFS) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS) 418 4 422
423 418 $$nref++;
424 }
425  
426 422 $child = $node->{children};
427  
428 422 ▶ while(defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child) 2078 422 2500
429 2078 $self->_count_func($child, $flags, $nref);
430 2078 $child = $child->{next};
431 }
432  
433 } elsif($flags & $TRAVERSE_LEAFS) {
434 1653 $$nref++;
435 }
436  
437 2082 return;
438 }
439  
440 # Gets the number of nodes in a tree.
441 4 ▶sub n_nodes() {
Subroutine n_nodes: called CC=3 SCAR=12.0
Pod documented
442  
443 4 my ($self, $root, $flags) = (shift, shift, shift);
444 4 my $n = 0;
445  
446 4 ▶ if(!(defined($root))) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $root) 0 4 4
447 0 return(0);
448 }
449 4 ▶ if(!($flags <= $TRAVERSE_MASK)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($flags <= $Tree::Nary::TRAVERSE_MASK) 0 4 4
450 0 return(0);
451 }
452  
453 4 $self->_count_func($root, $flags, \$n);
454  
455 4 return($n);
456 }
457  
458 # Gets the first child of a node.
459 2 ▶sub first_child() {
Subroutine first_child: called CC=2 SCAR=7.6
Pod documented
460  
461 2 my ($self, $node) = (shift, shift);
462  
463 2 ▶ if(!(defined($node))) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 2 2
464 0 return(undef);
465 }
466  
467 2 return($node->{children});
468 }
469  
470 # Gets the last child of a node.
471 2 ▶sub last_child() {
Subroutine last_child: called CC=4 SCAR=14.2
Pod documented
472  
473 2 my ($self, $node) = (shift, shift);
474  
475 2 ▶ if(!(defined($node))) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 2 2
476 0 return(undef);
477 }
478  
479 2 $node = $node->{children};
480  
481 2 ▶ if(defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node) 2 0 2
482 2 ▶ while(defined($node->{next})) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node->{"next"}) 6 2 8
483 6 $node = $node->{next};
484 }
485 }
486  
487 2 return($node);
488 }
489  
490 # Gets a child of a node, using the given index.
491 # the first child is at index 0.
492 # If the index is too big, 'undef' is returned.
493 10 ▶sub nth_child() {
Subroutine nth_child: called CC=5 SCAR=16.4
Pod documented
494  
495 10 my ($self, $node, $n) = (shift, shift, shift);
496  
497 10 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 10 10
498 0 return(undef);
499 }
500  
501 10 $node = $node->{children};
502  
503 10 ▶ if(defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node) 10 0 10
504 10 ▶ while(($n-- > 0) && defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n-- > 0 and defined $node) 12 10 22
Condition100%3/3
$n-- > 0 and defined $node
!ll&&!rl&&r
9112
MC/DC100%2/2
$n-- > 0 and defined $node
$n-- > 0 defined $node
Truth table100%3/3
A and B
A= $n-- > 0B= defined $node
ABresult
0X0
100
111
505 12 $node = $node->{next};
506 }
507 }
508  
509 10 return($node);
510 }
511  
512 #
513 # Insert methods
514 #
515  
516 # Inserts a node beneath the parent at the given position.
517 4 ▶sub insert() {
Subroutine insert: called CC=6 SCAR=20.8
Pod documented
518  
519 4 my ($self, $parent, $position, $node) = (shift, shift, shift, shift);
520  
521 4 ▶ if(!defined($parent)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $parent) 0 4 4
522 0 return($node);
523 }
524 4 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 4 4
525 0 return($node);
526 }
527 4 ▶ if(!$self->is_root($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($self->is_root($node)) 0 4 4
528 0 return($node);
529 }
530  
531 4 ▶ if($position > 0) {
Branch: 2 branches
BranchTrueFalseTotal
if ($position > 0) { } 3 1 4
elsif ($position == 0) { } 1 0 1
532 3 return($self->insert_before($parent, $self->nth_child($parent, $position), $node));
533 } elsif($position == 0) {
534 1 return($self->prepend($parent, $node));
535 } else {
536 0 return($self->append($parent, $node));
537 }
538 }
539  
540 # Inserts a node beneath the parent before the given sibling.
541 2073 ▶sub insert_before() {
Subroutine insert_before: called CC=10 SCAR=23.5
Pod documented
542  
543 2073 my ($self, $parent, $sibling, $node) = (shift, shift, shift, shift);
544  
545 2073 ▶ if(!defined($parent)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $parent) 0 2073 2073
546 0 return($node);
547 }
548 2073 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 2073 2073
549 0 return($node);
550 }
551 2073 ▶ if(!$self->is_root($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($self->is_root($node)) 0 2073 2073
552 0 return($node);
553 }
554  
555 2073 ▶ if(defined($sibling)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $sibling) 13 2060 2073
556 13 ▶ if($sibling->{parent} != $parent) {
Branch: 1 branch
BranchTrueFalseTotal
if ($sibling->{"parent"} != $parent) 0 13 13
557 0 return($node);
558 }
559 }
560  
561 2073 $node->{parent} = $parent;
562  
563 2073 ▶ if(defined($sibling)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $sibling) { } 13 2060 2073
564 13 ▶ if(defined($sibling->{prev})) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $sibling->{'prev'}) { } 2 11 13
565 2 $node->{prev} = $sibling->{prev};
566 2 $node->{prev}->{next} = $node;
567 2 $node->{next} = $sibling;
568 2 $sibling->{prev} = $node;
569 } else {
570 11 $node->{parent}->{children} = $node;
571 11 $node->{next} = $sibling;
572 11 $sibling->{prev} = $node;
573 }
574 } else {
575 2060 ▶ if(defined($parent->{children})) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $parent->{'children'}) { } 1643 417 2060
576 1643 $sibling = $parent->{children};
577  
578 1643 ▶ while(defined($sibling->{next})) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $sibling->{"next"}) 2458 1643 4101
579 2458 $sibling = $sibling->{next};
580 }
581  
582 1643 $node->{prev} = $sibling;
583 1643 $sibling->{next} = $node;
584 } else {
585 417 $node->{parent}->{children} = $node;
586 }
587 }
588  
589 2073 return($node);
590 }
591  
592 # Inserts a new node at the given position.
593 1 ▶sub insert_data() {
Subroutine insert_data: called CC=1 SCAR=0.0
Pod documented
594  
595 1 my ($self, $parent, $position, $data) = (shift, shift, shift, shift);
596  
597 1 return($self->insert($parent, $position, $self->new($data)));
598 }
599  
600 # Inserts a new node before the given sibling.
601 0 ▶sub insert_data_before() {
Subroutine insert_data_before: not called CC=1 SCAR=6.9
Pod documented
602  
603 0 my ($self, $parent, $sibling, $data) = (shift, shift, shift, shift);
604  
605 0 return($self->insert_before($parent, $sibling, $self->new($data)));
606 }
607  
608 # Inserts a node as the last child of the given parent.
609 2051 ▶sub append() {
Subroutine append: called CC=1 SCAR=0.0
Pod documented
610  
611 2051 my ($self, $parent, $node) = (shift, shift, shift);
612  
613 2051 return($self->insert_before($parent, undef, $node));
614 }
615  
616 # Inserts a new node as the first child of the given parent.
617 6 ▶sub append_data() {
Subroutine append_data: called CC=1 SCAR=0.0
Pod documented
618  
619 6 my ($self, $parent, $data) = (shift, shift, shift);
620  
621 6 return($self->insert_before($parent, undef, $self->new($data)));
622 }
623  
624 # Inserts a node as the first child of the given parent.
625 13 ▶sub prepend() {
Subroutine prepend: called CC=2 SCAR=7.6
Pod documented
626  
627 13 my ($self, $parent, $node) = (shift, shift, shift);
628  
629 13 ▶ if(!defined($parent)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $parent) 0 13 13
630 0 return($node);
631 }
632  
633 13 return($self->insert_before($parent, $parent->{children}, $node));
634 }
635  
636 # Inserts a new node as the first child of the given parent.
637 1 ▶sub prepend_data() {
Subroutine prepend_data: called CC=1 SCAR=0.0
Pod documented
638  
639 1 my ($self, $parent, $data) = (shift, shift, shift);
640  
641 1 return($self->prepend($parent, $self->new($data)));
642 }
643  
644 #
645 # Search methods
646 #
647  
648 22 ▶sub _traverse_pre_order() {
Subroutine _traverse_pre_order: called CC=8 SCAR=22.8
649  
650 22 my ($self, $node, $flags, $funcref, $argref) = (shift, shift, shift, shift, shift);
651  
652 22 ▶ if(defined($node->{children})) {
Branch: 2 branches
BranchTrueFalseTotal
if (defined $node->{'children'}) { } 8 14 22
elsif ($flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)) { } 0 21 21
653  
654 8 my $child = $self->new();
655  
656 8 ▶ if(($flags & $TRAVERSE_NON_LEAFS) && &$funcref($node, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)) 0 8 8
Condition33%1/3
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
!ll&&!rl&&r
080
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS &$funcref($node, $argref)
Truth table33%1/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_NON_LEAFSB= &$funcref($node, $argref)
ABresult
0X0
100
111
657 0 return($TRUE);
658 }
659  
660 8 $child = $node->{children};
661  
662 8 ▶ while(defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child) 20 8 28
663  
664 20 my $current = $self->new();
665  
666 20 $current = $child;
667 20 $child = $current->{next};
668 20 ▶ if($self->_traverse_pre_order($current, $flags, $funcref, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->_traverse_pre_order($current, $flags, $funcref, $argref)) 0 20 20
669 0 return($TRUE);
670 }
671 }
672  
673 ▶ } elsif(($flags & $TRAVERSE_LEAFS) && &$funcref($node, $argref)) {
Condition66%2/3
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)
!ll&&!rl&&r
770
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)
$flags & $Tree::Nary::TRAVERSE_LEAFS &$funcref($node, $argref)
Truth table66%2/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_LEAFSB= &$funcref($node, $argref)
ABresult
0X0
100
111
674 0 return($TRUE);
675 }
676  
677 22 return($FALSE);
678 }
679  
680 0 ▶sub _depth_traverse_pre_order() {
Subroutine _depth_traverse_pre_order: not called CC=9 SCAR=45.0
681  
682 0 my ($self, $node, $flags, $depth, $funcref, $argref) = (shift, shift, shift, shift, shift, shift);
683  
684 0 ▶ if(defined($node->{children})) {
Branch: 2 branches
BranchTrueFalseTotal
if (defined $node->{'children'}) { } 0 0 0
elsif ($flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)) { } 0 0 0
685  
686 0 my $child = $self->new();
687  
688 0 ▶ if(($flags & $TRAVERSE_NON_LEAFS) && &$funcref($node, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)) 0 0 0
Condition0%0/3
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
!ll&&!rl&&r
000
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS &$funcref($node, $argref)
Truth table0%0/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_NON_LEAFSB= &$funcref($node, $argref)
ABresult
0X0
100
111
689 0 return($TRUE);
690 }
691  
692 0 $depth--;
693 0 ▶ if(!$depth) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($depth) 0 0 0
694 0 return($FALSE);
695 }
696  
697 0 $child = $node->{children};
698  
699 0 ▶ while(defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child) 0 0 0
700  
701 0 my $current = $self->new();
702  
703 0 $current = $child;
704 0 $child = $current->{next};
705  
706 0 ▶ if($self->_traverse_pre_order($current, $flags, $depth, $funcref, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->_traverse_pre_order($current, $flags, $depth, $funcref, $argref)) 0 0 0
707 0 return($TRUE);
708 }
709 }
710  
711 ▶ } elsif(($flags & $TRAVERSE_LEAFS) && &$funcref($node, $argref)) {
Condition0%0/3
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)
!ll&&!rl&&r
000
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)
$flags & $Tree::Nary::TRAVERSE_LEAFS &$funcref($node, $argref)
Truth table0%0/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_LEAFSB= &$funcref($node, $argref)
ABresult
0X0
100
111
712 0 return($TRUE);
713 }
714  
715 0 return($FALSE);
716 }
717  
718 11 ▶sub _traverse_post_order() {
Subroutine _traverse_post_order: called CC=8 SCAR=23.4
719  
720 11 my ($self, $node, $flags, $funcref, $argref) = (shift, shift, shift, shift, shift);
721  
722 11 ▶ if(defined($node->{children})) {
Branch: 2 branches
BranchTrueFalseTotal
if (defined $node->{'children'}) { } 4 7 11
elsif ($flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)) { } 0 7 7
723  
724 4 my $child = $self->new();
725  
726 4 $child = $node->{children};
727  
728 4 ▶ while(defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child) 10 4 14
729  
730 10 my $current = $self->new();
731  
732 10 $current = $child;
733 10 $child = $current->{next};
734  
735 10 ▶ if($self->_traverse_post_order($current, $flags, $funcref, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->_traverse_post_order($current, $flags, $funcref, $argref)) 0 10 10
736 0 return($TRUE);
737 }
738 }
739  
740 4 ▶ if(($flags & $TRAVERSE_NON_LEAFS) && &$funcref($node, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)) 0 4 4
Condition33%1/3
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
!ll&&!rl&&r
040
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS &$funcref($node, $argref)
Truth table33%1/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_NON_LEAFSB= &$funcref($node, $argref)
ABresult
0X0
100
111
741 0 return($TRUE);
742 }
743  
744 ▶ } elsif(($flags & $TRAVERSE_LEAFS) && &$funcref($node, $argref)) {
Condition33%1/3
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)
!ll&&!rl&&r
070
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)
$flags & $Tree::Nary::TRAVERSE_LEAFS &$funcref($node, $argref)
Truth table33%1/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_LEAFSB= &$funcref($node, $argref)
ABresult
0X0
100
111
745 0 return($TRUE);
746 }
747  
748 11 return($FALSE);
749 }
750  
751 0 ▶sub _depth_traverse_post_order() {
Subroutine _depth_traverse_post_order: not called CC=9 SCAR=45.0
752  
753 0 my ($self, $node, $flags, $depth, $funcref, $argref) = (shift, shift, shift, shift, shift, shift);
754  
755 0 ▶ if(defined($node->{children})) {
Branch: 2 branches
BranchTrueFalseTotal
if (defined $node->{'children'}) { } 0 0 0
elsif ($flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)) { } 0 0 0
756  
757 0 $depth--;
758 0 ▶ if($depth) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth) 0 0 0
759  
760 0 my $child = $self->new();
761  
762 0 $child = $node->{children};
763  
764 0 ▶ while(defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child) 0 0 0
765  
766 0 my $current = $self->new();
767  
768 0 $current = $child;
769 0 $child = $current->{next};
770  
771 0 ▶ if($self->_depth_traverse_post_order($current, $flags, $depth, $funcref, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->_depth_traverse_post_order($current, $flags, $depth, $funcref, $argref)) 0 0 0
772 0 return($TRUE);
773 }
774 }
775 }
776 0 ▶ if(($flags & $TRAVERSE_NON_LEAFS) && &$funcref($node, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)) 0 0 0
Condition0%0/3
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
!ll&&!rl&&r
000
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS &$funcref($node, $argref)
Truth table0%0/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_NON_LEAFSB= &$funcref($node, $argref)
ABresult
0X0
100
111
777 0 return($TRUE);
778 }
779  
780 ▶ } elsif(($flags & $TRAVERSE_LEAFS) && &$funcref($node, $argref)) {
Condition0%0/3
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)
!ll&&!rl&&r
000
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)
$flags & $Tree::Nary::TRAVERSE_LEAFS &$funcref($node, $argref)
Truth table0%0/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_LEAFSB= &$funcref($node, $argref)
ABresult
0X0
100
111
781 0 return($TRUE);
782 }
783  
784 0 return($FALSE);
785 }
786  
787 21 ▶sub _traverse_in_order() {
Subroutine _traverse_in_order: called CC=9 SCAR=22.1
788  
789 21 my ($self, $node, $flags, $funcref, $argref) = (shift, shift, shift, shift, shift);
790  
791 21 ▶ if(defined($node->{children})) {
Branch: 2 branches
BranchTrueFalseTotal
if (defined $node->{'children'}) { } 8 13 21
elsif ($flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)) { } 1 12 13
792  
793 8 my $child = $self->new();
794 8 my $current = $self->new();
795  
796 8 $child = $node->{children};
797 8 $current = $child;
798 8 $child = $current->{next};
799  
800 8 ▶ if($self->_traverse_in_order($current, $flags, $funcref, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->_traverse_in_order($current, $flags, $funcref, $argref)) 1 7 8
801 1 return($TRUE);
802 }
803 7 ▶ if(($flags & $TRAVERSE_NON_LEAFS) && &$funcref($node, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)) 0 7 7
Condition66%2/3
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
!ll&&!rl&&r
340
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS &$funcref($node, $argref)
Truth table66%2/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_NON_LEAFSB= &$funcref($node, $argref)
ABresult
0X0
100
111
804 0 return($TRUE);
805 }
806  
807 7 ▶ while(defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child) 11 5 16
808 11 $current = $child;
809 11 $child = $current->{next};
810 11 ▶ if($self->_traverse_in_order($current, $flags, $funcref, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->_traverse_in_order($current, $flags, $funcref, $argref)) 2 9 11
811 2 return($TRUE);
812 }
813 }
814  
815 ▶ } elsif(($flags & $TRAVERSE_LEAFS) && &$funcref($node, $argref)) {
Condition66%2/3
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)
!ll&&!rl&&r
0121
MC/DC50%1/2
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)
$flags & $Tree::Nary::TRAVERSE_LEAFS &$funcref($node, $argref)
Truth table66%2/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_LEAFSB= &$funcref($node, $argref)
ABresult
0X0
100
111
816 1 return($TRUE);
817 }
818  
819 17 return($FALSE);
820 }
821  
822 0 ▶sub _depth_traverse_in_order() {
Subroutine _depth_traverse_in_order: not called CC=12 SCAR=50.5
823  
824 0 my ($self, $node, $flags, $depth, $funcref, $argref) = (shift, shift, shift, shift, shift, shift);
825  
826 0 ▶ if(defined($node->{children})) {
Branch: 2 branches
BranchTrueFalseTotal
if (defined $node->{'children'}) { } 0 0 0
elsif ($flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)) { } 0 0 0
827  
828 0 $depth--;
829 0 ▶ if($depth) {
Branch: 2 branches
BranchTrueFalseTotal
if ($depth) { } 0 0 0
elsif ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)) { } 0 0 0
830  
831 0 my $child = $self->new();
832 0 my $current = $self->new();
833  
834 0 $child = $node->{children};
835 0 $current = $child;
836 0 $child = $current->{next};
837  
838 0 ▶ if($self->_depth_traverse_in_order($current, $flags, $depth, $funcref, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->_depth_traverse_in_order($current, $flags, $depth, $funcref, $argref)) 0 0 0
839 0 return($TRUE);
840 }
841 0 ▶ if(($flags & $TRAVERSE_NON_LEAFS) && &$funcref($node, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)) 0 0 0
Condition0%0/3
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
!ll&&!rl&&r
000
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS &$funcref($node, $argref)
Truth table0%0/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_NON_LEAFSB= &$funcref($node, $argref)
ABresult
0X0
100
111
842 0 return($TRUE);
843 }
844  
845 0 ▶ while(defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child) 0 0 0
846 0 $current = $child;
847 0 $child = $current->{next};
848 0 ▶ if($self->_depth_traverse_in_order($current, $flags, $depth, $funcref, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->_depth_traverse_in_order($current, $flags, $depth, $funcref, $argref)) 0 0 0
849 0 return($TRUE);
850 }
851 }
852  
853 ▶ } elsif(($flags & $TRAVERSE_NON_LEAFS) && &$funcref($node, $argref)) {
Condition0%0/3
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
!ll&&!rl&&r
000
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($node, $argref)
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS &$funcref($node, $argref)
Truth table0%0/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_NON_LEAFSB= &$funcref($node, $argref)
ABresult
0X0
100
111
854 0 return($TRUE);
855 }
856  
857 ▶ } elsif(($flags & $TRAVERSE_LEAFS) && &$funcref($node, $argref)) {
Condition0%0/3
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)
!ll&&!rl&&r
000
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($node, $argref)
$flags & $Tree::Nary::TRAVERSE_LEAFS &$funcref($node, $argref)
Truth table0%0/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_LEAFSB= &$funcref($node, $argref)
ABresult
0X0
100
111
858 0 return($TRUE);
859 }
860  
861 0 return($FALSE);
862 }
863  
864 20 ▶sub _traverse_children() {
Subroutine _traverse_children: called CC=10 SCAR=24.1
865  
866 20 my ($self, $node, $flags, $funcref, $argref) = (shift, shift, shift, shift, shift);
867 20 my $child = $self->new();
868  
869 20 $child = $node->{children};
870  
871 20 ▶ while(defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child) 50 20 70
872  
873 50 my $current = $self->new();
874  
875 50 $current = $child;
876 50 $child = $current->{next};
877  
878 50 ▶ if(defined($current->{children})) {
Branch: 2 branches
BranchTrueFalseTotal
if (defined $current->{'children'}) { } 15 35 50
elsif ($flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($current, $argref)) { } 0 42 42
879 15 ▶ if(($flags & $TRAVERSE_NON_LEAFS) && &$funcref($current, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($current, $argref)) 0 15 15
Condition66%2/3
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($current, $argref)
!ll&&!rl&&r
3120
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($current, $argref)
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS &$funcref($current, $argref)
Truth table66%2/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_NON_LEAFSB= &$funcref($current, $argref)
ABresult
0X0
100
111
880 0 return($TRUE);
881 }
882 ▶ } elsif(($flags & $TRAVERSE_LEAFS) && &$funcref($current, $argref)) {
Condition66%2/3
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($current, $argref)
!ll&&!rl&&r
7280
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($current, $argref)
$flags & $Tree::Nary::TRAVERSE_LEAFS &$funcref($current, $argref)
Truth table66%2/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_LEAFSB= &$funcref($current, $argref)
ABresult
0X0
100
111
883 0 return($TRUE);
884 }
885 }
886  
887 20 $child = $node->{children};
888  
889 20 ▶ while(defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child) 50 20 70
890  
891 50 my $current = $self->new();
892  
893 50 $current = $child;
894 50 $child = $current->{next};
895  
896 50 ▶ if(defined($current->{children}) && $self->_traverse_children($current, $flags, $funcref, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $current->{"children"} and $self->_traverse_children($current, $flags, $funcref, $argref)) 0 50 50
Condition66%2/3
defined $current->{"children"} and $self->_traverse_children($current, $flags, $funcref, $argref)
!ll&&!rl&&r
35150
MC/DC0%0/2
defined $current->{"children"} and $self->_traverse_children($current, $flags, $funcref, $argref)
defined $current->{"children"} $self->_traverse_children($current, $flags, $funcref, $argref)
Truth table66%2/3
A and B
A= defined $current->{"children"}B= $self->_traverse_children($current, $flags, $funcref, $argref)
ABresult
0X0
100
111
897 0 return($TRUE);
898 }
899 }
900  
901 20 return($FALSE);
902 }
903  
904 0 ▶sub _depth_traverse_children() {
Subroutine _depth_traverse_children: not called CC=11 SCAR=48.8
905  
906 0 my ($self, $node, $flags, $depth, $funcref, $argref) = (shift, shift, shift, shift, shift, shift);
907 0 my $child = $self->new();
908  
909 0 $child = $node->{children};
910  
911 0 ▶ while(defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child) 0 0 0
912  
913 0 my $current = $self->new();
914  
915 0 $current = $child;
916 0 $child = $current->{next};
917  
918 0 ▶ if(defined($current->{children})) {
Branch: 2 branches
BranchTrueFalseTotal
if (defined $current->{'children'}) { } 0 0 0
elsif ($flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($current, $argref)) { } 0 0 0
919  
920 0 ▶ if(($flags & $TRAVERSE_NON_LEAFS) && &$funcref($current, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($current, $argref)) 0 0 0
Condition0%0/3
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($current, $argref)
!ll&&!rl&&r
000
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($current, $argref)
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS &$funcref($current, $argref)
Truth table0%0/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_NON_LEAFSB= &$funcref($current, $argref)
ABresult
0X0
100
111
921 0 return($TRUE);
922 }
923  
924 ▶ } elsif(($flags & $TRAVERSE_LEAFS) && &$funcref($current, $argref)) {
Condition0%0/3
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($current, $argref)
!ll&&!rl&&r
000
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_LEAFS and &$funcref($current, $argref)
$flags & $Tree::Nary::TRAVERSE_LEAFS &$funcref($current, $argref)
Truth table0%0/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_LEAFSB= &$funcref($current, $argref)
ABresult
0X0
100
111
925 0 return($TRUE);
926 }
927 }
928  
929 0 $depth--;
930 0 ▶ if(!$depth) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($depth) 0 0 0
931 0 return($FALSE);
932 }
933  
934 0 $child = $node->{children};
935  
936 0 ▶ while(defined($child)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $child) 0 0 0
937  
938 0 my $current = $self->new();
939  
940 0 $current = $child;
941 0 $child = $current->{next};
942  
943 0 ▶ if(defined($current->{children}) && $self->_depth_traverse_children($current, $flags, $depth, $funcref, $argref)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $current->{"children"} and $self->_depth_traverse_children($current, $flags, $depth, $funcref, $argref)) 0 0 0
Condition0%0/3
defined $current->{"children"} and $self->_depth_traverse_children($current, $flags, $depth, $funcref, $argref)
!ll&&!rl&&r
000
MC/DC0%0/2
defined $current->{"children"} and $self->_depth_traverse_children($current, $flags, $depth, $funcref, $argref)
defined $current->{"children"} $self->_depth_traverse_children($current, $flags, $depth, $funcref, $argref)
Truth table0%0/3
A and B
A= defined $current->{"children"}B= $self->_depth_traverse_children($current, $flags, $depth, $funcref, $argref)
ABresult
0X0
100
111
944 0 return($TRUE);
945 }
946 }
947  
948 0 return($FALSE);
949 }
950  
951 # Traverses a tree starting at the given root node. It calls the given function for each node visited.
952 # The traversal can be halted at any point by returning TRUE from given function.
953 10 ▶sub traverse() {
Subroutine traverse: called CC=20 SCAR=38.3
Pod documented
954  
955 10 my ($self, $root, $order, $flags, $depth, $funcref, $argref) = (shift, shift, shift, shift, shift, shift, shift);
956  
957 10 ▶ if(!defined($root)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $root) 0 10 10
958 0 return;
959 }
960 10 ▶ if(!defined($funcref)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $funcref) 0 10 10
961 0 return;
962 }
963 10 ▶ if(!($order <= $LEVEL_ORDER)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($order <= $Tree::Nary::LEVEL_ORDER) 0 10 10
964 0 return;
965 }
966 10 ▶ if(!($flags <= $TRAVERSE_MASK)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($flags <= $Tree::Nary::TRAVERSE_MASK) 0 10 10
967 0 return;
968 }
969 10 ▶ if(!($depth == -1 || $depth > 0)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($depth == -1 or $depth > 0) 0 10 10
Condition33%1/3
$depth == -1 or $depth > 0
l!l&&r!l&&!r
1000
MC/DC0%0/2
$depth == -1 or $depth > 0
$depth == -1 $depth > 0
Truth table33%1/3
A or B
A= $depth == -1B= $depth > 0
ABresult
1X1
011
000
970 0 return;
971 }
972  
973 SWITCH: {
974  
975 10 ▶ $order == $PRE_ORDER && do {
Branch: 1 branch
BranchTrueFalseTotal
$order == $Tree::Nary::PRE_ORDER and do { if ($depth < 0) { $self->_traverse_pre_order($root, $flags, $funcref, $argref); } else { $self->_depth_traverse_pre_order($root, $flags, $depth, $funcref, $argref); } ; last SWITCH } 2 8 10
976  
977 2 ▶ if($depth < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth < 0) { } 2 0 2
978 2 $self->_traverse_pre_order($root, $flags, $funcref, $argref);
979 } else {
980 0 $self->_depth_traverse_pre_order($root, $flags, $depth, $funcref, $argref);
981 }
982 2 last SWITCH;
983 };
984 8 ▶ $order == $POST_ORDER && do {
Branch: 1 branch
BranchTrueFalseTotal
$order == $Tree::Nary::POST_ORDER and do { if ($depth < 0) { $self->_traverse_post_order($root, $flags, $funcref, $argref); } else { $self->_depth_traverse_post_order($root, $flags, $depth, $funcref, $argref); } ; last SWITCH } 1 7 8
985  
986 1 ▶ if($depth < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth < 0) { } 1 0 1
987 1 $self->_traverse_post_order($root, $flags, $funcref, $argref);
988 } else {
989 0 $self->_depth_traverse_post_order($root, $flags, $depth, $funcref, $argref);
990 }
991 1 last SWITCH;
992 };
993 7 ▶ $order == $IN_ORDER && do {
Branch: 1 branch
BranchTrueFalseTotal
$order == $Tree::Nary::IN_ORDER and do { if ($depth < 0) { $self->_traverse_in_order($root, $flags, $funcref, $argref); } else { $self->_depth_traverse_in_order($root, $flags, $depth, $funcref, $argref); } ; last SWITCH } 2 5 7
994  
995 2 ▶ if($depth < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth < 0) { } 2 0 2
996 2 $self->_traverse_in_order($root, $flags, $funcref, $argref);
997 } else {
998 0 $self->_depth_traverse_in_order($root, $flags, $depth, $funcref, $argref);
999 }
1000 2 last SWITCH;
1001 };
1002 5 ▶ $order == $LEVEL_ORDER && do {
Branch: 1 branch
BranchTrueFalseTotal
$order == $Tree::Nary::LEVEL_ORDER and do { if (defined $root->{"children"}) { unless ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($root, $argref)) { if ($depth < 0) { $self->_traverse_children($root, $flags, $funcref, $argref); } else { --$depth; if ($depth) { $self->_depth_traverse_children($root, $flags, $depth, $funcref, $argref); } ; } ; } ; } elsif ($flags & $Tree::Nary::TRAVERSE_LEAFS) { &$funcref($root, $argref); } ; last SWITCH } 5 0 5
1003  
1004 5 ▶ if(defined($root->{children})) {
Branch: 2 branches
BranchTrueFalseTotal
if (defined $root->{'children'}) { } 5 0 5
elsif ($flags & $Tree::Nary::TRAVERSE_LEAFS) { } 0 0 0
1005 5 ▶ if(!(($flags & $TRAVERSE_NON_LEAFS) && &$funcref($root, $argref))) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($root, $argref)) 5 0 5
Condition66%2/3
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($root, $argref)
!ll&&!rl&&r
140
MC/DC0%0/2
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS and &$funcref($root, $argref)
$flags & $Tree::Nary::TRAVERSE_NON_LEAFS &$funcref($root, $argref)
Truth table66%2/3
A and B
A= $flags & $Tree::Nary::TRAVERSE_NON_LEAFSB= &$funcref($root, $argref)
ABresult
0X0
100
111
1006 5 ▶ if($depth < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth < 0) { } 5 0 5
1007 5 $self->_traverse_children($root, $flags, $funcref, $argref);
1008 } else {
1009 0 $depth--;
1010 0 ▶ if($depth) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth) 0 0 0
1011 0 $self->_depth_traverse_children($root, $flags, $depth, $funcref, $argref);
1012 }
1013 }
1014 }
1015 } elsif($flags & $TRAVERSE_LEAFS) {
1016 0 &$funcref($root, $argref);
1017 }
1018 5 last SWITCH;
1019 };
1020 } # End SWITCH
1021 }
1022  
1023 # Finds a node in a tree.
1024 2 ▶sub find() {
Subroutine find: called CC=4 SCAR=14.4
Pod documented
1025  
1026 2 my ($self, $root, $order, $flags, $data) = (shift, shift, shift, shift, shift);
1027 2 my @d;
1028  
1029 2 ▶ if(!defined($root)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $root) 0 2 2
1030 0 return(undef);
1031 }
1032 2 ▶ if(!($order <= $LEVEL_ORDER)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($order <= $Tree::Nary::LEVEL_ORDER) 0 2 2
1033 0 return(undef);
1034 }
1035 2 ▶ if(!($flags <= $TRAVERSE_MASK)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($flags <= $Tree::Nary::TRAVERSE_MASK) 0 2 2
1036 0 return(undef);
1037 }
1038  
1039 2 $d[0] = $data;
1040 2 $d[1] = undef;
1041  
1042 $self->traverse(
1043 $root,
1044 $order,
1045 $flags,
1046 -1,
1047 10 ▶ sub {
Subroutine __ANON__: called CC=2 SCAR=6.9
1048 10 my ($node, $ref_of_array) = (shift, shift);
1049  
1050 10 ▶ if($$ref_of_array[0] ne $node->{data}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($ref_of_array->[0] ne $node->{"data"}) 9 1 10
1051 9 return($FALSE);
1052 }
1053  
1054 1 $$ref_of_array[1] = $node;
1055  
1056 1 return($TRUE);
1057 },
1058 \@d
1059 2 );
1060  
1061 2 return($d[1]);
1062 }
1063  
1064 # Finds the first child of a node with the given data.
1065 1 ▶sub find_child() {
Subroutine find_child: called CC=8 SCAR=25.3
Pod documented
1066  
1067 1 my ($self, $node, $flags, $data) = (shift, shift, shift, shift);
1068  
1069 1 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 1 1
1070 0 return(undef);
1071 }
1072 1 ▶ if(!($flags <= $TRAVERSE_MASK)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($flags <= $Tree::Nary::TRAVERSE_MASK) 0 1 1
1073 0 return(undef);
1074 }
1075  
1076 1 $node = $node->{children};
1077  
1078 1 ▶ while(defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node) 2 0 2
1079  
1080 2 ▶ if($node->{data} eq $data) {
Branch: 1 branch
BranchTrueFalseTotal
if ($node->{"data"} eq $data) 1 1 2
1081 1 ▶ if($self->is_leaf($node)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->is_leaf($node)) { } 0 1 1
1082 0 ▶ if($flags & $TRAVERSE_LEAFS) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flags & $Tree::Nary::TRAVERSE_LEAFS) 0 0 0
1083 0 return($node);
1084 }
1085 } else {
1086 1 ▶ if($flags & $TRAVERSE_NON_LEAFS) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS) 1 0 1
1087 1 return($node);
1088 }
1089 }
1090 }
1091  
1092 1 $node = $node->{next};
1093 }
1094  
1095 0 return(undef);
1096 }
1097  
1098 # Calls a function for each of the children of a node.
1099 # Note that it doesn't descend beneath the child nodes.
1100 12 ▶sub children_foreach() {
Subroutine children_foreach: called CC=8 SCAR=22.0
Pod documented
1101  
1102 12 my ($self, $node, $flags, $funcref, $argref) = (shift, shift, shift, shift, shift);
1103  
1104 12 ▶ if(!defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $node) 0 12 12
1105 0 return;
1106 }
1107 12 ▶ if(!($flags <= $TRAVERSE_MASK)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($flags <= $Tree::Nary::TRAVERSE_MASK) 0 12 12
1108 0 return;
1109 }
1110 12 ▶ if(!defined($funcref)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $funcref) 0 12 12
1111 0 return;
1112 }
1113  
1114 12 $node = $node->{children};
1115  
1116 12 ▶ while(defined($node)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $node) 30 12 42
1117  
1118 30 my $current = $self->new();
1119  
1120 30 $current = $node;
1121 30 $node = $current->{next};
1122  
1123 30 ▶ if($self->is_leaf($current)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->is_leaf($current)) { } 23 7 30
1124 23 ▶ if($flags & $TRAVERSE_LEAFS) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flags & $Tree::Nary::TRAVERSE_LEAFS) 23 0 23
1125 23 &$funcref($current, $argref);
1126 }
1127 } else {
1128 7 ▶ if($flags & $TRAVERSE_NON_LEAFS) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flags & $Tree::Nary::TRAVERSE_NON_LEAFS) 7 0 7
1129 7 &$funcref($current, $argref);
1130 }
1131 }
1132 }
1133  
1134 12 return;
1135 }
1136  
1137 #
1138 # Sort methods
1139 #
1140  
1141 #_pchild_ref is just gathering references
1142 30 ▶sub _pchild_ref() {
Subroutine _pchild_ref: called CC=1 SCAR=0.0
1143  
1144 30 my ($node, $aref) = (shift, shift);
1145  
1146 30 push @$aref, $node;
1147 }
1148  
1149 # Sort a tree
1150 11 ▶sub tsort() {
Subroutine tsort: called CC=3 SCAR=11.0
Pod documented
1151  
1152 11 my ($self, $node) = (shift, shift);
1153 11 my @back;
1154  
1155 11 ▶ return if($self->is_leaf($node));
Branch: 1 branch
BranchTrueFalseTotal
if $self->is_leaf($node) 7 4 11
1156  
1157 # gather all the children references and sort them
1158 # according to the data field backwards (Z Y X W ...)
1159 4 $self->children_foreach($node, $Tree::Nary::TRAVERSE_ALL, \&_pchild_ref, \@back);
1160 4 @back = sort { $b->{data} cmp $a->{data} } @back;
1161  
1162 4 for (@back) { # for every reference found (in backward order)
1163 10 $self->unlink($_); # detach it from parent
1164 10 $self->prepend($node, $_); # prepend it 0> first child
1165 10 $self->tsort($_); # call tsort recursively for its children
1166 }
1167 }
1168  
1169 #
1170 # Comparison methods
1171 #
1172  
1173 # Generate a normalized tree
1174 12 ▶sub normalize() {
Subroutine normalize: called CC=3 SCAR=11.0
Pod documented
1175  
1176 12 my ($self, $node) = (shift, shift);
1177  
1178 # Initialize result for a leaf
1179 12 my $result = '*';
1180  
1181 12 ▶ if(!$self->is_leaf($node)) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($self->is_leaf($node)) 4 8 12
1182  
1183 4 my @childs;
1184 my @chldMaps;
1185  
1186 4 $self->children_foreach($node, $Tree::Nary::TRAVERSE_ALL, \&_pchild_ref, \@childs);
1187  
1188 4 for(@childs) {
1189 10 push @chldMaps, $self->normalize($_);
1190 }
1191  
1192 4 $result = '('.join('', sort @chldMaps).')';
1193 }
1194  
1195 12 return($result);
1196 }
1197  
1198 # Compares two trees and returns TRUE if they are identical
1199 # in their structures and their contents
1200 6 ▶sub is_identical() {
Subroutine is_identical: called CC=10 SCAR=25.0
Pod documented
1201  
1202 6 my ($self, $t1, $t2) = (shift, shift, shift);
1203 6 my $i;
1204 my @t1childs;
1205 6 my @t2childs;
1206  
1207 # Exit if one of them is leaf and the other isn't
1208 6 ▶ return($FALSE) if(($self->is_leaf($t1) && !$self->is_leaf($t2)) or
Branch: 1 branch
BranchTrueFalseTotal
if $self->is_leaf($t1) and not $self->is_leaf($t2) or not $self->is_leaf($t1) and $self->is_leaf($t2) 0 6 6
Condition55%5/9
$self->is_leaf($t1) and not $self->is_leaf($t2) or not $self->is_leaf($t1) and $self->is_leaf($t2)
l!l&&r!l&&!r
006
$self->is_leaf($t1) and not $self->is_leaf($t2)
!ll&&!rl&&r
240
not $self->is_leaf($t1) and $self->is_leaf($t2)
!ll&&!rl&&r
420
MC/DC0%0/4
$self->is_leaf($t1) and not $self->is_leaf($t2) or not $self->is_leaf($t1) and $self->is_leaf($t2)
$self->is_leaf($t1) not $self->is_leaf($t2) not $self->is_leaf($t1) $self->is_leaf($t2)
Truth table28%2/7
A and not(B) or not(C) and D
A= $self->is_leaf($t1)B= not $self->is_leaf($t2)C= not $self->is_leaf($t1)D= $self->is_leaf($t2)
ABCDresult
11XX1
0X111
10111
0X0X0
0X100
100X0
10100
1209 (!$self->is_leaf($t1) && $self->is_leaf($t2)));
1210  
1211 # Exit if they have different amount of children
1212 6 ▶ return($FALSE) if($self->n_children($t1) != $self->n_children($t2));
Branch: 1 branch
BranchTrueFalseTotal
if $self->n_children($t1) != $self->n_children($t2) 0 6 6
1213  
1214 # => HERE BOTH ARE LEAFS OR PARENTS WITH SAME AMOUNT OF CHILDREN
1215  
1216 6 ▶ return($FALSE) if($t1->{data} ne $t2->{data}); # exit if different content
Branch: 1 branch
BranchTrueFalseTotal
if $t1->{"data"} ne $t2->{"data"} 0 6 6
1217 6 ▶ return($TRUE) if($self->is_leaf($t1)); # if T1 is leaf, both are: hey, identical!!
Branch: 1 branch
BranchTrueFalseTotal
if $self->is_leaf($t1) 4 2 6
1218  
1219 # => HERE BOTH ARE PARENTS WITH SAME AMOUNT OF CHILDREN
1220  
1221 # get the children references for $t1 and $t2
1222 2 $self->children_foreach($t1, $Tree::Nary::TRAVERSE_ALL, \&_pchild_ref, \@t1childs);
1223 2 $self->children_foreach($t2, $Tree::Nary::TRAVERSE_ALL,\&_pchild_ref, \@t2childs);
1224  
1225 2 for $i (0 .. scalar(@t1childs)-1) { # iterate all children by index
1226 5 ▶ next if($self->is_identical($t1childs[$i], $t2childs[$i]) == $TRUE);
Branch: 1 branch
BranchTrueFalseTotal
if $self->is_identical($t1childs[$i], $t2childs[$i]) == $Tree::Nary::TRUE 5 0 5
1227 0 return($FALSE);
1228 }
1229  
1230 2 return($TRUE);
1231 }
1232  
1233 # Compare the structure of two trees by comparing their canonical shapes
1234 1 ▶sub has_same_struct() {
Subroutine has_same_struct: called CC=2 SCAR=7.4
Pod documented
1235  
1236 1 my ($self, $t1, $t2) = (shift, shift, shift);
1237 1 my $t1c = $self->normalize($t1);
1238 1 my $t2c = $self->normalize($t2);
1239  
1240 1 ▶ return($TRUE) if($t1c eq $t2c); # if the two canons are identical, structure is same
Branch: 1 branch
BranchTrueFalseTotal
if $t1c eq $t2c 1 0 1
1241 0 return($FALSE); # structure is different
1242 }
1243  
1244 2 1;
1245  
1246 __END__
↑ Summary