Code Coverage |
||||||||||
Lines |
Functions and Methods |
Classes and Traits |
||||||||
| Total | |
72.22% |
13 / 18 |
|
50.00% |
1 / 2 |
CRAP | |
0.00% |
0 / 1 |
| DependencyResolver | |
72.22% |
13 / 18 |
|
50.00% |
1 / 2 |
12.14 | |
0.00% |
0 / 1 |
| resolve | |
100.00% |
5 / 5 |
|
100.00% |
1 / 1 |
3 | |||
| dependencyResolve | |
61.54% |
8 / 13 |
|
0.00% |
0 / 1 |
9.79 | |||
| 1 | <?php |
| 2 | /** |
| 3 | * Jingga |
| 4 | * |
| 5 | * PHP Version 8.1 |
| 6 | * |
| 7 | * @package phpOMS\Algorithm\Graph; |
| 8 | * @copyright Dennis Eichhorn |
| 9 | * @license OMS License 2.0 |
| 10 | * @version 1.0.0 |
| 11 | * @link https://jingga.app |
| 12 | */ |
| 13 | declare(strict_types=1); |
| 14 | |
| 15 | namespace phpOMS\Algorithm\Graph; |
| 16 | |
| 17 | /** |
| 18 | * Dependency resolver class. |
| 19 | * |
| 20 | * @package phpOMS\Algorithm\Graph; |
| 21 | * @license OMS License 2.0 |
| 22 | * @link https://jingga.app |
| 23 | * @since 1.0.0 |
| 24 | */ |
| 25 | final class DependencyResolver |
| 26 | { |
| 27 | /** |
| 28 | * Resolve dependencies |
| 29 | * |
| 30 | * @param array $graph Graph to resolve |
| 31 | * |
| 32 | * @return null|array |
| 33 | * |
| 34 | * @since 1.0.0 |
| 35 | */ |
| 36 | public static function resolve(array $graph) : ?array |
| 37 | { |
| 38 | $resolved = []; |
| 39 | $unresolved = []; |
| 40 | foreach ($graph as $table => $_) { |
| 41 | self::dependencyResolve($table, $graph, $resolved, $unresolved); |
| 42 | } |
| 43 | |
| 44 | return empty($unresolved) ? $resolved : null; |
| 45 | } |
| 46 | |
| 47 | /** |
| 48 | * Algorithm to resolve dependencies |
| 49 | * |
| 50 | * @param int|string $item Item id |
| 51 | * @param array<int|string, array> $items All items |
| 52 | * |
| 53 | * @return void |
| 54 | * |
| 55 | * @since 1.0.0 |
| 56 | */ |
| 57 | private static function dependencyResolve(int | string $item, array $items, array &$resolved, array &$unresolved) : void |
| 58 | { |
| 59 | $unresolved[] = $item; |
| 60 | |
| 61 | if (!isset($items[$item])) { |
| 62 | return; |
| 63 | } |
| 64 | |
| 65 | foreach ($items[$item] as $dependency) { |
| 66 | if (!\in_array($dependency, $unresolved)) { |
| 67 | $unresolved[] = $dependency; |
| 68 | self::dependencyResolve($dependency, $items, $resolved, $unresolved); |
| 69 | } else { |
| 70 | continue; // circular dependency |
| 71 | } |
| 72 | } |
| 73 | |
| 74 | if (!\in_array($item, $resolved)) { |
| 75 | $resolved[] = $item; |
| 76 | } |
| 77 | |
| 78 | foreach ($unresolved as $key => $unres) { |
| 79 | if ($unres === $item) { |
| 80 | unset($unresolved[$key]); |
| 81 | } |
| 82 | } |
| 83 | } |
| 84 | } |