/usr/share/perl5/Algorithm/Dependency.pm is in libalgorithm-dependency-perl 1.110-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 | package Algorithm::Dependency;
=pod
=head1 NAME
Algorithm::Dependency - Base class for implementing various dependency trees
=head1 SYNOPSIS
use Algorithm::Dependency;
use Algorithm::Dependency::Source::File;
# Load the data from a simple text file
my $data_source = Algorithm::Dependency::Source::File->new( 'foo.txt' );
# Create the dependency object, and indicate the items that are already
# selected/installed/etc in the database
my $dep = Algorithm::Dependency->new(
source => $data_source,
selected => [ 'This', 'That' ]
) or die 'Failed to set up dependency algorithm';
# For the item 'Foo', find out the other things we also have to select.
# This WON'T include the item we selected, 'Foo'.
my $also = $dep->depends( 'Foo' );
print $also
? "By selecting 'Foo', you are also selecting the following items: "
. join( ', ', @$also )
: "Nothing else to select for 'Foo'";
# Find out the order we need to act on the items in.
# This WILL include the item we selected, 'Foo'.
my $schedule = $dep->schedule( 'Foo' );
=head1 DESCRIPTION
Algorithm::Dependency is a framework for creating simple read-only
dependency heirachies, where you have a set of items that rely on other
items in the set, and require actions on them as well.
Despite the most visible of these being software installation systems like
the CPAN installer, or debian apt-get, they are usefull in other situations.
This module intentionally uses implementation-neutral words, to avoid
confusion.
=head2 Terminology
The term C<ITEM> refers to a single entity, such as a single software
package, in the overall set of possible entities. Internally, this is a
fairly simple object. See L<Algorithm::Dependency::Item> for details.
The term C<SELECT> means that a particular item, for your purposes, has
already been acted up in the required way. For example, if the software
package had already been installed, and didn't need to be re-installed,
it would be C<SELECTED>.
The term C<SOURCE> refers to a location that contains the master set of
items. This will be very application specific, and might be a flat file,
some form of database, the list of files in a folder, or generated
dynamically.
=head2 General Description
Algorithm::Dependency implements algorithms relating to dependency
heirachies. To use this framework, all you need is a source for the master
list of all the items, and a list of those already selected. If your
dependency heirachy doesn't require the concept of items that are already
selected, simply don't pass anything to the constructor for it.
Please note that the class Algorithm::Dependency does NOT implement an
ordering, for speed and simplicity reasons. That is, the C<schedule> it
provides is not in any particular order. If item 'A' depends on item 'B',
it will not place B before A in the schedule. This makes it unsuitable for
things like software installers, as they typically would need B to be
installed before A, or the installation of A would fail.
For dependency heirachies requiring the items to be acted on in a particular
order, either top down or bottom up, see L<Algorithm::Dependency::Ordered>.
It should be more applicable for your needs. This is the the subclass you
would probably use to implement a simple ( non-versioned ) package
installation system. Please note that an ordered heirachy has additional
constraints. For example, circular dependencies ARE legal in a
non-ordered heirachy, but ARE NOT legal in an ordered heirachy.
=head2 Extending
A module for creating a source from a simple flat file is included. For
details see L<Algorithm::Dependency::Source::File>. Information on creating
a source for your particular use is in L<Algorithm::Dependency::Source>.
=head1 METHODS
=cut
use 5.005;
use strict;
use Algorithm::Dependency::Item ();
use Algorithm::Dependency::Source ();
use Params::Util qw{_INSTANCE _ARRAY};
use vars qw{$VERSION};
BEGIN {
$VERSION = '1.110';
}
#####################################################################
# Constructor
=pod
=head2 new %args
The constructor creates a new context object for the dependency algorithms to
act in. It takes as argument a series of options for creating the object.
=over 4
=item source => $Source
The only compulsory option is the source of the dependency items. This is
an object of a subclass of L<Algorithm::Dependency::Source>. In practical terms,
this means you will create the source object before creating the
Algorithm::Dependency object.
=item selected => [ 'A', 'B', 'C', etc... ]
The C<selected> option provides a list of those items that have already been
'selected', acted upon, installed, or whatever. If another item depends on one
in this list, we don't have to include it in the output of the C<schedule> or
C<depends> methods.
=item ignore_orphans => 1
Normally, the item source is expected to be largely perfect and error free.
An 'orphan' is an item name that appears as a dependency of another item, but
doesn't exist, or has been deleted.
By providing the C<ignore_orphans> flag, orphans are simply ignored. Without
the C<ignore_orphans> flag, an error will be returned if an orphan is found.
=back
The C<new> constructor returns a new Algorithm::Dependency object on success,
or C<undef> on error.
=cut
sub new {
my $class = shift;
my %args = @_;
my $source = _INSTANCE($args{source}, 'Algorithm::Dependency::Source')
or return undef;
# Create the object
my $self = bless {
source => $source, # Source object
selected => {},
}, $class;
# Were we given the 'ignore_orphans' flag?
if ( $args{ignore_orphans} ) {
$self->{ignore_orphans} = 1;
}
# Done, unless we have been given some selected items
_ARRAY($args{selected}) or return $self;
# Make sure each of the selected ids exists
my %selected = ();
foreach my $id ( @{ $args{selected} } ) {
# Does the item exist?
return undef unless $source->item($id);
# Is it a duplicate
return undef if $selected{$id};
# Add to the selected index
$selected{$id} = 1;
}
$self->{selected} = \%selected;
$self;
}
#####################################################################
# Basic methods
=pod
=head2 source
The C<source> method retrieves the L<Algorithm::Dependency::Source> object
for the algorithm context.
=cut
sub source { $_[0]->{source} }
=pod
=head2 selected_list
The C<selected_list> method returns, as a list and in alphabetical order,
the list of the names of the selected items.
=cut
sub selected_list { sort keys %{$_[0]->{selected}} }
=pod
=head2 selected $name
Given an item name, the C<selected> method will return true if the item is
selected, false is not, or C<undef> if the item does not exist, or an error
occurs.
=cut
sub selected { $_[0]->{selected}->{$_[1]} }
=pod
=head2 item $name
The C<item> method fetches and returns the item object, as specified by the
name argument.
Returns an L<Algorithm::Dependency::Item> object on success, or C<undef> if
an item does not exist for the argument provided.
=cut
sub item { $_[0]->{source}->item($_[1]) }
#####################################################################
# Main algorithm methods
=pod
=head2 depends $name1, ..., $nameN
Given a list of one or more item names, the C<depends> method will return
a reference to an array containing a list of the names of all the OTHER
items that also have to be selected to meet dependencies.
That is, if item A depends on B and C then the C<depends> method would
return a reference to an array with B and C. ( C<[ 'B', 'C' ]> )
If multiple item names are provided, the same applies. The list returned
will not contain duplicates.
The method returns a reference to an array of item names on success, a
reference to an empty array if no other items are needed, or C<undef>
on error.
=cut
sub depends {
my $self = shift;
my @stack = @_ or return undef;
my @depends = ();
my %checked = ();
# Process the stack
while ( my $id = shift @stack ) {
# Does the id exist?
my $Item = $self->{source}->item($id)
or $self->{ignore_orphans} ? next : return undef;
# Skip if selected or checked
next if $checked{$id};
# Add its depends to the stack
push @stack, $Item->depends;
$checked{$id} = 1;
# Add anything to the final output that wasn't one of
# the original input.
unless ( scalar grep { $id eq $_ } @_ ) {
push @depends, $id;
}
}
# Remove any items already selected
my $s = $self->{selected};
return [ sort grep { ! $s->{$_} } @depends ];
}
=pod
=head2 schedule $name1, ..., $nameN
Given a list of one or more item names, the C<depends> method will return,
as a reference to an array, the ordered list of items you should act upon.
This would be the original names provided, plus those added to satisfy
dependencies, in the prefered order of action. For the normal algorithm,
where order it not important, this is alphabetical order. This makes it
easier for someone watching a program operate on the items to determine
how far you are through the task and makes any logs easier to read.
If any of the names you provided in the arguments is already selected, it
will not be included in the list.
The method returns a reference to an array of item names on success, a
reference to an empty array if no items need to be acted upon, or C<undef>
on error.
=cut
sub schedule {
my $self = shift;
my @items = @_ or return undef;
# Get their dependencies
my $depends = $self->depends( @items ) or return undef;
# Now return a combined list, removing any items already selected.
# We are allowed to return an empty list.
my $s = $self->{selected};
return [ sort grep { ! $s->{$_} } @items, @$depends ];
}
=pod
=head2 schedule_all;
The C<schedule_all> method acts the same as the C<schedule> method, but
returns a schedule that selected all the so-far unselected items.
=cut
sub schedule_all {
my $self = shift;
$self->schedule( map { $_->id } $self->source->items );
}
1;
=pod
=head1 TO DO
Add the C<check_source> method, to verify the integrity of the source.
Possibly add Algorithm::Dependency::Versions, to implement an ordered
dependency tree with versions, like for perl modules.
Currently readonly. Make the whole thing writable, so the module can be
used as the core of an actual dependency application, as opposed to just
being a tool.
=head1 SUPPORT
Bugs should be submitted via the CPAN bug tracker, located at
L<http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Algorithm-Dependency>
For general comments, contact the author.
=head1 AUTHOR
Adam Kennedy E<lt>adamk@cpan.orgE<gt>
=head1 SEE ALSO
L<Algorithm::Dependency::Ordered>, L<Algorithm::Dependency::Item>,
L<Algorithm::Dependency::Source>, L<Algorithm::Dependency::Source::File>
=head1 COPYRIGHT
Copyright 2003 - 2009 Adam Kennedy.
This program is free software; you can redistribute
it and/or modify it under the same terms as Perl itself.
The full text of the license can be found in the
LICENSE file included with this module.
=cut
|