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