view release on metacpan or  search on metacpan

lib/Algorithm/DependencySolver/Traversal.pm  view on Meta::CPAN

package Algorithm::DependencySolver::Traversal;
$Algorithm::DependencySolver::Traversal::VERSION = '1.01';
use Moose;
use MooseX::FollowPBP;
use MooseX::Method::Signatures;

use List::MoreUtils qw(all uniq);

use Data::Dumper;

=head1 NAME

Algorithm::DependencySolver::Traversal - A module for traversing a dependency graph

=head1 VERSION

version 1.01

=head1 SYNOPSIS

    my $traversal = Algorithm::DependencySolver::Traversal->new(
        Solver => $solver,
        visit  => sub {
            my $operation = shift;
            print "Visited operation: ", $operation->id, "\n";
        },
    );

    $traversal->run;

=head1 DESCRIPTION

Given an L<Algorithm::DependencySolver::Solver.pm> object, traverses it
in such a way that upon entering a node, all of its prerequisites will
have already been entered.

=head2 Concurrency

Currently this module is I<not> thread-safe. However, it has been
design in such a way that it should be easy to allow concurrency at a
later stage, without needing to break backwards compatibility.

Note that if we allow concurrency, the C<visitable> list may be empty,
without indicating that the traversal is complete.

=head1 METHODS

=cut


has 'Solver' => (
    is       => 'ro',
    isa      => 'Algorithm::DependencySolver::Solver',
    required => 1,
);

has 'visitable' => (
    is      => 'rw',
#   isa     => 'ArrayRef[String]',
    default => sub { [] },
);

# indexed by $node->id; value is boolean
has 'visited' => (
    is      => 'ro',
#   isa     => 'HashRef[Bool]',
    default => sub { {} },
);

has 'visit' => (
    is       => 'rw',
    isa      => 'CodeRef',
    default  => sub { sub { 1 } },
);

has 'choose' => (
    is       => 'ro',
    isa      => 'CodeRef',
    default  => sub { sub { shift } },
);



=head2 C<choose>

During the traversal, we maintain a list of nodes, C<visitable>, which
can be immediately visited. If this list is empty, the traversal is
complete.

The C<choose> function is called to decide which node is C<visitable>
to visit next. Note that C<choose> is guaranteed to be called, even if
C<visitable> is a singleton (but not if it's empty).

=cut

method choose() {
    my $size = @{$self->get_visitable};
    die "choose(): precondition for size failed" unless $size;
    my $choice = $self->get_choose->(@{$self->get_visitable});