DFSSorter::dfs() - Code Metrics - spiral/common - Measure and Improve Code Quality continuously with Scrutinizer

DFSSorter::dfs() A
last analyzed 2020-03-12 14:40 UTC

↳ Parent: DFSSorter

Complexity

Conditions	3
Paths	3

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	9
CRAP Score	3

Importance

Changes

Metric	Value
cc	3
nc	3
nop	2
dl	0
loc	16
rs	9.7333
c	0
b	0
f	0
ccs	9
cts	9
cp	1
crap	3

<?php
/**
 * Spiral Framework.
 *
 * @license   MIT
 * @author    Lev Seleznev
 */

namespace Spiral\Support;

/**
 * Topological Sorting vs Depth First Traversal (DFS)
 * https://en.wikipedia.org/wiki/Topological_sorting.
 */
class DFSSorter
{
    const STATE_NEW    = 1;
    const STATE_PASSED = 2;

    /**
     * @var array string[]
     */
    private $keys = [];

    /**
     * @var array
     */
    private $states = [];

    /**
     * @var array mixed[]
     */
    private $stack = [];

    /**
     * @var array mixed[]
     */
    private $objects = [];

    /**
     * @var array mixed[]
     */
    private $dependencies = [];

    /**
     * @param string $key          Item key, has to be used as reference in dependencies.
     * @param mixed  $item
     * @param array  $dependencies Must include keys object depends on.
     *
     * @return self
     */
    public function addItem(string $key, $item, array $dependencies): DFSSorter
    {
        $this->keys[] = $key;
        $this->objects[$key] = $item;
        $this->dependencies[$key] = $dependencies;

        return $this;
    }

    /**
     * Return sorted stack.
     *
     * @return array
     */
    public function sort(): array
    {
        $items = array_values($this->keys);

        $this->states = $this->stack = [];
        foreach ($items as $item) {
            $this->dfs($item, $this->dependencies[$item]);
        }

        return $this->stack;
    }

    /**
     * @param string $key
     * @param array  $dependencies
     */
    private function dfs(string $key, array $dependencies)
    {
        if (isset($this->states[$key])) {
            return;
        }

        $this->states[$key] = self::STATE_NEW;
        foreach ($dependencies as $dependency) {
            $this->dfs($dependency, $this->dependencies[$dependency]);
        }

        $this->stack[] = $this->objects[$key];
        $this->states[$key] = self::STATE_PASSED;

        return;
    }
}


1		<?php
2		/**
3		* Spiral Framework.
4		*
5		* @license MIT
6		* @author Lev Seleznev
7		*/
8
9		namespace Spiral\Support;
10
11		/**
12		* Topological Sorting vs Depth First Traversal (DFS)
13		* https://en.wikipedia.org/wiki/Topological_sorting.
14		*/
15		class DFSSorter
16		{
17		const STATE_NEW = 1;
18		const STATE_PASSED = 2;
19
20		/**
21		* @var array string[]
22		*/
23		private $keys = [];
24
25		/**
26		* @var array
27		*/
28		private $states = [];
29
30		/**
31		* @var array mixed[]
32		*/
33		private $stack = [];
34
35		/**
36		* @var array mixed[]
37		*/
38		private $objects = [];
39
40		/**
41		* @var array mixed[]
42		*/
43		private $dependencies = [];
44
45		/**
46		* @param string $key Item key, has to be used as reference in dependencies.
47		* @param mixed $item
48		* @param array $dependencies Must include keys object depends on.
49		*
50		* @return self
51		*/
52	3	public function addItem(string $key, $item, array $dependencies): DFSSorter
53		{
54	3	$this->keys[] = $key;
55	3	$this->objects[$key] = $item;
56	3	$this->dependencies[$key] = $dependencies;
57
58	3	return $this;
59		}
60
61		/**
62		* Return sorted stack.
63		*
64		* @return array
65		*/
66	3	public function sort(): array
67		{
68	3	$items = array_values($this->keys);
69
70	3	$this->states = $this->stack = [];
71	3	foreach ($items as $item) {
72	3	$this->dfs($item, $this->dependencies[$item]);
73		}
74
75	3	return $this->stack;
76		}
77
78		/**
79		* @param string $key
80		* @param array $dependencies
81		*/
82	3	private function dfs(string $key, array $dependencies)
83		{
84	3	if (isset($this->states[$key])) {
85	3	return;
86		}
87
88	3	$this->states[$key] = self::STATE_NEW;
89	3	foreach ($dependencies as $dependency) {
90	3	$this->dfs($dependency, $this->dependencies[$dependency]);
91		}
92
93	3	$this->stack[] = $this->objects[$key];
94	3	$this->states[$key] = self::STATE_PASSED;
95
96	3	return;
97		}
98		}
99

spiral / common

DFSSorter::dfs() A last analyzed 2020-03-12 14:40 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

DFSSorter::dfs() A
last analyzed 2020-03-12 14:40 UTC