AStar::evaluateSuccessors() - Code Metrics - Inspection of "Refactor the AStar class to make it more readable" - jmgq/php-a-star - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( cf16e0...5c8744 )

by Jose

created 2021-02-14 19:23 UTC

AStar::evaluateSuccessors() A

↳ Parent: AStar

Complexity

Conditions	4
Paths	4

Size

Total Lines	16
Code Lines	8

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	9
CRAP Score	4

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
eloc	8
c	1
b	0
f	0
dl	0
loc	16
ccs	9
cts	9
cp	1
rs	10
cc	4
nc	4
nop	2
crap	4

<?php

namespace JMGQ\AStar;

use JMGQ\AStar\Node\Collection\NodeCollectionInterface;
use JMGQ\AStar\Node\Collection\NodeHashTable;
use JMGQ\AStar\Node\Node;

/**
 * @template TState
 */
class AStar
{
    /** @var DomainLogicInterface<TState> */
    private DomainLogicInterface $domainLogic;
    /** @var NodeCollectionInterface<TState> | NodeHashTable<TState> */
    private NodeCollectionInterface $openList;
    /** @var NodeCollectionInterface<TState> | NodeHashTable<TState> */
    private NodeCollectionInterface $closedList;

    /**
     * @param DomainLogicInterface<TState> $domainLogic
     */
    public function __construct(DomainLogicInterface $domainLogic)
    {
        $this->domainLogic = $domainLogic;
        $this->openList = new NodeHashTable();
        $this->closedList = new NodeHashTable();
    }

    /**
     * @param TState $start
     * @param TState $goal
filter:
    dependency_paths: ["lib/*"]
     * @return iterable<TState>
     */
    public function run(mixed $start, mixed $goal): iterable
    {
        $startNode = new Node($start);
        $goalNode = new Node($goal);

        return $this->executeAlgorithm($startNode, $goalNode);
    }

    /**
     * @param Node<TState> $start
     * @param Node<TState> $goal
     * @return iterable<TState>
     */
    private function executeAlgorithm(Node $start, Node $goal): iterable
    {
        $path = [];

        $this->clear();

        $start->setG(0);
        $start->setH($this->calculateEstimatedCost($start, $goal));

        $this->openList->add($start);

        while (!$this->openList->isEmpty()) {
            /** @var Node<TState> $currentNode Cannot be null because the open list is not empty */
            $currentNode = $this->openList->extractBest();

            $this->closedList->add($currentNode);

            if ($currentNode->getId() === $goal->getId()) {
                $path = $this->generatePathFromStartNodeTo($currentNode);
                break;
            }

            $successors = $this->getAdjacentNodesWithTentativeScore($currentNode, $goal);

            $this->evaluateSuccessors($successors, $currentNode);
        }

        return $path;
    }

    /**
     * Sets the algorithm to its initial state
     */
    private function clear(): void
    {
        $this->openList->clear();
        $this->closedList->clear();
    }

    /**
     * @param Node<TState> $node
     * @return iterable<Node<TState>>
     */
    private function generateAdjacentNodes(Node $node): iterable
    {
        $adjacentNodes = [];

        $adjacentStates = $this->domainLogic->getAdjacentNodes($node->getState());

        foreach ($adjacentStates as $state) {
            $adjacentNodes[] = new Node($state);
        }

        return $adjacentNodes;
    }

    /**
     * @param Node<TState> $node
     * @param Node<TState> $adjacent
     * @return float | int
     */
    private function calculateRealCost(Node $node, Node $adjacent): float | int
    {
        $state = $node->getState();
        $adjacentState = $adjacent->getState();

        return $this->domainLogic->calculateRealCost($state, $adjacentState);
    }

    /**
     * @param Node<TState> $start
     * @param Node<TState> $end
     * @return float | int
     */
    private function calculateEstimatedCost(Node $start, Node $end): float | int
    {
        $startState = $start->getState();
        $endState = $end->getState();

        return $this->domainLogic->calculateEstimatedCost($startState, $endState);
    }

    /**
     * @param Node<TState> $node
     * @return iterable<TState>
     */
    private function generatePathFromStartNodeTo(Node $node): iterable
    {
        $path = [];

        $currentNode = $node;

        while ($currentNode !== null) {
            array_unshift($path, $currentNode->getState());

            $currentNode = $currentNode->getParent();
        }

        return $path;
    }

