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 { $_[0]->current_hypothesis->head_proposition }
  16
  17 sub new_for {
  18   my ($class, $hyp, $props) = @_;
  19   $class->new(
  20     current_hypothesis => $hyp,
  21     alternatives => [],
  22     next_step => DX::Step::InvokeNextPredicate->new(
  23       proposition => $hyp->head_proposition,
  24     ),
  25     propositions => $props,
  26   );
  27 }
  28
  29 sub with_one_step {
  30   my ($self) = @_;
  31   my $hyp = $self->current_hypothesis;
  32   return undef unless my $step = $self->next_step;
  33   my ($first_alt, @rest_alt) = my @alt = @{$self->alternatives};
  34   my ($new_hyp, $alt_step) = $step->apply_to($hyp);
  35   if ($new_hyp) {
  36     return $self->but(
  37       current_hypothesis => $new_hyp,
  38       alternatives => [
  39         ($alt_step
  40           ? [ $hyp, $alt_step ]
  41           : ()),
  42         @alt
  43       ],
  44       next_step => DX::Step::InvokeNextPredicate->new(
  45         proposition => $self->next_proposition,
  46       ),
  47     );
  48   }
  49   if ($alt_step) {
  50     return $self->but(next_step => $alt_step);
  51   }
  52   return undef unless $first_alt;
  53   trace 'search.backtrack.rewind_to' => $first_alt->[1];
  54   return $self->but(
  55     current_hypothesis => $first_alt->[0],
  56     alternatives => \@rest_alt,
  57     next_step => $first_alt->[1],
  58   );
  59 }
  60
  61 sub find_solution {
  62   my $state = $_[0];
  63   while ($state and @{$state->current_hypothesis->outstanding_propositions}) {
  64     $state = $state->with_one_step;
  65   }
  66   trace 'search.solution.hyp' => $state->current_hypothesis if $state;
  67   return $state;
  68 }
  69
  70 sub force_backtrack {
  71   my ($self) = @_;
  72   my ($first_alt, @rest_alt) = @{$self->alternatives};
  73   return undef unless $first_alt;
  74   trace 'search.backtrack.forced' => $first_alt->[0];
  75   return ref($self)->new(
  76     current_hypothesis => $first_alt->[0],
  77     next_step => $first_alt->[1],
  78     alternatives => \@rest_alt,
  79     propositions => $self->propositions,
  80   );
  81 }
  82
  83 sub find_next_solution {
  84   my ($self) = @_;
  85   return undef unless my $bt = $self->force_backtrack;
  86   return $bt->find_solution;
  87 }
  88
  89 1;