Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
41 / 41
100.00% covered (success)
100.00%
10 / 10
 CRAP
100.00% covered (success)
100.00%
1 / 1
SearchDepthFirst
100.00% covered (success)
100.00%
41 / 41
100.00% covered (success)
100.00%
10 / 10
 19
100.00% covered (success)
100.00%
1 / 1
 __construct
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
 1
 rewind
100.00% covered (success)
100.00%
3 / 3
100.00% covered (success)
100.00%
1 / 1
 1
 initializeVisitStatusRecurse
100.00% covered (success)
100.00%
3 / 3
100.00% covered (success)
100.00%
1 / 1
 2
 next
100.00% covered (success)
100.00%
7 / 7
100.00% covered (success)
100.00%
1 / 1
 3
 getMovementDirection
n/a
0 / 0
n/a
0 / 0
 0
 move
100.00% covered (success)
100.00%
5 / 5
100.00% covered (success)
100.00%
1 / 1
 2
 getNextNode
100.00% covered (success)
100.00%
12 / 12
100.00% covered (success)
100.00%
1 / 1
 4
 getParent
100.00% covered (success)
100.00%
2 / 2
100.00% covered (success)
100.00%
1 / 1
 2
 endOfSearch
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
 1
 allChildrenFullyVisited
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
 1
 getNextVisitableChild
100.00% covered (success)
100.00%
6 / 6
100.00% covered (success)
100.00%
1 / 1
 2
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\NodeMapInterface;
12use pvc\interfaces\struct\treesearch\NodeVisitableInterface;
13use pvc\interfaces\struct\treesearch\VisitStatus;
14use pvc\struct\treesearch\err\StartNodeUnsetException;
15
16/**
17 * Class SearchDepthFirst
18 * @template NodeType of NodeVisitableInterface
19 * @extends SearchAbstract<NodeType>
20 */
21abstract class SearchDepthFirst extends SearchAbstract
22{
23    /**
24     * @param NodeMapInterface<NodeType> $nodeMap
25     */
26    public function __construct(protected NodeMapInterface $nodeMap)
27    {
28    }
29
30    /**
31     * rewind
32     * @throws StartNodeUnsetException
33     */
34    public function rewind(): void
35    {
36        parent::rewind();
37
38        /**
39         * set the visit status of all the nodes to NEVER_VISITED
40         */
41        $this->initializeVisitStatusRecurse($this->getStartNode());
42
43        /**
44         * initialize the node map
45         */
46        $this->nodeMap->initialize($this->getStartNode());
47    }
48
49    /**
50     * initializeVisitStatusRecurse
51     *
52     * @param  NodeType  $node
53     */
54    protected function initializeVisitStatusRecurse(NodeVisitableInterface $node): void
55    {
56        $node->initializeVisitStatus();
57        /** @var NodeType $child */
58        foreach ($node->getChildrenArray() as $child) {
59            $this->initializeVisitStatusRecurse($child);
60        }
61    }
62
63    /**
64     * next
65     * rewind fails if there is no start node.  If start node is set then
66     * you can always move, knowing the "moving" can simply be updating the visit status of
67     * the current node from never visited to partially visited to fully visited
68     */
69    public function next(): void
70    {
71        $direction = $this->getMovementDirection();
72        $this->move($direction);
73
74        if ($this->endOfSearch()) {
75            $this->invalidate();
76            $direction = Direction::DONT_MOVE;
77        }
78
79        /**
80         * move until the direction says stop
81         */
82        if ($direction != Direction::DONT_MOVE) {
83            $this->next();
84        }
85    }
86
87    /**
88     * getMovementDirection
89     * @return Direction
90     *
91     * returns MOVE_DOWN if we should keep iterating by recursing down through child nodes,
92     * returns STOP if we should stop iterating
93     * returns MOVE_UP if we should continue iterating by returning up to the parent
94     */
95    abstract protected function getMovementDirection(): Direction;
96    
97    /**
98     * move
99     * @return void
100     *
101     * you can move up, move down, or you can "move nowhere", which simply updates the visitation status.  The
102     * getDirection method is sensitive to the max levels property and will not allow a move 'below' max levels
103     * or 'above' startnode.
104     *
105     * returns true if we should stop moving through the tree and return current.
106     * returns false if we should keep moving through the tree
107     */
108    protected function move(Direction $direction): void
109    {
110        /**
111         * get the next node (could be null at the end of a search)
112         */
113        /** @var ?NodeType $nextNode */
114        $nextNode = $this->getNextNode($direction);
115
116        if (is_null($nextNode)) {
117            $this->invalidate();
118        }
119        else {
120            /**
121             * move
122             */
123            $this->setCurrent($nextNode);
124
125            /**
126             * adjust the current level
127             */
128            $this->setCurrentLevel($direction);
129        }
130    }
131
132    /**
133     * @param  Direction  $direction
134     *
135     * @return NodeType|null
136     */
137    protected function getNextNode(Direction $direction): ?NodeVisitableInterface
138    {
139        switch ($direction) {
140            case Direction::DONT_MOVE:
141                $nextNode = $this->current();
142                break;
143            case Direction::MOVE_UP:
144                $nextNode = $this->getParent();
145                break;
146            case Direction::MOVE_DOWN:
147                $nextNode = $this->getNextVisitableChild();
148                /**
149                 * we add a node to the node map every time we move down.  The type checker cannot see the
150                 * logic in the subclass that guarantees $nextNode is not null if we are moving down
151                 */
152                assert(!is_null($nextNode));
153                $this->nodeMap->setNode($nextNode, $this->current()?->getNodeId());
154                break;
155        }
156        return $nextNode;
157    }
158
159    /**
160     * getParent
161     * @return NodeType|null
162     */
163    protected function getParent(): ?NodeVisitableInterface
164    {
165        if (is_null($nodeId = $this->current()?->getNodeId())) return null;
166        return $this->nodeMap->getParent($nodeId);
167    }
168
169    private function endOfSearch(): bool
170    {
171        return is_null($this->current());
172    }
173
174    /**
175     * allChildrenFullyVisited
176     * @return bool
177     * returns true if all children have been fully visited or if the node has no children
178     */
179    protected function allChildrenFullyVisited(): bool
180    {
181        return is_null($this->getNextVisitableChild());
182    }
183
184    /**
185     * getNextVisitableChild
186     * @return NodeType|null
187     */
188    protected function getNextVisitableChild(): ?NodeVisitableInterface
189    {
190        /** @var array<NodeVisitableInterface> $children */
191        $children = $this->current()?->getChildrenArray() ?: [];
192
193        $callback = function(NodeVisitableInterface $child) {
194            return ($child->getVisitStatus() != VisitStatus::FULLY_VISITED);
195        };
196        /** @var ?NodeType $result */
197        $result = array_find($children, $callback);
198        return $result;
199    }
200}