line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
# -*- perl -*- |
2
|
|
|
|
|
|
|
|
3
|
|
|
|
|
|
|
# |
4
|
|
|
|
|
|
|
# $Id: GenericTree.pm,v 1.4 2004/02/02 08:11:59 eserte Exp $ |
5
|
|
|
|
|
|
|
# Author: Slaven Rezic |
6
|
|
|
|
|
|
|
# |
7
|
|
|
|
|
|
|
# Copyright (c) 1995-2000 Slaven Rezic. All rights reserved. |
8
|
|
|
|
|
|
|
# Copyright (C) 2000,2002 Online Office Berlin. All rights reserved. |
9
|
|
|
|
|
|
|
# Copyright (c) 2002,2004 Slaven Rezic. All rights reserved. |
10
|
|
|
|
|
|
|
# This program is free software; you can redistribute it and/or |
11
|
|
|
|
|
|
|
# modify it under the same terms as Perl itself. |
12
|
|
|
|
|
|
|
# |
13
|
|
|
|
|
|
|
# Mail: slaven@rezic.de |
14
|
|
|
|
|
|
|
# WWW: http://we-framework.sourceforge.net |
15
|
|
|
|
|
|
|
# |
16
|
|
|
|
|
|
|
# This is derived from Timex::Project. |
17
|
|
|
|
|
|
|
# |
18
|
|
|
|
|
|
|
|
19
|
|
|
|
|
|
|
package WE::Util::GenericTree; |
20
|
|
|
|
|
|
|
|
21
|
|
|
|
|
|
|
=head1 NAME |
22
|
|
|
|
|
|
|
|
23
|
|
|
|
|
|
|
WE::Util::GenericTree - generic class for tree representations |
24
|
|
|
|
|
|
|
|
25
|
|
|
|
|
|
|
=head1 SYNOPSIS |
26
|
|
|
|
|
|
|
|
27
|
|
|
|
|
|
|
$tree = new WE::Util::GenericTree $data |
28
|
|
|
|
|
|
|
|
29
|
|
|
|
|
|
|
=head1 DESCRIPTION |
30
|
|
|
|
|
|
|
|
31
|
|
|
|
|
|
|
=cut |
32
|
|
|
|
|
|
|
|
33
|
2
|
|
|
2
|
|
9
|
use strict; |
|
2
|
|
|
|
|
4
|
|
|
2
|
|
|
|
|
62
|
|
34
|
2
|
|
|
2
|
|
9
|
use vars qw($VERSION); |
|
2
|
|
|
|
|
3
|
|
|
2
|
|
|
|
|
145
|
|
35
|
|
|
|
|
|
|
$VERSION = sprintf("%d.%02d", q$Revision: 1.4 $ =~ /(\d+)\.(\d+)/); |
36
|
|
|
|
|
|
|
|
37
|
2
|
|
|
2
|
|
2097
|
use fields qw(Data Id Subtrees Parent Modified Separator); |
|
2
|
|
|
|
|
8178
|
|
|
2
|
|
|
|
|
14
|
|
38
|
|
|
|
|
|
|
|
39
|
|
|
|
|
|
|
=head2 new |
40
|
|
|
|
|
|
|
|
41
|
|
|
|
|
|
|
$tree = new WE::Util::GenericTree $data |
42
|
|
|
|
|
|
|
|
43
|
|
|
|
|
|
|
Construct a new GenericTree object with content $data. |
44
|
|
|
|
|
|
|
|
45
|
|
|
|
|
|
|
=cut |
46
|
|
|
|
|
|
|
|
47
|
|
|
|
|
|
|
sub new { |
48
|
92
|
|
|
92
|
1
|
100
|
my WE::Util::GenericTree $self; |
49
|
|
|
|
|
|
|
|
50
|
92
|
50
|
|
|
|
173
|
if ($] < 5.006) { |
51
|
0
|
|
|
|
|
0
|
my $class = shift; |
52
|
2
|
|
|
2
|
|
443
|
no strict 'refs'; |
|
2
|
|
|
|
|
3
|
|
|
2
|
|
|
|
|
13399
|
|
53
|
0
|
|
|
|
|
0
|
$self = bless [\%{"$class\::FIELDS"}], $class; |
|
0
|
|
|
|
|
0
|
|
54
|
|
|
|
|
|
|
} else { |
55
|
92
|
|
|
|
|
101
|
$self = shift; |
56
|
92
|
50
|
|
|
|
348
|
$self = fields::new($self) unless ref $self; |
57
|
|
|
|
|
|
|
} |
58
|
|
|
|
|
|
|
|
59
|
92
|
|
|
|
|
13304
|
my $data = shift; |
60
|
92
|
|
|
|
|
196
|
$self->data($data); |
61
|
|
|
|
|
|
|
|
62
|
92
|
|
|
|
|
195
|
$self->{Subtrees} = []; |
63
|
92
|
|
|
|
|
149
|
$self->{Parent} = undef; |
64
|
92
|
|
|
|
|
133
|
$self->{Modified} = 0; |
65
|
92
|
|
|
|
|
139
|
$self->{Separator} = "/"; |
66
|
|
|
|
|
|
|
|
67
|
92
|
|
|
|
|
350
|
$self; |
68
|
|
|
|
|
|
|
} |
69
|
|
|
|
|
|
|
|
70
|
|
|
|
|
|
|
sub maybe_construct { |
71
|
0
|
|
|
0
|
0
|
0
|
my $self = shift; |
72
|
0
|
|
|
|
|
0
|
my $obj = shift; |
73
|
0
|
0
|
|
|
|
0
|
if (UNIVERSAL::isa($obj, __PACKAGE__)) { |
74
|
0
|
|
|
|
|
0
|
$obj; |
75
|
|
|
|
|
|
|
} else { |
76
|
0
|
|
|
|
|
0
|
$self->new($obj); |
77
|
|
|
|
|
|
|
} |
78
|
|
|
|
|
|
|
} |
79
|
|
|
|
|
|
|
|
80
|
|
|
|
|
|
|
sub data { |
81
|
624
|
|
|
624
|
0
|
1286
|
my $self = shift; |
82
|
|
|
|
|
|
|
|
83
|
624
|
100
|
|
|
|
3409
|
if (@_) { |
84
|
92
|
|
|
|
|
123
|
my $data = shift; |
85
|
|
|
|
|
|
|
|
86
|
92
|
|
|
|
|
194
|
$self->{Data} = $data; |
87
|
92
|
50
|
66
|
|
|
605
|
if (ref $data && UNIVERSAL::can($data,"id")) { |
|
|
100
|
66
|
|
|
|
|
|
|
50
|
66
|
|
|
|
|
88
|
0
|
|
|
|
|
0
|
$self->{Id} = $data->id; |
89
|
|
|
|
|
|
|
} elsif (ref $data && UNIVERSAL::isa($data, "HASH") && exists $data->{Id}) { |
90
|
12
|
|
|
|
|
37
|
$self->{Id} = $data->{Id}; |
91
|
|
|
|
|
|
|
} elsif (defined $data) { |
92
|
80
|
|
|
|
|
203
|
$self->{Id} = $data; |
93
|
|
|
|
|
|
|
} else { |
94
|
0
|
|
|
|
|
0
|
die "No id found"; |
95
|
|
|
|
|
|
|
} |
96
|
|
|
|
|
|
|
} |
97
|
|
|
|
|
|
|
|
98
|
624
|
|
|
|
|
2387
|
$self->{Data}; |
99
|
|
|
|
|
|
|
} |
100
|
|
|
|
|
|
|
|
101
|
0
|
|
|
0
|
0
|
0
|
sub id { $_[0]->{Id} } |
102
|
|
|
|
|
|
|
|
103
|
|
|
|
|
|
|
# XXX setting of parent is not used for external use ... |
104
|
|
|
|
|
|
|
# use subtree (for the other direction) instead |
105
|
|
|
|
|
|
|
sub parent { |
106
|
663
|
|
|
663
|
0
|
1139
|
my($self, $parent) = @_; |
107
|
663
|
100
|
|
|
|
1066
|
if (defined $parent) { |
108
|
80
|
|
|
|
|
109
|
$self->{Parent} = $parent; |
109
|
80
|
|
|
|
|
153
|
$self->modified(1); |
110
|
|
|
|
|
|
|
} else { |
111
|
583
|
|
|
|
|
1481
|
$self->{Parent}; |
112
|
|
|
|
|
|
|
} |
113
|
|
|
|
|
|
|
} |
114
|
|
|
|
|
|
|
|
115
|
|
|
|
|
|
|
=head2 reparent |
116
|
|
|
|
|
|
|
|
117
|
|
|
|
|
|
|
$tree->reparent($newparent) |
118
|
|
|
|
|
|
|
|
119
|
|
|
|
|
|
|
Use this method only if there is already a parent. Otherwise, use the |
120
|
|
|
|
|
|
|
parent method. |
121
|
|
|
|
|
|
|
|
122
|
|
|
|
|
|
|
=cut |
123
|
|
|
|
|
|
|
|
124
|
|
|
|
|
|
|
sub reparent { |
125
|
0
|
|
|
0
|
1
|
0
|
my($self, $newparent) = @_; |
126
|
0
|
|
|
|
|
0
|
my $oldparent = $self->parent; |
127
|
|
|
|
|
|
|
# don't become a child of a descended tree :-) |
128
|
0
|
0
|
|
|
|
0
|
return if $self->is_descendent($newparent); |
129
|
0
|
0
|
|
|
|
0
|
return if !$oldparent; # don't reparent root |
130
|
0
|
|
|
|
|
0
|
$oldparent->delete_subtree($self); |
131
|
0
|
|
|
|
|
0
|
$newparent->subtree($self); |
132
|
|
|
|
|
|
|
} |
133
|
|
|
|
|
|
|
|
134
|
|
|
|
|
|
|
=head2 root |
135
|
|
|
|
|
|
|
|
136
|
|
|
|
|
|
|
$root = $tree->root; |
137
|
|
|
|
|
|
|
|
138
|
|
|
|
|
|
|
Return root node of the given $tree. |
139
|
|
|
|
|
|
|
|
140
|
|
|
|
|
|
|
=cut |
141
|
|
|
|
|
|
|
|
142
|
|
|
|
|
|
|
sub root { |
143
|
344
|
|
|
344
|
1
|
371
|
my $self = shift; |
144
|
344
|
100
|
|
|
|
577
|
if ($self->parent) { |
145
|
184
|
|
|
|
|
313
|
$self->parent->root; |
146
|
|
|
|
|
|
|
} else { |
147
|
160
|
|
|
|
|
313
|
$self; |
148
|
|
|
|
|
|
|
} |
149
|
|
|
|
|
|
|
} |
150
|
|
|
|
|
|
|
|
151
|
|
|
|
|
|
|
=head2 modified |
152
|
|
|
|
|
|
|
|
153
|
|
|
|
|
|
|
$modfied = $tree->modified |
154
|
|
|
|
|
|
|
|
155
|
|
|
|
|
|
|
Return true if the tree is modified, that is, one of root's #' |
156
|
|
|
|
|
|
|
subtrees are modified. |
157
|
|
|
|
|
|
|
|
158
|
|
|
|
|
|
|
$tree->modified($modified) |
159
|
|
|
|
|
|
|
|
160
|
|
|
|
|
|
|
Set the modified attribute (0 or 1) for the root tree. |
161
|
|
|
|
|
|
|
|
162
|
|
|
|
|
|
|
=cut |
163
|
|
|
|
|
|
|
|
164
|
|
|
|
|
|
|
sub modified { |
165
|
160
|
|
|
160
|
1
|
187
|
my($self, $flag) = @_; |
166
|
160
|
|
|
|
|
251
|
my $root = $self->root; |
167
|
160
|
50
|
|
|
|
283
|
if (defined $flag) { |
168
|
160
|
50
|
|
|
|
401
|
$root->{Modified} = ($flag ? 1 : 0); |
169
|
|
|
|
|
|
|
} else { |
170
|
0
|
|
|
|
|
0
|
$root->{Modified}; |
171
|
|
|
|
|
|
|
} |
172
|
|
|
|
|
|
|
} |
173
|
|
|
|
|
|
|
|
174
|
|
|
|
|
|
|
=head2 subtree |
175
|
|
|
|
|
|
|
|
176
|
|
|
|
|
|
|
$root->subtree([$tree1, ...]); |
177
|
|
|
|
|
|
|
|
178
|
|
|
|
|
|
|
With a $tree defined, put the trees as subtrees of $root. Without |
179
|
|
|
|
|
|
|
$tree, return either an array of subtrees (in array context) or a |
180
|
|
|
|
|
|
|
reference to the array of subtrees (in scalar context). |
181
|
|
|
|
|
|
|
|
182
|
|
|
|
|
|
|
The argument can be either GenericTree objects or another scalars, in |
183
|
|
|
|
|
|
|
which case they will be used as the data argument to the constructor |
184
|
|
|
|
|
|
|
of GenericTree. |
185
|
|
|
|
|
|
|
|
186
|
|
|
|
|
|
|
Alias: children. |
187
|
|
|
|
|
|
|
|
188
|
|
|
|
|
|
|
=cut |
189
|
|
|
|
|
|
|
|
190
|
|
|
|
|
|
|
sub subtree { |
191
|
543
|
|
|
543
|
1
|
634
|
my $self = shift; |
192
|
543
|
100
|
|
|
|
927
|
if (@_) { |
193
|
80
|
|
|
|
|
86
|
my @res; |
194
|
80
|
|
|
|
|
111
|
my $class = ref $self; |
195
|
80
|
|
|
|
|
218
|
foreach my $subtree (@_) { |
196
|
80
|
|
|
|
|
81
|
my WE::Util::GenericTree $sub; |
197
|
80
|
50
|
33
|
|
|
210
|
if (ref $subtree && UNIVERSAL::isa($subtree, __PACKAGE__)) { |
198
|
0
|
|
|
|
|
0
|
$sub = $subtree; |
199
|
|
|
|
|
|
|
} else { |
200
|
80
|
|
|
|
|
158
|
$sub = $class->new($subtree); |
201
|
|
|
|
|
|
|
} |
202
|
80
|
|
|
|
|
157
|
$sub->parent($self); |
203
|
80
|
|
|
|
|
87
|
push @{ $self->{Subtrees} }, $sub; |
|
80
|
|
|
|
|
157
|
|
204
|
80
|
|
|
|
|
160
|
$self->modified(1); |
205
|
80
|
|
|
|
|
203
|
push @res, $sub; |
206
|
|
|
|
|
|
|
} |
207
|
80
|
50
|
|
|
|
323
|
wantarray ? @res : $res[0]; |
208
|
|
|
|
|
|
|
} else { |
209
|
463
|
100
|
|
|
|
1252
|
wantarray ? @{ $self->{Subtrees} } : $self->{Subtrees}; |
|
264
|
|
|
|
|
995
|
|
210
|
|
|
|
|
|
|
} |
211
|
|
|
|
|
|
|
} |
212
|
|
|
|
|
|
|
|
213
|
|
|
|
|
|
|
*children = \&subtree; |
214
|
|
|
|
|
|
|
|
215
|
|
|
|
|
|
|
sub is_descendent { |
216
|
0
|
|
|
0
|
0
|
|
my($self, $tree) = @_; |
217
|
0
|
0
|
|
|
|
|
return 1 if $self eq $tree; |
218
|
0
|
|
|
|
|
|
foreach ($self->subtree) { |
219
|
0
|
|
|
|
|
|
my $r = $_->is_descendent($tree); |
220
|
0
|
0
|
|
|
|
|
return 1 if $r; |
221
|
|
|
|
|
|
|
} |
222
|
0
|
|
|
|
|
|
0; |
223
|
|
|
|
|
|
|
} |
224
|
|
|
|
|
|
|
|
225
|
|
|
|
|
|
|
sub delete_subtree { |
226
|
0
|
|
|
0
|
0
|
|
my($self, $subp) = @_; |
227
|
0
|
|
|
|
|
|
my @subtrees = $self->subtree; |
228
|
0
|
|
|
|
|
|
my @newsubtrees; |
229
|
0
|
|
|
|
|
|
foreach (@subtrees) { |
230
|
0
|
0
|
|
|
|
|
push @newsubtrees, $_ unless $_ eq $subp; |
231
|
|
|
|
|
|
|
} |
232
|
0
|
|
|
|
|
|
$self->{Subtrees} = \@newsubtrees; |
233
|
0
|
|
|
|
|
|
$self->modified(1); |
234
|
|
|
|
|
|
|
} |
235
|
|
|
|
|
|
|
|
236
|
|
|
|
|
|
|
=head2 find_by_pathname |
237
|
|
|
|
|
|
|
|
238
|
|
|
|
|
|
|
$tree = $root->find_by_pathname($pathname); |
239
|
|
|
|
|
|
|
|
240
|
|
|
|
|
|
|
Search and return the corresponding $tree (or undef if no such |
241
|
|
|
|
|
|
|
tree exists) for the given $pathname. |
242
|
|
|
|
|
|
|
|
243
|
|
|
|
|
|
|
=cut |
244
|
|
|
|
|
|
|
|
245
|
|
|
|
|
|
|
sub find_by_pathname { |
246
|
0
|
|
|
0
|
1
|
|
my($self, $pathname) = @_; |
247
|
0
|
0
|
|
|
|
|
return $self if $self->pathname eq $pathname; |
248
|
0
|
|
|
|
|
|
foreach ($self->subtree) { |
249
|
0
|
|
|
|
|
|
my $r = $_->find_by_pathname($pathname); |
250
|
0
|
0
|
|
|
|
|
return $r if defined $r; |
251
|
|
|
|
|
|
|
} |
252
|
0
|
|
|
|
|
|
return undef; |
253
|
|
|
|
|
|
|
} |
254
|
|
|
|
|
|
|
|
255
|
|
|
|
|
|
|
sub pathname { # virtual pathname! |
256
|
0
|
|
|
0
|
0
|
|
my($self, $separator) = @_; |
257
|
0
|
0
|
|
|
|
|
$separator = $self->separator if !defined $separator; |
258
|
0
|
|
|
|
|
|
my @path = $self->path; |
259
|
0
|
0
|
0
|
|
|
|
if (!defined $path[0] || $path[0] eq '') { |
260
|
0
|
|
|
|
|
|
shift @path; |
261
|
|
|
|
|
|
|
} |
262
|
0
|
|
|
|
|
|
join($separator, @path); |
263
|
|
|
|
|
|
|
} |
264
|
|
|
|
|
|
|
|
265
|
|
|
|
|
|
|
sub path { |
266
|
0
|
|
|
0
|
0
|
|
my($self) = @_; |
267
|
0
|
|
|
|
|
|
my @path; |
268
|
0
|
0
|
|
|
|
|
if (!defined $self->parent) { |
269
|
0
|
|
|
|
|
|
@path = ($self->id); |
270
|
|
|
|
|
|
|
} else { |
271
|
0
|
|
|
|
|
|
@path = ($self->parent->path, $self->id); |
272
|
|
|
|
|
|
|
} |
273
|
0
|
0
|
|
|
|
|
wantarray ? @path : \@path; |
274
|
|
|
|
|
|
|
} |
275
|
|
|
|
|
|
|
|
276
|
|
|
|
|
|
|
=head2 separator |
277
|
|
|
|
|
|
|
|
278
|
|
|
|
|
|
|
$separator = $tree->separator |
279
|
|
|
|
|
|
|
|
280
|
|
|
|
|
|
|
Return the separator for this tree. Defaults to /. |
281
|
|
|
|
|
|
|
|
282
|
|
|
|
|
|
|
$project->separator($separator); |
283
|
|
|
|
|
|
|
|
284
|
|
|
|
|
|
|
Set the separator for this tree to $separator. |
285
|
|
|
|
|
|
|
|
286
|
|
|
|
|
|
|
=cut |
287
|
|
|
|
|
|
|
|
288
|
|
|
|
|
|
|
sub separator { |
289
|
0
|
|
|
0
|
1
|
|
my($self, $separator) = @_; |
290
|
0
|
|
|
|
|
|
my $root = $self->root; |
291
|
0
|
0
|
|
|
|
|
if (defined $separator) { |
292
|
0
|
|
|
|
|
|
$root->{Separator} = $separator; |
293
|
|
|
|
|
|
|
} else { |
294
|
0
|
|
|
|
|
|
$root->{Separator}; |
295
|
|
|
|
|
|
|
} |
296
|
|
|
|
|
|
|
} |
297
|
|
|
|
|
|
|
|
298
|
|
|
|
|
|
|
sub level { |
299
|
0
|
|
|
0
|
0
|
|
my $self = shift; |
300
|
0
|
0
|
|
|
|
|
if (!defined $self->{Parent}) { |
301
|
0
|
|
|
|
|
|
0; |
302
|
|
|
|
|
|
|
} else { |
303
|
0
|
|
|
|
|
|
$self->{Parent}->level + 1; |
304
|
|
|
|
|
|
|
} |
305
|
|
|
|
|
|
|
} |
306
|
|
|
|
|
|
|
|
307
|
|
|
|
|
|
|
sub insert_tree { |
308
|
0
|
|
|
0
|
0
|
|
my($self, $obj, $type, $pathname) = @_; |
309
|
0
|
|
|
|
|
|
my $tree = $self->find_by_pathname($pathname); |
310
|
0
|
0
|
|
|
|
|
if (defined $tree) { |
311
|
0
|
0
|
|
|
|
|
if ($type eq '-below') { |
312
|
0
|
|
|
|
|
|
$tree->subtree($obj); |
313
|
|
|
|
|
|
|
} else { |
314
|
0
|
|
|
|
|
|
my $parent = $tree->parent; |
315
|
0
|
0
|
|
|
|
|
die "Can't find parent for $tree" unless $parent; |
316
|
|
|
|
|
|
|
|
317
|
0
|
|
|
|
|
|
my $i = 0; |
318
|
0
|
|
|
|
|
|
SEARCH: { |
319
|
0
|
|
|
|
|
|
foreach my $sub (@{ $parent->{Subtrees} }) { |
|
0
|
|
|
|
|
|
|
320
|
0
|
0
|
|
|
|
|
if ($sub eq $tree) { |
321
|
0
|
|
|
|
|
|
last SEARCH; |
322
|
|
|
|
|
|
|
} |
323
|
0
|
|
|
|
|
|
$i++; |
324
|
|
|
|
|
|
|
} |
325
|
0
|
|
|
|
|
|
die "Fatal: $tree not found in $parent"; |
326
|
|
|
|
|
|
|
} |
327
|
|
|
|
|
|
|
|
328
|
0
|
|
|
|
|
|
my $new_obj = $self->maybe_construct($obj); |
329
|
|
|
|
|
|
|
|
330
|
0
|
0
|
|
|
|
|
if ($type eq '-at') { |
|
|
0
|
|
|
|
|
|
|
|
0
|
|
|
|
|
|
331
|
0
|
|
|
|
|
|
$parent->{Subtrees}[$i] = $new_obj; |
332
|
|
|
|
|
|
|
} elsif ($type eq '-after') { |
333
|
0
|
|
|
|
|
|
splice @{ $parent->{Subtrees} }, $i, 0, $new_obj; |
|
0
|
|
|
|
|
|
|
334
|
|
|
|
|
|
|
} elsif ($type eq '-before') { |
335
|
0
|
|
|
|
|
|
splice @{ $parent->{Subtrees} }, $i-1, 0, $new_obj; |
|
0
|
|
|
|
|
|
|
336
|
|
|
|
|
|
|
} else { |
337
|
0
|
|
|
|
|
|
die "Invalid type $type"; |
338
|
|
|
|
|
|
|
} |
339
|
|
|
|
|
|
|
} |
340
|
|
|
|
|
|
|
} else { |
341
|
0
|
|
|
|
|
|
die "Can't find pathname $pathname"; |
342
|
|
|
|
|
|
|
} |
343
|
|
|
|
|
|
|
} |
344
|
|
|
|
|
|
|
|
345
|
|
|
|
|
|
|
1; |
346
|
|
|
|
|
|
|
|
347
|
|
|
|
|
|
|
__END__ |