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