Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
20 / 20
100.00% covered (success)
100.00%
3 / 3
 CRAP
100.00% covered (success)
100.00%
1 / 1
SearchBreadthFirst
100.00% covered (success)
100.00%
20 / 20
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%
12 / 12
100.00% covered (success)
100.00%
1 / 1
 4
 getNextLevelOfNodes
100.00% covered (success)
100.00%
5 / 5
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 * @extends SearchAbstract<NodeSearchableInterface>
17 */
18class SearchBreadthFirst extends SearchAbstract
19{
20    /**
21     * array of nodes in the "current level" of the tree
22     * @var array<NodeSearchableInterface>
23     */
24    private array $currentLevelNodes;
25
26    /**
27     * @var int
28     * index into $currentLevelNodes used to retrieve the next node
29     */
30    private int $currentIndex;
31
32
33    /**
34     * rewind
35     * @throws StartNodeUnsetException
36     */
37    public function rewind(): void
38    {
39        parent::rewind();
40
41        $this->currentLevelNodes = [$this->getStartNode()];
42
43        /**
44         * at the beginning of the iteration, the current node is returned without next() being called first. So
45         * there is nothing that advances the currentIndex pointer when the start node is returned as the first
46         * element in the iteration.  So really, the currentIndex should be 1, not 0
47         */
48        $this->currentIndex = 1;
49    }
50
51    /**
52     * next
53     */
54    public function next(): void
55    {
56        /**
57         * If there are no nodes at the current level, set valid to false and return
58         */
59        if (empty($this->currentLevelNodes)) {
60            $this->setCurrent(null);
61            return;
62        }
63
64        /**
65         * if we still have more nodes in the current level left, set the current node, increment the index
66         */
67        if (isset($this->currentLevelNodes[$this->currentIndex])) {
68            $this->currentNode = $this->currentLevelNodes[$this->currentIndex++];
69            return;
70        }
71
72        /**
73         * if we are at the maximum level permitted in the search and there are no more nodes at this level to
74         * process, set valid to false and return
75         */
76
77        if ($this->atMaxLevels()) {
78            $this->invalidate();
79        }
80
81        /**
82         * otherwise populate $currentLevelNodes with the next level of nodes
83         */
84        else {
85            /**
86             * get the nodes on the next level of the tree
87             */
88            $this->currentLevelNodes = $this->getNextLevelOfNodes();
89            $this->setCurrentLevel(Direction::MOVE_DOWN);
90            /**
91             * rewind the current index and keep going
92             */
93            $this->currentIndex = 0;
94            $this->next();
95        }
96    }
97
98    /**
99     * getNextLevelOfNodes
100     * @return array<NodeSearchableInterface>
101     */
102    protected function getNextLevelOfNodes(): array
103    {
104        $getChildrenCallback = function (NodeSearchableInterface $node): array {
105            return $node->getChildrenArray();
106        };
107        $childArrays = array_map($getChildrenCallback, $this->currentLevelNodes);
108        /**
109         * splat operator is required to unpack the outer array
110         */
111        return array_merge(...$childArrays);
112    }
113}