Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
13 / 13
100.00% covered (success)
100.00%
1 / 1
 CRAP
100.00% covered (success)
100.00%
1 / 1
SearchDepthFirstPreorder
100.00% covered (success)
100.00%
13 / 13
100.00% covered (success)
100.00%
1 / 1
 7
100.00% covered (success)
100.00%
1 / 1
 getMovementDirection
100.00% covered (success)
100.00%
13 / 13
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     * @return Direction
24     *
25     * returns MOVE_DOWN if we should keep iterating by recursing down through child nodes,
26     * returns STOP if we should stop moving through nodes
27     * returns MOVE_UP if we should continue moving by returning up to the parent
28     *
29     * the goal is to stop every time we hit a node we have never visited.
30     *
31     * This method also changes the visit status of the current node.
32     *
33     * if node never visited, we go to partially visited and stop.
34     *
35     * if node partially visited and if all the children are fully visited, we go to fully visited and move up.
36     * if a node is partially visited and not all the children are fully visited then we move down
37     */
38    protected function getMovementDirection(): Direction
39    {
40        assert(!is_null($this->current()));
41
42        switch ($this->current()->getVisitStatus()) {
43
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(VisitStatus::PARTIALLY_VISITED);
52                $direction = ($this->current() == $this->getStartNode()) ? Direction::MOVE_DOWN : Direction::DONT_MOVE;
53                break;
54
55            /**
56             * if all the children are fully visited, or we are at the max search level, then we move to full visited
57             * otherwise we move down.  The default case should never be true, which is to say that we should never
58             * be moving into a node that is fully visited.  The default case is only there to satisfy the type checker
59             * that the $direction variable will have a value in all cases.
60             */
61            case VisitStatus::PARTIALLY_VISITED:
62            default:
63                if ($this->allChildrenFullyVisited() || $this->atMaxLevels()) {
64                    $this->current()->setVisitStatus(VisitStatus::FULLY_VISITED);
65                    $direction = Direction::MOVE_UP;
66                } else {
67                    $direction = Direction::MOVE_DOWN;
68                }
69                break;
70        }
71        return $direction;
72    }
73}