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