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