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