Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
25 / 25
100.00% covered (success)
100.00%
3 / 3
 CRAP
100.00% covered (success)
100.00%
1 / 1
SearchBreadthFirst
100.00% covered (success)
100.00%
25 / 25
100.00% covered (success)
100.00%
3 / 3
 6
100.00% covered (success)
100.00%
1 / 1
 rewind
100.00% covered (success)
100.00%
3 / 3
100.00% covered (success)
100.00%
1 / 1
 1
 next
100.00% covered (success)
100.00%
13 / 13
100.00% covered (success)
100.00%
1 / 1
 4
 getNextLevelOfNodes
100.00% covered (success)
100.00%
9 / 9
100.00% covered (success)
100.00%
1 / 1
 1
1<?php
2
3/**
4 * @author: Doug Wilbourne (dougwilbourne@gmail.com)
5 */
6
7declare(strict_types=1);
8
9namespace pvc\struct\treesearch;
10
11use pvc\interfaces\struct\treesearch\NodeSearchableInterface;
12use pvc\struct\treesearch\err\StartNodeUnsetException;
13
14/**
15 * Class SearchStrategyBreadthFirst
16 *
17 * @template NodeType of NodeSearchableInterface
18 * @extends SearchAbstract<NodeType>
19 */
20class SearchBreadthFirst extends SearchAbstract
21{
22    /**
23     * array of nodes in the "current level" of the tree
24     *
25     * @var array<NodeType>
26     */
27    private array $currentLevelNodes;
28
29    /**
30     * @var int
31     * index into $currentLevelNodes used to retrieve the next node
32     */
33    private int $currentIndex;
34
35
36    /**
37     * rewind
38     *
39     * @throws StartNodeUnsetException
40     */
41    public function rewind(): void
42    {
43        parent::rewind();
44
45        $this->currentLevelNodes = [$this->getStartNode()];
46
47        /**
48         * at the beginning of the iteration, the current node is returned without next() being called first. So
49         * there is nothing that advances the currentIndex pointer when the start node is returned as the first
50         * element in the iteration.  So really, the currentIndex should be 1, not 0
51         */
52        $this->currentIndex = 1;
53    }
54
55    /**
56     * next
57     */
58    public function next(): void
59    {
60        /**
61         * If there are no nodes at the current level, set valid to false and return
62         */
63        if (empty($this->currentLevelNodes)) {
64            $this->setCurrent(null);
65            return;
66        }
67
68        /**
69         * if we still have more nodes in the current level left, set the current node, increment the index
70         */
71        if (isset($this->currentLevelNodes[$this->currentIndex])) {
72            $this->currentNode
73                = $this->currentLevelNodes[$this->currentIndex++];
74            return;
75        }
76
77        /**
78         * if we are at the maximum level permitted in the search and there are no more nodes at this level to
79         * process, set valid to false and return
80         */
81
82        if ($this->atMaxLevels()) {
83            $this->invalidate();
84        } /**
85         * otherwise populate $currentLevelNodes with the next level of nodes
86         */
87        else {
88            /**
89             * get the nodes on the next level of the tree
90             */
91            $this->currentLevelNodes = $this->getNextLevelOfNodes();
92            $this->setCurrentLevel(-Direction::MOVE_DOWN->value);
93            /**
94             * rewind the current index and keep going
95             */
96            $this->currentIndex = 0;
97            $this->next();
98        }
99    }
100
101    /**
102     * getNextLevelOfNodes
103     *
104     * @return array<NodeType>
105     */
106    protected function getNextLevelOfNodes(): array
107    {
108        /**
109         * @param  NodeType  $node
110         *
111         * @return array<NodeType>
112         */
113        $getChildrenCallback = function (NodeSearchableInterface $node): array {
114            return $node->getChildrenArray();
115        };
116        $childArrays = array_map(
117            $getChildrenCallback,
118            $this->currentLevelNodes
119        );
120        /**
121         * splat operator is required to unpack the outer array.  Phpstan
122         * does not understand the callback parameter is NodeType not
123         * NodeSearchableInterface so we need to type hint the result....
124         *
125         * @var array<NodeType> $result
126         */
127        $result = array_merge(...$childArrays);
128        return $result;
129    }
130}