view release on metacpan or  search on metacpan

lib/Algorithm/Dependency.pm  view on Meta::CPAN

#pod
#pod Returns an L<Algorithm::Dependency::Item> object on success, or C<undef> if
#pod an item does not exist for the argument provided.
#pod
#pod =cut

sub item { $_[0]->{source}->item($_[1]) }





#####################################################################
# Main algorithm methods

#pod =pod
#pod
#pod =head2 depends $name1, ..., $nameN
#pod
#pod Given a list of one or more item names, the C<depends> method will return
#pod a reference to an array containing a list of the names of all the OTHER
#pod items that also have to be selected to meet dependencies.
#pod
#pod That is, if item A depends on B and C then the C<depends> method would
#pod return a reference to an array with B and C. ( C<[ 'B', 'C' ]> )
#pod
#pod If multiple item names are provided, the same applies. The list returned
#pod will not contain duplicates.
#pod
#pod The method returns a reference to an array of item names on success, a
#pod reference to an empty array if no other items are needed, or C<undef>
#pod on error.
#pod
#pod NOTE: The result of C<depends> is ordered by an internal C<sort>
#pod irrespective of the ordering provided by the dependency handler.  Use
#pod L<Algorithm::Dependency::Ordered> and C<schedule> to use the most
#pod common ordering (process sequence)
#pod
#pod =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 =pod
#pod
#pod =head2 schedule $name1, ..., $nameN
#pod
#pod Given a list of one or more item names, the C<depends> method will
#pod return, as a reference to an array, the ordered list of items you
#pod should act upon in whichever order this particular dependency handler
#pod uses - see L<Algorithm::Dependency::Ordered> for one that implements
#pod the most common ordering (process sequence).
#pod
#pod This would be the original names provided, plus those added to satisfy
#pod dependencies, in the preferred order of action. For the normal algorithm,
#pod where order it not important, this is alphabetical order. This makes it
#pod easier for someone watching a program operate on the items to determine
#pod how far you are through the task and makes any logs easier to read.
#pod
#pod If any of the names you provided in the arguments is already selected, it
#pod will not be included in the list.
#pod
#pod The method returns a reference to an array of item names on success, a
#pod reference to an empty array if no items need to be acted upon, or C<undef>
#pod on error.
#pod
#pod =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 =pod
#pod
#pod =head2 schedule_all;
#pod
#pod The C<schedule_all> method acts the same as the C<schedule> method, but 
#pod returns a schedule that selected all the so-far unselected items.
#pod
#pod =cut

sub schedule_all {
	my $self = shift;
	$self->schedule( map { $_->id } $self->source->items );
}

1;

__END__

=pod

=encoding UTF-8

=head1 NAME

Algorithm::Dependency - Base class for implementing various dependency trees

=head1 VERSION

version 1.112

=head1 SYNOPSIS

Typical Usage: Ordering based on dependency requirements

lib/Algorithm/Dependency.pm  view on Meta::CPAN

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.

=head2 source

The C<source> method retrieves the L<Algorithm::Dependency::Source> object
for the algorithm context.

=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.

=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.

=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.

=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.

NOTE: The result of C<depends> is ordered by an internal C<sort>
irrespective of the ordering provided by the dependency handler.  Use
L<Algorithm::Dependency::Ordered> and C<schedule> to use the most
common ordering (process sequence)

=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 in whichever order this particular dependency handler
uses - see L<Algorithm::Dependency::Ordered> for one that implements
the most common ordering (process sequence).

This would be the original names provided, plus those added to satisfy
dependencies, in the preferred 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.

=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.

=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 SEE ALSO

L<Algorithm::Dependency::Ordered>, L<Algorithm::Dependency::Item>,
L<Algorithm::Dependency::Source>, L<Algorithm::Dependency::Source::File>

=head1 SUPPORT

Bugs may be submitted through L<the RT bug tracker|https://rt.cpan.org/Public/Dist/Display.html?Name=Algorithm-Dependency>
(or L<bug-Algorithm-Dependency@rt.cpan.org|mailto:bug-Algorithm-Dependency@rt.cpan.org>).

=head1 AUTHOR

Adam Kennedy <adamk@cpan.org>

=head1 CONTRIBUTORS

=for stopwords Adam Kennedy Karen Etheridge Mark Murawski

=over 4

=item *

Adam Kennedy <adam@ali.as>

=item *

Karen Etheridge <ether@cpan.org>

=item *

Mark Murawski <markm@intellasoft.net>