line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
package Set::Groups ; |
2
|
|
|
|
|
|
|
|
3
|
|
|
|
|
|
|
# ====================== |
4
|
|
|
|
|
|
|
# |
5
|
|
|
|
|
|
|
# Jacquelin Charbonnel - CNRS/LAREMA |
6
|
|
|
|
|
|
|
# |
7
|
|
|
|
|
|
|
# $Id: Groups.pm 22 2007-11-06 20:58:14Z jaclin $ |
8
|
|
|
|
|
|
|
# |
9
|
|
|
|
|
|
|
# ---- |
10
|
|
|
|
|
|
|
# |
11
|
|
|
|
|
|
|
# A set of groups. |
12
|
|
|
|
|
|
|
# Each group can own single members and group members. |
13
|
|
|
|
|
|
|
# A group can be flattened, i.e. expansed until each of his members is a single one. |
14
|
|
|
|
|
|
|
# |
15
|
|
|
|
|
|
|
# ---- |
16
|
|
|
|
|
|
|
# $LastChangedDate: 2007-11-06 21:58:14 +0100 (Tue, 06 Nov 2007) $ |
17
|
|
|
|
|
|
|
# $LastChangedRevision: 22 $ |
18
|
|
|
|
|
|
|
# $LastChangedBy: jaclin $ |
19
|
|
|
|
|
|
|
# $URL: https://svn.math/system-tools/trunk/Set-Groups/Groups.pm $ |
20
|
|
|
|
|
|
|
# |
21
|
|
|
|
|
|
|
# ====================== |
22
|
|
|
|
|
|
|
|
23
|
|
|
|
|
|
|
require Exporter ; |
24
|
|
|
|
|
|
|
@ISA = qw(Exporter); |
25
|
|
|
|
|
|
|
@EXPORT=qw() ; |
26
|
|
|
|
|
|
|
@EXPORT_OK = qw( ); |
27
|
|
|
|
|
|
|
|
28
|
1
|
|
|
1
|
|
23167
|
use 5.006; |
|
1
|
|
|
|
|
4
|
|
|
1
|
|
|
|
|
39
|
|
29
|
1
|
|
|
1
|
|
5
|
use Carp; |
|
1
|
|
|
|
|
3
|
|
|
1
|
|
|
|
|
68
|
|
30
|
1
|
|
|
1
|
|
5
|
use warnings; |
|
1
|
|
|
|
|
6
|
|
|
1
|
|
|
|
|
28
|
|
31
|
1
|
|
|
1
|
|
4
|
use strict; |
|
1
|
|
|
|
|
2
|
|
|
1
|
|
|
|
|
2332
|
|
32
|
|
|
|
|
|
|
|
33
|
|
|
|
|
|
|
our $VERSION = 0.8 ; # $LastChangedRevision: 22 $ |
34
|
|
|
|
|
|
|
my $hfmt = "Set::Groups: HORROR: group '%s' is cyclic, the walk is infinite... Bye" ; |
35
|
|
|
|
|
|
|
|
36
|
|
|
|
|
|
|
sub new() |
37
|
|
|
|
|
|
|
{ |
38
|
0
|
|
|
0
|
1
|
|
my ($type) = @_ ; |
39
|
0
|
|
|
|
|
|
my $this = { |
40
|
|
|
|
|
|
|
"group" => {} |
41
|
|
|
|
|
|
|
, "debug" => 0 |
42
|
|
|
|
|
|
|
} ; |
43
|
|
|
|
|
|
|
|
44
|
0
|
|
|
|
|
|
bless $this,$type ; |
45
|
0
|
|
|
|
|
|
return $this ; |
46
|
|
|
|
|
|
|
} |
47
|
|
|
|
|
|
|
|
48
|
|
|
|
|
|
|
sub setDebug($) |
49
|
|
|
|
|
|
|
{ |
50
|
0
|
|
|
0
|
1
|
|
my ($this,$level) = @_ ; |
51
|
0
|
|
|
|
|
|
$this->{"debug"} = $level ; |
52
|
|
|
|
|
|
|
} |
53
|
|
|
|
|
|
|
|
54
|
|
|
|
|
|
|
# ----------------- |
55
|
|
|
|
|
|
|
# Set management |
56
|
|
|
|
|
|
|
# ----------------- |
57
|
|
|
|
|
|
|
|
58
|
|
|
|
|
|
|
sub newGroup($) |
59
|
|
|
|
|
|
|
{ |
60
|
0
|
|
|
0
|
1
|
|
my ($this,$group) = @_ ; |
61
|
|
|
|
|
|
|
|
62
|
0
|
0
|
|
|
|
|
if (exists $this->{"group"}{$group}) |
63
|
|
|
|
|
|
|
{ |
64
|
0
|
|
|
|
|
|
return 0 ; |
65
|
|
|
|
|
|
|
} |
66
|
|
|
|
|
|
|
else |
67
|
|
|
|
|
|
|
{ |
68
|
0
|
|
|
|
|
|
$this->{"group"}{$group} = {} ; |
69
|
0
|
0
|
|
|
|
|
delete $this->{"partition"} if exists $this->{"partition"} ; |
70
|
0
|
|
|
|
|
|
return 1 ; |
71
|
|
|
|
|
|
|
} |
72
|
|
|
|
|
|
|
} |
73
|
|
|
|
|
|
|
|
74
|
|
|
|
|
|
|
sub deleteGroup($) |
75
|
|
|
|
|
|
|
{ |
76
|
0
|
|
|
0
|
1
|
|
my ($this,$group) = @_ ; |
77
|
|
|
|
|
|
|
|
78
|
0
|
0
|
|
|
|
|
if (exists $this->{"group"}{$group}) |
79
|
|
|
|
|
|
|
{ |
80
|
0
|
|
|
|
|
|
delete $this->{"group"}{$group} ; |
81
|
0
|
0
|
|
|
|
|
delete $this->{"partition"} if exists $this->{"partition"} ; |
82
|
0
|
|
|
|
|
|
return 1 ; |
83
|
|
|
|
|
|
|
} |
84
|
|
|
|
|
|
|
else |
85
|
|
|
|
|
|
|
{ |
86
|
0
|
|
|
|
|
|
return 0 ; |
87
|
|
|
|
|
|
|
} |
88
|
|
|
|
|
|
|
} |
89
|
|
|
|
|
|
|
|
90
|
|
|
|
|
|
|
sub getGroups() |
91
|
|
|
|
|
|
|
{ |
92
|
0
|
|
|
0
|
1
|
|
my ($this) = @_ ; |
93
|
0
|
|
|
|
|
|
return keys %{$this->{"group"}} ; |
|
0
|
|
|
|
|
|
|
94
|
|
|
|
|
|
|
} |
95
|
|
|
|
|
|
|
|
96
|
|
|
|
|
|
|
sub getCyclicGroups |
97
|
|
|
|
|
|
|
{ |
98
|
0
|
|
|
0
|
1
|
|
my($this) = @_ ; |
99
|
|
|
|
|
|
|
|
100
|
0
|
0
|
|
|
|
|
$this->_walk() unless exists $this->{"partition"} ; |
101
|
0
|
|
|
|
|
|
return keys(%{$this->{"partition"}{"cyclic"}}) ; |
|
0
|
|
|
|
|
|
|
102
|
|
|
|
|
|
|
} |
103
|
|
|
|
|
|
|
|
104
|
|
|
|
|
|
|
sub getAcyclicGroups |
105
|
|
|
|
|
|
|
{ |
106
|
0
|
|
|
0
|
1
|
|
my($this) = @_ ; |
107
|
|
|
|
|
|
|
|
108
|
0
|
0
|
|
|
|
|
$this->_walk() unless exists $this->{"partition"} ; |
109
|
0
|
|
|
|
|
|
return keys(%{$this->{"partition"}{"acyclic"}}) ; |
|
0
|
|
|
|
|
|
|
110
|
|
|
|
|
|
|
} |
111
|
|
|
|
|
|
|
|
112
|
|
|
|
|
|
|
sub hasGroup($) |
113
|
|
|
|
|
|
|
{ |
114
|
0
|
|
|
0
|
1
|
|
my($this,$group) = @_ ; |
115
|
0
|
|
|
|
|
|
return exists $this->{"group"}{$group} ; |
116
|
|
|
|
|
|
|
} |
117
|
|
|
|
|
|
|
|
118
|
|
|
|
|
|
|
# ----------------- |
119
|
|
|
|
|
|
|
# Group management |
120
|
|
|
|
|
|
|
# ----------------- |
121
|
|
|
|
|
|
|
|
122
|
|
|
|
|
|
|
sub addSingleTo($$) |
123
|
|
|
|
|
|
|
{ |
124
|
0
|
|
|
0
|
1
|
|
my ($this,$single,$group) = @_ ; |
125
|
|
|
|
|
|
|
|
126
|
0
|
0
|
|
|
|
|
warn "Set::Groups: NOTICE: 'addSingleTo' is deprecated, use 'addOwnSingleTo' instead" if $this->{"debug"}>0 ; |
127
|
0
|
|
|
|
|
|
return $this->addOwnSingleTo($single,$group) ; |
128
|
|
|
|
|
|
|
} |
129
|
|
|
|
|
|
|
|
130
|
|
|
|
|
|
|
sub addOwnSingleTo($$) |
131
|
|
|
|
|
|
|
{ |
132
|
0
|
|
|
0
|
1
|
|
my ($this,$single,$group) = @_ ; |
133
|
|
|
|
|
|
|
|
134
|
0
|
0
|
|
|
|
|
return 0 if exists $this->{"group"}{$group}{"single"}{$single} ; |
135
|
0
|
|
|
|
|
|
$this->{"group"}{$group}{"single"}{$single} = 1 ; |
136
|
0
|
|
|
|
|
|
return 1 ; |
137
|
|
|
|
|
|
|
} |
138
|
|
|
|
|
|
|
|
139
|
|
|
|
|
|
|
sub addGroupTo($$) |
140
|
|
|
|
|
|
|
{ |
141
|
0
|
|
|
0
|
1
|
|
my ($this,$mgroup,$group) = @_ ; |
142
|
|
|
|
|
|
|
|
143
|
0
|
0
|
|
|
|
|
warn "Set::Groups: NOTICE: 'addGroupTo' is deprecated, use 'addOwnGroupTo' instead" if $this->{"debug"}>0 ; |
144
|
0
|
|
|
|
|
|
return $this->addOwnGroupTo($mgroup,$group) ; |
145
|
|
|
|
|
|
|
} |
146
|
|
|
|
|
|
|
|
147
|
|
|
|
|
|
|
sub addOwnGroupTo($$) |
148
|
|
|
|
|
|
|
{ |
149
|
0
|
|
|
0
|
1
|
|
my ($this,$mgroup,$group) = @_ ; |
150
|
|
|
|
|
|
|
|
151
|
0
|
0
|
|
|
|
|
return 0 if exists $this->{"group"}{$group}{"group"}{$mgroup} ; |
152
|
0
|
0
|
|
|
|
|
$this->{"group"}{$mgroup} = {} unless (exists $this->{"group"}{$mgroup}) ; |
153
|
0
|
|
|
|
|
|
$this->{"group"}{$group}{"group"}{$mgroup} = 2 ; |
154
|
0
|
0
|
|
|
|
|
delete $this->{"partition"} if exists $this->{"partition"} ; |
155
|
0
|
|
|
|
|
|
return 1 ; |
156
|
|
|
|
|
|
|
} |
157
|
|
|
|
|
|
|
|
158
|
|
|
|
|
|
|
sub removeSingleFrom($$) |
159
|
|
|
|
|
|
|
{ |
160
|
0
|
|
|
0
|
1
|
|
my ($this,$single,$group) = @_ ; |
161
|
|
|
|
|
|
|
|
162
|
0
|
0
|
|
|
|
|
warn "Set::Groups: NOTICE: 'removeSingleFrom' is deprecated, use 'removeOwnSingleFrom' instead" if $this->{"debug"}>0 ; |
163
|
0
|
|
|
|
|
|
return $this->removeOwnSingleFrom($single,$group) ; |
164
|
|
|
|
|
|
|
} |
165
|
|
|
|
|
|
|
|
166
|
|
|
|
|
|
|
sub removeOwnSingleFrom($$) |
167
|
|
|
|
|
|
|
{ |
168
|
0
|
|
|
0
|
1
|
|
my ($this,$single,$group) = @_ ; |
169
|
|
|
|
|
|
|
|
170
|
0
|
0
|
|
|
|
|
if ($this->isSingleOf($single,$group)) |
171
|
|
|
|
|
|
|
{ |
172
|
0
|
|
|
|
|
|
delete $this->{"group"}{$group}{"single"}{$single} ; |
173
|
0
|
|
|
|
|
|
return 1 ; |
174
|
|
|
|
|
|
|
} |
175
|
0
|
|
|
|
|
|
else { return 0 ; } |
176
|
|
|
|
|
|
|
} |
177
|
|
|
|
|
|
|
|
178
|
|
|
|
|
|
|
sub removeGroupFrom($$) |
179
|
|
|
|
|
|
|
{ |
180
|
0
|
|
|
0
|
1
|
|
my ($this,$sub,$group) = @_ ; |
181
|
|
|
|
|
|
|
|
182
|
0
|
0
|
|
|
|
|
warn "Set::Groups: NOTICE: 'removeGroupFrom' is deprecated, use 'removeOwnGroupFrom' instead" if $this->{"debug"}>0 ; |
183
|
0
|
|
|
|
|
|
return $this->removeOwnGroupFrom($sub,$group) ; |
184
|
|
|
|
|
|
|
} |
185
|
|
|
|
|
|
|
|
186
|
|
|
|
|
|
|
sub removeOwnGroupFrom($$) |
187
|
|
|
|
|
|
|
{ |
188
|
0
|
|
|
0
|
1
|
|
my ($this,$sub,$group) = @_ ; |
189
|
|
|
|
|
|
|
|
190
|
0
|
0
|
|
|
|
|
if ($this->isGroupOf($sub,$group)) |
191
|
|
|
|
|
|
|
{ |
192
|
0
|
|
|
|
|
|
delete $this->{"group"}{$group}{"group"}{$sub} ; |
193
|
0
|
0
|
|
|
|
|
delete $this->{"partition"} if exists $this->{"partition"} ; |
194
|
0
|
|
|
|
|
|
return 1 ; |
195
|
|
|
|
|
|
|
} |
196
|
0
|
|
|
|
|
|
else { return 0 ; } |
197
|
|
|
|
|
|
|
} |
198
|
|
|
|
|
|
|
|
199
|
|
|
|
|
|
|
# This function performs a total walk, if needeed |
200
|
|
|
|
|
|
|
# At exit, the partition is always complete |
201
|
|
|
|
|
|
|
sub isAcyclic |
202
|
|
|
|
|
|
|
{ |
203
|
0
|
|
|
0
|
1
|
|
my ($this,$group) = @_ ; |
204
|
|
|
|
|
|
|
|
205
|
0
|
0
|
|
|
|
|
$this->_walk() unless exists($this->{"partition"}) ; |
206
|
0
|
|
|
|
|
|
return exists($this->{"partition"}{"acyclic"}{$group}) ; |
207
|
|
|
|
|
|
|
} |
208
|
|
|
|
|
|
|
|
209
|
|
|
|
|
|
|
sub isOwnSingleOf($$) |
210
|
|
|
|
|
|
|
{ |
211
|
0
|
|
|
0
|
1
|
|
my ($this,$candidate,$group) = @_ ; |
212
|
0
|
|
|
|
|
|
return exists $this->{"group"}{$group}{"single"}{$candidate} ; |
213
|
|
|
|
|
|
|
} |
214
|
|
|
|
|
|
|
|
215
|
|
|
|
|
|
|
sub isOwnGroupOf($$) |
216
|
|
|
|
|
|
|
{ |
217
|
0
|
|
|
0
|
1
|
|
my ($this,$candidate,$group) = @_ ; |
218
|
0
|
|
|
|
|
|
return exists $this->{"group"}{$group}{"group"}{$candidate} ; |
219
|
|
|
|
|
|
|
} |
220
|
|
|
|
|
|
|
|
221
|
|
|
|
|
|
|
sub isSingleOf($$) |
222
|
|
|
|
|
|
|
{ |
223
|
0
|
|
|
0
|
1
|
|
my ($this,$candidate,$group) = @_ ; |
224
|
|
|
|
|
|
|
|
225
|
0
|
0
|
0
|
|
|
|
carp sprintf($hfmt,$group) if $this->{"debug"}>0 && !$this->isAcyclic($group) ; |
226
|
0
|
|
|
|
|
|
my %fs = $this->_flattenedSinglesOf($group) ; |
227
|
0
|
|
|
|
|
|
return exists $fs{$candidate} ; |
228
|
|
|
|
|
|
|
} |
229
|
|
|
|
|
|
|
|
230
|
|
|
|
|
|
|
sub isGroupOf($$) |
231
|
|
|
|
|
|
|
{ |
232
|
0
|
|
|
0
|
1
|
|
my ($this,$candidate,$group) = @_ ; |
233
|
|
|
|
|
|
|
|
234
|
0
|
0
|
0
|
|
|
|
carp sprintf($hfmt,$group) if $this->{"debug"}>0 && !$this->isAcyclic($group) ; |
235
|
0
|
|
|
|
|
|
my %fs = $this->_flattenedGroupsOf($group) ; |
236
|
0
|
|
|
|
|
|
return exists $fs{$candidate} ; |
237
|
|
|
|
|
|
|
} |
238
|
|
|
|
|
|
|
|
239
|
|
|
|
|
|
|
sub getOwnSinglesOf($) |
240
|
|
|
|
|
|
|
{ |
241
|
0
|
|
|
0
|
1
|
|
my ($this,$group) = @_ ; |
242
|
0
|
|
|
|
|
|
return keys %{$this->{"group"}{$group}{"single"}} ; |
|
0
|
|
|
|
|
|
|
243
|
|
|
|
|
|
|
} |
244
|
|
|
|
|
|
|
|
245
|
|
|
|
|
|
|
sub getOwnGroupsOf($) |
246
|
|
|
|
|
|
|
{ |
247
|
0
|
|
|
0
|
1
|
|
my ($this,$group) = @_ ; |
248
|
0
|
|
|
|
|
|
return keys %{$this->{"group"}{$group}{"group"}} ; |
|
0
|
|
|
|
|
|
|
249
|
|
|
|
|
|
|
} |
250
|
|
|
|
|
|
|
|
251
|
|
|
|
|
|
|
sub getSinglesOf($) |
252
|
|
|
|
|
|
|
{ |
253
|
0
|
|
|
0
|
1
|
|
my ($this,$group) = @_ ; |
254
|
|
|
|
|
|
|
|
255
|
0
|
0
|
0
|
|
|
|
carp sprintf($hfmt,$group) if $this->{"debug"}>0 && !$this->isAcyclic($group) ; |
256
|
0
|
|
|
|
|
|
my %h = $this->_flattenedSinglesOf($group) ; |
257
|
0
|
|
|
|
|
|
return keys %h ; |
258
|
|
|
|
|
|
|
} |
259
|
|
|
|
|
|
|
|
260
|
|
|
|
|
|
|
sub getGroupsOf($) |
261
|
|
|
|
|
|
|
{ |
262
|
0
|
|
|
0
|
1
|
|
my ($this,$group) = @_ ; |
263
|
|
|
|
|
|
|
|
264
|
0
|
0
|
0
|
|
|
|
carp sprintf($hfmt,$group) if $this->{"debug"}>0 && !$this->isAcyclic($group) ; |
265
|
0
|
|
|
|
|
|
my %h = $this->_flattenedGroupsOf($group) ; |
266
|
0
|
|
|
|
|
|
return keys %h ; |
267
|
|
|
|
|
|
|
} |
268
|
|
|
|
|
|
|
|
269
|
|
|
|
|
|
|
# ----------------- |
270
|
|
|
|
|
|
|
# private methods |
271
|
|
|
|
|
|
|
# ----------------- |
272
|
|
|
|
|
|
|
|
273
|
|
|
|
|
|
|
sub _flattenedSinglesOf() |
274
|
|
|
|
|
|
|
{ |
275
|
0
|
|
|
0
|
|
|
my ($this,$group) = @_ ; |
276
|
|
|
|
|
|
|
|
277
|
0
|
|
|
|
|
|
my %flat = () ; |
278
|
0
|
0
|
|
|
|
|
%flat = %{$this->{"group"}{$group}{"single"}} |
|
0
|
|
|
|
|
|
|
279
|
|
|
|
|
|
|
if exists $this->{"group"}{$group}{"single"} ; |
280
|
|
|
|
|
|
|
|
281
|
0
|
|
|
|
|
|
for my $k (keys %{$this->{"group"}{$group}{"group"}}) |
|
0
|
|
|
|
|
|
|
282
|
|
|
|
|
|
|
{ |
283
|
0
|
|
|
|
|
|
my %fs = $this->_flattenedSinglesOf($k) ; |
284
|
0
|
|
|
|
|
|
for my $kk (keys %fs) |
285
|
|
|
|
|
|
|
{ |
286
|
0
|
|
|
|
|
|
$flat{$kk} = 1 ; |
287
|
|
|
|
|
|
|
} |
288
|
|
|
|
|
|
|
} |
289
|
0
|
|
|
|
|
|
return %flat ; |
290
|
|
|
|
|
|
|
} |
291
|
|
|
|
|
|
|
|
292
|
|
|
|
|
|
|
sub _flattenedGroupsOf() |
293
|
|
|
|
|
|
|
{ |
294
|
0
|
|
|
0
|
|
|
my ($this,$group) = @_ ; |
295
|
|
|
|
|
|
|
|
296
|
0
|
|
|
|
|
|
my %flat = () ; |
297
|
0
|
|
|
|
|
|
for my $k (keys %{$this->{"group"}{$group}{"group"}}) |
|
0
|
|
|
|
|
|
|
298
|
|
|
|
|
|
|
{ |
299
|
0
|
|
|
|
|
|
$flat{$k} = 1 ; |
300
|
0
|
0
|
0
|
|
|
|
if (! exists $this->{"group"}{$k}{"group"} || scalar keys %{$this->{"group"}{$k}{"group"}}==0) |
|
0
|
|
|
|
|
|
|
301
|
|
|
|
|
|
|
{ |
302
|
|
|
|
|
|
|
} |
303
|
|
|
|
|
|
|
else |
304
|
|
|
|
|
|
|
{ |
305
|
0
|
|
|
|
|
|
my %fs = $this->_flattenedGroupsOf($k) ; |
306
|
0
|
|
|
|
|
|
for my $kk (keys %fs) |
307
|
|
|
|
|
|
|
{ |
308
|
0
|
|
|
|
|
|
$flat{$kk} = 1 ; |
309
|
|
|
|
|
|
|
} |
310
|
|
|
|
|
|
|
} |
311
|
|
|
|
|
|
|
} |
312
|
0
|
|
|
|
|
|
return %flat ; |
313
|
|
|
|
|
|
|
} |
314
|
|
|
|
|
|
|
|
315
|
|
|
|
|
|
|
# This function don't perform a total walk |
316
|
|
|
|
|
|
|
# At exit, the partition is incomplete |
317
|
|
|
|
|
|
|
sub _isAcyclic($$) |
318
|
|
|
|
|
|
|
{ |
319
|
0
|
|
|
0
|
|
|
my ($this,$group,$passed) = @_ ; |
320
|
|
|
|
|
|
|
|
321
|
0
|
0
|
|
|
|
|
if (exists $passed->{$group}) |
322
|
|
|
|
|
|
|
{ |
323
|
0
|
|
|
|
|
|
$this->{"partition"}{"cyclic"}{$group} = 1 ; |
324
|
0
|
|
|
|
|
|
return 0 ; |
325
|
|
|
|
|
|
|
} |
326
|
0
|
|
|
|
|
|
my %passed = ( %$passed, $group => 1 ) ; |
327
|
|
|
|
|
|
|
|
328
|
0
|
|
|
|
|
|
for my $k (keys %{$this->{"group"}{$group}{"group"}}) |
|
0
|
|
|
|
|
|
|
329
|
|
|
|
|
|
|
{ |
330
|
0
|
0
|
|
|
|
|
next if exists $this->{"partition"}{"acyclic"}{$k} ; |
331
|
0
|
0
|
|
|
|
|
if (exists $this->{"partition"}{"cyclic"}{$k}) |
332
|
|
|
|
|
|
|
{ |
333
|
0
|
|
|
|
|
|
$this->{"partition"}{"cyclic"}{$group} = 1 ; |
334
|
0
|
|
|
|
|
|
return 0 ; |
335
|
|
|
|
|
|
|
} |
336
|
0
|
0
|
|
|
|
|
if ($this->_isAcyclic($k,\%passed)==1) |
337
|
|
|
|
|
|
|
{ |
338
|
0
|
|
|
|
|
|
$this->{"partition"}{"acyclic"}{$k} = 1 ; |
339
|
|
|
|
|
|
|
} |
340
|
|
|
|
|
|
|
else |
341
|
|
|
|
|
|
|
{ |
342
|
0
|
|
|
|
|
|
$this->{"partition"}{"cyclic"}{$k} = 1 ; |
343
|
0
|
|
|
|
|
|
$this->{"partition"}{"cyclic"}{$group} = 1 ; |
344
|
0
|
|
|
|
|
|
return 0 ; |
345
|
|
|
|
|
|
|
} |
346
|
|
|
|
|
|
|
} |
347
|
0
|
|
|
|
|
|
$this->{"partition"}{"acyclic"}{$group} = 1 ; |
348
|
0
|
|
|
|
|
|
return 1 ; |
349
|
|
|
|
|
|
|
} |
350
|
|
|
|
|
|
|
|
351
|
|
|
|
|
|
|
# Perform an inconditionnal walk on the graph |
352
|
|
|
|
|
|
|
sub _walk() |
353
|
|
|
|
|
|
|
{ |
354
|
0
|
|
|
0
|
|
|
my ($this) = @_ ; |
355
|
|
|
|
|
|
|
|
356
|
0
|
0
|
|
|
|
|
carp "Set::Groups: DEBUG: walking on the graph to find cycles..." if $this->{"debug"}>0 ; |
357
|
0
|
0
|
|
|
|
|
delete $this->{"partition"} if exists $this->{"partition"} ; |
358
|
0
|
|
|
|
|
|
for my $group ($this->getGroups()) |
359
|
|
|
|
|
|
|
{ |
360
|
0
|
|
|
|
|
|
$this->_isAcyclic($group,{}) ; |
361
|
|
|
|
|
|
|
} |
362
|
|
|
|
|
|
|
} |
363
|
|
|
|
|
|
|
|
364
|
|
|
|
|
|
|
1; |
365
|
|
|
|
|
|
|
|
366
|
|
|
|
|
|
|
|
367
|
|
|
|
|
|
|
|
368
|
|
|
|
|
|
|
|
369
|
|
|
|
|
|
|
=head1 NAME |
370
|
|
|
|
|
|
|
|
371
|
|
|
|
|
|
|
Set::Groups - A set of groups. |
372
|
|
|
|
|
|
|
|
373
|
|
|
|
|
|
|
=head1 SYNOPSIS |
374
|
|
|
|
|
|
|
|
375
|
|
|
|
|
|
|
use Set::Groups ; |
376
|
|
|
|
|
|
|
|
377
|
|
|
|
|
|
|
# create a set of groups |
378
|
|
|
|
|
|
|
$groups = new Set::Groups ; |
379
|
|
|
|
|
|
|
|
380
|
|
|
|
|
|
|
# create a group MyGroup with a single member |
381
|
|
|
|
|
|
|
$groups->addOwnSingleTo("single1","MyGroup") ; |
382
|
|
|
|
|
|
|
|
383
|
|
|
|
|
|
|
# add a group member into MyGroup |
384
|
|
|
|
|
|
|
$groups->addOwnGroupTo("Member1Group","MyGroup") ; |
385
|
|
|
|
|
|
|
|
386
|
|
|
|
|
|
|
# add a single members into the previous member group |
387
|
|
|
|
|
|
|
$groups->addOwnSingleTo("single2","Member1Group") ; |
388
|
|
|
|
|
|
|
|
389
|
|
|
|
|
|
|
# add a group member into the previous member group |
390
|
|
|
|
|
|
|
$groups->addOwnGroupTo("Member2Group","Member1Group") ; |
391
|
|
|
|
|
|
|
|
392
|
|
|
|
|
|
|
# add a single members into the previous member group |
393
|
|
|
|
|
|
|
$groups->addOwnSingleTo("single3","Member2Group") ; |
394
|
|
|
|
|
|
|
|
395
|
|
|
|
|
|
|
# flatten the group MyGroup |
396
|
|
|
|
|
|
|
@singles = $groups->getSinglesOf("MyGroup") ; |
397
|
|
|
|
|
|
|
@groups = $groups->getGroupsOf("MyGroup") ; |
398
|
|
|
|
|
|
|
$present = $groups->isSingleOf("single3","MyGroup") ; |
399
|
|
|
|
|
|
|
$present = $groups->isGroupOf("Member2Group","MyGroup") ; |
400
|
|
|
|
|
|
|
|
401
|
|
|
|
|
|
|
=head1 DESCRIPTION |
402
|
|
|
|
|
|
|
|
403
|
|
|
|
|
|
|
The Groups object implements a set of groups. |
404
|
|
|
|
|
|
|
Each group can own single members and group members. |
405
|
|
|
|
|
|
|
A group can be flattened, i.e. expansed until each of his members is a single one. |
406
|
|
|
|
|
|
|
|
407
|
|
|
|
|
|
|
=cut |
408
|
|
|
|
|
|
|
|
409
|
|
|
|
|
|
|
=head1 CONSTRUCTORS |
410
|
|
|
|
|
|
|
|
411
|
|
|
|
|
|
|
=head3 new |
412
|
|
|
|
|
|
|
|
413
|
|
|
|
|
|
|
Create a new group set. |
414
|
|
|
|
|
|
|
|
415
|
|
|
|
|
|
|
my $groups = new Set::Groups |
416
|
|
|
|
|
|
|
|
417
|
|
|
|
|
|
|
=head1 INSTANCE METHODS |
418
|
|
|
|
|
|
|
|
419
|
|
|
|
|
|
|
=head3 setDebug |
420
|
|
|
|
|
|
|
|
421
|
|
|
|
|
|
|
Set a debug level (0 or 1). |
422
|
|
|
|
|
|
|
|
423
|
|
|
|
|
|
|
$groups->setDebug(1) ; |
424
|
|
|
|
|
|
|
|
425
|
|
|
|
|
|
|
=head2 Set management |
426
|
|
|
|
|
|
|
|
427
|
|
|
|
|
|
|
=head3 newGroup |
428
|
|
|
|
|
|
|
|
429
|
|
|
|
|
|
|
Create a new empty group and add it into the set. |
430
|
|
|
|
|
|
|
A group is everything which can be a key of a hash. |
431
|
|
|
|
|
|
|
Returns 1 on success, 0 otherwise. |
432
|
|
|
|
|
|
|
|
433
|
|
|
|
|
|
|
$groups->newGroup("a_group") ; |
434
|
|
|
|
|
|
|
$groups->newGroup(1) ; |
435
|
|
|
|
|
|
|
|
436
|
|
|
|
|
|
|
=head3 deleteGroup |
437
|
|
|
|
|
|
|
|
438
|
|
|
|
|
|
|
Delete a group from the set. Return 1 on success, 0 otherwise. |
439
|
|
|
|
|
|
|
|
440
|
|
|
|
|
|
|
$groups->deleteGroup("a_group") ; |
441
|
|
|
|
|
|
|
|
442
|
|
|
|
|
|
|
=head3 getGroups |
443
|
|
|
|
|
|
|
|
444
|
|
|
|
|
|
|
Return the list of the groups present into the set. |
445
|
|
|
|
|
|
|
|
446
|
|
|
|
|
|
|
@groups = $groups->getGroups() ; |
447
|
|
|
|
|
|
|
|
448
|
|
|
|
|
|
|
=head3 getCyclicGroups |
449
|
|
|
|
|
|
|
|
450
|
|
|
|
|
|
|
Return the list of the cyclic groups (i.e. self-contained) present into the set. |
451
|
|
|
|
|
|
|
|
452
|
|
|
|
|
|
|
@groups = $groups->getGroups() ; |
453
|
|
|
|
|
|
|
|
454
|
|
|
|
|
|
|
=head3 getAcyclicGroups |
455
|
|
|
|
|
|
|
|
456
|
|
|
|
|
|
|
Return the list of the acyclic groups (i.e. not self-contained) present into the set. |
457
|
|
|
|
|
|
|
|
458
|
|
|
|
|
|
|
@groups = $groups->getGroups() ; |
459
|
|
|
|
|
|
|
|
460
|
|
|
|
|
|
|
=head3 hasGroup |
461
|
|
|
|
|
|
|
|
462
|
|
|
|
|
|
|
Check if a group is present into the set. |
463
|
|
|
|
|
|
|
|
464
|
|
|
|
|
|
|
$present = $groups->hasGroup("a_group") ; |
465
|
|
|
|
|
|
|
|
466
|
|
|
|
|
|
|
=head2 Groups management |
467
|
|
|
|
|
|
|
|
468
|
|
|
|
|
|
|
=head3 addOwnSingleTo |
469
|
|
|
|
|
|
|
|
470
|
|
|
|
|
|
|
Add a single member to a group. |
471
|
|
|
|
|
|
|
A single is everything which can be a key of a hash. |
472
|
|
|
|
|
|
|
If the group doesn't exist in the set, it is created. |
473
|
|
|
|
|
|
|
Return 1 on success, 0 otherwise. |
474
|
|
|
|
|
|
|
|
475
|
|
|
|
|
|
|
$groups->addOwnSingleTo("single","a_group") ; |
476
|
|
|
|
|
|
|
|
477
|
|
|
|
|
|
|
=head3 addOwnGroupTo |
478
|
|
|
|
|
|
|
|
479
|
|
|
|
|
|
|
Add a group member to a group. |
480
|
|
|
|
|
|
|
If the embedding group doesn't exist in the set, it is created. |
481
|
|
|
|
|
|
|
If the member group doesn't exist in the set, it is created as an empty group. |
482
|
|
|
|
|
|
|
Return 1 on success, 0 otherwise. |
483
|
|
|
|
|
|
|
|
484
|
|
|
|
|
|
|
$groups->addOwnGroupTo("group_member","a_group") ; |
485
|
|
|
|
|
|
|
|
486
|
|
|
|
|
|
|
=head3 removeOwnSingleFrom |
487
|
|
|
|
|
|
|
|
488
|
|
|
|
|
|
|
Remove an own single from a group. Return 1 on success, 0 otherwise. |
489
|
|
|
|
|
|
|
|
490
|
|
|
|
|
|
|
$groups->removeOwnSingleFrom("single","a_group") ; |
491
|
|
|
|
|
|
|
|
492
|
|
|
|
|
|
|
=head3 removeOwnGroupFrom |
493
|
|
|
|
|
|
|
|
494
|
|
|
|
|
|
|
Remove a group member from a group. Return 1 on success, 0 otherwise. |
495
|
|
|
|
|
|
|
|
496
|
|
|
|
|
|
|
$groups->removeOwnGroupFrom("a_member_group","a_group") ; |
497
|
|
|
|
|
|
|
|
498
|
|
|
|
|
|
|
=head3 isAcyclic |
499
|
|
|
|
|
|
|
|
500
|
|
|
|
|
|
|
Check if a group is acyclic. |
501
|
|
|
|
|
|
|
|
502
|
|
|
|
|
|
|
$is_acyclic = $groups->isAcyclic("a_group") ; |
503
|
|
|
|
|
|
|
|
504
|
|
|
|
|
|
|
=head3 isOwnSingleOf |
505
|
|
|
|
|
|
|
|
506
|
|
|
|
|
|
|
Check if a single is an own member of a group. |
507
|
|
|
|
|
|
|
|
508
|
|
|
|
|
|
|
$present = $groups->isOwnSingleOf("single","a_group") ; |
509
|
|
|
|
|
|
|
|
510
|
|
|
|
|
|
|
=head3 isOwnGroupOf |
511
|
|
|
|
|
|
|
|
512
|
|
|
|
|
|
|
Check if a group is an own member of a group. |
513
|
|
|
|
|
|
|
|
514
|
|
|
|
|
|
|
$present = $groups->isOwnGroupOf("a_group_member","a_group") ; |
515
|
|
|
|
|
|
|
|
516
|
|
|
|
|
|
|
=head3 isSingleOf |
517
|
|
|
|
|
|
|
|
518
|
|
|
|
|
|
|
Check if a single is a (own or not) member of a group. |
519
|
|
|
|
|
|
|
|
520
|
|
|
|
|
|
|
$present = $groups->isSingleOf("single","an_acyclic_group") ; |
521
|
|
|
|
|
|
|
|
522
|
|
|
|
|
|
|
Warning - Calling this method with a cyclic group as argument gives a infinite recursion. |
523
|
|
|
|
|
|
|
|
524
|
|
|
|
|
|
|
=head3 isGroupOf |
525
|
|
|
|
|
|
|
|
526
|
|
|
|
|
|
|
Check if a group is a (own or not) member of a group. |
527
|
|
|
|
|
|
|
|
528
|
|
|
|
|
|
|
$present = $groups->isGroupOf("a_group_member","an_acyclic_group") ; |
529
|
|
|
|
|
|
|
|
530
|
|
|
|
|
|
|
Warning - Calling this method with a cyclic group as argument gives a infinite recursion. |
531
|
|
|
|
|
|
|
|
532
|
|
|
|
|
|
|
=head3 getOwnSinglesOf |
533
|
|
|
|
|
|
|
|
534
|
|
|
|
|
|
|
Return the list of own singles of a group. |
535
|
|
|
|
|
|
|
|
536
|
|
|
|
|
|
|
@singles = $groups->getOwnSinglesOf("a_group") ; |
537
|
|
|
|
|
|
|
|
538
|
|
|
|
|
|
|
=head3 getOwnGroupsOf |
539
|
|
|
|
|
|
|
|
540
|
|
|
|
|
|
|
Return the list of own groups of a group. |
541
|
|
|
|
|
|
|
|
542
|
|
|
|
|
|
|
@groups = $groups->getOwnGroupsOf("a_group") ; |
543
|
|
|
|
|
|
|
|
544
|
|
|
|
|
|
|
=head3 getSinglesOf |
545
|
|
|
|
|
|
|
|
546
|
|
|
|
|
|
|
Return the list of (own or not) singles of an acyclic group. |
547
|
|
|
|
|
|
|
|
548
|
|
|
|
|
|
|
@singles = $groups->getSinglesOf("an_acyclic_group") ; |
549
|
|
|
|
|
|
|
|
550
|
|
|
|
|
|
|
Warning - Calling this method with a cyclic group as argument gives a infinite recursion. |
551
|
|
|
|
|
|
|
|
552
|
|
|
|
|
|
|
=head3 getGroupsOf |
553
|
|
|
|
|
|
|
|
554
|
|
|
|
|
|
|
Return the list of (own or not) groups of an acyclic group. |
555
|
|
|
|
|
|
|
|
556
|
|
|
|
|
|
|
@groups = $groups->getGroupsOf("an_acyclic_group") ; |
557
|
|
|
|
|
|
|
|
558
|
|
|
|
|
|
|
Warning - Calling this method with a cyclic group as argument gives a infinite recursion. |
559
|
|
|
|
|
|
|
|
560
|
|
|
|
|
|
|
=head3 addGroupTo |
561
|
|
|
|
|
|
|
|
562
|
|
|
|
|
|
|
Deprecated - Replaced by addOwnGroupTo. |
563
|
|
|
|
|
|
|
|
564
|
|
|
|
|
|
|
=head3 addSingleTo |
565
|
|
|
|
|
|
|
|
566
|
|
|
|
|
|
|
Deprecated - Replaced by addOwnSingleTo. |
567
|
|
|
|
|
|
|
|
568
|
|
|
|
|
|
|
=head3 removeGroupFrom |
569
|
|
|
|
|
|
|
|
570
|
|
|
|
|
|
|
Deprecated - Replaced by removeOwnGroupFrom. |
571
|
|
|
|
|
|
|
|
572
|
|
|
|
|
|
|
=head3 removeSingleFrom |
573
|
|
|
|
|
|
|
|
574
|
|
|
|
|
|
|
Deprecated - Replaced by removeOwnSingleFrom. |
575
|
|
|
|
|
|
|
|
576
|
|
|
|
|
|
|
=head1 EXAMPLES |
577
|
|
|
|
|
|
|
|
578
|
|
|
|
|
|
|
Suppose a group file like : |
579
|
|
|
|
|
|
|
|
580
|
|
|
|
|
|
|
admin:root,adm |
581
|
|
|
|
|
|
|
team:piotr,lioudmila,adam,annette,jacquelin |
582
|
|
|
|
|
|
|
true-users:james,sophie,@team,mohammed |
583
|
|
|
|
|
|
|
everybody:@admin,operator,@true-users |
584
|
|
|
|
|
|
|
daemon:apache,smmsp,named,daemon |
585
|
|
|
|
|
|
|
virtual:nobody,halt,@daemon |
586
|
|
|
|
|
|
|
all:@everybody,@virtual |
587
|
|
|
|
|
|
|
|
588
|
|
|
|
|
|
|
where C<@name> means I, then the following code : |
589
|
|
|
|
|
|
|
|
590
|
|
|
|
|
|
|
use Set::Groups ; |
591
|
|
|
|
|
|
|
|
592
|
|
|
|
|
|
|
$groups = new Set::Groups ; |
593
|
|
|
|
|
|
|
while(<>) |
594
|
|
|
|
|
|
|
{ |
595
|
|
|
|
|
|
|
($group,$members) = /^(\S+):(.*)$/ ; |
596
|
|
|
|
|
|
|
@members = split(/,/,$members) ; |
597
|
|
|
|
|
|
|
for $member (@members) |
598
|
|
|
|
|
|
|
{ |
599
|
|
|
|
|
|
|
if ($member=~/^@/) |
600
|
|
|
|
|
|
|
{ |
601
|
|
|
|
|
|
|
$member=~s/^@// ; |
602
|
|
|
|
|
|
|
$groups->addOwnGroupTo($member,$group) ; |
603
|
|
|
|
|
|
|
} |
604
|
|
|
|
|
|
|
else |
605
|
|
|
|
|
|
|
{ |
606
|
|
|
|
|
|
|
$groups->addOwnSingleTo($member,$group) ; |
607
|
|
|
|
|
|
|
} |
608
|
|
|
|
|
|
|
} |
609
|
|
|
|
|
|
|
} |
610
|
|
|
|
|
|
|
die "some groups are cyclic" if scalar($groups->getCyclicGroups())>0 ; |
611
|
|
|
|
|
|
|
print "singles: ",join(', ',$groups->getSinglesOf("all")),"\n" ; |
612
|
|
|
|
|
|
|
print "groups: ",join(', ',$groups->getGroupsOf("all")),"\n" ; |
613
|
|
|
|
|
|
|
|
614
|
|
|
|
|
|
|
gives : |
615
|
|
|
|
|
|
|
|
616
|
|
|
|
|
|
|
singles: apache, sophie, jacquelin, lioudmila, mohammed, smmsp, nobody, adm, annette, operator, james, named, adam, halt, root, daemon, piotr |
617
|
|
|
|
|
|
|
groups: admin, everybody, team, daemon, true-users, virtual |
618
|
|
|
|
|
|
|
|
619
|
|
|
|
|
|
|
=cut |
620
|
|
|
|
|
|
|
=head1 AUTHOR |
621
|
|
|
|
|
|
|
|
622
|
|
|
|
|
|
|
Jacquelin Charbonnel, C<< >> |
623
|
|
|
|
|
|
|
|
624
|
|
|
|
|
|
|
=head1 BUGS |
625
|
|
|
|
|
|
|
|
626
|
|
|
|
|
|
|
Please report any bugs or feature requests to |
627
|
|
|
|
|
|
|
C, or through the web interface at |
628
|
|
|
|
|
|
|
L. |
629
|
|
|
|
|
|
|
I will be notified, and then you'll automatically be notified of progress on |
630
|
|
|
|
|
|
|
your bug as I make changes. |
631
|
|
|
|
|
|
|
|
632
|
|
|
|
|
|
|
=head1 SUPPORT |
633
|
|
|
|
|
|
|
|
634
|
|
|
|
|
|
|
You can find documentation for this module with the perldoc command. |
635
|
|
|
|
|
|
|
|
636
|
|
|
|
|
|
|
perldoc Set-Groups |
637
|
|
|
|
|
|
|
|
638
|
|
|
|
|
|
|
You can also look for information at: |
639
|
|
|
|
|
|
|
|
640
|
|
|
|
|
|
|
=over 4 |
641
|
|
|
|
|
|
|
|
642
|
|
|
|
|
|
|
=item * AnnoCPAN: Annotated CPAN documentation |
643
|
|
|
|
|
|
|
|
644
|
|
|
|
|
|
|
L |
645
|
|
|
|
|
|
|
|
646
|
|
|
|
|
|
|
=item * CPAN Ratings |
647
|
|
|
|
|
|
|
|
648
|
|
|
|
|
|
|
L |
649
|
|
|
|
|
|
|
|
650
|
|
|
|
|
|
|
=item * RT: CPAN's request tracker |
651
|
|
|
|
|
|
|
|
652
|
|
|
|
|
|
|
L |
653
|
|
|
|
|
|
|
|
654
|
|
|
|
|
|
|
=item * Search CPAN |
655
|
|
|
|
|
|
|
|
656
|
|
|
|
|
|
|
L |
657
|
|
|
|
|
|
|
|
658
|
|
|
|
|
|
|
=back |
659
|
|
|
|
|
|
|
|
660
|
|
|
|
|
|
|
=head1 COPYRIGHT & LICENSE |
661
|
|
|
|
|
|
|
|
662
|
|
|
|
|
|
|
Copyright Jacquelin Charbonnel E jacquelin.charbonnel at math.cnrs.fr E |
663
|
|
|
|
|
|
|
|
664
|
|
|
|
|
|
|
This software is governed by the CeCILL-C license under French law and |
665
|
|
|
|
|
|
|
abiding by the rules of distribution of free software. You can use, |
666
|
|
|
|
|
|
|
modify and/ or redistribute the software under the terms of the CeCILL-C |
667
|
|
|
|
|
|
|
license as circulated by CEA, CNRS and INRIA at the following URL |
668
|
|
|
|
|
|
|
"http://www.cecill.info". |
669
|
|
|
|
|
|
|
|
670
|
|
|
|
|
|
|
As a counterpart to the access to the source code and rights to copy, |
671
|
|
|
|
|
|
|
modify and redistribute granted by the license, users are provided only |
672
|
|
|
|
|
|
|
with a limited warranty and the software's author, the holder of the |
673
|
|
|
|
|
|
|
economic rights, and the successive licensors have only limited |
674
|
|
|
|
|
|
|
liability. |
675
|
|
|
|
|
|
|
|
676
|
|
|
|
|
|
|
In this respect, the user's attention is drawn to the risks associated |
677
|
|
|
|
|
|
|
with loading, using, modifying and/or developing or reproducing the |
678
|
|
|
|
|
|
|
software by the user in light of its specific status of free software, |
679
|
|
|
|
|
|
|
that may mean that it is complicated to manipulate, and that also |
680
|
|
|
|
|
|
|
therefore means that it is reserved for developers and experienced |
681
|
|
|
|
|
|
|
professionals having in-depth computer knowledge. Users are therefore |
682
|
|
|
|
|
|
|
encouraged to load and test the software's suitability as regards their |
683
|
|
|
|
|
|
|
requirements in conditions enabling the security of their systems and/or |
684
|
|
|
|
|
|
|
data to be ensured and, more generally, to use and operate it in the |
685
|
|
|
|
|
|
|
same conditions as regards security. |
686
|
|
|
|
|
|
|
|
687
|
|
|
|
|
|
|
The fact that you are presently reading this means that you have had |
688
|
|
|
|
|
|
|
knowledge of the CeCILL-C license and that you accept its terms. |
689
|
|
|
|
|
|
|
|