Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
0.00% covered (danger)
0.00%
0 / 18
0.00% covered (danger)
0.00%
0 / 1
 CRAP
0.00% covered (danger)
0.00%
0 / 1
SearchDepthFirstPreorder
0.00% covered (danger)
0.00%
0 / 18
0.00% covered (danger)
0.00%
0 / 1
 56
0.00% covered (danger)
0.00%
0 / 1
 getMovementDirection
0.00% covered (danger)
0.00%
0 / 18
0.00% covered (danger)
0.00%
0 / 1
 56
1<?php
2
3/**
4 * @author: Doug Wilbourne (dougwilbourne@gmail.com)
5 */
6declare(strict_types=1);
7
8namespace pvc\struct\treesearch;
9
10use pvc\interfaces\struct\treesearch\NodeVisitableInterface;
11use pvc\interfaces\struct\treesearch\VisitStatus;
12
13/**
14 * Class SearchStrategyDepthFirstPreorder
15 * @template NodeId of array-key
16 * @template NodeType of NodeVisitableInterface
17 *
18 * @extends SearchDepthFirst<NodeId, NodeType>
19 */
20class SearchDepthFirstPreorder extends SearchDepthFirst
21{
22    /**
23     * getMovementDirection
24     *
25     * @return Direction
26     *
27     * returns MOVE_DOWN if we should keep iterating by recursing down through child nodes,
28     * returns STOP if we should stop moving through nodes
29     * returns MOVE_UP if we should continue moving by returning up to the parent
30     *
31     * the goal is to stop every time we hit a node we have never visited.
32     *
33     * This method also changes the visit status of the current node.
34     *
35     * if node never visited, we go to partially visited and stop.
36     *
37     * if node partially visited and if all the children are fully visited, we go to fully visited and move up.
38     * if a node is partially visited and not all the children are fully visited then we move down
39     */
40    protected function getMovementDirection(): Direction
41    {
42        assert(!is_null($this->current()));
43
44        switch ($this->current()->getVisitStatus()) {
45            /**
46             * in preorder mode, stop when we first encounter a node.  There's an initialization condition to
47             * account for:  rewind is called in the first iteration and next for all subsequent iterations.
48             * Because current has been called before next the first time around, the start node has already been
49             * returned, so we do not want to return it again.
50             */
51            case VisitStatus::NEVER_VISITED:
52                $this->current()->setVisitStatus(
53                    VisitStatus::PARTIALLY_VISITED
54                );
55                $direction = ($this->current() == $this->getStartNode())
56                    ? Direction::MOVE_DOWN : Direction::DONT_MOVE;
57                break;
58
59            /**
60             * if all the children are fully visited, or we are at the max search level, then we move to full visited
61             * otherwise we move down.  The default case should never be true, which is to say that we should never
62             * be moving into a node that is fully visited.  The default case is only there to satisfy the type checker
63             * that the $direction variable will have a value in all cases.
64             */
65            case VisitStatus::PARTIALLY_VISITED:
66            default:
67                if ($this->allChildrenFullyVisited() || $this->atMaxLevels()) {
68                    $this->current()->setVisitStatus(
69                        VisitStatus::FULLY_VISITED
70                    );
71                    $direction = Direction::MOVE_UP;
72                } else {
73                    $direction = Direction::MOVE_DOWN;
74                }
75                break;
76        }
77        return $direction;
78    }
79}