    /**
     * @param Node<TState> $node
     * @param Node<TState> $goal
     * @return iterable<Node<TState>>
     */
    private function getAdjacentNodesWithTentativeScore(Node $node, Node $goal): iterable
    {
        $nodes = $this->generateAdjacentNodes($node);

        foreach ($nodes as $adjacentNode) {
            $adjacentNode->setG($node->getG() + $this->calculateRealCost($node, $adjacentNode));
            $adjacentNode->setH($this->calculateEstimatedCost($adjacentNode, $goal));
        }

        return $nodes;
    }

    /**
     * @param iterable<Node<TState>> $successors
     * @param Node<TState> $parent
     */
    private function evaluateSuccessors(iterable $successors, Node $parent): void
    {
        foreach ($successors as $successor) {
            if ($this->nodeAlreadyPresentInListWithBetterOrSameRealCost($successor, $this->openList)) {
                continue;
            }

            if ($this->nodeAlreadyPresentInListWithBetterOrSameRealCost($successor, $this->closedList)) {
                continue;
            }

            $successor->setParent($parent);

            $this->closedList->remove($successor);

            $this->openList->add($successor);
        }
    }

    /**
     * @param Node<TState> $node
     * @param NodeCollectionInterface<TState> $nodeList
     * @return bool
     */
    private function nodeAlreadyPresentInListWithBetterOrSameRealCost(
        Node $node,
        NodeCollectionInterface $nodeList
    ): bool {
        if ($nodeList->contains($node)) {
            /** @var Node<TState> $nodeInList Cannot be null because the list contains it */
            $nodeInList = $nodeList->get($node->getId());

            if ($node->getG() >= $nodeInList->getG()) {
                return true;
            }
        }

        return false;
    }
}


