lib/DX/SearchState.pm

   1 package DX::SearchState;
   2
   3 use Types::Standard qw(Maybe);
   4 use DX::Step::InvokeNextPredicate;
   5 use DX::Class;
   6
   7 has current_hypothesis => (is => 'ro', isa => Hypothesis, required => 1);
   8
   9 has next_step => (is => 'ro', isa => Maybe[Step]);
  10
  11 has propositions => (is => 'ro', isa => PropositionSequence, required => 1);
  12
  13 has alternatives => (is => 'ro', isa => AlternativeList, required => 1);
  14
  15 sub next_proposition {
  16   my ($self, $hyp) = @_;
  17   $hyp ||= $self->current_hypothesis;
  18   $self->propositions->members->[
  19     $hyp->resolved_propositions->resolved_count
  20   ];
  21 }
  22
  23 sub new_for {
  24   my ($class, $hyp, $props) = @_;
  25   $class->new(
  26     current_hypothesis => $hyp,
  27     alternatives => [],
  28     next_step => DX::Step::InvokeNextPredicate->new(
  29       proposition => $props->members->[0],
  30     ),
  31     propositions => $props,
  32   );
  33 }
  34
  35 sub with_one_step {
  36   my ($self) = @_;
  37   my $hyp = $self->current_hypothesis;
  38   return undef unless my $step = $self->next_step;
  39   my ($first_alt, @rest_alt) = my @alt = @{$self->alternatives};
  40   my ($new_hyp, $alt_step) = $step->apply_to($hyp);
  41   if ($new_hyp) {
  42     return $self->but(
  43       current_hypothesis => $new_hyp,
  44       alternatives => [
  45         ($alt_step
  46           ? [ $hyp, $alt_step ]
  47           : ()),
  48         @alt
  49       ],
  50       next_step => DX::Step::InvokeNextPredicate->new(
  51         proposition => $self->next_proposition($new_hyp),
  52       ),
  53     );
  54   }
  55   if ($alt_step) {
  56     return $self->but(next_step => $alt_step);
  57   }
  58   return undef unless $first_alt;
  59   trace 'search.backtrack.rewind_to' => $first_alt->[1];
  60   return $self->but(
  61     current_hypothesis => $first_alt->[0],
  62     alternatives => \@rest_alt,
  63     next_step => $first_alt->[1],
  64   );
  65 }
  66
  67 sub find_solution {
  68   my $state = $_[0];
  69   while ($state and $state->next_proposition) {
  70     $state = $state->with_one_step;
  71   }
  72   trace 'search.solution.hyp' => $state->current_hypothesis if $state;
  73   return $state;
  74 }
  75
  76 sub force_backtrack {
  77   my ($self) = @_;
  78   my ($first_alt, @rest_alt) = @{$self->alternatives};
  79   return undef unless $first_alt;
  80   trace 'search.backtrack.forced' => $first_alt->[0];
  81   return ref($self)->new(
  82     current_hypothesis => $first_alt->[0],
  83     next_step => $first_alt->[1],
  84     alternatives => \@rest_alt,
  85     propositions => $self->propositions,
  86   );
  87 }
  88
  89 sub find_next_solution {
  90   my ($self) = @_;
  91   return undef unless my $bt = $self->force_backtrack;
  92   return $bt->find_solution;
  93 }
  94
  95 1;