BestFirstStrategy::insert()   A
last analyzed

Complexity

Conditions 1
Paths 1

Size

Total Lines 3
Code Lines 1

Duplication

Lines 0
Ratio 0 %

Importance

Changes 1
Bugs 0 Features 0
Metric Value
cc 1
eloc 1
c 1
b 0
f 0
nc 1
nop 2
dl 0
loc 3
rs 10
1
<?php declare(strict_types=1);
2
3
namespace Stratadox\PuzzleSolver\SearchStrategy;
4
5
use SplPriorityQueue;
6
use Stratadox\PuzzleSolver\Heuristic;
7
use Stratadox\PuzzleSolver\Puzzle;
8
use Stratadox\PuzzleSolver\Moves;
9
10
/**
11
 * Best-first search strategy
12
 *
13
 * Best-first searches enqueue newly encountered nodes by order of quality. The
14
 * move that is most likely to lead to the desired outcome is considered first.
15
 *
16
 * @author Stratadox
17
 */
18
final class BestFirstStrategy implements SearchStrategy
19
{
20
    /** @var SplPriorityQueue */
21
    private $queue;
22
    /** @var Puzzle */
23
    private $originalPuzzle;
24
    /** @var Heuristic */
25
    private $heuristic;
26
27
    private function __construct(
28
        SplPriorityQueue $queue,
29
        Puzzle $originalPuzzle,
30
        Heuristic $heuristic
31
    ) {
32
        $this->queue = $queue;
33
        $this->originalPuzzle = $originalPuzzle;
34
        $this->heuristic = $heuristic;
35
    }
36
37
    public static function withHeuristic(
38
        Heuristic $heuristic,
39
        Puzzle $puzzle
40
    ): SearchStrategy {
41
        $queue = new SplPriorityQueue();
42
        $queue->insert(Moves::none(), 0); // @todo heuristic
43
        return new self($queue, $puzzle, $heuristic);
44
    }
45
46
    public function isOngoing(): bool
47
    {
48
        return !$this->queue->isEmpty();
49
    }
50
51
    public function consider(Puzzle $puzzle): bool
52
    {
53
        $this->insert($puzzle->movesSoFar(), $this->heuristic->estimate($puzzle));
54
        return true;
55
    }
56
57
    public function nextCandidate(): Puzzle
58
    {
59
        return $this->originalPuzzle->afterMaking(...$this->queue->extract());
60
    }
61
62
    private function insert(Moves $moves, float $heuristic): void
63
    {
64
        $this->queue->insert($moves, -($moves->cost() + $heuristic));
65
    }
66
}
67