1		<?php
2
3		namespace JMGQ\AStar;
4
5		use JMGQ\AStar\Node\Collection\NodeCollectionInterface;
6		use JMGQ\AStar\Node\Collection\NodeHashTable;
7		use JMGQ\AStar\Node\Node;
8
9		/**
10		* @template TState
11		*/
12		class AStar
13		{
14		/** @var DomainLogicInterface<TState> */
15		private DomainLogicInterface $domainLogic;
16		/** @var NodeCollectionInterface<TState> \| NodeHashTable<TState> */
17		private NodeCollectionInterface $openList;
18		/** @var NodeCollectionInterface<TState> \| NodeHashTable<TState> */
19		private NodeCollectionInterface $closedList;
20
21		/**
22		* @param DomainLogicInterface<TState> $domainLogic
23		*/
24	12	public function __construct(DomainLogicInterface $domainLogic)
25		{
26	12	$this->domainLogic = $domainLogic;
27	12	$this->openList = new NodeHashTable();
28	12	$this->closedList = new NodeHashTable();
29	12	}
30
31		/**
32		* @param TState $start
33		* @param TState $goal
		0 ignored issues – show Bug introduced 2021-02-14 15:19 UTC by Report Bug Copy Issue Report The type `JMGQ\AStar\TState` was not found. Maybe you did not declare it correctly or list all dependencies? The issue could also be caused by a filter entry in the build configuration. If the path has been excluded in your configuration, e.g. `excluded_paths: ["lib/"]`, you can move it to the dependency path list as follows: filter: dependency_paths: ["lib/"] For further information see https://scrutinizer-ci.com/docs/tools/php/php-scrutinizer/#list-dependency-paths Loading history...
34		* @return iterable<TState>
35		*/
36	12	public function run(mixed $start, mixed $goal): iterable
37		{
38	12	$startNode = new Node($start);
39	12	$goalNode = new Node($goal);
40
41	12	return $this->executeAlgorithm($startNode, $goalNode);
42		}
43
44		/**
45		* @param Node<TState> $start
46		* @param Node<TState> $goal
47		* @return iterable<TState>
48		*/
49	12	private function executeAlgorithm(Node $start, Node $goal): iterable
50		{
51	12	$path = [];
52
53	12	$this->clear();
54
55	12	$start->setG(0);
56	12	$start->setH($this->calculateEstimatedCost($start, $goal));
57
58	12	$this->openList->add($start);
59
60	12	while (!$this->openList->isEmpty()) {
61		/** @var Node<TState> $currentNode Cannot be null because the open list is not empty */
62	12	$currentNode = $this->openList->extractBest();
63
64	12	$this->closedList->add($currentNode);
65
66	12	if ($currentNode->getId() === $goal->getId()) {
67	11	$path = $this->generatePathFromStartNodeTo($currentNode);
68	11	break;
69		}
70
71	10	$successors = $this->getAdjacentNodesWithTentativeScore($currentNode, $goal);
72
73	10	$this->evaluateSuccessors($successors, $currentNode);
74		}
75
76	12	return $path;
77		}
78
79		/**
80		* Sets the algorithm to its initial state
81		*/
82	12	private function clear(): void
83		{
84	12	$this->openList->clear();
85	12	$this->closedList->clear();
86	12	}
87
88		/**
89		* @param Node<TState> $node
90		* @return iterable<Node<TState>>
91		*/
92	10	private function generateAdjacentNodes(Node $node): iterable
93		{
94	10	$adjacentNodes = [];
95
96	10	$adjacentStates = $this->domainLogic->getAdjacentNodes($node->getState());
97
98	10	foreach ($adjacentStates as $state) {
99	9	$adjacentNodes[] = new Node($state);
100		}
101
102	10	return $adjacentNodes;
103		}
104
105		/**
106		* @param Node<TState> $node
107		* @param Node<TState> $adjacent
108		* @return float \| int
109		*/
110	9	private function calculateRealCost(Node $node, Node $adjacent): float \| int
111		{
112	9	$state = $node->getState();
113	9	$adjacentState = $adjacent->getState();
114
115	9	return $this->domainLogic->calculateRealCost($state, $adjacentState);
116		}
117
118		/**
119		* @param Node<TState> $start
120		* @param Node<TState> $end
121		* @return float \| int
122		*/
123	12	private function calculateEstimatedCost(Node $start, Node $end): float \| int
124		{
125	12	$startState = $start->getState();
126	12	$endState = $end->getState();
127
128	12	return $this->domainLogic->calculateEstimatedCost($startState, $endState);
129		}
130
131		/**
132		* @param Node<TState> $node
133		* @return iterable<TState>
134		*/
135	11	private function generatePathFromStartNodeTo(Node $node): iterable
136		{
137	11	$path = [];
138
139	11	$currentNode = $node;
140
141	11	while ($currentNode !== null) {
142	11	array_unshift($path, $currentNode->getState());
143
144	11	$currentNode = $currentNode->getParent();
145		}
146
147	11	return $path;
148		}
149
150		/**
151		* @param Node<TState> $node
152		* @param Node<TState> $goal
153		* @return iterable<Node<TState>>
154		*/
155	10	private function getAdjacentNodesWithTentativeScore(Node $node, Node $goal): iterable
156		{
157	10	$nodes = $this->generateAdjacentNodes($node);
158
159	10	foreach ($nodes as $adjacentNode) {
160	9	$adjacentNode->setG($node->getG() + $this->calculateRealCost($node, $adjacentNode));
161	9	$adjacentNode->setH($this->calculateEstimatedCost($adjacentNode, $goal));
162		}
163
164	10	return $nodes;
165		}
166
167		/**
168		* @param iterable<Node<TState>> $successors
169		* @param Node<TState> $parent
170		*/
171	10	private function evaluateSuccessors(iterable $successors, Node $parent): void
172		{
173	10	foreach ($successors as $successor) {
174	9	if ($this->nodeAlreadyPresentInListWithBetterOrSameRealCost($successor, $this->openList)) {
175	6	continue;
176		}
177
178	9	if ($this->nodeAlreadyPresentInListWithBetterOrSameRealCost($successor, $this->closedList)) {
179	7	continue;
180		}
181
182	9	$successor->setParent($parent);
183
184	9	$this->closedList->remove($successor);
185
186	9	$this->openList->add($successor);
187		}
188	10	}
189
190		/**
191		* @param Node<TState> $node
192		* @param NodeCollectionInterface<TState> $nodeList
193		* @return bool
194		*/
195	9	private function nodeAlreadyPresentInListWithBetterOrSameRealCost(
196		Node $node,
197		NodeCollectionInterface $nodeList
198		): bool {
199	9	if ($nodeList->contains($node)) {
200		/** @var Node<TState> $nodeInList Cannot be null because the list contains it */
201	8	$nodeInList = $nodeList->get($node->getId());
202
203	8	if ($node->getG() >= $nodeInList->getG()) {
204	7	return true;
205		}
206		}
207
208	9	return false;
209		}
210		}
211

jmgq / php-a-star

Push — master ( cf16e0...5c8744 )

AStar::evaluateSuccessors() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like