line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
package Code::Includable::Tree::NodeMethods; |
2
|
|
|
|
|
|
|
|
3
|
|
|
|
|
|
|
our $AUTHORITY = 'cpan:PERLANCAR'; # AUTHORITY |
4
|
|
|
|
|
|
|
our $DATE = '2021-07-02'; # DATE |
5
|
|
|
|
|
|
|
our $DIST = 'Role-TinyCommons-Tree'; # DIST |
6
|
|
|
|
|
|
|
our $VERSION = '0.127'; # VERSION |
7
|
|
|
|
|
|
|
|
8
|
3
|
|
|
3
|
|
477
|
use strict; |
|
3
|
|
|
|
|
6
|
|
|
3
|
|
|
|
|
215
|
|
9
|
|
|
|
|
|
|
our $IGNORE_NO_CHILDREN_METHOD = 1; |
10
|
|
|
|
|
|
|
|
11
|
|
|
|
|
|
|
our $GET_PARENT_METHOD = 'parent'; |
12
|
|
|
|
|
|
|
our $GET_CHILDREN_METHOD = 'children'; |
13
|
|
|
|
|
|
|
our $SET_PARENT_METHOD = 'parent'; |
14
|
|
|
|
|
|
|
our $SET_CHILDREN_METHOD = 'children'; |
15
|
|
|
|
|
|
|
|
16
|
|
|
|
|
|
|
# we must contain no other functions |
17
|
|
|
|
|
|
|
|
18
|
3
|
|
|
3
|
|
16
|
use Scalar::Util (); |
|
3
|
|
|
|
|
5
|
|
|
3
|
|
|
|
|
6398
|
|
19
|
|
|
|
|
|
|
|
20
|
|
|
|
|
|
|
# like children, but always return list |
21
|
|
|
|
|
|
|
sub _children_as_list { |
22
|
320
|
|
|
320
|
|
466
|
my $self = shift; |
23
|
320
|
|
|
|
|
466
|
my @children; |
24
|
320
|
50
|
|
|
|
564
|
if ($IGNORE_NO_CHILDREN_METHOD) { |
25
|
320
|
|
|
|
|
435
|
eval { |
26
|
320
|
|
|
|
|
727
|
@children = $self->$GET_CHILDREN_METHOD; |
27
|
|
|
|
|
|
|
}; |
28
|
320
|
50
|
|
|
|
1586
|
return () if $@; |
29
|
|
|
|
|
|
|
} else { |
30
|
0
|
|
|
|
|
0
|
@children = $self->$GET_CHILDREN_METHOD; |
31
|
|
|
|
|
|
|
} |
32
|
|
|
|
|
|
|
|
33
|
320
|
100
|
|
|
|
582
|
if (@children == 1) { |
34
|
245
|
100
|
|
|
|
472
|
return () unless defined($children[0]); |
35
|
209
|
100
|
|
|
|
463
|
return @{$children[0]} if ref($children[0]) eq 'ARRAY'; |
|
201
|
|
|
|
|
530
|
|
36
|
|
|
|
|
|
|
} |
37
|
83
|
|
|
|
|
137
|
@children; |
38
|
|
|
|
|
|
|
} |
39
|
|
|
|
|
|
|
|
40
|
|
|
|
|
|
|
# direct children first |
41
|
|
|
|
|
|
|
sub _descendants { |
42
|
80
|
|
|
80
|
|
117
|
my ($self, $res) = @_; |
43
|
80
|
|
|
|
|
116
|
my @children = _children_as_list($self); |
44
|
80
|
|
|
|
|
124
|
push @$res, @children; |
45
|
80
|
|
|
|
|
146
|
for (@children) { _descendants($_, $res) } |
|
72
|
|
|
|
|
121
|
|
46
|
|
|
|
|
|
|
} |
47
|
|
|
|
|
|
|
|
48
|
|
|
|
|
|
|
sub descendants { |
49
|
8
|
|
|
8
|
1
|
17
|
my $self = shift; |
50
|
8
|
|
|
|
|
14
|
my $res = []; |
51
|
8
|
|
|
|
|
24
|
_descendants($self, $res); |
52
|
8
|
|
|
|
|
64
|
@$res; |
53
|
|
|
|
|
|
|
} |
54
|
|
|
|
|
|
|
|
55
|
|
|
|
|
|
|
sub _descendants_depth_first { |
56
|
40
|
|
|
40
|
|
67
|
my ($self, $res) = @_; |
57
|
40
|
|
|
|
|
66
|
my @children = _children_as_list($self); |
58
|
40
|
|
|
|
|
75
|
for (@children) { |
59
|
36
|
|
|
|
|
58
|
push @$res, $_; |
60
|
36
|
|
|
|
|
67
|
_descendants_depth_first($_, $res); |
61
|
|
|
|
|
|
|
} |
62
|
|
|
|
|
|
|
} |
63
|
|
|
|
|
|
|
|
64
|
|
|
|
|
|
|
sub descendants_depth_first { |
65
|
4
|
|
|
4
|
1
|
32
|
my $self = shift; |
66
|
4
|
|
|
|
|
10
|
my $res = []; |
67
|
4
|
|
|
|
|
25
|
_descendants_depth_first($self, $res); |
68
|
4
|
|
|
|
|
34
|
@$res; |
69
|
|
|
|
|
|
|
} |
70
|
|
|
|
|
|
|
|
71
|
|
|
|
|
|
|
sub ancestors { |
72
|
9
|
|
|
9
|
1
|
1139
|
my $self = shift; |
73
|
9
|
|
|
|
|
13
|
my @res; |
74
|
9
|
|
|
|
|
35
|
my $parent = $self->$GET_PARENT_METHOD; |
75
|
9
|
|
|
|
|
41
|
while ($parent) { |
76
|
14
|
|
|
|
|
41
|
push @res, $parent; |
77
|
14
|
|
|
|
|
41
|
$parent = $parent->$GET_PARENT_METHOD; |
78
|
|
|
|
|
|
|
} |
79
|
9
|
|
|
|
|
70
|
@res; |
80
|
|
|
|
|
|
|
} |
81
|
|
|
|
|
|
|
|
82
|
|
|
|
|
|
|
sub retrieve_parent { |
83
|
4
|
|
|
4
|
1
|
12
|
my $self = shift; |
84
|
4
|
|
|
|
|
37
|
$self->$GET_PARENT_METHOD; |
85
|
|
|
|
|
|
|
} |
86
|
|
|
|
|
|
|
|
87
|
|
|
|
|
|
|
sub walk { |
88
|
0
|
|
|
0
|
1
|
0
|
my ($self, $code) = @_; |
89
|
0
|
|
|
|
|
0
|
for (descendants($self)) { |
90
|
0
|
|
|
|
|
0
|
$code->($_); |
91
|
|
|
|
|
|
|
} |
92
|
|
|
|
|
|
|
} |
93
|
|
|
|
|
|
|
|
94
|
|
|
|
|
|
|
sub first_node { |
95
|
4
|
|
|
4
|
1
|
12
|
my ($self, $code) = @_; |
96
|
4
|
|
|
|
|
10
|
for (descendants($self)) { |
97
|
20
|
100
|
|
|
|
73
|
return $_ if $code->($_); |
98
|
|
|
|
|
|
|
} |
99
|
0
|
|
|
|
|
0
|
undef; |
100
|
|
|
|
|
|
|
} |
101
|
|
|
|
|
|
|
|
102
|
|
|
|
|
|
|
sub is_first_child { |
103
|
12
|
|
|
12
|
1
|
26
|
my $self = shift; |
104
|
12
|
|
|
|
|
41
|
my $parent = $self->$GET_PARENT_METHOD; |
105
|
12
|
100
|
|
|
|
71
|
return 0 unless $parent; |
106
|
8
|
|
|
|
|
18
|
my @siblings = _children_as_list($parent); |
107
|
8
|
50
|
|
|
|
67
|
@siblings && Scalar::Util::refaddr($self) == Scalar::Util::refaddr($siblings[0]); |
108
|
|
|
|
|
|
|
} |
109
|
|
|
|
|
|
|
|
110
|
|
|
|
|
|
|
sub is_last_child { |
111
|
12
|
|
|
12
|
1
|
23
|
my $self = shift; |
112
|
12
|
|
|
|
|
38
|
my $parent = $self->$GET_PARENT_METHOD; |
113
|
12
|
100
|
|
|
|
76
|
return 0 unless $parent; |
114
|
8
|
|
|
|
|
17
|
my @siblings = _children_as_list($parent); |
115
|
8
|
50
|
|
|
|
94
|
@siblings && Scalar::Util::refaddr($self) == Scalar::Util::refaddr($siblings[-1]); |
116
|
|
|
|
|
|
|
} |
117
|
|
|
|
|
|
|
|
118
|
|
|
|
|
|
|
sub is_only_child { |
119
|
12
|
|
|
12
|
1
|
26
|
my $self = shift; |
120
|
12
|
|
|
|
|
37
|
my $parent = $self->$GET_PARENT_METHOD; |
121
|
12
|
100
|
|
|
|
71
|
return 0 unless $parent; |
122
|
8
|
|
|
|
|
17
|
my @siblings = _children_as_list($parent); |
123
|
8
|
|
|
|
|
38
|
@siblings==1;# && Scalar::Util::refaddr($self) == Scalar::Util::refaddr($siblings[0]); |
124
|
|
|
|
|
|
|
} |
125
|
|
|
|
|
|
|
|
126
|
|
|
|
|
|
|
sub is_nth_child { |
127
|
12
|
|
|
12
|
1
|
27
|
my ($self, $n) = @_; |
128
|
12
|
|
|
|
|
37
|
my $parent = $self->$GET_PARENT_METHOD; |
129
|
12
|
50
|
|
|
|
54
|
return 0 unless $parent; |
130
|
12
|
|
|
|
|
25
|
my @siblings = _children_as_list($parent); |
131
|
12
|
50
|
|
|
|
131
|
@siblings >= $n && Scalar::Util::refaddr($self) == Scalar::Util::refaddr($siblings[$n-1]); |
132
|
|
|
|
|
|
|
} |
133
|
|
|
|
|
|
|
|
134
|
|
|
|
|
|
|
sub is_nth_last_child { |
135
|
12
|
|
|
12
|
1
|
32
|
my ($self, $n) = @_; |
136
|
12
|
|
|
|
|
40
|
my $parent = $self->$GET_PARENT_METHOD; |
137
|
12
|
50
|
|
|
|
63
|
return 0 unless $parent; |
138
|
12
|
|
|
|
|
26
|
my @siblings = _children_as_list($parent); |
139
|
12
|
50
|
|
|
|
114
|
@siblings >= $n && Scalar::Util::refaddr($self) == Scalar::Util::refaddr($siblings[-$n]); |
140
|
|
|
|
|
|
|
} |
141
|
|
|
|
|
|
|
|
142
|
|
|
|
|
|
|
sub is_first_child_of_type { |
143
|
20
|
|
|
20
|
1
|
38
|
my $self = shift; |
144
|
20
|
|
|
|
|
77
|
my $parent = $self->$GET_PARENT_METHOD; |
145
|
20
|
50
|
|
|
|
85
|
return 0 unless $parent; |
146
|
20
|
|
|
|
|
36
|
my $type = ref($self); |
147
|
20
|
|
|
|
|
48
|
my @siblings = grep { ref($_) eq $type } _children_as_list($parent); |
|
100
|
|
|
|
|
198
|
|
148
|
20
|
50
|
|
|
|
218
|
@siblings && Scalar::Util::refaddr($self) == Scalar::Util::refaddr($siblings[0]); |
149
|
|
|
|
|
|
|
} |
150
|
|
|
|
|
|
|
|
151
|
|
|
|
|
|
|
sub is_last_child_of_type { |
152
|
40
|
|
|
40
|
1
|
68
|
my $self = shift; |
153
|
40
|
|
|
|
|
131
|
my $parent = $self->$GET_PARENT_METHOD; |
154
|
40
|
50
|
|
|
|
166
|
return 0 unless $parent; |
155
|
40
|
|
|
|
|
69
|
my $type = ref($self); |
156
|
40
|
|
|
|
|
83
|
my @siblings = grep { ref($_) eq $type } _children_as_list($parent); |
|
200
|
|
|
|
|
396
|
|
157
|
40
|
50
|
|
|
|
362
|
@siblings && Scalar::Util::refaddr($self) == Scalar::Util::refaddr($siblings[-1]); |
158
|
|
|
|
|
|
|
} |
159
|
|
|
|
|
|
|
|
160
|
|
|
|
|
|
|
sub is_only_child_of_type { |
161
|
8
|
|
|
8
|
1
|
19
|
my $self = shift; |
162
|
8
|
|
|
|
|
38
|
my $parent = $self->$GET_PARENT_METHOD; |
163
|
8
|
50
|
|
|
|
39
|
return 0 unless $parent; |
164
|
8
|
|
|
|
|
14
|
my $type = ref($self); |
165
|
8
|
|
|
|
|
28
|
my @siblings = grep { ref($_) eq $type } _children_as_list($parent); |
|
40
|
|
|
|
|
83
|
|
166
|
8
|
|
|
|
|
40
|
@siblings == 1; # && Scalar::Util::refaddr($self) == Scalar::Util::refaddr($siblings[0]); |
167
|
|
|
|
|
|
|
} |
168
|
|
|
|
|
|
|
|
169
|
|
|
|
|
|
|
sub is_nth_child_of_type { |
170
|
16
|
|
|
16
|
1
|
36
|
my ($self, $n) = @_; |
171
|
16
|
|
|
|
|
55
|
my $parent = $self->$GET_PARENT_METHOD; |
172
|
16
|
50
|
|
|
|
70
|
return 0 unless $parent; |
173
|
16
|
|
|
|
|
36
|
my $type = ref($self); |
174
|
16
|
|
|
|
|
37
|
my @siblings = grep { ref($_) eq $type } _children_as_list($parent); |
|
80
|
|
|
|
|
161
|
|
175
|
16
|
50
|
|
|
|
139
|
@siblings >= $n && Scalar::Util::refaddr($self) == Scalar::Util::refaddr($siblings[$n-1]); |
176
|
|
|
|
|
|
|
} |
177
|
|
|
|
|
|
|
|
178
|
|
|
|
|
|
|
sub is_nth_last_child_of_type { |
179
|
16
|
|
|
16
|
1
|
37
|
my ($self, $n) = @_; |
180
|
16
|
|
|
|
|
52
|
my $parent = $self->$GET_PARENT_METHOD; |
181
|
16
|
50
|
|
|
|
71
|
return 0 unless $parent; |
182
|
16
|
|
|
|
|
35
|
my $type = ref($self); |
183
|
16
|
|
|
|
|
36
|
my @children = grep { ref($_) eq $type } _children_as_list($parent); |
|
80
|
|
|
|
|
163
|
|
184
|
16
|
50
|
|
|
|
137
|
@children >= $n && Scalar::Util::refaddr($self) == Scalar::Util::refaddr($children[-$n]); |
185
|
|
|
|
|
|
|
} |
186
|
|
|
|
|
|
|
|
187
|
|
|
|
|
|
|
sub prev_sibling { |
188
|
12
|
|
|
12
|
1
|
25
|
my $self = shift; |
189
|
12
|
50
|
|
|
|
54
|
my $parent = $self->$GET_PARENT_METHOD or return undef; |
190
|
12
|
|
|
|
|
197
|
my $refaddr = Scalar::Util::refaddr($self); |
191
|
12
|
|
|
|
|
63
|
my @siblings = _children_as_list($parent); |
192
|
12
|
|
|
|
|
35
|
for my $i (1..$#siblings) { |
193
|
40
|
100
|
|
|
|
96
|
if (Scalar::Util::refaddr($siblings[$i]) == $refaddr) { |
194
|
8
|
|
|
|
|
42
|
return $siblings[$i-1]; |
195
|
|
|
|
|
|
|
} |
196
|
|
|
|
|
|
|
} |
197
|
4
|
|
|
|
|
21
|
undef; |
198
|
|
|
|
|
|
|
} |
199
|
|
|
|
|
|
|
|
200
|
|
|
|
|
|
|
sub prev_siblings { |
201
|
8
|
|
|
8
|
1
|
17
|
my $self = shift; |
202
|
8
|
50
|
|
|
|
33
|
my $parent = $self->$GET_PARENT_METHOD or return (); |
203
|
8
|
|
|
|
|
42
|
my $refaddr = Scalar::Util::refaddr($self); |
204
|
8
|
|
|
|
|
18
|
my @siblings = _children_as_list($parent); |
205
|
8
|
|
|
|
|
23
|
for my $i (1..$#siblings) { |
206
|
24
|
100
|
|
|
|
82
|
if (Scalar::Util::refaddr($siblings[$i]) == $refaddr) { |
207
|
4
|
|
|
|
|
49
|
return @siblings[0..$i-1]; |
208
|
|
|
|
|
|
|
} |
209
|
|
|
|
|
|
|
} |
210
|
4
|
|
|
|
|
22
|
(); |
211
|
|
|
|
|
|
|
} |
212
|
|
|
|
|
|
|
|
213
|
|
|
|
|
|
|
sub next_sibling { |
214
|
12
|
|
|
12
|
1
|
25
|
my $self = shift; |
215
|
12
|
50
|
|
|
|
48
|
my $parent = $self->$GET_PARENT_METHOD or return undef; |
216
|
12
|
|
|
|
|
58
|
my $refaddr = Scalar::Util::refaddr($self); |
217
|
12
|
|
|
|
|
25
|
my @siblings = _children_as_list($parent); |
218
|
12
|
|
|
|
|
33
|
for my $i (0..$#siblings-1) { |
219
|
32
|
100
|
|
|
|
84
|
if (Scalar::Util::refaddr($siblings[$i]) == $refaddr) { |
220
|
8
|
|
|
|
|
42
|
return $siblings[$i+1]; |
221
|
|
|
|
|
|
|
} |
222
|
|
|
|
|
|
|
} |
223
|
4
|
|
|
|
|
18
|
undef; |
224
|
|
|
|
|
|
|
} |
225
|
|
|
|
|
|
|
|
226
|
|
|
|
|
|
|
sub next_siblings { |
227
|
8
|
|
|
8
|
1
|
19
|
my $self = shift; |
228
|
8
|
50
|
|
|
|
30
|
my $parent = $self->$GET_PARENT_METHOD or return (); |
229
|
8
|
|
|
|
|
43
|
my $refaddr = Scalar::Util::refaddr($self); |
230
|
8
|
|
|
|
|
30
|
my @siblings = _children_as_list($parent); |
231
|
8
|
|
|
|
|
27
|
for my $i (0..$#siblings-1) { |
232
|
28
|
100
|
|
|
|
63
|
if (Scalar::Util::refaddr($siblings[$i]) == $refaddr) { |
233
|
4
|
|
|
|
|
31
|
return @siblings[$i+1 .. $#siblings]; |
234
|
|
|
|
|
|
|
} |
235
|
|
|
|
|
|
|
} |
236
|
4
|
|
|
|
|
21
|
(); |
237
|
|
|
|
|
|
|
} |
238
|
|
|
|
|
|
|
|
239
|
|
|
|
|
|
|
sub is_root { |
240
|
4
|
|
|
4
|
1
|
11
|
my ($self, $n) = @_; |
241
|
4
|
|
|
|
|
17
|
my $parent = $self->$GET_PARENT_METHOD; |
242
|
4
|
100
|
|
|
|
31
|
return $parent ? 0:1; |
243
|
|
|
|
|
|
|
} |
244
|
|
|
|
|
|
|
|
245
|
|
|
|
|
|
|
sub has_min_children { |
246
|
0
|
|
|
0
|
1
|
0
|
my ($self, $m) = @_; |
247
|
0
|
|
|
|
|
0
|
my @children = _children_as_list($self); |
248
|
0
|
|
|
|
|
0
|
@children >= $m; |
249
|
|
|
|
|
|
|
} |
250
|
|
|
|
|
|
|
|
251
|
|
|
|
|
|
|
sub has_max_children { |
252
|
0
|
|
|
0
|
1
|
0
|
my ($self, $n) = @_; |
253
|
0
|
|
|
|
|
0
|
my @children = _children_as_list($self); |
254
|
0
|
|
|
|
|
0
|
@children <= $n; |
255
|
|
|
|
|
|
|
} |
256
|
|
|
|
|
|
|
|
257
|
|
|
|
|
|
|
sub has_children_between { |
258
|
0
|
|
|
0
|
1
|
0
|
my ($self, $m, $n) = @_; |
259
|
0
|
|
|
|
|
0
|
my @children = _children_as_list($self); |
260
|
0
|
0
|
|
|
|
0
|
@children >= $m && @children <= $n; |
261
|
|
|
|
|
|
|
} |
262
|
|
|
|
|
|
|
|
263
|
|
|
|
|
|
|
# remove self from parent |
264
|
|
|
|
|
|
|
sub remove { |
265
|
4
|
|
|
4
|
1
|
9
|
my $self = shift; |
266
|
4
|
50
|
|
|
|
31
|
my $parent = $self->$GET_PARENT_METHOD or return; |
267
|
4
|
|
|
|
|
26
|
my $refaddr = Scalar::Util::refaddr($self); |
268
|
4
|
|
|
|
|
7
|
my @remaining_siblings; |
269
|
4
|
|
|
|
|
11
|
for my $sibling (_children_as_list($parent)) { |
270
|
12
|
100
|
|
|
|
32
|
if (Scalar::Util::refaddr($sibling) == $refaddr) { |
271
|
4
|
|
|
|
|
12
|
$sibling->$SET_PARENT_METHOD(undef); |
272
|
4
|
|
|
|
|
16
|
next; |
273
|
|
|
|
|
|
|
} |
274
|
8
|
|
|
|
|
13
|
push @remaining_siblings, $sibling; |
275
|
|
|
|
|
|
|
} |
276
|
4
|
|
|
|
|
27
|
$parent->$SET_CHILDREN_METHOD(\@remaining_siblings); |
277
|
|
|
|
|
|
|
} |
278
|
|
|
|
|
|
|
|
279
|
|
|
|
|
|
|
# check references |
280
|
|
|
|
|
|
|
sub check { |
281
|
10
|
|
|
10
|
1
|
20
|
my $self = shift; |
282
|
10
|
|
100
|
|
|
43
|
my $opts = shift // {}; |
283
|
|
|
|
|
|
|
|
284
|
10
|
100
|
|
|
|
28
|
if ($opts->{check_root}) { |
285
|
4
|
|
|
|
|
14
|
my $parent = $self->$GET_PARENT_METHOD; |
286
|
4
|
100
|
|
|
|
46
|
defined $parent and die "check: parent is not undef"; |
287
|
|
|
|
|
|
|
} |
288
|
|
|
|
|
|
|
|
289
|
|
|
|
|
|
|
# check that all children refers back to me in their parent |
290
|
8
|
|
|
|
|
21
|
my $refaddr = Scalar::Util::refaddr($self); |
291
|
8
|
|
|
|
|
12
|
my $i = 0; |
292
|
8
|
|
|
|
|
19
|
for my $child (_children_as_list($self)) { |
293
|
12
|
|
|
|
|
31
|
my $childs_parent = $child->$GET_PARENT_METHOD; |
294
|
12
|
100
|
66
|
|
|
90
|
unless (defined $childs_parent && |
295
|
|
|
|
|
|
|
Scalar::Util::refaddr($childs_parent) == $refaddr) { |
296
|
4
|
|
|
|
|
50
|
die "check: Child #$i of $self does not refer back to its parent"; |
297
|
|
|
|
|
|
|
} |
298
|
|
|
|
|
|
|
check($child, { |
299
|
|
|
|
|
|
|
recurse=>1, |
300
|
|
|
|
|
|
|
#check_root=>0, |
301
|
8
|
50
|
|
|
|
35
|
}) if $opts->{recurse}; |
302
|
|
|
|
|
|
|
} |
303
|
|
|
|
|
|
|
} |
304
|
|
|
|
|
|
|
|
305
|
|
|
|
|
|
|
|
306
|
|
|
|
|
|
|
1; |
307
|
|
|
|
|
|
|
# ABSTRACT: Tree node routines |
308
|
|
|
|
|
|
|
|
309
|
|
|
|
|
|
|
__END__ |