DFSSorter::dfs() - Code Metrics - Inspection of "new isolator + isolator test" - spiral/components - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Branch — develop (85a9c8)

by Anton

created 2016-01-22 00:49 UTC

DFSSorter::dfs() A

↳ Parent: DFSSorter

Complexity

Conditions	3
Paths	3

Size

Total Lines	16
Code Lines	9

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
c	1
b	0
f	0
dl	0
loc	16
rs	9.4285
cc	3
eloc	9
nc	3
nop	2

<?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 $this
     */
    public function addItem($key, $item, array $dependencies)
    {
        $this->keys[] = $key;
        $this->objects[$key] = $item;
        $this->dependencies[$key] = $dependencies;

        return $this;
    }

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

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

        return $this->stack;
    }

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

spiral / components

Branch — develop (85a9c8)

DFSSorter::dfs() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like