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     * @param NodeVisitableInterface $node
51     */
52    protected function initializeVisitStatusRecurse(NodeVisitableInterface $node): void
53    {
54        $node->initializeVisitStatus();
55        /** @var NodeVisitableInterface $child */
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        $nextNode = $this->getNextNode($direction);
112
113        if (is_null($nextNode)) {
114            $this->invalidate();
115        } else {
116            /**
117             * move
118             */
119            $this->setCurrent($nextNode);
120
121            /**
122             * adjust the current level
123             */
124            $this->setCurrentLevel($direction);
125        }
126    }
127
128    protected function getNextNode(Direction $direction): ?NodeVisitableInterface
129    {
130        switch ($direction) {
131            case Direction::DONT_MOVE:
132                $nextNode = $this->current();
133                break;
134            case Direction::MOVE_UP:
135                $nextNode = $this->getParent();
136                break;
137            case Direction::MOVE_DOWN:
138                $nextNode = $this->getNextVisitableChild();
139                /**
140                 * we add a node to the node map every time we move down.  The type checker cannot see the
141                 * logic in the subclass that guarantees $nextNode is not null if we are moving down
142                 */
143                assert(!is_null($nextNode));
144                $this->nodeMap->setNode($nextNode, $this->current()?->getNodeId());
145                break;
146        }
147        return $nextNode;
148    }
149
150    /**
151     * getParent
152     * @return NodeVisitableInterface|null
153     */
154    protected function getParent(): ?NodeVisitableInterface
155    {
156        if (is_null($nodeId = $this->current()?->getNodeId())) return null;
157        return $this->nodeMap->getParent($nodeId);
158    }
159
160    private function endOfSearch(): bool
161    {
162        return is_null($this->current());
163    }
164
165    /**
166     * allChildrenFullyVisited
167     * @return bool
168     * returns true if all children have been fully visited or if the node has no children
169     */
170    protected function allChildrenFullyVisited(): bool
171    {
172        return is_null($this->getNextVisitableChild());
173    }
174
175    /**
176     * getNextVisitableChild
177     * @return NodeVisitableInterface|null
178     */
179    protected function getNextVisitableChild(): ?NodeVisitableInterface
180    {
181        /** @var array<NodeVisitableInterface> $children */
182        $children = $this->current()?->getChildrenArray() ?: [];
183
184        $callback = function(NodeVisitableInterface $child) {
185            return ($child->getVisitStatus() != VisitStatus::FULLY_VISITED);
186        };
187        return array_find($children, $callback);
188    }
189}